[Freeciv-Dev] (PR#11509) a greedy CM

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Mike pointed out that for AIs on lower difficulty levels we should just 
do a greedy CM.  It occurred to me that with the current greedy-ish b&b 
algorithm this will only take a couple of lines of code.

This patch adds a new parameter do_full_search to the CM parameter.  It 
defaults to TRUE.  But if you set it to FALSE then the first sufficient 
solution found will be accepted.  99% of the time this will be the best 
solution, and the remaining 1% doesn't really matter at all for easy and 
normal AI.

It is untested.

-jason

Index: common/aicore/cm.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/aicore/cm.c,v
retrieving revision 1.54
diff -u -r1.54 cm.c
--- common/aicore/cm.c  13 Dec 2004 16:23:30 -0000      1.54
+++ common/aicore/cm.c  14 Dec 2004 06:43:03 -0000
@@ -1644,6 +1644,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 FALSE;
+    }
   }
 
   /* try to move to a child branch, if we can.  If not (including if we're
@@ -1856,6 +1861,8 @@
   dest->require_happy = FALSE;
   dest->allow_disorder = FALSE;
   dest->allow_specialists = TRUE;
+
+  dest->do_full_search = TRUE;
 }
 
 /***************************************************************************
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  14 Dec 2004 06:43:03 -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;
 };