Re[2]: [gnugo-devel] reading patch

[Paul Pogonyshev]

this patch improves and replaces pogonyshev_3_10.2.

i've revised the code in break_chain2_efficient_moves() which handles
the "common special case". it is simplified and bugfixed now. i
rewrote it to be 1D and made it check if _any_ stone of X string is
on the second line, while the current implementation checks whether
the _origin_ of the X string is there, which is clearly incorrect.

this change doesn't cause any regression changes, but it helps to save
some reading nodes (see below). looks like when current implementation
of break_chain2_efficient_moves() fails to detect the "special case",
it is found later by some other function, but some reading nodes are
wasted by then. it may be a good idea to look for repetetive work in
reading module. it is possible that several functions constantly find
the same (or partially overlapping) sets of moves.

another change is that superstring_breakchain() now uses
is_self_atari() instead of approxlib(). this, however, didn't improved
regression results neither.

the main change is that superstring_breakchain() now contains two
variants of attacking chainlinks with two liberties. the first is
exactly the same as in original patch, while the second was proposed
by Gunnar and uses almost the same logic as
break_chain2_efficient_moves(). when adding the patch you may either
keep both (they are #if'ed) or delete one of the two.

regression delta of the first variant remained the same (9 passes, 3
fails). the delta of the second varinat is 5 passes, no fails. here is
the regression difference between variants (all results are by the
first variant):

connection:78   PASS   properly solved.
lazarus:15      PASS   accidential.
13x13:65        PASS   rather properly solved than not. H4 is now
                       valued twice as high as it was.
nngs3:470       PASS   accidential.

nngs1:2         FAIL   move reasons for K19 improved and caused a
                       fail. to me, K18 looks much better, but gnugo
                       can't find it (neither now, nor patched).
lazarus:10      FAIL   it currently discards T8 for a wrong reason. it
                       thinks that white P16 saves the dragon after
                       T8. when patched, it no longer likes P16, but 
                       can't find the real reason of T8 failure (it
                       is quite deep).
trevorb:300     FAIL   previously it passed for a wrong reason (F2 was
                       valued about 7 points). now it values F1 about
                       29 and F2 about 27.

so, i'd say that the first version is better (+2 proper passes, and +3
fails, where reading improved, but owl failed). but, of course, 3
fails are there and it is not good. maybe nngs1:2 and trevorb:300
can be fixed with some pattern.

now about reading nodes.

  test file      not patched    bugfixed    variant 1       variant 2

  reading              100%       97.91%       98.48%          98.37%
  owl                  100%       98.90%      100.62%          99.96%
  owl1                 100%       98.28%       99.67%          99.88%
  nicklas4             100%       97.85%       98.67%          98.64%

so, bugfix in break_chain2_efficient_moves() saves about 1.5% reading
nodes. after that, variant 1 costs about 1.0% - 1.2% and variant 2
costs about 0.6% - 0.8% reading nodes.

all results are on top of 3.3.9 + gunnar_3_10.1 + gunnar_3_10.2.

Paul


Index: gnugo/engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.78
diff -u -r1.78 reading.c
--- gnugo/engine/reading.c      28 Sep 2002 14:15:26 -0000      1.78
+++ gnugo/engine/reading.c      8 Oct 2002 10:55:39 -0000
@@ -4398,9 +4398,8 @@
   int adj, adjs[MAXCHAIN];
   int adj2, adjs2[MAXCHAIN];
   int libs[2];
-  int ai, aj;
-  int bi, bj;
-  int ci, cj;
+  int dlib;
+  int pos1, pos2;
   
   /* Find links with 2 liberties. */
   adj = chainlinks2(str, adjs, 2);
@@ -4445,26 +4444,26 @@
      * Update: This was too crude. Also require that the X stone is on
      * the second line and that the proposed move is not a self-atari.
      */
-    ai = I(libs[0]);
-    aj = J(libs[0]);
-    bi = I(libs[1]);
-    bj = J(libs[1]);
-    ci = I(adjs[r]);
-    cj = J(adjs[r]);
-    if (gg_abs(ai - bi) == 1
-       && gg_abs(aj - bj) == 1
-       && (ci == 1 || ci == board_size - 2
-           || cj == 1 || cj == board_size - 2)) {
-
-      if ((ai == 0 || ai == board_size - 1
-          || aj == 0 || aj == board_size - 1)
-         && !is_self_atari(libs[1], board[str]))
-       ADD_CANDIDATE_MOVE(libs[1], 0, *moves);
-
-      if ((bi == 0 || bi == board_size - 1
-          || bj == 0 || bj == board_size - 1)
-         && !is_self_atari(libs[0], board[str]))
-       ADD_CANDIDATE_MOVE(libs[0], 0, *moves);
+    dlib = libs[0] - libs[1];
+    if (dlib == SW(0) || dlib == NW(0)
+        || dlib == NE(0) || dlib == SE(0)) {
+      pos1 = gg_max(libs[0], libs[1]) - NS;
+      pos2 = gg_min(libs[0], libs[1]) + NS;
+      if ((is_edge_vertex(pos1)
+          || (board[pos1] == other && same_string(pos1, adjs[r])))
+         && (is_edge_vertex(pos2)
+         || (board[pos2] == other && same_string(pos2, adjs[r])))) {
+        
+       /* Note that libs[1] is on the edge iff libs[1]-dlib is off
+         * board (since liberties are placed diagonally). Similar is
+         * about libs[0].
+         */
+        if (!ON_BOARD(libs[1]-dlib) && !is_self_atari(libs[0], color))
+         ADD_CANDIDATE_MOVE(libs[0], 0, *moves);
+
+        if (!ON_BOARD(libs[0]+dlib) && !is_self_atari(libs[1], color))
+         ADD_CANDIDATE_MOVE(libs[1], 0, *moves);
+      }
     }
   }
 }
@@ -4697,43 +4696,107 @@
                       int liberty_cap)
 {
   int color = board[str];
+  int other = OTHER_COLOR(color);
   int adj;
   int adjs[MAXCHAIN];
   int k;
-  int apos;
+  int liberties;
+  int libs[2];
+#if 0
+  int dlib;
+  int pos1, pos2;
+#endif
+  struct reading_moves moves;
   int savemove = 0;
   int savecode = 0;
 
   SETUP_TRACE_INFO("superstring_breakchain", str);
 
-  proper_superstring_chainlinks(str, &adj, adjs, liberty_cap);
+  proper_superstring_chainlinks(str, &adj, adjs,
+    gg_min(liberty_cap, 2));
+
+  moves.num = 0;
   for (k = 0; k < adj; k++) {
+    liberties = countlib(adjs[k]);
+    
+    if (liberties == 1) {
+      findlib(adjs[k], 1, libs);
+      ADD_CANDIDATE_MOVE(libs[0], 0, moves);
+    }
+    else { /* two liberties */
+      findlib(adjs[k], 2, libs);
+
+#if 1
+      /* We only try to play a liberty of chainlink if it is not a self-
+       * atari move and opponent won't get more than two liberties when
+       * trying to escape. It producec useless moves sometimes, but not
+       * very often.
+       */
+      if (approxlib(libs[1], other, 4, NULL) < 4
+          && !is_self_atari(libs[0], color))
+       ADD_CANDIDATE_MOVE(libs[0], 0, moves);
+      
+      if (approxlib(libs[0], other, 4, NULL) < 4
+          && !is_self_atari(libs[1], color))
+       ADD_CANDIDATE_MOVE(libs[1], 0, moves);
+#else
+      /* We only try to play a liberty of chainlink if our stone doesn't
+       * get into self-atari and the chainlink cannot escape atari after
+       * such move. See break_chain2_efficient_moves() for explanation
+       * of the code below.
+       */
+      if (approxlib(libs[1], other, 3, NULL) < 3
+          && !is_self_atari(libs[0], color))
+       ADD_CANDIDATE_MOVE(libs[0], 0, moves);
+      
+      if (approxlib(libs[0], other, 3, NULL) < 3
+          && !is_self_atari(libs[1], color))
+       ADD_CANDIDATE_MOVE(libs[1], 0, moves);
+
+      dlib = libs[0] - libs[1];
+      if (dlib == SW(0) || dlib == NW(0)
+          || dlib == NE(0) || dlib == SE(0)) {
+        pos1 = gg_max(libs[0], libs[1]) - NS;
+        pos2 = gg_min(libs[0], libs[1]) + NS;
+        if (((board[pos1] == other && same_string(pos1, adjs[k]))
+            || is_edge_vertex(pos1))
+           && (board[pos2] == other && same_string(pos2, adjs[k]))
+           || (is_edge_vertex(pos2))) {
+        
+          if (!ON_BOARD(libs[1]-dlib) && !is_self_atari(libs[0], color))
+           ADD_CANDIDATE_MOVE(libs[0], 0, moves);
+
+          if (!ON_BOARD(libs[0]+dlib) && !is_self_atari(libs[1], color))
+           ADD_CANDIDATE_MOVE(libs[1], 0, moves);
+        }
+      }
+#endif
+    }
+  }
+
+  for (k = 0; k < moves.num ; k++) {
     int new_komaster, new_kom_pos;
     int ko_move;
 
-    if (countlib(adjs[k]) > 1)
-      continue;
-    findlib(adjs[k], 1, &apos);
-
-    if (komaster_trymove(apos, color, "superstring_break_chain", str,
+    if (komaster_trymove(moves.pos[k], color, "superstring_break_chain", str,
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, savecode == 0 && stackp <= ko_depth)) {
       if (!ko_move) {
        int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
        if (acode == 0) {
          popgo();
-         *move = apos;
-         SGFTRACE(apos, WIN, "attack defended");
+         *move = moves.pos[k];
+         SGFTRACE(moves.pos[k], WIN, "attack defended");
          return WIN;
        }
        else if (acode != WIN) {
-         UPDATE_SAVED_KO_RESULT(savecode, savemove, acode, apos);
+         UPDATE_SAVED_KO_RESULT(savecode, savemove, acode, moves.pos[k]);
        }
        popgo();
       }
       else {
        if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
-         savemove = apos;
+         savemove = moves.pos[k];
          savecode = KO_B;
        }
        popgo();