Author: Dan Newman
Date: 23:22:55 12/04/01
Go up one level in this thread
On December 04, 2001 at 20:11:34, martin fierz wrote: >On December 04, 2001 at 09:16:22, Severi Salminen wrote: > >>Hi! >> >>What is the definition of "hamming distance"? What characteristics should I test >>when testing my random numbers' suitability for zobrist keys? What alternatives >>there are for random number generators besides the rand() in C? >> >>Severi > >aloha! > >my experience is from a checkers program, but it shouldnt really matter. >i am using 32-bit random numbers generated by calling rand() twice, because >rand() only returns a 16-bit value on my compiler. i used to use these numbers >and read some posts here about hamming distance, so i decided to check: i >produced myself a set of random numbers x_i with the condition >hammingdistance(x_i,x_j) >=10 instead of the numbers the random generator was >generating. in my test suite i run a depth 19 search on 80 positions and can >compare two different versions - result: no difference. while i did have small >changes like 101% or 99% in some test positions, it was never much and on >average just zero. i don't know if my condition above is stupid or if it doesnt >really matter. i think the condition is stupid, because you will only have a >real problem if x_i XOR x_j equals some other x_k. or if x_i XOR x_j XOR x_k >equals x_l XOR x_m etc. >looks like these conditions are kind of hard to check... i also think it doesnt >matter: another thing i did was to initialize rand() with different seeds and >see what happens. result: again zero. i'd like to see someone come up with hard >numbers showing that rand() is really bad for generating zobrist keys. i don't >believe it is. > >cheers > martin There could be a small problem with joining 16-bit random numbers into 32-bit random numbers using rand(). Most rand()s produce sequences of numbers in which the low order bits change in a very predictable pattern. For instance, the lowest order bit typically goes 0 1 0 1 0 1 ... on a series of calls. The next bit typicall does something like 0 1 1 0 1 1 0 1 1. As you get to higher bits, the patterns become much more complex with a longer repeating sequence. What this means is that if you take the numbers in pairs as they are produced to make 32-bit numbers, then some of the bits will be highly correlated, and you will have (effectively) numbers that are only as "good" as 31-bit or 30-bit or perhaps smaller numbers. Bits 0 and 16 will in fact be perfectly anti-correlated. If you can somehow scramble the order in which the 16-bit numbers are combined into 32-bit numbers, then this problem should go away. Of course a 30 bit number may be almost as good as a 32-bit number anyway... The best thing to do (I think) is to get a good 32-bit random number generator in C (or whatever language you're using) so that you can get repeatable results on different machines and with different compilers. -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.