Author: Dieter Buerssner
Date: 09:48:14 10/30/03
Go up one level in this thread
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):
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.