Author: Robert Hyatt
Date: 06:38:55 01/09/98
Go up one level in this thread
On January 08, 1998 at 21:43:46, Don Dailey wrote: >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 I agree. bitboards are sparsely populated. using them to form a hash signature would be difficult compared with the Zobrist approach, and the random distribution of the signatures would probably be nowhere near as good...
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.