[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] finishing the cache transition
|
From: |
Gunnar Farnebäck |
|
Subject: |
Re: [gnugo-devel] finishing the cache transition |
|
Date: |
Wed, 26 May 2004 04:31:27 +0200 |
|
User-agent: |
EMH/1.14.1 SEMI/1.14.3 (Ushinoya) FLIM/1.14.2 (Yagi-Nishiguchi) APEL/10.3 Emacs/21.3 (sparc-sun-solaris2.9) MULE/5.0 (SAKAKI) |
I wrote:
> This patch finishes the cache transition by implementing
> TRACE_CACHED_RESULT macros and doing some preparations for removing
> the old cache implementation. The actual removal will come in a
> separate patch.
The removal has been done by the patch gunnar_5_7.7. The patch below
continues with some further cleaning of hash.[ch] and cache.[ch].
- global variable hashdata renamed to board_hash
- hashdata_compare() function removed
- fields in struct stats_data updated for new cache
- initialization of Zobrist random numbers in hash.c and cache.c
unified
- new function hash_init_zobrist_array() in hash.c
- macro hashdata_remainder() never uses more than the 32 lowest bits of
the hash value
- hashdata_NULL, hashdata_clear(), and hashdata_init() macros removed
- any number of MIN_HASHBITS can now be used
- ROUTINE_COSTS revised
The revision of hashdata_remainder() both simplifies the code and
eliminates one potential source of platform dependencies. For the use
in computing the index into the hashtable 32 random bits are of course
sufficient to get a nice and uniform distribution.
Remaining questions:
1. In goal_to_hashvalue(), is there any advantage in summing white and
black hashvalues over the goal instead of the (in my opinion) more
natural solution to add a new set of random values and xor-ing them
as usual?
2. In board.c there is a macro
#define USE_BOARD_CACHES (NUM_HASHVALUES <= 4)
which is used for some conditional code. Is there any point in
keeping this around any more?
The regression result is a FAIL in gunnar:48, which is completely
accidental. The node count changes are totally insignificant with
reductions of about 0.05%.
/Gunnar
Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.97
diff -u -r1.97 board.c
--- engine/board.c 25 May 2004 03:13:23 -0000 1.97
+++ engine/board.c 25 May 2004 23:07:29 -0000
@@ -267,13 +267,13 @@
do {\
PUSH_VERTEX(board[pos]);\
board[pos] = color;\
- hashdata_invert_stone(&hashdata, pos, color);\
+ hashdata_invert_stone(&board_hash, pos, color);\
} while (0)
#define DO_REMOVE_STONE(pos)\
do {\
PUSH_VERTEX(board[pos]);\
- hashdata_invert_stone(&hashdata, pos, board[pos]);\
+ hashdata_invert_stone(&board_hash, pos, board[pos]);\
board[pos] = EMPTY;\
} while (0)
@@ -393,7 +393,7 @@
komi = state->komi;
movenum = state->move_number;
- hashdata_recalc(&hashdata, board, board_ko_pos);
+ hashdata_recalc(&board_hash, board, board_ko_pos);
new_position();
}
@@ -432,7 +432,7 @@
move_history_pointer = 0;
movenum = 0;
- hashdata_recalc(&hashdata, board, board_ko_pos);
+ hashdata_recalc(&board_hash, board, board_ko_pos);
new_position();
}
@@ -465,7 +465,7 @@
static int stack[MAXSTACK];
static int move_color[MAXSTACK];
-static Hash_data hashdata_stack[MAXSTACK];
+static Hash_data board_hash_stack[MAXSTACK];
/*
* trymove pushes the position onto the stack, and makes a move
@@ -501,24 +501,24 @@
if (pos == NO_MOVE) {
if (komaster != EMPTY)
gg_snprintf(buf, 100, "%s (variation %d, hash %s, komaster %s:%s)",
- message, count_variations, hashdata_to_string(&hashdata),
+ message, count_variations, hashdata_to_string(&board_hash),
color_to_string(komaster), location_to_string(kom_pos));
else
- gg_snprintf(buf, 100, "%s (variation %d, hash %s)",
- message, count_variations, hashdata_to_string(&hashdata));
+ gg_snprintf(buf, 100, "%s (variation %d, hash %s)", message,
+ count_variations, hashdata_to_string(&board_hash));
}
else {
if (komaster != EMPTY)
gg_snprintf(buf, 100,
"%s at %s (variation %d, hash %s, komaster %s:%s)",
message, location_to_string(pos), count_variations,
- hashdata_to_string(&hashdata),
+ hashdata_to_string(&board_hash),
color_to_string(komaster),
location_to_string(kom_pos));
else
gg_snprintf(buf, 100, "%s at %s (variation %d, hash %s)",
message, location_to_string(str), count_variations,
- hashdata_to_string(&hashdata));
+ hashdata_to_string(&board_hash));
}
sgftreeAddPlayLast(sgf_dumptree, color, I(pos), J(pos));
sgftreeAddComment(sgf_dumptree, buf);
@@ -556,11 +556,11 @@
message = "UNKNOWN";
if (komaster != EMPTY)
gg_snprintf(buf, 100, "tryko: %s (variation %d, %s, komaster %s:%s)",
- message, count_variations, hashdata_to_string(&hashdata),
+ message, count_variations, hashdata_to_string(&board_hash),
color_to_string(komaster), location_to_string(kom_pos));
else
- gg_snprintf(buf, 100, "tryko: %s (variation %d, %s)",
- message, count_variations, hashdata_to_string(&hashdata));
+ gg_snprintf(buf, 100, "tryko: %s (variation %d, %s)", message,
+ count_variations, hashdata_to_string(&board_hash));
/* Add two pass moves to the SGF output to simulate the ko threat
* and the answer.
@@ -650,7 +650,7 @@
move_color[stackp] = color;
/*
- * FIXME: Do we really have to store hashdata in a stack?
+ * FIXME: Do we really have to store board_hash in a stack?
*
* Answer: No, we don't. But for every stone that we add
* or remove, we must call hashdata_invert_stone(). This is
@@ -664,10 +664,10 @@
*/
BEGIN_CHANGE_RECORD();
PUSH_VALUE(board_ko_pos);
- memcpy(&hashdata_stack[stackp], &hashdata, sizeof(hashdata));
+ memcpy(&board_hash_stack[stackp], &board_hash, sizeof(board_hash));
if (board_ko_pos != NO_MOVE) {
- hashdata_invert_ko(&hashdata, board_ko_pos);
+ hashdata_invert_ko(&board_hash, board_ko_pos);
}
board_ko_pos = NO_MOVE;
@@ -693,7 +693,7 @@
undo_trymove();
- memcpy(&hashdata, &(hashdata_stack[stackp]), sizeof(hashdata));
+ memcpy(&board_hash, &(board_hash_stack[stackp]), sizeof(board_hash));
if (sgf_dumptree) {
char buf[100];
@@ -720,7 +720,7 @@
{
stackp--;
undo_trymove();
- memcpy(&hashdata, &(hashdata_stack[stackp]), sizeof(hashdata));
+ memcpy(&board_hash, &(board_hash_stack[stackp]), sizeof(board_hash));
}
#endif
@@ -759,7 +759,7 @@
if (count_variations)
gprintf("%o (variation %d)", count_variations-1);
#else
- gprintf("%o (%s)", hashdata_to_string(&hashdata));
+ gprintf("%o (%s)", hashdata_to_string(&board_hash));
#endif
gprintf("%o\n");
@@ -791,7 +791,7 @@
move_history_pointer = 0;
}
-/* Place a stone on the board and update the hashdata. This operation
+/* Place a stone on the board and update the board_hash. This operation
* destroys all move history.
*/
@@ -803,13 +803,13 @@
ASSERT1(board[pos] == EMPTY, pos);
board[pos] = color;
- hashdata_invert_stone(&hashdata, pos, color);
+ hashdata_invert_stone(&board_hash, pos, color);
reset_move_history();
new_position();
}
-/* Remove a stone from the board and update the hashdata. This
+/* Remove a stone from the board and update the board_hash. This
* operation destroys the move history.
*/
@@ -820,7 +820,7 @@
ASSERT_ON_BOARD1(pos);
ASSERT1(IS_STONE(board[pos]), pos);
- hashdata_invert_stone(&hashdata, pos, board[pos]);
+ hashdata_invert_stone(&board_hash, pos, board[pos]);
board[pos] = EMPTY;
reset_move_history();
new_position();
@@ -842,11 +842,11 @@
/* Check the hash table to see if it corresponds to the cumulative one. */
hashdata_recalc(&oldkey, board, board_ko_pos);
- gg_assert(hashdata_compare(&oldkey, &hashdata) == 0);
+ gg_assert(hashdata_is_equal(oldkey, board_hash));
#endif
if (board_ko_pos != NO_MOVE)
- hashdata_invert_ko(&hashdata, board_ko_pos);
+ hashdata_invert_ko(&board_hash, board_ko_pos);
board_ko_pos = NO_MOVE;
/* If the move is a pass, we can skip some steps. */
@@ -863,7 +863,7 @@
#if CHECK_HASHING
/* Check the hash table to see if it equals the previous one. */
hashdata_recalc(&oldkey, board, board_ko_pos);
- gg_assert(hashdata_compare(&oldkey, &hashdata) == 0);
+ gg_assert(hashdata_is_equal(oldkey, board_hash));
#endif
}
@@ -1652,7 +1652,7 @@
if (!libs) {
/* First see if this result is cached. */
- if (hashdata_is_equal(hashdata, entry->position_hash)
+ if (hashdata_is_equal(board_hash, entry->position_hash)
&& maxlib <= entry->threshold) {
return entry->liberties;
}
@@ -1665,13 +1665,13 @@
*/
entry->threshold = MAXLIBS;
entry->liberties = liberties;
- entry->position_hash = hashdata;
+ entry->position_hash = board_hash;
return liberties;
}
}
- /* We initialize the cache entry threshold to `maxlib'. If do_appoxlib()
+ /* We initialize the cache entry threshold to `maxlib'. If do_approxlib()
* or slow_approxlib() finds all the liberties (that is, they don't use
* `maxlib' value for an early return), they will set threshold to
* MAXLIBS themselves.
@@ -1684,7 +1684,7 @@
liberties = slow_approxlib(pos, color, maxlib, libs);
entry->liberties = liberties;
- entry->position_hash = hashdata;
+ entry->position_hash = board_hash;
#else /* not USE_BOARD_CACHES */
@@ -1950,7 +1950,7 @@
if (!libs) {
/* First see if this result is cached. */
- if (hashdata_is_equal(hashdata, entry->position_hash)
+ if (hashdata_is_equal(board_hash, entry->position_hash)
&& maxlib <= entry->threshold) {
return entry->liberties;
}
@@ -1963,7 +1963,7 @@
*/
entry->threshold = MAXLIBS;
entry->liberties = liberties;
- entry->position_hash = hashdata;
+ entry->position_hash = board_hash;
return liberties;
}
@@ -1977,7 +1977,7 @@
*/
entry->threshold = liberties < maxlib ? MAXLIBS : maxlib;
entry->liberties = liberties;
- entry->position_hash = hashdata;
+ entry->position_hash = board_hash;
#else /* not USE_BOARD_CACHES */
@@ -3897,9 +3897,9 @@
&& captured_stones == 1) {
/* In case of a double ko: clear old ko position first. */
if (board_ko_pos != NO_MOVE)
- hashdata_invert_ko(&hashdata, board_ko_pos);
+ hashdata_invert_ko(&board_hash, board_ko_pos);
board_ko_pos = string[s].libs[0];
- hashdata_invert_ko(&hashdata, board_ko_pos);
+ hashdata_invert_ko(&board_hash, board_ko_pos);
}
}
Index: engine/board.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.h,v
retrieving revision 1.11
diff -u -r1.11 board.h
--- engine/board.h 30 Apr 2004 00:04:26 -0000 1.11
+++ engine/board.h 25 May 2004 23:07:30 -0000
@@ -361,11 +361,10 @@
/* Hashing and Caching statistics. */
struct stats_data {
int nodes; /* Number of visited nodes while reading */
- int position_entered; /* Number of Positions entered. */
- int position_hits; /* Number of hits of Positions. */
- int read_result_entered; /* Number of Read_results entered. */
- int read_result_hits; /* Number of hits of Read_results. */
- int hash_collisions; /* Number of hash collisions. */
+ int read_result_entered; /* Number of read results entered. */
+ int read_result_hits; /* Number of hits of read results. */
+ int trusted_read_result_hits; /* Number of hits of read results */
+ /* with sufficient remaining depth. */
};
extern struct stats_data stats;
Index: engine/boardlib.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/boardlib.c,v
retrieving revision 1.3
diff -u -r1.3 boardlib.c
--- engine/boardlib.c 25 May 2004 03:13:25 -0000 1.3
+++ engine/boardlib.c 25 May 2004 23:07:31 -0000
@@ -49,7 +49,7 @@
Intersection shadow[BOARDMAX];
/* Hashing of positions. */
-Hash_data hashdata;
+Hash_data board_hash;
int stackp; /* stack pointer */
int position_number; /* position number */
Index: engine/cache.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.c,v
retrieving revision 1.43
diff -u -r1.43 cache.c
--- engine/cache.c 25 May 2004 03:13:26 -0000 1.43
+++ engine/cache.c 25 May 2004 23:07:31 -0000
@@ -44,61 +44,57 @@
/* The transposition table itself. */
Transposition_table ttable;
+
+#define INIT_ARRAY(a) \
+ hash_init_zobrist_array(a, (int) (sizeof(a) / sizeof(a[0])))
+
+/* Arrays with random numbers for Zobrist hashing of input data (other
+ * than the board position). If you add an array here, do not forget
+ * to also initialize it in keyhash_init() below.
+ */
static Hash_data komaster_hash[NUM_KOMASTER_STATES];
static Hash_data kom_pos_hash[BOARDMAX];
static Hash_data target1_hash[BOARDMAX];
static Hash_data target2_hash[BOARDMAX];
static Hash_data routine_hash[NUM_CACHE_ROUTINES];
-static struct init_struct {
- Hash_data *array;
- int array_size;
-} hash_init_values[] = {
- {komaster_hash, NUM_KOMASTER_STATES},
- {kom_pos_hash, BOARDMAX},
- {target1_hash, BOARDMAX},
- {target2_hash, BOARDMAX},
- {routine_hash, NUM_CACHE_ROUTINES},
- {NULL, 0}
-};
-
-/* Initialize random hash values identifying input data (other than the
- * board position) in a cache entry.
- */
static void
keyhash_init(void)
{
static int is_initialized = 0;
- Hash_data *array;
- int size;
- int i;
- int j;
-
- if (is_initialized)
- return;
- for (i = 0; hash_init_values[i].array != NULL; i++) {
- array = hash_init_values[i].array;
- size = hash_init_values[i].array_size;
-
- for (j = 0; j < size; j++)
- hashdata_init(array[j], gg_urand(), gg_urand());
+ if (!is_initialized) {
+ struct gg_rand_state state;
+ /* Since the hash initialization consumes a varying number of random
+ * numbers depending on the size of the Hash_data struct, we save the
+ * state of the random generator now and restore it afterwards.
+ */
+ gg_get_rand_state(&state);
+
+ INIT_ARRAY(komaster_hash);
+ INIT_ARRAY(kom_pos_hash);
+ INIT_ARRAY(target1_hash);
+ INIT_ARRAY(target2_hash);
+ INIT_ARRAY(routine_hash);
+
+ gg_set_rand_state(&state);
+ is_initialized = 1;
}
-
- is_initialized = 1;
}
static void
-calculate_hashval_for_tt(int routine, int target1, int target2,
- Hash_data *hashdata2)
+calculate_hashval_for_tt(Hash_data *hashdata, int routine, int target1,
+ int target2, Hash_data *extra_hash)
{
- *hashdata2 = hashdata; /* from globals.c */
- hashdata_xor(*hashdata2, komaster_hash[get_komaster()]);
- hashdata_xor(*hashdata2, kom_pos_hash[get_kom_pos()]);
- hashdata_xor(*hashdata2, routine_hash[routine]);
- hashdata_xor(*hashdata2, target1_hash[target1]);
+ *hashdata = board_hash; /* from globals.c */
+ hashdata_xor(*hashdata, komaster_hash[get_komaster()]);
+ hashdata_xor(*hashdata, kom_pos_hash[get_kom_pos()]);
+ hashdata_xor(*hashdata, routine_hash[routine]);
+ hashdata_xor(*hashdata, target1_hash[target1]);
if (target2 != NO_MOVE)
- hashdata_xor(*hashdata2, target2_hash[target2]);
+ hashdata_xor(*hashdata, target2_hash[target2]);
+ if (extra_hash)
+ hashdata_xor(*hashdata, *extra_hash);
}
@@ -134,16 +130,10 @@
static void
tt_clear(Transposition_table *table)
{
- Hashentry hash_null = {{hashdata_NULL, 0}, {hashdata_NULL, 0}};
- unsigned int i;
-
- if (table->is_clean)
- return;
-
- for (i = 0; i < table->num_entries; i++)
- table->entries[i] = hash_null;
-
- table->is_clean = 1;
+ if (!table->is_clean) {
+ memset(table->entries, 0, table->num_entries * sizeof(table->entries[0]));
+ table->is_clean = 1;
+ }
}
@@ -174,15 +164,13 @@
Hashentry *entry;
Hashnode *node;
- /* Get the combined hash value. */
- calculate_hashval_for_tt(routine, target1, target2, &hashval);
- if (extra_hash)
- hashdata_xor(hashval, *extra_hash);
-
/* Sanity check. */
if (remaining_depth < 0 || remaining_depth > HN_MAX_REMAINING_DEPTH)
return 0;
+ /* Get the combined hash value. */
+ calculate_hashval_for_tt(&hashval, routine, target1, target2, extra_hash);
+
/* Get the correct entry and node. */
entry = &table->entries[hashdata_remainder(hashval, table->num_entries)];
if (hashdata_is_equal(hashval, entry->deepest.key))
@@ -192,7 +180,7 @@
else
return 0;
- stats.position_hits++;
+ stats.read_result_hits++;
/* Return data. Only set the result if remaining depth in the table
* is big enough to be trusted. The move can always be used for move
@@ -200,12 +188,12 @@
*/
if (move)
*move = hn_get_move(node->data);
- if ((unsigned) remaining_depth <= hn_get_remaining_depth(node->data)) {
+ if (remaining_depth <= (int) hn_get_remaining_depth(node->data)) {
if (value1)
*value1 = hn_get_value1(node->data);
if (value2)
*value2 = hn_get_value2(node->data);
- stats.read_result_hits++;
+ stats.trusted_read_result_hits++;
return 2;
}
@@ -218,9 +206,8 @@
void
tt_update(Transposition_table *table,
- enum routine_id routine, int target1, int target2,
- int remaining_depth,
- Hash_data *extra_hash,
+ enum routine_id routine, int target1, int target2,
+ int remaining_depth, Hash_data *extra_hash,
int value1, int value2, int move)
{
Hash_data hashval;
@@ -228,20 +215,17 @@
Hashnode *deepest;
Hashnode *newest;
unsigned int data;
- /* Get routine costs definitions from cache.h. */
+ /* Get routine costs definitions from liberty.h. */
static const int routine_costs[] = { ROUTINE_COSTS };
gg_assert(routine_costs[NUM_CACHE_ROUTINES] == -1);
- /* Get the combined hash value. */
- calculate_hashval_for_tt(routine, target1, target2,
- &hashval);
- if (extra_hash)
- hashdata_xor(hashval, *extra_hash);
-
/* Sanity check. */
if (remaining_depth < 0 || remaining_depth > HN_MAX_REMAINING_DEPTH)
return;
+ /* Get the combined hash value. */
+ calculate_hashval_for_tt(&hashval, routine, target1, target2, extra_hash);
+
data = hn_create_data(remaining_depth, value1, value2, move,
routine_costs[routine]);
@@ -252,14 +236,14 @@
/* See if we found an already existing node. */
if (hashdata_is_equal(hashval, deepest->key)
- && (unsigned) remaining_depth >= hn_get_remaining_depth(deepest->data)) {
+ && remaining_depth >= (int) hn_get_remaining_depth(deepest->data)) {
/* Found deepest */
deepest->data = data;
}
else if (hashdata_is_equal(hashval, newest->key)
- && (unsigned) remaining_depth >=
hn_get_remaining_depth(newest->data)) {
+ && remaining_depth >= (int) hn_get_remaining_depth(newest->data)) {
/* Found newest */
newest->data = data;
@@ -287,7 +271,7 @@
newest->data = data;
}
- stats.position_entered++;
+ stats.read_result_entered++;
table->is_clean = 0;
}
Index: engine/cache.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/cache.h,v
retrieving revision 1.50
diff -u -r1.50 cache.h
--- engine/cache.h 25 May 2004 03:13:26 -0000 1.50
+++ engine/cache.h 25 May 2004 23:07:31 -0000
@@ -42,6 +42,7 @@
* routine
* str1
* str2
+ * extra hashvalue, optional (e.g. encoding a goal array)
*
* The data field packs into 32 bits the following
* fields:
Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.91
diff -u -r1.91 genmove.c
--- engine/genmove.c 25 May 2004 03:13:29 -0000 1.91
+++ engine/genmove.c 25 May 2004 23:07:32 -0000
@@ -79,7 +79,7 @@
/* Initialize things for hashing of positions. */
reading_cache_clear();
- hashdata_recalc(&hashdata, board, board_ko_pos);
+ hashdata_recalc(&board_hash, board, board_ko_pos);
worms_examined = -1;
initial_influence_examined = -1;
Index: engine/hash.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.c,v
retrieving revision 1.26
diff -u -r1.26 hash.c
--- engine/hash.c 22 May 2004 20:21:43 -0000 1.26
+++ engine/hash.c 25 May 2004 23:07:32 -0000
@@ -44,10 +44,10 @@
static int is_initialized = 0;
-/* Random values for the hash function. For stones and ko position. */
-static Hashvalue white_hash[BOARDMAX][NUM_HASHVALUES];
-static Hashvalue black_hash[BOARDMAX][NUM_HASHVALUES];
-static Hashvalue ko_hash[BOARDMAX][NUM_HASHVALUES];
+/* Random values for the board hash function. For stones and ko position. */
+static Hash_data white_hash[BOARDMAX];
+static Hash_data black_hash[BOARDMAX];
+static Hash_data ko_hash[BOARDMAX];
/* Get a random Hashvalue, where all bits are used. */
@@ -63,36 +63,37 @@
return h;
}
+/* Fill an array with random numbers for Zobrist hashing. */
+void
+hash_init_zobrist_array(Hash_data *array, int size)
+{
+ int i, j;
+ for (i = 0; i < size; i++)
+ for (j = 0; j < NUM_HASHVALUES; j++)
+ array[i].hashval[j] = hash_rand();
+}
/*
- * Initialize the entire hash system.
+ * Initialize the board hash system.
*/
void
hash_init(void)
{
- int pos;
- int i;
struct gg_rand_state state;
if (is_initialized)
return;
/* Since the hash initialization consumes a varying number of random
- * numbers depending on the size of the Hashvalue type, we save the
+ * numbers depending on the size of the Hash_data struct, we save the
* state of the random generator now and restore it afterwards.
*/
gg_get_rand_state(&state);
-
- for (i = 0; i < NUM_HASHVALUES; i++)
- for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
- /* Note: We initialize _all_ positions, not just those on board.
- * This way we don't have to worry about changing board sizes.
- */
- black_hash[pos][i] = hash_rand();
- white_hash[pos][i] = hash_rand();
- ko_hash[pos][i] = hash_rand();
- }
+
+ hash_init_zobrist_array(black_hash, BOARDMAX);
+ hash_init_zobrist_array(white_hash, BOARDMAX);
+ hash_init_zobrist_array(ko_hash, BOARDMAX);
gg_set_rand_state(&state);
@@ -117,19 +118,14 @@
target->hashval[i] = 0;
for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
- if (board[pos] == WHITE) {
- for (i = 0; i < NUM_HASHVALUES; i++)
- target->hashval[i] ^= white_hash[pos][i];
- }
- else if (board[pos] == BLACK) {
- for (i = 0; i < NUM_HASHVALUES; i++)
- target->hashval[i] ^= black_hash[pos][i];
- }
+ if (p[pos] == WHITE)
+ hashdata_xor(*target, white_hash[pos]);
+ else if (p[pos] == BLACK)
+ hashdata_xor(*target, black_hash[pos]);
}
if (ko_pos != 0)
- for (i = 0; i < NUM_HASHVALUES; i++)
- target->hashval[i] ^= ko_hash[ko_pos][i];
+ hashdata_xor(*target, ko_hash[ko_pos]);
}
@@ -140,13 +136,10 @@
void
hashdata_invert_ko(Hash_data *hd, int pos)
{
- int i;
- for (i = 0; i < NUM_HASHVALUES; i++)
- hd->hashval[i] ^= ko_hash[pos][i];
+ hashdata_xor(*hd, ko_hash[pos]);
}
-
/*
* Set or remove a stone of COLOR at pos in a Hash_data.
*/
@@ -154,35 +147,18 @@
void
hashdata_invert_stone(Hash_data *hd, int pos, int color)
{
- int k;
-
- if (color == BLACK) {
- for (k = 0; k < NUM_HASHVALUES; k++)
- hd->hashval[k] ^= black_hash[pos][k];
- }
- else if (color == WHITE) {
- for (k = 0; k < NUM_HASHVALUES; k++)
- hd->hashval[k] ^= white_hash[pos][k];
- }
+ if (color == BLACK)
+ hashdata_xor(*hd, black_hash[pos]);
+ else if (color == WHITE)
+ hashdata_xor(*hd, white_hash[pos]);
}
-int
-hashdata_compare(Hash_data *hd1, Hash_data *hd2)
-{
- int rc = 0;
- int i;
-
- for (i = 0; i < NUM_HASHVALUES; i++)
- if (hd1->hashval[i] != hd2->hashval[i])
- rc = 2;
- if (rc == 2 && i > 0)
- stats.hash_collisions++;
-
- return rc;
-}
-
-/* Compute hash value to identify the goal area. */
+/* Compute hash value to identify the goal area.
+ *
+ * FIXME: It would be cleaner to have a separate zobrist array for the
+ * goal and xor the values in goal as usual.
+ */
Hash_data
goal_to_hashvalue(const char *goal)
{
@@ -195,7 +171,8 @@
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_value.hashval[i] += (white_hash[pos].hashval[i]
+ + black_hash[pos].hashval[i]);
return return_value;
}
@@ -217,6 +194,19 @@
return buffer;
}
+
+#if NUM_HASHVALUES > 2
+int
+hashdata_is_equal_func(Hash_data *hd1, Hash_data *hd2)
+{
+ int i;
+ for (i = 0; i < NUM_HASHVALUES; i++)
+ if (hd1->hashval[i] != hd2->hashval[i])
+ return 0;
+
+ return 1;
+}
+#endif
/*
Index: engine/hash.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/hash.h,v
retrieving revision 1.28
diff -u -r1.28 hash.h
--- engine/hash.h 22 May 2004 20:21:43 -0000 1.28
+++ engine/hash.h 25 May 2004 23:07:32 -0000
@@ -24,7 +24,6 @@
#define _HASH_H_
#include "config.h"
-#include "board.h"
#include <limits.h>
/*
@@ -79,83 +78,65 @@
Hashvalue hashval[NUM_HASHVALUES];
} Hash_data;
-extern Hash_data hashdata;
+extern Hash_data board_hash;
Hash_data goal_to_hashvalue(const char *goal);
+void hash_init_zobrist_array(Hash_data *array, int size);
void hash_init(void);
void hashdata_recalc(Hash_data *hd, Intersection *board, int ko_pos);
-int hashdata_compare(Hash_data *hd1, Hash_data *hd2);
void hashdata_invert_ko(Hash_data *hd, int pos);
void hashdata_invert_stone(Hash_data *hd, int pos, int color);
-int hashdata_diff_dump(Hash_data *key1, Hash_data *key2);
-
char *hashdata_to_string(Hash_data *hashdata);
/* ---------------------------------------------------------------- */
+/* There is no need to involve all bits in the remainder computation
+ * as long as we only use it to compute a key into a hash table. 32
+ * random bits are sufficient to get an even distribution within any
+ * hashtable of reasonable size. By never using more than 32 bits we
+ * also reduce the platform dependency of the GNU Go engine.
+*/
+#define hashdata_remainder(hd, num) \
+ (((hd).hashval[0] & 0xffffffffU) % (num))
#if NUM_HASHVALUES == 1
-#define hashdata_NULL {{0}}
-#define hashdata_clear(hd) \
- do { \
- (hd).hashval[0] = 0; \
- } while (0)
-#define hashdata_init(hd, uint1, uint2) \
- do { \
- (hd).hashval[0] = (((Hashvalue) uint1) << 32 | (uint2)); \
- } while (0)
-
#define hashdata_is_equal(hd1, hd2) \
((hd1).hashval[0] == (hd2).hashval[0])
#define hashdata_xor(hd1, hd2) \
- do { \
- (hd1).hashval[0] ^= (hd2).hashval[0]; \
- } while (0)
-
-#define hashdata_remainder(hd, num) \
- ((hd).hashval[0] % (num))
+ (hd1).hashval[0] ^= (hd2).hashval[0]
#elif NUM_HASHVALUES == 2
-#define hashdata_NULL {{0, 0}}
-#define hashdata_clear(hd) \
- do { \
- (hd).hashval[0] = 0; \
- (hd).hashval[1] = 0; \
- } while (0)
-#define hashdata_init(hd, uint1, uint2) \
- do { \
- (hd).hashval[0] = (uint1); \
- (hd).hashval[1] = (uint2); \
- } while (0)
-
#define hashdata_is_equal(hd1, hd2) \
((hd1).hashval[0] == (hd2).hashval[0] \
&& (hd1).hashval[1] == (hd2).hashval[1])
+
#define hashdata_xor(hd1, hd2) \
do { \
(hd1).hashval[0] ^= (hd2).hashval[0]; \
(hd1).hashval[1] ^= (hd2).hashval[1]; \
} while (0)
-/* This is only an approximation.
- * The real remainder can be calculated by
- * (ax+y)%z = (a%z)(x%z)+(y%z)
- * but this is good enough for use in the cache.
- */
-#define hashdata_remainder(hd, num) \
- (((hd).hashval[0] + (hd).hashval[1]) % (num))
-
#else
-#error NUM_HASHVALUES > 2 not implemented yet
+int hashdata_is_equal_func(Hash_data *hd1, Hash_data *hd2);
+
+#define hashdata_is_equal(hd1, hd2) \
+ hashdata_is_equal_func(&(hd1), &(hd2))
+
+#define hashdata_xor(hd1, hd2) \
+ do { \
+ int i; \
+ for (i = 0; i < NUM_HASHVALUES; i++) \
+ (hd1).hashval[i] ^= (hd2).hashval[i]; \
+ } while (0)
#endif
Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.216
diff -u -r1.216 liberty.h
--- engine/liberty.h 25 May 2004 03:13:33 -0000 1.216
+++ engine/liberty.h 25 May 2004 23:07:32 -0000
@@ -104,11 +104,17 @@
/* To prioritize between different types of reading, we give a cost
* ranking to each of the routines above:
- * 3 for owl, 2 for break-in, 1 for connection, 0 for tactical reading.
+ *
+ * 4 semeai
+ * 3 owl
+ * 2 break-in
+ * 1 connection
+ * 0 tactical reading
+ *
* -1 is left at the end for a consistency check.
*/
#define ROUTINE_COSTS \
- 3, 3, 3, 1, 1, 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, -1
const char *routine_id_to_string(enum routine_id routine);
Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.90
diff -u -r1.90 optics.c
--- engine/optics.c 25 May 2004 03:13:42 -0000 1.90
+++ engine/optics.c 25 May 2004 23:07:33 -0000
@@ -2558,7 +2558,7 @@
int k;
int does_capture = does_capture_something(pos, color);
- remembered_board_hashes[stackp] = hashdata;
+ remembered_board_hashes[stackp] = board_hash;
if (!trymove(pos, color, message, str))
return 0;
@@ -2567,7 +2567,7 @@
return 1;
for (k = 0; k < stackp; k++)
- if (hashdata_compare(&hashdata, &remembered_board_hashes[k]) == 0) {
+ if (hashdata_is_equal(board_hash, remembered_board_hashes[k])) {
popgo();
return 0;
}
Index: engine/utils.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/utils.c,v
retrieving revision 1.92
diff -u -r1.92 utils.c
--- engine/utils.c 25 May 2004 03:13:46 -0000 1.92
+++ engine/utils.c 25 May 2004 23:07:43 -0000
@@ -2319,23 +2319,19 @@
void
clearstats()
{
- stats.nodes = 0;
- stats.position_entered = 0;
- stats.position_hits = 0;
- stats.read_result_entered = 0;
- stats.read_result_hits = 0;
- stats.hash_collisions = 0;
+ stats.nodes = 0;
+ stats.read_result_entered = 0;
+ stats.read_result_hits = 0;
+ stats.trusted_read_result_hits = 0;
}
void
showstats()
{
- gprintf("Nodes: %d\n", stats.nodes);
- gprintf("Positions entered: %d\n", stats.position_entered);
- gprintf("Position hits: %d\n", stats.position_hits);
- gprintf("Read results entered: %d\n", stats.read_result_entered);
- gprintf("Read result hits: %d\n", stats.read_result_hits);
- gprintf("Hash collisions: %d\n", stats.hash_collisions);
+ gprintf("Nodes: %d\n", stats.nodes);
+ gprintf("Read results entered: %d\n", stats.read_result_entered);
+ gprintf("Read result hits: %d\n", stats.read_result_hits);
+ gprintf("Trusted read result hits: %d\n", stats.trusted_read_result_hits);
}
Index: interface/play_solo.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_solo.c,v
retrieving revision 1.32
diff -u -r1.32 play_solo.c
--- interface/play_solo.c 25 May 2004 03:13:49 -0000 1.32
+++ interface/play_solo.c 25 May 2004 23:07:44 -0000
@@ -102,12 +102,11 @@
movenum, i, j);
}
- totalstats.nodes += stats.nodes;
- totalstats.position_entered += stats.position_entered;
- totalstats.position_hits += stats.position_hits;
- totalstats.read_result_entered += stats.read_result_entered;
- totalstats.hash_collisions += stats.hash_collisions;
- total_owl_count += get_owl_node_counter();
+ totalstats.nodes += stats.nodes;
+ totalstats.read_result_entered += stats.read_result_entered;
+ totalstats.read_result_hits += stats.read_result_hits;
+ totalstats.trusted_read_result_hits += stats.trusted_read_result_hits;
+ total_owl_count += get_owl_node_counter();
}
t2 = gg_cputime();
@@ -120,22 +119,16 @@
}
sgffile_output(&sgftree);
-#if 0
- if (t2 == t1)
- printf("%.3f moves played\n", (double) (save_moves-moves));
- else
- printf("%.3f moves/sec\n", (save_moves-moves)/(t2-t1));
-#else
printf("%10d moves played in %0.3f seconds\n", save_moves-moves, t2-t1);
if (save_moves != moves)
printf("%10.3f seconds/move\n", (t2-t1)/(save_moves-moves));
+
printf("%10d nodes\n", totalstats.nodes);
- printf("%10d positions entered\n", totalstats.position_entered);
- printf("%10d position hits\n", totalstats.position_hits);
printf("%10d read results entered\n", totalstats.read_result_entered);
- printf("%10d hash collisions\n", totalstats.hash_collisions);
+ printf("%10d read result hits\n", totalstats.read_result_hits);
+ printf("%10d trusted read result hits\n",
+ totalstats.trusted_read_result_hits);
printf("%10d owl nodes\n", total_owl_count);
-#endif
}