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

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

In my context, they are equal. But they are only useful for obtaining a random seed, or perhaps for book randomness. They are not good for Zobrist randoms...

[bob]

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

I suspect it depends. Who in their right mind does real crypto work on a mac? Linux has run on big and small systems and might well be chosen for that...

[rbarreira]

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

I suspect it depends. Who in their right mind does real crypto work on a mac? Linux has run on big and small systems and might well be chosen for that...

Anyone who wants to generate a RSA key pair for private use for example.

In my context, they are equal. But they are only useful for obtaining a random seed, or perhaps for book randomness. They are not good for Zobrist randoms...

You can keep saying that, but it won't stop the fact that using /dev/random leaves you exposed to a potential delay of several seconds in your program for no good reason (unless you are doing something crypto related, in which case the delay is justified). Whether this delay happens or not depends not only on how many bytes you request, but also on whether other programs running on the computer are doing it too.

This is not a theoretical problem, it's very easy to demonstrate in practice by running something like "hex /dev/random" from a Linux console.

Under Linux /dev/urandom also returns true randomness from the same entropy pool that /dev/random uses (if available), so the numbers won't be any worse than in the case that /dev/random wouldn't have blocked.

[bob]

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

I suspect it depends. Who in their right mind does real crypto work on a mac? Linux has run on big and small systems and might well be chosen for that...

Anyone who wants to generate a RSA key pair for private use for example.

That (a) doesn't require a bunch of random numbers and (b) is not "time critical". I don't see the connection...

In my context, they are equal. But they are only useful for obtaining a random seed, or perhaps for book randomness. They are not good for Zobrist randoms...

You can keep saying that, but it won't stop the fact that using /dev/random leaves you exposed to a potential delay of several seconds in your program for no good reason (unless you are doing something crypto related, in which case the delay is justified). Whether this delay happens or not depends not only on how many bytes you request, but also on whether other programs running on the computer are doing it too.

How often do you seed your PRNG in a chess engine? Once, at most, and generally not at all?

We already expect a _several_ second delay at engine startup if EGTBs are used, On my linux box, od -x /dev/random never blocks for more than 1-2 seconds, and that only if I first drain all the existing numbers...

This is not a theoretical problem, it's very easy to demonstrate in practice by running something like "hex /dev/random" from a Linux console.

Under Linux /dev/urandom also returns true randomness from the same entropy pool that /dev/random uses (if available), so the numbers won't be any worse than in the case that /dev/random wouldn't have blocked.

[rbarreira]

That (a) doesn't require a bunch of random numbers and (b) is not "time critical". I don't see the connection...

a) Wrong. How do you generate a unique key pair without a source of randomness?
b) Who said it's time critical? You are confusing two parts of the debate. I was making a point about Mac OS's lack of cryptographic random numbers in /dev/random for this part of the discussion.

How often do you seed your PRNG in a chess engine? Once, at most, and generally not at all?

If you do it once a game, taking a few seconds unnecessarily is sub-optimal especially if you're running lots of fast games.

Seriously, what's your argument for requiring cryptographically-safe random numbers to seed a PRNG for a chess program?

We already expect a _several_ second delay at engine startup if EGTBs are used

How does that make it OK to waste several more seconds to get a PRNG seed which could be gotten in essentially zero time? Ridiculous...

[sje]

There is some enlightenment here: http://en.wikipedia.org/wiki//dev/random

[bob]

That (a) doesn't require a bunch of random numbers and (b) is not "time critical". I don't see the connection...

a) Wrong. How do you generate a unique key pair without a source of randomness?

What part of "doesn't require a bunch of random numbers" is unclear? How often do you re-compute the pairs (as in using say SSH)? Once every blue moon or two???

b) Who said it's time critical? You are confusing two parts of the debate. I was making a point about Mac OS's lack of cryptographic random numbers in /dev/random for this part of the discussion.

I simply pointed out that that aspect is pretty much unimportant. You won't use "enough" of the /dev/random values on MacOS to encounter a problem, IMHO. If you block a time or two, who cares? You don't do that kind of operation very often. We don't need those kinds of randomness guarantees to seed a PRNG, period. We just need something that changes all of the bits on occasion, not just the high-order bits such as using a system timer with poor resolution.

How often do you seed your PRNG in a chess engine? Once, at most, and generally not at all?

If you do it once a game, taking a few seconds unnecessarily is sub-optimal especially if you're running lots of fast games.

I do not do it, ever. I don't see any reason to do so, given an effective PRNG to provide opening book randomness. All I do is burn the first N numbers, where N is a random number that could come from the system clock or whatever.

Seriously, what's your argument for requiring cryptographically-safe random numbers to seed a PRNG for a chess program?

I don't require that at all. My point was that whether you use /dev/random or /dev/urandom probably doesn't matter to a chess engine.

We already expect a _several_ second delay at engine startup if EGTBs are used

How does that make it OK to waste several more seconds to get a PRNG seed which could be gotten in essentially zero time? Ridiculous...

Not all linux kernels have /dev/urandom. Ditto for other older systems... I was responding to the idea of using /dev/random, generically, as an easy solution to seed a PRNG, if one desires to do that.

[rbarreira]

Bob, again you are confusing two different things. The Mac OS /dev/random does NOT block, it does not require true entropy so it's equivalent to /dev/urandom. Therefore it is not good enough for crytographic purposes, which YES, can be important on a Mac despite your earlier statement that no one "in their right mind" would do anything crypto-related there.

It's pointless for me to keep replying when you didn't even read the documentation posted earlier by Steven, and don't make any effort to read my points. Instead you keep replying to things no one said.

[bob]

Bob, again you are confusing two different things. The Mac OS /dev/random does NOT block, it does not require true entropy so it's equivalent to /dev/urandom. Therefore it is not good enough for crytographic purposes, which YES, can be important on a Mac despite your earlier statement that no one "in their right mind" would do anything crypto-related there.

It's pointless for me to keep replying when you didn't even read the documentation posted earlier by Steven, and don't make any effort to read my points. Instead you keep replying to things no one said.

OK, my take on this. In linux, as is well-known, /dev/random gives better numbers, but can lag and block if you ask for too many/ /dev/urandom does not block (although it is still slow) but gives a weaker stream of random numbers.

In MacOS, both are the same.

Again, who cares? Nobody is going to need crypto-standard random numbers on a Mac. Regardless of what you are "guessing". You don't need that level of random numbers to produce public/private key pairs and such. Mac's are _not_ going to be used by the true crypto crowd to do any heavy work with really long and independent random numbers.

In chess, the chances of /dev/random blocking on linux are essentially zero. Nobody is continually draining it unless you take a really large box (say a 64 processor alpha box or something similar) that might actually be used by the crypto guys. But in chess, not going to happen, if all you want is to seed a PRGN with a different number each time you play a game. I will say it again, in chess, /dev/random is _not_ going top block. Because nobody is going to play chess and be generating tons of random numbers via /dev/random. If you do that, good. That is what, one machine out of maybe 500 million on the planet?

I have used /dev/random many times to get a seed over the years, or to get an n bit number so that I can burn the first N random values from my PRNG so that I start at a different place for book randomness. Never had it block, or cause me any delay of any kind. Because as I said, nobody is using these machines for that kind of work to any measurable extent.

Your worry is "way out there" on the far edge of any significant probability...

Most don't seed things this way at all. But it will work just fine...

[rbarreira]

If you think that end users generating crypto keys don't need cryptographically-safe random numbers (which is a contradiction, but ok...) surely you also agree that these random numbers are overkill for chess.

My whole point can be stated very simply. Using /dev/random for chess or most other applications cannot be better than using urandom because it will either return numbers with equal quality to urandom (same source), or block. To realize this you only have to be able to read the relevant man page.

It's not about probabilities, it's about simple logic and avoiding unneeded problems when no advantages are gained. This is a core principle of quality in programming.