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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

I enabled logging of time stats.  Then I loaded a single late-game
savegame with a very large civ.

Current code:

2: CM-opt: overall=10.312096s queries=170 60.659388ms / query, 22538 applies

Greedy patch with do_full_search enabled (should be identical):

2: CM-opt: overall=9.993475s queries=170 58.785147ms / query, 22538 applies

(any speed difference here is just normal variation.)

Greedy patch with do_full_search disabled (should be much faster):

2: CM-opt: overall=0.057328s queries=137 0.418453ms / query, 349 applies

So indeed it is a fair bit faster.  Looking around at the various cities
I can't tell any difference in accuracy (the first correct solution is
usually the best one).

Notes:

1.  It's not truly greedy.  It doesn't take the first solution but the
first satisfactory one (that meets the minimums).  Usually this makes no
difference.

2.  My original patch was quite buggy because it did "return FALSE"
instead of "return TRUE" causing the CM to simply lock up - oops.  Also
it didn't work with CMA because CMA didn't use cm_init_parameter
correctly.  This patch fixes both.

3.  I think these numbers show the B&B algorithm to be flexible enough
to meet all of our needs.  Of course you AI guys should test this on
your own.

-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:31:26 -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:31:27 -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,11 @@
       copy_partial_solution(&state->best, &state->current, state);
       state->best_value = value;
     }
+    if (state->best_value.sufficient
+       && !state->parameter.do_full_search) {
+      /* Short-cut the result of the search and just take this solution! */
+      return TRUE;
+    }
   }
 
   /* try to move to a child branch, if we can.  If not (including if we're
@@ -1851,6 +1856,8 @@
   memcpy(dest, src, sizeof(struct cm_parameter));
 }
 
+#define DEFAULT_DO_FULL_SEARCH FALSE
+
 /**************************************************************************
   Initialize the parameter to sane default values.
 **************************************************************************/
@@ -1865,6 +1872,8 @@
   dest->require_happy = FALSE;
   dest->allow_disorder = FALSE;
   dest->allow_specialists = TRUE;
+
+  dest->do_full_search = DEFAULT_DO_FULL_SEARCH;
 }
 
 /***************************************************************************
@@ -1882,6 +1891,8 @@
   dest->require_happy = FALSE;
   dest->allow_disorder = TRUE;
   dest->allow_specialists = TRUE;
+
+  dest->do_full_search = 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:31:27 -0000
@@ -36,6 +36,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. */
+  bool do_full_search;
+
   int factor[O_MAX];
   int happy_factor;
 };