1
/* This file is a part of gtkboard, a board games system.
2
Copyright (C) 2003, Arvind Narayanan <arvindn@users.sourceforge.net>
4
This program is free software; you can redistribute it and/or modify
5
it under the terms of the GNU General Public License as published by
6
the Free Software Foundation; either version 2 of the License, or
7
(at your option) any later version.
9
This program is distributed in the hope that it will be useful,
10
but WITHOUT ANY WARRANTY; without even the implied warranty of
11
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
GNU General Public License for more details.
14
You should have received a copy of the GNU General Public License
15
along with this program; if not, write to the Free Software
16
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111 USA
28
\brief hash table which implements transposition tables.
30
A hash entry stores the following information:
32
depth to which it has been explored
33
verification code (secondary hash value)
35
if there is a collision and the table is less than (say) 75% full, search
36
sequentially till an empty cell is found
37
otherwise just kick out the previous entry
38
(if depth of the current entry is smaller than the earlier entry, search
39
sequentially till a shallower node is found and kick it out)
41
When used with DFID, if l levels were completed on the previous move, l-2
42
levels (ply) will be completed almost instantly on this move. Even if we are
43
unable to complete level l on this move, it mattereth not, for the
44
partial information will be there in the hash table and will be useful
56
// FIXME: write a function called debug or something instead of doing it this way
57
extern int opt_verbose;
59
/* TODO: use a secondary hash fn of 16 bits to use as increment in case
60
of collision. Also use it for 16 of the 48 bits of the check field */
62
/* TODO: hash the state also. games like chess will need it */
66
guint32 check; /* should this be 32 or 64 ? */
67
/* hmm.. maybe 48: that would fit nicely into 3 words */
76
static int hash_table_size = 1 << 16;
77
static int hash_table_max = 3 * 1 << 14;
78
static int num_hash_coeffts = 1024;
79
static uint *hash_coeffts = NULL;
80
static hash_t *hash_table = NULL;
81
static int hash_filled = 0;
82
static int hash_eval_hits = 0, hash_eval_misses = 0;
83
static int hash_move_hits = 0, hash_move_misses = 0;
85
static void hash_init ()
86
/* malloc the stuff */
87
// FIXME: Do we need to free this?
90
if (hash_coeffts) return;
91
hash_coeffts = (uint *) malloc (num_hash_coeffts * sizeof (uint));
92
assert (hash_coeffts);
93
for (i=0; i<num_hash_coeffts; i++)
94
hash_coeffts[i] = (random() << 1u) + 1;
95
hash_table = (hash_t *) malloc (hash_table_size * sizeof (hash_t));
97
for (i=0; i<hash_table_size; i++)
98
hash_table[i].free = 1;
101
static uint get_hash (byte *pos, int poslen)
107
for (i = 0; i < poslen; i++)
108
hash += (pos[i] * hash_coeffts[i%num_hash_coeffts]);
112
static uint get_check (byte *pos, int poslen)
113
/* just another hash function */
119
for (i=0; i < poslen; i++)
120
check += (pos[i] * hash_coeffts
121
[num_hash_coeffts-1-(i%num_hash_coeffts)]);
125
// FIXME: hash should work with state as well
126
void hash_insert (byte *pos, int poslen, int num_moves, int depth, float eval,
129
uint start = get_hash (pos, poslen) % hash_table_size;
130
uint check = get_check (pos, poslen);
132
for (idx=start; cnt <= 10; idx = (idx+1) % hash_table_size, cnt++)
134
if (hash_table[idx].free)
136
if (hash_filled >= hash_table_max)
141
if (hash_table[idx].stale)
143
/* even if the same position is already there it should be
144
overwritten with the new depth */
145
if (hash_table[idx].check == check)
147
if (hash_filled >= hash_table_max && depth > hash_table[idx].depth)
150
if (hash_table[idx].free == 0 && hash_table[idx].best_move)
151
free (hash_table[idx].best_move);
152
hash_table[idx].free = 0;
153
hash_table[idx].check = check;
154
hash_table[idx].num_moves = num_moves;
155
hash_table[idx].eval = eval;
156
hash_table[idx].depth = depth;
157
hash_table[idx].stale = 0;
158
hash_table[idx].best_move = (move ? movdup (move) : NULL);
161
int hash_get_eval (byte *pos, int poslen, int num_moves, int depth, float *evalp)
162
/* get the eval of a pos if it is there in the hash table
163
retval = was it found
166
uint idx = get_hash (pos, poslen) % hash_table_size;
167
uint check = get_check (pos, poslen);
168
for (; hash_table[idx].free == 0; idx = (idx+1) % hash_table_size)
170
if (hash_table[idx].check == check) /* found it */
172
/* don't compare 2 evals at different depths*/
173
if (hash_table[idx].depth == depth
174
&& hash_table[idx].num_moves == num_moves)
177
*evalp = hash_table[idx].eval;
178
hash_table[idx].stale = 0;
185
/* found a free slot before encountering this pos */
190
byte * hash_get_move (byte *pos, int poslen, int num_moves)
192
uint idx = get_hash (pos, poslen) % hash_table_size;
193
uint check = get_check (pos, poslen);
194
for (; hash_table[idx].free == 0; idx = (idx+1) % hash_table_size)
196
if (hash_table[idx].check == check) /* found it */
198
if (hash_table[idx].num_moves == num_moves)
200
hash_table[idx].stale = 0;
202
return hash_table[idx].best_move;
207
/* found a free slot before encountering this pos */
215
for (i=0; i<hash_table_size; i++)
217
if (hash_table[i].free == 0 && hash_table[i].best_move)
218
free (hash_table[i].best_move);
219
hash_table[i].free = 1;
224
void hash_print_stats ()
227
if (opt_verbose) printf ("hashtable: size=%d \tfilled=%d \teval_hits=%d \teval_misses=%d \tmove_hits=%d \tmove_misses=%d \t",
228
hash_table_size, hash_filled,
229
hash_eval_hits, hash_eval_misses, hash_move_hits, hash_move_misses);
230
hash_eval_hits = hash_eval_misses = hash_move_hits = hash_move_misses = 0;
231
for (i=0; i<hash_table_size; i++)
233
if (!hash_table[i].free && hash_table[i].stale)
235
hash_table[i].stale = 1;
237
if (opt_verbose) printf ("stale=%d\n", stale);
added
removed
.pc/debian-changes-0.11pre0+cvs.2003.11.02-1/src/hash.c
