Author: Sven Reichard
Date: 06:48:57 10/12/99
Go up one level in this thread
On October 11, 1999 at 20:48:30, Nicolas Carrasco wrote:
>Is is possible to implement Hash Tables to a game that stores the position on
>arrays like: int piece[64] and int color[64] >with a decent speed?
>
>What solutions?
>
>Thanks Scott
Hash tables generally do not depend on the board representation. You need a hash
function, but it doesn't have to access the board itself.
One possibility is to assign a hash key (usually a 64-bit number) to each piece
on each square (i.e., 64(squares)*6(pieces)*2(colors) keys). We define the hash
key for the position by XORing the keys for each piece, and by flipping all bits
if black is to move. An empty square always gets the key 0.
However, we don't calculate it this way. Assume we are at some position, where
we already know the hash key. Now we do a move from, say, src to dest, with a
piece P, capturing another piece Q (which might be empty). Then
newHashKey = NOT(oldHashKey XOR key(P on src) XOR key(P on dest)
XOR key(Q on dest))
is the key for the resulting position. The "NOT" takes care of switching the
right to move, the XORs remove Q and move P from src to dest.
Note that to get back to the old key (when undoing the move) we do exactly the
same as above, with new and old hash keys interchanged.
What you do with the obtained keys is up to you. You can use some bits to find
an index in the hash table, and store the others with the hash entry to identify
the position.
To define good keys for each Piece/Square is another issue. I would just use
random numbers, but maybe there is a better way to do that.
Sven.
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.