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