#include "chess.h"
#include "data.h"
/* last modified 02/22/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, j;
/*
************************************************************
* *
* 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 = trans_ref + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++, htable++) {
word1 = htable->word1;
word2 = htable->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->word1 = word1;
htable->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 - 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 + (draft == MAX_DRAFT));
ptable = hash_path + (temp_hashkey & hash_path_mask);
for (i = 0; i < 16; i++, ptable++)
if (ptable->path_sig == temp_hashkey) {
for (j = ply; j < Min(MAXPLY - 1, ptable->hash_pathl + ply);
j++)
tree->pv[ply - 1].path[j] =
ptable->hash_path_moves[j - ply];
if (draft != MAX_DRAFT &&
ptable->hash_pathl + ply < MAXPLY - 1)
tree->pv[ply - 1].pathh = 0;
tree->pv[ply - 1].pathl =
Min(MAXPLY - 1, ply + ptable->hash_pathl);
ptable->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 02/22/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 = trans_ref + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++, htable++) {
if (temp_hashkey == (htable->word1 ^ htable->word2)) {
replace = htable;
break;
}
}
if (!replace) {
replace_draft = 99999;
htable = trans_ref + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++, htable++) {
age = htable->word1 >> 55;
draft = (htable->word1 >> 17) & 0x7fff;
if (age != transposition_age && replace_draft > draft) {
replace = htable;
replace_draft = draft;
}
}
if (!replace) {
htable = trans_ref + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++, htable++) {
draft = (htable->word1 >> 17) & 0x7fff;
if (replace_draft > draft) {
replace = htable;
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 02/22/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 = trans_ref + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++, htable++) {
if ((htable->word2 ^ htable->word1) == temp_hashkey) {
htable->word1 &= ~((uint64_t) 0x1fffff << 32);
htable->word1 |= (uint64_t) tree->pv[0].path[ply] << 32;
htable->word2 = temp_hashkey ^ htable->word1;
break;
}
}
if (entry == 4) {
htable = trans_ref + (temp_hashkey & hash_mask);
replace = 0;
replace_draft = 99999;
for (entry = 0; entry < 4; entry++, htable++) {
age = htable->word1 >> 55;
draft = (htable->word1 >> 17) & 0x7fff;
if (age != transposition_age && replace_draft > draft) {
replace = htable;
replace_draft = draft;
}
}
if (!replace) {
htable = trans_ref + (temp_hashkey & hash_mask);
for (entry = 0; entry < 4; entry++, htable++) {
draft = (htable->word1 >> 17) & 0x7fff;
if (replace_draft > draft) {
replace = htable;
replace_draft = draft;
}
}
}
replace->word1 = word1;
replace->word2 = temp_hashkey ^ word1;
}
}