Re: [gnugo-devel] reading patch

[Gunnar Farneback]

I wrote:
> I may make some experiments with this. In any case it now wants to
> play E11 instead of A18 at move 130 and all later repetitions of the
> mistake. Locally A16 is better than E11 but compared to A18 it's a
> huge improvement.

The appended patch makes A16 the highest valued local move. Now we
get, at move 130,

1. A16 17.80
2. M5  16.30
3. E11 15.86
(  A18 -1.00)

- new function break_chain4_moves()
- owl moves for non-critical dragons discarded
- do_owl_analyze_semeai() revised
- detect_owl_blunder() also looks for semeai defenses
- estimate_strategical_value() revised

Break_chain4_moves() is only called from defend2() and only when
be_aggressive (see Paul's patch) is set. It can certainly be used in
more contexts but for now I've only enabled this use.

The change in do_owl_analyze_semeai() was needed to solve semeai:54.
The rest of the changes are various tweaks to get proper valuation of
A16 above and to avoid having it discarded as a blunder.

Regression delta:
reading:182     pass (FAIL before patch)
reading:184     pass (FAIL before patch)
connection:94   PASS 1 D9 [1 D9]
strategy:36     PASS R6 [!D18]
nicklas3:401    FAIL F9 [A5]
semeai:54       pass (FAIL before patch)
nngs2:600       FAIL D6 [B5]
nngs4:210       PASS B19 [!S5]

The failures:

nicklas3:401
This is a tidy position with a principally important mistake which
should be looked into. The failure is not really the fault of this
patch though. Before the patch it considered F9 a blunder (correct)
because F8 became owl attackable (wrong). After the patch it
understands that F8 is perfectly safe also after F9 and no longer
discards it as a blunder. The real problem with F9 is that B9 is
brought alive, but this was not understood neither before nor after
the patch.

nngs2:600
Possibly a real failure of the patch. The position is quite complex
and something goes wrong, although I'm not sure what. I'll look
further into it.

The patch gives a very minor slowdown. Should be well worth the
improvements.

Before patch:
Total nodes: 1521433025 2282073 8820795
Total time: 7508.94 (8663.79)

After patch:
Total nodes: 1525806058 2285638 8823933
Total time: 7606.68 (8626.89)

/Gunnar

Index: engine/move_reasons.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/move_reasons.c,v
retrieving revision 1.114
diff -u -r1.114 move_reasons.c
--- engine/move_reasons.c       9 Jun 2003 16:05:32 -0000       1.114
+++ engine/move_reasons.c       20 Jun 2003 08:21:33 -0000
@@ -595,6 +595,14 @@
   return !move[pos].move_safety;
 }
 
+/* Check whether a dragon is non-critical. */
+static int
+concerns_noncritical_dragon(int pos, int what)
+{
+  UNUSED(pos);
+  return dragon[what].status != CRITICAL; 
+}
+
 
 /* (what) points to two worms listed in either_data. Returns true if
  * this is a "attack either" move reason, and one of the worms attackable.
@@ -1882,6 +1890,10 @@
       DEFEND_MOVE, DEFEND_MOVE_GOOD_KO, DEFEND_MOVE_BAD_KO, -1},
     move_is_marked_unsafe, REDUNDANT,
     "  %1m: 0.0 - tactical move vs %1m (unsafe move)\n"},
+  { { OWL_ATTACK_MOVE, OWL_ATTACK_MOVE_GOOD_KO, OWL_ATTACK_MOVE_BAD_KO,
+      OWL_DEFEND_MOVE, OWL_DEFEND_MOVE_GOOD_KO, OWL_DEFEND_MOVE_BAD_KO, -1},
+    concerns_noncritical_dragon, REDUNDANT,
+    "  %1m: 0.0 - owl move vs %1m (non-critical)\n"},
   { { -1 }, NULL, 0, ""}  /* Keep this entry at end of the list. */
 };
 
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.170
diff -u -r1.170 owl.c
--- engine/owl.c        10 Jun 2003 04:52:45 -0000      1.170
+++ engine/owl.c        20 Jun 2003 08:21:36 -0000
@@ -524,9 +524,10 @@
 
     for (sworm = 0; sworm <= s_worms; sworm++) {
       critical_semeai_worms[sworm] = 0;
-      if (board[semeai_worms[sworm]] == other
-         && attack(semeai_worms[sworm], &upos) == WIN) {
-       if (semeai_trust_tactical_attack(semeai_worms[sworm])
+      if (board[semeai_worms[sworm]] == other) {
+       int acode = attack(semeai_worms[sworm], &upos);
+       if (acode == WIN
+           && semeai_trust_tactical_attack(semeai_worms[sworm])
            && important_semeai_worms[sworm]) {
          *resulta = WIN;
          *resultb = WIN;
@@ -536,7 +537,8 @@
          SGFTRACE_SEMEAI(upos, WIN, WIN, "tactical win found");
          READ_RETURN_SEMEAI(read_result, move, upos, WIN, WIN);
        }
-       else if (find_defense(semeai_worms[sworm], NULL)) {
+       else if (acode != 0
+                && find_defense(semeai_worms[sworm], NULL)) {
          critical_semeai_worms[sworm] = 1;
          owl_add_move(moves, upos, 95, "attack semeai worm", 1, 0, NO_MOVE,
                       MAX_SEMEAI_MOVES);
Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.115
diff -u -r1.115 reading.c
--- engine/reading.c    19 Jun 2003 18:57:45 -0000      1.115
+++ engine/reading.c    20 Jun 2003 08:21:39 -0000
@@ -194,6 +194,8 @@
                                       int be_aggressive);
 static void break_chain3_moves(int str, struct reading_moves *moves,
                               int be_aggressive);
+static void break_chain4_moves(int str, struct reading_moves *moves,
+                              int be_aggressive);
 static void superstring_moves(int str, struct reading_moves *moves, 
                              int liberty_cap, int does_attack);
 static void superstring_break_chain_moves(int str, int liberty_cap,
@@ -1450,6 +1452,9 @@
       || (be_aggressive && stackp <= backfill_depth))
     break_chain3_moves(str, &moves, be_aggressive);
 
+  if (be_aggressive && stackp <= backfill_depth)
+    break_chain4_moves(str, &moves, be_aggressive);
+
   /* Only order and test the new set of moves. */
   order_moves(str, &moves, other, read_function_name, saved_num_moves, 
NO_MOVE);
     
@@ -4670,6 +4675,113 @@
   }
 }
 
+/*
+ * (str) points to a group.
+ * If there is a string in the surrounding chain having
+ * exactly four liberties whose attack leads to the rescue of
+ * (str), break_chain4_moves(str, *moves) adds attack moves against
+ * the surrounding string as candidate moves.
+ */
+
+static void
+break_chain4_moves(int str, struct reading_moves *moves, int be_aggressive)
+{
+  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[4];
+  int possible_moves[MAX_MOVES];
+  int mw[BOARDMAX];
+
+  memset(mw, 0, sizeof(mw));
+  
+  adj = chainlinks2(str, adjs, 4);
+  for (r = 0; r < adj; r++) {
+    int lib1 = 0, lib2 = 0, lib3 = 0, lib4 = 0;
+    apos = adjs[r];
+
+    /* We make a list in the (adjs) array of the liberties
+     * of boundary strings having exactly four liberties. We mark
+     * each liberty in the mw array so that we do not list any
+     * more than once.
+     */
+    findlib(apos, 4, libs);
+
+    /* If the 4 liberty chain easily can run away through one of the
+     * liberties, we don't play on any of the other liberties.
+     */
+    lib1 = approxlib(libs[0], other, 5, NULL);
+    lib2 = approxlib(libs[1], other, 5, NULL);
+    if (lib1 >= 5 && lib2 >= 5)
+      continue;
+    lib3 = approxlib(libs[2], other, 5, NULL);
+
+    if ((lib1 >= 5 || lib2 >= 5) && lib3 >= 5)
+      continue;
+    lib4 = approxlib(libs[3], other, 5, NULL);
+
+    if ((lib1 >= 5 || lib2 >= 5 || lib3 >= 5) && lib4 >= 5)
+      continue;
+
+    if (lib1 >= 5 && !mw[libs[0]]) {
+      mw[libs[0]] = 1;
+      possible_moves[u++] = libs[0];
+      continue;
+    }
+    
+    if (lib2 >= 5 && !mw[libs[1]]) {
+      mw[libs[1]] = 1;
+      possible_moves[u++] = libs[1];
+      continue;
+    }
+    
+    if (lib3 >= 5 && !mw[libs[2]]) {
+      mw[libs[2]] = 1;
+      possible_moves[u++] = libs[2];
+      continue;
+    }
+
+    if (lib4 >= 5 && !mw[libs[3]]) {
+      mw[libs[3]] = 1;
+      possible_moves[u++] = libs[3];
+      continue;
+    }
+
+    /* No easy escape, try all liberties. */
+    for (k = 0; k < 4; k++) {
+      if (!mw[libs[k]]) {
+       mw[libs[k]] = 1;
+       possible_moves[u++] = libs[k];
+      }
+    }
+
+    if (stackp <= backfill2_depth
+       || (be_aggressive && stackp <= backfill_depth))
+      defend_secondary_chain_moves(adjs[r], moves, 4);
+  }
+
+  for (v = 0; v < u; v++) {
+    /* We do not wish to consider the move if it can be 
+     * immediately recaptured, unless stackp < backfill2_depth.
+     * Beyond backfill2_depth, the necessary capturing move might not
+     * get generated in follow-up for the attacker.
+     * (This currently only makes a difference at stackp == backfill2_depth.)
+     */
+    int xpos = possible_moves[v];
+    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_chain4");
+  }
+}
 
 /* This function looks for moves attacking those components
  * of the surrounding chain of the superstring (see find_superstring
Index: engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.73
diff -u -r1.73 utils.c
--- engine/utils.c      19 Jun 2003 18:57:45 -0000      1.73
+++ engine/utils.c      20 Jun 2003 08:21:40 -0000
@@ -1006,6 +1006,22 @@
        && DRAGON2(bpos).safety != STRONGLY_ALIVE) {
       int kworm = NO_MOVE;
       int acode = owl_confirm_safety(move, bpos, defense_point, &kworm);
+
+      /* If owl couldn't confirm safety, maybe semeai can. */
+      if (acode != WIN) {
+       int r;
+       for (r = 0; r < DRAGON2(bpos).neighbors; r++) {
+         int neighbor = dragon2[DRAGON2(bpos).adjacent[r]].origin;
+         int resultb;
+         if (board[neighbor] == color)
+           continue;
+         owl_analyze_semeai_after_move(move, color, neighbor, bpos,
+                                       NULL, &resultb, NULL, 1, NULL);
+         if (resultb == 0)
+           acode = WIN;
+       }
+      }
+      
       if (acode == 0) {
        verbose = save_verbose;
        TRACE("Dragon at %1m becomes attackable.\n", bpos);
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.102
diff -u -r1.102 value_moves.c
--- engine/value_moves.c        18 Jun 2003 11:01:24 -0000      1.102
+++ engine/value_moves.c        20 Jun 2003 08:21:43 -0000
@@ -2466,8 +2466,9 @@
      */
     if (attack_move_reason_known(pos, aa)
        || defense_move_reason_known(pos, aa)
-       || owl_attack_move_reason_known(pos, aa)
-       || owl_defense_move_reason_known(pos, aa)
+       || ((owl_attack_move_reason_known(pos, aa)
+            || owl_defense_move_reason_known(pos, aa))
+           && dragon[aa].status == CRITICAL)
        || move_reason_known(pos, SEMEAI_MOVE, aa)) {
       /* But if the strategical value was larger than the territorial
        * value (e.g. because connecting to strong dragon) we award the