A transposition table is a cache of the board positions previously evaluated. These positions can be reached in various ways, known as transpositions. The transpositions are represented by a hash table. If a board positions is already represented in the hash table, the position does not need to be re-examined, the evaluation is taken from the hash table.
The hash table used is a hash table of Zobrist Keys.
Firstly we populate an array named hashkeys with 781 random numbers (generated by std::mt19927_64 which is a Mersenne twister)
A Zobrist key is generated for the current board position by XOR into the Zobrist key the hashkeys that we generated for 0 to 780 as follows:
12 pieces *64 squares – 0 to 767
void Hashing::generateHashKeys()
{
twister.seed(5489u); //standard seed
for (int i = 0; i < 781; i++)
{
hashkeys[i] = twister();
}
}
- 1 side black – 768
- 4 castling rights – 769 to 772
- 8 en passant file – 773 to 780
I have set up a struct transpositionTable:
typedef struct
{
unsigned long long key;
int depth;
int flags;
int value;
int best;
} transpositionTable;
An instance is created with the class: Hashing::transpositionTable hash_table[HASHSIZE];
key is the full Zobrist key.
depth is the depth of the search.
flags are: hashfEXACT 0, hashfALPHA 1, hashfBETA 2
If hashfEXACT, the evaluation.
If flag hashfALPHA, then at most the evaluation.
If hashfBETA, at least the evaluation
best is the best move encountered the last time the position was searched.
The following functions help populate the transposition table.
void Hashing::setZobristPiece(int square, Defs::Pieces piece) //populate piece on square
{
if (piece > Defs::Pieces::empty && piece <= Defs::Pieces::enpassant )
{ int file = (square & 7); int rank = (square >> 4);
int sq64 = (rank * 8) + (file + 1);
zobristKey ^= hashkeys[(sq64 * static_cast(piece)) - 1];
}
}void Hashing::setZobristEp(int square) //populate en passant
{
int file = square & 7;
zobristKey ^= hashkeys[773 + file];
}void Hashing::setZobristSide() //populate black
{
zobristKey ^= 768; //set if black. Reverse if white
}void Hashing::setZobristCastle(int castleflag) //populate castling flag
{
if (castleflag & 1) { zobristKey ^= 769; }
if (castleflag & 2) { zobristKey ^= 770; }
if (castleflag & 4) { zobristKey ^= 771; }
if (castleflag & 8) { zobristKey ^= 772; }
}The RecordHash function populates the transpositionTable structure with a position.
void Hashing::RecordHash(int depth, int val, int hashf, int bestMove)
The key for the array is Zobrist Key modulo the defined size of the hash table that I have set at hex 400000. Any clashes will overwrite. This is done to prevent the use of too much memory.
define HASHSIZE 0x400000 //int 4,194,304The ProbeHash function – int Hashing::ProbeHash(int depth, int alpha, int beta)
It gets a pointer to the transposition table for a key
transpositionTable* transpoTable = &hash_table[zobristKey % HASHSIZE];If key exactly matches the Zobrist key, depth is at least the search depth:
If the flag is hashfEXACT, value (the evaluation) is returned.
If the flag is hashfALPHA and value is <= alpha, the alpha passed to the function is returned. If the flag is hashfBETA and value is >= beta, the beta passed to the function is returned.
Negamax Function
Probe the hash table to see if the current board position has already been recorded, and if so, and a value is found, return that value.
If at depth zero, evaluate the board, record the hash and its value, return the value
For each child, if value >= beta, call RecordHash with hashfBETA flag and return beta.
If value > alpha, set alpha to value, set hashFlag to hashfEXACT and record to the hash table.
When called:
Below is pseudocode of how this fits into a negamax function
int negamax( int alpha, int beta, int depth ) {
int hashFlag = hashfALPHA; // define hash flag
int hashVal = Hash.ProbeHash(depth, alpha, beta);
if (hashVal != VALUNKNOWN)
{
// if the move has already been searched (hence has a value)
// we just return the score for this move without searching it
return hashVal;
}
if( depth == 0 ) return quiescence( alpha, beta );
for ( all moves) {
score = -alphaBeta( -beta, -alpha, depth - 1 );
if( val >= beta )
// store hash entry with the score equal to beta
Hash.RecordHash(depth, beta, hashfBETA);
return beta; // fail hard beta-cutoff
if( val > alpha )
alpha = val; // alpha acts like max in MiniMax
// switch hash flag from storing score for fail-low node
// to the one storing score for PV node
hashFlag = hashfEXACT;
}
// store hash entry with the score equal to alpha
Hash.RecordHash(depth, alpha, hashFlag);
return alpha;
}