1 /* this contains all the code the the hash tables (transposition tables)
2
3 The transposition table has 2 levels. The first level is replaced if the new entry
4 has a higher priority than the old entry. The 2nd level is a "always replace" level
5 where entries are placed if they are of lower priority than the first level.
6 */
7 #include "includes.h"
8 #include "knightcap.h"
9
10 int hash_hits, hash_misses, hash_shallow;
11 static int bad_updates, good_updates;
12 static unsigned hash_tag=0;
13 extern int mulling;
14
15 extern struct state *state;
16
17 #if APLINUX
18 static unsigned num_cells;
19 static unsigned cell;
20 #endif
21
22 #define PAR_HASH_LEVEL -1
23
24 struct hash_entry *hash_table;
25 unsigned hash_table_size;
26
27 static int initialised;
28
hts()29 unsigned hts()
30 {
31 return hash_table_size;
32 }
33
hash_reset_stats(void)34 void hash_reset_stats(void)
35 {
36 hash_misses = hash_hits = hash_shallow = 0;
37 bad_updates = good_updates = 0;
38 }
39
hash_reset(void)40 void hash_reset(void)
41 {
42 if (!initialised) return;
43
44 if (!hash_table) {
45 init_hash_table();
46 return;
47 }
48
49 memset(hash_table, 0,
50 sizeof(hash_table[0])*hash_table_size);
51 lprintf(0,"reset hash table\n");
52 if (state->move_time > 1)
53 brain_fill_hash(NULL);
54 }
55
56
init_hash_table(void)57 void init_hash_table(void)
58 {
59 int size;
60
61 if (initialised) return;
62 initialised = 1;
63
64 hash_reset_stats();
65
66 do {
67 hash_table_size = (state->hash_table_size * 1024*1024) /
68 sizeof(hash_table[0]);
69
70 #if HASH_LEVELS
71 hash_table_size &= ~(HASH_LEVELS - 1);
72 #endif
73
74 size = hash_table_size*sizeof(hash_table[0]);
75
76 hash_table = (struct hash_entry *)malloc(size);
77
78 if (!hash_table) {
79 state->hash_table_size--;
80 }
81 } while (!hash_table);
82
83 printf("hash table size %d MB %d entries\n",
84 state->hash_table_size, hash_table_size);
85
86 if (!mulling) {
87 hash_reset();
88 order_reset();
89 }
90 #if APLINUX
91 num_cells = getncel();
92 cell = getcid();
93 #endif
94 }
95
get_index(Position * b)96 static inline unsigned get_index(Position *b)
97 {
98 unsigned ret;
99 ret = b->hash1 % hash_table_size;
100 #if HASH_LEVELS
101 ret &= ~(HASH_LEVELS - 1);
102 #endif
103 return ret;
104 }
105
check_hash(Position * b,int depth,Eval testv,Eval * v,Move * move)106 int check_hash(Position *b,
107 int depth, Eval testv, Eval *v, Move *move)
108 {
109 struct hash_entry *t;
110 uint32 hashindex = get_index(b);
111
112 t = &hash_table[hashindex];
113
114 #if APLINUX
115 if (depth > PAR_HASH_LEVEL) {
116 int get_flag = 0;
117 int cid = (b->hash1 >> HASH_TABLE_BITS) % num_cells;
118 get(cid, &b->h_entry, sizeof(*t), t, &get_flag, NULL);
119 amcheck(&get_flag, 1);
120 } else {
121 b->h_entry = (*t);
122 }
123 t = &b->h_entry;
124 #endif
125
126 #if HASH_LEVELS
127 {
128 int j;
129 for (j=0;j<HASH_LEVELS;j++, t++)
130 if (t->hash2 == b->hash2 &&
131 t->hash1 == b->hash1) break;
132 if (j == HASH_LEVELS) {
133 if (depth)
134 hash_misses++;
135 return HASH_MISS;
136 }
137 }
138 #else
139 if (t->hash2 != b->hash2 ||
140 t->hash1 != b->hash1) {
141 if (depth)
142 hash_misses++;
143 return HASH_MISS;
144 }
145 #endif
146
147 if (move) {
148 /* even if we get a hash miss we return the move
149 if we have one - it might be a good guess */
150 move->from = t->from;
151 move->to = t->to;
152 }
153
154 if (t->depth_high >= depth && t->high.v < testv.v) {
155 if (depth)
156 hash_hits++;
157 (*v) = t->high;
158 return HASH_HIT;
159 }
160
161 if (t->depth_low >= depth && t->low.v >= testv.v) {
162 if (depth)
163 hash_hits++;
164 (*v) = t->low;
165 return HASH_HIT;
166 }
167 if (depth)
168 hash_shallow++;
169 return HASH_MISS;
170 }
171
172
fetch_hash(Position * b)173 struct hash_entry *fetch_hash(Position *b)
174 {
175 struct hash_entry *t;
176 uint32 hashindex;
177
178 init_hash_table();
179
180 hashindex = get_index(b);
181 t = &hash_table[hashindex];
182
183 #if HASH_LEVELS
184 {
185 int j;
186 for (j=0;j<HASH_LEVELS;j++, t++)
187 if (t->hash2 == b->hash2 &&
188 t->hash1 == b->hash1) break;
189 if (j == HASH_LEVELS) {
190 return NULL;
191 }
192 }
193 #else
194 if (t->hash2 != b->hash2 ||
195 t->hash1 != b->hash1) {
196 return 0;
197 }
198 #endif
199
200 return t;
201 }
202
maxdepth(struct hash_entry * t)203 static inline int maxdepth(struct hash_entry *t)
204 {
205 return imax(t->depth_low, t->depth_high);
206 }
207
insert_hash(Position * b,int depth,Eval testv,Eval evaluation,Move * move)208 void insert_hash(Position *b, int depth, Eval testv, Eval evaluation, Move *move)
209 {
210 int depth0;
211 struct hash_entry *t;
212 uint32 hashindex = get_index(b);
213 int lower = (evaluation.v >= testv.v); /* is this a new lower bound? */
214 #if APLINUX
215 struct hash_entry *t1;
216 int cid;
217 #endif
218
219 t = &hash_table[hashindex];
220
221 #if APLINUX
222 t1 = t;
223
224 t = &b->h_entry;
225 #endif
226
227 if (t[0].move_num || t[1].move_num) {
228 if (t[0].hash1 != b->hash1)
229 return;
230 else {
231 lprintf(0, "overwriting hash entry: %d %d %d/%d depth=%d/%d %08x by: %08x depth=%d\n",
232 t[0].move_num, t[1].move_num, t[0].low.v, t[0].high.v,
233 t[0].depth_low, t[0].depth_high, t[0].hash1, b->hash1, depth);
234 }
235 }
236
237 /* see if it matches either entry */
238 if (t[0].hash1 == b->hash1 && t[0].hash2 == b->hash2) {
239 /* we match the deep entry, don't need to do anything */
240 } else if (t[1].hash1 == b->hash1 && t[1].hash2 == b->hash2) {
241 /* we match the "always" entry. This might refresh the
242 hash tag on the always entry, so check if the always
243 and deep entries need swapping */
244 if (maxdepth(&t[1]) >= maxdepth(&t[0])) {
245 struct hash_entry tmp;
246 tmp = t[0];
247 t[0] = t[1];
248 t[1] = tmp;
249 } else {
250 /* they don't need swapping, just use the
251 "always" entry */
252 t++;
253 }
254 } else if (t[0].tag == hash_tag && maxdepth(&t[0]) > depth) {
255 /* the deep entry is deeper than the new entry. Use
256 the always entry unless this is a quiesce entry
257 and the always entry isn't */
258 if (depth == 0 && maxdepth(&t[1]) > 0 && t[1].tag == hash_tag)
259 return;
260 /* put it in the "always replace" slot */
261 t++;
262 } else {
263 /* replace the deep entry, and move the deep entry to the
264 "always" slot */
265 t[1] = t[0];
266 }
267
268 t->tag = hash_tag;
269
270 if (t->hash2 != b->hash2 || t->hash1 != b->hash1) {
271 t->depth_low = 0;
272 t->depth_high = 0;
273 t->low = makeeval(b, -INFINITY);
274 t->high = makeeval(b, INFINITY);
275 t->hash1 = b->hash1;
276 t->hash2 = b->hash2;
277 t->from = t->to = A1;
278 } else {
279 #if SAVE_EXTENSIONS
280 if (depth > 2 && depth >= (lower?t->depth_low+1:t->depth_high+1)) {
281 ddprintf(0, "%s %d %d %d %d %d %d %d\n",
282 position_to_ppn(b),
283 t->depth_low, t->depth_high,
284 t->low.v, t->high.v,
285 lower?evaluation.v:t->low.v,
286 lower?t->high.v:evaluation.v,
287 depth);
288 }
289 #endif
290 if (depth < (lower?t->depth_low:t->depth_high))
291 bad_updates++;
292 else if ((lower?t->depth_low:t->depth_high) > 0)
293 good_updates++;
294
295 }
296
297 if (lower) {
298 if (move) {
299 t->from = move->from;
300 t->to = move->to;
301 }
302 depth0 = t->depth_low;
303 t->depth_low = depth;
304 t->low = evaluation;
305 if (t->high.v < t->low.v) {
306 if (depth0 == depth && t->depth_high == depth) {
307 t->high = t->low;
308 } else {
309 t->high = makeeval(b, INFINITY);
310 t->depth_high = 0;
311 }
312 }
313 } else {
314 depth0 = t->depth_high;
315 t->depth_high = depth;
316 t->high = evaluation;
317 if (t->high.v < t->low.v) {
318 if (depth0 == depth && t->depth_low == depth) {
319 t->low = t->high;
320 } else {
321 t->low = makeeval(b, -INFINITY);
322 t->depth_low = 0;
323 }
324 }
325 }
326
327 #if APLINUX
328 if (depth > PAR_HASH_LEVEL) {
329 cid = (b->hash1 >> HASH_TABLE_BITS) % num_cells;
330 put(cid, t, sizeof(*t), t1, NULL, NULL, 0);
331 } else {
332 (*t1) = (*t);
333 }
334 #endif
335 }
336
hash_change_tag(int move_num)337 void hash_change_tag(int move_num)
338 {
339 static int last_move_num;
340 if (move_num < last_move_num) {
341 hash_reset();
342 }
343
344 last_move_num = move_num;
345
346 hash_tag = (hash_tag % 15) + 1;
347 }
348
hashstats(void)349 char *hashstats(void)
350 {
351 static char ret[30];
352 sprintf(ret, "h/s/b=%d/%d/%d%%",
353 (100*hash_hits)/(hash_misses+hash_hits+hash_shallow+1),
354 (100*hash_shallow)/(hash_misses+hash_hits+hash_shallow+1),
355 (100*bad_updates)/(good_updates+bad_updates+1));
356 return ret;
357 }
358
359
360
check_hash2(Position * b,int depth,Eval testv,Eval * v)361 int check_hash2(Position *b, int depth, Eval testv, Eval *v)
362 {
363 struct hash_entry *t;
364 uint32 hashindex = get_index(b);
365
366 t = &hash_table[hashindex];
367
368 #if HASH_LEVELS
369 {
370 int j;
371 for (j=0;j<HASH_LEVELS;j++, t++)
372 if (t->hash2 == b->hash2 &&
373 t->hash1 == b->hash1) break;
374 if (j == HASH_LEVELS) {
375 return 0;
376 }
377 }
378 #else
379 if (t->hash2 != b->hash2 ||
380 t->hash1 != b->hash1) {
381 return 0;
382 }
383 #endif
384
385 if (t->depth_high >= depth && t->high.v < testv.v) {
386 if (depth)
387 hash_hits++;
388 (*v) = t->high;
389 return 1;
390 }
391
392 if (depth)
393 hash_shallow++;
394 return 0;
395 }
396
ettc_check_hash(Position * b,Move * moves,int num_moves,int depth,Eval testv,Eval * v,Move * m1)397 int ettc_check_hash(Position *b, Move *moves, int num_moves,
398 int depth, Eval testv, Eval *v, Move *m1)
399 {
400 int m;
401 uint32 hash1, hash2;
402 Eval v1;
403 int cutoff = 0;
404
405 hash1 = b->hash1;
406 hash2 = b->hash2;
407
408 testv = flip(testv);
409
410 depth--;
411
412 for (m=0;m<num_moves;m++) {
413 remove_hash(b, moves[m].from, b->board[moves[m].from]);
414 if (b->board[moves[m].to]) {
415 remove_hash(b, moves[m].to, b->board[moves[m].to]);
416 }
417 add_hash(b, moves[m].to, b->board[moves[m].from]);
418 b->hash1 ^= 1;
419
420 if (check_hash2(b, depth, testv, &v1)) {
421 /* now confirm it */
422 Position b1;
423
424 b->hash1 = hash1;
425 b->hash2 = hash2;
426
427 if (!do_move(&b1, b, &moves[m])) continue;
428 if (check_repitition(&b1, 1)) continue;
429
430 if (check_hash2(&b1, depth, testv, &v1)) {
431 if (!cutoff || (-v1.v) > v->v) {
432 cutoff = 1;
433 (*v) = v1;
434 v->v = -v->v;
435 if (m1)
436 (*m1) = moves[m];
437 }
438 }
439 } else {
440 b->hash1 = hash1;
441 b->hash2 = hash2;
442 }
443 }
444
445 return cutoff;
446 }
447
448
449 /* return >0 if this move could produce a hash hit, <0 if it can't
450 and =0 if we can't tell */
hash_ordering(Position * b,Move * move,Eval testv)451 int hash_ordering(Position *b, Move *move, Eval testv)
452 {
453 uint32 hash1, hash2, hashindex;
454 struct hash_entry *t;
455
456 hash1 = b->hash1;
457 hash2 = b->hash2;
458
459 testv = flip(testv);
460
461 remove_hash(b, move->from, b->board[move->from]);
462 if (b->board[move->to]) {
463 remove_hash(b, move->to, b->board[move->to]);
464 }
465 add_hash(b, move->to, b->board[move->from]);
466 b->hash1 ^= 1;
467
468
469 hashindex = get_index(b);
470 t = &hash_table[hashindex];
471
472 #if HASH_LEVELS
473 {
474 int j;
475 for (j=0;j<HASH_LEVELS;j++, t++)
476 if (t->hash2 == b->hash2 &&
477 t->hash1 == b->hash1) break;
478 if (j == HASH_LEVELS) {
479 b->hash1 = hash1;
480 b->hash2 = hash2;
481 return 0;
482 }
483 }
484 #else
485 if (t->hash2 != b->hash2 ||
486 t->hash1 != b->hash1) {
487 b->hash1 = hash1;
488 b->hash2 = hash2;
489 return 0;
490 }
491 #endif
492
493 b->hash1 = hash1;
494 b->hash2 = hash2;
495
496 if (t->low.v >= testv.v) {
497 return -(1+((t->low.v - testv.v) / (STATIC_PAWN_VALUE/2)));
498 }
499
500 if (t->high.v < testv.v) {
501 return 1+((testv.v - t->high.v) / (STATIC_PAWN_VALUE/2));
502 }
503
504 return 0;
505 }
506