[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] persistent semeai caching
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] persistent semeai caching |
|
Date: |
Thu, 19 Aug 2004 20:42:37 +0200 (CEST) |
- persistent semeai caching
As explained when I posted my cache to reorganize the persistent caching,
there is now rather little to do to implement this. The most crucial part of
computing the "active area" (the area that has to match to declare the
result valid when trying to reuse it). I solved this by reusing the function
to do this in the owl case, and applying it once for each goal dragon in
the semeai.
Other than that, the only noteworthy thing might be that I also added a hash
of the goal areas. This e.g. makes sure we don't reuse a result that
was obtained without "recompute_dragons" when we are supposed to recompute
it.
I haven't done measurements of the performance improvement yet. There is
one FAIL in nicklas1:1405 but I _think_ this is due to a bug in existing
code.
Arend
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.221
diff -u -p -r1.221 liberty.h
--- engine/liberty.h 19 Jul 2004 12:23:08 -0000 1.221
+++ engine/liberty.h 19 Aug 2004 18:29:21 -0000
@@ -80,6 +80,7 @@ enum routine_id {
OWL_CONNECTION_DEFENDS,
OWL_SUBSTANTIAL,
OWL_CONFIRM_SAFETY,
+ ANALYZE_SEMEAI,
NUM_CACHE_ROUTINES
};
@@ -99,7 +100,8 @@ enum routine_id {
"owl_does_attack", \
"owl_connection_defends", \
"owl_substantial", \
- "owl_confirm_safety"
+ "owl_confirm_safety", \
+ "analyze_semeai"
/* To prioritize between different types of reading, we give a cost
* ranking to each of the routines above:
@@ -113,7 +115,7 @@ enum routine_id {
* -1 is left at the end for a consistency check.
*/
#define ROUTINE_COSTS \
- 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, -1
+ 3, 3, 4, 0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, -1
const char *routine_id_to_string(enum routine_id routine);
@@ -268,6 +270,18 @@ void store_persistent_owl_cache(enum rou
int tactical_nodes, char goal[BOARDMAX],
int goal_color);
void owl_hotspots(float values[BOARDMAX]);
+int search_persistent_semeai_cache(enum routine_id routine,
+ int apos, int bpos, int cpos, int color,
+ Hash_data *goal_hash,
+ int *resulta, int *resultb,
+ int *move, int *certain);
+void store_persistent_semeai_cache(enum routine_id routine,
+ int apos, int bpos, int cpos, int color,
+ Hash_data *goal_hash,
+ int resulta, int resultb,
+ int move, int certain, int tactical_nodes,
+ char goala[BOARDMAX], char goalb[BOARDMAX]);
+
/* readconnect.c */
int string_connect(int str1, int str2, int *move);
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.216
diff -u -p -r1.216 owl.c
--- engine/owl.c 2 Jun 2004 02:53:26 -0000 1.216
+++ engine/owl.c 19 Aug 2004 18:29:21 -0000
@@ -351,10 +351,12 @@ owl_analyze_semeai_after_move(int move,
int dummy_semeai_move;
double start = 0.0;
int reading_nodes_when_called = get_reading_node_counter();
+ int nodes_used;
int new_dragons[BOARDMAX];
struct local_owl_data *owla;
struct local_owl_data *owlb;
+ Hash_data goal_hash;
if (!resulta)
resulta = &dummy_resulta;
@@ -362,7 +364,7 @@ owl_analyze_semeai_after_move(int move,
resultb = &dummy_resultb;
if (!semeai_move)
semeai_move = &dummy_semeai_move;
-
+
if (debug & DEBUG_OWL_PERFORMANCE)
start = gg_cputime();
@@ -397,6 +399,8 @@ owl_analyze_semeai_after_move(int move,
}
}
}
+
+
sgf_dumptree = NULL;
if (verbose > 0)
@@ -448,9 +452,9 @@ owl_analyze_semeai_after_move(int move,
ASSERT1(board[apos] == OTHER_COLOR(board[bpos]), apos);
count_variations = 1;
if (move == PASS_MOVE)
- TRACE("owl_analyze_semeai: %1m vs. %1m\n", apos, bpos);
+ DEBUG(DEBUG_SEMEAI, "owl_analyze_semeai: %1m vs. %1m\n", apos, bpos);
else
- TRACE("owl_analyze_semeai_after_move %C %1m: %1m vs. %1m\n",
+ DEBUG(DEBUG_SEMEAI, "owl_analyze_semeai_after_move %C %1m: %1m vs. %1m\n",
color, move, apos, bpos);
if (owl) {
@@ -474,6 +478,29 @@ owl_analyze_semeai_after_move(int move,
result_certain = 1;
+ {
+ Hash_data temp = goal_to_hashvalue(owla->goal);
+ goal_hash = goal_to_hashvalue(owlb->goal);
+ hashdata_xor(goal_hash, temp);
+ }
+ if (owl
+ && search_persistent_semeai_cache(ANALYZE_SEMEAI,
+ apos, bpos, move, color, &goal_hash,
+ resulta, resultb, semeai_move,
+ semeai_result_certain)) {
+ if (move == PASS_MOVE) {
+ DEBUG(DEBUG_OWL_PERFORMANCE,
+ "analyze_semeai %1m vs. %1m, result %d %d %1m (cached)\n",
+ apos, bpos, *resulta, *resultb, *semeai_move);
+ }
+ else {
+ DEBUG(DEBUG_OWL_PERFORMANCE,
+ "analyze_semeai_after_move %C %1m: %1m vs. %1m, result %d %d %1m
(cached)\n",
+ color, move, apos, bpos, *resulta, *resultb, *semeai_move);
+ }
+ return;
+ }
+
/* In some semeai situations one or both players have the option to
* choose between seki and ko for the life and death of both. In
* general this choice depends on the ko threat situation, the
@@ -504,24 +531,30 @@ owl_analyze_semeai_after_move(int move,
*resultb = REVERSE_RESULT(*resultb);
}
+ nodes_used = get_reading_node_counter() - reading_nodes_when_called;
if (move == PASS_MOVE) {
DEBUG(DEBUG_OWL_PERFORMANCE,
"analyze_semeai %1m vs. %1m, result %d %d %1m (%d, %d nodes, %f
seconds)\n",
apos, bpos, *resulta, *resultb, *semeai_move, local_owl_node_counter,
- get_reading_node_counter() - reading_nodes_when_called,
- gg_cputime() - start);
+ nodes_used, gg_cputime() - start);
}
else {
DEBUG(DEBUG_OWL_PERFORMANCE,
"analyze_semeai_after_move %C %1m: %1m vs. %1m, result %d %d %1m (%d,
%d nodes, %f seconds)\n",
color, move, apos, bpos, *resulta, *resultb, *semeai_move,
local_owl_node_counter,
- get_reading_node_counter() - reading_nodes_when_called,
- gg_cputime() - start);
+ nodes_used, gg_cputime() - start);
}
if (semeai_result_certain)
*semeai_result_certain = result_certain;
+
+ if (owl)
+ store_persistent_semeai_cache(ANALYZE_SEMEAI, apos, bpos, move, color,
+ &goal_hash,
+ *resulta, *resultb, *semeai_move,
+ result_certain, nodes_used,
+ owla->goal, owlb->goal);
}
Index: engine/persistent.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/persistent.c,v
retrieving revision 1.25
diff -u -p -r1.25 persistent.c
--- engine/persistent.c 19 Jul 2004 12:23:08 -0000 1.25
+++ engine/persistent.c 19 Aug 2004 18:29:21 -0000
@@ -74,6 +74,9 @@
#define MAX_BREAKIN_CACHE_DEPTH 1
#define MAX_BREAKIN_CACHE_SIZE 150
+#define MAX_SEMEAI_CACHE_DEPTH 0
+#define MAX_SEMEAI_CACHE_SIZE 150
+
#define MAX_CACHE_DEPTH 5
@@ -90,13 +93,15 @@ struct persistent_cache_entry {
int apos; /* first input coordinate */
int bpos; /* second input coordinate */
int cpos; /* third input coordinate */
- Hash_data goal_hash; /* hash of the goal in break-in reading */
+ int color; /* Move at (cpos) by (color) in analyze_semeai_after_move() */
+ Hash_data goal_hash; /* hash of the goals in break-in and semeai reading */
int result;
+ int result2;
int result_certain;
int remaining_depth;
int node_limit;
int move; /* first result coordinate */
- int move2; /* second result coordinate */
+ int move2;/* second result coordinate */
int cost; /* Usually no. of tactical nodes spent on this reading result. */
int score; /* Heuristic guess of the worth of the cache entry. */
};
@@ -122,6 +127,9 @@ struct persistent_cache {
static void compute_active_owl_area(struct persistent_cache_entry *entry,
const char goal[BOARDMAX],
int goal_color);
+static void compute_active_semeai_area(struct persistent_cache_entry *entry,
+ const char goal[BOARDMAX],
+ int dummy);
static void compute_active_reading_area(struct persistent_cache_entry *entry,
const char reading_shadow[BOARDMAX],
int dummy);
@@ -153,6 +161,10 @@ struct persistent_cache owl_cache =
"owl cache", compute_active_owl_area,
NULL, 0, -1 };
+struct persistent_cache semeai_cache =
+ { MAX_SEMEAI_CACHE_SIZE, MAX_SEMEAI_CACHE_DEPTH, 0.75,
+ "semeai cache", compute_active_semeai_area,
+ NULL, 0, -1 };
/* ================================================================ */
/* Common helper functions. */
@@ -245,6 +257,8 @@ print_persistent_cache_entry(struct pers
if (entry->cpos != NO_MOVE)
gprintf("%ocpos = %1m\n", entry->cpos);
gprintf("%oresult = %s\n", result_to_string(entry->result));
+ if (entry->result2 != 0)
+ gprintf("%oresult2 = %s\n", result_to_string(entry->result2));
if (entry->result_certain != -1)
gprintf("%oresult_certain = %d\n", entry->result_certain);
if (entry->node_limit != -1)
@@ -362,7 +376,8 @@ purge_persistent_cache(struct persistent
static struct persistent_cache_entry *
find_persistent_cache_entry(struct persistent_cache *cache,
enum routine_id routine, int apos, int bpos,
- int cpos, Hash_data *goal_hash, int node_limit)
+ int cpos, int color,
+ Hash_data *goal_hash, int node_limit)
{
int k;
for (k = 0; k < cache->current_size; k++) {
@@ -371,6 +386,7 @@ find_persistent_cache_entry(struct persi
&& entry->apos == apos
&& entry->bpos == bpos
&& entry->cpos == cpos
+ && entry->color == color
&& depth - stackp <= entry->remaining_depth
&& (entry->node_limit >= node_limit || entry->result_certain)
&& (goal_hash == NULL
@@ -388,18 +404,22 @@ find_persistent_cache_entry(struct persi
static int
search_persistent_cache(struct persistent_cache *cache,
enum routine_id routine, int apos, int bpos,
- int cpos, Hash_data *goal_hash, int node_limit,
- int *result, int *move, int *move2, int *certain)
+ int cpos, int color,
+ Hash_data *goal_hash, int node_limit,
+ int *result, int *result2, int *move, int *move2,
+ int *certain)
{
/* Try to find entry. */
struct persistent_cache_entry *entry;
- entry = find_persistent_cache_entry(cache, routine, apos, bpos, cpos,
+ entry = find_persistent_cache_entry(cache, routine, apos, bpos, cpos, color,
goal_hash, node_limit);
if (entry == NULL)
return 0;
/* Set return values. */
*result = entry->result;
+ if (result2)
+ *result2 = entry->result2;
if (move)
*move = entry->move;
if (move2)
@@ -414,6 +434,7 @@ search_persistent_cache(struct persisten
gprintf("%oRetrieved position from %s:\n", cache->name);
print_persistent_cache_entry(entry);
}
+ /* FIXME: This is an ugly hack. */
if (cache->name == "reading cache"
&& (debug & DEBUG_READING_PERFORMANCE)
&& entry->cost >= MIN_READING_NODES_TO_REPORT) {
@@ -439,8 +460,9 @@ search_persistent_cache(struct persisten
static void
store_persistent_cache(struct persistent_cache *cache,
enum routine_id routine,
- int apos, int bpos, int cpos, Hash_data *goal_hash,
- int result, int move, int move2,
+ int apos, int bpos, int cpos, int color,
+ Hash_data *goal_hash,
+ int result, int result2, int move, int move2,
int certain, int node_limit,
int cost, const char goal[BOARDMAX], int goal_color)
{
@@ -479,9 +501,11 @@ store_persistent_cache(struct persistent
entry->apos = apos;
entry->bpos = bpos;
entry->cpos = cpos;
+ entry->color = color;
if (goal_hash)
entry->goal_hash = *goal_hash;
entry->result = result;
+ entry->result2 = result2;
entry->result_certain = certain;
entry->node_limit = node_limit;
entry->remaining_depth = depth - stackp;
@@ -535,6 +559,7 @@ persistent_cache_init()
init_cache(&breakin_cache);
init_cache(&connection_cache);
init_cache(&owl_cache);
+ init_cache(&semeai_cache);
}
@@ -546,6 +571,7 @@ clear_persistent_caches()
connection_cache.current_size = 0;
breakin_cache.current_size = 0;
owl_cache.current_size = 0;
+ semeai_cache.current_size = 0;
}
/* Discards all persistent cache entries that are no longer useful.
@@ -559,13 +585,13 @@ purge_persistent_caches()
purge_persistent_cache(&connection_cache);
purge_persistent_cache(&breakin_cache);
purge_persistent_cache(&owl_cache);
+ purge_persistent_cache(&semeai_cache);
}
/* ================================================================ */
/* Tactical reading functions */
/* ================================================================ */
-
/* Look for a valid read result in the persistent cache.
* Return 1 if found, 0 otherwise.
*/
@@ -574,8 +600,8 @@ search_persistent_reading_cache(enum rou
int *result, int *move)
{
return search_persistent_cache(&reading_cache,
- routine, str, NO_MOVE, NO_MOVE, NULL,
- -1, result, move, NULL, NULL);
+ routine, str, NO_MOVE, NO_MOVE, EMPTY, NULL,
+ -1, result, NULL, move, NULL, NULL);
}
@@ -585,8 +611,8 @@ store_persistent_reading_cache(enum rout
int result, int move, int nodes)
{
store_persistent_cache(&reading_cache, routine,
- str, NO_MOVE, NO_MOVE, NULL,
- result, move, NO_MOVE, -1, -1,
+ str, NO_MOVE, NO_MOVE, EMPTY, NULL,
+ result, NO_MOVE, move, NO_MOVE, -1, -1,
nodes, shadow, EMPTY);
}
@@ -783,9 +809,9 @@ search_persistent_connection_cache(enum
int str2, int *result, int *move)
{
return search_persistent_cache(&connection_cache, routine,
- str1, str2, NO_MOVE, NULL,
+ str1, str2, NO_MOVE, EMPTY, NULL,
connection_node_limit,
- result, move, NULL, NULL);
+ result, NULL, move, NULL, NULL);
}
/* Store a new connection result in the persistent cache. */
@@ -795,8 +821,10 @@ store_persistent_connection_cache(enum r
int result, int move, int tactical_nodes,
char connection_shadow[BOARDMAX])
{
- store_persistent_cache(&connection_cache, routine, str1, str2, NO_MOVE, NULL,
- result, move, NO_MOVE, -1, connection_node_limit,
+ store_persistent_cache(&connection_cache, routine,
+ str1, str2, NO_MOVE, EMPTY, NULL,
+ result, NO_MOVE, move, NO_MOVE, -1,
+ connection_node_limit,
tactical_nodes, connection_shadow, EMPTY);
}
@@ -930,8 +958,8 @@ search_persistent_breakin_cache(enum rou
int node_limit, int *result, int *move)
{
return search_persistent_cache(&breakin_cache, routine,
- str, NO_MOVE, NO_MOVE, goal_hash,
- node_limit, result, move, NULL, NULL);
+ str, NO_MOVE, NO_MOVE, EMPTY, goal_hash,
+ node_limit, result, NULL, move, NULL, NULL);
}
/* Store a new breakin result in the persistent cache. */
@@ -943,8 +971,8 @@ store_persistent_breakin_cache(enum rout
char breakin_shadow[BOARDMAX])
{
store_persistent_cache(&breakin_cache, routine,
- str, NO_MOVE, NO_MOVE, goal_hash,
- result, move, NO_MOVE, -1, breakin_node_limit,
+ str, NO_MOVE, NO_MOVE, EMPTY, goal_hash,
+ result, NO_MOVE, move, NO_MOVE, -1, breakin_node_limit,
tactical_nodes, breakin_shadow, EMPTY);
}
@@ -1070,9 +1098,9 @@ search_persistent_owl_cache(enum routine
int *result, int *move, int *move2, int *certain)
{
return search_persistent_cache(&owl_cache,
- routine, apos, bpos, cpos, NULL,
+ routine, apos, bpos, cpos, EMPTY, NULL,
owl_node_limit,
- result, move, move2, certain);
+ result, NULL, move, move2, certain);
}
@@ -1083,20 +1111,25 @@ store_persistent_owl_cache(enum routine_
int tactical_nodes,
char goal[BOARDMAX], int goal_color)
{
- store_persistent_cache(&owl_cache, routine, apos, bpos, cpos, NULL,
- result, move, move2, certain, owl_node_limit,
+ store_persistent_cache(&owl_cache, routine, apos, bpos, cpos, EMPTY, NULL,
+ result, NO_MOVE, move, move2, certain, owl_node_limit,
tactical_nodes, goal, goal_color);
}
-static void compute_active_owl_area(struct persistent_cache_entry *entry,
- const char goal[BOARDMAX],
- int goal_color)
+/* This function is used by owl and semai active area computation. We assume
+ * that (goal) marks a dragon of color (goal_color), i.e. all intersections
+ * in the goal that are not a stone of this color are ignored. The calling
+ * functions must have zeroed the active area, and is allowed to preset
+ * some intersection to be active.
+ */
+static void
+compute_active_owl_type_area(const char goal[BOARDMAX], int goal_color,
+ signed char active[BOARDMAX])
{
int k, r;
int pos;
int other = OTHER_COLOR(goal_color);
- signed char active[BOARDMAX];
/* We let the active area be the goal +
* distance four expansion through empty intersections and own stones +
@@ -1108,14 +1141,8 @@ static void compute_active_owl_area(stru
*/
for (pos = BOARDMIN; pos < BOARDMAX; pos++)
if (ON_BOARD(pos))
- active[pos] = (goal[pos] != 0);
-
- /* Also add critical moves to the active area. */
- if (ON_BOARD1(entry->move))
- active[entry->move] = 1;
-
- if (ON_BOARD1(entry->move2))
- active[entry->move2] = 1;
+ active[pos] |= (goal[pos]
+ && board[pos] == goal_color);
/* Distance four expansion through empty intersections and own stones. */
for (k = 1; k < 5; k++) {
@@ -1180,7 +1207,25 @@ static void compute_active_owl_area(stru
}
}
}
-
+}
+
+static void
+compute_active_owl_area(struct persistent_cache_entry *entry,
+ const char goal[BOARDMAX], int goal_color)
+{
+ int pos;
+ signed char active[BOARDMAX];
+ memset(active, 0, BOARDMAX);
+
+ /* Add critical moves to the active area. */
+ if (ON_BOARD1(entry->move))
+ active[entry->move] = 1;
+
+ if (ON_BOARD1(entry->move2))
+ active[entry->move2] = 1;
+
+ compute_active_owl_type_area(goal, goal_color, active);
+
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
int value = board[pos];
if (!ON_BOARD(pos))
@@ -1195,6 +1240,88 @@ static void compute_active_owl_area(stru
}
+/* ================================================================ */
+/* Semeai reading functions */
+/* ================================================================ */
+
+/* Look for stored result in semeai cache. Returns 1 if result found, 0
+ * otherwise.
+ */
+int
+search_persistent_semeai_cache(enum routine_id routine,
+ int apos, int bpos, int cpos, int color,
+ Hash_data *goal_hash,
+ int *resulta, int *resultb,
+ int *move, int *certain)
+{
+ return search_persistent_cache(&semeai_cache, routine, apos, bpos, cpos,
+ color, goal_hash, semeai_node_limit,
+ resulta, resultb, move, NULL, certain);
+}
+
+
+/* Store a new read result in the persistent semeai cache. */
+void
+store_persistent_semeai_cache(enum routine_id routine,
+ int apos, int bpos, int cpos, int color,
+ Hash_data *goal_hash,
+ int resulta, int resultb, int move, int certain,
+ int tactical_nodes,
+ char goala[BOARDMAX], char goalb[BOARDMAX])
+{
+ char goal[BOARDMAX];
+ int pos;
+
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+ goal[pos] = goala[pos] || goalb[pos];
+ store_persistent_cache(&semeai_cache, routine,
+ apos, bpos, cpos, color, goal_hash,
+ resulta, resultb, move, NO_MOVE,
+ certain, semeai_node_limit,
+ tactical_nodes, goal, EMPTY);
+}
+
+
+static void
+compute_active_semeai_area(struct persistent_cache_entry *entry,
+ const char goal[BOARDMAX], int dummy)
+{
+ int pos;
+ signed char active_b[BOARDMAX];
+ signed char active_w[BOARDMAX];
+ UNUSED(dummy);
+ memset(active_b, 0, BOARDMAX);
+ memset(active_w, 0, BOARDMAX);
+
+ /* Add critical move to the active area. */
+ if (ON_BOARD1(entry->move)) {
+ active_b[entry->move] = 1;
+ active_w[entry->move] = 1;
+ }
+ if (ON_BOARD1(entry->cpos)) {
+ active_b[entry->cpos] = 1;
+ active_w[entry->cpos] = 1;
+ }
+
+ compute_active_owl_type_area(goal, BLACK, active_b);
+ compute_active_owl_type_area(goal, WHITE, active_b);
+
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+ int value = board[pos];
+ if (!ON_BOARD(pos))
+ continue;
+ if (!active_b[pos] && !active_w[pos])
+ value = GRAY;
+ else if (IS_STONE(board[pos]) && countlib(pos) > 4
+ && (active_b[pos] > 0 || active_w[pos] > 0))
+ value |= HIGH_LIBERTY_BIT;
+
+ entry->board[pos] = value;
+ }
+}
+
+
+
/* Helper for the owl_hotspots() function below. */
static void
mark_dragon_hotspot_values(float values[BOARDMAX], int dr,
- [gnugo-devel] persistent semeai caching,
Arend Bayer <=