[Freeciv-Dev] (PR#7007) CM speedup patch: pruning on primary stat production

["Benoit Hudson" <bh@xxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=7007 >

This patch provides pruning based on primary stats not being
statisfiable.

What it adds:
- enum cm_answer = { YES,NO, MAYBE}
        Useful for questions like "can I satisfy this constraint?"
        I use it in this patch, and I'll use it in other patches.

- optimize_final runs in backwards order (more fields to less);
  If no combination using i fields produces enough primary stats, then
  we know that no combination using i-1 fields works so we can just quit
  the loop now.  I take care of the problem of disorder correctly (far
  as I know; see the comments in the new function
  result_has_sufficient_primary for details).

- more comments in optimize_final.

Profiling shows that we thusly ignore slightly less than 10% of the
combinations we would otherwise check, reducing the number of calls to
real_fill_out_result (the most costly per-call function) by over 10%.
This is in an all-AI game to 500 AD ; humans building big cities should
see larger savings.

        -- Benoît

Index: cm.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/cm.c,v
retrieving revision 1.18
diff -b -c -3 -p -u -r1.18 cm.c
--- cm.c        2003/11/22 16:32:01     1.18
+++ cm.c        2003/11/30 23:14:36
@@ -152,6 +152,42 @@
 #define MAX_COMBINATIONS                               150

 /*
+ * Useful in asking cheap questions to avoid asking an expensive one:
+ * YES/NO are definitive, MAYBE means we have to ask the expensive
+ * question.
+ * Note: none of these is zero.  This means we can't usefully use
+ * operator ! on them as we can on a bool.  This is by design: what
+ * does !MAYBE mean?
+ */
+enum cm_answer { YES=1, NO=2, MAYBE=3 };
+
+/* Return the max of a1 and a2, according to NO < MAYBE < YES.
+   This roughly corresponds to a boolean OR. */
+static enum cm_answer answer_or(enum cm_answer a1, enum cm_answer a2) {
+  if(a1==YES || a2==YES) {
+    return YES;
+  }
+  if(a1==MAYBE || a2==MAYBE) {
+    return MAYBE;
+  }
+  return NO;
+}
+
+/* Return the max of a1 and a2, according to YES < MAYBE < NO.
+   This roughly corresponds to a boolean AND. */
+#if 0
+static enum cm_answer answer_and(enum cm_answer a1, enum cm_answer a2) {
+  if(a1==NO || a2==NO) {
+    return NO;
+  }
+  if(a1==MAYBE || a2==MAYBE) {
+    return MAYBE;
+  }
+  return YES;
+}
+#endif
+
+/*
  * Maps (trade, taxmen) -> (gold_production, gold_surplus)
  * Maps (trade, entertainers) -> (luxury_production, luxury_surplus)
  * Maps (trade, scientists) -> (science_production, science_surplus)
@@ -317,6 +353,54 @@ static bool can_use_specialist(struct ci
 }

 /****************************************************************************
+  Like is_valid but only looks at primary stats (food/shields/trade).
+  Mostly ignores disorder/happy, totally ignores secondary stats.
+  We only mostly ignore disorder in that a city in disorder may
+  have sufficient primary production, but the surplus may be capped to zero,
+  which may be insufficient.  In that case we return MAYBE.
+*****************************************************************************/
+static enum cm_answer result_has_sufficient_primary(
+        const struct cm_parameter *const parameter,
+        const struct cm_result *const result)
+{
+  enum cm_stat stat;
+  for(stat=0; stat<NUM_PRIMARY_STATS; ++stat) {
+    if(result->surplus[stat] < parameter->minimal_surplus[stat]) {
+      if(!result->disorder) {
+        return NO;
+      }
+      else {
+        /* city is in disorder: food/shields capped to zero. */
+        if(result->surplus[stat]!=0) {
+          /* this is the true surplus; if it's not sufficient we're hosed. */
+          return NO;
+        } else {
+          /* surplus is zero; so it could actually be anything positive */
+          return MAYBE;
+        }
+      }
+    }
+  }
+  return YES;
+}
+
+/****************************************************************************
+  Return TRUE iff the city is sufficiently happy.
+*****************************************************************************/
+static bool result_has_sufficient_happiness(
+        const struct cm_parameter *const parameter,
+        const struct cm_result *const result)
+{
+  if (!parameter->allow_disorder && result->disorder) {
+    return FALSE;
+  }
+  if (parameter->require_happy && !result->happy) {
+    return FALSE;
+  }
+  return TRUE;
+}
+
+/****************************************************************************
  Returns TRUE iff is the result has the required surplus and the city
  isn't in disorder and the city is happy if this is required.
 *****************************************************************************/
@@ -331,10 +415,7 @@ static bool is_valid_result(const struct
     return FALSE;
   }

-  if (!parameter->allow_disorder && result->disorder) {
-    return FALSE;
-  }
-  if (parameter->require_happy && !result->happy) {
+  if(result_has_sufficient_happiness(parameter, result) == FALSE) {
     return FALSE;
   }

@@ -1327,6 +1408,7 @@ static void optimize_final(struct city *
 {
   int fields_used, i;
   int results_used = 0, not_enough_primary = 0, not_enough_secondary = 0;
+  int not_enough_happiness = 0;
   /* Just for the compiler. Guarded by best_result->found_a_valid */
   int best_major_fitness = 0, best_minor_fitness = 0;

@@ -1334,10 +1416,13 @@ static void optimize_final(struct city *

   best_result->found_a_valid = FALSE;

-  /* Loop over all combinations */
-  for (fields_used = 0;
-       fields_used <= MIN(cache3.fields_available_total, pcity->size);
-       fields_used++) {
+  /* Loop over all combinations, backwards so we can prune. */
+  for (fields_used = MIN(cache3.fields_available_total, pcity->size);
+       fields_used >= 0;
+       fields_used--) {
+    /* if no combo had enough primary with i fields, then no combo
+       with i-1 fields can possibly have enough primary stats. */
+    enum cm_answer one_combo_had_enough_primary = NO;
     freelog(OPTIMIZE_FINAL_LOG_LEVEL,
            "there are %d combinations which use %d fields",
            count_valid_combinations(fields_used), fields_used);
@@ -1346,6 +1431,7 @@ static void optimize_final(struct city *
          &cache3.results[fields_used].combinations[i];
       int stat, major_fitness, minor_fitness;
       struct cm_result result;
+      enum cm_answer sufficient;

       if (!current->is_valid) {
        continue;
@@ -1371,19 +1457,44 @@ static void optimize_final(struct city *
       }

       /*
-       * the secondary stats aren't calculated yet but we want to use
-       * is_valid_result()
+       * Check whether we have enough primary.
+       * If NO, we don't, so skip to the next combo.
+       * If MAYBE, we might if we could make the city content, but we
+       *        already have all elvises so we can't.
+       * If YES, we do, so keep going.
+       *
+       * In any case, update whether some combo had enough primary.
+       * It's in updating this that MAYBE is useful.
        */
-      result.surplus[GOLD] = parameter->minimal_surplus[GOLD];
-      result.surplus[LUXURY] = parameter->minimal_surplus[LUXURY];
-      result.surplus[SCIENCE] = parameter->minimal_surplus[SCIENCE];
+      sufficient = result_has_sufficient_primary(parameter, &result);

-      if (!is_valid_result(parameter, &result)) {
+      one_combo_had_enough_primary = answer_or(sufficient,
+          one_combo_had_enough_primary);
+
+      switch(sufficient) {
+        case NO:
+        case MAYBE:
        not_enough_primary++;
        freelog(OPTIMIZE_FINAL_LOG_LEVEL2, "    not enough primary");
+          continue; /* the for loop. */
+        case YES:
+          break; /* the switch statement. */
+      }
+
+      /*
+       * Check for sufficient happiness.  If we're not
+       * sufficiently happy with all elvises we're hosed.
+       */
+      if(result_has_sufficient_happiness(parameter, &result)==FALSE) {
+       freelog(OPTIMIZE_FINAL_LOG_LEVEL2, "    not enough happiness");
+        not_enough_happiness++;
        continue;
       }

+
+      /*
+       * Find how to best set up specialists (rather than all elvises).
+       */
       find_best_specialist_arrangement(pcity, parameter, current, &result,
                                       &major_fitness, &minor_fitness);
       if (!result.found_a_valid) {
@@ -1406,15 +1517,26 @@ static void optimize_final(struct city *
       } else {
        freelog(OPTIMIZE_FINAL_LOG_LEVEL2,
                "    isn't better than the best result");
-      }
     }
+    } /* end loop over combinations, for a fixed number of fields. */
+
+    /* If no combination had enough primary, don't bother trying with
+       fewer workers.  A MAYBE result means fewer workers might
+       be OK as long as we can eliminate disorder. */
+    if(one_combo_had_enough_primary==NO) {
+      break;
   }
+  } /* end loop over number of fields. */

   freelog(OPTIMIZE_FINAL_LOG_LEVEL,
          "%d combinations don't have the required minimal primary surplus",
          not_enough_primary);

   freelog(OPTIMIZE_FINAL_LOG_LEVEL,
+         "%d combinations don't have the required minimal happiness",
+         not_enough_happiness);
+
+  freelog(OPTIMIZE_FINAL_LOG_LEVEL,
          "%d combinations don't have the required minimal secondary surplus",
          not_enough_secondary);