Author: Robert Hyatt
Date: 10:09:15 10/30/03
Go up one level in this thread
On October 30, 2003 at 12:48:14, Dieter Buerssner wrote: >On October 30, 2003 at 10:59:59, Robert Hyatt wrote: > >>So? You are adding yet another constraint that nobody had to start with. >>I said "with my Numerical Recipes" RNG." >> >>But for Zobrist hashing, the MS rng will work just fine. > >I agree, here. It might be more difficult, to get it right, however. See for >example Bruce's code on his page, which can give different results with the same >compiler, depending on compiler options. A further complication may be, that >RAND_MAX will vary from compiler to compiler. It even is not guaranteed, that >RAND_MAX+1 is a power of 2. > >>You only need a >>total of 768 RNG's. I don't know of any 32 bit RNG with a period that >>short, or that produces badly non-random numbers in the first 1500 numbers. >>Even the old C library random(), ran() and rand() calls work just fine >>there, although I suggest using the one in Crafty's source as it is a known >>good generator with a very long period. > >You repeated this several times, but it is not true. It is actually known as a >rather bad generator (I don't think it matters at all for Zorbrist hashing). > >Actually, it is a generator, where failure can be seen with only 500 (!) calls >to it. It fails Marsaglia's duplicate birthday test big time (simulating some >statistics about duplicate birthday spacings with only 500 calls to the PRNG, >the result is *very far* from what is expected by an analytical formula. Good >PRNGs have no problem with this test). It also fails some tests on randomness >designed by myself - but they need more calls to the PRNG (but not necessarily a >really big number). A sample output (I copied the PRNG from Crafty 17.14 >utility.c): OK. I haven't run that test. I have tested for runs up and down, the poker test, test for uniformness, for cycles, etc. It has never failed a single one of those... > >DUP. BIRTHDAY SPACINGS TEST, M= 256 N=2**23 LAMBDA= 0.5000 sample size 500 > bits sum chi^2 dof p > 1 to 23: 2817.96 3 1.000000 > 2 to 24: 1329.79 3 1.000000 > 3 to 25: 1352.03 3 1.000000 > 4 to 26: 1344.82 3 1.000000 > 5 to 27: 1210.38 3 1.000000 > 6 to 28: 1100.29 3 1.000000 > 7 to 29: 1031.66 3 1.000000 > 8 to 30: 1317.93 3 1.000000 > 9 to 31: 831.49 3 1.000000 > 10 to 32: 1034.34 3 1.000000 > average: 12908.80 3 1.000000 > av = 1.46 (diff = 0.964) sig = 0.145 T-test yields 1.000000 > Uni test for 10 pvalues: AD-test 1.0000000 KS-test 1.0000000 > >In the above test, 500 calls to the PRNG were done, of which 23 bits were used. >The test was repeated 10 times, using different bit positions of the output of >the PRNG. > >A Poisson distribution with lambda = 0.5 is expected. Simulation with the lagged >fibonacci generator you use gives lambda = 1.46. The p-values in the table above >should be not close to 0 or 1 for a good generator. The failure can be >reproduced easily. Also it fails all different parametrizations of the duplicate >birthday spacing test. All decent PRNGs have no problem at all with this test. > >So, it shows, that even for rather simple simulations, this specific PRNG should >not be used. > >BTW. I think Knuth suggested the PRNG you use with subtraction instead of >addition. But it will fail the above test nevertheless. All lagged Fibonacci >generators with a not very long table (much longer than the 55) will fail the >test, when using xor, add or sub. The only exception is a lagged fibonacci >generator based on multiplication (only odd numbers can be used then, making it >a 31 instead of a 32 bit generator for typical efficient implementations). > >The same generator would also easily work on 64-bit numbers with the same code. >But it would show the same severe deficiences. > >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.