[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] Patch: Caching for owl reading
|
From: |
Inge Wallin |
|
Subject: |
[gnugo-devel] Patch: Caching for owl reading |
|
Date: |
Wed, 21 Jan 2004 22:23:32 +0100 |
|
User-agent: |
KMail/1.4.3 |
Ok, here is the final version of new style caching for owl reading. It seems
to work, although I haven't yet taken the time to run all the regressions and
time it compared to the old implementation.
Arend wrote:
> This patch converts the break-in code to use Inge's new cache. It will
> conflict slightly with Inge's owl patch, as I had to change the prototyp
> of tt_get, too (adding the additional hash value to identify the goal).
> But it should be trivial to merge.
>
> No regression changes (*), almost no node count change.
This doesn't surprise me in the least (the no node count change). You see,
Arend, that what you did was to search in the cache for reading results with
a special hash value for the goal. But you never stored it so there was
nothing to find. In fact, it surprises me that you didn't get more nodes.
Perhaps break-in reading doesn't gain much by caching.
I have now prepared tt_update for such store, but I think it is better if you
do the actual changes for this yourself. I think the risk is less that way.
Summary:
- use new cache for owl reading
- prepare tt_update() for storing break_in reading nodes
-Inge
Index: engine/cache.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v
retrieving revision 1.34
diff -u -r1.34 cache.c
--- engine/cache.c 21 Jan 2004 18:39:10 -0000 1.34
+++ engine/cache.c 21 Jan 2004 21:13:04 -0000
@@ -176,15 +176,15 @@
tt_get(Transposition_table *table,
int komaster, int kom_pos, enum routine_id routine, int target,
int remaining_depth,
- int *result, int *move, Hash_data *extra_hash)
+ Hash_data *extra_hash,
+ int *value1, int *value2, int *move)
{
Hash_data hashval;
Hashentry_ng *entry;
Hashnode_ng *node;
/* Get the combined hash value. */
- calculate_hashval_for_tt(komaster, kom_pos, routine, target,
- &hashval);
+ calculate_hashval_for_tt(komaster, kom_pos, routine, target, &hashval);
if (extra_hash)
hashdata_xor(hashval, *extra_hash);
@@ -210,8 +210,10 @@
if (move)
*move = hn_get_move(*node);
if ((unsigned) remaining_depth <= hn_get_remaining_depth(*node)) {
- if (result)
- *result = hn_get_result1(*node);
+ if (value1)
+ *value1 = hn_get_value1(*node);
+ if (value2)
+ *value2 = hn_get_value2(*node);
return 2;
}
@@ -225,7 +227,9 @@
void
tt_update(Transposition_table *table,
int komaster, int kom_pos, enum routine_id routine, int target,
- int remaining_depth, int result, int move)
+ int remaining_depth,
+ Hash_data *extra_hash,
+ int value1, int value2, int move)
{
Hash_data hashval;
Hashentry_ng *entry;
@@ -235,7 +239,16 @@
/* Get the combined hash value. */
calculate_hashval_for_tt(komaster, kom_pos, routine, target, &hashval);
- data = hn_create_data(remaining_depth, result, 0, move, 0);
+ if (extra_hash)
+ hashdata_xor(hashval, *extra_hash);
+
+ /* Sanity check. */
+ if (remaining_depth < 0)
+ remaining_depth = 0;
+ if (remaining_depth > HN_MAX_REMAINING_DEPTH)
+ remaining_depth = HN_MAX_REMAINING_DEPTH;
+
+ data = hn_create_data(remaining_depth, value1, value2, move, 0);
/* Get the entry and nodes. */
entry = &table->entries[hashdata_remainder(hashval, table->num_entries)];
Index: engine/cache.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.h,v
retrieving revision 1.39
diff -u -r1.39 cache.h
--- engine/cache.h 21 Jan 2004 18:39:10 -0000 1.39
+++ engine/cache.h 21 Jan 2004 21:13:04 -0000
@@ -51,8 +51,8 @@
*
* RESERVED : 5 bits
* remaining_depth: 5 bits (depth - stackp) NOTE: HN_MAX_REMAINING_DEPTH
- * result1 : 4 bits
- * result2 : 4 bits
+ * value1 : 4 bits
+ * value2 : 4 bits
* move : 10 bits
* flags : 4 bits
*/
@@ -73,15 +73,15 @@
/* Hn is for hash node. */
#define hn_get_remaining_depth(hn) (((hn).data >> 22) & 0x1f)
-#define hn_get_result1(hn) (((hn).data >> 18) & 0x0f)
-#define hn_get_result2(hn) (((hn).data >> 14) & 0x0f)
+#define hn_get_value1(hn) (((hn).data >> 18) & 0x0f)
+#define hn_get_value2(hn) (((hn).data >> 14) & 0x0f)
#define hn_get_move(hn) (((hn).data >> 4) & 0x3ff)
#define hn_get_flags(hn) (((hn).data >> 0) & 0x0f)
-#define hn_create_data(remaining_depth, result1, result2, move, flags) \
+#define hn_create_data(remaining_depth, value1, value2, move, flags) \
(((remaining_depth & 0x1f) << 22) \
- | (((result1) & 0x0f) << 18) \
- | (((result2) & 0x0f) << 14) \
+ | (((value1) & 0x0f) << 18) \
+ | (((value2) & 0x0f) << 14) \
| (((move) & 0x3ff) << 4) \
| (((flags) & 0x0f) << 0))
@@ -101,12 +101,13 @@
int tt_get(Transposition_table *table,
int komaster, int kom_pos, enum routine_id routine,
int target, int remaining_depth,
- int *result, int *move,
- Hash_data *extra_hash);
+ Hash_data *extra_hash,
+ int *value1, int *value2, int *move);
void tt_update(Transposition_table *table,
int komaster, int kom_pos, enum routine_id routine,
int target, int remaining_depth,
- int result, int move);
+ Hash_data *extra_hash,
+ int value1, int value2, int move);
/* ================================================================ */
@@ -357,16 +358,28 @@
#define READ_RETURN0_NG(komaster, kom_pos, routine, str, remaining_depth) \
do { \
- tt_update(&ttable, komaster, kom_pos, routine, str, remaining_depth, 0,
0);\
+ tt_update(&ttable, komaster, kom_pos, routine, str, remaining_depth,
NULL,\
+ 0, 0, NO_MOVE);\
return 0; \
} while (0)
#define READ_RETURN_NG(komaster, kom_pos, routine, str, remaining_depth,
point, move, value) \
do { \
- tt_update(&ttable, komaster, kom_pos, routine, str, remaining_depth,
value, move);\
+ tt_update(&ttable, komaster, kom_pos, routine, str, remaining_depth,
NULL,\
+ value, 0, move);\
if ((value) != 0 && (point) != 0) *(point) = (move); \
return (value); \
} while (0)
+
+#define READ_RETURN2_NG(komaster, kom_pos, routine, str, remaining_depth,
point, move, value1, value2) \
+ do { \
+ tt_update(&ttable, komaster, kom_pos, routine, str, remaining_depth,
NULL,\
+ value1, value2, move);\
+ if ((value1) != 0 && (point) != 0) *(point) = (move); \
+ return (value1); \
+ } while (0)
+
+/* ---------------- */
#define READ_RETURN0(read_result) \
do { \
Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.103
diff -u -r1.103 gnugo.h
--- engine/gnugo.h 7 Sep 2003 23:02:45 -0000 1.103
+++ engine/gnugo.h 21 Jan 2004 21:13:04 -0000
@@ -194,6 +194,9 @@
* Regarding HASH_DEFAULT:
* Hashing all functions saves time, but wastes table space, which is
* bad when the reading is complicated. HASH_DEFAULT is a compromise.
+ *
+ * FIXME: This is no longer true with the newer transposition table
+ * and its fancy replacement scheme. We can now hash everything.
*/
#define HASH_FIND_DEFENSE 0x0001 /* NOTE : can specify -d0x... */
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.190
diff -u -r1.190 owl.c
--- engine/owl.c 21 Jan 2004 12:45:04 -0000 1.190
+++ engine/owl.c 21 Jan 2004 21:13:04 -0000
@@ -59,7 +59,8 @@
#define MAX_SEMEAI_MOVES 6 /* semeai branch factor */
#define MAX_SEMEAI_DEPTH 100 /* Don't read below this depth */
#define MAX_LUNCHES 10
-#define MAX_GOAL_WORMS 15 /* maximum number of worms in a dragon to be
cataloged */
+#define MAX_GOAL_WORMS 15 /* maximum number of worms in a dragon to be */
+ /* cataloged. NOTE: Must fit in value2 in
hashnode! */
#define MAX_ESCAPE 3 /* After this many escape moves, owl_determine_life is
*/
/* not called
*/
@@ -1601,15 +1602,58 @@
struct eyevalue probable_eyes; /* Best guess of eyevalue. */
const char *live_reason;
int move_cutoff;
+#if USE_HASHTABLE_NG
+ int xpos;
+ int value1;
+ int value2;
+#else
Read_result *read_result = NULL;
+ int found_read_result;
+#endif
int this_variation_number = count_variations - 1;
SETUP_TRACE_INFO("owl_attack", str);
shape_patterns.initialized = 0;
+#if USE_HASHTABLE_NG
+
+ if ((stackp <= owl_branch_depth) && (hashflags & HASH_OWL_ATTACK)
+ && tt_get(&ttable, komaster, kom_pos, OWL_ATTACK, str,
+ depth - stackp, NULL,
+ &value1, &value2, &xpos) == 2) {
+
+ /* TRACE_CACHED_RESULT(*read_result);*/
+ if (value1 != 0) {
+ if (move)
+ *move = xpos;
+ }
+ if (value1 == GAIN) {
+ if (wormid) {
+ if (goal_worms_computed)
+ *wormid = value2;
+ else
+ *wormid = MAX_GOAL_WORMS;
+ }
+ }
+
+ if (value1 == WIN)
+ TRACE("%oVariation %d: DEAD (cached)\n", this_variation_number);
+ else
+ TRACE("%oVariation %d: ALIVE (cached)\n", this_variation_number);
+
+ SGFTRACE(xpos, value1, "cached");
+
+ return value1;
+ }
+
+
+#else
+
if ((stackp <= owl_branch_depth) && (hashflags & HASH_OWL_ATTACK)) {
- if (get_read_result(OWL_ATTACK, komaster, kom_pos, &str, &read_result)) {
+ found_read_result = get_read_result(OWL_ATTACK, komaster, kom_pos,
+ &str, &read_result);
+ if (found_read_result) {
TRACE_CACHED_RESULT(*read_result);
if (rr_get_result(*read_result) != 0) {
if (move)
@@ -1635,11 +1679,18 @@
}
}
+#endif
+
/* If reading goes to deep or we run out of nodes, we assume life. */
if (reading_limit_reached(&live_reason, this_variation_number)) {
SGFTRACE(0, 0, live_reason);
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp,
+ move, 0, 0);
+#else
READ_RETURN(read_result, move, 0, 0);
+#endif
}
memset(mw, 0, sizeof(mw));
@@ -1681,11 +1732,21 @@
SGFTRACE(0, acode, live_reason);
TRACE("%oVariation %d: ALIVE (%s)\n", this_variation_number,
live_reason);
if (acode == 0)
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp,
+ move, 0, 0);
+#else
READ_RETURN(read_result, move, 0, 0);
+#endif
else {
if (wormid)
*wormid = saveworm;
+#if USE_HASHTABLE_NG
+ READ_RETURN2_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp,
+ move, mpos, acode, saveworm);
+#else
READ_RETURN2(read_result, move, mpos, acode, saveworm);
+#endif
}
}
@@ -1775,7 +1836,12 @@
this_variation_number);
SGFTRACE(0, WIN, "no defense");
close_pattern_list(other, &shape_patterns);
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp,
+ move, 0, WIN);
+#else
READ_RETURN(read_result, move, 0, WIN);
+#endif
}
else if (dpos != NO_MOVE) {
/* The dragon could be defended by one more move. Try to
@@ -1821,7 +1887,11 @@
TRACE("%oVariation %d: ALIVE (escaped)\n", this_variation_number);
SGFTRACE(0, 0, "escaped");
close_pattern_list(other, &shape_patterns);
+#if USE_HASHTABLE_NG
+ READ_RETURN0_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp)
+#else
READ_RETURN0(read_result);
+#endif
}
#endif
@@ -1931,7 +2001,12 @@
SGFTRACE(mpos, WIN, winstr);
}
close_pattern_list(other, &shape_patterns);
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp,
+ move, mpos, WIN);
+#else
READ_RETURN(read_result, move, mpos, WIN);
+#endif
}
else if (experimental_owl_ext && dcode == LOSS) {
if (saveworm == MAX_GOAL_WORMS
@@ -2010,11 +2085,21 @@
SGFTRACE(savemove, savecode, "attack effective (gain) - E");
if (wormid)
*wormid = saveworm;
+#if USE_HASHTABLE_NG
+ READ_RETURN2_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp,
+ move, savemove, savecode, saveworm);
+#else
READ_RETURN2(read_result, move, savemove, savecode, saveworm);
+#endif
}
else {
SGFTRACE(savemove, savecode, "attack effective (ko) - E");
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp,
+ move, savemove, savecode);
+#else
READ_RETURN(read_result, move, savemove, savecode);
+#endif
}
}
@@ -2024,7 +2109,11 @@
count_variations - this_variation_number);
SGFTRACE(0, 0, winstr);
}
+#if USE_HASHTABLE_NG
+ READ_RETURN0_NG(komaster, kom_pos, OWL_ATTACK, str, depth - stackp);
+#else
READ_RETURN0(read_result);
+#endif
}
@@ -2241,15 +2330,58 @@
int escape_route;
const char *live_reason;
int move_cutoff;
+# if USE_HASHTABLE_NG
+ int xpos;
+ int value1;
+ int value2;
+#else
Read_result *read_result = NULL;
+ int found_read_result;
+#endif
int this_variation_number = count_variations - 1;
SETUP_TRACE_INFO("owl_defend", str);
shape_patterns.initialized = 0;
+#if USE_HASHTABLE_NG
+
+ if ((stackp <= owl_branch_depth) && (hashflags & HASH_OWL_DEFEND)
+ && tt_get(&ttable, komaster, kom_pos, OWL_DEFEND, str,
+ depth - stackp, NULL,
+ &value1, &value2, &xpos) == 2) {
+
+ /* TRACE_CACHED_RESULT(*read_result);*/
+
+ if (value1 != 0) {
+ if (move)
+ *move = xpos;
+ }
+ if (value1 == LOSS) {
+ if (wormid) {
+ if (goal_worms_computed)
+ *wormid = value2;
+ else
+ *wormid = MAX_GOAL_WORMS;
+ }
+ }
+
+ if (value1 == WIN || value1 == LOSS)
+ TRACE("%oVariation %d: ALIVE (cached)\n", this_variation_number);
+ else
+ TRACE("%oVariation %d: DEAD (cached)\n", this_variation_number);
+
+ SGFTRACE(xpos, value1, "cached");
+
+ return value1;
+ }
+
+#else
+
if ((stackp <= owl_branch_depth) && (hashflags & HASH_OWL_DEFEND)) {
- if (get_read_result(OWL_DEFEND, komaster, kom_pos, &str, &read_result)) {
+ found_read_result = get_read_result(OWL_DEFEND, komaster, kom_pos,
+ &str, &read_result);
+ if (found_read_result) {
TRACE_CACHED_RESULT(*read_result);
if (rr_get_result(*read_result) != 0) {
if (move)
@@ -2276,6 +2408,8 @@
}
}
+#endif
+
/* In order to get a defense move even if we seem to already have
* escaped and to reduce the impact of overestimated escape
* possibilities, we don't declare escape victory on the first move.
@@ -2291,13 +2425,23 @@
*/
TRACE("%oVariation %d: ALIVE (escaped)\n", this_variation_number);
SGFTRACE(0, WIN, "escaped");
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_DEFEND, str, depth - stackp,
+ move, 0, WIN);
+#else
READ_RETURN(read_result, move, 0, WIN);
+#endif
}
/* If reading goes to deep or we run out of nodes, we assume life. */
if (reading_limit_reached(&live_reason, this_variation_number)) {
SGFTRACE(0, WIN, live_reason);
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_DEFEND, str, depth - stackp,
+ move, 0, WIN);
+#else
READ_RETURN(read_result, move, 0, WIN);
+#endif
}
memset(mw, 0, sizeof(mw));
@@ -2314,7 +2458,12 @@
SGFTRACE(0, WIN, live_reason);
TRACE("%oVariation %d: ALIVE (%s)\n",
this_variation_number, live_reason);
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_DEFEND, str, depth - stackp,
+ move, 0, WIN);
+#else
READ_RETURN(read_result, move, 0, WIN);
+#endif
}
}
else {
@@ -2493,7 +2642,12 @@
SGFTRACE(mpos, WIN, winstr);
}
close_pattern_list(color, &shape_patterns);
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_DEFEND, str, depth - stackp,
+ move, mpos, WIN);
+#else
READ_RETURN(read_result, move, mpos, WIN);
+#endif
}
if (acode == GAIN)
saveworm = wid;
@@ -2520,17 +2674,32 @@
SGFTRACE(savemove, savecode, "defense effective (loss) - B");
if (wormid)
*wormid = saveworm;
+#if USE_HASHTABLE_NG
+ READ_RETURN2_NG(komaster, kom_pos, OWL_DEFEND, str, depth - stackp,
+ move, savemove, savecode, saveworm);
+#else
READ_RETURN2(read_result, move, savemove, savecode, saveworm);
+#endif
}
else {
SGFTRACE(savemove, savecode, "defense effective (ko) - B");
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_DEFEND, str, depth - stackp,
+ move, savemove, savecode);
+#else
READ_RETURN(read_result, move, savemove, savecode);
+#endif
}
}
if (number_tried_moves == 0 && min_eyes(&probable_eyes) >= 2) {
SGFTRACE(0, WIN, "genus probably >= 2");
+#if USE_HASHTABLE_NG
+ READ_RETURN_NG(komaster, kom_pos, OWL_DEFEND, str, depth - stackp,
+ move, 0, WIN);
+#else
READ_RETURN(read_result, move, 0, WIN);
+#endif
}
@@ -2542,7 +2711,11 @@
SGFTRACE(0, 0, winstr);
}
+#if USE_HASHTABLE_NG
+ READ_RETURN0_NG(komaster, kom_pos, OWL_DEFEND, str, depth - stackp);
+#else
READ_RETURN0(read_result);
+#endif
}
Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.64
diff -u -r1.64 readconnect.c
--- engine/readconnect.c 21 Jan 2004 18:39:11 -0000 1.64
+++ engine/readconnect.c 21 Jan 2004 21:13:05 -0000
@@ -2750,7 +2750,8 @@
&& (hashflags & HASH_BREAK_IN)
&& !has_passed
&& tt_get(&ttable, komaster, kom_pos, BREAK_IN, str,
- depth - stackp, &retval, &xpos, goal_hash) == 2) {
+ depth - stackp, goal_hash,
+ &retval, NULL, &xpos) == 2) {
/* FIXME: Use move for move ordering if tt_get() returned 1 */
SGFTRACE(xpos, retval, "cached");
if (move)
Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.135
diff -u -r1.135 reading.c
--- engine/reading.c 21 Jan 2004 18:39:11 -0000 1.135
+++ engine/reading.c 21 Jan 2004 21:13:05 -0000
@@ -1224,8 +1224,8 @@
if ((stackp <= depth) && (hashflags & HASH_FIND_DEFENSE)
&& tt_get(&ttable, komaster, kom_pos, FIND_DEFENSE, str,
- depth - stackp,
- &retval, &xpos, NULL) == 2) {
+ depth - stackp, NULL,
+ &retval, NULL, &xpos) == 2) {
/* Note that if return value is 1 (too small depth), the move will
* still be used for move ordering.
*/
@@ -3026,8 +3026,8 @@
*/
if ((stackp <= depth) && (hashflags & HASH_ATTACK)
&& tt_get(&ttable, komaster, kom_pos, ATTACK, str,
- depth - stackp,
- &retval, &xpos, NULL) == 2) {
+ depth - stackp, NULL,
+ &retval, NULL, &xpos) == 2) {
SGFTRACE(xpos, retval, "cached");
if (move)
*move = xpos;
- [gnugo-devel] Patch: Caching for owl reading,
Inge Wallin <=