Author: Don Dailey
Date: 18:43:46 01/08/98
Go up one level in this thread
On January 08, 1998 at 20:04:22, John Scalo wrote:
>On January 08, 1998 at 19:51:44, Robert Hyatt wrote:
>
>>On January 08, 1998 at 17:57:13, John Scalo wrote:
>>
>>>Reviewing the bottlenecks in my program, I realize that my hash key
>>>algorithm is fairly inefficient. It uses the Zobrist algorithm for
>>>creating keys from relatively large structures like an [8][8] array, but
>>>it's too slow.
>>>
>>>I would think that having bitboards of white's and black's pieces would
>>>be sufficient to come up with a 32-bit key quickly, but I haven't been
>>>able to come up with anything that gives a "random" enough distribution.
>>>
>>>Any ideas? I looked at Crafty but couldn't figure out exactly what it
>>>was doing.
>>>
>>>Thanks,
>>
>>
>>the main "key" is to compute the hash key incrementally as you make and
>>unmake moves, rather than looping over the entire board to construct the
>>thing before you do a probe. The nice thing about the "exclusive-or"
>>operation is that if you exclusive-or the same value with the hash key
>>a second time, it undoes the first exclusive-or... so you can easily
>>update
>>the hash key as you move pieces around...
>
>Ah.. That explains why you attach the key to the search global in
>Crafty. What values/structures do you use to update the key after a
>move? The move itself or the new bitboard(s) ?
>
>Thanks,
>John
When you make a move you xor the current key with the random table
values in your table. Each piece of each color has it's own table
of well distributed random numbers. Something like this:
newkey = oldkey ^ random_table[WHITE][PAWN][FROM_SQ_INDEX]
^ random_table[WHITE][PAWN][TO_SQ_INDEX];
This might be your operation for updating the hash key for e2e4. This
is extremely fast, no branch logic and only one move to deal with
instead
of 32 pieces.
If the move is a capture you also xor out the captured piece. Because
of the described property of xor if you reach the same position after
a bunch of aimless moves the key will magically end up the same which
is important. Some programs have an unmake operation. If your program
unmakes moves then place the old key in a stack so that you can pop it
off instead of recomputing it for take backs. I would recommend that
you unamke it anyway at first to prove it's correctness and then do
the fast stack thing.
The bit boards have nothing to do with this. I would not try to
create a hash key from the bitboards without really knowing what
your are doing (the incremental method is faster anyway.)
- Don
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.