• 13
• 18
• 19
• 27
• 10

# Implementing Transposition Table - NegaMax Search

This topic is 2049 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am trying to implement a transposition table in my search incorporating zobrist key a brief description - at each position you have 13 different pieces, 1-6 from player 1, 1-6 from player 2, and 0 (empty) that means my zobrist key table will be of size 13 * 25. I filled my table with some random values wit the code below

public void intZobristKeys() {

Random ranZobristKey;
ranZobristKey = new Random();

for (int positon = 0; positon < 325; positon++) {
zobrist_table[positon][EMPTY] = ranZobristKey.nextInt();
zobrist_table[positon][PLAYER_ONE] = ranZobristKey.nextInt();
zobrist_table[positon][PLAYER_TWO] = ranZobristKey.nextInt();
}

}

am stuck where do i move from here as in the link between this and recording the actual moves in the transposition table eg {hashkey, state value, depth} etc any help ?

##### Share on other sites
First a minor detail: Things are a tiny bit simpler if you don't encode the empty squares in the Zobrist key.

Here are the things you are missing:

• Whenever the board changes (a piece moves, or is added, or is removed), change zobrist_key appropriately.

 void add_piece(int square, int piece_type) { // ... // [[ Here goes your usual code to add a piece to the board ]] // ... zobrist_key ^= zobrist_table[square][piece_type]; }

• Create a structure TranspositionTableEntry that contains at least these fields: zobrist_key, depth, bound_type (exact, lower_bound, upper_bound), score, best_move.
• Create a large [fixed-size] array of those structures.
• Add code at the end of the search to store the results of the search in the table (the bound type depends on where the result falls with respect to the alpha-beta window). You'll need a replacement scheme to make sure you don't throw away important information, but you can start simply writing the results in transposition_table[zobrist_key%table_size], always overwriting whatever was there.
• Add code at the beginning of the search to look up the table and check if the zobrist_key matches. Then see if we can use the score (depth is high enough) to improve alpha or beta or to simply return it. If you still have to search this node (depth wasn't high enough, or the score wasn't exact and the bound improvement doesn't make alpha>=beta), you can still use the information of what move happened to be best or produced a beta cut last time we visited this position.

• http://web.archive.org/web/20071214140939/http://www.seanet.com/~brucemo/topics/zobrist.htm
• http://web.archive.org/web/20080315233307/http://www.seanet.com/~brucemo/topics/hashing.htm
• http://chessprogramming.wikispaces.com/Transposition+Table

##### Share on other sites
Hi alvaro,

Thanks soo much for your response and detailed explanation of my question.

I was able to implement the transposition table. and there was an improvement from my previous experiment.

Thanks once again...