[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] persistent caching for break-in reading
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] persistent caching for break-in reading |
|
Date: |
Sun, 8 Jun 2003 16:53:36 +0200 (CEST) |
This is persistent caching for the break_in reading. It is pretty
aggressive (i.e., a rather small active area); but this is actually
safer in the case of break-in reading.
It should be pointed out that this does make a big difference even
when examing only a single position. The reason is that the break-in
analysis is repeated for every move that gets a territorial evaluation.
And with the persistent caches, these "after move" evaluation can benefit
from the initial evaluations.
(The code is again borrowed from the readconnect case, apart from the
computation of the reading shadow, which I need drastically smaller.
Actually, the connection reading shadow looks a little too big to me.)
Arend
diff -X /home/arend/.diffignore -ur ../gnugo-break-through/engine/genmove.c
./engine/genmove.c
--- ../gnugo-break-through/engine/genmove.c Fri May 23 22:56:21 2003
+++ ./engine/genmove.c Sat Jun 7 18:03:45 2003
@@ -111,6 +111,7 @@
purge_persistent_reading_cache();
purge_persistent_connection_cache();
+ purge_persistent_breakin_cache();
/* Don't print reading traces during make_worms and make_dragons unless
* the user really wants it (verbose == 3).
diff -X /home/arend/.diffignore -ur ../gnugo-break-through/engine/globals.c
./engine/globals.c
--- ../gnugo-break-through/engine/globals.c Sun Jun 8 09:20:33 2003
+++ ./engine/globals.c Sat Jun 7 20:41:13 2003
@@ -83,7 +83,9 @@
int semeai_node_limit;
int connect_depth; /* Used by Tristan Cazenave's connection reader. */
int connect_depth2; /* Used by alternater connection reader. */
-int connection_node_limit;
+int connection_node_limit;
+int breakin_node_limit; /* Reading limits for break_in/block_off reading */
+int breakin_depth;
int mandated_depth; /* deep reading cut off, mandated value */
int mandated_backfill_depth; /* deep reading cut off, mandated value */
int mandated_backfill2_depth; /* deep reading cut off, mandated value */
diff -X /home/arend/.diffignore -ur ../gnugo-break-through/engine/liberty.h
./engine/liberty.h
--- ../gnugo-break-through/engine/liberty.h Sun Jun 8 09:20:34 2003
+++ ./engine/liberty.h Sat Jun 7 20:41:15 2003
@@ -339,6 +339,14 @@
int result, int move,
int tactical_nodes,
char connection_shadow[BOARDMAX]);
+int search_persistent_breakin_cache(int routine, int str, Hash_data goal_hash,
+ int *result, int *move);
+void store_persistent_breakin_cache(int routine, int str, Hash_data goal_hash,
+ int result, int move,
+ int tactical_nodes,
+ char breakin_shadow[BOARDMAX]);
+void purge_persistent_breakin_cache(void);
+void clear_persistent_breakin_cache(void);
void purge_persistent_owl_cache(void);
void clear_persistent_owl_cache(void);
int search_persistent_owl_cache(int routine, int apos, int bpos, int cpos,
@@ -801,6 +809,8 @@
extern int connect_depth;
extern int connect_depth2;
extern int connection_node_limit;
+extern int breakin_depth;
+extern int breakin_node_limit;
extern int level; /* controls the strength of play */
extern int semeai_variations; /* max variations considered reading semeai */
extern float best_move_values[10];
diff -X /home/arend/.diffignore -ur ../gnugo-break-through/engine/persistent.c
./engine/persistent.c
--- ../gnugo-break-through/engine/persistent.c Mon Jun 2 18:09:54 2003
+++ ./engine/persistent.c Sat Jun 7 18:13:47 2003
@@ -34,9 +34,10 @@
* active area may cause an incorrect read result to be retrieved from
* the cache.
*
- * Persistent caching has so far been implemented for tactical reading
- * and owl reading (with connection reading and semeai reading planned
- * for the future). Since different data is stored for the different
+ * Persistent caching has so far been implemented for tactical reading,
+ * owl reading, connection reading and break-in reading (with semeai
+ * reading planned for the future).
+ * Since different data is stored for the different
* types of reading, similar but different data structures and
* functions are implemented for each cache.
*
@@ -111,6 +112,28 @@
persistent_connection_cache[MAX_CONNECTION_CACHE_SIZE];
static int persistent_connection_cache_size = 0;
+#define MAX_BREAKIN_CACHE_SIZE 150
+#define MAX_BREAKIN_CACHE_DEPTH 1
+
+struct breakin_cache {
+ int boardsize;
+ char board[BOARDMAX];
+ int movenum;
+ int nodes;
+ int score;
+ int remaining_depth;
+ int routine; /* BREAK_IN or BLOCK_OFF */
+ int str; /* string to connect (origin) */
+ Hash_data goal_hash; /* hash of the goal to which to connect to */
+ int result;
+ int move;
+ int stack[MAX_CONNECTION_CACHE_DEPTH];
+ int move_color[MAX_CONNECTION_CACHE_DEPTH];
+};
+
+static struct breakin_cache
+persistent_breakin_cache[MAX_BREAKIN_CACHE_SIZE];
+static int persistent_breakin_cache_size = 0;
/* Owl reading cache. */
@@ -154,6 +177,11 @@
int str1, int str2);
static void print_persistent_connection_cache_entry(int k);
+/* Breakin reading functions. */
+static int find_persistent_breakin_cache_entry(int routine, int str,
+ Hash_data goal_hash);
+static void print_persistent_breakin_cache_entry(int k);
+
/* Owl functions. */
static void print_persistent_owl_cache_entry(int k);
static void mark_dragon_hotspot_values(float values[BOARDMAX], int pos,
@@ -995,6 +1023,330 @@
gprintf("%oresult = %d\n", entry->result);
gprintf("%omove = %1m\n", entry->move);
+ for (r = 0; r < MAX_CONNECTION_CACHE_DEPTH; r++) {
+ if (entry->stack[r] == 0)
+ break;
+ gprintf("%ostack[%d] = %C %1m\n", r, entry->move_color[r],
+ entry->stack[r]);
+ }
+
+ draw_active_area(entry->board, NO_MOVE);
+}
+
+/* ================================================================ */
+/* Break-in reading functions */
+/* ================================================================ */
+
+/* Remove persistent cache entries which are no longer current. */
+void
+purge_persistent_breakin_cache()
+{
+ int k;
+ int r;
+ static int last_purge_position_number = -1;
+ gg_assert(stackp == 0);
+
+ /* Never do this more than once per move. */
+ if (last_purge_position_number == position_number)
+ return;
+ else
+ last_purge_position_number = position_number;
+
+ for (k = 0; k < persistent_breakin_cache_size; k++) {
+ int entry_ok = 1;
+ int played_moves = 0;
+
+ if (persistent_breakin_cache[k].boardsize != board_size)
+ entry_ok = 0;
+ else {
+ for (r = 0; r < MAX_CONNECTION_CACHE_DEPTH; r++) {
+ int apos = persistent_breakin_cache[k].stack[r];
+ int color = persistent_breakin_cache[k].move_color[r];
+ if (apos == 0)
+ break;
+ if (board[apos] == EMPTY
+ && trymove(apos, color, "purge_persistent_breakin_cache", 0,
+ EMPTY, 0))
+ played_moves++;
+ else {
+ entry_ok = 0;
+ break;
+ }
+ }
+ }
+
+ if (!entry_ok
+ || !verify_stored_board(persistent_breakin_cache[k].board)) {
+ /* Move the last entry in the cache here and back up the loop
+ * counter to redo the test at this position in the cache.
+ */
+ if (0)
+ gprintf("Purging entry %d from cache.\n", k);
+ if (k < persistent_breakin_cache_size - 1)
+ persistent_breakin_cache[k]
+ = persistent_breakin_cache[persistent_breakin_cache_size - 1];
+ k--;
+ persistent_breakin_cache_size--;
+ }
+ else {
+ /* This is to retire older cache entries that no longer get used. */
+ persistent_breakin_cache[k].score *= 3;
+ persistent_breakin_cache[k].score /= 4;
+ }
+
+ while (played_moves--)
+ popgo();
+ }
+}
+
+void
+clear_persistent_breakin_cache()
+{
+ persistent_breakin_cache_size = 0;
+}
+
+
+/* Locate a matching entry in the persistent breakin cache. Return the
+ * entry number or -1 if none found.
+ */
+static int
+find_persistent_breakin_cache_entry(int routine, int str,
+ Hash_data goal_hash)
+{
+ int k;
+ ASSERT1(str == find_origin(str), str);
+
+ for (k = 0; k < persistent_breakin_cache_size; k++) {
+ /* Check that everything matches. */
+ struct breakin_cache *entry = &(persistent_breakin_cache[k]);
+ int j;
+ if (entry->routine != routine
+ || entry->str != str
+ || entry->boardsize != board_size
+ || entry->remaining_depth < (depth - stackp))
+ continue;
+ for (j = 0; j < NUM_HASHVALUES; j++)
+ if (entry->goal_hash.hashval[j] != goal_hash.hashval[j])
+ break;
+ if (j < NUM_HASHVALUES)
+ continue;
+
+ if (!verify_stored_board(entry->board))
+ continue;
+
+ return k;
+ }
+
+ return -1;
+}
+
+
+/* Look for a valid read result in the persistent breakin cache.
+ * Return 1 if found, 0 otherwise.
+ */
+int
+search_persistent_breakin_cache(int routine, int str, Hash_data goal_hash,
+ int *result, int *move)
+{
+ int k;
+ struct breakin_cache *entry;
+
+ k = find_persistent_breakin_cache_entry(routine, str, goal_hash);
+ if (k == -1)
+ return 0;
+
+ /* Match found. Increase score and fill in the answer. */
+ entry = &(persistent_breakin_cache[k]);
+ entry->score += entry->nodes;
+ if (result)
+ *result = entry->result;
+ if (move)
+ *move = entry->move;
+ ASSERT1(entry->result == 0
+ || entry->move == NO_MOVE
+ || ON_BOARD(entry->move),
+ entry->move);
+
+ return 1;
+}
+
+
+/* Store a new breakin result in the persistent cache. */
+void
+store_persistent_breakin_cache(int routine, int str, Hash_data goal_hash,
+ int result, int move, int tactical_nodes,
+ char breakin_shadow[BOARDMAX])
+{
+ char active[BOARDMAX];
+ int k;
+ int r;
+ struct breakin_cache *entry;
+ int other = OTHER_COLOR(board[str]);
+ int pos;
+
+ ASSERT1(result == 0 || (move == 0) || ON_BOARD(move), move);
+
+
+ /* If cache is still full, consider kicking out an old entry. */
+ if (persistent_breakin_cache_size == MAX_BREAKIN_CACHE_SIZE) {
+ int worst_entry = -1;
+ int worst_score = score;
+
+ for (k = 1; k < persistent_breakin_cache_size; k++) {
+ if (persistent_breakin_cache[k].score < worst_score) {
+ worst_score = persistent_breakin_cache[k].score;
+ worst_entry = k;
+ }
+ }
+
+ if (worst_entry != -1) {
+ /* Move the last entry in the cache here to make space.
+ */
+ if (worst_entry < persistent_breakin_cache_size - 1)
+ persistent_breakin_cache[worst_entry]
+ = persistent_breakin_cache[persistent_breakin_cache_size - 1];
+ persistent_breakin_cache_size--;
+ }
+ else
+ return;
+ }
+
+ entry = &(persistent_breakin_cache[persistent_breakin_cache_size]);
+ entry->boardsize = board_size;
+ entry->movenum = movenum;
+ entry->nodes = tactical_nodes;
+ entry->score = tactical_nodes;
+ entry->remaining_depth = depth - stackp;
+ entry->routine = routine;
+ entry->str = str;
+ entry->goal_hash = goal_hash;
+ entry->result = result;
+ entry->move = move;
+
+ for (r = 0; r < MAX_BREAKIN_CACHE_DEPTH; r++) {
+ if (r < stackp)
+ get_move_from_stack(r, &(entry->stack[r]), &(entry->move_color[r]));
+ else {
+ entry->stack[r] = 0;
+ entry->move_color[r] = EMPTY;
+ }
+ }
+
+ /* Remains to set the board. We let the active area be
+ * the two strings to connect +
+ * the breakin shadow +
+ * distance two expansion through empty intersections and own stones +
+ * adjacent opponent strings +
+ * liberties of adjacent opponent strings with less than five liberties +
+ * liberties of low liberty neighbors of adjacent opponent strings
+ * with less than five liberties.
+ */
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+ active[pos] = breakin_shadow[pos];
+
+ mark_string(str, active, 1);
+
+ /* To be safe, also add the successful move. */
+ if (result != 0 && move != 0)
+ active[move] = 1;
+
+ /* Distance two expansion through empty intersections and own stones. */
+ for (k = 1; k < 3; k++) {
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++){
+ if (!ON_BOARD(pos) || board[pos] == other || active[pos] != 0)
+ continue;
+ if ((ON_BOARD(SOUTH(pos)) && active[SOUTH(pos)] == k)
+ || (ON_BOARD(WEST(pos)) && active[WEST(pos)] == k)
+ || (ON_BOARD(NORTH(pos)) && active[NORTH(pos)] == k)
+ || (ON_BOARD(EAST(pos)) && active[EAST(pos)] == k)) {
+ if (board[pos] == EMPTY)
+ active[pos] = k + 1;
+ else
+ mark_string(pos, active, (char) (k + 1));
+ }
+ }
+ }
+
+ /* Adjacent opponent strings. */
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+ if (board[pos] != other || active[pos] != 0)
+ continue;
+ for (r = 0; r < 4; r++) {
+ int pos2 = pos + delta[r];
+ if (ON_BOARD(pos2) && board[pos2] != other && active[pos2] != 0) {
+ mark_string(pos, active, (char) 1);
+ break;
+ }
+ }
+ }
+
+ /* Liberties of adjacent opponent strings with less than five liberties +
+ * liberties of low liberty neighbors of adjacent opponent strings
+ * with less than five liberties.
+ */
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+ if (board[pos] == other && active[pos] != 0 && countlib(pos) < 5) {
+ int libs[4];
+ int liberties = findlib(pos, 4, libs);
+ int adjs[MAXCHAIN];
+ int adj;
+ for (r = 0; r < liberties; r++)
+ active[libs[r]] = 1;
+
+ /* Also add liberties of neighbor strings if these are three
+ * or less.
+ */
+ adj = chainlinks(pos, adjs);
+ for (r = 0; r < adj; r++) {
+ if (countlib(adjs[r]) <= 3) {
+ int s;
+ liberties = findlib(adjs[r], 3, libs);
+ for (s = 0; s < liberties; s++)
+ active[libs[s]] = 1;
+ }
+ }
+ }
+ }
+
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+ int value = board[pos];
+ if (!ON_BOARD(pos))
+ continue;
+ if (!active[pos])
+ value = GRAY;
+ else if (IS_STONE(board[pos]) && countlib(pos) > 4)
+ value |= HIGH_LIBERTY_BIT;
+
+ persistent_breakin_cache[persistent_breakin_cache_size].board[pos] =
+ value;
+ }
+
+ if (0) {
+ gprintf("%o Stored result in cache (entry %d):\n",
+ persistent_breakin_cache_size);
+ print_persistent_breakin_cache_entry(persistent_breakin_cache_size);
+ }
+
+ persistent_breakin_cache_size++;
+}
+
+
+/* For debugging purposes. */
+static void
+print_persistent_breakin_cache_entry(int k)
+{
+ struct breakin_cache *entry = &(persistent_breakin_cache[k]);
+ int r;
+ gprintf("%oboardsize = %d\n", entry->boardsize);
+ gprintf("%omovenum = %d\n", entry->movenum);
+ gprintf("%onodes = %d\n", entry->nodes);
+ gprintf("%oscore = %d\n", entry->score);
+ gprintf("%oremaining_depth = %d\n", entry->remaining_depth);
+ gprintf("%oroutine = %d\n", entry->routine);
+ gprintf("%ostr = %1m\n", entry->str);
+ gprintf("%oresult = %d\n", entry->result);
+ gprintf("%omove = %1m\n", entry->move);
+
for (r = 0; r < MAX_CONNECTION_CACHE_DEPTH; r++) {
if (entry->stack[r] == 0)
break;
diff -X /home/arend/.diffignore -ur ../gnugo-break-through/engine/readconnect.c
./engine/readconnect.c
--- ../gnugo-break-through/engine/readconnect.c Thu Jun 5 18:27:14 2003
+++ ./engine/readconnect.c Sat Jun 7 20:31:05 2003
@@ -92,6 +92,8 @@
/* Used by alternate connections. */
static char connection_shadow[BOARDMAX];
+static char breakin_shadow[BOARDMAX];
+
/* Statistics. */
static int global_connection_node_counter = 0;
@@ -2596,6 +2598,7 @@
&& board[conn1.queue[k]] == color) {
str2 = conn1.queue[k];
TRACE("%oUsing %1m as secondary target.\n", str2);
+ mark_string(str2, breakin_shadow, 1);
break;
}
@@ -2632,7 +2635,7 @@
num_moves = find_connection_moves(str, str2, color_to_move,
&conn1, &conn2, max_dist1, max_dist2,
moves, *total_distance);
-
+
{
int move;
if (num_moves < MAX_MOVES
@@ -2641,17 +2644,13 @@
moves[num_moves++] = move;
}
}
+ for (k = 0; k < num_moves; k++)
+ breakin_shadow[moves[k]] = 1;
return num_moves;
}
-/* These depth values are set relative to the standard readconnnect depth
- * limits at each call of break_in()/block_off().
- * */
-static int break_in_node_limit;
-static int break_in_depth;
-
/* Can (str) connect to goal[] if the other color moves first? */
static int
recursive_break(int str, const char goal[BOARDMAX], int *move,
@@ -2682,12 +2681,12 @@
return 0;
}
- if (nodes_connect > break_in_node_limit) {
+ if (nodes_connect > breakin_node_limit) {
SGFTRACE(PASS_MOVE, 0, "connection node limit reached");
return 0;
}
- if (stackp > break_in_depth) {
+ if (stackp > breakin_depth) {
SGFTRACE(PASS_MOVE, 0, "connection depth limit reached");
return 0;
}
@@ -2806,12 +2805,12 @@
}
#endif
- if (nodes_connect > break_in_node_limit) {
+ if (nodes_connect > breakin_node_limit) {
SGFTRACE(PASS_MOVE, WIN, "connection node limit reached");
return WIN;
}
- if (stackp > break_in_depth) {
+ if (stackp > breakin_depth) {
SGFTRACE(PASS_MOVE, WIN, "connection depth limit reached");
return WIN;
}
@@ -2909,9 +2908,6 @@
int tactical_nodes;
Hash_data goal_hash = goal_to_hashvalue(goal);
- break_in_node_limit = connection_node_limit / 5;
- break_in_depth = connect_depth2 - 5;
-
if (move == NULL)
move = &dummy_move;
@@ -2922,11 +2918,15 @@
return 0;
str = find_origin(str);
+ if (search_persistent_breakin_cache(BREAK_IN, str, goal_hash,
+ &result, move))
+ return result;
+
save_verbose = verbose;
if (verbose > 0)
verbose--;
start = gg_cputime();
- memset(connection_shadow, 0, sizeof(connection_shadow));
+ memset(breakin_shadow, 0, sizeof(breakin_shadow));
result = recursive_break(str, goal, move, EMPTY, NO_MOVE, 0, &goal_hash);
verbose = save_verbose;
tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
@@ -2942,6 +2942,8 @@
dump_stack();
goaldump(goal);
}
+ store_persistent_breakin_cache(BREAK_IN, str, goal_hash, result, *move,
+ tactical_nodes, breakin_shadow);
return result;
}
@@ -2962,9 +2964,6 @@
int tactical_nodes;
Hash_data goal_hash = goal_to_hashvalue(goal);
- break_in_node_limit = connection_node_limit / 5;
- break_in_depth = connect_depth2 - 5;
-
if (move == NULL)
move = &dummy_move;
@@ -2972,12 +2971,15 @@
*move = PASS_MOVE;
str = find_origin(str);
+ if (search_persistent_breakin_cache(BREAK_IN, str, goal_hash,
+ &result, move))
+ return result;
save_verbose = verbose;
if (verbose > 0)
verbose--;
start = gg_cputime();
- memset(connection_shadow, 0, sizeof(connection_shadow));
+ memset(breakin_shadow, 0, sizeof(breakin_shadow));
result = recursive_block(str, goal, move, EMPTY, NO_MOVE, 0,
&goal_hash);
verbose = save_verbose;
@@ -2995,6 +2997,8 @@
goaldump(goal);
dump_stack();
}
+ store_persistent_breakin_cache(BLOCK_OFF, str, goal_hash, result, *move,
+ tactical_nodes, breakin_shadow);
return result;
}
diff -X /home/arend/.diffignore -ur ../gnugo-break-through/engine/utils.c
./engine/utils.c
--- ../gnugo-break-through/engine/utils.c Sun Jun 8 09:20:42 2003
+++ ./engine/utils.c Sat Jun 7 20:41:23 2003
@@ -634,6 +634,9 @@
#define CONNECT_DEPTH 64
#define CONNECT_DEPTH2 20
+#define BREAKIN_NODE_LIMIT 400
+#define BREAKIN_DEPTH 15
+
/* Set the various reading depth parameters. If mandated_depth_value
* is not -1 that value is used; otherwise the depth values are
* set as a function of level. The parameter mandated_depth_value
@@ -729,6 +732,8 @@
connect_depth = gg_max(2, CONNECT_DEPTH + 2 * depth_level);
connect_depth2 = gg_max(2, CONNECT_DEPTH2 + 2 * depth_level);
connection_node_limit = CONNECT_NODE_LIMIT * pow(1.5, depth_level);
+ breakin_depth = gg_max(2, BREAKIN_DEPTH + 2 * depth_level);
+ breakin_node_limit = BREAKIN_NODE_LIMIT * pow(1.5, depth_level);
if (mandated_depth != -1)
depth = mandated_depth;
diff -X /home/arend/.diffignore -ur ../gnugo-break-through/engine/value_moves.c
./engine/value_moves.c
--- ../gnugo-break-through/engine/value_moves.c Sun Jun 8 09:20:43 2003
+++ ./engine/value_moves.c Sat Jun 7 20:41:25 2003
@@ -1948,7 +1948,9 @@
OPPOSITE_INFLUENCE(color))) {
compute_influence(OTHER_COLOR(color), safe_stones, strength,
&move_influence, pos, "after move");
+ increase_depth_values();
break_territories(OTHER_COLOR(color), &move_influence, 0);
+ decrease_depth_values();
this_value = influence_delta_territory(OPPOSITE_INFLUENCE(color),
&move_influence, color, pos);
compute_followup_influence(&move_influence, &followup_influence,
diff -X /home/arend/.diffignore -ur ../gnugo-break-through/interface/play_gtp.c
./interface/play_gtp.c
--- ../gnugo-break-through/interface/play_gtp.c Sun Jun 8 09:20:43 2003
+++ ./interface/play_gtp.c Sat Jun 7 20:41:27 2003
@@ -1126,6 +1126,8 @@
UNUSED(s);
clear_persistent_reading_cache();
clear_persistent_owl_cache();
+ clear_persistent_connection_cache();
+ clear_persistent_breakin_cache();
return gtp_success("");
}
- [gnugo-devel] persistent caching for break-in reading,
Arend Bayer <=