[gnugo-devel] optics patch

[Gunnar Farneback]

This patch revises mkeyes.c, recognize_eye() and adds some rather cool
functionality to test the consistency of the eye graph database.

- recognize_eye() revised
- new function test_eyeshape() in optics.c
- new gtp command test_eyeshape
- vital and num_vital fields removed from struct eye_graph
- mkeyes.c revised
- bugfixes in eyes.db

The revision of recognize_eye() is mostly code reorganization, but it
also makes the change that a pattern (with min != max) doesn't have to
have one common vital point (* or @); it suffices with separate attack
and defense points.

What's really fun here though is the test_eyeshape() function. To
explain what it does, I'll give an example. Start GNU Go in gtp mode
and run the commands

boardsize 9
test_eyeshape E6 F6 E5 F5 F4

The test_eyeshape() function is called and plays up this position:

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

Then it loops through all configurations of black stones inside the
eyespace. For each configuration it calls the owl code to get the
status of the white group. If the group is alive, it tests all legal
black moves inside the eyespace and checks with the owl code that
white has a defense. If the group is dead, it tests all white moves
inside the eyespace and checks with the owl code that there still is
an attack. If the group is critical, it tests that the given attack
and defense moves are indeed effective. Finally, if the group is alive
and black has filled all the eyespace except for a single point, it is
verified that white is still alive after capturing the black stones.

Inconsistencies are reported like below:

G3 dead, but F6 defends:
   A B C D E F G H J
 9 . . X X X X X X . 9
 8 . X X . . . . X X 8
 7 . X + O O O O . X 7
 6 . X . O X . O . X 6
 5 . X . O + X O . X 5
 4 . X . O O X O . X 4
 3 . X X . O O O . X 3
 2 . . X X . . . X X 2     WHITE has captured 0 stones
 1 . . . X X X X X . 1     BLACK has captured 0 stones
   A B C D E F G H J

G3 dead, but E5 defends:
   A B C D E F G H J
 9 . . X X X X X X . 9
 8 . X X . . . . X X 8
 7 . X + O O O O . X 7
 6 . X . O X . O . X 6
 5 . X . O + X O . X 5
 4 . X . O O X O . X 4
 3 . X X . O O O . X 3
 2 . . X X . . . X X 2     WHITE has captured 0 stones
 1 . . . X X X X X . 1     BLACK has captured 0 stones
   A B C D E F G H J

This considerably eases the detection of errors in the graph database.
Consistency of the database doesn't imply correctness, though, but it
goes a long way in the right direction.

Some remarks:
* This is just a limited start, only allowing test of closed eyespaces
  with an abundance of outer liberties. There is much more to do with
  this new testing paradigm.
* This doesn't test just the graph database but rather the owl code in
  it's entirety. 
* Don't bother starting to fix eyes.db. You will just conflict with
  changes I'm doing.
* Use "-t" to see the eyeshape it's analyzing. Use "-t -t" to see all
  tested positions.

The patch is in the CVS.

/Gunnar

Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.45
diff -u -r1.45 liberty.h
--- engine/liberty.h    2001/11/14 19:16:28     1.45
+++ engine/liberty.h    2001/11/15 21:41:07
@@ -470,6 +470,7 @@
 int max_eye_value(int pos);
 void make_proper_eye_space(int pos, int color);
 void remove_eyepoint(int pos, int color);
+void test_eyeshape(int eyesize, int *eye_vertices);
 
 
 /* debugging support */
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.25
diff -u -r1.25 optics.c
--- engine/optics.c     2001/11/10 14:07:10     1.25
+++ engine/optics.c     2001/11/15 21:41:09
@@ -1359,7 +1359,7 @@
  * half_eye_data, add_moves, color), where pos is the origin of an eyespace,
  * returns 1 if there is a pattern in eyes.c matching the eyespace, or
  * 0 if no match is found. If there is a key point for attack, (*attack_point)
- * is set to its location, or (-1, -1) if there is none.
+ * is set to its location, or NO_MOVE if there is none.
  * Similarly (*defense_point) is the location of a vital defense point. *min
  * and *max are the minimum and maximum number of eyes that can be
  * made in this eyespace respectively. Vital attack/defense points
@@ -1390,6 +1390,9 @@
   int kpos;
   int num_marginals = 0;
 
+  gg_assert(attack_point != NULL);
+  gg_assert(defense_point != NULL);
+    
   /* Set `eye_color' to the owner of the eye. */
   eye_color = eye[pos].color;
   if (eye_color == BLACK_BORDER)
@@ -1544,71 +1547,74 @@
       }
     }
 
+    /* We have found a match! Now sort out the vital moves. */
     if (q == eye_size) {
       *max = graphs[graph].max;
       *min = graphs[graph].min;
       if (*max != *min) {
-       gg_assert(graphs[graph].vital >= 0);
-       if (attack_point)
-         *attack_point = vpos[map[graphs[graph].vital]];
-       if (defense_point)
-         *defense_point = vpos[map[graphs[graph].vital]];
+       /* Collect all attack and defense points in the pattern. */
+       int attack_points[4 * MAXEYE];
+       int defense_points[4 * MAXEYE];
+       int num_attacks = 0;
+       int num_defenses = 0;
+
+       for (k = 0; k < graphs[graph].esize; k++) {
+         if (graphs[graph].vertex[k].type == '*'
+             || graphs[graph].vertex[k].type == '<')
+           attack_points[num_attacks++] = vpos[map[k]];
+         else if (graphs[graph].vertex[k].type == '@'
+                  || graphs[graph].vertex[k].type == '(') {
+           /* check for marginal matching half eye diagonal
+            * If it is a half eye diagonal, the half eye preceeds
+            * the diagonal in the list of vertices
+            */
+           if (map[k] > 0 && is_halfeye(heye, vpos[map[k]-1])) {
+             /* add all diagonals as vital */
+             int ix;
+             struct half_eye_data *this_half_eye = &heye[vpos[map[k]-1]];
+             
+             for (ix = 0; ix < this_half_eye->num_attacks; ix++)
+               attack_points[num_attacks++] = this_half_eye->attack_point[ix];
+           }
+           else
+             attack_points[num_attacks++] = vpos[map[k]];
+         }
+         
+         if (graphs[graph].vertex[k].type == '*'
+             || graphs[graph].vertex[k].type == '>')
+           defense_points[num_defenses++] = vpos[map[k]];
+         else if (graphs[graph].vertex[k].type == '@'
+                  || graphs[graph].vertex[k].type == ')') {
+           /* check for marginal matching half eye diagonal */
+           if (map[k] > 0 && is_halfeye(heye, vpos[map[k]-1])) {
+             /* add all diagonals as vital */
+             int ix;
+             struct half_eye_data *this_half_eye = &heye[vpos[map[k]-1]];
+
+             for (ix = 0; ix < this_half_eye->num_defends; ix++)
+               defense_points[num_defenses++] = 
this_half_eye->defense_point[ix];
+           }
+           else
+             defense_points[num_defenses++] = vpos[map[k]];
+         }
+       }
+       
+       gg_assert(num_attacks > 0 && num_defenses > 0);
+       *attack_point = attack_points[0];
+       *defense_point = defense_points[0];
        DEBUG(DEBUG_EYES, "  vital points: %1m (attack) %1m (defense)\n",
              *attack_point, *defense_point);
        DEBUG(DEBUG_EYES, "  pattern matched:  %d\n", graphs[graph].id);
 
        if (add_moves) {
-         for (k = graphs[graph].vital; k < graphs[graph].esize; k++) {
-           if (eye_color != color) {
-             if (graphs[graph].vertex[k].type == '*'
-                 || graphs[graph].vertex[k].type == '<') {
-               /* add attack vital move */
-               add_vital_eye_move(vpos[map[k]], pos, eye_color);
-             }
-             else if (graphs[graph].vertex[k].type == '@'
-                      || graphs[graph].vertex[k].type == '(') {
- 
-               /* check for marginal matching half eye diagonal
-                * If it is a half eye diagonal, the half eye preceeds
-                * the diagonal in the list of vertices
-                */
-               if (map[k] > 0 && is_halfeye(heye, vpos[map[k]-1])) {
-                 /* add all diagonals as vital */
-                 int ix;
-                 struct half_eye_data *this_half_eye = &heye[vpos[map[k]-1]];
-
-                 for (ix = 0; ix < this_half_eye->num_attacks; ix++) {
-                   add_vital_eye_move(this_half_eye->attack_point[ix],
-                                      pos, eye_color);
-                 }
-               }
-               else
-                 add_vital_eye_move(vpos[map[k]], pos, eye_color);
-             }
-           }
-           else {
-             if (graphs[graph].vertex[k].type == '*'
-                 || graphs[graph].vertex[k].type == '>')
-               /* add defense vital move */
-               add_vital_eye_move(vpos[map[k]], pos, eye_color);
-             else if (graphs[graph].vertex[k].type == '@'
-                      || graphs[graph].vertex[k].type == ')') {
-               /* check for marginal matching half eye diagonal */
-               if (map[k] > 0 && is_halfeye(heye, vpos[map[k]-1])) {
-                 /* add all diagonals as vital */
-                 int ix;
-                 struct half_eye_data *this_half_eye = &heye[vpos[map[k]-1]];
-
-                 for (ix = 0; ix < this_half_eye->num_defends; ix++) {
-                   add_vital_eye_move(this_half_eye->defense_point[ix],
-                                      pos, eye_color);
-                 }
-               }
-               else
-                 add_vital_eye_move(vpos[map[k]], pos, eye_color);
-             }
-           }
+         if (eye_color != color) {
+           for (k = 0; k < num_attacks; k++)
+             add_vital_eye_move(attack_points[k], pos, eye_color);
          }
+         else {
+           for (k = 0; k < num_defenses; k++)
+             add_vital_eye_move(defense_points[k], pos, eye_color);
+         }
        }
       }
       TRACE("eye space at %1m of type %d\n", pos, graphs[graph].id);
@@ -1999,6 +2005,185 @@
   }
 
   return value;
+}
+
+
+/* Test whether the optics code evaluates an eyeshape consistently. */
+void test_eyeshape(int eyesize, int *eye_vertices)
+{
+  int k;
+  int n, N;
+  int mx[BOARDMAX];
+  int pos;
+  int str = NO_MOVE;
+  int attack_code;
+  int attack_point;
+  int defense_code;
+  int defense_point;
+  int save_verbose;
+  Position starting_position;
+
+  /* Clear the board and initialize the engine properly. */
+  clear_board();
+  reset_engine();
+
+  /* Mark the eyespace in the mx array. */
+  memset(mx, 0, sizeof(mx));
+  for (k = 0; k < eyesize; k++) {
+    ASSERT_ON_BOARD1(eye_vertices[k]);
+    mx[eye_vertices[k]] = 1;
+  }
+
+  /* Play white stones surrounding the eyespace, including diagonals. */
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (!ON_BOARD(pos) || mx[pos] == 1)
+      continue;
+    for (k = 0; k < 8; k++) {
+      if (ON_BOARD(pos + delta[k]) && mx[pos + delta[k]] == 1) {
+       play_move(pos, WHITE);
+       str = pos;
+       break;
+      }
+    }
+  }
+
+  /* Play black stones surrounding the white group, but leaving all
+   * liberties empty.
+   */
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (mx[pos] == 1 || board[pos] != EMPTY || liberty_of_string(pos, str))
+      continue;
+    for (k = 0; k < 8; k++) {
+      if (ON_BOARD(pos + delta[k])
+         && liberty_of_string(pos + delta[k], str)) {
+       play_move(pos, BLACK);
+       break;
+      }
+    }
+  }
+
+  /* Show the board if verbose is on. Then turn off traces so we don't
+   * get any from make_worms(), make_dragons(), or the owl reading.
+   */
+  if (verbose)
+    showboard(0);
+  save_verbose = verbose;
+  verbose = 0;
+  
+  
+  /* Store this position so we can come back to it. */
+  store_position(&starting_position);
+
+  /* Loop over all configurations of black stones inserted in the
+   * eyeshape. There are N = 2^(eyesize) configurations and we can
+   * straightforwardly use binary representation to enumerate them.
+   */
+  N = 1 << eyesize;
+  for (n = 0; n < N; n++) {
+    int valid = 1;
+    int internal_stones = 0;
+    
+    restore_position(&starting_position);
+    /* Play the stones for this configuration. */
+    for (k = 0; k < eyesize; k++) {
+      if (n & (1 << k)) {
+       if (!is_legal(eye_vertices[k], BLACK)) {
+         valid = 0;
+         break;
+       }
+       play_move(eye_vertices[k], BLACK);
+       internal_stones++;
+      }
+    }
+
+    if (!valid)
+      continue;
+
+    if (save_verbose > 1)
+      showboard(0);
+
+    /* Now we are ready to test the consistency. This is most easily
+     * done with help from the owl code. First we must prepare for
+     * this though.
+     */
+    examine_position(WHITE, EXAMINE_DRAGONS_WITHOUT_OWL);
+
+    attack_code = owl_attack(str, &attack_point, NULL);
+
+    if (attack_code == 0) {
+      /* The owl code claims there is no attack. We test this by
+       * trying to attack on all empty spaces in the eyeshape.
+       */
+      for (k = 0; k < eyesize; k++) {
+       if (board[eye_vertices[k]] == EMPTY
+           && is_legal(eye_vertices[k], BLACK)
+           && owl_does_attack(eye_vertices[k], str)) {
+         gprintf("%1m alive, but %1m attacks:\n",
+                 str, eye_vertices[k]);
+         showboard(0);
+         gprintf("\n");
+       }
+      }
+
+      /* Furthermore, if the eyespace is almost filled, white should
+       * be able to play on the remaining eyespace point and still be
+       * alive.
+       */
+      if (internal_stones == eyesize - 1) {
+       for (k = 0; k < eyesize; k++) {
+         if (board[eye_vertices[k]] == EMPTY
+             && !owl_does_defend(eye_vertices[k], str)) {
+           gprintf("%1m alive, but almost filled with nakade:\n",
+                   str);
+           showboard(0);
+         }
+       }
+      }
+    }
+    else {
+      defense_code = owl_defend(str, &defense_point, NULL);
+      if (defense_code == 0) {
+       /* The owl code claims there is no defense. We test this by
+        * trying to defend on all empty spaces in the eyeshape.
+        */
+       for (k = 0; k < eyesize; k++) {
+         if (board[eye_vertices[k]] == EMPTY
+             && is_legal(eye_vertices[k], WHITE)
+             && owl_does_defend(eye_vertices[k], str)) {
+           gprintf("%1m dead, but %1m defends:\n",
+                   str, eye_vertices[k]);
+           showboard(0);
+           gprintf("\n");
+         }
+       }
+      }
+      else {
+       /* The owl code claims the dragon is critical. Verify the
+         * attack and defense points.
+        */
+       if (board[attack_point] != EMPTY
+                || !is_legal(attack_point, BLACK)) {
+         gprintf("Bad attack point %1m:\n", attack_point);
+         showboard(0);
+       }
+       else if (!owl_does_attack(attack_point, str)) {
+         gprintf("Attack point %1m failed:\n", attack_point);
+         showboard(0);
+       }
+
+       if (board[defense_point] != EMPTY
+                || !is_legal(defense_point, WHITE)) {
+         gprintf("Bad defense point %1m:\n", defense_point);
+         showboard(0);
+       }
+       else if (!owl_does_defend(defense_point, str)) {
+         gprintf("Defense point %1m failed:\n", defense_point);
+         showboard(0);
+       }
+      }
+    }
+  }
+  verbose = save_verbose;
 }
 
 
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.43
diff -u -r1.43 play_gtp.c
--- interface/play_gtp.c        2001/11/15 16:18:40     1.43
+++ interface/play_gtp.c        2001/11/15 21:41:10
@@ -126,6 +126,7 @@
 DECLARE(gtp_set_level);
 DECLARE(gtp_showboard);
 DECLARE(gtp_start_sgftrace);
+DECLARE(gtp_test_eyeshape);
 DECLARE(gtp_top_moves);
 DECLARE(gtp_top_moves_white);
 DECLARE(gtp_top_moves_black);
@@ -199,6 +200,7 @@
   {"same_dragon",            gtp_same_dragon},
   {"showboard",                      gtp_showboard},
   {"start_sgftrace",         gtp_start_sgftrace},
+  {"test_eyeshape",           gtp_test_eyeshape},
   {"top_moves",               gtp_top_moves},
   {"top_moves_black",         gtp_top_moves_black},
   {"top_moves_white",         gtp_top_moves_white},
@@ -1784,6 +1786,37 @@
 /*********
  * debug *
  *********/
+
+
+/* Function:  Test an eyeshape for inconsistent evaluations
+ * Arguments: Eyeshape vertices
+ * Fails:     Bad vertices
+ * Returns:   Failure reports on stderr.
+ */
+static int
+gtp_test_eyeshape(char *s, int id)
+{
+  int n;
+  int i, j;
+  int eye_vertices[MAX_BOARD * MAX_BOARD];
+  int eyesize = 0;
+
+  n = gtp_decode_coord(s, &i, &j);
+  while (n > 0) {
+    eye_vertices[eyesize] = POS(i, j);
+    eyesize++;
+    s += n;
+    n = gtp_decode_coord(s, &i, &j);
+  }
+  
+  if (eyesize == 0)
+    return gtp_failure(id, "invalid coordinate");
+
+  test_eyeshape(eyesize, eye_vertices);
+
+  return gtp_success(id, "");
+}
+
 
 
 /* Function:  Returns elapsed CPU time in seconds.
Index: patterns/eyes.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/eyes.db,v
retrieving revision 1.10
diff -u -r1.10 eyes.db
--- patterns/eyes.db    2001/11/14 19:16:28     1.10
+++ patterns/eyes.db    2001/11/15 21:41:11
@@ -278,7 +278,7 @@
 # Match before 421
 
  X
-X*X
+X.X
 
 :2,2
 
@@ -931,7 +931,7 @@
 Pattern 572
 
 xx
address@hidden
+!X!
 
 :0,0
 
Index: patterns/eyes.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/eyes.h,v
retrieving revision 1.3
diff -u -r1.3 eyes.h
--- patterns/eyes.h     2001/09/06 21:34:20     1.3
+++ patterns/eyes.h     2001/11/15 21:41:11
@@ -58,9 +58,6 @@
   int three_neighbors;            /* number of vertices with 3 neighbors   */
   int max;                        /* number of eyes if O plays first       */
   int min;                        /* number of eyes if X plays first       */
-  int vital;                      /* 1st attack and defense vital point    */
-                                 /* (only if max != min)  */
-  int num_vital;                  /* number of vital points                */
 };
 
 extern struct eye_graph graphs[];
Index: patterns/mkeyes.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkeyes.c,v
retrieving revision 1.3
diff -u -r1.3 mkeyes.c
--- patterns/mkeyes.c   2001/09/06 21:34:20     1.3
+++ patterns/mkeyes.c   2001/11/15 21:41:11
@@ -62,8 +62,8 @@
   int ends[MAXPATNO];
   int two_neighbors[MAXPATNO];
   int three_neighbors[MAXPATNO];
-  int vital[MAXPATNO];
-  int num_vital[MAXPATNO];
+  int num_attacks = 0;
+  int num_defenses = 0;
   int debug = 0;
   
   printf("\
@@ -78,8 +78,6 @@
   memset(two_neighbors, 0, sizeof(two_neighbors));
   memset(three_neighbors, 0, sizeof(three_neighbors));
   memset(esize, 0, sizeof(esize));
-  memset(vital, -1, sizeof(vital));
-  memset(num_vital, 0, sizeof(num_vital));
 
   while (fgets(line, MAXLINE, stdin)) {
 
@@ -112,6 +110,8 @@
       m = 0;
       esize[patno] = 0;
       msize[patno] = 0;
+      num_attacks = 0;
+      num_defenses = 0;
       continue;
     }
     
@@ -164,16 +164,20 @@
          case '@':
            msize[patno]++;
            marginal[m][n] = 1;
-           if (vital[patno] < 0)
-             vital[patno] = esize[patno];
-           num_vital[patno]++;
+           num_attacks++;
+           num_defenses++;
            break;
            
          case '(':
+           msize[patno]++;
+           marginal[m][n] = 1;
+           num_attacks++;
+           break;
+           
          case ')':
            msize[patno]++;
            marginal[m][n] = 1;
-           num_vital[patno]++;
+           num_defenses++;
            break;
            
          case 'x':
@@ -182,15 +186,18 @@
            
          case '*':
            marginal[m][n] = 0;
-           if (vital[patno] < 0)
-             vital[patno] = esize[patno];
-           num_vital[patno]++;
+           num_attacks++;
+           num_defenses++;
            break;
            
          case '<':
+           marginal[m][n] = 0;
+           num_attacks++;
+           break;
+
          case '>':
            marginal[m][n] = 0;
-           num_vital[patno]++;
+           num_defenses++;
            break;
            
          case 'X':
@@ -199,8 +206,8 @@
            
          default:
            fprintf(stderr, 
-                   "mkeyes: invalid character %c in pattern\n",
-                   line[n]);
+                   "mkeyes: invalid character %c in pattern %d\n",
+                   line[n], eye_number[patno]);
            abort();
            break;
        }
@@ -215,6 +222,25 @@
       sscanf(line, ":%d,%d", &(max[patno]), &(min[patno]));
       if (debug)
        fprintf(stderr, "max=%d, min=%d\n", max[patno], min[patno]);
+
+      if (max[patno] != min[patno]) {
+       if (num_attacks == 0 || num_defenses == 0) {
+         fprintf(stderr,
+                 "mkeyes: missing attack or defense point in pattern %d\n",
+                 eye_number[patno]);
+         abort();
+       }
+      }
+      
+      if (max[patno] == min[patno]) {
+       if (num_attacks > 0 || num_defenses > 0) {
+         fprintf(stderr,
+                 "mkeyes: attack or defense point in settled pattern %d\n",
+                 eye_number[patno]);
+         abort();
+       }
+      }
+      
       printf("static struct eye_vertex eye%d[] = {\n", eye_number[patno]);
       for (l = 0; l < esize[patno]; l++) {
        
@@ -292,10 +318,11 @@
        else
          printf("\n};\n\n");
       }
+      
       patno++;
       if (patno >= MAXPATNO) {
        fprintf(stderr,
-               "Error: Too many eye patterns. Increase MAXPATNO in 
mkeyes.c\n");
+               "mkeyes: Too many eye patterns. Increase MAXPATNO in 
mkeyes.c\n");
        abort();
       }
     }
@@ -305,14 +332,13 @@
   printf("\nstruct eye_graph graphs[] = {\n");
   for (l = 0; l < patno; l++) {
 
-    printf("   {eye%d, %d, %d, %d, %d, %d, %d, %d, %d, %d, %d}",
+    printf("   {eye%d, %d, %d, %d, %d, %d, %d, %d, %d}",
           eye_number[l], eye_number[l], esize[l], msize[l], ends[l],
-          two_neighbors[l], three_neighbors[l], max[l], min[l], vital[l],
-          num_vital[l]);
+          two_neighbors[l], three_neighbors[l], max[l], min[l]);
     if (l < patno-1)
       printf(",\n");
     else
-      printf(",\n{NULL, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}\n};\n");
+      printf(",\n{NULL, 0, 0, 0, 0, 0, 0, 0, 0}\n};\n");
   }
   return 0;
 }