[gnugo-devel] arend_1_16.1: moyo size computation revised

[Arend Bayer]

This patch fixes the computation of the adjacent moyo size to a dragon.
This computation needs to know the moyo segmentation; as this is
currently a internal variable of influence.c, I added a new function
influence_get_moyo_segmentation that exports the moyo part of the
segmentation information of the initial influence. This function should
be useful for a future moyo module as well.

I only ran a small part of the regression where the patch did well. Anyway
the correction of the logical mistake seems clearly indicated.

-Arend

- new function influence_get_moyo_segmentation
- computations of moyo size surrounding a dragon changed

Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.33
diff -u -r1.33 dragon.c
--- engine/dragon.c     2001/12/02 21:46:02     1.33
+++ engine/dragon.c     2001/12/03 23:23:11
@@ -37,6 +37,7 @@
 static int compute_dragon_status(int pos);
 static void dragon_eye(int pos, struct eye_data[BOARDMAX]);
 static int compute_escape(int pos, int dragon_status_known);
+static void compute_surrounding_moyo_sizes(int opposite);
 
 static int dragon2_initialized;
 static int lively_white_dragons;
@@ -371,11 +372,15 @@
   time_report(2, "  resegment_initial_influence", NO_MOVE, 1.0);
 
   /* Compute the surrounding moyo sizes. */
-  for (d = 0; d < number_of_dragons; d++) {
-    dragon2[d].moyo = influence_get_moyo_size(dragon2[d].origin,
-                                             DRAGON(d).color);
-  }
-  time_report(2, "  influence_get_moyo_size", NO_MOVE, 1.0);
+  for (d = 0; d < number_of_dragons; d++) 
+    dragon2[d].moyo = 2 * BOARDMAX;
+  /* Set moyo sizes according to initial_influence. */
+  compute_surrounding_moyo_sizes(0);
+  /* Set moyo sizes according to initial_opposite_influence if
+   * this yields smaller results.
+   */
+  compute_surrounding_moyo_sizes(1);
+  time_report(2, "  time to compute moyo sizes", NO_MOVE, 1.0);
 
   /* Determine status: ALIVE, DEAD, CRITICAL or UNKNOWN */
   for (m = 0; m < board_size; m++)
@@ -1510,6 +1515,46 @@
     }
 
   return dragon_escape(goal, board[pos], escape_value);
+};
+
+/*
+ * Sum up the surrounding moyo sizes for each dragon. Write this into
+ * dragon2[].moyo if it is smaller than the current entry. If (opposite)
+ * is true, we use initial_opposite_influence, otherwise initial_influence.
+ */
+static void
+compute_surrounding_moyo_sizes(int opposite)
+{
+  int i, j;
+  int pos;
+  int m, n;
+  int result[MAX_BOARD * MAX_BOARD];
+  int moyo_is_adjacent[MAX_BOARD * MAX_BOARD][MAX_MOYOS + 1];
+  struct moyo_data moyos;
+
+  influence_get_moyo_segmentation(opposite, &moyos);
+  for (i = 0; i < number_of_dragons; i++) {
+    result[i] = 0;
+    for (j = 1; j <= moyos.number; j++)
+      moyo_is_adjacent[i][j] = 0;
+  };
+  for (m = 0; m < board_size; m++)
+    for (n = 0; n < board_size; n++) {
+      pos = POS(m, n);
+      if ((moyos.segmentation[pos] != 0)
+          && (board[pos] == moyos.owner[moyos.segmentation[pos]]))
+        moyo_is_adjacent
+          [dragon[pos].id][moyos.segmentation[pos]] = 1; 
+    };
+  for (i = 0; i < number_of_dragons; i++) {
+    for (j = 1; j <= moyos.number; j++)
+      if (moyo_is_adjacent[i][j]) {
+         result[i] += moyos.size[j];
+      }
+    if (result[i] < dragon2[i].moyo) {
+       dragon2[i].moyo = result[i];
+    }
+  }
 }
 
 
Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.21
diff -u -r1.21 influence.c
--- engine/influence.c  2001/11/26 14:54:28     1.21
+++ engine/influence.c  2001/12/03 23:23:18
@@ -1096,6 +1096,66 @@
   return gg_min(result1, result2);
 }
 
+/* Export the moyo segmentation. If (opposite) is true, then
+ * initial_opposite_influence is used, otherwise initial_influence.
+ */
+void
+influence_get_moyo_segmentation(int opposite, 
+                                struct moyo_data *moyos)
+{
+  int m, n;
+  int pos;
+  int min_moyo_id;
+  int max_moyo_id;
+  int i;
+  struct influence_data *q;
+
+  min_moyo_id = MAX_REGIONS;
+  max_moyo_id = 0;
+
+  if (opposite) {
+    q = &initial_opposite_influence;
+  }
+  else {
+    q = &initial_influence;
+  };
+  /* Find out range of region ids used by moyos. */
+  for (m = 0; m < board_size; m++)
+    for (n = 0; n < board_size; n++) {
+      pos = POS(m, n);
+      if (q->moyo_segmentation[I(pos)][J(pos)] != 0) {
+        min_moyo_id = gg_min(min_moyo_id,
+                    q->moyo_segmentation[I(pos)][J(pos)]);
+        max_moyo_id = gg_max(max_moyo_id,
+                    q->moyo_segmentation[I(pos)][J(pos)]);
+      }
+    }
+  moyos->number = max_moyo_id - min_moyo_id + 1;
+
+  /* Export segmentation. */
+  for (m = 0; m < board_size; m++)
+    for (n = 0; n < board_size; n++) {
+      pos = POS(m, n);
+      if (q->moyo_segmentation[I(pos)][J(pos)] != 0) {
+        moyos->segmentation[pos]
+             = q->moyo_segmentation[I(pos)][J(pos)] - min_moyo_id + 1;
+      }
+      else {
+        moyos->segmentation[pos] = 0;
+      }
+    }
+  /* Export size and owner info. */
+  for (i = min_moyo_id; i <= max_moyo_id; i++) {
+    moyos->size[i - min_moyo_id + 1] = q->region_size[i];
+    if (q->region_type[i] & BLACK_REGION) {
+      moyos->owner[i - min_moyo_id  +1] = BLACK;
+    }
+    else {
+      moyos->owner[i - min_moyo_id  +1] = WHITE;
+    }
+  }
+}
+
 /* Compute the influence before a move has been made, which can
  * later be compared to the influence after a move. Assume that
  * the other color is in turn to move.
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.54
diff -u -r1.54 liberty.h
--- engine/liberty.h    2001/12/03 20:57:53     1.54
+++ engine/liberty.h    2001/12/03 23:23:22
@@ -455,7 +455,17 @@
 #define INFLUENCE_SAVED_STONE     1
 #define INFLUENCE_CAPTURED_STONE  2
 
+/* This format is used when exporting the moyo segmentation. */
+#define MAX_MOYOS MAX_BOARD*MAX_BOARD
 
+struct moyo_data
+{
+  int number; /* Number of moyos. */
+  int segmentation[BOARDMAX]; /* Numbers the moyos. */
+  int size[MAX_MOYOS];
+  int owner[MAX_MOYOS];
+};
+
 /* Influence functions. */
 void compute_initial_influence(int color, int dragons_known);
 void resegment_initial_influence(void);
@@ -465,6 +475,8 @@
 int influence_moyo_color(int pos);
 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);
 float influence_estimate_score(float moyo_coeff, float area_coeff);
 void influence_mark_non_territory(int pos, int color);