[gnugo-devel] Re: Trevor test case 240

[Gunnar Farneback]

I wrote:
> The owl mistake is unfortunately not possible to solve by simple
> tuning but requires revising central parts of the owl code. If I find
> a solution I'll discuss that in a separate message.

The owl mistake is best illustrated in move 34 of trevor24.sgf. If we
run

../interface/gnugo --quiet -l games/trevor/trevor_24.sgf -L 34 --decide-dragon 
G9

using current CVS, we get

G9 cannot be attacked (1 variations)
G9 is alive as it stands

That is not at all the case since this is the position:

   A B C D E F G H J
 9 . . . . X . X X . 9
 8 . . . . . X O X . 8
 7 . . X . O X O X X 7
 6 . . . . . O O O . 6
 5 . . . . O . . O . 5
 4 . X X . . X . . . 4
 3 X . X X X . O . . 3
 2 . X O O O O . . . 2     WHITE has captured 0 stones
 1 . O . . . . . . . 1     BLACK has captured 2 stones
   A B C D E F G H J

To see better what happens we add the options "-t -d2" to the command
above and get a few hundred lines of traces. The interesting part is
this: 

> owl_attack G9
> half or false eye found at F9
> false eye at F9 for dragon at PASS
> Eyespace at A9: color=black border, esize=17, msize=3
> A9
> B9
> C9
> D9
> A8
> B8
> C8
> D8 (!)
> A7
> B7
> A6
> B6
> C6 (!)
> A5
> B5
> C5 (!)
> A4
> 
> ....
> ...!
> ..  
> ..! 
> ..! 
> .   
> 
> marginal eye space at D8, score 30 (eye at A9, max 2, min 2, pessimistic_min 
> 1)
> Eyespace at F9: color=black border, esize=1, msize=1
> F9 (!)
> 
> !
> 
> eye space at F9 of type 102
> Eyespace at J9: color=black border, esize=2, msize=0
> J9
> J8
> 
> .
> .
> 
> eye space at J9 of type 201
> Variation 0: ALIVE (2 or more secure eyes)
> G9 cannot be attacked (1 variations)

What this says is that it's counting the entire upper left corner and
parts of the left side as eyespace for the G9 dragon, thus thinking
it's well alive. This is of course no good.

To solve this either requires changing something in the eyespace
formation code or changing the conditions for counting an eyespace to
the dragon under consideration by the owl code. The latter approach is
more tractable. Today the requirement is that at least one
non-marginal vertex of the eye-space is adjacent to a stone of the
goal dragon, here D9 and E9 satisfy this condition. Clearly this
requirement isn't restrictive enough. After some experimentation I've
found that the following definition works better:

"An eyespace counts for the goal dragon if there are at least two
distinct connections, adjacent or diagonal, between non-marginal
vertices of the eye space and stones of the goal dragon."

The following patch implements this change and has been added to the
CVS. Apply the patch in reverse if you want to verify the analysis
above.

After the patch we here get

G9 can be attacked at D8 (6 variations)
G9 can be defended at D8 (2 variations)

which is quite correct.

/Gunnar

Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.15
diff -u -r1.15 owl.c
--- engine/owl.c        2001/10/04 18:38:53     1.15
+++ engine/owl.c        2001/10/06 20:34:15
@@ -1124,7 +1124,7 @@
                            &ko_move, savecode == 0))
        continue;
       TRACE("Trying %C %1m\n", other, mpos);
-      
+
       /* We have now made a move. Analyze the new position. */
       push_owl(owl);
       mw[mpos] = 1;
@@ -1869,9 +1869,10 @@
    * are the eyespaces of the dragon. Now we find their
    * origins.
    *
-   * It is required that at least one non-marginal eye space is
-   * directly adjacent to the goal dragon, otherwise there is a risk
-   * that we include irrelevant eye spaces.
+   * 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)
@@ -1882,26 +1883,15 @@
   for (m = 0; m < board_size; m++)
     for (n = 0; n < board_size; n++)
       if (BOARD(m, n) && owl->goal[m][n]) {
-       if (m > 0
-           && eye[POS(m-1, n)].color == eye_color
-           && eye[POS(m-1, n)].origin != NO_MOVE
-           && !eye[POS(m-1, n)].marginal)
-         mw[I(eye[POS(m-1, n)].origin)][J(eye[POS(m-1, n)].origin)] = 1;
-       if (m < board_size-1
-           && eye[POS(m+1, n)].color == eye_color
-           && eye[POS(m+1, n)].origin != NO_MOVE
-           && !eye[POS(m+1, n)].marginal)
-         mw[I(eye[POS(m+1, n)].origin)][J(eye[POS(m+1, n)].origin)] = 1;
-       if (n > 0
-           && eye[POS(m, n-1)].color == eye_color
-           && eye[POS(m, n-1)].origin != NO_MOVE
-           && !eye[POS(m, n-1)].marginal)
-         mw[I(eye[POS(m, n-1)].origin)][J(eye[POS(m, n-1)].origin)] = 1;
-       if (n < board_size-1
-           && eye[POS(m, n+1)].color == eye_color
-           && eye[POS(m, n+1)].origin != NO_MOVE
-           && !eye[POS(m, n+1)].marginal)
-         mw[I(eye[POS(m, n+1)].origin)][J(eye[POS(m, n+1)].origin)] = 1;
+       for (k = 0; k < 8; k++) {
+         int dm = deltai[k];
+         int dn = deltaj[k];
+         if (ON_BOARD2(m+dm, n+dn)
+             && eye[POS(m+dm, n+dn)].color == eye_color
+             && eye[POS(m+dm, n+dn)].origin != NO_MOVE
+             && !eye[POS(m+dm, n+dn)].marginal)
+           mw[I(eye[POS(m+dm, n+dn)].origin)][J(eye[POS(m+dm, 
n+dn)].origin)]++;
+       }
       }
 
   for (m = 0; m < board_size; m++)
@@ -1919,7 +1909,7 @@
     for (n = 0; n<board_size; n++) {
       if ((eye[POS(m, n)].color == eye_color)
          && (eye[POS(m, n)].origin != NO_MOVE)
-         && (mw[I(eye[POS(m, n)].origin)][J(eye[POS(m, n)].origin)])
+         && (mw[I(eye[POS(m, n)].origin)][J(eye[POS(m, n)].origin)] > 1)
          && (!eye[POS(m, n)].marginal || life)
          && (eye[POS(m, n)].neighbors <= 1)) {
        mx[m][n] = 1;
@@ -1994,7 +1984,7 @@
 
   for (m = 0; m < board_size; m++)
     for (n = 0; n < board_size; n++) 
-      if (mw[m][n]
+      if (mw[m][n] > 1
          && (eye[POS(m, n)].origin == POS(m, n)))
       {
        int value = 0;
@@ -2008,7 +1998,7 @@
         */
        for (i = 0; i < board_size; i++)
          for (j = 0; j < board_size; j++)
-           if (mw[i][j]
+           if (mw[i][j] > 1
                && eye[POS(i, j)].origin == POS(m, n)
                && owl->inessential[i][j])
              pessimistic_min = 0;