Author: Robert Hyatt
Date: 07:43:23 04/06/01
Go up one level in this thread
On April 06, 2001 at 06:27:57, David Rasmussen wrote: >On April 05, 2001 at 22:23:17, Robert Hyatt wrote: > >> >>a hamming distance of 16 is not very good for 64 bit values... > >I tested the numbers you use in Crafty, and the minimum hamming distance between >any pair of numbers you generate, is 14. That's even worse that 16. Just for >your information, only one pair of the numbers you generate, have this low >distance. It is the 185th number and the 394th number you generate. That is, the >keys for w_bishop_random[15] and b_queen_random[32] have a hamming distance of >14. > >Am I missing something here or are you? :) Actually I don't know. My first test was to do some trillion node searches and measure _actual_ collisions. I stored the actual hash key (64 bits) as I do now, plus the real board position (32 bytes, 4 bits for each square). And each time I got a hash hit, I did a real position match as well. For a test that searched about 1 trillion nodes per move, over a part of a full game, I get _zero_ collisions. As far as the minimum hamming distance goes, I'm much less worried about that so long as it is > 8. I am more interested in the _average_ hamming distance. I once modified the code to require > 24. It took quite a while to compute the needed values with that constraint, but it finished. I could find no improvement in hashing collisions however, so I tossed that test away. Another important thing you probably are not testing is "sensibility". IE no need to test the two random values for hamming distance if the two values represent squares that can not be moved to (IE a bishop on light squares can't ever use the other half of the board, nor those random values. The more likely two squares can be hit in one move, the more important that hamming distance is. I also don't really care about tha hamming distance between a bishop and a knight, since this hashing scheme is all about drastically changing the key by moving a single piece. That is probably why I didn't see a 14 distance, since I didn't check the numbers like that. Probably about the best you can do overall is a distance of 32 - log2(#values). That is assuming you compare _every_ number against every other number, something I didn't try to do when I was testing.
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.