Author: Roberto Waldteufel
Date: 12:38:19 09/21/98
Go up one level in this thread
On September 21, 1998 at 15:02:28, William H Rogers wrote:
>On September 21, 1998 at 13:48:58, John Coffey wrote:
>
>>I haven't seen very much on the net that describes an efficient hash
>>algorithm.
>>
>>My first thought was that I would hash the entire board, but I am guessing that
>>it is slow to create. Then it occured to me that I could hash just the
>>moves made (somehow) so that if someone played Nf3, Nc6, Nc3, Nf6 in
>>any move order I would get the same hash key. The only problem with this
>>is that in some endgame positions you could get pieces on the same squares
>>by many different moves. So then it occurs to me to hash each piece on each
>>square ... I start with a hash value for the whole board and then as each piece
>>moves then I subtract the hash value for a piece moving off of that sqaure and
>>then I add the hash value for the piece moving to the new square. This would
>>give me a whole-board hash that is dynamically updated.
>>
>>I assume that hash values will use exclusive-or's to combine them?
>>
>>Then there is the problem of multiple positions ending up with the same hash
>>key. I am not sure what to do about this yet. Do I have to store the entire
>>board position and compare that to make sure I haven't got some other position?
>>If I end up with duplicate keys then do I erase the old position and fill it in
>>with the new, or do I keep both positions? Do I keep positions that were found
>>2 to 3 moves ago? (After some real moves have been made on the board.) What
>>do I do when the hash table starts to get full?
>>
>>
>>I assume that BSP trees would be slower than hashing.
>>
>>How much space does each hash position usually take?
>>
>>John Coffey
>
>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
This page took 0.02 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.