Author: Dieter Buerssner
Date: 08:45:48 12/05/01
Go up one level in this thread
On December 05, 2001 at 02:22:55, Dan Newman wrote: >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. I agree with almost anything said. Some additional info. Many rand() only return 15 bits (but not less, because 15 bits is required by the ISO-C Standard). Your lowest order period of 2 is the typical case for linear congruential generators (LCGs) with a modulus of a power of 2 (all literature suggests prime numbers ...). I think, only some early BSD systems used that bad PRNG. The rand sources I know, and also others I don't know, but have tested for there properities, still often use LCGs, but typically use the 15 most significant bits of the output of a 31 bit LGC. So the period of the last bit should be 2^16. No serious simulation would use such a PRNG, but for hashing, it will be enough. You only need about 1000 numbers, which is much less then the period of the last bit, even when you call rand() 5 times (for 64 bits). >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. I totally agree. Multiply with carry generators need about two lines of code (compared to one line for a LCG). Another curiosity, I want to mention. Often it seems to be stated here, that one can look for random numbers with some special properities. Like finding a sequence with a good Hamming distance in the cited text above. Such a sequence of numbers are not (pseudo) random numbers anymore, because it would not show the expected statistics for this properity! As Martin, I also found absolutly no practical difference by using different PRNGs (from simple ones to combining some of the most state of art ones). Regards, Dieter
This page took 0.01 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.