[gnugo-devel] find_half_and_false_eyes() function

[Paul Pogonyshev]

this patch adds new function find_half_and_false_eyes(). i didn't
check it against regression tests, but i checked a similar patch
before gunnar_3_9.5. there must be no changes.

changes:
  - new function find_half_and_false_eyes().
  - owl doesn't 
reevaluate eye vertices after finding a false eye.
  
Paul


Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.103
diff -u -r1.103 owl.c
--- engine/owl.c        16 Sep 2002 07:27:49 -0000      1.103
+++ engine/owl.c        17 Sep 2002 20:15:04 -0000
@@ -2284,7 +2284,6 @@
   struct eye_data *eye = owl->my_eye;
   char mw[BOARDMAX];  /* mark relevant eye origins */
   char mz[BOARDMAX];  /* mark potentially irrelevant eye origins */
-  signed char mx[BOARDMAX]; /* mark potential half or false eyes */
   int vital_values[BOARDMAX];
   int dummy_eyemin = 0;
   int dummy_eyemax = 0;
@@ -2296,10 +2295,8 @@
   int k;
   int lunch;
   int eye_color;
-  int topological_intersections;
   int save_debug = debug;
   memset(mw, 0, sizeof(mw));
-  memset(mx, 0, sizeof(mx));
   memset(mz, 0, sizeof(mz));
   memset(vital_values, 0, sizeof(vital_values));
   UNUSED(komaster);
@@ -2381,76 +2378,8 @@
       owl->half_eye[POS(m, n)].value = 10.0;
     }

-  /* Find topological half eyes and false eyes by analyzing the
-   * diagonal intersections, as described in the Texinfo
-   * documentation (Eyes/Eye Topology).
-   */
-
-  /* First mark the potential halfeyes or false eyes. */
-  topological_intersections = 0;
-  for (m = 0; m < board_size; m++)
-    for (n = 0; n < board_size; n++) {
-      int pos = POS(m, n);
-      if (eye[pos].color == eye_color
-         && eye[pos].origin != NO_MOVE
-         && mw[eye[pos].origin] > 1
-         && !eye[pos].marginal
-         && eye[pos].neighbors <= 1) {
-       mx[pos] = 1;
-       topological_intersections++;
-      }
-    }
-
-  /* Then examine them. */
-  while (topological_intersections > 0) {
-    for (m = 0; m < board_size; m++)
-      for (n = 0; n < board_size; n++) {
-       int pos = POS(m, n);
-       float sum;
-
-       if (mx[pos] <= 0)
-         continue;
-
-       mx[pos] = -1;
-       topological_intersections--;
-       
-       sum = topological_eye(pos, color, owl->my_eye, owl->half_eye);
-       
-       if (sum >= 4.0) {
-         /* False eye. */
-         int previously_marginal = eye[pos].marginal;
-         owl->half_eye[pos].type = FALSE_EYE;
-         if (eye[pos].esize == 1
-             || is_legal(pos, OTHER_COLOR(color))
-             || board[pos] == OTHER_COLOR(color)) {
-           add_false_eye(pos, eye, owl->half_eye);
-       
-           /* Marginal status may have changed. This can change the
-             * topological eye evaluation for diagonal neighbors, so
-             * we mark these for another pass if they have already
-             * been examined.
-            */
-           if (!previously_marginal) {
-             for (k = 4; k < 8; k++) {
-               int i = m + deltai[k];
-               int j = n + deltaj[k];
-               if (ON_BOARD(POS(i, j)) && mx[POS(i, j)] == -1) {
-                 mx[POS(i, j)] = 1;
-                 topological_intersections++;
-               }
-             }
-           }
-         }
-       }
-       else if (sum > 2.0) {
-         owl->half_eye[pos].type = HALF_EYE;
-         ASSERT1(owl->half_eye[pos].num_attacks > 0, pos);
-         ASSERT_ON_BOARD1(owl->half_eye[pos].attack_point[0]);
-         ASSERT1(owl->half_eye[pos].num_defends > 0, pos);
-         ASSERT_ON_BOARD1(owl->half_eye[pos].defense_point[0]);
-       }
-      }
-  }
+  /* Find topological half eyes and false eyes. */
+  find_half_and_false_eyes(color, eye, owl->half_eye, mw);

   set_eyevalue(probable_eyes, 0, 0, 0, 0);
   /* This test must be conditioned on (m, n) being its own origin,
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.49
diff -u -r1.49 optics.c
--- engine/optics.c     16 Sep 2002 07:27:49 -0000      1.49
+++ engine/optics.c     17 Sep 2002 20:15:10 -0000
@@ -1971,6 +1971,51 @@
 }


+/* Find topological half eyes and false eyes by analyzing the
+ * diagonal intersections, as described in the Texinfo
+ * documentation (Eyes/Eye Topology).
+ */
+void
+find_half_and_false_eyes(int color, struct eye_data eye[BOARDMAX],
+                        struct half_eye_data heye[BOARDMAX],
+                        char find_mask[BOARDMAX])
+{
+  int eye_color = (color == WHITE ? WHITE_BORDER : BLACK_BORDER);
+  int pos;
+  float sum;
+
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    /* skip eyespaces which owl 
doesn't want to be searched */
+    if (!ON_BOARD(pos) || (find_mask && find_mask[eye[pos].origin] <= 1))
+      continue;
+
+    /* skip every vertex which can't 
be a false or half eye */
+    if (eye[pos].color != eye_color
+        || eye[pos].marginal
+        || eye[pos].neighbors > 1)
+      continue;
+
+    sum = topological_eye(pos, color, eye, heye);
+    if (sum >= 4.0) {
+      /* false eye */
+      heye[pos].type = FALSE_EYE;
+      if (eye[pos].esize == 1
+          || is_legal(pos, OTHER_COLOR(color))
+          || board[pos] == OTHER_COLOR(color))
+        add_false_eye(pos, eye, heye);
+    }
+    else if (sum > 2.0) {
+      /* half eye */
+      heye[pos].type = HALF_EYE;
+      ASSERT1(heye[pos].num_attacks > 0, pos);
+      ASSERT_ON_BOARD1(heye[pos].attack_point[0]);
+      ASSERT1(heye[pos].num_defends > 0, pos);
+      ASSERT_ON_BOARD1(heye[pos].defense_point[0]);
+    }
+  }
+}
+
+
 /*
  * Local Variables:
  * tab-width: 8
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.113
diff -u -r1.113 liberty.h
--- engine/liberty.h    16 Sep 2002 07:27:48 -0000      1.113
+++ engine/liberty.h    17 Sep 2002 20:15:13 -0000
@@ -896,6 +896,9 @@
 void make_domains(struct eye_data b_eye[BOARDMAX],
                   struct eye_data w_eye[BOARDMAX],
                  int owl_call);
+void find_half_and_false_eyes(int color, struct eye_data eye[BOARDMAX],
+                             struct half_eye_data heye[BOARDMAX],
+                             char find_mask[BOARDMAX]);

 void set_eyevalue(struct eyevalue *e, int a, int b, int c, int d);
 int min_eyes(struct eyevalue *e);
Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.76
diff -u -r1.76 dragon.c
--- engine/dragon.c     16 Sep 2002 08:30:28 -0000      1.76
+++ engine/dragon.c     17 Sep 2002 20:15:19 -0000
@@ -179,49 +179,9 @@
     }
   time_report(2, "  time to find lunches", NO_MOVE, 1.0);

-
-  /* Find topological half eyes and false eyes by analyzing the
-   * diagonal intersections, as described in the Texinfo
-   * documentation (Eyes/Eye Topology).
-   *
-   * FIXME: Consolidate this piece of code with the very similar one
-   * in owl_determine_life().
-   */
-
-  for (str = BOARDMIN; str < BOARDMAX; str++)
-    if (ON_BOARD(str)) {
-      float sum;
-
-      if (black_eye[str].color == BLACK_BORDER
-         && !black_eye[str].marginal
-         && black_eye[str].neighbors <= 1) {
-       sum = topological_eye(str, BLACK, black_eye, half_eye);
-       if (sum >= 4.0) {
-         half_eye[str].type = FALSE_EYE;
-         if (black_eye[str].esize == 1
-             || is_legal(str, WHITE)
-             || board[str] == WHITE)
-           add_false_eye(str, black_eye, half_eye);
-       }
-       else if (sum > 2.0)
-         half_eye[str].type = HALF_EYE;
-      }
-
-      if (white_eye[str].color == WHITE_BORDER
-         && !white_eye[str].marginal
-         && white_eye[str].neighbors <= 1) {
-       sum = topological_eye(str, WHITE, white_eye, half_eye);
-       if (sum >= 4.0) {
-         half_eye[str].type = FALSE_EYE;
-         if (white_eye[str].esize == 1
-             || is_legal(str, BLACK)
-             || board[str] == BLACK)
-           add_false_eye(str, white_eye, half_eye);
-       }
-       else if (sum > 2.0)
-         half_eye[str].type = HALF_EYE;
-      }
-    }
+  /* Find topological half eyes and false eyes. */
+  find_half_and_false_eyes(BLACK, black_eye, half_eye, NULL);
+  find_half_and_false_eyes(WHITE, white_eye, half_eye, NULL);

   /* Pattern based modification of the eye shapes computed by
    * make_domains and halfeye analysis.