[gnugo-devel] Surrounding moyo sizes

[Gunnar Farneback]

This patch reimplements the computation of surrounding moyo sizes when
experimental connections are enabled. The reason for this can be found
in the message
http://mail.gnu.org/pipermail/gnugo-devel/2002-August/002452.html
where I wrote:

|?The main new weakness is caused by the experimental connection code
|?doing away with most of the B patterns in conn.db. This is not a bad
|?thing by itself but has the side effect of affecting the segmentation
|?of moyo regions (see the use of INHIBIT_CONNECTION in
|?whose_moyo_restricted()). In practice this means that the surrounding
|?moyo size may become severely overestimated in certain positions,
|?causing critical or possibly even dead dragons to be considered
|?trivially alive without any need for owl reading. This is obviously
|?very bad and needs to be solved somehow.

Instead of using the segmentation of moyos done in the influence code,
we count the amount of moyo being closer to the given dragon than to
any other stones of the same color. (The reason for only looking at
stones of the same color is that we do want to count moyo for dead
opponent stones.) To keep track of which worms are closest to each
vertex of the board, new arrays close_*_worms[][] and
number_close_*_worms[] are introduced. Those are filled in by
compute_effective_worm_sizes() which already did that kind of
computations.

- new arrays close_worms[][], close_white_worms[][],
  close_black_worms[][], number_close_worms[],
  number_close_white_worms[], number_close_black_worms[]
- compute_surrounding_moyo_sizes() revised
- alternative implementation of compute_surrounding_moyo_sizes() for
  experimental-connections option
- new function influence_get_moyo_data()

After this patch I think --experimental-connections is starting to
become a solid option. The regression delta is 62 passes against 33
failures. When playing --experimental-connections against
non-experimental connections, the experimental option won 59/100 as
white and 54/100 as black. Although this is unlikely to be very
statistically robust (when playing black it had 20 wins in the first
batch of 50 games and 34 wins in the second batch) I do think it
truly is stronger.

The remaining issue is speed. Although I haven't measured it recently
there's reason to suspect that it's still clearly slower with
experimental connections. On the other hand there's no persistent
cache for connections implemented yet.

/Gunnar

Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.73
diff -u -r1.73 dragon.c
--- engine/dragon.c     4 Sep 2002 20:33:57 -0000       1.73
+++ engine/dragon.c     8 Sep 2002 13:08:35 -0000
@@ -1597,46 +1597,115 @@
  * is true, we use initial_opposite_influence, otherwise initial_influence.
  * If dragons_known is false, then .moyo_size_pre_owl is set, otherwise
  * .moyo_size_post_owl and .moyo_territorial_value.
+ *
+ * Currently this is implemented differently depending on whether
+ * experimental connections are used or not. The reason why this is
+ * needed is that most of the B patterns in conn.db are disabled for
+ * experimental connections, which may cause the moyo segmentation to
+ * pass through cutting points between dragons, making the surrounding
+ * moyo size mostly useless. Instead we only use the part of the
+ * surrounding moyo which is closest to some worm of the dragon.
  */
 static void
 compute_surrounding_moyo_sizes(int opposite, int dragon_status_known)
 {
   int pos;
   int d;
-  int mx[MAX_MOYOS + 1];
-  struct moyo_data moyos;
 
-  influence_get_moyo_segmentation(opposite, &moyos);
+  if (!experimental_connections) {
+    int mx[MAX_MOYOS + 1];
+    struct moyo_data moyos;
 
-  memset(mx, 0, sizeof(mx));
-  for (d = 0; d < number_of_dragons; d++) {
-    int this_moyo_size = 0;
-    float this_moyo_value = 0.0;
-    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-      int moyo_number = moyos.segmentation[pos];
-      if (board[pos] != DRAGON(d).color
-          || moyo_number == 0
-          || dragon[pos].id != d
-          || moyos.owner[moyo_number] != board[pos])
-        continue;
+    influence_get_moyo_segmentation(opposite, &moyos);
 
-      if (mx[moyo_number] != d + 1) {
-        mx[moyo_number] = d + 1;
-        this_moyo_size += moyos.size[moyo_number];
-       this_moyo_value += moyos.territorial_value[moyo_number];
+    memset(mx, 0, sizeof(mx));
+    for (d = 0; d < number_of_dragons; d++) {
+      int this_moyo_size = 0;
+      float this_moyo_value = 0.0;
+      for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+       int moyo_number = moyos.segmentation[pos];
+       if (board[pos] != DRAGON(d).color
+           || moyo_number == 0
+           || dragon[pos].id != d
+           || moyos.owner[moyo_number] != board[pos])
+         continue;
+       
+       if (mx[moyo_number] != d + 1) {
+         mx[moyo_number] = d + 1;
+         this_moyo_size += moyos.size[moyo_number];
+         this_moyo_value += moyos.territorial_value[moyo_number];
+       }
+      }
+      
+      if (!dragon_status_known) {
+       if (this_moyo_size < dragon2[d].moyo_size_pre_owl) {
+         dragon2[d].moyo_size_pre_owl = this_moyo_size;
+       }
       }
+      else
+       if (this_moyo_size < dragon2[d].moyo_size_post_owl) {
+         dragon2[d].moyo_size_post_owl = this_moyo_size;
+         dragon2[d].moyo_territorial_value = this_moyo_value;
+       }
     }
+  }
+  else {
+    int k;
+    int moyo_color[BOARDMAX];
+    float territory_value[BOARDMAX];
+    float moyo_sizes[BOARDMAX];
+    float moyo_values[BOARDMAX];
+    
+    influence_get_moyo_data(opposite, moyo_color, territory_value);
 
-    if (!dragon_status_known) {
-      if (this_moyo_size < dragon2[d].moyo_size_pre_owl) {
-       dragon2[d].moyo_size_pre_owl = this_moyo_size;
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      moyo_sizes[pos] = 0.0;
+      moyo_values[pos] = 0.0;
+    }
+    
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (!ON_BOARD(pos))
+       continue;
+      
+      if (moyo_color[pos] == board[pos])
+       continue;
+      
+      if (moyo_color[pos] == WHITE) {
+       for (k = 0; k < number_close_white_worms[pos]; k++) {
+         int w = close_white_worms[pos][k];
+         int dr = dragon[w].origin;
+         
+         moyo_sizes[dr] += 1.0 / number_close_white_worms[pos];
+         moyo_values[dr] += (territory_value[pos]
+                             / number_close_white_worms[pos]);
+       }
+      }
+      
+      if (moyo_color[pos] == BLACK) {
+       for (k = 0; k < number_close_black_worms[pos]; k++) {
+         int w = close_black_worms[pos][k];
+         int dr = dragon[w].origin;
+         
+         moyo_sizes[dr] += 1.0 / number_close_black_worms[pos];
+         moyo_values[dr] += (territory_value[pos]
+                             / number_close_black_worms[pos]);
+       }
       }
     }
-    else
-      if (this_moyo_size < dragon2[d].moyo_size_post_owl) {
+
+    for (d = 0; d < number_of_dragons; d++) {
+      int this_moyo_size = (int) moyo_sizes[dragon2[d].origin];
+      float this_moyo_value = moyo_values[dragon2[d].origin];
+      
+      if (!dragon_status_known) {
+       if (this_moyo_size < dragon2[d].moyo_size_pre_owl)
+         dragon2[d].moyo_size_pre_owl = this_moyo_size;
+      }
+      else if (this_moyo_size < dragon2[d].moyo_size_post_owl) {
        dragon2[d].moyo_size_post_owl = this_moyo_size;
        dragon2[d].moyo_territorial_value = this_moyo_value;
       }
+    }
   }
 }
 
Index: engine/globals.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v
retrieving revision 1.27
diff -u -r1.27 globals.c
--- engine/globals.c    3 Sep 2002 00:28:12 -0000       1.27
+++ engine/globals.c    8 Sep 2002 13:08:35 -0000
@@ -145,6 +145,13 @@
 float best_move_values[10];
 int   best_moves[10];
 
+int close_worms[BOARDMAX][4];
+int number_close_worms[BOARDMAX];
+int close_black_worms[BOARDMAX][4];
+int number_close_black_worms[BOARDMAX];
+int close_white_worms[BOARDMAX][4];
+int number_close_white_worms[BOARDMAX];
+
 /* Various statistics are collected here. */
 struct stats_data stats;
 
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.59
diff -u -r1.59 influence.c
--- engine/influence.c  8 Aug 2002 23:03:03 -0000       1.59
+++ engine/influence.c  8 Sep 2002 13:08:39 -0000
@@ -1540,6 +1540,33 @@
   }
 }
 
+/* Another function to export a certain amount of moyo data. */
+void
+influence_get_moyo_data(int opposite, int moyo_color[BOARDMAX],
+                       float territory_value[BOARDMAX])
+{
+  int m, n;
+  struct influence_data *q;
+
+  if (opposite)
+    q = &initial_opposite_influence;
+  else
+    q = &initial_influence;
+
+  for (m = 0; m < board_size; m++)
+    for (n = 0; n < board_size; n++) {
+      if (whose_moyo_restricted(q, m, n) == BLACK)
+       moyo_color[POS(m, n)] = BLACK;
+      else if (whose_moyo_restricted(q, m, n) == WHITE)
+       moyo_color[POS(m, n)] = WHITE;
+      else
+       moyo_color[POS(m, n)] = EMPTY;
+      
+      territory_value[POS(m, n)] = gg_abs(q->territory_value[m][n]);
+    }
+}
+
+
 /* Export the territory valuation at an intersection from initial_influence;
  * it is given from (color)'s point of view.
  */
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.110
diff -u -r1.110 liberty.h
--- engine/liberty.h    2 Sep 2002 14:19:22 -0000       1.110
+++ engine/liberty.h    8 Sep 2002 13:08:42 -0000
@@ -553,6 +553,8 @@
 int influence_area_color(int pos);
 int influence_get_moyo_size(int pos, int color);
 void influence_get_moyo_segmentation(int opposite, struct moyo_data *moyo);
+void influence_get_moyo_data(int opposite, int moyo_color[BOARDMAX],
+                            float territory_value[BOARDMAX]);
 float influence_estimate_score(float moyo_coeff, float area_coeff);
 void influence_mark_non_territory(int pos, int color);
 float influence_initial_territory(int pos, int color);
@@ -659,6 +661,25 @@
 extern int stackp;                /* stack pointer */
 extern int count_variations;      /* count (decidestring) */
 extern SGFTree *sgf_dumptree;
+
+/* Arrays pointing out the closest worms from each vertex.  The first
+ * one is the closest worms of either color, the last two ones ignore
+ * worms of the other color.  Beyond a certain distance from any worm
+ * no close worm is listed at all.  Only the closest worm is listed
+ * and if more than one are equally close they are all listed. The
+ * number of equally close worms is given in the number_*_worms
+ * arrays. If more than MAX_CLOSE_WORMS are equally close, none is
+ * listed.
+ *
+ * See compute_effective_worm_sizes() in worm.c for details.
+ */
+#define MAX_CLOSE_WORMS 4
+extern int close_worms[BOARDMAX][MAX_CLOSE_WORMS];
+extern int number_close_worms[BOARDMAX];
+extern int close_black_worms[BOARDMAX][MAX_CLOSE_WORMS];
+extern int number_close_black_worms[BOARDMAX];
+extern int close_white_worms[BOARDMAX][MAX_CLOSE_WORMS];
+extern int number_close_white_worms[BOARDMAX];
 
 
 struct stats_data {
Index: engine/worm.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/worm.c,v
retrieving revision 1.39
diff -u -r1.39 worm.c
--- engine/worm.c       4 Sep 2002 07:23:46 -0000       1.39
+++ engine/worm.c       8 Sep 2002 13:08:46 -0000
@@ -29,6 +29,9 @@
 #include "patterns.h"
 
 static void compute_effective_worm_sizes(void);
+static void do_compute_effective_worm_sizes(int color,
+                                           int (*cw)[MAX_CLOSE_WORMS],
+                                           int *ncw, int max_distance);
 static void compute_unconditional_status(void);
 static void find_worm_attacks_and_defenses(void);
 static void find_worm_threats(void);
@@ -526,11 +529,27 @@
  * shared are counted with equal fractional values for each worm.
  *
  * We never count intersections further away than distance 3.
+ *
+ * This function is also used to compute arrays with information about
+ * the distances to worms of both or either color. In the latter case
+ * we count intersections up to a distance of 5.
  */
 
 static void
 compute_effective_worm_sizes()
 {
+  do_compute_effective_worm_sizes(BLACK | WHITE, close_worms,
+                                 number_close_worms, 3);
+  do_compute_effective_worm_sizes(BLACK, close_black_worms,
+                                 number_close_black_worms, 5);
+  do_compute_effective_worm_sizes(WHITE, close_white_worms,
+                                 number_close_white_worms, 5);
+}
+
+static void
+do_compute_effective_worm_sizes(int color, int (*cw)[MAX_CLOSE_WORMS],
+                               int *ncw, int max_distance)
+{
   int pos;
 
   /* Distance to closest worm, -1 means unassigned, 0 that there is
@@ -558,18 +577,18 @@
     
     nworms[pos] = 0;
     
-    if (board[pos] == EMPTY)
-      distance[pos] = -1;
-    else {
+    if (board[pos] & color) {
       distance[pos] = 0;
       worms[pos][0] = worm[pos].origin;
       nworms[pos]++;
     }
+    else
+      distance[pos] = -1;
   }
   
   dist = 0;
   found_one = 1;
-  while (found_one && dist <= 3) {
+  while (found_one && dist <= max_distance) {
     found_one = 0;
     dist++;
     for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
@@ -599,25 +618,44 @@
       }
     }
   }
-  
-  /* Distribute (fractional) contributions to the worms. */
+
+  /* Compute the effective sizes but only when all worms are considered. */
+  if (color == (BLACK | WHITE)) {
+    /* Distribute (fractional) contributions to the worms. */
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (!ON_BOARD(pos))
+       continue;
+      
+      for (k = 0; k < nworms[pos]; k++) {
+       int w = worms[pos][k];
+       if (board[pos] == EMPTY)
+         worm[w].effective_size += 0.5/nworms[pos];
+       else
+         worm[w].effective_size += 1.0;
+      }
+    }
+    
+    /* Propagate the effective size values all over the worms. */
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+      if (IS_STONE(board[pos]) && is_worm_origin(pos, pos))
+       propagate_worm(pos);
+  }
+
+  /* Fill in the appropriate close_*_worms (cw) and
+   * number_close_*_worms (ncw) arrays.
+   */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
     if (!ON_BOARD(pos))
       continue;
-    
-    for (k = 0; k < nworms[pos]; k++) {
-      int w = worms[pos][k];
-      if (board[pos] == EMPTY)
-       worm[w].effective_size += 0.5/nworms[pos];
-      else
-       worm[w].effective_size += 1.0;
-    }
+
+    if (nworms[pos] > MAX_CLOSE_WORMS)
+      ncw[pos] = 0;
+    else
+      ncw[pos] = nworms[pos];
+
+    for (k = 0; k < ncw[pos]; k++)
+      cw[pos][k] = worms[pos][k];
   }
-    
-  /* Propagate the effective size values all over the worms. */
-  for (pos = BOARDMIN; pos < BOARDMAX; pos++)
-    if (IS_STONE(board[pos]) && is_worm_origin(pos, pos))
-      propagate_worm(pos);
 }
 
 /* Identify worms which are unconditionally uncapturable in the