[gnugo-devel] breakin speedup

[Arend Bayer]

- persistent breakin cache made more aggressive

This makes the active area somewhat smaller, and more importantly, it
uses 3 liberties instead of 4 as cutoff for a "high liberty bit".

It causes two FAILs, but I think the performance boost is worth it.

This is the last non-trivial thing from my personal todo-list for 3.4,
and in particular I don't expect any substantial change to the break-in
code anymore. So we can now seriously evaluate whether we want to
have the break-in code on by default.
I will send new timings result in a separate e-mail.

Arend


trevora:370     FAIL D9 [F6]
trevorb:510     FAIL A7 [C6|B6]
Total nodes: 1500306519 2301782 8424426


Index: engine/persistent.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/persistent.c,v
retrieving revision 1.13
diff -u -p -r1.13 persistent.c
--- engine/persistent.c 18 Jun 2003 14:26:58 -0000      1.13
+++ engine/persistent.c 24 Jun 2003 09:34:43 -0000
@@ -61,7 +61,8 @@
 /* ================================================================ */

 /* Used in active area. */
-#define HIGH_LIBERTY_BIT 4
+#define HIGH_LIBERTY_BIT  4
+#define HIGH_LIBERTY_BIT2 8

 /* Tactical reading cache. */

@@ -214,11 +215,11 @@ draw_active_area(char board[BOARDMAX], i
        c = '.';
       else if (board[pos] == WHITE)
        c = cw;
-      else if (board[pos] == (WHITE | HIGH_LIBERTY_BIT))
+      else if (board[pos] & 3 == WHITE)
        c = 'O';
       else if (board[pos] == BLACK)
        c = cb;
-      else if (board[pos] == (BLACK | HIGH_LIBERTY_BIT))
+      else if (board[pos] & 3 == BLACK)
        c = 'X';
       if (board[pos] == GRAY)
        c = '?';
@@ -252,9 +253,10 @@ verify_stored_board(char p[BOARDMAX])
       continue;
     else if ((p[pos] & 3) != board[pos])
       return 0;
-    else if (!(p[pos] & HIGH_LIBERTY_BIT))
+    else if (!(p[pos] & (HIGH_LIBERTY_BIT | HIGH_LIBERTY_BIT2)))
       continue;
-    else if (countlib(pos) <= 4)
+    else if (((p[pos] & HIGH_LIBERTY_BIT) && countlib(pos) <= 4)
+             || (p[pos] & HIGH_LIBERTY_BIT2 && countlib(pos) <= 3))
       return 0;
   }

@@ -1037,6 +1039,7 @@ print_persistent_connection_cache_entry(
 /*                   Break-in reading functions                     */
 /* ================================================================ */

+
 /* Remove persistent cache entries which are no longer current. */
 void
 purge_persistent_breakin_cache()
@@ -1114,6 +1117,7 @@ find_persistent_breakin_cache_entry(int
                                    Hash_data goal_hash)
 {
   int k;
+  int color;
   ASSERT1(str == find_origin(str), str);

   for (k = 0; k < persistent_breakin_cache_size; k++) {
@@ -1233,8 +1237,8 @@ store_persistent_breakin_cache(int routi
   }

   /* Remains to set the board. We let the active area be
-   * the two strings to connect +
-   * the breakin shadow +
+   * the string to connect +
+   * 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 +
@@ -1273,21 +1277,23 @@ store_persistent_breakin_cache(int routi
       continue;
     for (r = 0; r < 4; r++) {
       int pos2 = pos + delta[r];
-      if (ON_BOARD(pos2) && board[pos2] != other && active[pos2] != 0) {
+      if (ON_BOARD(pos2)
+         && board[pos2] != other
+         && active[pos2] && active[pos2] <= 2) {
        mark_string(pos, active, (char) 1);
        break;
       }
     }
   }

-  /* Liberties of adjacent opponent strings with less than five liberties +
+  /* Liberties of adjacent opponent strings with less than four liberties +
    * liberties of low liberty neighbors of adjacent opponent strings
    * 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) < 4) {
       int libs[4];
-      int liberties = findlib(pos, 4, libs);
+      int liberties = findlib(pos, 3, libs);
       int adjs[MAXCHAIN];
       int adj;
       for (r = 0; r < liberties; r++)
@@ -1309,13 +1315,13 @@ store_persistent_breakin_cache(int routi
   }

   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
-    int value = board[pos];
+    char value = board[pos];
     if (!ON_BOARD(pos))
       continue;
     if (!active[pos])
       value = GRAY;
-    else if (IS_STONE(board[pos]) && countlib(pos) > 4)
-      value |= HIGH_LIBERTY_BIT;
+    else if (IS_STONE(board[pos]) && countlib(pos) > 3)
+      value |= HIGH_LIBERTY_BIT2;

     persistent_breakin_cache[persistent_breakin_cache_size].board[pos] =
       value;
Index: engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.74
diff -u -p -r1.74 utils.c
--- engine/utils.c      21 Jun 2003 06:02:14 -0000      1.74
+++ engine/utils.c      24 Jun 2003 09:34:45 -0000
@@ -636,7 +636,7 @@ play_connect_n(int color, int do_connect
 #define CONNECT_DEPTH2       20

 #define BREAKIN_NODE_LIMIT  400
-#define BREAKIN_DEPTH       15
+#define BREAKIN_DEPTH       14

 /* Set the various reading depth parameters. If mandated_depth_value
  * is not -1 that value is used; otherwise the depth values are