Author: John Coffey
Date: 13:36:38 09/29/98
Go up one level in this thread
On September 29, 1998 at 16:04:45, vincent dichiacchio wrote:
>Can anyone explain how opening book transpositions are identified? My guess is
>that opening book files are just permanent hash coded transposition tables, but
>I am not sure.
>Thanks,
>Vince
From what I understand, that is pretty close. There was a recent
discussion about this relating to hash tables in general. I will
send my whole file on hashing to anyone who wants it.
Old discussion below. Sorry if anyone is not credited ....
----------------------------------------------------------------------------
by William H Rogers on September 21, 1998 at 15:02:28:
In Reply to: Efficient hash algorithm? posted by John Coffey on September 21,
1998 at 13:48:58:
John
Hashing does not take up much space and is fairly easy to program.
You scan the chessboard at any point and place a 0 for an empty square or a 1
for a square that is occupied. Then take the first 16 bits and "OR" them with
the second 16 bits, etc. until you get the whole board. This will give you an
address for 64K of openings for chess books. Once you find a hash code for the
opening you enter your move and a move number.
That is all there is to it, however, you will find on some occasions that
different combinations of the chess board lead to the same location causing a
bad move. Such collisions can be avoided by several techniques, such as looking
at the move number of the current move and comparing it to the move number in
the hash table. This does not always work, but it is a good starting point.
Thanks for the email.
BILL ROGERS
If you only count whether or not a square is occupied, you will get a lot of
false matches when the same squares are occupied by different pieces. I think
the best method is to define a set of numbers using a random number algorithm at
the start of the program, so that each piece/side/square combination is
associated with a unique number. You then xor the hash key with the appropriate
number whenever you add or remove a piece from the board. However, in reality
you need to maintain two separate hash keys, using two separate sets of
piece/side/square keys. The second one is a checksum value which is stored in
the table and used to detect false matches. This should be at least 64 bits to
be safe. This is how I do it in Rabbit, and I believe it is a fairly standard
approach.
The question of replacement strategy is not so conclusive: different programs do
it in different ways. I use depth to decide whether to erase an old record to
make way for a new one, giving priority to the record with greater depth.
As for what to store, I suggest the following as a minimal set:
1) checksum (8 bytes)
2) upper bound (2 bytes)
3) lower bound (2bytes)
4) best move (2 bytes, but there are clever ways to reduce this to one byte if
you are trying to save space)
Best wishes,
Roberto
Posted by Tom Kerrigan on September 21, 1998 at 18:12:36:
In Reply to: Re: Efficient hash algorithm? posted by Roberto Waldteufel on
September 21, 1998 at 15:38:19:
Mostly correct, although maintaining two numbers to describe the position is
overkill. One 64 bit number should be enough.
You should also have two hash tables, one with an "always overwrite" replacement
policy and another with a replacement policy based on depth. Almost everybody I
know agrees that this is the best way to do things on a PC.
Here's what I store in my hash table entries:
bytes thing
8 position number
2 score
1 flag (is the score an upper bound? lower bound? exact?)
1 depth
4 move
Which adds up to 16 bytes, which is an excellent number of bytes for a hash
table entry. :)
-Tom
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.