-
Notifications
You must be signed in to change notification settings - Fork 2
/
hash.c
436 lines (431 loc) · 21.5 KB
/
hash.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
#include "chess.h"
#include "data.h"
/* last modified 09/16/14 */
/*
*******************************************************************************
* *
* HashProbe() is used to retrieve entries from the transposition table so *
* this sub-tree won't have to be searched again if we reach a position that *
* has been searched previously. A transposition table position contains *
* the following data packed into 128 bits with each item taking the number *
* of bits given in the table below: *
* *
* shr bits name description *
* 55 9 age search id to identify old trans/ref entries. *
* 53 2 type 0->value is worthless; 1-> value represents a *
* fail-low bound; 2-> value represents a fail-high *
* bound; 3-> value is an exact score. *
* 32 21 move best move from the current position, according to *
* the search at the time this position was stored. *
* 17 15 draft the depth of the search below this position, which *
* is used to see if we can use this entry at the *
* current position. *
* 0 17 value unsigned integer value of this position + 65536. *
* this might be a good score or search bound. *
* 0 64 key 64 bit hash signature, used to verify that this *
* entry goes with the current board position. *
* *
* The underlying scheme here is that we use a "bucket" of N entries. In *
* HashProbe() we simply compare against each of the four entries for a *
* match. Each "bucket" is carefully aligned to a 64-byte boundary so that *
* the bucket fits into a single cache line for efficiency. The bucket size *
* (N) is currently set to 4. *
* *
* Crafty uses the lockless hashing approach to avoid lock overhead in the *
* hash table accessing (reading or writing). What we do is store the key *
* and the information in two successive writes to memory. But since there *
* is nothing that prevents another CPU from interlacing its writes with *
* ours, we want to make sure that the bound/draft/etc really goes with the *
* key. Consider thread 1 trying to store A1 and A2 in two successive 64 *
* words, while thread 2 is trying to store B1 and B2. Since the two cpus *
* are fully independent, we could end up with {A1,A2}, {A1,B2}, {B1,A2} or *
* {B1,B2}. The two cases with one word of entry A and one word of entry B *
* are problematic since the information part does not belong with the *
* signature part, and a hash hit (signature match) will retrieve data that *
* does not match the position. Let's assume that the first word is the *
* signature (A1 or B1) and the second word is the data (A2 or B2). What we *
* do is store A1^A2 (exclusive-or the two parts) in the 1 (key) slot of the *
* entry, and store A2 in the data part. Now, before we try to compare the *
* signatures, we have to "un-corrupt" the stored signature by again using *
* xor, since A1^A2^A2 gives us the original A1 signature again. But if we *
* store A1^A2, and the data part gets replaced by B2, then we try to match *
* against A1^A2^B2 and that won't match unless we are lucky and A2 == B2 *
* which means the match is OK anyway. This eliminates the need to lock the *
* hash table while storing the two values, which would be a big performance *
* hit since hash entries are probed/stored in almost every node of the tree *
* except for the quiescence search. *
* *
*******************************************************************************
*/
int HashProbe(TREE * RESTRICT tree, int ply, int depth, int side, int alpha,
int beta, int *value) {
HASH_ENTRY *htable;
HPATH_ENTRY *ptable;
uint64_t word1, word2, temp_hashkey;
int type, draft, avoid_null = 0, val, entry, i;
/*
************************************************************
* *
* All we have to do is loop through four entries to see *
* if there is a signature match. There can only be one *
* instance of any single signature, so the first match is *
* all we need. *
* *
************************************************************
*/
tree->hash_move[ply] = 0;
temp_hashkey = (side) ? HashKey : ~HashKey;
htable = hash_table + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++) {
word1 = htable[entry].word1;
word2 = htable[entry].word2 ^ word1;
if (word2 == temp_hashkey)
break;
}
/*
************************************************************
* *
* If we found a match, we have to verify that the draft *
* is at least equal to the current depth, if not higher, *
* and that the bound/score will let us terminate the *
* search early. *
* *
* We also return an "avoid_null" status if the matched *
* entry does not have enough draft to terminate the *
* current search but does have enough draft to prove that *
* a null-move search would not fail high. This avoids *
* the null-move search overhead in positions where it is *
* simply a waste of time to try it. *
* *
* If this is an EXACT entry, we are going to store the PV *
* in a safe place so that if we get a hit on this entry, *
* we can recover the PV and see the complete path rather *
* rather than one that is incomplete. *
* *
* One other issue is to update the age field if we get a *
* hit on an old position, so that it won't be replaced *
* just because it came from a previous search. *
* *
************************************************************
*/
if (entry < 4) {
if (word1 >> 55 != transposition_age) {
word1 =
(word1 & 0x007fffffffffffffull) | ((uint64_t) transposition_age <<
55);
htable[entry].word1 = word1;
htable[entry].word2 = word1 ^ word2;
}
val = (word1 & 0x1ffff) - 65536;
draft = (word1 >> 17) & 0x7fff;
tree->hash_move[ply] = (word1 >> 32) & 0x1fffff;
type = (word1 >> 53) & 3;
if ((type & UPPER) &&
depth - null_depth - depth / null_divisor - 1 <= draft && val < beta)
avoid_null = AVOID_NULL_MOVE;
if (depth <= draft) {
if (val > 32000)
val -= ply - 1;
else if (val < -32000)
val += ply - 1;
*value = val;
/*
************************************************************
* *
* We have three types of results. An EXACT entry was *
* stored when val > alpha and val < beta, and represents *
* an exact score. An UPPER entry was stored when val < *
* alpha, which represents an upper bound with the score *
* likely being even lower. A LOWER entry was stored when *
* val > beta, which represents alower bound with the *
* score likely being even higher. *
* *
* For EXACT entries, we save the path from the position *
* to the terminal node that produced the backed-up score *
* so that we can complete the PV if we get a hash hit on *
* this entry. *
* *
************************************************************
*/
switch (type) {
case EXACT:
if (val > alpha && val < beta) {
SavePV(tree, ply, 1);
ptable = hash_path + (temp_hashkey & hash_path_mask);
for (entry = 0; entry < 16; entry++)
if (ptable[entry].path_sig == temp_hashkey) {
for (i = ply;
i < Min(MAXPLY - 1, ptable[entry].hash_pathl + ply); i++)
tree->pv[ply - 1].path[i] =
ptable[entry].hash_path_moves[i - ply];
if (ptable[entry].hash_pathl + ply < MAXPLY - 1)
tree->pv[ply - 1].pathh = 0;
tree->pv[ply - 1].pathl =
Min(MAXPLY - 1, ply + ptable[entry].hash_pathl);
ptable[entry].hash_path_age = transposition_age;
break;
}
}
return HASH_HIT;
case UPPER:
if (val <= alpha)
return HASH_HIT;
break;
case LOWER:
if (val >= beta)
return HASH_HIT;
break;
}
}
return avoid_null;
}
return HASH_MISS;
}
/* last modified 09/16/14 */
/*
*******************************************************************************
* *
* HashStore() is used to store entries into the transposition table so that *
* this sub-tree won't have to be searched again if the same position is *
* reached. We basically store three types of entries: *
* *
* (1) EXACT. This entry is stored when we complete a search at some ply *
* and end up with a score that is greater than alpha and less than *
* beta, which is an exact score, which also has a best move to try *
* if we encounter this position again. *
* *
* (2) LOWER. This entry is stored when we complete a search at some ply *
* and end up with a score that is greater than or equal to beta. We *
* know know that this score should be at least equal to beta and may *
* well be even higher. So this entry represents a lower bound on *
* the score for this node, and we also have a good move to try since *
* it caused the cutoff, although we do not know if it is the best *
* move or not since not all moves were search. *
* *
* (3) UPPER. This entry is stored when we complete a search at some ply *
* and end up with a score that is less than or equal to alpha. We *
* know know that this score should be at least equal to alpha and *
* may well be even lower. So this entry represents an upper bound *
* on the score for this node. We have no idea about which move is *
* best in this position since they all failed low, so we store a *
* best move of zero. *
* *
* For storing, we may require three passes. We make our first pass looking *
* for an entry that matches the current hash signature. If we find a match *
* then we are constrained to overwrite that entry regardless of any other *
* considerations. The second pass looks for entries stored in previous *
* searches (not iterations) and chooses the one with the shallowest draft, *
* if one is found; Otherwise we make a final pass over the bucket and *
* choose the entry with the shallowest draft, period. *
* *
*******************************************************************************
*/
void HashStore(TREE * RESTRICT tree, int ply, int depth, int side, int type,
int value, int bestmove) {
HASH_ENTRY *htable, *replace = 0;
HPATH_ENTRY *ptable;
uint64_t word1, temp_hashkey;
int entry, draft, age, replace_draft, i, j;
/*
************************************************************
* *
* "Fill in the blank" and build a table entry from *
* current search information. *
* *
************************************************************
*/
word1 = transposition_age;
word1 = (word1 << 2) | type;
if (value > 32000)
value += ply - 1;
else if (value < -32000)
value -= ply - 1;
word1 = (word1 << 21) | bestmove;
word1 = (word1 << 15) | depth;
word1 = (word1 << 17) | (value + 65536);
temp_hashkey = (side) ? HashKey : ~HashKey;
/*
************************************************************
* *
* Now we search for an entry to overwrite in three *
* passes. *
* *
* Pass 1: If any signature in the table matches the *
* current signature, we are going to overwrite this *
* entry, period. It might seem worthwhile to check the *
* draft and not overwrite if the table draft is greater *
* than the current remaining depth, but after you think *
* about it, this is a bad idea. If the draft is *
* greater than or equal the current remaining depth, *
* then we should never get here unless the stored bound *
* or score is unusable because of the current alpha/ *
* beta window. So we are overwriting to avoid losing *
* the current result. *
* *
* Pass 2: If any of the entries come from a previous *
* search (not iteration) then we choose the entry from *
* this set that has the smallest draft, since it is the *
* least potentially usable result. *
* *
* Pass 3: If neither of the above two found an entry to *
* overwrite, we simply choose the entry from the bucket *
* with the smallest draft and overwrite that. *
* *
************************************************************
*/
htable = hash_table + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++) {
if (temp_hashkey == (htable[entry].word1 ^ htable[entry].word2)) {
replace = htable + entry;
break;
}
}
if (!replace) {
replace_draft = 99999;
for (entry = 0; entry < 4; entry++) {
age = htable[entry].word1 >> 55;
draft = (htable[entry].word1 >> 17) & 0x7fff;
if (age != transposition_age && replace_draft > draft) {
replace = htable + entry;
replace_draft = draft;
}
}
if (!replace) {
for (entry = 0; entry < 4; entry++) {
draft = (htable[entry].word1 >> 17) & 0x7fff;
if (replace_draft > draft) {
replace = htable + entry;
replace_draft = draft;
}
}
}
}
/*
************************************************************
* *
* Now that we know which entry to replace, we simply *
* stuff the values and exit. Note that the two 64 bit *
* words are xor'ed together and stored as the signature *
* for the "lockless-hash" approach. *
* *
************************************************************
*/
replace->word1 = word1;
replace->word2 = temp_hashkey ^ word1;
/*
************************************************************
* *
* If this is an EXACT entry, we are going to store the PV *
* in a safe place so that if we get a hit on this entry, *
* we can recover the PV and see the complete path rather *
* rather than one that is incomplete. *
* *
************************************************************
*/
if (type == EXACT) {
ptable = hash_path + (temp_hashkey & hash_path_mask);
for (i = 0; i < 16; i++, ptable++) {
if (ptable->path_sig == temp_hashkey ||
((transposition_age - ptable->hash_path_age) > 1)) {
for (j = ply; j < tree->pv[ply - 1].pathl; j++)
ptable->hash_path_moves[j - ply] = tree->pv[ply - 1].path[j];
ptable->hash_pathl = tree->pv[ply - 1].pathl - ply;
ptable->path_sig = temp_hashkey;
ptable->hash_path_age = transposition_age;
break;
}
}
}
}
/* last modified 09/16/14 */
/*
*******************************************************************************
* *
* HashStorePV() is called by Iterate() to insert the PV moves so they will *
* be searched before any other moves. Normally the PV moves would be in *
* the table, but on occasion they can be overwritten, particularly the ones *
* that are a significant distance from the root since those table entries *
* will have a low draft. *
* *
*******************************************************************************
*/
void HashStorePV(TREE * RESTRICT tree, int side, int ply) {
HASH_ENTRY *htable, *replace;
uint64_t temp_hashkey, word1;
int entry, draft, replace_draft, age;
/*
************************************************************
* *
* First, compute the initial hash address and the fake *
* entry we will store if we don't find a valid match *
* already in the table. *
* *
************************************************************
*/
temp_hashkey = (side) ? HashKey : ~HashKey;
word1 = transposition_age;
word1 = (word1 << 2) | WORTHLESS;
word1 = (word1 << 21) | tree->pv[0].path[ply];
word1 = (word1 << 32) | 65536;
/*
************************************************************
* *
* Now we search for an entry to overwrite in three *
* passes. *
* *
* Pass 1: If any signature in the table matches the *
* current signature, we are going to overwrite this *
* entry, period. It might seem worthwhile to check the *
* draft and not overwrite if the table draft is greater *
* than the current remaining depth, but after you think *
* about it, this is a bad idea. If the draft is *
* greater than or equal the current remaining depth, *
* then we should never get here unless the stored bound *
* or score is unusable because of the current alpha/ *
* beta window. So we are overwriting to avoid losing *
* the current result. *
* *
* Pass 2: If any of the entries come from a previous *
* search (not iteration) then we choose the entry from *
* this set that has the smallest draft, since it is the *
* least potentially usable result. *
* *
* Pass 3: If neither of the above two found an entry to *
* overwrite, we simply choose the entry from the bucket *
* with the smallest draft and overwrite that. *
* *
************************************************************
*/
htable = hash_table + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++) {
if ((htable[entry].word2 ^ htable[entry].word1) == temp_hashkey) {
htable[entry].word1 &= ~((uint64_t) 0x1fffff << 32);
htable[entry].word1 |= (uint64_t) tree->pv[0].path[ply] << 32;
htable[entry].word2 = temp_hashkey ^ htable[entry].word1;
break;
}
}
if (entry == 4) {
replace = 0;
replace_draft = 99999;
for (entry = 0; entry < 4; entry++) {
age = htable[entry].word1 >> 55;
draft = (htable[entry].word1 >> 17) & 0x7fff;
if (age != transposition_age && replace_draft > draft) {
replace = htable + entry;
replace_draft = draft;
}
}
if (!replace) {
for (entry = 0; entry < 4; entry++) {
draft = (htable[entry].word1 >> 17) & 0x7fff;
if (replace_draft > draft) {
replace = htable + entry;
replace_draft = draft;
}
}
}
replace->word1 = word1;
replace->word2 = temp_hashkey ^ word1;
}
}