[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] reading/chain breaking
From: |
Martin Holters |
Subject: |
[gnugo-devel] reading/chain breaking |
Date: |
Sat, 11 Sep 2004 11:41:51 +0200 |
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++) {
- [gnugo-devel] reading/chain breaking,
Martin Holters <=