Artifacts and Banishment

[Carnivean]

Originally Posted by MattB

Couldn't you take, say, the 3rd and 4th digit of the exact number of milliseconds since the last user imput, say 4 and 7, then take, in this instance, the 4th and 7th digit of the total physical memory usage of the computer at that time (in Kb). That would surely be as random as brownian motion?

The best random is to take something from outside the computer. I believe that some cyptographic systems use feedback from a port (usb, sound) that is reacting to the environment.

[AnonymousHero]

Originally Posted by Carnivean

The best random is to take something from outside the computer. I believe that some cyptographic systems use feedback from a port (usb, sound) that is reacting to the environment.

The Linux kernel does this as standard for /dev/random and /dev/urandom. Recently /dev/urandom was also made to block (but maybe it's a distro-specific thing?) until it had gathered at least N bits of entropy. You can also use the getentropy() system call. People that know much more about these things than me seem to be of the opinion that doing this yourself (i.e. as an application programmer) is a bad idea -- it's easy to inadvertently introduce a way for attackers to manipulate the entropy gathering if an attacker becomes able to control the "feedback" you're using.

Similar mechanisms exist for Windows.

Incidentally @MattB: Even for games, you'd probably want to just use one of the above mechanisms to get a game seed and periodically reset the game seed from there. In fact, you could probably just get all your random numbers from /dev/urandom (or equivalent) since it should be plenty fast enough for any game needs. However, I believe Angband actually relies on having a consistent RNG throughout the level (for loading/saving) and for the town -- or at least it did in the past. I'm not sure if that was changed during 4.0.

It doesn't matter much for games, but it's also interesting to note that reseeding is critical when doing fork() for any application which cares about the cryptographic qualities of its RNG. If you don't you're going to get two endless streams of identical numbers from then on. This is partciularly nasty if you're writing a library (e.g. LibreSSL) since you may not be in control of forking.

[AnonymousHero]

Originally Posted by MattB

Couldn't you take, say, the 3rd and 4th digit of the exact number of milliseconds since the last user imput, say 4 and 7, then take, in this instance, the 4th and 7th digit of the total physical memory usage of the computer at that time (in Kb). That would surely be as random as brownian motion?

That's only (log_2 10)^2 + \epsilon bits of entropy. (The amount of physical memory is almost certainly going to be 2^n for very limited values of n. Which reduces entropy of that part to something negligable -- I won't bother doing an actual calculation )

Sufficient for games (probably), but not anything serious .

[quarague]

Originally Posted by MattB

Couldn't you take, say, the 3rd and 4th digit of the exact number of milliseconds since the last user imput, say 4 and 7, then take, in this instance, the 4th and 7th digit of the total physical memory usage of the computer at that time (in Kb). That would surely be as random as brownian motion?

Actually, that works fairly well with some slight modifications. I seem to recall that several random number generators use the time since 1.1.1970 at Midnight in seconds (or something similar) as input, hit it with a bunch of high powered maths and then get a random number between 0 and 1 out of it. Of course, from some perspective this is not random at all, but in practice it is sufficiently random for almost all practical applications. In particular it can't be predicted, ie if you observe the random numbers for a while you can't predict the next ones.

[MattB]

Originally Posted by AnonymousHero

However, I believe Angband actually relies on having a consistent RNG throughout the level (for loading/saving) and for the town

Ah, didn't consider that. It makes sense though. Shows what I know...

[AnonymousHero]

Originally Posted by quarague

Actually, that works fairly well with some slight modifications. I seem to recall that several random number generators use the time since 1.1.1970 at Midnight in seconds (or something similar) as input, hit it with a bunch of high powered maths and then get a random number between 0 and 1 out of it. Of course, from some perspective this is not random at all, but in practice it is sufficiently random for almost all practical applications. In particular it can't be predicted, ie if you observe the random numbers for a while you can't predict the next ones.

At risk of being a party-pooper: Probably OK for games and such, for anything serious... not OK.

(See my other comment.)

EDIT: Alright, I'll elaborate a little bit. Time-in-seconds since 1970 only spans... let's see... about 2 billion numbers (until 2038 or so). That's something that can easily be brute-forced these days. To avoid brute force you need something like 2^64 or, even better, 2^128. Computers are well-powerful, but they can't beat exponentials!

[AnonymousHero]

Originally Posted by MattB

Ah, didn't consider that. It makes sense though. Shows what I know...

Don't feel bad. This stuff surprisingly deep and even my shallow knowledge of the subject took about 5-10 years of casual picking-up during my otherwise regularly scheduled CS education .

EDIT: I should also say... you got the right basic idea in that you want some externally random data to mix into your "predictable" randomness. These days good random number generators are basically based on encryption: You use a small amount of "real" random data (entropy) and use that as a key for an encryption algorithm (in CTR mode, so it's encrypting 0, 1, 2, 3...) and have that algorithm pump out endless streams of data based on that initial truly random seed. This is what /dev/random and /dev/urandom and getentropy() and GetEntropy(), etc. do.

[MattB]

Originally Posted by AnonymousHero

At risk of being a party-pooper: Probably OK for games and such, for anything serious... not OK.

Isn't this a forum about a game, though?

Although it has got me thinking that maybe I am wrong about what this forum is for. I reckon it's either that:

i) This forum is in code and it's actually about government-level cryptology and everyone, except me, is in on it.

or, more likely:

ii) We are all part of the dreaded RNG. In some kind of Arthur Dent way, we (the forum) exist solely to blindly churn out the very Random Numbers that we battle against daily. Every character of text that we input is converted into hexadecimal and forms, at the next release, the 'random' number string that is used to obliterate our @'s. Meanwhile Nick is laughing maniacally in some Magrathean lair in Australia...

[Derakon]

There's two main uses for randomness: security and videogames. In security, if someone can figure out the random number(s) you used, then they can pretty quickly break your encryption, rendering it useless. Having "strong" randomness is thus vitally important. In videogames, it matters less -- the main thing you want is for the player to not notice that sequences are repeating. Basing your randomness off of hard-to-predict stuff like "milliseconds since 1970-01-01 00:00:00" or "milliseconds between program start and player's first input" is generally good enough. Sure, the player could hypothetically manipulate the game by adjusting their system clock or via very carefully-timed inputs, but practically speaking nobody cares.

Unless of course your game has online leaderboards and is popular.

[AnonymousHero]

Originally Posted by MattB

Isn't this a forum about a game, though?

Although it has got me thinking that maybe I am wrong about what this forum is for. I reckon it's either that:

i) This forum is in code and it's actually about government-level cryptology and everyone, except me, is in on it.

or, more likely:

ii) We are all part of the dreaded RNG. In some kind of Arthur Dent way, we (the forum) exist solely to blindly churn out the very Random Numbers that we battle against daily. Every character of text that we input is converted into hexadecimal and forms, at the next release, the 'random' number string that is used to obliterate our @'s. Meanwhile Nick is laughing maniacally in some Magrathean lair in Australia...

Brilliant! Thanks for that!

Sometimes us programmer types do diverge a little bit off-topic .