A fast PRNG for generating hash codes

[bob]

I have yet to encounter a random generator that is so poor that the Zobrist keys generated with it performs below average. If it produces all zeros, or too few bits, then it is no good, but that is about all.

I must admit I never tried to measure the performance of super-simple PRNG like (seed *= 0x10003)>>16 for a 16-bit random.

The only one I have seen that fails was the old unix C library 16 bit PRNG. Even constructing 64 bit signatures via or'ing 4 16 bit values together faired poorly. I don't even use one today for my Zobrist numbers, they are statically initialized.

[hgm]

I guess the so-called 16-bit PRNG is really a 15-bit generator, avoiding negative ints. This would explain why glueing 4 together is not good enough.

[wgarvin]

I have yet to encounter a random generator that is so poor that the Zobrist keys generated with it performs below average. If it produces all zeros, or too few bits, then it is no good, but that is about all.

I must admit I never tried to measure the performance of super-simple PRNG like (seed *= 0x10003)>>16 for a 16-bit random.

The only one I have seen that fails was the old unix C library 16 bit PRNG. Even constructing 64 bit signatures via or'ing 4 16 bit values together faired poorly. I don't even use one today for my Zobrist numbers, they are statically initialized.

Most standard library rand() implementations are really crappy. You might end up on a system that doesn't have a crappy rand(), but... why take the chance?

Good PRNGs are small and source is freely available. Any program that needs decent pseudorandom numbers should just include its own PRNG to generate them. For zobrist keys, there's the extra benefit of getting deterministic results that are reproducible across different platforms and standard libs.

[sje]

Good PRNGs are small and source is freely available. Any program that needs decent pseudorandom numbers should just include its own PRNG to generate them. For zobrist keys, there's the extra benefit of getting deterministic results that are reproducible across different platforms and standard libs.

And those results must be reproducible if the Zobrist codes are used to index an external opening book file, assuming the requirement that a book file must be platform independent. There are endian issues here as well, and these can affect a PRNG that makes platform dependent assumptions on byte ordering.

Cautionary tale #1: In the old days of DEC pdp8 machines with a 12 bit architecture, it was no surprise to find out that the standard rand() routine had a period of -- you've guessed it -- only 2^12.

Cautionary tale #2: Seeding a good PRNG from a poorly chosen seed makes for poor results. And seeding with the time of day or time of epoch doesn't work well if the time resolution is one second and the seeding is ever done more than once a second. This happened to a simulation of mine from long ago when I found the cause of identical results of some consecutive pairs of runs.

[hgm]

I ran into case #2 in WinBoard: originally it seeded by seconds, and the random was only used for generatig FRC initial positions. Then I implemented the GUI book, and used the same random for move selection from this book. That went well until I ran into a book draw. As such a draw happens nearly instantly, the next game (run through a different instance of WinBoard, spawned by PSWBTM) was started in the same second, and thus with the same seed. The result was that about 100 games were identical book draws!

Now I seed WinBoard with milliseconds.

[Teemu Pudas]

The result was that about 100 games were identical book draws!

Now I seed WinBoard with milliseconds.

So anyone with a machine that's ten times as fast as yours is going to run into the same problem? Or what if they run [core count] copies of Winboard concurrently?

[smrf]

While actually supporting a monochrome approach for computer chess programming I am using twins of such generated 32 Bit values (serving the needs of the data model) , thus having in fact 64 Bits for to distinguish positions.

[rbarreira]

The result was that about 100 games were identical book draws!

Now I seed WinBoard with milliseconds.

So anyone with a machine that's ten times as fast as yours is going to run into the same problem? Or what if they run [core count] copies of Winboard concurrently?

More like 1000 times faster (milliseconds vs seconds). If you're running it concurrently it's extremely unlikely that the several instances will be perfectly synchronized for any significant period of time...

[hgm]

The result was that about 100 games were identical book draws!

Now I seed WinBoard with milliseconds.

So anyone with a machine that's ten times as fast as yours is going to run into the same problem? Or what if they run [core count] copies of Winboard concurrently?

Indeed, this could still be a problem. (Teemu is right, as usual, because the millisec are really fake, and increment in steps of 16 or 20.) What would you propose? I guess using the process ID in the random seed could be better.

[mar]

The result was that about 100 games were identical book draws!

Now I seed WinBoard with milliseconds.

So anyone with a machine that's ten times as fast as yours is going to run into the same problem? Or what if they run [core count] copies of Winboard concurrently?

Indeed, this could still be a problem. (Teemu is right, as usual, because the millisec are really fake, and increment in steps of 16 or 20.) What would you propose? I guess using the process ID in the random seed could be better.

Don't know about linux/macos but speaking of windows: yes it has a 16+ms granularity which sucks. Using QueryPerformanceCounter() instead should do the trick.