Re: [gnugo-devel] Eye pattern 304

[Paul Pogonyshev]

i wrote:
> SP LEE wrote:
> > This is the game I posted before regarding life and death, where gnugo
> > played black. After white played J2, the black group on lower side was
> > dead. I think I'm not yet on the stage of fix any problem of the software
> > (it's still too complicated for me), but after studied tons of debug
> > output of gnugo I found some strange things. Before white played J2, I
> > let gnugo analyze "owl_attack L2". It's good that it started to consider
> > at first the attack position J2. For the following sequence it
> > considered:
> > W:J2 B:H2 W:J3 B:K2 W:J4 B:F2 W:E2 B:K1 W:L4 B:F1
> >
> > gnugo thought there was an eye at G1 of type 304 and the group was alive
> > due to "getting deep, look lively". If I'm right, this eye is of type
> > 0111. However, I think if attacker moves first, there should be no eye.
>
> this is a real problem that needs some investigation (althought it's not
> the main cause of owl's fail in this position).
>
> pattern 304 is perfectly valid, but it shouldn't match in this position.
> i'll try to look into the matter and determine why it got matched where
> 202 should have been.

here is a patch that solves the problem.

regression breakage:

trevorb:160     PASS 1 N8 [1 ..*]
trevorb:590     PASS M9 [H12|M9]
trevorc:240     PASS K2 [K2]
trevorc:820     FAIL B12 [A6]

i haven't looked at the passes, but the fail is not bad. gnugo thinks that
B12 kills the whole black dragon. it misses A10 after W:B12, B:C7, W:A9
(A9 looks like a clever move, but doesn't really work because of A10).
not a bad misread i think (and Evan agrees :) maybe a pattern can solve it.

i measured an increase in owl nodes of about 0.6 - 0.7%. however, the count
i took as original is for a slightly older of gnu go, so the real change
may differ a bit.

- find_half_and_false_eyes() bugfixed
- improve_lunch_attack() revised

smaller changes include:
- new type of marginal vertices INESSENTIAL_MARGINAL which don't (marginals
  that don't participate in graph matching)
- D219 pattern retired

thanks go to SP Lee for pointing the problem out.

Paul


Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.166
diff -u -p -r1.166 liberty.h
--- engine/liberty.h    1 May 2003 20:55:26 -0000       1.166
+++ engine/liberty.h    4 May 2003 20:40:08 -0000
@@ -51,9 +51,10 @@ extern Hash_data    hashdata;
 /* ================================================================ */
 
 
-#define FALSE_EYE          1
-#define HALF_EYE           2
-#define INHIBIT_CONNECTION 4
+#define FALSE_EYE              1
+#define HALF_EYE               2
+#define INHIBIT_CONNECTION     4
+#define INESSENTIAL_MARGINAL   8
 
 
 /* A string with n stones can have at most 2(n+1) liberties. From this
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.72
diff -u -p -r1.72 optics.c
--- engine/optics.c     12 Apr 2003 02:54:20 -0000      1.72
+++ engine/optics.c     4 May 2003 20:40:15 -0000
@@ -1125,46 +1125,47 @@ recognize_eye(int pos, int *attack_point
 
   /* Create list of eye vertices */
   for (pos2 = BOARDMIN; pos2 < BOARDMAX; pos2++) {
-    if (!ON_BOARD(pos2))
+    if (!ON_BOARD(pos2)
+       || eye[pos2].origin != pos
+       || (heye[pos2].type & INESSENTIAL_MARGINAL))
       continue;
-    if (eye[pos2].origin == pos) {
-      vpos[eye_size] = pos2;
-      marginal[eye_size] = eye[pos2].marginal;
+
+    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 (marginal[eye_size])
-       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;
-      }
-      
+       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++;
   }
   
   /* We attempt to construct a map from the graph to the eyespace
@@ -1495,18 +1496,31 @@ add_false_eye(int pos, struct eye_data e
              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++;
-  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++;
+  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--;
+      }
+    }
+  }
+
   propagate_eye(eye[pos].origin, eye);
 }
 
@@ -1589,8 +1603,12 @@ find_half_and_false_eyes(int color, stru
     
     /* 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)
+       || eye[pos].marginal
+#if 0
+       || (eye[pos].neighbors > 1 && !is_edge_vertex(pos)))
+#else
+       || eye[pos].neighbors > 1)
+#endif
       continue;
     
     sum = topological_eye(pos, color, eye, heye);
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.154
diff -u -p -r1.154 owl.c
--- engine/owl.c        30 Apr 2003 16:20:27 -0000      1.154
+++ engine/owl.c        4 May 2003 20:40:29 -0000
@@ -4492,6 +4492,7 @@ improve_lunch_attack(int lunch, int atta
   int adj[MAXCHAIN];
 
   if (safe_move(attack_point, color)) {
+#if 0
     if (countstones(lunch) == 1 && is_corner_vertex(attack_point)
        && chainlinks2(lunch, adj, 1) == 0) {
       for (k = 0; k < 4; k++) {
@@ -4504,6 +4505,29 @@ improve_lunch_attack(int lunch, int atta
        }
       }
     }
+#else
+    if (is_edge_vertex(lunch)
+       && is_edge_vertex(attack_point)
+       && neighbor_of_string(attack_point, lunch)) {
+      int stones = countstones(lunch);
+      int libs[2];
+
+      if (stones == 1
+         || (stones == 2
+             && findlib(lunch, 2, libs) == 2
+             && is_edge_vertex(libs[0])
+             && is_edge_vertex(libs[1]))) {
+       for (k = 0; k < 4; k++) {
+         int apos = attack_point + delta[k];
+         if (!ON_BOARD(attack_point - delta[k]) && board[apos] == EMPTY) {
+           if (does_attack(apos, lunch) && safe_move(apos, color))
+             return apos;
+           break;
+         }
+       }
+      }
+    }
+#endif
   
     return attack_point;
   }
Index: patterns/owl_defendpats.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/owl_defendpats.db,v
retrieving revision 1.92
diff -u -p -r1.92 owl_defendpats.db
--- patterns/owl_defendpats.db  2 May 2003 15:04:59 -0000       1.92
+++ patterns/owl_defendpats.db  4 May 2003 20:40:36 -0000
@@ -824,20 +824,21 @@ xx...X.        slide (usually inferior t
 :8,-,value(70)
 
 
-Pattern D219
-# tm Modified (3.1.17)
-
-OO*        capture edge stone to maybe make eye
-.X.
----
-
-:8,-,value(50)
-
-OO*
-aA.
----
-
-;does_attack(*,A) && !obvious_false_oeye(a)
+# pp Removed (3.3.20). This job is now done by improve_lunch_attack().
+#Pattern D219
+## tm Modified (3.1.17)
+#
+#OO*        capture edge stone to maybe make eye
+#.X.
+#---
+#
+#:8,-,value(50)
+#
+#OO*
+#aA.
+#---
+#
+#;does_attack(*,A) && !obvious_false_oeye(a)
 
 
 Pattern D220