[gnugo-devel] persistent caching patch

[Gunnar Farneback]

In the recent NNGS game gnugo-3.5.2-mog-200311072205.sgf GNU Go played
a clearly meaningless move at Q1 (move 254). This turned out to be
caused by a too small active area in the persistent owl cache. At move
204,

   A B C D E F G H J K L M N O P Q R S T
19 . . . . . . . . . . . . . X . . O . . 19
18 . . . . . O O O X . X X X O X O . O . 18
17 . . . . . X X O X . . O X O X X O . . 17
16 . . O O O O O X . X X O O O O X . . . 16
15 . O X X X X X X . . . X . O . X O O . 15
14 . . O O O O O O X X . . . . . X O X O 14
13 . X O X . X O O . . . X . O O X O X . 13
12 . . O X . X X O X X X O O . X . X X . 12
11 . . . . X O O X X . . X O X . . . . . 11
10 . O . X . . . X . + . X O X . X . . . 10
 9 . O X X X X X . . O . . O O X . . . . 9
 8 O O O O O O X O . . O . . . O X . . . 8
 7 . O X X X X O O . . . . . O O X . . . 7
 6 . . X O O X O . . . O . X . . X . . . 6
 5 . X . O . O X O O . O . . O O X . . . 5
 4 . . . O . O X X X X X X X X O X . X . 4
 3 . . X X O O O X . . X O O O X X X . X 3
 2 . O . O . O . O X . X O . O O O O X . 2
 1 . . . . . . O . O O X O X X X . O O . 1
   A B C D E F G H J K L M N O P Q R S T

owl reading found the N1 dragon to be alive. (Arguable result but that
doesn't matter for this discussion.) Since the N1 dragon was entirely
enclosed by white stones, the active area became very small, namely

   A B C D E F G H J K L M N O P Q R S T
19 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 19
18 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 18
17 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 17
16 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 16
15 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 15
14 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 14
13 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 13
12 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 12
11 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 11
10 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 10
 9 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 9
 8 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 8
 7 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 7
 6 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 6
 5 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 5
 4 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 4
 3 ? ? ? ? ? ? ? ? ? ? ? o o o ? ? ? . ? 3
 2 ? ? ? ? ? ? ? ? ? ? ? o . o o o o ? . 2
 1 ? ? ? ? ? ? ? ? ? ? ? o[x]x x . o o . 1
   A B C D E F G H J K L M N O P Q R S T

The interesting thing here is that the liberties of the white M3
string are included in the active area since it is short on liberties
and a further reduction is rather likely to affect the reading.
However, what happened in the game was that M3 got an increase by six
liberties when the G5 string was captured, but since that string
wasn't included in the active area no new owl reading was done.

The conclusion is that it would make sense to include not only the
liberties but also the neighbors of low liberty strings in the active
area. Usually this would have no effect on the efficiency of the
persistent caches since stones on the board tend to remain where they
are, but when some neighbor happens to be captured it would clearly be
a good idea to redo the reading.

This patch implements this for the owl, connection, and break-in
persistent caches. The tactical reading persistent cache doesn't have
this problem. As part of the solution I needed to add a new variation
of the mark_string() function which works on a signed char array.

- new function signed_mark_string()
- computation of active area revised in store_persistent_connection_cache(), 
  store_persistent_breakin_cache(), and store_persistent_owl_cache()

I haven't checked the effect on the regressions yet.

/Gunnar

Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.87
diff -u -r1.87 board.c
--- engine/board.c      1 Oct 2003 14:36:38 -0000       1.87
+++ engine/board.c      8 Nov 2003 16:55:48 -0000
@@ -2862,6 +2862,23 @@
 }
 
 
+/* Signed char variant of the function above.
+ * FIXME: Do we want to convert all mark_string() to signed char?
+ */
+void
+signed_mark_string(int str, signed char mx[BOARDMAX], signed char mark)
+{
+  int pos = str;
+
+  ASSERT1(IS_STONE(board[str]), str);
+
+  do {
+    mx[pos] = mark;
+    pos = NEXT_STONE(pos);
+  } while (pos != str);
+}
+
+
 /* Returns true if at least one move has been played at pos
  * at deeper than level 'cutoff' in the reading tree.
  */
Index: engine/board.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.h,v
retrieving revision 1.4
diff -u -r1.4 board.h
--- engine/board.h      3 Sep 2003 16:59:58 -0000       1.4
+++ engine/board.h      8 Nov 2003 16:55:49 -0000
@@ -275,6 +275,7 @@
 int same_string(int str1, int str2);
 int adjacent_strings(int str1, int str2);
 void mark_string(int str, char mx[BOARDMAX], char mark);
+void signed_mark_string(int str, signed char mx[BOARDMAX], signed char mark);
 
 /* Count and/or find liberties at (pos). */
 int countlib(int str);
Index: engine/persistent.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/persistent.c,v
retrieving revision 1.18
diff -u -r1.18 persistent.c
--- engine/persistent.c 7 Sep 2003 23:02:45 -0000       1.18
+++ engine/persistent.c 8 Nov 2003 16:55:54 -0000
@@ -849,7 +849,7 @@
                                  int result, int move, int tactical_nodes,
                                  char connection_shadow[BOARDMAX])
 {
-  char active[BOARDMAX];
+  signed char active[BOARDMAX];
   int k;
   int r;
   int score = tactical_nodes;
@@ -913,15 +913,16 @@
    * the connection shadow +
    * distance two expansion through empty intersections and own stones +
    * adjacent opponent strings +
-   * liberties of adjacent opponent strings with less than five liberties +
-   * liberties of low liberty neighbors of adjacent opponent strings
-   * with less than five liberties.
+   * liberties and neighbors of adjacent opponent strings with less than
+   * five liberties +
+   * liberties and neighbors of low liberty neighbors of adjacent opponent
+   * strings with less than five liberties.
    */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
     active[pos] = connection_shadow[pos];
 
-  mark_string(str1, active, 1);
-  mark_string(str2, active, 1);
+  signed_mark_string(str1, active, 1);
+  signed_mark_string(str2, active, 1);
 
   /* To be safe, also add the successful move. */
   if (result != 0 && move != 0)
@@ -939,7 +940,7 @@
        if (board[pos] == EMPTY)
          active[pos] = k + 1;
        else
-         mark_string(pos, active, (char) (k + 1));
+         signed_mark_string(pos, active, (signed char) (k + 1));
       }
     }
   }
@@ -951,7 +952,7 @@
     for (r = 0; r < 4; r++) {
       int pos2 = pos + delta[r];
       if (ON_BOARD(pos2) && board[pos2] != other && active[pos2] != 0) {
-       mark_string(pos, active, (char) 1);
+       signed_mark_string(pos, active, 1);
        break;
       }
     }
@@ -962,7 +963,7 @@
    * with less than five liberties.
    */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-    if (board[pos] == other && active[pos] != 0 && countlib(pos) < 5) {
+    if (board[pos] == other && active[pos] > 0 && countlib(pos) < 5) {
       int libs[4];
       int liberties = findlib(pos, 4, libs);
       int adjs[MAXCHAIN];
@@ -975,11 +976,17 @@
        */
       adj = chainlinks(pos, adjs);
       for (r = 0; r < adj; r++) {
+       signed_mark_string(adjs[r], active, -1);
        if (countlib(adjs[r]) <= 3) {
          int s;
+         int adjs2[MAXCHAIN];
+         int adj2;
          liberties = findlib(adjs[r], 3, libs);
          for (s = 0; s < liberties; s++)
            active[libs[s]] = 1;
+         adj2 = chainlinks(pos, adjs2);
+         for (s = 0; s < adj2; s++)
+           signed_mark_string(adjs2[s], active, -1);
        }
       }
     }
@@ -995,7 +1002,7 @@
       continue;
     if (!active[pos])
       value = GRAY;
-    else if (IS_STONE(board[pos]) && countlib(pos) > 4)
+    else if (IS_STONE(board[pos]) && countlib(pos) > 4 && active[pos] > 0)
       value |= HIGH_LIBERTY_BIT;
     
     persistent_connection_cache[persistent_connection_cache_size].board[pos] =
@@ -1185,7 +1192,7 @@
                               int result, int move, int tactical_nodes,
                               char breakin_shadow[BOARDMAX])
 {
-  char active[BOARDMAX];
+  signed char active[BOARDMAX];
   int k;
   int r;
   struct breakin_cache *entry;
@@ -1245,14 +1252,15 @@
    * the breakin shadow (which contains the goal) +
    * distance two expansion through empty intersections and own stones +
    * adjacent opponent strings +
-   * liberties of adjacent opponent strings with less than five liberties +
-   * liberties of low liberty neighbors of adjacent opponent strings
-   * with less than five liberties.
+   * liberties and neighbors of adjacent opponent strings with less than
+   * five liberties +
+   * liberties and neighbors of low liberty neighbors of adjacent opponent
+   * strings with less than five liberties.
    */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
     active[pos] = breakin_shadow[pos];
 
-  mark_string(str, active, 1);
+  signed_mark_string(str, active, 1);
 
   /* To be safe, also add the successful move. */
   if (result != 0 && move != 0)
@@ -1270,7 +1278,7 @@
        if (board[pos] == EMPTY)
          active[pos] = k + 1;
        else
-         mark_string(pos, active, (char) (k + 1));
+         signed_mark_string(pos, active, (signed char) (k + 1));
       }
     }
   }
@@ -1284,7 +1292,7 @@
       if (ON_BOARD(pos2)
          && board[pos2] != other
          && active[pos2] && active[pos2] <= 2) {
-       mark_string(pos, active, (char) 1);
+       signed_mark_string(pos, active, 1);
        break;
       }
     }
@@ -1295,7 +1303,7 @@
    * with less than five liberties.
    */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-    if (board[pos] == other && active[pos] != 0 && countlib(pos) < 4) {
+    if (board[pos] == other && active[pos] > 0 && countlib(pos) < 4) {
       int libs[4];
       int liberties = findlib(pos, 3, libs);
       int adjs[MAXCHAIN];
@@ -1308,11 +1316,17 @@
        */
       adj = chainlinks(pos, adjs);
       for (r = 0; r < adj; r++) {
+       signed_mark_string(adjs[r], active, -1);
        if (countlib(adjs[r]) <= 3) {
          int s;
+         int adjs2[MAXCHAIN];
+         int adj2;
          liberties = findlib(adjs[r], 3, libs);
          for (s = 0; s < liberties; s++)
            active[libs[s]] = 1;
+         adj2 = chainlinks(pos, adjs2);
+         for (s = 0; s < adj2; s++)
+           signed_mark_string(adjs2[s], active, -1);
        }
       }
     }
@@ -1324,7 +1338,7 @@
       continue;
     if (!active[pos])
       value = GRAY;
-    else if (IS_STONE(board[pos]) && countlib(pos) > 3)
+    else if (IS_STONE(board[pos]) && countlib(pos) > 3 && active[pos] > 0)
       value |= HIGH_LIBERTY_BIT2;
     
     persistent_breakin_cache[persistent_breakin_cache_size].board[pos] =
@@ -1458,7 +1472,7 @@
                           int tactical_nodes,
                           char goal[BOARDMAX], int goal_color)
 {
-  char active[BOARDMAX];
+  signed char active[BOARDMAX];
   int pos;
   int k;
   int r;
@@ -1492,9 +1506,10 @@
    * the goal +
    * distance four expansion through empty intersections and own stones +
    * adjacent opponent strings +
-   * liberties of adjacent opponent strings with less than five liberties +
-   * liberties of low liberty neighbors of adjacent opponent strings
-   * with less than five liberties.
+   * liberties and neighbors of adjacent opponent strings with less than
+   * five liberties +
+   * liberties and neighbors of low liberty neighbors of adjacent opponent
+   * strings with less than five liberties.
    */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
     if (ON_BOARD(pos))
@@ -1510,7 +1525,7 @@
   /* Distance four expansion through empty intersections and own stones. */
   for (k = 1; k < 5; k++) {
     for (pos = BOARDMIN; pos < BOARDMAX; pos++){
-      if (!ON_BOARD(pos) || board[pos] == other || active[pos] != 0) 
+      if (!ON_BOARD(pos) || board[pos] == other || active[pos] > 0) 
        continue;
       if ((ON_BOARD(SOUTH(pos)) && active[SOUTH(pos)] == k)
          || (ON_BOARD(WEST(pos)) && active[WEST(pos)] == k)
@@ -1519,7 +1534,7 @@
        if (board[pos] == EMPTY)
          active[pos] = k + 1;
        else
-         mark_string(pos, active, (char) (k + 1));
+         signed_mark_string(pos, active, (signed char) (k + 1));
       }
     }
   }
@@ -1531,7 +1546,7 @@
     for (r = 0; r < 4; r++) {
       int pos2 = pos + delta[r];
       if (ON_BOARD(pos2) && board[pos2] != other && active[pos2] != 0) {
-       mark_string(pos, active, (char) 1);
+       signed_mark_string(pos, active, 1);
        break;
       }
     }
@@ -1542,7 +1557,7 @@
    * with less than five liberties.
    */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-    if (board[pos] == other && active[pos] != 0 && countlib(pos) < 5) {
+    if (board[pos] == other && active[pos] > 0 && countlib(pos) < 5) {
       int libs[4];
       int liberties = findlib(pos, 4, libs);
       int adjs[MAXCHAIN];
@@ -1555,11 +1570,17 @@
        */
       adj = chainlinks(pos, adjs);
       for (r = 0; r < adj; r++) {
+       signed_mark_string(adjs[r], active, -1);
        if (countlib(adjs[r]) <= 3) {
          int s;
+         int adjs2[MAXCHAIN];
+         int adj2;
          liberties = findlib(adjs[r], 3, libs);
          for (s = 0; s < liberties; s++)
            active[libs[s]] = 1;
+         adj2 = chainlinks(pos, adjs2);
+         for (s = 0; s < adj2; s++)
+           signed_mark_string(adjs2[s], active, -1);
        }
       }
     }
@@ -1571,7 +1592,7 @@
       continue;
     if (!active[pos])
       value = GRAY;
-    else if (IS_STONE(board[pos]) && countlib(pos) > 4)
+    else if (IS_STONE(board[pos]) && countlib(pos) > 4 && active[pos] > 0)
       value |= HIGH_LIBERTY_BIT;
     
     persistent_owl_cache[persistent_owl_cache_size].board[pos] = value;