Incremental Zobrist - slow?
Posted: Sat Jun 20, 2009 6:00 am
Hi all,
I hit a bit of a wall regarding speed of Zobrist key/hash management. For a long time my program generated the entire hash for a given board from scratch (when needed, like for rep detection - every makeMove and for evaluation). I decided to improve that and take advantage of the Zobrist key property that you can just keep it up to date as you make move by zor-ing the required keys. It turns out I lose about 30% of speed doing that!!
I must be doing something wrong. The code to update the hash of the board is done in make move, and looks something like this (for a non-capture) for example:
This turns out to generate a lot of code in assembler. I am compiling for a 64 bit platform. Also when using AMD's CodeAnalyst it does indeed point out that a lot of cycles (about 30%) of the makeMove function are spent in there.
Is there anything that I am missing? Some tricks that people do to generate those xors faster? Store the keys in a better way?
Thanks in advance,
Vlad.
I hit a bit of a wall regarding speed of Zobrist key/hash management. For a long time my program generated the entire hash for a given board from scratch (when needed, like for rep detection - every makeMove and for evaluation). I decided to improve that and take advantage of the Zobrist key property that you can just keep it up to date as you make move by zor-ing the required keys. It turns out I lose about 30% of speed doing that!!
I must be doing something wrong. The code to update the hash of the board is done in make move, and looks something like this (for a non-capture) for example:
Code: Select all
m_kHashKey ^= g_kPieceCodes[m_iSideToMove][kMove.m_piece][fromSq] ^ g_kPieceCodes[m_iSideToMove][kMove.m_piece][toSq];
Is there anything that I am missing? Some tricks that people do to generate those xors faster? Store the keys in a better way?
Thanks in advance,
Vlad.