Re: [gnugo-devel] Eye pattern 304

[Gunnar Farneback]

I wrote:
> There seems to be more difficulties of this kind. Appended is a patch
> adding the new test case owl1:313.

I see my working copy wasn't quite up to date. It should be owl1:315.

> I agree that it's correct to remove the superfluous margin from the
> eyespace, but in light of the failure described above I think we
> should make a slightly more drastic change to the code. Instead of
> using inessential margins and patching up add_false_eye() to modify
> the eyespace in various situations, we should simply rebuild the
> eyespaces from scratch after the topological analysis. I believe this
> will make the code both simpler and more robust.

This is done by the patch below. In addition to solving the new test
case, the only regression changes are three accidental fails, owl:123,
owl:150, and global:44. In all cases it looks like the eye analysis is
improved.

- inessential margins retired
- new function partition_eyespaces()
- new function owl_find_relevant_eyespaces()

/Gunnar

Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.172
diff -u -r1.172 liberty.h
--- engine/liberty.h    19 May 2003 16:11:16 -0000      1.172
+++ engine/liberty.h    20 May 2003 21:35:55 -0000
@@ -51,10 +51,9 @@
 /* ================================================================ */
 
 
-#define FALSE_EYE              1
-#define HALF_EYE               2
-#define INHIBIT_CONNECTION     4
-#define INESSENTIAL_MARGINAL   8
+#define FALSE_EYE          1
+#define HALF_EYE           2
+#define INHIBIT_CONNECTION 4
 
 
 /* A string with n stones can have at most 2(n+1) liberties. From this
@@ -1068,6 +1067,7 @@
 void make_domains(struct eye_data b_eye[BOARDMAX],
                   struct eye_data w_eye[BOARDMAX],
                  int owl_call);
+void partition_eyespaces(struct eye_data eye[BOARDMAX], int color);
 void find_half_and_false_eyes(int color, struct eye_data eye[BOARDMAX],
                              struct half_eye_data heye[BOARDMAX],
                              char find_mask[BOARDMAX]);
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.74
diff -u -r1.74 optics.c
--- engine/optics.c     9 May 2003 22:44:38 -0000       1.74
+++ engine/optics.c     20 May 2003 21:36:00 -0000
@@ -220,46 +220,47 @@
   if (!owl_call)
     find_cuts();
   
- /* The eye spaces are all found. Now we need to find the origins. */
-  if (b_eye)
-    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-      if (!ON_BOARD(pos))
-       continue;
-      if (b_eye[pos].origin == NO_MOVE 
-         && b_eye[pos].color == BLACK_BORDER)
-      {
-       int esize = 0;
-       int msize = 0;
-
-       originate_eye(pos, pos, &esize, &msize, b_eye);
-       b_eye[pos].esize = esize;
-       b_eye[pos].msize = msize;
-      }
-    }
+  /* The eye spaces are all found. Now we need to find the origins. */
+  partition_eyespaces(b_eye, BLACK);
+  partition_eyespaces(w_eye, WHITE);
+}
 
-  if (w_eye)
-    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-      if (!ON_BOARD(pos))
-       continue;
-      if (w_eye[pos].origin == NO_MOVE
-         && w_eye[pos].color == WHITE_BORDER)
-      {
-       int esize = 0;
-       int msize = 0;
-
-       originate_eye(pos, pos, &esize, &msize, w_eye);
-       w_eye[pos].esize = esize;
-       w_eye[pos].msize = msize;
-      }
+/* Find connected eyespace components and compute relevant statistics. */
+void
+partition_eyespaces(struct eye_data eye[BOARDMAX], int color)
+{
+  int pos;
+  int eye_color;
+
+  if (!eye)
+    return;
+
+  if (color == WHITE)
+    eye_color = WHITE_BORDER;
+  else
+    eye_color = BLACK_BORDER;
+  
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+    if (ON_BOARD(pos))
+      eye[pos].origin = NO_MOVE;
+
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (!ON_BOARD(pos))
+      continue;
+    if (eye[pos].origin == NO_MOVE && eye[pos].color == eye_color) {
+      int esize = 0;
+      int msize = 0;
+      
+      originate_eye(pos, pos, &esize, &msize, eye);
+      eye[pos].esize = esize;
+      eye[pos].msize = msize;
     }
+  }
 
   /* Now we count the number of neighbors and marginal neighbors
    * of each vertex.
    */
-  if (b_eye)
-    count_neighbours(b_eye);
-  if (w_eye)
-    count_neighbours(w_eye);
+  count_neighbours(eye);
 }
 
 
@@ -1123,49 +1124,48 @@
   if (eye[pos].msize > MAXEYE)
     return 0;
 
-  /* Create list of eye vertices. Ignore inessential marginals. */
+  /* Create list of eye vertices */
   for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
-    if (!ON_BOARD(pos2)
-       || eye[pos2].origin != pos
-       || (heye[pos2].type & INESSENTIAL_MARGINAL))
+    if (!ON_BOARD(pos2))
       continue;
-
-    vpos[eye_size] = pos2;
-    marginal[eye_size] = eye[pos2].marginal;
-    if (marginal[eye_size])
-      num_marginals++;
-    neighbors[eye_size] = eye[pos2].neighbors;
-    if (0) {
+    if (eye[pos2].origin == pos) {
+      vpos[eye_size] = pos2;
+      marginal[eye_size] = eye[pos2].marginal;
       if (marginal[eye_size])
-       TRACE("(%1m)", vpos[eye_size]);
-      else
-       TRACE(" %1m ", vpos[eye_size]);
-      TRACE("\n");
-    }
-
-    if (is_corner_vertex(pos2))
-      edge[eye_size] = 2;
-    else if (is_edge_vertex(pos2))
-      edge[eye_size] = 1;
-    else 
-      edge[eye_size] = 0;
-
-    if (is_halfeye(heye, pos2)) {
-      neighbors[eye_size]++;      /* Increase neighbors of half eye. */
+       num_marginals++;
+      neighbors[eye_size] = eye[pos2].neighbors;
+      if (0) {
+       if (marginal[eye_size])
+         TRACE("(%1m)", vpos[eye_size]);
+       else
+         TRACE(" %1m ", vpos[eye_size]);
+       TRACE("\n");
+      }
+      
+      if (is_corner_vertex(pos2))
+       edge[eye_size] = 2;
+      else if (is_edge_vertex(pos2))
+       edge[eye_size] = 1;
+      else 
+       edge[eye_size] = 0;
+      
+      if (is_halfeye(heye, pos2)) {
+       neighbors[eye_size]++;      /* Increase neighbors of half eye. */
+       eye_size++;
+       /* Use a virtual marginal vertex for mapping purposes. We set it
+        * to be at NO_MOVE so it won't accidentally count as a
+        * neighbor for another vertex. Note that the half eye precedes
+        * the virtual marginal vertex in the list.
+        */
+       vpos[eye_size] = NO_MOVE;
+       marginal[eye_size] = 1;
+       num_marginals++;
+       edge[eye_size] = 0;
+       neighbors[eye_size] = 1;
+      }
+      
       eye_size++;
-      /* Use a virtual marginal vertex for mapping purposes. We set it
-       * to be at NO_MOVE so it won't accidentally count as a
-       * neighbor for another vertex. Note that the half eye precedes
-       * the virtual marginal vertex in the list.
-       */
-      vpos[eye_size] = NO_MOVE;
-      marginal[eye_size] = 1;
-      num_marginals++;
-      edge[eye_size] = 0;
-      neighbors[eye_size] = 1;
     }
-
-    eye_size++;
   }
   
   /* We attempt to construct a map from the graph to the eyespace
@@ -1489,50 +1489,25 @@
 }     
 
 
-/* add_false_eye() turns a proper eyespace into a margin. It also turns
- * neighbor marginals into inessential when some conditions are met.
- * Consider this example:
- *
- *   ...O.
- *   XXXOX
- *   X....
- *
- * When the topological algorithm does its job, the eye is turned from
- * '..!' to '.!!'. Since we prohibit such eyespaces, the easiest way to
- * work it around is to ignore the right marginal vertex at graph matching
- * stage. We mark it as "inessential" here and recognize_eye() ignores
- * such marginals.
- */
+/* add_false_eye() turns a proper eyespace into a margin. */
+
 void
 add_false_eye(int pos, struct eye_data eye[BOARDMAX],
              struct half_eye_data heye[BOARDMAX])
 {
   int k;
-  int detach_neighbor_marginals;
   ASSERT1(heye[pos].type == FALSE_EYE, pos);
   DEBUG(DEBUG_EYES, "false eye found at %1m\n", pos);
 
   if (eye[pos].color == GRAY || eye[pos].marginal != 0)
     return;
-
+  
   eye[pos].marginal = 1;
   eye[eye[pos].origin].msize++;
-  detach_neighbor_marginals = (eye[pos].neighbors > 1 && is_edge_vertex(pos));
-
-  for (k = 0; k < 4; k++) {
-    int neighbor = pos + delta[k];
-    if (ON_BOARD(neighbor) && eye[neighbor].origin == eye[pos].origin) {
-      eye[neighbor].marginal_neighbors++;
-      if (detach_neighbor_marginals
-         && eye[neighbor].marginal
-         && eye[neighbor].neighbors == 1) {
-       heye[neighbor].type |= INESSENTIAL_MARGINAL;
-       eye[pos].neighbors--;
-       eye[pos].marginal_neighbors--;
-      }
-    }
-  }
-
+  for (k = 0; k < 4; k++)
+    if (ON_BOARD(pos + delta[k])
+       && eye[pos + delta[k]].origin == eye[pos].origin)
+      eye[pos + delta[k]].marginal_neighbors++;
   propagate_eye(eye[pos].origin, eye);
 }
 
@@ -1615,12 +1590,8 @@
     
     /* skip every vertex which can't be a false or half eye */
     if (eye[pos].color != eye_color
-       || eye[pos].marginal
-#if 0
-       || (eye[pos].neighbors > 1 && !is_edge_vertex(pos)))
-#else
-       || eye[pos].neighbors > 1)
-#endif
+        || eye[pos].marginal
+        || eye[pos].neighbors > 1)
       continue;
     
     sum = topological_eye(pos, color, eye, heye);
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.163
diff -u -r1.163 owl.c
--- engine/owl.c        12 May 2003 19:28:32 -0000      1.163
+++ engine/owl.c        20 May 2003 21:36:10 -0000
@@ -166,6 +166,8 @@
                               struct owl_move_data *moves,
                               struct eyevalue *probable_eyes,
                               int *eyemin, int *eyemax);
+static void owl_find_relevant_eyespaces(struct local_owl_data *owl,
+                                       char mw[BOARDMAX], char mz[BOARDMAX]);
 static int owl_estimate_life(struct local_owl_data *owl,
                             struct local_owl_data *second_owl,
                             struct owl_move_data vital_moves[MAX_MOVES],
@@ -2507,12 +2509,9 @@
   int pos;
   int k;
   int lunch;
-  int eye_color;
   int num_eyes = 0;
   int num_lunches = 0;
   int save_debug = debug;
-  memset(mw, 0, sizeof(mw));
-  memset(mz, 0, sizeof(mz));
   memset(vital_values, 0, sizeof(vital_values));
   UNUSED(komaster);
 
@@ -2544,38 +2543,7 @@
 
   owl_make_domains(owl, second_owl);
 
-  /* The eyespaces we want to evaluate are the ones which
-   * are adjacent to the dragon (whose stones comprise the
-   * support of goal) which are not GRAY_BORDERED. These
-   * are the eyespaces of the dragon. Now we find their
-   * origins.
-   *
-   * It is required that there are at least two distinct connections,
-   * adjacent or diagonal, between non-marginal eyespace vertices and
-   * stones of the goal dragon. Otherwise there is a risk that we
-   * include irrelevant eye spaces.
-   */
-
-  if (color == WHITE)
-    eye_color = WHITE_BORDER;
-  else
-    eye_color = BLACK_BORDER;
-
-  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-    if (board[pos] == color) {
-      for (k = 0; k < 8; k++) {
-       int pos2 = pos + delta[k];
-       if (ON_BOARD(pos2)
-           && eye[pos2].color == eye_color
-           && !eye[pos2].marginal) {
-         if (owl->goal[pos])
-           mw[eye[pos2].origin]++;
-         else
-           mz[eye[pos2].origin]++;
-       }
-      }
-    }
-  }
+  owl_find_relevant_eyespaces(owl, mw, mz);
 
   /* Reset halfeye data. Set topological eye value to something big. */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
@@ -2586,6 +2554,13 @@
   /* Find topological half eyes and false eyes. */
   find_half_and_false_eyes(color, eye, owl->half_eye, mw);
 
+  /* The eyespaces may have been split or changed in other ways by the
+   * topological analysis, so we need to regenerate them and once more
+   * determine which ones are relevant.
+   */
+  partition_eyespaces(owl->my_eye, owl->color);
+  owl_find_relevant_eyespaces(owl, mw, mz);
+  
   set_eyevalue(probable_eyes, 0, 0, 0, 0);
 
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
@@ -2831,7 +2806,7 @@
     *eyemax += max_eyes(probable_eyes);
     /* If we have at least two different eyespaces and can create one eye
      * in sente, we assume there's a chance to create another one. This is
-     * needed because optics code don't know about eyespaces influenting
+     * needed because optics code don't know about eyespaces influencing
      * each other and combination moves (i.e. double threats to create an
      * eye).
      */
@@ -2845,6 +2820,51 @@
   debug = save_debug;
 }
 
+
+/* The eyespaces we want to evaluate are the ones which
+ * are adjacent to the dragon (whose stones comprise the
+ * support of goal) which are not GRAY_BORDERED. These
+ * are the eyespaces of the dragon. Now we find their
+ * origins.
+ *
+ * It is required that there are at least two distinct connections,
+ * adjacent or diagonal, between non-marginal eyespace vertices and
+ * stones of the goal dragon. Otherwise there is a risk that we
+ * include irrelevant eye spaces.
+ */
+
+static void
+owl_find_relevant_eyespaces(struct local_owl_data *owl,
+                           char mw[BOARDMAX], char mz[BOARDMAX])
+{
+  int pos;
+  int eye_color;
+  int k;
+  struct eye_data *eye = owl->my_eye;
+  
+  if (owl->color == WHITE)
+    eye_color = WHITE_BORDER;
+  else
+    eye_color = BLACK_BORDER;
+
+  memset(mw, 0, BOARDMAX * sizeof(mw[0]));
+  memset(mz, 0, BOARDMAX * sizeof(mz[0]));
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (board[pos] == owl->color) {
+      for (k = 0; k < 8; k++) {
+       int pos2 = pos + delta[k];
+       if (ON_BOARD(pos2)
+           && eye[pos2].color == eye_color
+           && !eye[pos2].marginal) {
+         if (owl->goal[pos])
+           mw[eye[pos2].origin]++;
+         else
+           mz[eye[pos2].origin]++;
+       }
+      }
+    }
+  }
+}
 
 /* Case 1.
  *