[gnugo-devel] reading/chain breaking

[Martin Holters]

Hi!

Following patch solves reading:52 and 53, which I was aiming for, and
lazarus:13, which I haven't analysed. No other regression delta.
Changes in OWL and connection node counts are negligible, reading nodes
increase by only about 0.1%. Despite of that, I experienced a _decrease_
of total run-time by about 2%, which I can't quite explain but assume to
be caused by some external influence.

/Martin

Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.151
diff -u -r1.151 reading.c
--- engine/reading.c    19 Jul 2004 12:23:09 -0000      1.151
+++ engine/reading.c    11 Sep 2004 09:16:12 -0000
@@ -285,8 +285,10 @@
 static void propose_edge_moves(int str, int *libs, int liberties,
                               struct reading_moves *moves, int color);
 static void break_chain_moves(int str, struct reading_moves *moves);
-static void defend_secondary_chain_moves(int str, struct reading_moves *moves,
-                                        int min_liberties);
+static int  defend_secondary_chain1_moves(int str, struct reading_moves *moves,
+                                         int min_liberties);
+static void defend_secondary_chain2_moves(int str, struct reading_moves *moves,
+                                         int min_liberties);
 static void break_chain2_efficient_moves(int str, 
                                         struct reading_moves *moves);
 static void do_find_break_chain2_efficient_moves(int str, int adj,
@@ -3912,6 +3914,10 @@
  * ---------   ---------
  *
  * the code that follows can find the attacking move at *.
+ *
+ * Also for situations in which c has three liberties, one of which in common
+ * with b, the respective attacking move is found (see reading:52 for an 
+ * example).
  */
 
 static void
@@ -3921,15 +3927,17 @@
   int other = OTHER_COLOR(color);
   int adj, adjs[MAXCHAIN];
   int adj2, adjs2[MAXCHAIN];
-  int libs2[2];
+  int libs2[3];
   int apos;
   int bpos = 0;
   int cpos;
   int dpos;
   int epos;
+  int clibs;
   int dlibs;
   int elibs;
-  int k, s, t;
+  int bc_common_lib;
+  int k, s, t, u;
 
   ASSERT1(countlib(str) == 2, str);
 
@@ -3960,9 +3968,10 @@
       continue;
 
     /* Now require that (bpos) has a chain link, different from (str),
-     * also with two liberties.
+     * also with two liberties, or with three liberties, but one in common 
+     * with (bpos). 
      */
-    adj2 = chainlinks2(bpos, adjs2, 2);
+    adj2 = chainlinks3(bpos, adjs2, 3);
 
     for (s = 0; s < adj2; s++) {
       cpos = adjs2[s];
@@ -3970,30 +3979,47 @@
        continue;
       
       /* Pick up the liberties of (cpos). */
-      findlib(cpos, 2, libs2);
+      clibs = findlib(cpos, 3, libs2);
+
+      /* No need to do something fancy if it is in atari already. */
+      if (clibs < 2)
+       continue;
+
+      /* (cpos) has three liberties, none of which in commmon with (bpos)
+       * attacking it seems too difficult. */
+      bc_common_lib = have_common_lib(bpos, cpos, NULL);
+      if (clibs > 2 && !bc_common_lib)
+       continue;
 
       /* Try playing at a liberty. Before doing this, verify that
-       * (cpos) cannot get more than two liberties by answering on the
-       * other liberty and that we are not putting ourselves in atari.
-       * We also shouldn't allow ourselves to get fewer liberties than
-       * the defender.
+       * (cpos) cannot get more than three liberties by answering on 
+       * another liberty and that we are not putting ourselves in atari.
+       * We also should only allow ourselves to get fewer liberties than
+       * the defender in case (bpos) and (cpos) have a common liberty.
        */
-      for (t = 0; t < 2; t++) {
+      for (t = 0; t < clibs; t++) {
        dpos = libs2[t];
-       epos = libs2[1-t];
 
        if (is_self_atari(dpos, other))
          continue;
 
-       elibs = approxlib(epos, color, 4, NULL);
-       if (elibs > 3)
-         continue;
+       for (u = 0; u < clibs; u++) {
+         if (t == u)
+           continue;
 
-       dlibs = approxlib(dpos, other, 3, NULL);
-       if (elibs > dlibs)
-         continue;
+         epos = libs2[u];
+
+         elibs = approxlib(epos, color, 4, NULL);
+         if (elibs > 3)
+           break;
+
+         dlibs = approxlib(dpos, other, 3, NULL);
+         if (elibs > dlibs && !bc_common_lib)
+           break;
+       }
 
-       ADD_CANDIDATE_MOVE(dpos, 0, *moves, "special_attack4");
+       if (u >= clibs) /* No break occurred. */
+         ADD_CANDIDATE_MOVE(dpos, 0, *moves, "special_attack4");
       }
     }
   }
@@ -4347,34 +4373,113 @@
 }
 
 
-/* defend_secondary_chain_moves() tries to break a chain by defending
+/* defend_secondary_chain1_moves() tries to break a chain by defending
  * "secondary chain", that is, own strings surrounding a given
  * opponent string (which is in turn a chainlink for another own
- * string, phew... :).  Currently, it only defends own strings in
- * atari.
+ * string, phew... :).  It only defends own strings in atari.
+ *
+ * When defending is done by stretching, it is required that the defending
+ * stone played gets at least `min_liberties', or one less if it is 
+ * adjacent to the opponent chainlink.
  *
- * It is required that the defending stone played gets at least
- * `min_liberties', or one less if it is adjacent to the opponent
- * chainlink.
+ * Returns true if there where any secondary strings that needed defence 
+ * (which does not imply they actually where defended).
  */
-static void
-defend_secondary_chain_moves(int str, struct reading_moves *moves,
-                            int min_liberties)
+static int
+defend_secondary_chain1_moves(int str, struct reading_moves *moves,
+    int min_liberties)
 {
-  int r;
+  int r, s;
   int color = OTHER_COLOR(board[str]);
   int xpos;
   int adj;
+  int adj2;
   int adjs[MAXCHAIN];
+  int adjs2[MAXCHAIN];
 
   /* Find links in atari. */
   adj = chainlinks2(str, adjs, 1);
 
   for (r = 0; r < adj; r++) {
+    /* Stretch out. */
     findlib(adjs[r], 1, &xpos);
     if (approxlib(xpos, color, min_liberties, NULL)
        + neighbor_of_string(xpos, str) >= min_liberties)
-      ADD_CANDIDATE_MOVE(xpos, 0, *moves, "defend_secondary_chain");
+      ADD_CANDIDATE_MOVE(xpos, 0, *moves, "defend_secondary_chain1-A");
+
+    /* Capture adjacent stones in atari, if any. */
+    adj2 = chainlinks2(adjs[r], adjs2, 1);
+    for (s = 0; s < adj2; s++) {
+      findlib(adjs2[s], 1, &xpos);
+      if (!is_self_atari(xpos, color))
+       ADD_CANDIDATE_MOVE(xpos, 0, *moves, "defend_secondary_chain1-B");
+    }
+  }
+
+  return adj;
+}
+
+
+/* defend_secondary_chain2_moves() tries to break a chain by defending
+ * "secondary chain", that is, own strings surrounding a given
+ * opponent string (which is in turn a chainlink for another own
+ * string, phew... :).  It only defends own strings in
+ * with two liberties.
+ *
+ * When defending is done by stretching, it is required that the defending
+ * stone played gets at least `min_liberties', or one less if it is 
+ * adjacent to the opponent chainlink. Defence can also be done by capturing
+ * opponent stones or trying to capture them with an atari.
+ */
+static void
+defend_secondary_chain2_moves(int str, struct reading_moves *moves,
+    int min_liberties)
+{
+  int r, s, t;
+  int color = OTHER_COLOR(board[str]);
+  int xpos;
+  int adj;
+  int adj2;
+  int adjs[MAXCHAIN];
+  int adjs2[MAXCHAIN];
+  int libs[2];
+
+  /* Find links with two liberties. */
+  adj = chainlinks2(str, adjs, 2);
+
+  for (r = 0; r < adj; r++) {
+    if (!have_common_lib(str, adjs[r], NULL))
+      continue;
+
+    /* Stretch out. */
+    findlib(adjs[r], 2, libs);
+    for (t = 0; t < 2; t++) {
+      xpos = libs[t];
+      if (approxlib(xpos, color, min_liberties, NULL)
+         + neighbor_of_string(xpos, str) >= min_liberties)
+       ADD_CANDIDATE_MOVE(xpos, 0, *moves, "defend_secondary_chain2-A");
+    }
+
+    /* Capture adjacent stones in atari, if any. */
+    adj2 = chainlinks2(adjs[r], adjs2, 1);
+    for (s = 0; s < adj2; s++) {
+      findlib(adjs2[s], 1, &xpos);
+      if (!is_self_atari(xpos, color))
+       ADD_CANDIDATE_MOVE(xpos, 0, *moves, "defend_secondary_chain2-B");
+    }
+
+    /* Look for neighbours we can atari. */
+    adj2 = chainlinks2(adjs[r], adjs2, 2);
+    for (s = 0; s < adj2; s++) {
+      findlib(adjs2[s], 2, libs);
+      for (t = 0; t < 2; t++) {
+       /* Only atari if target has no easy escape with his other liberty. */
+       if (approxlib(libs[1-t], OTHER_COLOR(color), 3, NULL) < 3 
+           &&  !is_self_atari(libs[t], color)) {
+         ADD_CANDIDATE_MOVE(libs[t], 0, *moves, "defend_secondary_chain2-C");
+       }
+      }
+    }
   }
 }
 
@@ -4529,11 +4634,14 @@
     if (stackp <= break_chain_depth
        || (be_aggressive && stackp <= backfill_depth)) {
       /* If the chain link cannot escape easily, try to defend all adjacent
-       * friendly stones in atari (if any).
+       * friendly stones in atari (if any). If there are none, defend 
+       * adjacent friendly stones with only two liberties.
        */
       if (approxlib(libs[0], other, 4, NULL) < 4
-         && approxlib(libs[1], other, 4, NULL) < 4)
-       defend_secondary_chain_moves(adjs[r], moves, 2);
+         && approxlib(libs[1], other, 4, NULL) < 4) {
+       if (!defend_secondary_chain1_moves(adjs[r], moves, 2))
+         defend_secondary_chain2_moves(adjs[r], moves, 2);
+      }
     }
 
     if (unsafe[0] && unsafe[1]
@@ -4678,7 +4786,7 @@
 
     if (stackp <= backfill2_depth
        || (be_aggressive && stackp <= backfill_depth))
-      defend_secondary_chain_moves(adjs[r], moves, 3);
+      defend_secondary_chain1_moves(adjs[r], moves, 3);
   }
 
   for (v = 0; v < u; v++) {
@@ -4786,7 +4894,7 @@
 
     if (stackp <= backfill2_depth
        || (be_aggressive && stackp <= backfill_depth))
-      defend_secondary_chain_moves(adjs[r], moves, 4);
+      defend_secondary_chain1_moves(adjs[r], moves, 4);
   }
 
   for (v = 0; v < u; v++) {