Re: [gnugo-devel] fast_defense() improvement

[Arend Bayer]

> So this is what the attached patch does. I have also rewritten the

And here it actually is.

Arend


Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.98
diff -u -p -r1.98 board.c
--- engine/board.c      27 May 2004 00:08:46 -0000      1.98
+++ engine/board.c      1 Jun 2004 22:14:20 -0000
@@ -2383,6 +2383,41 @@ findstones(int str, int maxstones, int *
 }
 
 
+/* 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_adjacent_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 -p -r1.12 board.h
--- engine/board.h      27 May 2004 00:08:46 -0000      1.12
+++ engine/board.h      1 Jun 2004 22:14:21 -0000
@@ -302,6 +302,7 @@ int have_common_lib(int str1, int str2, 
 /* Count the number of stones in a string. */
 int countstones(int str);
 int findstones(int str, int maxstones, int *stones);
+int count_adjacent_stones(int str1, int str2, int maxstones);
 
 /* Special function for reading.c */
 void incremental_order_moves(int move, int color, int string,
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.214
diff -u -p -r1.214 owl.c
--- engine/owl.c        31 May 2004 13:53:25 -0000      1.214
+++ engine/owl.c        1 Jun 2004 22:14:28 -0000
@@ -576,6 +576,9 @@ do_owl_analyze_semeai(int apos, int bpos
   ASSERT1(board[apos] == owla->color, apos);
   ASSERT1(board[bpos] == owlb->color, bpos);
 
+  apos = find_origin(apos);
+  bpos = find_origin(bpos);
+
   if (stackp <= semeai_branch_depth && (hashflags & HASH_SEMEAI)
       && !pass && owl_phase
       && tt_get(&ttable, SEMEAI, apos, bpos, depth - stackp, NULL,
Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.143
diff -u -p -r1.143 reading.c
--- engine/reading.c    25 May 2004 03:13:45 -0000      1.143
+++ engine/reading.c    1 Jun 2004 22:14:34 -0000
@@ -1240,8 +1240,11 @@ static int
 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];
+  static unsigned liberty_mark = -1;
+  static unsigned lm[BOARDMAX];
 
   ASSERT1(libs != NULL, str);
   ASSERT1(move != NULL, str);
@@ -1255,6 +1258,82 @@ fast_defense(int str, int liberties, int
       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 num_adjacent_stones;
+
+    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 && lib == libs[0]
+        && 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.
+     */
+    num_adjacent_stones = count_adjacent_stones(adjs[j], str, missing);
+    ASSERT1(num_adjacent_stones >= 1, str);
+    if (!liberty_of_string(lib, str)
+       && num_adjacent_stones >= missing) {
+      *move = lib;
+      return 1;
+    }
+
+    /* What is the total number of liberties of the friendly strings around
+     * the lunch?
+     */
+    if (++liberty_mark == 0)
+      memset(lm, 0, sizeof(lm));
+    /* Loop over all neighbors of the lunch. */
+    adj2 = chainlinks(adjs[j], adjs2);
+    for (k = 0; k < adj2; k++) {
+      /* Loop over all liberties of the neighbor. */
+      alib = findlib(adjs2[k], MAXLIBS, alibs);
+      for (l = 0; l < alib; l++) {
+       if (lm[alibs[l]] != liberty_mark) {
+         lm[alibs[l]] = liberty_mark;
+         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)
+     * - reduce us by one more liberty with a throw-in; this
+     *   is only possible if there is only one adjacent stone in the
+     *   lunch to the string (-1)
+     * Probably there are more damezumari-type cases, but as a heuristic,
+     * it seems good enough.
+     */
+    total += countstones(adjs[j]) - 2;
+    if (lm[lib] == liberty_mark)
+      total--;
+    if (num_adjacent_stones == 1)
+      total--;
+
+    if (total >= goal_liberties) {
+      *move = lib;
+      return 1;
+    }
+  }
+
   return 0;
 }