Jump to content

  • Log In with Google      Sign In   
  • Create Account


Implementing Transposition Table - NegaMax Search


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 stoneyrich   Members   -  Reputation: 142

Like
0Likes
Like

Posted 09 August 2012 - 02:53 AM

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 ?

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12003

Like
0Likes
Like

Posted 09 August 2012 - 05:12 AM

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:
  • Add a member zobrist_key to your board description.
  • 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.

Read up these links:
  • 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


#3 stoneyrich   Members   -  Reputation: 142

Like
0Likes
Like

Posted 09 August 2012 - 08:40 AM

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...




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS