[gnugo-devel] break_chain3_moves() revision

[Paul Pogonyshev]

This patch solves a problem i discovered while a observing a GNU Go
vs. GNU Go game.  It also adds it as a test in `reading.tst'.

Unfortunately, it also causes a fail in 13x13:39.  I used new
DUMP_ALL_RESULTS debugging method to trace it down and here is what i
got: 

     A B C D E F G H J K L M N
  13 . . . . . . . . . . . . . 13
  12 . . . . X . . . O . . . . 12
  11 . . X X . X O O . X . . . 11
  10 . . . X X O + . . + X . . 10
   9 . . . O O . O . . . . . . 9
   8 . . . . . . . . . . . . . 8
   7 . . . + . . + . . + X . . 7
   6 . . . X . X X X . . . X . 6
   5 . . . . . X O O O . O O X 5     WHITE (O) has captured 0 stones
   4 . . X + O O X X . O . . O 4     BLACK (X) has captured 1 stones
   3 . X . O . . . X X O . . . 3
   2 . . O . . . . X O O . . . 2
   1 . . . . . . . . . . . . . 1
     A B C D E F G H J K L M N

in the position above (after white J5, black H4) GNU Go doesn't see an
attack on G4 string.  This is because after white G2 it now plays
black F2 (a reasonable move) and then fails to kill due to fourlib
depth cutoff.

I consider this a tolerable fail.

The downside in node increase is absolutely negligible:

before:  1349505274 2426761 9050963
after:   1349589958 2427052 9050125

Speaking of DUMP_ALL_RESULTS, i improved it a bit (now depth is
outputted in addition to stack dump) and put the patch in CVS.  The
reasoning behind the change is that we can get different results at
different depth cutoffs (this does happen) and `join' can't handle
them properly.  The new debug method proved to be useful for tracing
down subtle changes in tactical reading.  It is quite slow however
(since dumps are megabytes in size for typical tests).

Paul



Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.129
diff -u -p -r1.129 reading.c
--- engine/reading.c    23 Nov 2003 23:10:55 -0000      1.129
+++ engine/reading.c    23 Nov 2003 23:24:23 -0000
@@ -4434,12 +4434,10 @@ break_chain3_moves(int str, struct readi
   int color = board[str];
   int other = OTHER_COLOR(color);
   int r;
-  int k;
   int u = 0, v;
   int apos;
   int adj;
   int adjs[MAXCHAIN];
-  int libs[3];
   int possible_moves[MAX_MOVES];
   int mw[BOARDMAX];
 
@@ -4447,7 +4445,11 @@ break_chain3_moves(int str, struct readi
   
   adj = chainlinks2(str, adjs, 3);
   for (r = 0; r < adj; r++) {
-    int lib1 = 0, lib2 = 0, lib3 = 0;
+    int k;
+    int libs[3];
+    int liberties[3];
+    int escape = NO_MOVE;
+
     apos = adjs[r];
 
     /* We make a list in the (adjs) array of the liberties
@@ -4459,31 +4461,46 @@ break_chain3_moves(int str, struct readi
 
     /* If the 3 liberty chain easily can run away through one of the
      * liberties, we don't play on any of the other liberties.
+     * However, as an exception, if a liberty to escape is on the
+     * edge, both its adjacent edge vertices are empty and one of them
+     * is adjacent to the defender's string, we allow an escapement
+     * through this liberty to get one more liberty.  See reading:193
+     * for an example where this is useful.
      */
-    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);
+    for (k = 0; k < 3; k++) {
+      liberties[k] = approxlib(libs[k], other, 5, NULL);
+      if (liberties[k] == 4) {
+       int i;
 
-    if ((lib1 >= 4 || lib2 >= 4) && lib3 >= 4)
-      continue;
+       for (i = 0; i < 4; i++) {
+         if (!ON_BOARD(libs[k] + delta[i])) {
+           int left = libs[k] + delta[(i + 1) % 4];
+           int right = libs[k] + delta[(i + 3) % 4];
 
-    if (lib1 >= 4 && !mw[libs[0]]) {
-      mw[libs[0]] = 1;
-      possible_moves[u++] = libs[0];
-      continue;
+           if (board[left] == EMPTY
+               && board[right] == EMPTY
+               && (neighbor_of_string(left, str)
+                   || neighbor_of_string(right, str)))
+             liberties[k] = 3;
+
+           break;
+         }
+       }
+      }
+
+      if (liberties[k] >= 4) {
+       if (escape)
+         break;
+       escape = libs[k];
+      }
     }
-    
-    if (lib2 >= 4 && !mw[libs[1]]) {
-      mw[libs[1]] = 1;
-      possible_moves[u++] = libs[1];
+
+    if (k < 3)
       continue;
-    }
-    
-    if (lib3 >= 4 && !mw[libs[2]]) {
-      mw[libs[2]] = 1;
-      possible_moves[u++] = libs[2];
+
+    if (escape) {
+      mw[escape] = 1;
+      possible_moves[u++] = escape;
       continue;
     }
 
Index: regression/reading.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/reading.tst,v
retrieving revision 1.61
diff -u -p -r1.61 reading.tst
--- regression/reading.tst      17 Nov 2003 09:46:18 -0000      1.61
+++ regression/reading.tst      23 Nov 2003 23:24:24 -0000
@@ -801,6 +801,11 @@ loadsgf games/reading43.sgf
 192 attack D4
 #? [0]
 
+# break_chain3_moves() problem.
+loadsgf games/selfplay2.sgf 199
+193 attack A4
+#? [0]
+
 # Report number of nodes visited by the tactical reading
 10000 get_reading_node_counter
 #? [0]&
Index: regression/games/selfplay2.sgf
===================================================================
RCS file: regression/games/selfplay2.sgf
diff -N regression/games/selfplay2.sgf
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ regression/games/selfplay2.sgf      23 Nov 2003 23:24:52 -0000
@@ -0,0 +1,44 @@
+(;GM[1]FF[3]
+RU[Japanese]SZ[19]HA[0]KM[5.5]
+PW[White]
+PB[Black]
+GN[White (W) vs. Black (B)]
+DT[2003-11-22]
+SY[Cgoban 1.9.14]TM[-]
+RE[W+11.5]
+;B[pd];W[cp];B[qp];W[dl];B[pl];W[qj];B[eq];W[iq];B[do];W[co];B[cd];
+W[ep];B[fq];W[dp];B[eo];W[mp];B[ec];W[qf];B[nc];W[rd];B[qc];W[dn];
+B[en];W[em];B[gn];W[ch];B[fp];W[in];B[fm];W[oq];B[jd];W[gc];B[rc];
+W[ge];B[pn];W[qh];B[ql];W[jb];B[pr];W[or];B[cr];W[df];B[fk];W[di];
+B[re];W[rf];B[qd];W[pq];B[qr];W[qq];B[rq];W[mn];B[pp];W[be];B[bd];
+W[fb];B[cb];W[rk];B[el];W[dm];B[dk];W[bl];B[cj];W[rm];B[ee];W[bj];
+B[bi];W[ck];B[ef];W[dj];B[bf];W[bh];B[de];W[cf];B[ce];W[bg];B[ae];
+W[gr];B[fr];W[gs];B[rl];W[sl];B[gq];W[ng];B[hr];W[ir];B[hs];W[db];
+B[is];W[eb];B[jr];W[jq];B[kr];W[il];B[kq];W[kp];B[ml];W[op];B[nm];
+W[oo];B[qm];W[lq];B[rn];W[lr];B[js];W[ni];B[ij];W[sm];B[bq];W[ek];
+B[sf];W[sg];B[se];W[rh];B[an];W[bn];B[sn];W[ao];B[sk];W[sj];B[da];
+W[sl];B[sm];W[dc];B[ic];W[ib];B[lb];W[cc];B[bb];W[ed];B[bc];W[lm];
+B[eg];W[lg];B[kc];W[md];B[nd];W[jc];B[me];W[id];B[je];W[ie];B[hq];
+W[hp];B[ho];W[ip];B[io];W[jo];B[gp];W[jp];B[hn];W[hm];B[of];W[ok];
+B[fi];W[fj];B[gj];W[ej];B[fl];W[hh];B[gh];W[ps];B[rs];W[kb];B[ld];
+W[la];B[ma];W[ka];B[mb];W[fe];B[jk];W[og];B[jh];W[hg];B[li];W[nf];
+B[mj];W[oe];B[ol];W[nk];B[ll];W[bp];B[aq];W[kl];B[kk];W[jl];B[dd];
+W[fc];B[nj];W[oj];B[mi];W[mh];B[ap];W[am];B[dh];W[cg];B[dg];W[cq];
+B[bs];W[ii];B[br];W[ji];B[jf];W[gl];B[hi];W[kh];B[kg];W[ih];B[jg];
+W[lh];B[lf];W[kj];B[mk];W[qe];B[sd];W[ea];B[ki];W[jj];B[ik];W[hk];
+B[hj];W[hl];B[gg];W[if];B[ig];W[hf];B[pk];W[pj];B[pe];W[pf];B[ca];
+W[od];B[oc];W[ne];B[mf];W[nn];B[mg];W[nh];B[ei];W[po];B[qo];W[dq];
+B[dr];W[on];B[ff];W[om];B[nl];W[pm];B[gm];W[jn];B[ls];W[ms];B[ks];
+W[lj];B[ag];W[ah];B[af];W[gk];B[fo];W[sk];B[lk];W[qn];B[hb];W[hc];
+B[pn];W[kd];B[ke];W[qn];B[ci];W[ai];B[pn];W[sc];B[sb];W[qn];B[cn];
+W[bo];B[pn];W[ad];B[ac];W[qn];B[bm];W[cm];B[pn];W[rr];B[sr];W[qn];
+B[mr];W[ns];B[pn];W[lc];B[mc];W[qn];B[lp];W[mq];B[pn];W[os];B[qs];
+W[qn];B[fd];W[gd];B[pn];W[gf];B[qn];W[mm];B[qk];W[tt];B[tt];
+TW[fa][ga][ha][ia][ja][gb][hb][ec][ic][fd][hd][he][of][pg][qg][rg][oh][ph][sh][bi][ci][oi][pi][qi][ri][si][aj][cj][rj][ak][bk][dk][al][cl][bm][im][jm][km][an][cn][kn][ln][ko][lo][mo][no][lp][np][nq][mr][nr]
+TB[aa][ba][na][oa][pa][qa][ra][sa][ab][nb][ob][pb][qb][rb][lc][pc][sc][ad][kd][md][rd][be][le][kf][fg][eh][fh][gi][rm][fn][go][ro][so][rp][sp][sq][ar][er][gr][rr][as][cs][ds][es][fs][gs][ss]
+C[The game is over.  Final score:
+   White = 51 territory + 22 captures + 5.5 komi = 78.5
+   Black = 47 territory + 20 captures = 67
+White wins by 11.5.
+]
+)