Re: [gnugo-devel] Patch for break_chain3_moves

[SP lee]

> SP Lee wrote:
> > The following tweak makes gnugo generate more aggressive chain breaking
> > moves. The regression breakage (I might overlook some cases because
> > there are recently lots of regression changes on the cvs):
>
> On top of 3.5.4 I get the following regression results:
>
> reading:64      FAIL 1 R3 [3 N1]
> reading:194     PASS 0 [0]
> strategy:13     PASS N18 [N18]
> arb:203         FAIL N3 [T7]
> lazarus:5       PASS R13 [R13]
> lazarus:13      PASS R13 [R13|M8|L9]
> nngs:370        PASS O5 [!Q1]
> nngs:371        PASS 0 [0]
> trevorc:1490    FAIL N9 [J10]
> strategy3:119   PASS D9 [D9|J3]
> 13x13:39        FAIL J5 [H4|J4]
> strategy4:190   FAIL E14 [D13]
> owl1:263        PASS 1 R11 [1 R11]
> nngs2:150       FAIL E9 [M3|L3]
> nngs3:710       FAIL C2 [Q2]
> nngs3:1170      FAIL B7 [B1]
> nngs4:470       FAIL N10 [R8]
> 9x9:210         PASS F8 [F8|E9]
> 9 PASS
> 9 FAIL
> Total nodes: 1496586662 2754388 10864949 (+1% +0.43% -0.073%)
>
> /Gunnar
>

I have modified the patch to generate a little less reading nodes and also changed the BACKFILL2_DEPTH from 5 to 9, which allows break_chain2_moves to be called from attack3 in a rather deep level. Now I got reading:64, trevorc:1490, nngs3:710,1170 passed. When I increased the ko_depth from 8 to 12 I got nngs4:470 passed. Since 13x13:39 is not really a fail, there are totally 9 passes and 3 fails. I'll run a full regression test later.

 

I'm not sure whether the increased node count is now a real problem. Maybe we could add another level above 10 for experiments.

 

 

SP Lee

 

$ cvs diff -u reading.c
Index: reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.137
diff -u -r1.137 reading.c
--- reading.c   24 Jan 2004 23:21:13 -0000      1.137
+++ reading.c   26 Jan 2004 06:58:49 -0000
@@ -240,6 +240,12 @@
   int num_tried;
 };

 

+struct chain_liberties
+{
+  int pos;
+  int expected_lib;
+};
+
 /*
  * The functions in reading.c are used to read whether groups
  * can be captured or not. See the Texinfo documentation
@@ -4539,12 +4545,13 @@
   int libs[3];
   int possible_moves[MAX_MOVES];
   int mw[BOARDMAX];
+  struct chain_liberties chain_lib[3];
+  int sorted,temp;

 

   memset(mw, 0, sizeof(mw));

 

   adj = chainlinks2(str, adjs, 3);
   for (r = 0; r < adj; r++) {
-    int lib1 = 0, lib2 = 0, lib3 = 0;
     apos = adjs[r];

 

     /* We make a list in the (adjs) array of the liberties
@@ -4556,32 +4563,63 @@

 

     /* If the 3 liberty chain easily can run away through one of the
      * liberties, we don't play on any of the other liberties.
+     * Usually it's not easy to escape from the 3 liberties, but
+     * there are cases like (O to break chain of X's):
+     *  ..XXXX
+     *  .a...X
+     *  bXOOOX  If X plays on a, the leftmost chain's no. liberties is
+     *  .cX.XX       changed to 5, b to 4 and c to 6.
+     *  ......
+     *  If X plays on any of the liberties to change the total
+     *  liberties to 4, it's still not easy to escape since it's O's
+     *  turn to move and the liberties can be reduced back.
      */
-    lib1 = approxlib(libs[0], other, 4, NULL);
-    lib2 = approxlib(libs[1], other, 4, NULL);
-    if (lib1 >= 4 && lib2 >= 4)
-      continue;
-    lib3 = approxlib(libs[2], other, 4, NULL);
+    chain_lib[0].pos = libs[0];
+    chain_lib[0].expected_lib = approxlib(libs[0], other, 5, NULL);
+    chain_lib[1].pos = libs[1];
+    chain_lib[1].expected_lib = approxlib(libs[1], other, 5, NULL);
+    chain_lib[2].pos = libs[2];
+    chain_lib[2].expected_lib = approxlib(libs[2], other, 5, NULL);
+
+    /* sort the 3 liberties with their expected libertied after a move
+     * at pos
+     */
+    do {
+      sorted = 1;
+      if (chain_lib[0].expected_lib < chain_lib[1].expected_lib) {
+       temp = chain_lib[0].pos;
+       chain_lib[0].pos = chain_lib[1].pos;
+       chain_lib[1].pos = temp;
+       temp = chain_lib[0].expected_lib;
+       chain_lib[0].expected_lib = chain_lib[1].expected_lib;
+       chain_lib[1].expected_lib = temp;
+      }
+      if (chain_lib[1].expected_lib < chain_lib[2].expected_lib) {
+       temp = chain_lib[1].pos;
+       chain_lib[1].pos = chain_lib[2].pos;
+       chain_lib[2].pos = temp;
+       temp = chain_lib[1].expected_lib;
+       chain_lib[1].expected_lib = chain_lib[2].expected_lib;
+       chain_lib[2].expected_lib = temp;
+       sorted = 0;
+      }
+    } while (!sorted);

 

-    if ((lib1 >= 4 || lib2 >= 4) && lib3 >= 4)
-      continue;

 

-    if (lib1 >= 4 && !mw[libs[0]]) {
-      mw[libs[0]] = 1;
-      possible_moves[u++] = libs[0];
+    if (chain_lib[1].expected_lib >= 5)
       continue;
-    }
-
-    if (lib2 >= 4 && !mw[libs[1]]) {
-      mw[libs[1]] = 1;
-      possible_moves[u++] = libs[1];
+
+    if (chain_lib[2].expected_lib > chain_lib[1].expected_lib) {
+      mw[chain_lib[2].pos] = 1;
+      possible_moves[u++] = chain_lib[2].pos;
       continue;
     }
-
-    if (lib3 >= 4 && !mw[libs[2]]) {
-      mw[libs[2]] = 1;
-      possible_moves[u++] = libs[2];
-      continue;
+    else {
+      /* In this case chain_lib[2].expected_lib == chain_lib[1].expected_lib
+       */
+      if (chain_lib[0].expected_lib < chain_lib[1].expected_lib)
+        /* We'll only try the 2 liberties with equal expected_lib */
+        mw[chain_lib[0].pos] = 1;
     }

 

     /* No easy escape, try all liberties. */
@@ -4605,13 +4643,21 @@
      * (This currently only makes a difference at stackp == backfill2_depth.)
      */
     int xpos = possible_moves[v];
+    int lib_stone = approxlib(xpos, color, 3, libs);
     if (stackp <= break_chain_depth
        || (be_aggressive && stackp <= backfill_depth)
-       || approxlib(xpos, color, 2, NULL) > 1)
-      /* We use a negative initial score here as we prefer to find
-       * direct defense moves.
-       */
-      ADD_CANDIDATE_MOVE(xpos, -2, *moves, "break_chain3");
+       || lib_stone > 1) {
+       /* When the stone for chain breaking has 2 liberties, it is only safe
+        * when it's opponent would reduce own liberty to 1 while trying to
+        * catch this 2 liberty stone.
+        */
+        if ((lib_stone != 2) || approxlib(libs[0], other, 3, NULL) == 2 ||
+          approxlib(libs[1], other, 3, NULL) == 2)
+         /* We use a negative initial score here as we prefer to find
+          * direct defense moves.
+          */
+          ADD_CANDIDATE_MOVE(xpos, -2, *moves, "break_chain3");
+      }
   }
 }

$ cvs diff -u utils.c
Index: utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.87
diff -u -r1.87 utils.c
--- utils.c     24 Jan 2004 04:04:56 -0000      1.87
+++ utils.c     26 Jan 2004 07:08:19 -0000
@@ -609,11 +609,11 @@
 #define DEPTH                16
 #define BRANCH_DEPTH         13
 #define BACKFILL_DEPTH       12
-#define BACKFILL2_DEPTH       5
+#define BACKFILL2_DEPTH       9
 #define BREAK_CHAIN_DEPTH     7
 #define SUPERSTRING_DEPTH     7
 #define FOURLIB_DEPTH         7
-#define KO_DEPTH              8
+#define KO_DEPTH              12

 

 #if 0
 #undef FOURLIB_DEPTH