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 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.