Author: John Scalo
Date: 10:20:48 01/14/98
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.01 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.