#include #include #include "chess.h" #include "data.h" /* last modified 09/14/99 */ /* ******************************************************************************** * * * 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: * * * * bits name SL description * * 3 age 61 search id to identify old trans/ref entries. * * 2 type 59 0->value is worthless; 1-> value represents a fail- * * low bound; 2-> value represents a fail-high bound; * * 3-> value is an exact score. * * 1 threat 58 threat extension flag, 1 -> extend this position. * * 5 unused 53 unused at present time. * * 21 move 32 best move from the current position, according to the * * search at the time this position was stored. * * 15 draft 17 the depth of the search below this position, which is * * used to see if we can use this entry at the current * * position. note that this is in units of 1/60th of a * * ply. * * 17 value 0 unsigned integer value of this position + 65536. * * this might be a good score or search bound. * * * * 64 key 0 64 bit hash signature, used to verify that this entry * * goes with the current board position. * * * ******************************************************************************** */ int HashProbe(TREE *tree, int ply, int depth, int wtm, int *alpha, int *beta, int *threat) { register BITBOARD word1, word2; register int type, draft, avoid_null=0, val, pieces, null_depth; register unsigned int word1l, word1r; BITBOARD temp_hashkey; HASH_ENTRY *htable; /* ---------------------------------------------------------- | | | first, compute the initial hash address and choose | | which hash table (based on color) to probe. | | | ---------------------------------------------------------- */ tree->hash_move[ply]=0; #if !defined(FAST) tree->transposition_probes++; #endif /* ---------------------------------------------------------- | | | now, check both "parts" of the hash table to see if | | this position is in either one. | | | ---------------------------------------------------------- */ pieces=(wtm) ? TotalWhitePieces : TotalBlackPieces; null_depth=(depth>6*INCPLY && pieces>8) ? null_max : null_min; temp_hashkey=(wtm) ? HashKey : ~HashKey; htable=trans_ref_a+((int) temp_hashkey&hash_maska); word1=htable->word1; word2=word1^htable->word2; if (word2 == temp_hashkey) do { #if !defined(FAST) tree->transposition_hits++; #endif word1l=word1>>32; word1r=word1; val=(word1r & 0377777)-65536; draft=word1r>>17; tree->hash_move[ply]=word1l & 07777777; *threat=(word1l>>26) & 01; type=(word1l>>27) & 03; if ((type & UPPER) && depth-null_depth <= draft && val < *beta) avoid_null=AVOID_NULL_MOVE; if (depth > draft) break; switch (type) { case EXACT: if (abs(val) > MATE-300) { if (val > 0) val-=(ply-1); else val+=(ply-1); } *alpha=val; return(EXACT); case UPPER: if (val <= *alpha) { *alpha=val; return(UPPER); } break; case LOWER: if (val >= *beta) { *beta=val; return(LOWER); } break; } } while(0); htable=trans_ref_b+((int)temp_hashkey&hash_maskb); word1=htable->word1; word2=word1^htable->word2; if (word2 == temp_hashkey) { #if !defined(FAST) tree->transposition_hits++; #endif word1l=word1>>32; word1r=word1; val=(word1r & 0377777)-65536; draft=word1r>>17; if (tree->hash_move[ply]==0) tree->hash_move[ply]=word1l & 07777777; *threat=(word1l>>26) & 01; type=(word1l>>27) & 03; if ((type & UPPER) && depth-null_depth <= draft && val < *beta) avoid_null=AVOID_NULL_MOVE; if (depth > draft) return(avoid_null); switch (type) { case EXACT: if (abs(val) > MATE-300) { if (val > 0) val-=(ply-1); else val+=(ply-1); } *alpha=val; return(EXACT); case UPPER: if (val <= *alpha) { *alpha=val; return(UPPER); } return(avoid_null); case LOWER: if (val >= *beta) { *beta=val; return(LOWER); } return(avoid_null); } } return(avoid_null); } /* last modified 09/14/99 */ /* ******************************************************************************** * * * 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. a transposition/refutation table position contains the following * * data packed into 128 bits, with each item taking the number of bits given * * in the table below. * * * * bits name SL description * * 3 age 61 search id to identify old trans/ref entried. * * 2 type 59 0->value is worthless; 1-> value represents a fail- * * low bound; 2-> value represents a fail-high bound; * * 3-> value is an exact score. * * 1 threat 58 threat extension flag, 1 -> extend this position. * * 5 unused 53 unused at present time. * * 21 move 32 best move from the current position, according to the * * search at the time this position was stored. * * 15 draft 17 the depth of the search below this position, which is * * used to see if we can use this entry at the current * * position. note that this is in units of 1/60th of a * * ply. * * 17 value 0 unsigned integer value of this position + 65536. * * this might be a good score or search bound. * * * * 64 key 0 64 bit hash signature, used to verify that this entry * * goes with the current board position. * * * ******************************************************************************** */ void HashStore(TREE *tree, int ply, int depth, int wtm, int type, int value, int threat) { register BITBOARD word1, word2; register HASH_ENTRY *htablea, *htableb; register int draft, age; register unsigned int word1l, word1r; /* ---------------------------------------------------------- | | | "fill in the blank" and build a table entry from | | current search information. | | | ---------------------------------------------------------- */ word1l=((((transposition_id<<2)+type)<<1)+threat)<<26; if (type == EXACT) { if (value > MATE-300) value=value+ply-1; else if (value < -MATE+300) value=value-ply+1; if ((int) tree->pv[ply].pathl >= ply) word1l|=tree->pv[ply].path[ply]; } else if (type == LOWER) { word1l|=tree->current_move[ply]; value=Min(value,MATE-300); } else { value=Max(value,-MATE+300); } word1r=(depth<<17)+value+65536; word1=word1r+((BITBOARD)word1l<<32); word2=(wtm) ? HashKey : ~HashKey; /* ---------------------------------------------------------- | | | if the draft of this entry is greater than the draft | | of the entry in the "depth-priority" table, or if the | | entry in the depth-priority table is from an old | | search, move that entry to the always-store table and | | then replace the depth-priority table entry by the new | | hash result. | | | ---------------------------------------------------------- */ htablea=trans_ref_a+((int) word2&hash_maska); draft=(int) htablea->word1>>17 & 077777; age=htablea->word1>>61; age=age && (age!=transposition_id); if (age || (depth >= draft)) { if ((word1^word2) != htablea->word2) { htableb=trans_ref_b+((int) (htablea->word2)&hash_maskb); htableb->word1=htablea->word1; htableb->word2=htablea->word2; } htablea->word1=word1; htablea->word2=word1^word2; } else { htableb=trans_ref_b+((int) word2&hash_maskb); htableb->word1=word1; htableb->word2=word1^word2; } } /* last modified 01/30/99 */ /* ******************************************************************************** * * * HashStorePV() is called by Iterate() to insert the PV moves so they will * * be searched before any other moves. * * * ******************************************************************************** */ void HashStorePV(TREE *tree, int ply, int wtm) { register HASH_ENTRY *htablea, *htableb; register BITBOARD temp_hashkey; /* ---------------------------------------------------------- | | | first, compute the initial hash address and choose | | which hash table (based on color) to probe. | | | ---------------------------------------------------------- */ temp_hashkey=(wtm) ? HashKey : ~HashKey; htablea=trans_ref_a+(((int) temp_hashkey)&hash_maska); htableb=trans_ref_b+(((int) temp_hashkey)&hash_maskb); /* ---------------------------------------------------------- | | | now "fill in the blank" and build a table entry from | | current search information. | | | ---------------------------------------------------------- */ if ((htablea->word2^htablea->word1) == temp_hashkey && (htablea->word1>>61)) { htablea->word2=htablea->word2^htablea->word1; htablea->word1&=~((BITBOARD) 07777777<<32); htablea->word1|=(BITBOARD) tree->pv[ply].path[ply]<<32; htablea->word2=htablea->word2^htablea->word1; } else if ((htableb->word2^htableb->word1) == temp_hashkey) { htableb->word2=htableb->word2^htableb->word1; htableb->word1&=~((BITBOARD) 07777777<<32); htableb->word1|=(BITBOARD) tree->pv[ply].path[ply]<<32; htableb->word2=htableb->word2^htableb->word1; } else { htableb->word1=(BITBOARD) 65536; htableb->word1|=((BITBOARD) ((transposition_id<<2)+WORTHLESS))<<59; htableb->word1|=(BITBOARD) tree->pv[ply].path[ply]<<32; htableb->word2=temp_hashkey^htableb->word1; } }