Author: David Rasmussen
Date: 08:57:23 04/06/01
Go up one level in this thread
On April 06, 2001 at 10:43:23, Robert Hyatt wrote: >> >>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. > So do I, after I corrected my search bug, as you can read elsewhere. >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. > Why? The minimum distance pairs are the worst cases, but they are still there. >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. > I don't collisions either now, so it is very hard to test the effect of different sets of numbers, as none of the sets give collisions within even long amounts of time. This hints that it might not be worth the effort to generate particularly good numbers at all. But it is still theoretically interesting, I think. >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. > Of course. >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 is a question for the domain of coding theory. As I've posted elsewhere, the non-linear 64-bit code with the largest dimension that we know of today, is an extended BCH code. It is entirely possible to generate 840 numbers with minimum hamming distance 23 so 32 - log2(#values) is not a bound.
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.