[gnugo-devel] influence and move valuation patch

[Gunnar Farneback]

As some people may have noticed, e.g. on NNGS, GNU Go 3.1.13 has some
rather serious problems with the endgame. This is an old defect in the
influence code that has become more visible since the computation of
territorial value was moved to entirely be done by the influence code
(new in 3.1.13). I know how to fix this, but it will require a few
patches to do it. The first one is appended below and does some
preparations for the real fixes.

* The influence_value part of the move valuation has been removed.
  Instead that part is included in the territorial_value. It didn't
  really make much sense to keep them apart and was more confusing
  than anything else.

* The delta_territory computation in influence.c has been
  restructured, simplifying the code a lot. It now also includes the
  changes in moyo and area of course. 

* To see what vertices on the board contribute to the "change in
  territory" value, use the -d0x100000 option, DEBUG_TERRITORY.

I have added the patch to CVS.

/Gunnar

Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.21
diff -u -r1.21 gnugo.h
--- engine/gnugo.h      2001/10/18 15:40:56     1.21
+++ engine/gnugo.h      2001/11/10 18:54:16
@@ -212,26 +212,27 @@
 
 /* debug flag bits */
 /* NOTE : can specify -d0x... */
-#define DEBUG_INFLUENCE           0x00001
-#define DEBUG_EYES                0x00002
-#define DEBUG_OWL                 0x00004
-#define DEBUG_ESCAPE              0x00008
-#define DEBUG_MATCHER             0x00010
-#define DEBUG_DRAGONS             0x00020
-#define DEBUG_SEMEAI              0x00040
-#define DEBUG_LOADSGF             0x00080
-#define DEBUG_HELPER              0x00100
-#define DEBUG_READING             0x00200
-#define DEBUG_WORMS               0x00400
-#define DEBUG_MOVE_REASONS        0x00800
-#define DEBUG_OWL_PERFORMANCE     0x01000
-#define DEBUG_LIFE                0x02000
-#define DEBUG_FILLLIB             0x04000
-#define DEBUG_READING_PERFORMANCE 0x08000
-#define DEBUG_SCORING             0x10000
-#define DEBUG_AFTERMATH           0x20000
-#define DEBUG_ATARI_ATARI         0x40000
-#define DEBUG_READING_CACHE       0x80000
+#define DEBUG_INFLUENCE           0x0001
+#define DEBUG_EYES                0x0002
+#define DEBUG_OWL                 0x0004
+#define DEBUG_ESCAPE              0x0008
+#define DEBUG_MATCHER             0x0010
+#define DEBUG_DRAGONS             0x0020
+#define DEBUG_SEMEAI              0x0040
+#define DEBUG_LOADSGF             0x0080
+#define DEBUG_HELPER              0x0100
+#define DEBUG_READING             0x0200
+#define DEBUG_WORMS               0x0400
+#define DEBUG_MOVE_REASONS        0x0800
+#define DEBUG_OWL_PERFORMANCE     0x1000
+#define DEBUG_LIFE                0x2000
+#define DEBUG_FILLLIB             0x4000
+#define DEBUG_READING_PERFORMANCE 0x8000
+#define DEBUG_SCORING             0x010000
+#define DEBUG_AFTERMATH           0x020000
+#define DEBUG_ATARI_ATARI         0x040000
+#define DEBUG_READING_CACHE       0x080000
+#define DEBUG_TERRITORY           0x100000
 /* hash flag bits 
  *
  * Regarding HASH_DEFAULT:
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.17
diff -u -r1.17 influence.c
--- engine/influence.c  2001/11/09 19:03:43     1.17
+++ engine/influence.c  2001/11/10 18:54:17
@@ -31,6 +31,7 @@
 #include "influence.h"
 #include "patterns.h"
 
+static void value_territory(struct influence_data *q);
 static void segment_influence(struct influence_data *q);
 static void print_influence(struct influence_data *q, int dragons_known);
 static void print_numeric_influence(struct influence_data *q,
@@ -57,7 +58,7 @@
 static struct influence_data escape_influence;
 
 /* Cache of delta_territory_values. */
-static int delta_territory_cache[BOARDMAX];
+static float delta_territory_cache[BOARDMAX];
 
 /* If set, print influence map when computing this move. Purely for
  * debugging.
@@ -769,6 +770,7 @@
       if (q->black_strength[i][j] > 0.0)
        accumulate_influence(q, i, j, BLACK);
     }
+  value_territory(q);
   segment_influence(q);
   /* FIXME: The "board_size - 19" stuff below is an ugly workaround for a bug
    *        in main.c
@@ -890,6 +892,59 @@
   return EMPTY;
 }
 
+/* Give territorial value to each vertex.
+ *
+ * A vertex with a lively stone has territorial value of 0.
+ * For other vertices the value is
+ * 1 if the vertex is classified as territory.
+ * 0.35 if it is classified as moyo
+ * 0.13 if it is classified as area
+ * 0.0 if it is classified as neutral
+ * One point is added for a vertex with a dead stone.
+ * Furthermore black points have a negative sign.
+ *
+ * The results are written to the territory_value[][] array of the
+ * influence data.
+ */
+static void
+value_territory(struct influence_data *q)
+{
+  int i, j;
+  for (i = 0; i < board_size; i++)
+    for (j = 0; j < board_size; j++) {
+      q->territory_value[i][j] = 0.0;
+
+      if (q->p[i][j] == EMPTY
+         || (q->black_strength[i][j] == 0 && q->white_strength[i][j] == 0)) {
+       int owner = whose_territory(q, i, j);
+       if (owner == BLACK)
+         q->territory_value[i][j] = -1.0;
+       else if (owner == WHITE)
+         q->territory_value[i][j] = 1.0;
+       else {
+         owner = whose_moyo(q, i, j);
+         if (owner == BLACK)
+           q->territory_value[i][j] = -0.35;
+         else if (owner == WHITE)
+           q->territory_value[i][j] = 0.35;
+         else {
+           owner = whose_moyo(q, i, j);
+           if (owner == BLACK)
+             q->territory_value[i][j] = -0.13;
+           else if (owner == WHITE)
+             q->territory_value[i][j] = 0.13;
+         }
+       }
+       /* Dead stone, add one to the territory value. */
+       if (BOARD(i, j) == BLACK)
+         q->territory_value[i][j] += 1.0;
+       else if (BOARD(i, j) == WHITE)
+         q->territory_value[i][j] -= 1.0;
+      }
+    }
+}
+
+
 /* Segment the influence map into connected regions of territory,
  * moyo, or area. What to segment on is determined by the the function
  * pointer region_owner. The segmentation is performed for both
@@ -1104,86 +1159,6 @@
 }
 
 
-/* Count the amount of territory for color. */
-static int
-sum_territory(struct influence_data *q, int color)
-{
-  int i, j;
-  int territory = 0;
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++)
-      if ((q->p[i][j] == EMPTY ||
-          (q->black_strength[i][j] == 0 && q->white_strength[i][j] == 0))
-         && whose_territory(q, i, j) == color) {
-       territory++;
-       if (board[POS(i, j)] != EMPTY)
-         territory++;
-      }
-  return territory;
-}
-
-/* Count the amount of moyo for color. */
-static int
-sum_moyo(struct influence_data *q, int color)
-{
-  int i, j;
-  int moyo = 0;
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++)
-      if ((q->p[i][j] == EMPTY ||
-          (q->black_strength[i][j] == 0 && q->white_strength[i][j] == 0))
-         && whose_moyo(q, i, j) == color)
-       moyo++;
-  return moyo;
-}
-
-/* Count the amount of moyo, that is not also territory, for color. */
-static int
-sum_strict_moyo(struct influence_data *q, int color)
-{
-  int i, j;
-  int moyo = 0;
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++)
-      if ((q->p[i][j] == EMPTY ||
-          (q->black_strength[i][j] == 0 && q->white_strength == 0))
-         && whose_moyo(q, i, j) == color
-         && whose_territory(q, i, j) != color)
-       moyo++;
-  return moyo;
-}
-
-/* Count the amount of area for color. */
-static int
-sum_area(struct influence_data *q, int color)
-{
-  int i, j;
-  int area = 0;
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++)
-      if ((q->p[i][j] == EMPTY
-          || (q->black_strength[i][j] == 0 && q->white_strength == 0))
-         && whose_area(q, i, j) == color)
-       area++;
-  return area;
-}
-
-/* Count the amount of area, that is not also moyo, for color. */
-static int
-sum_strict_area(struct influence_data *q, int color)
-{
-  int i, j;
-  int area = 0;
-  for (i = 0; i < board_size; i++)
-    for (j = 0; j < board_size; j++)
-      if ((q->p[i][j] == EMPTY ||
-          (q->black_strength[i][j] == 0 && q->white_strength == 0))
-         && whose_area(q, i, j) == color
-         && whose_moyo(q, i, j) != color)
-       area++;
-  return area;
-}
-
 /* Return the color who has territory at pos, or EMPTY. */
 int
 influence_territory_color(int pos)
@@ -1205,107 +1180,45 @@
   return whose_area(&initial_influence, I(pos), J(pos));
 }
 
-/* Compute the difference in territory made by a move by color at (pos). */
-int
-influence_delta_territory(int pos, int color,
-                         char saved_stones[BOARDMAX])
+/* Compute the difference in territory made by a move by color at (pos).
+ * This also includes the changes in moyo and area.
+ */
+float
+influence_delta_territory(int pos, int color, char saved_stones[BOARDMAX])
 {
-  int delta;
+  int i, j;
+  float delta = 0.0;
   if (delta_territory_cache[pos] != NOT_COMPUTED)
     return delta_territory_cache[pos];
   if (0)
     gprintf("influence_delta_territory for %1m %s = ", pos,
            color_to_string(color));
   compute_move_influence(I(pos), J(pos), color, saved_stones);
-  delta = (sum_territory(&move_influence, color) -
-          sum_territory(&initial_influence, color) -
-          sum_territory(&move_influence, OTHER_COLOR(color)) +
-          sum_territory(&initial_influence, OTHER_COLOR(color)));
-  if (0)
-    gprintf("%d\n", delta);
-  delta_territory_cache[pos] = delta;
-  return delta;
-}
-
-/* Compute the difference in moyo made by a move by color at pos. */
-int
-influence_delta_moyo(int pos, int color,
-                    char saved_stones[BOARDMAX])
-{
-  int delta;
-  if (0)
-    gprintf("influence_delta_moyo for %1m %s = ", pos,
-           color_to_string(color));
-  compute_move_influence(I(pos), J(pos), color, saved_stones);
-  delta = (sum_moyo(&move_influence, color) -
-          sum_moyo(&initial_influence, color) -
-          sum_moyo(&move_influence, OTHER_COLOR(color)) +
-          sum_moyo(&initial_influence, OTHER_COLOR(color)));
-  if (0)
-    gprintf("%d\n", delta);
-  return delta;
-}
-
-/* Compute the difference in strict moyo made by a move by color at pos. */
-int
-influence_delta_strict_moyo(int pos, int color,
-                           char saved_stones[BOARDMAX])
-{
-  int delta;
-  if (0)
-    gprintf("influence_delta_strict_moyo for %1m %s = ", pos,
-           color_to_string(color));
-  compute_move_influence(I(pos), J(pos), color, saved_stones);
-  /* friendly influence is valued greater than unfriendly 
-   * to compensate for an observed failure to take fuseki big points */
-  delta = (1.5*sum_strict_moyo(&move_influence, color) -
-          1.5*sum_strict_moyo(&initial_influence, color) -
-          sum_strict_moyo(&move_influence, OTHER_COLOR(color)) +
-          sum_strict_moyo(&initial_influence, OTHER_COLOR(color)));
-  if (0)
-    gprintf("%d\n", delta);
-  return delta;
-}
 
-/* Compute the difference in area made by a move by color at pos. */
-int
-influence_delta_area(int pos, int color,
-                    char saved_stones[BOARDMAX])
-{
-  int delta;
-  if (0)
-    gprintf("influence_delta_area for %1m %s = ", pos,
-           color_to_string(color));
-  compute_move_influence(I(pos), J(pos), color, saved_stones);
-  /* friendly influence is valued greater than unfriendly 
-   * to compensate for an observed failure to take fuseki big points */
-  delta = (1.5*sum_area(&move_influence, color) -
-          1.5*sum_area(&initial_influence, color) -
-          sum_area(&move_influence, OTHER_COLOR(color)) +
-          sum_area(&initial_influence, OTHER_COLOR(color)));
+  for (i = 0; i < board_size; i++)
+    for (j = 0; j < board_size; j++) {
+      float new_value = move_influence.territory_value[i][j];
+      float old_value = initial_influence.territory_value[i][j];
+      /* Negate values if we are black. */
+      if (color == BLACK) {
+       new_value = -new_value;
+       old_value = -old_value;
+      }
+      
+      if (new_value != old_value) {
+       DEBUG(DEBUG_TERRITORY, "  - %m territory change %f (%f -> %f)\n",
+               i, j, new_value - old_value, old_value, new_value);
+       delta += new_value - old_value;
+      }
+    }
+  
   if (0)
-    gprintf("%d\n", delta);
+    gprintf("%f\n", delta);
+  delta_territory_cache[pos] = delta;
+  
   return delta;
 }
 
-/* Compute the difference in strict area made by a move by color at pos. */
-int
-influence_delta_strict_area(int pos, int color,
-                           char saved_stones[BOARDMAX])
-{
-  int delta;
-  if (0)
-    gprintf("influence_delta_strict_area for %1m %s = ", pos,
-           color_to_string(color));
-  compute_move_influence(I(pos), J(pos), color, saved_stones);
-  delta = (sum_strict_area(&move_influence, color) -
-          sum_strict_area(&initial_influence, color) -
-          sum_strict_area(&move_influence, OTHER_COLOR(color)) +
-          sum_strict_area(&initial_influence, OTHER_COLOR(color)));
-  if (0)
-    gprintf("%d\n", delta);
-  return delta;
-}
 
 /* Estimate the score. A positive value means white is ahead. The
  * score is estimated from the initial_influence, which must have been
Index: engine/influence.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.h,v
retrieving revision 1.3
diff -u -r1.3 influence.h
--- engine/influence.h  2001/09/06 21:34:20     1.3
+++ engine/influence.h  2001/11/10 18:54:18
@@ -48,7 +48,7 @@
 /* Value in delta_territory_cache indicating that the value has not
  * been computed. Arbitrary but unattainable.
  */
-#define NOT_COMPUTED (-2 * MAX_BOARD * MAX_BOARD)
+#define NOT_COMPUTED (-2.0 * MAX_BOARD * MAX_BOARD)
 
 /* Values for the float working area w when used only for marking. */
 #define UNMARKED 0.0
@@ -94,6 +94,8 @@
   int region_type[MAX_REGIONS];
   int region_size[MAX_REGIONS];
   int number_of_regions;
+
+  float territory_value[MAX_BOARD][MAX_BOARD];
 
   int color_to_move; /* Which color is in turn to move. */
   
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.42
diff -u -r1.42 liberty.h
--- engine/liberty.h    2001/11/10 14:07:10     1.42
+++ engine/liberty.h    2001/11/10 18:54:18
@@ -431,12 +431,7 @@
 /* Influence functions. */
 void compute_initial_influence(int color, int dragons_known);
 void resegment_initial_influence(void);
-int influence_delta_territory(int pos, int color, char saved_stones[BOARDMAX]);
-int influence_delta_moyo(int pos, int color, char saved_stones[BOARDMAX]);
-int influence_delta_strict_moyo(int pos, int color,
-                               char saved_stones[BOARDMAX]);
-int influence_delta_area(int pos, int color, char saved_stones[BOARDMAX]);
-int influence_delta_strict_area(int pos, int color,
+float influence_delta_territory(int pos, int color,
                                char saved_stones[BOARDMAX]);
 int influence_territory_color(int pos);
 int influence_moyo_color(int pos);
Index: engine/move_reasons.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.c,v
retrieving revision 1.35
diff -u -r1.35 move_reasons.c
--- engine/move_reasons.c       2001/11/06 16:36:50     1.35
+++ engine/move_reasons.c       2001/11/10 18:54:23
@@ -105,7 +105,6 @@
       move[ii].additional_ko_value    = 0.0;
       move[ii].territorial_value      = 0.0;
       move[ii].strategical_value      = 0.0;
-      move[ii].influence_value        = 0.0;
       move[ii].maxpos_shape           = 0.0;
       move[ii].numpos_shape           = 0;
       move[ii].maxneg_shape           = 0.0;
@@ -2324,9 +2323,7 @@
  * Estimate the direct territorial value of a move at (pos).
  */
 static void
-estimate_territorial_value(int pos, int color,
-                          char saved_stones[BOARDMAX],
-                          float score)
+estimate_territorial_value(int pos, int color, float score)
 {
   int k;
   int aa = NO_MOVE;
@@ -2336,6 +2333,7 @@
   float secondary_value = 0.0;
 
   int does_block = 0;
+  char saved_stones[BOARDMAX];
 
   memset(saved_stones, 0, BOARDMAX);
   
@@ -2922,62 +2920,6 @@
 
 
 /*
- * Estimate the influence value of a move at (pos).
- *
- * FIXME: This is much too simplified.
- */
-static void
-estimate_influence_value(int pos, int color,
-                        char saved_stones[BOARDMAX])
-{
-  int k;
-  int does_expand = 0;
-
-  /* If the influence_value is non-zero, we have already computed it
-   * once and don't have to redo it. This may happen when move values
-   * are reevaluated after looking for endgame moves or after
-   * revise_semeai().
-   */
-  if (move[pos].influence_value == 0.0) {
-    for (k = 0; k < MAX_REASONS; k++) {
-      int r = move[pos].reason[k];
-      if (r < 0)
-       break;
-      
-      switch (move_reasons[r].type) {
-      case CONNECT_MOVE:
-      case CUT_MOVE:
-      case BLOCK_TERRITORY_MOVE:
-      case EXPAND_TERRITORY_MOVE:
-      case STRATEGIC_ATTACK_MOVE:
-      case STRATEGIC_DEFEND_MOVE:
-      case EXPAND_MOYO_MOVE:
-      case OWL_ATTACK_MOVE:
-      case OWL_ATTACK_MOVE_GOOD_KO:
-      case OWL_ATTACK_MOVE_BAD_KO:
-      case OWL_DEFEND_MOVE:
-      case OWL_DEFEND_MOVE_GOOD_KO:
-      case OWL_DEFEND_MOVE_BAD_KO:
-      case SEMEAI_MOVE:
-       does_expand = 1;
-       break;
-      }
-    }
-    
-    if (!does_expand || move[pos].move_safety == 0)
-      return;
-    
-    move[pos].influence_value =
-      0.35 * influence_delta_strict_moyo(pos, color, saved_stones);
-    move[pos].influence_value +=
-      0.13 * influence_delta_strict_area(pos, color, saved_stones);
-  }
-  
-  if (move[pos].influence_value != 0.0)
-    TRACE("  %1m: %f - influence\n", pos, move[pos].influence_value);
-}
-
-/*
  * Estimate the strategical value of a move at (pos).
  */
 static void
@@ -3494,7 +3436,6 @@
 {
   float tot_value;
   float shape_factor;
-  char saved_stones[BOARDMAX];
 
   gg_assert(stackp == 0);
   
@@ -3521,19 +3462,12 @@
     /* Estimate the value of various aspects of the move. The order
      * is significant. Territorial value must be computed before
      * strategical value. See connection_value().
-     *
-     * The saved_stones[] array is initialized by
-     * estimate_territorial_value() and reused in
-     * estimate_influence_value().
      */
-    estimate_territorial_value(pos, color, saved_stones, score);
+    estimate_territorial_value(pos, color, score);
     estimate_strategical_value(pos, color, score);
-    estimate_influence_value(pos, color, saved_stones);
   }
 
-  tot_value = (move[pos].territorial_value
-              + move[pos].strategical_value
-              + move[pos].influence_value);
+  tot_value = move[pos].territorial_value + move[pos].strategical_value;
 
   shape_factor = compute_shape_factor(pos);
 
Index: engine/move_reasons.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.h,v
retrieving revision 1.7
diff -u -r1.7 move_reasons.h
--- engine/move_reasons.h       2001/10/26 07:21:11     1.7
+++ engine/move_reasons.h       2001/11/10 18:54:23
@@ -75,7 +75,6 @@
   float territorial_value; /* Value in terms of actual profit. */
   float strategical_value; /* Value with respect to strength, weakness, and
                              safety of all groups on the board. */
-  float influence_value;   /* Value from thickness and moyo. */
 
   float maxpos_shape;      /* Maximal positive contribution to shape */
   float maxneg_shape;      /* Maximal negative contribution to shape */