[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] liberty counting, revised
|
From: |
Paul Pogonyshev |
|
Subject: |
[gnugo-devel] liberty counting, revised |
|
Date: |
Tue, 15 Oct 2002 22:21:00 +0300 |
i checked the speed. rewritten function is 4-8 times faster (depending
on position) than the old one, which seems to be good enough ;)
i also ran the complete regression suit with an assertion set,
checking that new function always gives correct result. after one
bugfix it started doing so ;)
changes:
- exactlib() is renamed to accuratelib() as Marco Scheurer proposed.
gtp command is renamed to accuratelib as well.
- accuratelib() is bugfixed and now seems to always tell the truth.
- incremental_sloppy_self_atari() is finally integrated into
is_self_atari().
code maintenance changes:
- new 'neighbor' variable in extended_chainlinks() replaced
(libs[r] + delta[k]) expression which was repeated 4 times there.
- use variables for pos + delta[k] instead of for delta[k] alone in
slow_approxlib().
regression delta is zero.
Paul
Index: gnugo/engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.58
diff -u -r1.58 utils.c
--- gnugo/engine/utils.c 9 Oct 2002 18:36:23 -0000 1.58
+++ gnugo/engine/utils.c 15 Oct 2002 19:10:37 -0000
@@ -762,52 +762,6 @@
ko_depth = save_ko_depth;
}
-/* Play a stone at (pos) and count the number of liberties for the
- * resulting string. This requires (pos) to be empty.
- *
- * This function differs from approxlib() by the fact that it removes
- * captured stones before counting the liberties.
- */
-
-int
-accurate_approxlib(int pos, int color, int maxlib, int *libs)
-{
- int fast_liberties = -1;
- int liberties = 0;
- SGFTree *save_sgf_dumptree = sgf_dumptree;
- int save_count_variations = count_variations;
-
- ASSERT1(board[pos] == EMPTY, pos);
- ASSERT1(IS_STONE(color), pos);
-
- if (!libs) {
- fast_liberties = fastlib(pos, color, 0);
- if (fast_liberties >= 0) {
- return fast_liberties;
- }
- }
-
- sgf_dumptree = 0;
- /* Use tryko() since we don't care whether the move would violate
- * the ko rule.
- */
- if (tryko(pos, color, "accurate approxlib", EMPTY, 0)) {
- if (libs != NULL)
- liberties = findlib(pos, maxlib, libs);
- else
- liberties = countlib(pos);
- popgo();
- }
-
- if (fast_liberties >= 0 && liberties > 0) {
- ASSERT1(fast_liberties == liberties, pos);
- }
-
- sgf_dumptree = save_sgf_dumptree;
- count_variations = save_count_variations;
-
- return liberties;
-}
/*******************
* Detect blunders *
@@ -855,7 +809,7 @@
char safe_stones[BOARDMAX])
{
int libs[5];
- int liberties = accurate_approxlib(move, color, 5, libs);
+ int liberties = accuratelib(move, color, 5, libs);
int apos;
int trouble = 0;
int save_verbose = verbose;
Index: gnugo/engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.36
diff -u -r1.36 readconnect.c
--- gnugo/engine/readconnect.c 10 Sep 2002 20:06:01 -0000 1.36
+++ gnugo/engine/readconnect.c 15 Oct 2002 19:10:46 -0000
@@ -2946,7 +2946,7 @@
if (findlib(str, 1, &lib) > 1)
return 0;
- if (accurate_approxlib(lib, board[str], 2, NULL) > 1)
+ if (accuratelib(lib, board[str], 2, NULL) > 1)
return 0;
/* FIXME: Should exclude snapback. */
Index: gnugo/engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.111
diff -u -r1.111 owl.c
--- gnugo/engine/owl.c 9 Oct 2002 23:23:21 -0000 1.111
+++ gnugo/engine/owl.c 15 Oct 2002 19:11:10 -0000
@@ -4285,8 +4285,8 @@
else
pos2 = libs[0];
- if (accurate_approxlib(pos2, color, MAXLIBS, NULL)
- > accurate_approxlib(defense_point, color, MAXLIBS, NULL)
+ if (accuratelib(pos2, color, MAXLIBS, NULL)
+ > accuratelib(defense_point, color, MAXLIBS, NULL)
&& does_defend(pos2, lunch)) {
TRACE("Moved defense of lunch %1m from %1m to %1m.\n",
lunch, defense_point, pos2);
Index: gnugo/engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.124
diff -u -r1.124 liberty.h
--- gnugo/engine/liberty.h 9 Oct 2002 18:36:23 -0000 1.124
+++ gnugo/engine/liberty.h 15 Oct 2002 19:11:18 -0000
@@ -159,6 +159,7 @@
int findlib(int str, int maxlib, int *libs);
int fastlib(int pos, int color, int ignore_capture);
int approxlib(int pos, int color, int maxlib, int *libs);
+int accuratelib(int pos, int color, int maxlib, int *libs);
int count_common_libs(int str1, int str2);
int find_common_libs(int str1, int str2, int maxlib, int *libs);
int have_common_lib(int str1, int str2, int *lib);
@@ -169,9 +170,6 @@
void update_random_seed(void);
-
-/* Play at (pos) and then count the liberties. */
-int accurate_approxlib(int pos, int color, int maxlib, int *libs);
/* Check for self atari. */
int is_self_atari(int pos, int color);
Index: gnugo/engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.52
diff -u -r1.52 board.c
--- gnugo/engine/board.c 5 Oct 2002 09:15:44 -0000 1.52
+++ gnugo/engine/board.c 15 Oct 2002 19:11:39 -0000
@@ -202,6 +202,17 @@
(board[pos] == string[s].color\
&& string[string_number[pos]].mark != string_mark)
+/* Note that these two macros are not complementary. Both return
+ * false if board[pos] != color.
+ */
+#define UNMARKED_COLOR_STRING(pos, color)\
+ (board[pos] == color\
+ && string[string_number[pos]].mark != string_mark)
+
+#define MARKED_COLOR_STRING(pos, color)\
+ (board[pos] == color\
+ && string[string_number[pos]].mark == string_mark)
+
#define MARK_STRING(pos) string[string_number[pos]].mark = string_mark
#define STRING_AT_VERTEX(pos, s)\
@@ -275,7 +286,6 @@
static int do_remove_string(int s);
static void do_play_move(int pos, int color);
static int slow_approxlib(int pos, int color, int maxlib, int *libs);
-static int incremental_sloppy_self_atari(int pos, int color);
/* Statistics. */
@@ -1996,16 +2006,17 @@
/* Count the liberties a stone of the given color would get if played
* at (pos). Captures are ignored based on the ignore_capture flag.
- * (pos) must be empty. It will fail if there is more than one
+ * (pos) must be empty. It will fail if there is more than two
* string neighbor of the same color. In this case, the return value
- * is -1. Captures are not handled, so if ignore_capture is 0, and
- * a capture is required, -1 is returned.
+ * is -1. Captures are handled in a very limited way, so if
+ * ignore_capture is 0, and a capture is required, it will often
+ * return -1.
*
* The intent of this function is to be as fast as possible, not
- * necessarily complete.
+ * necessarily complete. But if it returns a positive value (meaning
+ * it has succeeded), the value is guaranteed to be correct.
*
- * Note well, that it relies on incremental data (?), and the number
- * of liberties (if over MAX_LIBERTIES) may be inaccurate (?).
+ * Note well, that it relies on incremental data.
*/
int
@@ -2042,6 +2053,7 @@
ally1 = neighbor;
}
}
+
for (k = 0; k < 4; k++) {
int neighbor = pos + delta[k];
int neighbor_color = board[neighbor];
@@ -2049,11 +2061,16 @@
&& neighbor_color == other
&& LIBERTIES(neighbor) == 1) {
int neighbor_size = COUNTSTONES(neighbor);
+#if 0
if ((neighbor_size <= 2 && !ally1)
- || (neighbor_size == 1
+ || (neighbor_size == 1
&& ally1
&& !ally2
&& COUNTSTONES(ally1) == 1)) {
+#else
+ if (neighbor_size == 1
+ || (neighbor_size == 2 && !ally1)) {
+#endif
/* Here, we can gain only the adjacent new liberty. */
fast_liberties++;
}
@@ -2072,6 +2089,7 @@
fast_liberties += LIBERTIES(ally1) - 1;
if (ally2)
fast_liberties += LIBERTIES(ally2) - count_common_libs(ally1, ally2);
+
return fast_liberties;
}
@@ -2092,16 +2110,14 @@
{
int k;
int liberties = 0;
- int fast_liberties = 0;
ASSERT1(board[pos] == EMPTY, pos);
ASSERT1(IS_STONE(color), pos);
if (!libs) {
- fast_liberties = fastlib(pos, color, 1);
- if (fast_liberties >= 0) {
+ int fast_liberties = fastlib(pos, color, 1);
+ if (fast_liberties >= 0)
return fast_liberties;
- }
}
if (!strings_initialized)
@@ -2123,7 +2139,7 @@
MARK_LIBERTY(pos);
if (UNMARKED_LIBERTY(SOUTH(pos))) {
- if (libs != NULL && liberties < maxlib)
+ if (libs != NULL)
libs[liberties] = SOUTH(pos);
liberties++;
/* Stop counting if we reach maxlib. */
@@ -2132,11 +2148,11 @@
MARK_LIBERTY(SOUTH(pos));
}
else if (board[SOUTH(pos)] == color) {
- int s = string_number[SOUTH(pos)];
- for (k = 0; k < string[s].liberties; k++) {
- int lib = string[s].libs[k];
+ struct string_data *s = &string[string_number[SOUTH(pos)]];
+ for (k = 0; k < s->liberties; k++) {
+ int lib = s->libs[k];
if (UNMARKED_LIBERTY(lib)) {
- if (libs != NULL && liberties < maxlib)
+ if (libs != NULL)
libs[liberties] = lib;
liberties++;
if (liberties >= maxlib)
@@ -2147,7 +2163,7 @@
}
if (UNMARKED_LIBERTY(WEST(pos))) {
- if (libs != NULL && liberties < maxlib)
+ if (libs != NULL)
libs[liberties] = WEST(pos);
liberties++;
/* Stop counting if we reach maxlib. */
@@ -2156,11 +2172,11 @@
MARK_LIBERTY(WEST(pos));
}
else if (board[WEST(pos)] == color) {
- int s = string_number[WEST(pos)];
- for (k = 0; k < string[s].liberties; k++) {
- int lib = string[s].libs[k];
+ struct string_data *s = &string[string_number[WEST(pos)]];
+ for (k = 0; k < s->liberties; k++) {
+ int lib = s->libs[k];
if (UNMARKED_LIBERTY(lib)) {
- if (libs != NULL && liberties < maxlib)
+ if (libs != NULL)
libs[liberties] = lib;
liberties++;
if (liberties >= maxlib)
@@ -2171,7 +2187,7 @@
}
if (UNMARKED_LIBERTY(NORTH(pos))) {
- if (libs != NULL && liberties < maxlib)
+ if (libs != NULL)
libs[liberties] = NORTH(pos);
liberties++;
/* Stop counting if we reach maxlib. */
@@ -2180,11 +2196,11 @@
MARK_LIBERTY(NORTH(pos));
}
else if (board[NORTH(pos)] == color) {
- int s = string_number[NORTH(pos)];
- for (k = 0; k < string[s].liberties; k++) {
- int lib = string[s].libs[k];
+ struct string_data *s = &string[string_number[NORTH(pos)]];
+ for (k = 0; k < s->liberties; k++) {
+ int lib = s->libs[k];
if (UNMARKED_LIBERTY(lib)) {
- if (libs != NULL && liberties < maxlib)
+ if (libs != NULL)
libs[liberties] = lib;
liberties++;
if (liberties >= maxlib)
@@ -2194,29 +2210,27 @@
}
}
+ /* Note that we don't mark liberties anymore since we're about
+ * to leave.
+ */
if (UNMARKED_LIBERTY(EAST(pos))) {
- if (libs != NULL && liberties < maxlib)
+ if (libs != NULL)
libs[liberties] = EAST(pos);
liberties++;
/* Stop counting if we reach maxlib. */
if (liberties >= maxlib)
return liberties;
- /* Unneeded since we're about to leave. */
-#if 0
- MARK_LIBERTY(EAST(pos));
-#endif
}
else if (board[EAST(pos)] == color) {
- int s = string_number[EAST(pos)];
- for (k = 0; k < string[s].liberties; k++) {
- int lib = string[s].libs[k];
+ struct string_data *s = &string[string_number[EAST(pos)]];
+ for (k = 0; k < s->liberties; k++) {
+ int lib = s->libs[k];
if (UNMARKED_LIBERTY(lib)) {
- if (libs != NULL && liberties < maxlib)
+ if (libs != NULL)
libs[liberties] = lib;
liberties++;
if (liberties >= maxlib)
return liberties;
- MARK_LIBERTY(lib);
}
}
}
@@ -2225,6 +2239,194 @@
}
+/* Find the liberties a stone of the given color would get if played
+ * at (pos). This function takes into consideration all captures. Its
+ * return value is exact in that sense it counts all the liberties,
+ * unless (maxlib) allows it to stop earlier. (pos) must be empty. If
+ * libs != NULL, the locations of up to maxlib liberties are written
+ * into libs[]. The counting of liberties may or may not be halted
+ * when maxlib is reached. The number of liberties is returned.
+ *
+ * This function guarantees that liberties which are not results of
+ * captures come first in libs[] array. To find whether all the
+ * liberties starting from a given one are results of captures, one
+ * may use if (board[libs[k]] != EMPTY) construction.
+ *
+ * If you want the number or the locations of all liberties, however
+ * many they are, you should pass MAXLIBS as the value for maxlib and
+ * allocate space for libs[] accordingly.
+ */
+
+int
+accuratelib(int pos, int color, int maxlib, int *libs)
+{
+ int k, l;
+ int liberties = 0;
+ int lib;
+ int captured[4];
+ int captures = 0;
+
+ ASSERT1(board[pos] == EMPTY, pos);
+ ASSERT1(IS_STONE(color), pos);
+
+ if (!libs) {
+ int fast_liberties = fastlib(pos, color, 0);
+ if (fast_liberties >= 0)
+ return fast_liberties;
+ }
+
+ if (!strings_initialized)
+ init_board();
+
+ string_mark++;
+ liberty_mark++;
+ MARK_LIBERTY(pos);
+
+ for (k = 0; k < 4; k++) {
+ int pos2 = pos + delta[k];
+ if (UNMARKED_LIBERTY(pos2)) {
+ /* A trivial liberty */
+ if (libs)
+ libs[liberties] = pos2;
+ liberties++;
+ if (liberties >= maxlib)
+ return liberties;
+
+ MARK_LIBERTY(pos2);
+ }
+ else if (board[pos2] == color) {
+ /* An own neighbor string */
+ struct string_data *s = &string[string_number[pos2]];
+
+ if (s->liberties <= MAX_LIBERTIES || maxlib <= MAX_LIBERTIES - 1) {
+ /* The easy case - we already have all (necessary) liberties of
+ * the string listed
+ */
+ for (l = 0; l < s->liberties; l++) {
+ lib = s->libs[l];
+ if (UNMARKED_LIBERTY(lib)) {
+ if(libs)
+ libs[liberties] = lib;
+ liberties++;
+ if(liberties >= maxlib)
+ return liberties;
+
+ MARK_LIBERTY(lib);
+ }
+ }
+ }
+ else {
+ /* The harder case - we need to find all the liberties of the
+ * string by traversing its stones. We stop as soon as we have
+ * traversed all the stones or have reached maxlib. Unfortunately,
+ * we cannot use the trick from findlib() since some of the
+ * liberties may already have been marked.
+ */
+ int stone = pos2;
+ do {
+ if (UNMARKED_LIBERTY(SOUTH(stone))) {
+ if (libs)
+ libs[liberties] = SOUTH(stone);
+ liberties++;
+ if (liberties >= maxlib)
+ return liberties;
+
+ MARK_LIBERTY(SOUTH(stone));
+ }
+
+ if (UNMARKED_LIBERTY(WEST(stone))) {
+ if (libs)
+ libs[liberties] = WEST(stone);
+ liberties++;
+ if (liberties >= maxlib)
+ return liberties;
+
+ MARK_LIBERTY(WEST(stone));
+ }
+
+ if (UNMARKED_LIBERTY(NORTH(stone))) {
+ if (libs)
+ libs[liberties] = NORTH(stone);
+ liberties++;
+ if (liberties >= maxlib)
+ return liberties;
+
+ MARK_LIBERTY(NORTH(stone));
+ }
+
+ if (UNMARKED_LIBERTY(EAST(stone))) {
+ if (libs)
+ libs[liberties] = EAST(stone);
+ liberties++;
+ if (liberties >= maxlib)
+ return liberties;
+
+ MARK_LIBERTY(EAST(stone));
+ }
+
+ stone = NEXT_STONE(stone);
+ } while (stone != pos2);
+ }
+
+ MARK_STRING(pos2);
+ }
+ else if (board[pos2] == OTHER_COLOR(color)
+ && string[string_number[pos2]].liberties == 1) {
+ /* A capture. */
+ captured[captures++] = pos2;
+ }
+ }
+
+ /* Now we look at all the captures found in the previous step */
+ for (k = 0; k < captures; k++) {
+ lib = captured[k];
+
+ /* Add the stone adjacent to (pos) to the list of liberties if
+ * it is not also adjacent to an own marked string (otherwise,
+ * it will be added later).
+ */
+ if (!MARKED_COLOR_STRING(SOUTH(lib), color)
+ && !MARKED_COLOR_STRING(WEST(lib), color)
+ && !MARKED_COLOR_STRING(NORTH(lib), color)
+ && !MARKED_COLOR_STRING(EAST(lib), color)) {
+ if (libs)
+ libs[liberties] = lib;
+ liberties++;
+ if (liberties >= maxlib)
+ return liberties;
+ }
+
+ /* Check if we already know of this capture. */
+ for (l = 0; l < k; l++)
+ if (string_number[captured[l]] == string_number[lib])
+ break;
+
+ if (l == k) {
+ /* Traverse all the stones of the capture and add to the list
+ * of liberties those, which are adjacent to at least one own
+ * marked string.
+ */
+ do {
+ if (MARKED_COLOR_STRING(SOUTH(lib), color)
+ || MARKED_COLOR_STRING(WEST(lib), color)
+ || MARKED_COLOR_STRING(NORTH(lib), color)
+ || MARKED_COLOR_STRING(EAST(lib), color)) {
+ if (libs)
+ libs[liberties] = lib;
+ liberties++;
+ if (liberties >= maxlib)
+ return liberties;
+ }
+
+ lib = NEXT_STONE(lib);
+ } while (lib != captured[k]);
+ }
+ }
+
+ return liberties;
+}
+
+
/* Find the number of common liberties of the two strings at str1 and str2.
*/
@@ -2596,10 +2798,11 @@
*/
for (r = 0; r < liberties; r++) {
for (k = 0; k < 4; k++) {
- if ((board[libs[r] + delta[k]] == OTHER_COLOR(board[str])
- || (both_colors && board[libs[r] + delta[k]] == board[str]))
- && UNMARKED_STRING(libs[r] + delta[k])) {
- adj[n] = string[string_number[libs[r] + delta[k]]].origin;
+ int neighbor = libs[r] + delta[k];
+ if ((board[neighbor] == OTHER_COLOR(board[str])
+ || (both_colors && board[neighbor] == board[str]))
+ && UNMARKED_STRING(neighbor)) {
+ adj[n] = string[string_number[neighbor]].origin;
MARK_STRING(adj[n]);
n++;
}
@@ -2636,8 +2839,15 @@
int
is_self_atari(int pos, int color)
{
- int liberties;
- int result;
+ int other = OTHER_COLOR(color);
+ /* number of empty neighbors */
+ int trivial_liberties = 0;
+ /* number of captured opponent strings */
+ int captures = 0;
+ /* Whether there is a friendly neighbor with a spare liberty. If it
+ * has more than one spare liberty we immediately return 0.
+ */
+ int far_liberties = 0;
ASSERT_ON_BOARD1(pos);
ASSERT1(board[pos] == EMPTY, pos);
@@ -2646,21 +2856,82 @@
if (!strings_initialized)
init_board();
- /* 1. Try first without really putting the stone on the board. */
- /* FIXME: Integrate incremental_sloppy_self_atari() here. */
- result = incremental_sloppy_self_atari(pos, color);
- if (result != -1)
- return result;
+ /* 1. Try first to solve the problem without much work. */
+ string_mark++;
+
+ if (LIBERTY(SOUTH(pos)))
+ trivial_liberties++;
+ else if (board[SOUTH(pos)] == color) {
+ if (LIBERTIES(SOUTH(pos)) > 2)
+ return 0;
+ if (LIBERTIES(SOUTH(pos)) == 2)
+ far_liberties++;
+ }
+ else if (board[SOUTH(pos)] == other
+ && LIBERTIES(SOUTH(pos)) == 1 && UNMARKED_STRING(SOUTH(pos))) {
+ captures++;
+ MARK_STRING(SOUTH(pos));
+ }
+
+ if (LIBERTY(WEST(pos)))
+ trivial_liberties++;
+ else if (board[WEST(pos)] == color) {
+ if (LIBERTIES(WEST(pos)) > 2)
+ return 0;
+ if (LIBERTIES(WEST(pos)) == 2)
+ far_liberties++;
+ }
+ else if (board[WEST(pos)] == other
+ && LIBERTIES(WEST(pos)) == 1 && UNMARKED_STRING(WEST(pos))) {
+ captures++;
+ MARK_STRING(WEST(pos));
+ }
+
+ if (LIBERTY(NORTH(pos)))
+ trivial_liberties++;
+ else if (board[NORTH(pos)] == color) {
+ if (LIBERTIES(NORTH(pos)) > 2)
+ return 0;
+ if (LIBERTIES(NORTH(pos)) == 2)
+ far_liberties++;
+ }
+ else if (board[NORTH(pos)] == other
+ && LIBERTIES(NORTH(pos)) == 1 && UNMARKED_STRING(NORTH(pos))) {
+ captures++;
+ MARK_STRING(NORTH(pos));
+ }
+
+ if (LIBERTY(EAST(pos)))
+ trivial_liberties++;
+ else if (board[EAST(pos)] == color) {
+ if (LIBERTIES(EAST(pos)) > 2)
+ return 0;
+ if (LIBERTIES(EAST(pos)) == 2)
+ far_liberties++;
+ }
+ else if (board[EAST(pos)] == other
+ && LIBERTIES(EAST(pos)) == 1 && UNMARKED_STRING(EAST(pos))) {
+ captures++;
+#if 0
+ MARK_STRING(EAST(pos));
+#endif
+ }
- /* 2. It was not so easy. Now see if we can put the stone on the board.
- * If we can't, this is a self atari.
+ /* Each captured string is guaranteed to produce at least one
+ * liberty. These are disjoint from both trivial liberties and far
+ * liberties. The two latter may however coincide.
*/
- if (!do_trymove(pos, color, 1))
+ if (trivial_liberties + captures >= 2)
+ return 0;
+
+ if ((far_liberties > 0) + captures >= 2)
+ return 0;
+
+ if (captures == 0 && far_liberties + trivial_liberties <= 1)
return 1;
- liberties = string[string_number[pos]].liberties;
- silent_popgo();
-
- return liberties <= 1;
+
+ /* 2. It was not so easy. We use accuratelib() in this case. */
+ return accuratelib(pos, color, 2, NULL) <= 1;
}
@@ -3854,44 +4125,44 @@
*/
string_mark++;
- if (board[south] == color && UNMARKED_STRING(south)) {
+ if (UNMARKED_COLOR_STRING(south, color)) {
neighbor_allies++;
s = string_number[south];
MARK_STRING(south);
}
- else if (board[south] == other && UNMARKED_STRING(south)) {
+ else if (UNMARKED_COLOR_STRING(south, other)) {
remove_liberty(string_number[south], pos);
MARK_STRING(south);
}
- if (board[west] == color && UNMARKED_STRING(west)) {
+ if (UNMARKED_COLOR_STRING(west, color)) {
neighbor_allies++;
s = string_number[west];
MARK_STRING(west);
}
- else if (board[west] == other && UNMARKED_STRING(west)) {
+ else if (UNMARKED_COLOR_STRING(west, other)) {
remove_liberty(string_number[west], pos);
MARK_STRING(west);
}
- if (board[north] == color && UNMARKED_STRING(north)) {
+ if (UNMARKED_COLOR_STRING(north, color)) {
neighbor_allies++;
s = string_number[north];
MARK_STRING(north);
}
- else if (board[north] == other && UNMARKED_STRING(north)) {
+ else if (UNMARKED_COLOR_STRING(north, other)) {
remove_liberty(string_number[north], pos);
MARK_STRING(north);
}
- if (board[east] == color && UNMARKED_STRING(east)) {
+ if (UNMARKED_COLOR_STRING(east, color)) {
neighbor_allies++;
s = string_number[east];
#if 0
MARK_STRING(east);
#endif
}
- else if (board[east] == other && UNMARKED_STRING(east)) {
+ else if (UNMARKED_COLOR_STRING(east, other)) {
remove_liberty(string_number[east], pos);
#if 0
MARK_STRING(east);
@@ -3943,140 +4214,44 @@
liberty_mark++;
MARK_LIBERTY(pos);
string_mark++;
+
for (k = 0; k < 4; k++) {
- int d = delta[k];
- if (UNMARKED_LIBERTY(pos + d)) {
+ int pos2 = pos + delta[k];
+ if (UNMARKED_LIBERTY(pos2)) {
if (libs)
- libs[liberties] = pos + d;
+ libs[liberties] = pos2;
liberties++;
if (liberties == maxlib)
return liberties;
- MARK_LIBERTY(pos + d);
+ MARK_LIBERTY(pos2);
}
- else if (board[pos + d] == color
- && UNMARKED_STRING(pos + d)) {
- int s = string_number[pos + d];
- int pos2;
- pos2 = FIRST_STONE(s);
+ else if (UNMARKED_COLOR_STRING(pos2, color)) {
+ int s = string_number[pos2];
+ int stone;
+ stone = FIRST_STONE(s);
do {
int l;
for (l = 0; l < 4; l++) {
- int d2 = delta[l];
- if (UNMARKED_LIBERTY(pos2 + d2)) {
+ int lib = stone + delta[l];
+ if (UNMARKED_LIBERTY(lib)) {
if (libs)
- libs[liberties] = pos2 + d2;
+ libs[liberties] = lib;
liberties++;
if (liberties == maxlib)
return liberties;
- MARK_LIBERTY(pos2 + d2);
+ MARK_LIBERTY(lib);
}
}
- pos2 = NEXT_STONE(pos2);
- } while (!BACK_TO_FIRST_STONE(s, pos2));
- MARK_STRING(pos + d);
+ stone = NEXT_STONE(stone);
+ } while (!BACK_TO_FIRST_STONE(s, stone));
+ MARK_STRING(pos2);
}
}
+
return liberties;
}
-
-/* Determine whether a move by color at pos might be a self atari.
- * This function is sloppy in that it only does a quick check for two
- * liberties and might miss certain cases.
- * Return value 0 means it cannot be a self atari.
- * Return value 1 means it definitely is a self atari.
- * Return value -1 means uncertain.
- */
-
-static int
-incremental_sloppy_self_atari(int pos, int color)
-{
- int other = OTHER_COLOR(color);
- /* number of empty neighbors */
- int trivial_liberties = 0;
- /* number of captured opponent strings */
- int captures = 0;
- /* Whether there is a friendly neighbor with a spare liberty. If it
- * has more than one spare liberty we immediately return 0.
- */
- int far_liberties = 0;
-
- /* Clear string mark. */
- string_mark++;
-
- if (board[SOUTH(pos)] == EMPTY)
- trivial_liberties++;
- else if (board[SOUTH(pos)] == color) {
- if (LIBERTIES(SOUTH(pos)) > 2)
- return 0;
- if (LIBERTIES(SOUTH(pos)) == 2)
- far_liberties++;
- }
- else if (board[SOUTH(pos)] == other
- && LIBERTIES(SOUTH(pos)) == 1 && UNMARKED_STRING(SOUTH(pos))) {
- captures++;
- MARK_STRING(SOUTH(pos));
- }
-
- if (board[WEST(pos)] == EMPTY)
- trivial_liberties++;
- else if (board[WEST(pos)] == color) {
- if (LIBERTIES(WEST(pos)) > 2)
- return 0;
- if (LIBERTIES(WEST(pos)) == 2)
- far_liberties++;
- }
- else if (board[WEST(pos)] == other
- && LIBERTIES(WEST(pos)) == 1 && UNMARKED_STRING(WEST(pos))) {
- captures++;
- MARK_STRING(WEST(pos));
- }
-
- if (board[NORTH(pos)] == EMPTY)
- trivial_liberties++;
- else if (board[NORTH(pos)] == color) {
- if (LIBERTIES(NORTH(pos)) > 2)
- return 0;
- if (LIBERTIES(NORTH(pos)) == 2)
- far_liberties++;
- }
- else if (board[NORTH(pos)] == other
- && LIBERTIES(NORTH(pos)) == 1 && UNMARKED_STRING(NORTH(pos))) {
- captures++;
- MARK_STRING(NORTH(pos));
- }
-
- if (board[EAST(pos)] == EMPTY)
- trivial_liberties++;
- else if (board[EAST(pos)] == color) {
- if (LIBERTIES(EAST(pos)) > 2)
- return 0;
- if (LIBERTIES(EAST(pos)) == 2)
- far_liberties++;
- }
- else if (board[EAST(pos)] == other
- && LIBERTIES(EAST(pos)) == 1 && UNMARKED_STRING(EAST(pos))) {
- captures++;
- MARK_STRING(EAST(pos));
- }
-
- /* Each captured string is guaranteed to produce at least one
- * liberty. These are disjoint from both trivial liberties and far
- * liberties. The two latter may however coincide.
- */
-
- if (trivial_liberties + captures >= 2)
- return 0;
-
- if ((far_liberties > 0) + captures >= 2)
- return 0;
-
- if (captures == 0 && far_liberties + trivial_liberties <= 1)
- return 1;
-
- return -1;
-}
/* ================================================================ *
Index: gnugo/interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.94
diff -u -r1.94 play_gtp.c
--- gnugo/interface/play_gtp.c 9 Oct 2002 18:36:23 -0000 1.94
+++ gnugo/interface/play_gtp.c 15 Oct 2002 19:11:43 -0000
@@ -67,6 +67,7 @@
DECLARE(gtp_echo);
DECLARE(gtp_echo_err);
DECLARE(gtp_eval_eye);
+DECLARE(gtp_accuratelib);
DECLARE(gtp_final_score);
DECLARE(gtp_final_status);
DECLARE(gtp_final_status_list);
@@ -165,6 +166,7 @@
{"echo" , gtp_echo},
{"echo_err" , gtp_echo_err},
{"estimate_score", gtp_estimate_score},
+ {"accuratelib", gtp_accuratelib},
{"experimental_score", gtp_experimental_score},
{"eval_eye", gtp_eval_eye},
{"final_score", gtp_final_score},
@@ -740,6 +742,34 @@
return gtp_failure("vertex must not be empty");
liberties = findlib(POS(i, j), MAXLIBS, libs);
+ gtp_start_response(GTP_SUCCESS);
+ gtp_print_vertices2(liberties, libs);
+ return gtp_finish_response();
+}
+
+
+/* Function: Determine which liberties a stone of given color
+ * will get if played at given vertex.
+ * Arguments: move (color + vertex)
+ * Fails: invalid color, invalid vertex, occupied vertex
+ * Returns: Sorted space separated list of liberties
+ */
+static int
+gtp_accuratelib(char *s)
+{
+ int i, j;
+ int color;
+ int libs[MAXLIBS];
+ int liberties;
+
+ if (!gtp_decode_move(s, &color, &i, &j))
+ return gtp_failure("invalid color or coordinate");
+
+ if (BOARD(i, j) != EMPTY)
+ return gtp_failure("vertex must be empty");
+
+ liberties = accuratelib(POS(i, j), color, MAXLIBS, libs);
+
gtp_start_response(GTP_SUCCESS);
gtp_print_vertices2(liberties, libs);
return gtp_finish_response();
Index: gnugo/patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.82
diff -u -r1.82 mkpat.c
--- gnugo/patterns/mkpat.c 30 Sep 2002 21:04:14 -0000 1.82
+++ gnugo/patterns/mkpat.c 15 Oct 2002 19:11:49 -0000
@@ -224,9 +224,9 @@
{"approx_olib", 1, 0.03,
"approxlib(%s, color, MAX_LIBERTIES, NULL)"},
{"xlib", 1, 0.05,
- "accurate_approxlib(%s, OTHER_COLOR(color), MAX_LIBERTIES, NULL)"},
+ "accuratelib(%s, OTHER_COLOR(color), MAX_LIBERTIES, NULL)"},
{"olib", 1, 0.05,
- "accurate_approxlib(%s,color, MAX_LIBERTIES, NULL)"},
+ "accuratelib(%s, color, MAX_LIBERTIES, NULL)"},
{"xcut", 1, 0.01, "cut_possible(%s,OTHER_COLOR(color))"},
{"ocut", 1, 0.05, "cut_possible(%s,color)"},
{"edge_double_sente", 4, 3.00,
- [gnugo-devel] liberty counting, revised,
Paul Pogonyshev <=