Author: Robert Hyatt
Date: 11:16:21 01/14/98
Go up one level in this thread
On January 14, 1998 at 13:20:48, John Scalo wrote: >Quick recap: > >I asked about a fast hash algorithm as the one I was using to hash the >entire board every time was probably too slow. Bob Hyatt and Don Dailey >graciously enlightened me to the technique of incrementally updating the >hash key after each move. > >Fade to the present:-) > >I implemented this and the nps went way up but unfortunately so did the >number of nodes! So much so that the total time to find the same move in >the same position went up on average 4%. After thinking and testing I >realized that this is because the "incremental method" only works for >true _transpositions of moves_ and may not always see two identical >positions as having the same key. Therefore a lot of matches are missed. > >Here's an example - > >Say you have nothing but two kings on the board; white king at c2 and >black king at c7. Now take these two series of moves: > >Seq A: Seq B: >c2-c3 c7-c6 c2-c1 c7-c6 >c3-b2 c1-b2 > >In both sequences, you end up with the same position: wk on b2, bk on >c6. > >The key in seq A would be something like: >origKey ^ randTable[white][king][c3] ^ > randTable[black][king][c6] ^ > randTable[white][king][b2] > >And for B: >origKey ^ randTable[white][king][c1] ^ > randTable[black][king][c6] ^ > randTable[white][king][b2] > >So call v,w,x,y,z random numbers in the table. > >key[A] = v^w^y^z >key[B] = v^x^y^z > >And these of course will be different numbers. > >So is this by design or am I missing something? If it's by design, does >it make sense that hashing the entire board every time is actually >faster because the # of nodes is so much lower? You aren't doing the calculation right. The original key should have two values exclusive-or'ed together... the two numbers representing the location of the two white kings. If you move one white king, you have to do two exclusive-or operations to update the key. Once with the random value for the original square, which effectively takes it *out* of the key, and then once for the new key. Somehow you appear to have interpreted this as being move-based. It is not, it is position-based. IE, if you incrementally update the hash key as we originally explained, and at any point during the search you create a brand new one by simply exclusive-or'ing the values for each piece on each square in the current position, the two hash signatures will be *identical*...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.