Author: Don Dailey
Date: 22:31:30 01/14/98
Go up one level in this thread
By the way, I mentioned originally that you should do a global hash compute and call both routines after each move with an assertion that they are equal as a debugging step. You would have caught the bug right away. I would still do this step, it will ensure that everything is the way it should be. How do you calculate the address into the hash table? Don't forget that color to move is a factor. How many bits of hash key do you use and how do they relate to the address calculation? Are you saving best move? This is a biggie. There are actually a lot of fine points and "gotch's" with hash table implementation. Bob is the master in this area. - Don 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?
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.