Re: [gnugo-devel] illegal move! (fwd)

[Gunnar Farnebäck]

Arend wrote (on May 6):
> GNU Go wants to play an illegal move (suicide) at the end of this game.
> filllib.c ist the culprit (I haven't analyzed it further).

Further analysis traces the problem back to
atari_atari_blunder_size(), which comes up with an inappropriate
defense (reinforcement) move. This is the position:

   A B C D E F G H J K L M N O P Q R S T
19 . . X X X X . X . X O X O . X O . . . 19
18 . X O O O O X X X X O X X X X X O O . 18
17 X X X O . X X O O X O X X O X . X O . 17
16 O X O O O X O O X O O O X O X X O O . 16
15 O X X X X X O O . O . X O O X . . . . 15
14 O O X O O O O X . O . X . O X . O . . 14
13 O . O . O X O O O . O O . O O . . . . 13
12 . O . . O X X X X O . . . . . . O . . 12
11 . . O O O X . X X X O O X . O . O X . 11
10 O . O X X . X O O X X X O O . + . . . 10
 9 X O O X . X . X O O O X O X O O . O . 9
 8 X X X . X O X X X X O X X X X X O O O 8
 7 X O O O X O X O O O O O O X . . X O X 7
 6 . X O X O O X X O X O X X X . . X X X 6
 5 X . X X O X X . O X O O O O X . . . . 5
 4 . X . X O O O O O X O . . O X X . . . 4
 3 . . X . X X O X X X X O . O X . . . . 3
 2 . . . . X O . O X . O X X O X X X X X 2
 1 . . . . X O O . X . O . X O O O O O O 1
   A B C D E F G H J K L M N O P Q R S T

What happens is that when fill_liberty() considers the move white H5,
atari_atari_blunder_size() finds that it allows M3 to be captured, but
also that capturing at G9 (assuming H5 had already been played) would
solve the problem. Unfortunately G9 doesn't work before H5 since it's
illegal, but that is not checked.

Actually the atari_atari sequence after white H5 (black H1, white G2,
black N3) is illusory since white can capture at G9 and then black has
no way to make life even though M3 can be captured. That is somewhat
beside the point here but I've added this as test case atari_atari:27.
The original filllib problem has been added as filllib:46 with H5, N3,
and M1 as acceptable answers.

The patch below solves the illegal move problem by generating multiple
defense moves in atari_atari_blunder_size() and also testing that they
really are effective in the original position. It is not quite perfect
though since it comes up with G2, which is legal and safe but loses
one point compared to the correct answers.

The regression results beside the new tests consist of two PASSES for
nngs:1060 and strategy3:119. In both those test cases good moves were
previously devalued due to bogus blunder detection.

- atari_atari_blunder_size() revised to return multiple defense moves
  and also verifies them more carefully

By the way the atari_atari code is getting increasingly more messy. It
could really use a serious rewrite if someone is up to a challenge.

/Gunnar

Index: engine/combination.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/combination.c,v
retrieving revision 1.50
diff -u -r1.50 combination.c
--- engine/combination.c        12 Apr 2004 15:22:28 -0000      1.50
+++ engine/combination.c        3 Jun 2004 02:51:18 -0000
@@ -349,6 +349,9 @@
  * The arrays saved_dragons[] and saved_worms[] should be one for
  * stones belonging to dragons or worms respectively, which are
  * supposedly saved by (move).
+ *
+ * FIXME: We probably want to change the calling convention of this
+ *        function to return all defense moves.
  */
 int
 atari_atari_confirm_safety(int color, int move, int *defense, int minsize,
@@ -356,26 +359,42 @@
                           const char saved_worms[BOARDMAX])
 {
   char safe_stones[BOARDMAX];
+  char defense_moves[BOARDMAX];
+  int pos;
+  int blunder_size;
 
   mark_safe_stones(color, move, saved_dragons, saved_worms, safe_stones);
+  blunder_size = atari_atari_blunder_size(color, move, defense_moves,
+                                         safe_stones);
 
-  return (atari_atari_blunder_size(color, move, defense, safe_stones)
-         >= minsize);
+  if (defense) {
+    /* Return one arbitrary defense move. */
+    *defense = NO_MOVE;
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+      if (ON_BOARD(pos) && defense_moves[pos]) {
+       *defense = pos;
+       break;
+      }
+  }
+  
+  return blunder_size >= minsize;
 }
- 
+
 
 /* This function checks whether any new combination attack appears after
  * move at (move) has been made, and returns its size (in points).
  * safe_stones marks which of our stones are supposedly safe after this move.
  */
 int
-atari_atari_blunder_size(int color, int move, int *defense,
+atari_atari_blunder_size(int color, int move, char defense_moves[BOARDMAX],
                         const char safe_stones[BOARDMAX])
 {
   int apos;
   int defense_point = NO_MOVE, after_defense_point = NO_MOVE;
   int aa_val, after_aa_val;
   int other = OTHER_COLOR(color);
+  char defense_points[BOARDMAX];
+  int last_forbidden = NO_MOVE;
 
   /* If aa_depth is too small, we can't see any combination attacks,
    * so in this respect the move is safe enough.
@@ -384,6 +403,7 @@
     return 0;
 
   memset(forbidden, 0, sizeof(forbidden));
+  memset(defense_points, 0, sizeof(defense_points));
 
   /* FIXME: Maybe these should be moved after the tryko() below? */
   compute_aa_status(other, safe_stones);
@@ -395,7 +415,7 @@
     abortgo(__FILE__, __LINE__, "trymove", move);
   increase_depth_values();
 
-  aa_val = do_atari_atari(other, &apos, &defense_point, NULL,
+  aa_val = do_atari_atari(other, &apos, &defense_point, defense_points,
                          NO_MOVE, 0, 0, NULL);
   after_aa_val = aa_val;
 
@@ -421,6 +441,7 @@
      */
     after_defense_point = defense_point;
     forbidden[apos] = 1;
+    last_forbidden = apos;
     aa_val = do_atari_atari(other, &apos, &defense_point, NULL,
                            NO_MOVE, 0, aa_val, NULL);
   }
@@ -433,14 +454,58 @@
    */
   compute_aa_status(other, NULL);
   compute_aa_values(other);
+  forbidden[last_forbidden] = 0;
   aa_val = do_atari_atari(other, NULL, NULL, NULL, NO_MOVE, 0, 0, NULL);
-  if (after_aa_val - aa_val > 0) {
-    if (defense)
-      *defense = after_defense_point;
-    return after_aa_val - aa_val;
-  }
-  else
+  if (aa_val >= after_aa_val)
     return 0;
+
+  /* Try the potential defense moves to see which are effective. */
+  if (defense_moves) {
+    int pos;
+    /* defense_points[] contains potential defense moves. Now we
+     * examine which of them really work.
+     */
+    
+    /* FIXME: Maybe these should be moved after the tryko() below? */
+    compute_aa_status(other, safe_stones);
+    compute_aa_values(other);
+      
+    memcpy(defense_moves, defense_points, sizeof(defense_points));
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (!ON_BOARD(pos) || !defense_moves[pos])
+       continue;
+
+      if (!trymove(pos, color, "atari_atari", NO_MOVE)) {
+       defense_moves[pos] = 0;
+       continue;
+      }
+      increase_depth_values();
+
+      if (attack(pos, NULL)) {
+       defense_moves[pos] = 0;
+       decrease_depth_values();
+       popgo();
+       continue;
+      }
+      
+      /* Accept illegal ko capture here. */
+      if (!tryko(move, color, NULL))
+       /* Really shouldn't happen. */
+       abortgo(__FILE__, __LINE__, "trymove", move);
+      increase_depth_values();
+      
+      if (do_atari_atari(other, &apos, &defense_point, NULL, NO_MOVE,
+                        0, after_aa_val, NULL) >= after_aa_val)
+       defense_moves[pos] = 0;
+
+      decrease_depth_values();
+      popgo();
+      decrease_depth_values();
+      popgo();
+    }
+  }
+  
+  return after_aa_val - aa_val;
 }
 
 
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.219
diff -u -r1.219 liberty.h
--- engine/liberty.h    2 Jun 2004 02:53:25 -0000       1.219
+++ engine/liberty.h    3 Jun 2004 02:51:18 -0000
@@ -466,7 +466,7 @@
                               const char saved_dragons[BOARDMAX],
                               const char saved_worms[BOARDMAX]);
 
-int atari_atari_blunder_size(int color, int tpos, int *move,
+int atari_atari_blunder_size(int color, int tpos, char defense_moves[BOARDMAX],
                             const char safe_stones[BOARDMAX]);
 
 int review_move_reasons(int *move, float *val, int color,
Index: engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.95
diff -u -r1.95 utils.c
--- engine/utils.c      2 Jun 2004 02:53:27 -0000       1.95
+++ engine/utils.c      3 Jun 2004 02:51:20 -0000
@@ -933,11 +933,11 @@
 {
   int libs[5];
   int liberties = accuratelib(move, color, 5, libs);
-  int apos;
   int trouble = 0;
   int save_verbose = verbose;
   float return_value = 0.0;
   int atari;
+  char defense_moves[BOARDMAX];
   
   if (defense_point)
     *defense_point = NO_MOVE;
@@ -973,13 +973,20 @@
    * set up some combination attack that didn't exist before. We do
    * this last to avoid duplicate blunder reports.
    */
-  atari = atari_atari_blunder_size(color, move, &apos, safe_stones);
+  atari = atari_atari_blunder_size(color, move, defense_moves, safe_stones);
   if (atari) {
-    ASSERT_ON_BOARD1(apos);
-    if (defense_point)
-      *defense_point = apos;
+    if (defense_point) {
+      /* FIXME: Choose defense point more systematically. */
+      int pos;
+      *defense_point = NO_MOVE;
+      for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+       if (ON_BOARD(pos) && defense_moves[pos]) {
+         *defense_point = pos;
+         break;
+       }
+    }
     verbose = save_verbose;
-    TRACE("Combination attack appears at %1m.\n", apos);
+    TRACE("Combination attack appears.\n");
     return_value += (float) atari;
   }
 
Index: regression/atari_atari.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/atari_atari.tst,v
retrieving revision 1.44
diff -u -r1.44 atari_atari.tst
--- regression/atari_atari.tst  10 Mar 2004 15:54:47 -0000      1.44
+++ regression/atari_atari.tst  3 Jun 2004 02:51:20 -0000
@@ -114,3 +114,8 @@
 loadsgf games/self_play/354-34-2.sgf 150
 26 combination_defend white
 #? [E11|E12]*
+
+loadsgf games/filllib14.sgf
+play white H5
+27 combination_attack black
+#? [0]
Index: regression/filllib.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/filllib.tst,v
retrieving revision 1.29
diff -u -r1.29 filllib.tst
--- regression/filllib.tst      16 Apr 2004 07:16:45 -0000      1.29
+++ regression/filllib.tst      3 Jun 2004 02:51:20 -0000
@@ -154,3 +154,6 @@
 45 reg_genmove black
 #? [G9]*
 
+loadsgf games/filllib14.sgf
+46 reg_genmove white
+#? [N3|H5|M1]
Index: regression/games/filllib14.sgf
===================================================================
RCS file: regression/games/filllib14.sgf
diff -N regression/games/filllib14.sgf
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ regression/games/filllib14.sgf      3 Jun 2004 02:51:20 -0000
@@ -0,0 +1,17 @@
+(;GM[1]FF[4]CA[UTF-8]
+HA[2]SZ[19]RU[AGA]KM[0.50]TM[600]OT[20/120 Canadian]
+PW[yagr]PB[colaTurca]WR[8k]BR[10k]DT[2004-05-06]PC[The Kiseido Go Server (KGS) 
at http://kgs.kiseido.com/]AB[pd][dp]C[yagr [8k\]: GTP Engine for yagr (white): 
GNU Go version 3.5.4
+]RE[W+Resign]
+;W[dc];B[pp];W[nc];B[ce];W[ed];B[cc];W[nq];B[oq];W[np];B[op];W[no];B[jq];W[cn];B[dn];W[dm];B[co];W[en];B[do];W[cm];B[em];W[fn];B[el]
+;W[cj];B[ej];W[kc];B[ch];W[qf];B[qc];W[qi];B[oe];W[fp];B[fq];W[gq];B[eq];W[gp];B[gm];W[ip];B[jp];W[io];B[jo];W[in];B[jn];W[im];B[gn]
+;W[jm];B[go];W[cb];B[bc];W[ql];B[qn];W[ge];B[jj];W[fm];B[gl];W[ep];B[cq];W[km];B[iq];W[hr];B[ir];W[lo];B[lr];W[nr];B[or];W[fr];B[er]
+;W[gs];B[hq];W[hp];B[es];W[bo];B[bp];W[me];B[bn];W[fl];B[fk];W[bm];B[ao];W[di];B[dk];W[ck];B[dj];W[ci];B[ln];W[kn];B[mn];W[mo];B[ml]
+;W[ko];B[nn];W[kp];B[kq];W[lq];B[mr];W[ns];B[ms];W[ks];B[is];W[kr];B[oo];W[bh];B[am];W[cd];B[bd];W[dd];B[bl];W[cg];B[dh];W[eh];B[dg]
+;W[df];B[cl];W[bf];B[be];W[ae];B[bb];W[db];B[hh];W[jf];B[hf];W[he];B[fh];W[eg];B[fg];W[os];B[pr];W[ps];B[qr];W[rm];B[rn];W[qs];B[rr]
+;W[rd];B[pl];W[rc];B[ob];W[qb];B[pb];W[rb];B[nb];W[nf];B[of];W[og];B[mc];W[nd];B[md];W[ne];B[lb];W[kb];B[ee];W[ff];B[de];W[ef];B[fe]
+;W[gf];B[fd];W[fb];B[fc];W[eb];B[gb];W[gd];B[gc];W[ga];B[ha];W[pk];B[ol];W[li];B[rl];W[rk];B[sm];W[sl];B[qm];W[rl];B[sn];W[jh];B[gj]
+;W[mj];B[lk];W[gg];B[gh];W[hg];B[ih];W[mk];B[ib];W[ic];B[jb];W[ka];B[jc];W[jd];B[id];W[je];B[le];W[ld];B[lf];W[lg];B[lc];W[kd];B[la]
+;W[ok];B[nk];W[nj];B[nl];W[hc];B[hb];W[hd];B[fa];W[bk];B[ak];W[aj];B[al];W[rs];B[sr];W[ig];B[ji];W[ki];B[kj];W[fs];B[lj];W[ad];B[ac]
+;W[kg];B[af];W[ag];B[cf];W[ae];B[ja];W[ei];B[fi];W[ik];B[hk];W[ij];B[ii];W[lm];B[ll];W[mm];B[nm];W[hj];B[hl];W[jk];B[il];W[kk];B[jl]
+;W[kl];B[hi];W[af];B[ri];W[qh];B[mi];W[pa];B[oa];W[ma];B[mb];W[oi];B[oc];W[qd];B[od];W[ng];B[ca];W[eo];B[fo];W[ss];B[da];W[ad];B[ea]
+;W[hm];B[hn])