Author: Nicolas Carrasco
Date: 13:43:57 10/12/99
Go up one level in this thread
thanks On October 12, 1999 at 09:48:57, Sven Reichard wrote: >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.