[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] fast_defense() improvement
From: |
nando |
Subject: |
[gnugo-devel] fast_defense() improvement |
Date: |
Sat, 29 May 2004 23:06:53 +0200 |
Hi,
The idea is simple : there might be some adjacent opponent stones in atari,
checking if capturing them wouldn't give enough liberties to win, proved to
be cheap enough.
No breakage. Performance impact :
- reading nodes : -4.7%
- owl nodes : < +0.1%
- connection nodes : < +0.01%
My imprecise timings give me a 4% speedup.
nando
- new function count_adj_stones() in board.c
- fast_defense() looks for neighbor opponent strings in atari
Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.98
diff -u -r1.98 board.c
--- engine/board.c 27 May 2004 00:08:46 -0000 1.98
+++ engine/board.c 29 May 2004 20:36:01 -0000
@@ -2383,6 +2383,41 @@
}
+/* Counts how many stones in str1 are directly adjacent to str2.
+ * A limit can be given in the maxstones parameter so that the
+ * function returns immediately. See fast_defense() in reading.c
+ */
+
+int
+count_adj_stones(int str1, int str2, int maxstones)
+{
+ int s1, s2;
+ int size;
+ int pos;
+ int k;
+ int count = 0;
+
+ ASSERT_ON_BOARD1(str1);
+ ASSERT1(IS_STONE(board[str1]), str1);
+ ASSERT_ON_BOARD1(str2);
+ ASSERT1(IS_STONE(board[str2]), str2);
+
+ s1 = string_number[str1];
+ s2 = string_number[str2];
+ size = string[s1].size;
+
+ /* Traverse the stones of the string, by following the cyclic chain. */
+ pos = FIRST_STONE(s1);
+ for (k = 0; k < size && count < maxstones; k++) {
+ if (NEIGHBOR_OF_STRING(pos, s2, board[str2]))
+ count++;
+ pos = NEXT_STONE(pos);
+ }
+
+ return count;
+}
+
+
/* chainlinks returns (in the (adj) array) the chains surrounding
* the string at (str). The number of chains is returned.
*/
Index: engine/board.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.h,v
retrieving revision 1.12
diff -u -r1.12 board.h
--- engine/board.h 27 May 2004 00:08:46 -0000 1.12
+++ engine/board.h 29 May 2004 20:36:01 -0000
@@ -302,6 +302,7 @@
/* Count the number of stones in a string. */
int countstones(int str);
int findstones(int str, int maxstones, int *stones);
+int count_adj_stones(int str1, int str2, int maxstones);
/* Special function for reading.c */
void incremental_order_moves(int move, int color, int string,
Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.143
diff -u -r1.143 reading.c
--- engine/reading.c 25 May 2004 03:13:45 -0000 1.143
+++ engine/reading.c 29 May 2004 20:36:01 -0000
@@ -1240,8 +1240,9 @@
fast_defense(int str, int liberties, int *libs, int *move)
{
int color = board[str];
- int k;
+ int j, k, l;
int goal_liberties = (stackp < fourlib_depth ? 5 : 4);
+ int adj, adjs[MAXCHAIN];
ASSERT1(libs != NULL, str);
ASSERT1(move != NULL, str);
@@ -1255,6 +1256,69 @@
return 1;
}
}
+
+ /* Check the cases where an opponent neighbor string is in
+ * atari.
+ */
+ adj = chainlinks2(str, adjs, 1);
+ for (j = 0; j < adj; j++) {
+ int lib;
+ int missing = goal_liberties - liberties;
+ int total = 0;
+ int adj2, adjs2[MAXCHAIN];
+ int alib, alibs[MAXLIBS];
+ int mw[BOARDMAX];
+
+ findlib(adjs[j], 1, &lib);
+ /* We aren't interested in ko (at this stage). And playing
+ * our own last liberty to capture is prone to snapbacks,
+ * so better let the 'normal' reading routines do the job.
+ */
+ if ((liberties == 1 && liberty_of_string(lib, str)
+ && countstones(adjs[j]) <= 2)
+ || is_ko(lib, color, NULL))
+ continue;
+
+ /* Would the capture already gain enough liberties ?
+ * No need to test the case if the move is one of our liberties,
+ * it has already been done in the first loop of this function.
+ */
+ if (!liberty_of_string(lib, str)
+ && count_adj_stones(adjs[j], str, missing) >= missing) {
+ *move = lib;
+ return 1;
+ }
+
+ /* Let's totalize liberties of the friendly strings around the
+ * lunch.
+ */
+ memset(mw, 0, sizeof(mw));
+ adj2 = chainlinks(adjs[j], adjs2);
+ for (k = 0; k < adj2; k++) {
+ alib = findlib(adjs2[k], MAXLIBS, alibs);
+ for (l = 0; l < alib; l++) {
+ mw[alibs[l]]++;
+ if (mw[alibs[l]] == 1)
+ total++;
+ }
+ }
+
+ /* The captured string is treated as common liberties, and
+ * some adjustements are made :
+ * - we're adding a stone for capturing the lunch (-1)
+ * - opponent might be able to remove a liberty (-1)
+ * - and possibly force us to connect (-1)
+ */
+ total += countstones(adjs[j]) - 2;
+ if (mw[lib] < 2)
+ total--;
+
+ if (total >= goal_liberties) {
+ *move = lib;
+ return 1;
+ }
+ }
+
return 0;
}
- [gnugo-devel] fast_defense() improvement,
nando <=