[gnugo-devel] find_half_eyes()

[Paul Pogonyshev]

changes:
  - new function find_half_eyes().
  - no more eyespace reevaluation after finding false eyes (maybe the
    engine is now 0.01% faster ;).

there should be no changes in regression besides 10 last tests in
nngs2.tst (which i recall to be new).

Paul


Index: gnugo/engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.102
diff -u -r1.102 owl.c
--- gnugo/engine/owl.c  10 Sep 2002 20:17:27 -0000      1.102
+++ gnugo/engine/owl.c  15 Sep 2002 15:50:43 -0000
@@ -2272,7 +2272,6 @@
                   int *probable_max)
 {
   char mw[BOARDMAX];  /* mark relevant eye origins */
-  signed char mx[BOARDMAX]; /* mark potential half or false eyes */
   int vital_values[BOARDMAX];
   int true_genus = 0;
   struct eyevalue eyevalue;
@@ -2283,10 +2282,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(vital_values, 0, sizeof(vital_values));
   UNUSED(komaster);
 
@@ -2355,76 +2352,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 || life)
-         && 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_eyes(color, eye, owl->half_eye, mw);
 
   *probable_min = 0;
   *probable_max = 0;
Index: gnugo/engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.48
diff -u -r1.48 optics.c
--- gnugo/engine/optics.c       22 Jul 2002 16:49:26 -0000      1.48
+++ gnugo/engine/optics.c       15 Sep 2002 15:50:49 -0000
@@ -762,7 +762,7 @@
     print_eye(eye, heye, pos);
     DEBUG(DEBUG_EYES, "\n");
   }
-  
+
   /* First we try to let the life code evaluate the eye space. */
   if (life && eye[pos].esize <= life_eyesize) {
     struct eyevalue value1;
@@ -898,7 +898,7 @@
     print_eye(eye, heye, pos);
     DEBUG(DEBUG_EYES, "\n");
   }
-  
+
   /* First we try to let the life code evaluate the eye space. */
   if (life
       && eye[pos].esize <= life_eyesize
@@ -1955,6 +1955,49 @@
   verbose = save_verbose;
 }
 
+/* Find topological half eyes and false eyes by analyzing the
+ * diagonal intersections, as described in the Texinfo
+ * documentation (Eyes/Eye Topology).
+ */
+
+void
+find_half_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 && !life)
+        || 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:
Index: gnugo/engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.112
diff -u -r1.112 liberty.h
--- gnugo/engine/liberty.h      10 Sep 2002 15:05:42 -0000      1.112
+++ gnugo/engine/liberty.h      15 Sep 2002 15:50:52 -0000
@@ -894,6 +894,9 @@
 void make_domains(struct eye_data b_eye[BOARDMAX],
                   struct eye_data w_eye[BOARDMAX],
                  int owl_call);
+void find_half_eyes(int color, struct eye_data eye[BOARDMAX],
+                   struct half_eye_data heye[BOARDMAX],
+                   char find_mask[BOARDMAX]);
 
 int is_halfeye(struct half_eye_data heye[BOARDMAX], int pos);
 
Index: gnugo/engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.74
diff -u -r1.74 dragon.c
--- gnugo/engine/dragon.c       10 Sep 2002 15:05:42 -0000      1.74
+++ gnugo/engine/dragon.c       15 Sep 2002 15:50:56 -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 || life)
-         && 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 || life)
-         && 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 */
+  find_half_eyes(BLACK, black_eye, half_eye, NULL);
+  find_half_eyes(WHITE, white_eye, half_eye, NULL);
 
   /* Pattern based modification of the eye shapes computed by
    * make_domains and halfeye analysis.