[freeciv-ai] (PR#11509) a greedy CM

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=11509 >

As I said before it's not truly greedy, it'll take the first sufficient
solution.  For CMA this is great, but for AI it's not so good because if
there is no sufficient solution the full algorithm will run (with CMA
this will only happen once, then the city is released).

So this patch makes it a tri-state setting:
  - Take first solution.
  - Take first sufficient solution.
  - Take best solution.

In most cases the first two will be the same.  In most cases all three
will give the same solution.  In a few cases #2 will be slower than #1.
 #3 will always be slower than #1 and usually slower than #2.  In a few
cases #3 will be better than #2, and in a few cases #2 will be better
than #1.  ("better" meaning more correct.)

Remember that #1 is insanely faster than #3, since it's linear rather
than exponential.  With large cities (as in my earlier test) it could be
100x faster.  With _very_ large cities, maybe up to 1000x faster.

Oh, and using #1 with my previous timing savegame (CMA) gives:

2: CM-opt: overall=0.042907s queries=137 0.313190ms / query, 274 applies

which isn't really worth it (as I said, #2 is better than #1 for CMA).

-jason

Index: client/agents/cma_core.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/agents/cma_core.c,v
retrieving revision 1.74
diff -u -r1.74 cma_core.c
--- client/agents/cma_core.c    21 Mar 2005 17:34:27 -0000      1.74
+++ client/agents/cma_core.c    11 Apr 2005 16:47:49 -0000
@@ -582,6 +582,10 @@
   dio_get_uint8(&din, &version);
   assert(version == 2);
 
+  /* Initialize the parameter (includes some AI-only fields that aren't
+   * touched below). */
+  cm_init_parameter(parameter);
+
   output_type_iterate(i) {
     dio_get_sint16(&din, &parameter->minimal_surplus[i]);
     dio_get_sint16(&din, &parameter->factor[i]);
@@ -590,9 +594,6 @@
   dio_get_sint16(&din, &parameter->happy_factor);
   dio_get_uint8(&din, &dummy); /* Dummy value; used to be factor_target. */
   dio_get_bool8(&din, &parameter->require_happy);
-  /* These options are only for server-AI use. */
-  parameter->allow_disorder = FALSE;
-  parameter->allow_specialists = TRUE;
 
   return TRUE;
 }
Index: common/aicore/cm.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/cm.c,v
retrieving revision 1.62
diff -u -r1.62 cm.c
--- common/aicore/cm.c  7 Apr 2005 04:36:02 -0000       1.62
+++ common/aicore/cm.c  11 Apr 2005 16:47:49 -0000
@@ -91,7 +91,7 @@
    if GATHER_TIME_STATS is on */
 #define PRINT_TIME_STATS_EVERY_QUERY
 
-#define LOG_TIME_STATS                                  LOG_DEBUG
+#define LOG_TIME_STATS                                  LOG_NORMAL
 #define LOG_CM_STATE                                    LOG_DEBUG
 #define LOG_LATTICE                                     LOG_DEBUG
 #define LOG_REACHED_LEAF                                LOG_DEBUG
@@ -1648,6 +1648,21 @@
       copy_partial_solution(&state->best, &state->current, state);
       state->best_value = value;
     }
+    switch (state->parameter.search_type) {
+    case SEARCH_FIRST_SOLUTION:
+      /* Short-cut the result of the search and take the first solution! */
+      return TRUE;
+    case SEARCH_FIRST_SUFFICIENT_SOLUTION:
+      if (state->best_value.sufficient) {
+       /* Short-cut the result of the search and just take the first
+        * sufficient solution! */
+       return TRUE;
+      }
+      break;
+    case SEARCH_BEST_SOLUTION:
+      /* Continue with the search until it's done. */
+      break;
+    }
   }
 
   /* try to move to a child branch, if we can.  If not (including if we're
@@ -1851,6 +1866,8 @@
   memcpy(dest, src, sizeof(struct cm_parameter));
 }
 
+#define DEFAULT_DO_FULL_SEARCH SEARCH_FIRST_SOLUTION
+
 /**************************************************************************
   Initialize the parameter to sane default values.
 **************************************************************************/
@@ -1865,6 +1882,8 @@
   dest->require_happy = FALSE;
   dest->allow_disorder = FALSE;
   dest->allow_specialists = TRUE;
+
+  dest->search_type = DEFAULT_DO_FULL_SEARCH;
 }
 
 /***************************************************************************
@@ -1882,6 +1901,8 @@
   dest->require_happy = FALSE;
   dest->allow_disorder = TRUE;
   dest->allow_specialists = TRUE;
+
+  dest->search_type = DEFAULT_DO_FULL_SEARCH;
 }
 
 /****************************************************************************
Index: common/aicore/cm.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/cm.h,v
retrieving revision 1.13
diff -u -r1.13 cm.h
--- common/aicore/cm.h  3 Dec 2004 09:39:41 -0000       1.13
+++ common/aicore/cm.h  11 Apr 2005 16:47:49 -0000
@@ -29,6 +29,12 @@
 #include "city.h"              /* CITY_MAP_SIZE */
 #include "shared.h"            /* bool type */
 
+enum cm_search_type {
+  SEARCH_FIRST_SOLUTION, /* Fast, usually correct */
+  SEARCH_FIRST_SUFFICIENT_SOLUTION, /* Usually fast, more correct */
+  SEARCH_BEST_SOLUTION /* Slow, always correct */
+};
+
 /* A description of the goal. */
 struct cm_parameter {
   int minimal_surplus[O_MAX];
@@ -36,6 +42,12 @@
   bool allow_disorder;
   bool allow_specialists;
 
+  /* If set, a full search is done.  This takes exponential time but will
+   * always find the best solution.  If unset, the first solution will be
+   * taken.  This gives the wrong result 1% of the time but takes only
+   * linear time. */
+  enum cm_search_type search_type;
+
   int factor[O_MAX];
   int happy_factor;
 };