-
-
Yes. Strictly speaking the RNG is actually a PRNG -- that is, a "Pseudo-Random Number Generator"; not actually random. It generates results that look random to a human, but are actually entirely deterministic. And this is true for almost all programs in use. Computers do not innately have any source of randomness; all of their processes are deterministic. You must provide some outside input for there to be something "truly random". Some examples of this:
* Adjust the RNG based on the exact time at which the program is launched (for computers that have an externally-set clock). But the RNG is deterministic from here on.
* Start from a fixed state, but adjust the RNG very quickly (e.g. 60x/second) while waiting at the starting screen; it is unlikely that the user will wait exactly the same time before starting the program every time. But the RNG is still entirely deterministic.
* Adjust the RNG based on the timings and values of the user's inputs. Still deterministic -- if the user provides the same inputs at the same times they will get the same results. But hard to manipulate.
* Connect a module to the computer that provides randomness by measuring e.g. the movement of particles with a laser (Brownian motion). This approach is of course very rare as it requires special hardware, but can be useful for highly-secure systems that need to be unpredictable, because it actually is random.
I hang out in a forum dedicated to the creation of "tool-assisted speedruns" of videogames, where the community members strive to generate the sequences of inputs that will complete a game as quickly as possible, without the limitations of how precisely and quickly an actual human can generate those inputs. They mostly focus on console games which start up with a known state; by running the game within an emulator they can examine the state of memory, including of the RNG, and thereby arrange things such that the random numbers they need naturally occur exactly when they are needed. For example, in a fight the opponent always misses and the player always gets critical hits. This isn't done by "cheating" (by forcing the RNG into a specific state), but rather by knowing the process by which the RNG generates numbers and making certain that the inputs to the RNG and the timing used to "consume" its numbers result in the desired outcomes.Comment
-
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?
Alternatively, all Angband players should all be able to remotely access ERNIE!
P.S. my favourite bit of that wikipedia article is "the draw is only valid if it is statistically random". What does that mean??!Comment
-
One for the Dark Lord on his dark throne
In the Land of Mordor where the Shadows lie.Comment
-
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.Last edited by AnonymousHero; June 19, 2015, 05:55.Comment
-
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.
Comment
-
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.Comment
-
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!Last edited by AnonymousHero; June 19, 2015, 22:38.Comment
-
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.Last edited by AnonymousHero; June 19, 2015, 22:54.Comment
-
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...Comment
-
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.
Comment
-
Brilliant! Thanks for that!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...
Sometimes us programmer types do diverge a little bit off-topic.
Comment
Tweet
Comment