A fast PRNG for generating hash codes

[bob]

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.

In linux just grab "/dev/random" which is a very good random number generator... That will give you a unique seed each time you call it, unless you just use /dev/random for the numbers themselves. Note that this is not a PRNG in the normal sense of "P"...

[wgarvin]

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.

You could use QueryPerformanceCounter() and mix the low bits of whatever it returns into your seed.

[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?

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.

In linux just grab "/dev/random" which is a very good random number generator... That will give you a unique seed each time you call it, unless you just use /dev/random for the numbers themselves. Note that this is not a PRNG in the normal sense of "P"...

/dev/random does not guarantee to return data immediately. It may block if it runs out of random data until additional randomness is gathered (from the keyboard, etc.). In fact this is easy to simulate by running for example "hex /dev/random". It can remain blocked for several seconds on my system at least.

/dev/urandom (note the u) is better for any application which does not require cryptographically-random data.

[Teemu Pudas]

More like 1000 times faster (milliseconds vs seconds).

The next game vs the next 99 games, so with 16 ms it's actually slightly surprising that it didn't happen again.

I nth the QueryPerformanceCounter() suggestion.

[sje]

Seeding the PRNG:

1) Use current epoch time:

Good: simple and cheap
Bad: Must wait up to a second between seedings; few bits available

2) Use /dev/urandom

Good: simple, cheap, and plenty of bits
Bad: Not available for Windows

3) Use /dev/random

Good: simple, cheap, plenty of bits, and supposedly of cryptographic quality
Bad: Not available for Windows, can be slow and occasionally very slow

4) Use a hardware device like the one sold at http://www.entropykey.co.uk/

Good: simple, plenty of bits, and supposedly of cryptographic quality
Bad: Cost £36, every end user needs one

5) Use an Internet random bit server

Good: cheap, plenty of bits, and supposedly of cryptographic quality
Bad: Need network access, server may be down at times

[smrf]

Could following modification be useful?

Code: Select all

// setzt (Zeit-) zufällige Generator-Startzahl
U32 Tool::Randomize(void)
{
  using namespace std;

  // Zeitpuffer
  time_t thisMoment;

  // ermittle eine Startzahl aus der Systemzeit
  time(&thisMoment);

  // abhängig von Zeit und altem Seed-Zustand
  return SetSeed(Random() ^ (U32)thisMoment);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

[bob]

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.

In linux just grab "/dev/random" which is a very good random number generator... That will give you a unique seed each time you call it, unless you just use /dev/random for the numbers themselves. Note that this is not a PRNG in the normal sense of "P"...

/dev/random does not guarantee to return data immediately. It may block if it runs out of random data until additional randomness is gathered (from the keyboard, etc.). In fact this is easy to simulate by running for example "hex /dev/random". It can remain blocked for several seconds on my system at least.

/dev/urandom (note the u) is better for any application which does not require cryptographically-random data.

That only happens when you "drain" the thing (/dev/random). For a seed it works great. For a monte-carlo application, it doesn't work well at all (too slow). I would not use /dev/urandom as a pure random number generator either, again, too slow. Unless you don't need a ton of numbers (such as seeding a Zobrist array). But as I said, this is not a PRNG... Which would make it not good for Zobrist as your book would never work if you use those values...

[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?

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.

In linux just grab "/dev/random" which is a very good random number generator... That will give you a unique seed each time you call it, unless you just use /dev/random for the numbers themselves. Note that this is not a PRNG in the normal sense of "P"...

/dev/random does not guarantee to return data immediately. It may block if it runs out of random data until additional randomness is gathered (from the keyboard, etc.). In fact this is easy to simulate by running for example "hex /dev/random". It can remain blocked for several seconds on my system at least.

/dev/urandom (note the u) is better for any application which does not require cryptographically-random data.

That only happens when you "drain" the thing. For a seed it works great. For a monte-carlo application, it doesn't work well at all (too slow).

It doesn't work great if another running program drains it. Or if you are running potentially fast games as what hgm was doing.

In my opinion /dev/random should only be used when cryptographic standards of randomness are required. For everything else there's /dev/urandom which seems good enough and guarantees performance.

[sje]

Code: Select all

NAME
     random , urandom -- random data source devices.

SYNOPSIS
     pseudo-device random

DESCRIPTION
     The random device produces uniformly distributed random byte values of poten-
     tially high quality.

     To obtain random bytes, open /dev/random for reading and read from it.

     To add entropy to the random generation system, open /dev/random for writing
     and write data that you believe to be somehow random.

     /dev/urandom is a compatibility nod to Linux. On Linux, /dev/urandom will pro-
     duce lower quality output if the entropy pool drains, while /dev/random will
     prefer to block and wait for additional entropy to be collected.  With Yarrow,
     this choice and distinction is not necessary, and the two devices behave iden-
     tically. You may use either.

OPERATION
     The random device implements the Yarrow pseudo random number generator algo-
     rithm and maintains its entropy pool.  Additional entropy is fed to the genera-
     tor regularly by the SecurityServer daemon from random jitter measurements of
     the kernel.  SecurityServer is also responsible for periodically saving some
     entropy to disk and reloading it during startup to provide entropy in early
     system operation.

     You may feed additional entropy to the generator by writing it to the random
     device, though this is not required in a normal operating environment.

LIMITATIONS AND WARNINGS
     Yarrow is a fairly resilient algorithm, and is believed to be resistant to non-
     root.  The quality of its output is however dependent on regular addition of
     appropriate entropy. If the SecurityServer system daemon fails for any reason,
     output quality will suffer over time without any explicit indication from the
     random device itself.

     Paranoid programmers can counteract this risk somewhat by collecting entropy of
     their choice (e.g. from keystroke or mouse timings) and seeding it into random
     directly before obtaining important random numbers.

FILES
     /dev/random
     /dev/urandom

HISTORY
     A random device appeared in Linux operating system.

[rbarreira]

Looks like they don't require real entropy for /dev/random in Mac OS, looks like a questionable decision to me...