Subversion Repositories Games.Chess Giants

#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;

  }

}