Author: Dan Newman
Date: 14:21:11 09/22/98
Go up one level in this thread
On September 22, 1998 at 12:17:03, Pat King wrote: > >On September 22, 1998 at 08:50:53, Pat King wrote: > > >>The odds of a search not containing a mistake are therefore >>(1-2^-32)^n, where n is the number of nodes searched. To >>have a 50% chance of an error, you'd need to search about 3e+09 >>nodes. With null-move, that's about 20 plies. > >He (I) also said > >>PS Since 1-2^32 is so close to 1, there's probably a fair amount >>of error in that 3e+09 estimate, but you can stand a LOT of error >>in this case and still have the argument hold up! > >Well, upon pondering the problem I made a refined estimate (but >still only an estimate) of 2^32 or about 4.3 e+09 nodes, which >works out to 20.2 plies instead of 19.something. Is the 2^32 >figure for P(lookup error)=.5 for a 32 bit key a coincidence? I >suspect not. If not, then you can easily decide on how much error >you're willing to tolerate. Based on this analysis, 64 bits >certainly seems like overkill to me. > >Pat I just tried measuring the hashing error rate in my latest program. I ran it on WAC at 5s/position with a 32-bit hash code (effectively a 33-bit hash code since I use side-to-move as one of the index bits instead of hashing side-to-move into the hashcode itself). I got 679 errors at a rate of 1.1 errors per second--about the rate that I gotten earlier. One thing to watch out for is poor sets of random numbers: random numbers produced by a simple linear congruence generator aren't very "random" in their low order bits--the zero order bit, for instance, simply alternates between 0 and 1 on successive generations. Now, suppose you do as I do and generate the hash code as two 32-bit numbers using two tables of 32-bit random numbers. If you fill these tables out with a linear congruence generator without any further processing of the numbers, you get the zero order bits of the two halves of the 64-bit hashcode perfectly correlated (and the other low order bits somewhat correlated). This effectively shrinks the size of the hashcode to less than 63 bits--how much less I don't know. I've tried several techniques to massage the random number tables. Currently I compare each new random number from the generator with all the numbers already in the random number tables and reject any that aren't sufficiently "different". This can take a painfully long time depending on how strict a criterion is used, so I don't do this in the chess program itself--I dump the numbers to a file to be read in by the engine. What I do to compare the numbers is I count the number of bits that are the same in the two numbers. If too many bits are the same or too few (we don't want perfect anti-correlation) in any of the comparisons, I throw out the number. The last time I generated a set, I rejected numbers that either had fewer than 8 bits or more than 24 bits the same. I seem to recall reading (on the net somewhere--probably rgcc) about a technique for directly generating a good set of bit patterns. I think it was something that came from the field of error coding or from cryptography--two fields I know very little about... -Dan.
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.