[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] caching for break-in reading
From: |
Arend Bayer |
Subject: |
[gnugo-devel] caching for break-in reading |
Date: |
Tue, 3 Jun 2003 18:13:28 +0200 (CEST) |
- new helper functions goal_to_hashvalue(), xor_hashvalues()
- new function get_read_result_hash_modified to enable calling functions
to use a modified hash value
- results for recursive_break() and recursive_block() now get cached
The tricky part is that the fields str1 and str2 in the read result do
not suffice to store the goal[] array. However, as the likelyhood of
hash collisions is extremely small for these functions (as they are by some
magnitudes less frequent than do_attack etc.), I decided to store this
information in the hash value instead. So at the beginning, the goal[]
array gets assigned a hash value, and this is persistenly used throughout
the search tree to modify the hash value (with an xor).
In principle, this machinery could also be used by owl to store the goal,
etc.
Arend
Index: engine/cache.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v
retrieving revision 1.23
diff -u -p -r1.23 cache.c
--- engine/cache.c 22 Apr 2003 02:48:04 -0000 1.23
+++ engine/cache.c 3 Jun 2003 16:09:07 -0000
@@ -56,7 +56,8 @@ static void hashnode_unlink_closed_resul
int statistics[][20]);
static void hashtable_partially_clear(Hashtable *table);
static int do_get_read_result(int routine, int komaster, int kom_pos,
- int str1, int str2, Read_result **read_result);
+ int str1, int str2, Read_result **read_result,
+ Hash_data *hashmodifier);
/*
@@ -662,6 +663,27 @@ reading_cache_clear()
hashtable_clear(movehash);
}
+int
+get_read_result_hash_modified(int routine, int komaster, int kom_pos,
+ int *str, Hash_data *hashmodifier,
+ Read_result **read_result)
+{
+ /* Only store the result if stackp <= depth. Above that, there
+ * is no branching, so we won't gain anything.
+ */
+ if (stackp > depth) {
+ *read_result = NULL;
+ return 0;
+ }
+
+ /* Find the origin of the string in order to make the caching of read
+ * results work better.
+ */
+ *str = find_origin(*str);
+
+ return do_get_read_result(routine, komaster, kom_pos, *str, NO_MOVE,
+ read_result, hashmodifier);
+}
/*
* Return a Read_result for the current position, routine and location.
@@ -685,7 +707,7 @@ get_read_result(int routine, int komaste
*str = find_origin(*str);
return do_get_read_result(routine, komaster, kom_pos, *str, NO_MOVE,
- read_result);
+ read_result, NULL);
}
@@ -711,18 +733,20 @@ get_read_result2(int routine, int komast
*str2 = find_origin(*str2);
return do_get_read_result(routine, komaster, kom_pos, *str1, *str2,
- read_result);
+ read_result, NULL);
}
static int
do_get_read_result(int routine, int komaster, int kom_pos,
- int str1, int str2, Read_result **read_result)
+ int str1, int str2, Read_result **read_result,
+ Hash_data *hashmodifier)
{
Hashnode *node;
unsigned int data1 = rr_input_data1(routine, komaster, kom_pos,
str1, depth - stackp);
unsigned int data2 = rr_input_data2(str2);
+ Hash_data modified_hash;
#if CHECK_HASHING
Hash_data key;
@@ -737,8 +761,13 @@ do_get_read_result(int routine, int koma
#endif /* CHECK_HASHING */
+ if (hashmodifier)
+ modified_hash = xor_hashvalues(&hashdata, hashmodifier);
+ else
+ modified_hash = hashdata;
+
/* First try to look this position up in the table. */
- node = hashtable_search(movehash, &hashdata);
+ node = hashtable_search(movehash, &modified_hash);
if (node != NULL) {
Read_result *result;
@@ -758,10 +787,10 @@ do_get_read_result(int routine, int koma
routine, str1, str2);
}
else {
- node = hashtable_enter_position(movehash, &hashdata);
+ node = hashtable_enter_position(movehash, &modified_hash);
if (node) {
DEBUG(DEBUG_READING_CACHE, "Created position %H in the hash table...\n",
- (unsigned long) hashdata.hashval);
+ (unsigned long) modified_hash.hashval);
}
else {
DEBUG(DEBUG_READING_CACHE, "Unable to clean up the hash table!\n");
Index: engine/cache.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.h,v
retrieving revision 1.28
diff -u -p -r1.28 cache.h
--- engine/cache.h 22 Apr 2003 02:48:04 -0000 1.28
+++ engine/cache.h 3 Jun 2003 16:09:08 -0000
@@ -255,6 +255,9 @@ void sgf_trace_semeai(const char *func,
int get_read_result(int routine, int komaster, int kom_pos,
int *str, Read_result **read_result);
+int get_read_result_hash_modified(int routine, int komaster, int kom_pos,
+ int *str, Hash_data *hash_modifier,
+ Read_result **read_result);
int get_read_result2(int routine, int komaster, int kom_pos,
int *str1, int *str2, Read_result **read_result);
@@ -388,7 +391,10 @@ int get_read_result2(int routine, int ko
#define CONNECT 5
#define DISCONNECT 6
-#define MAX_ROUTINE DISCONNECT
+#define BREAK_IN 7
+#define BLOCK_OFF 8
+
+#define MAX_ROUTINE BLOCK_OFF
#define NUM_ROUTINES (MAX_ROUTINE + 1)
Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.95
diff -u -p -r1.95 gnugo.h
--- engine/gnugo.h 2 Jun 2003 23:49:47 -0000 1.95
+++ engine/gnugo.h 3 Jun 2003 16:09:09 -0000
@@ -255,11 +255,14 @@ extern int output_flags; /* amount
#define HASH_SEMEAI 0x0400
#define HASH_CONNECT 0x0800
#define HASH_DISCONNECT 0x1000
+#define HASH_BREAK_IN 0x2000
+#define HASH_BLOCK_OFF 0x4000
#define HASH_NOTHING 0
#define HASH_ALL 0xffff
#define HASH_DEFAULT (HASH_ATTACK | HASH_FIND_DEFENSE\
| HASH_OWL_ATTACK | HASH_OWL_DEFEND | HASH_SEMEAI\
- | HASH_CONNECT | HASH_DISCONNECT)
+ | HASH_CONNECT | HASH_DISCONNECT\
+ | HASH_BREAK_IN | HASH_BLOCK_OFF)
extern int debug; /* debug flags */
extern int hashflags; /* hash flags */
Index: engine/hash.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.c,v
retrieving revision 1.14
diff -u -p -r1.14 hash.c
--- engine/hash.c 2 Jan 2003 00:23:28 -0000 1.14
+++ engine/hash.c 3 Jun 2003 16:09:09 -0000
@@ -383,7 +383,7 @@ hashdata_compare(Hash_data *hd1, Hash_da
for (i = 0; i < NUM_HASHVALUES; i++)
if (hd1->hashval[i] != hd2->hashval[i])
rc = 2;
- if ( rc == 2 && i > 0)
+ if (rc == 2 && i > 0)
stats.hash_collisions++;
#if FULL_POSITION_IN_HASH
@@ -392,6 +392,38 @@ hashdata_compare(Hash_data *hd1, Hash_da
#endif
return rc;
+}
+
+/* Compute hash value to identify the goal area. */
+Hash_data
+goal_to_hashvalue(char *goal)
+{
+ int i, pos;
+ Hash_data return_value;
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ return_value.hashval[i] = 0;
+ for (pos = BOARDMIN; pos < BOARDMAX; pos++)
+ if (ON_BOARD(pos) && goal[pos])
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ return_value.hashval[i] += white_hash[pos][i] + black_hash[pos][i];
+ return return_value;
+}
+
+/* Returns an XOR of the two hash values. The full board position is copied
+ * over from hash1 if FULL_POSITION_IN_HASH is set.
+ */
+Hash_data
+xor_hashvalues(Hash_data *hash1, Hash_data *hash2)
+{
+ int i;
+ Hash_data return_value;
+
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ return_value.hashval[i] = hash1->hashval[i] ^ hash2->hashval[i];
+#if FULL_POSITION_IN_HASH
+ return_value.hashpos = hash1->hashpos;
+#endif
+ return return_value;
}
Index: engine/hash.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.h,v
retrieving revision 1.9
diff -u -p -r1.9 hash.h
--- engine/hash.h 2 Jan 2003 00:23:28 -0000 1.9
+++ engine/hash.h 3 Jun 2003 16:09:09 -0000
@@ -133,6 +133,8 @@ typedef struct {
#endif
} Hash_data;
+Hash_data xor_hashvalues(Hash_data *key1, Hash_data *key2);
+Hash_data goal_to_hashvalue(char *goal);
void hash_init(void);
#if FULL_POSITION_IN_HASH
@@ -147,6 +149,7 @@ void hashdata_invert_stone(Hash_data *hd
void hashdata_set_tomove(Hash_data *hd, int to_move);
int hashdata_diff_dump(Hash_data *key1, Hash_data *key2);
+
#endif
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.176
diff -u -p -r1.176 liberty.h
--- engine/liberty.h 2 Jun 2003 23:49:47 -0000 1.176
+++ engine/liberty.h 3 Jun 2003 16:09:11 -0000
@@ -40,7 +40,7 @@
/* ================================================================ */
-/* A few variables below are of types defined in hash.h. */
+/* We need the defintion of type Hash_data here. */
#include "hash.h"
/* Other modules get read-only access to this variable. */
Index: engine/printutils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/printutils.c,v
retrieving revision 1.36
diff -u -p -r1.36 printutils.c
--- engine/printutils.c 27 May 2003 08:48:24 -0000 1.36
+++ engine/printutils.c 3 Jun 2003 16:09:11 -0000
@@ -419,6 +419,10 @@ routine_to_string(int routine)
return "CONNECT";
else if (routine == DISCONNECT)
return "DISCONNECT";
+ else if (routine == BREAK_IN)
+ return "BREAK_IN";
+ else if (routine == BLOCK_OFF)
+ return "BLOCK_OFF";
else
return "ERROR";
}
Index: engine/readconnect.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/readconnect.c,v
retrieving revision 1.49
diff -u -p -r1.49 readconnect.c
--- engine/readconnect.c 2 Jun 2003 23:49:48 -0000 1.49
+++ engine/readconnect.c 3 Jun 2003 16:09:14 -0000
@@ -48,9 +48,11 @@ static int recursive_connect2(int str1,
static int recursive_disconnect2(int str1, int str2, int *move,
int komaster, int kom_pos, int has_passed);
static int recursive_break(int str, char goal[BOARDMAX], int *move,
- int komaster, int kom_pos, int has_passed);
+ int komaster, int kom_pos, int has_passed,
+ Hash_data *goal_hash);
static int recursive_block(int str, char goal[BOARDMAX], int *move,
- int komaster, int kom_pos, int has_passed);
+ int komaster, int kom_pos, int has_passed,
+ Hash_data *goal_hash);
static int add_array(int *array, int elt);
static int element_array(int *array,int elt);
@@ -2632,13 +2634,14 @@ find_break_moves(int str, char goal[BOAR
/* These depth values are set relative to the standard readconnnect depth
* limits at each call of break_in()/block_off().
* */
-int break_in_node_limit;
-int break_in_depth;
+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, char goal[BOARDMAX], int *move,
- int komaster, int kom_pos, int has_passed)
+ int komaster, int kom_pos, int has_passed,
+ Hash_data *goal_hash)
{
int color = board[str];
int moves[MAX_MOVES];
@@ -2648,9 +2651,7 @@ recursive_break(int str, char goal[BOARD
int xpos;
int savemove = NO_MOVE;
int savecode = 0;
-#if 0
int found_read_result;
-#endif
Read_result *read_result = NULL;
SETUP_TRACE_INFO("recursive_break", str);
@@ -2676,24 +2677,23 @@ recursive_break(int str, char goal[BOARD
return 0;
}
-#if 0
if (stackp <= depth
- && (hashflags & HASH_CONNECT)
+ && (hashflags & HASH_BREAK_IN)
&& !has_passed) {
- found_read_result = get_read_result2(CONNECT, komaster, kom_pos,
- &str1, &str2, &read_result);
+ found_read_result
+ = get_read_result_hash_modified(BREAK_IN, komaster, kom_pos,
+ &str, goal_hash, &read_result);
if (found_read_result) {
- TRACE_CACHED_RESULT2(*read_result);
+ TRACE_CACHED_RESULT(*read_result);
if (rr_get_result(*read_result) != 0)
if (move)
*move = rr_get_move(*read_result);
- SGFTRACE2(rr_get_move(*read_result),
- rr_get_result(*read_result), "cached");
+ SGFTRACE(rr_get_move(*read_result),
+ rr_get_result(*read_result), "cached");
return rr_get_result(*read_result);
}
}
-#endif
#if 0
if (trivial_connection(str1, str2, &xpos) == WIN) {
@@ -2717,7 +2717,7 @@ recursive_break(int str, char goal[BOARD
if (!ko_move) {
int acode = recursive_block(str, goal, NULL,
new_komaster, new_kom_pos,
- has_passed);
+ has_passed, goal_hash);
popgo();
if (acode == 0) {
SGFTRACE(xpos, WIN, "break effective");
@@ -2730,7 +2730,7 @@ recursive_break(int str, char goal[BOARD
}
else {
if (recursive_block(str, goal, NULL, new_komaster, new_kom_pos,
- has_passed) != WIN) {
+ has_passed, goal_hash) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -2757,7 +2757,8 @@ recursive_break(int str, char goal[BOARD
/* Can (str) connect to goal[] if the other color moves first? */
static int
recursive_block(int str, char goal[BOARDMAX], int *move,
- int komaster, int kom_pos, int has_passed)
+ int komaster, int kom_pos, int has_passed,
+ Hash_data *goal_hash)
{
int color = board[str];
int other = OTHER_COLOR(color);
@@ -2768,9 +2769,7 @@ recursive_block(int str, char goal[BOARD
int xpos;
int savemove = NO_MOVE;
int savecode = 0;
-#if 0
int found_read_result;
-#endif
Read_result *read_result = NULL;
SETUP_TRACE_INFO("recursive_block", str);
@@ -2802,22 +2801,21 @@ recursive_block(int str, char goal[BOARD
return WIN;
}
-#if 0
- if ((stackp <= depth) && (hashflags & HASH_DISCONNECT)) {
- found_read_result = get_read_result2(DISCONNECT, komaster, kom_pos,
- &str1, &str2, &read_result);
+ if ((stackp <= depth) && (hashflags & HASH_BLOCK_OFF)) {
+ found_read_result
+ = get_read_result_hash_modified(BLOCK_OFF, komaster, kom_pos,
+ &str, goal_hash, &read_result);
if (found_read_result) {
- TRACE_CACHED_RESULT2(*read_result);
+ TRACE_CACHED_RESULT(*read_result);
if (rr_get_result(*read_result) != 0)
if (move)
*move = rr_get_move(*read_result);
- SGFTRACE2(rr_get_move(*read_result),
- rr_get_result(*read_result), "cached");
+ SGFTRACE(rr_get_move(*read_result),
+ rr_get_result(*read_result), "cached");
return rr_get_result(*read_result);
}
}
-#endif
if (ladder_capture(str, &xpos) == WIN) {
SGFTRACE(xpos, WIN, "string capturable");
@@ -2838,7 +2836,8 @@ recursive_block(int str, char goal[BOARD
&ko_move, stackp <= ko_depth && savecode == 0)) {
if (!ko_move) {
int dcode = recursive_break(str, goal, NULL,
- new_komaster, new_kom_pos, has_passed);
+ new_komaster, new_kom_pos, has_passed,
+ goal_hash);
popgo();
if (dcode == 0) {
SGFTRACE(xpos, WIN, "block effective");
@@ -2851,7 +2850,7 @@ recursive_block(int str, char goal[BOARD
}
else {
if (recursive_break(str, goal, NULL, new_komaster, new_kom_pos,
- has_passed) != WIN) {
+ has_passed, goal_hash) != WIN) {
savemove = xpos;
savecode = KO_B;
}
@@ -2863,7 +2862,8 @@ recursive_block(int str, char goal[BOARD
if (num_moves == 0
&& distance >= 1.0
&& (has_passed
- || !recursive_break(str, goal, NULL, komaster, kom_pos, 1))) {
+ || !recursive_break(str, goal, NULL, komaster, kom_pos, 1,
+ goal_hash))) {
SGFTRACE(NO_MOVE, WIN, "no move, probably disconnected");
READ_RETURN(read_result, move, NO_MOVE, WIN);
}
@@ -2884,7 +2884,7 @@ recursive_block(int str, char goal[BOARD
* not contain stones), if he gets the first move.
*/
int
-break_in(int str, char goal [BOARDMAX], int *move)
+break_in(int str, char goal[BOARDMAX], int *move)
{
int dummy_move;
int save_verbose;
@@ -2892,6 +2892,7 @@ break_in(int str, char goal [BOARDMAX],
int reading_nodes_when_called = get_reading_node_counter();
double start = 0;
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;
@@ -2911,7 +2912,7 @@ break_in(int str, char goal [BOARDMAX],
verbose--;
start = gg_cputime();
memset(connection_shadow, 0, sizeof(connection_shadow));
- result = recursive_break(str, goal, move, EMPTY, NO_MOVE, 0);
+ 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;
if (0) {
@@ -2943,6 +2944,7 @@ block_off(int str, char goal[BOARDMAX],
int reading_nodes_when_called = get_reading_node_counter();
double start = 0;
int tactical_nodes;
+ Hash_data goal_hash = goal_to_hashvalue(goal);
if (move == NULL)
move = &dummy_move;
@@ -2957,7 +2959,8 @@ block_off(int str, char goal[BOARDMAX],
verbose--;
start = gg_cputime();
memset(connection_shadow, 0, sizeof(connection_shadow));
- result = recursive_block(str, goal, move, EMPTY, NO_MOVE, 0);
+ result = recursive_block(str, goal, move, EMPTY, NO_MOVE, 0,
+ &goal_hash);
verbose = save_verbose;
tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [gnugo-devel] caching for break-in reading,
Arend Bayer <=