[gnugo-devel] reading patch

[Paul Pogonyshev]

this patch (hopefully) improves reading. it concerns
superstring_breakchain() function. the change is that it now also
tries to capture those chains which have two liberties. it slows the
engine down somewhat, but i think the gain is worth that.

after lots of testing i've discovered that the following restrictions
on which chains try to eat are (probably) the best:

  - own stone played won't be in atari.
  - if opponent tries to escape with the second liberty, he won't have
    more than two liberties (allows to read ladder-like attacks).

i used approxlib(), but it might be useful to try is_self_atari() for
checking the first condition.

regression delta is 9 PASSes and 3 FAILs, but i suspect that two of
the FAILs are due to bad test answers. here the delta is, with
comments:

reading:37      PASS   properly solved.
reading:140     PASS   properly solved.
reading:170     PASS   properly solved (the aimed test).
owl:237         PASS   properly solved (same position as in reading:
                       170).
connection:78   PASS   properly solved (same position as in
                       trevorb:300).
lazarus:15      PASS   looks quite accidential (move valuations
                       changed a bit).
13x13:65        PASS   rather properly solved than not. H4 is now
                       valued twice as high as it was.
nngs2:70        PASS   L18 is now valued about 12 instead of 38. looks
                       like a solved one.
nngs3:470       PASS   looks accidential.

nngs1:2         FAIL   this one is quite misterious. see comments
                       below.
lazarus:10      FAIL   i'm pretty certain it's not a fail. it's rather
                       a pass. white T6 saves the entire dragon and
                       black T8 looks like the only move which might
                       help (and it played T8). the test might need
                       revision.
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. is F1 really a fail?

about nngs1:2. before the patch it had the following move reasons for
K19:

  Move at K19 attacks L19 with good ko
  Move at K19 attacks N19
  Move at K19 attacks M18
  Move at K19 connects P17 and L18
  Move at K19 connects L18 and P19
  Move at K19 connects L18 and N16

with the patch the list changed to:

  Move at K19 attacks L19 with good ko
  Move at K19 attacks N19 with good ko
  Move at K19 attacks M18 with good ko

for me, the second version looks more correct. however, it causes
great underestimation of K19 move. actually, i think it is bad that
gnugo never considers K18. maybe a pattern will help?

i also had these results during experiments:

connection:6    PASS   i don't know if it is a real pass, since i
                       don't understand why the worms are amalgamated
                       in that test and why they shouldn't be.
global:31       PASS   passed for a wrong reason.

nngs2:150       FAIL   looked accidential, but i wasn't sure.

if the second restriction is changed to

  - if opponent tries to escape with the second liberty, he won't have
    more than ONE liberty (atari can't be escaped from),

there remain these results:

reading:37      PASS
reading:170     PASS
owl:237         PASS
nngs2:70        PASS

for the issues i mentioned about FAILs, i'm not sure if it is good
there's not a single one ;)

engine seems to be slowed down by about 2% on such tests as reading
and owl_rot, but on nngs2 difference is very small. taking into
consideration possible inaccuracy, i think it might be around 0.5%.

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      2 Oct 2002 19:34:41 -0000
@@ -4700,40 +4700,60 @@
   int adj;
   int adjs[MAXCHAIN];
   int k;
-  int apos;
+  int liberties;
+  int libs[2];
+  struct reading_moves moves;
   int savemove = 0;
   int savecode = 0;
 
   SETUP_TRACE_INFO("superstring_breakchain", str);
 
   proper_superstring_chainlinks(str, &adj, adjs, liberty_cap);
+
+  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 if (liberties == 2) {
+      findlib(adjs[k], 2, libs);
+
+      if (approxlib(libs[0], color, 2, NULL) > 1
+          && approxlib(libs[1], OTHER_COLOR(color), 4, NULL) < 4)
+       ADD_CANDIDATE_MOVE(libs[0], 0, moves);
+      
+      if (approxlib(libs[1], color, 2, NULL) > 1
+          && approxlib(libs[0], OTHER_COLOR(color), 4, NULL) < 4)
+       ADD_CANDIDATE_MOVE(libs[1], 0, moves);
+    }
+  }
+
+  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();