[gnugo-devel] fast_defense() improvement

[nando]

Hi,

The idea is simple : there might be some adjacent opponent stones in atari,
checking if capturing them wouldn't give enough liberties to win, proved to
be cheap enough.

No breakage. Performance impact :
- reading nodes :      -4.7%
- owl nodes :        < +0.1%
- connection nodes : < +0.01%

My imprecise timings give me a 4% speedup.

nando

- new function count_adj_stones() in board.c
- fast_defense() looks for neighbor opponent strings in atari

Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.98
diff -u -r1.98 board.c
--- engine/board.c      27 May 2004 00:08:46 -0000      1.98
+++ engine/board.c      29 May 2004 20:36:01 -0000
@@ -2383,6 +2383,41 @@
 }
 
 
+/* Counts how many stones in str1 are directly adjacent to str2.
+ * A limit can be given in the maxstones parameter so that the
+ * function returns immediately. See fast_defense() in reading.c
+ */
+
+int
+count_adj_stones(int str1, int str2, int maxstones)
+{
+  int s1, s2;
+  int size;
+  int pos;
+  int k;
+  int count = 0;
+
+  ASSERT_ON_BOARD1(str1);
+  ASSERT1(IS_STONE(board[str1]), str1);
+  ASSERT_ON_BOARD1(str2);
+  ASSERT1(IS_STONE(board[str2]), str2);
+
+  s1 = string_number[str1];
+  s2 = string_number[str2];
+  size = string[s1].size;
+
+  /* Traverse the stones of the string, by following the cyclic chain. */
+  pos = FIRST_STONE(s1);
+  for (k = 0; k < size && count < maxstones; k++) {
+    if (NEIGHBOR_OF_STRING(pos, s2, board[str2]))
+      count++;
+    pos = NEXT_STONE(pos);
+  }
+
+  return count;
+}
+
+
 /* chainlinks returns (in the (adj) array) the chains surrounding
  * the string at (str). The number of chains is returned.
  */
Index: engine/board.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.h,v
retrieving revision 1.12
diff -u -r1.12 board.h
--- engine/board.h      27 May 2004 00:08:46 -0000      1.12
+++ engine/board.h      29 May 2004 20:36:01 -0000
@@ -302,6 +302,7 @@
 /* Count the number of stones in a string. */
 int countstones(int str);
 int findstones(int str, int maxstones, int *stones);
+int count_adj_stones(int str1, int str2, int maxstones);
 
 /* Special function for reading.c */
 void incremental_order_moves(int move, int color, int string,
Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.143
diff -u -r1.143 reading.c
--- engine/reading.c    25 May 2004 03:13:45 -0000      1.143
+++ engine/reading.c    29 May 2004 20:36:01 -0000
@@ -1240,8 +1240,9 @@
 fast_defense(int str, int liberties, int *libs, int *move)
 {
   int color = board[str];
-  int k;
+  int j, k, l;
   int goal_liberties = (stackp < fourlib_depth ? 5 : 4);
+  int adj, adjs[MAXCHAIN];
 
   ASSERT1(libs != NULL, str);
   ASSERT1(move != NULL, str);
@@ -1255,6 +1256,69 @@
       return 1;
     }
   }
+
+  /* Check the cases where an opponent neighbor string is in
+   * atari.
+   */
+  adj = chainlinks2(str, adjs, 1);
+  for (j = 0; j < adj; j++) {
+    int lib;
+    int missing = goal_liberties - liberties;
+    int total = 0;
+    int adj2, adjs2[MAXCHAIN];
+    int alib, alibs[MAXLIBS];
+    int mw[BOARDMAX];
+
+    findlib(adjs[j], 1, &lib);
+    /* We aren't interested in ko (at this stage). And playing
+     * our own last liberty to capture is prone to snapbacks,
+     * so better let the 'normal' reading routines do the job.
+     */
+    if ((liberties == 1 && liberty_of_string(lib, str)
+        && countstones(adjs[j]) <= 2)
+       || is_ko(lib, color, NULL))
+      continue;
+
+    /* Would the capture already gain enough liberties ?
+     * No need to test the case if the move is one of our liberties,
+     * it has already been done in the first loop of this function.
+     */
+    if (!liberty_of_string(lib, str)
+       && count_adj_stones(adjs[j], str, missing) >= missing) {
+      *move = lib;
+      return 1;
+    }
+
+    /* Let's totalize liberties of the friendly strings around the 
+     * lunch.
+     */
+    memset(mw, 0, sizeof(mw));
+    adj2 = chainlinks(adjs[j], adjs2);
+    for (k = 0; k < adj2; k++) {
+      alib = findlib(adjs2[k], MAXLIBS, alibs);
+      for (l = 0; l < alib; l++) {
+       mw[alibs[l]]++;
+       if (mw[alibs[l]] == 1)
+         total++;
+      }
+    }
+
+    /* The captured string is treated as common liberties, and
+     * some adjustements are made :
+     * - we're adding a stone for capturing the lunch (-1)
+     * - opponent might be able to remove a liberty (-1)
+     * - and possibly force us to connect (-1)
+     */
+    total += countstones(adjs[j]) - 2;
+    if (mw[lib] < 2)
+      total--;
+
+    if (total >= goal_liberties) {
+      *move = lib;
+      return 1;
+    }
+  }
+
   return 0;
 }