5 ms·

I don't understand much of crypto... But I am game developer, and game developers (specially RPG fans) love random numbers. Some games of mine, I suspected so

by speeder 13y ago

I don't understand much of crypto... But I am game developer, and game developers (specially RPG fans) love random numbers. Some games of mine, I suspected something was off with the PRNG, and did something like they did on the ending, I used the random number generator to draw pictures. Biased generators were quite obvious, because they made obvious patterns (one of the worst offenders was C default random function on the mingw that came with Dev-Cpp, instead of drawing noise, or weird noise, it drew diagonal lines... yes, LINES, it became clear to me that it was terrible...) In the end I choose Mersenne Twister, it is a very good PRNG... For games that is, although the Mersenne Twister does generate random looking numbers, its author claim it is bad for crypto, Mersenne Twister, I don't remember why, can be predictable enough for anti-crypto.

mistercow 13y ago
> its author claim it is bad for crypto, Mersenne Twister, I don't remember why Because after observing a certain number of outputs, you can completely predict its subsequent outputs.
- marshray 13y ago
  Yep. Plus, MT uses a huge amount of memory. I don't see any reason to use it any more now that modern stream ciphers have gotten so fast.
  - tptacek 13y ago
    It is the unfortunate de facto standard for built-in noncryptographic RNGs in high-level languages. PHP, Python, and Ruby all rely on MT generators (all 3 have real CSPRNGs too).
    - marshray 13y ago
      Quick, somebody start the NoTwister movement.
nikic 13y ago
MT is not suitable for crypto because after observing 637 values you can predict all further values. 637 is the size of MTs internal state vector and the output of MT are basically just values from that state vector run through a tempering function. That tempering function is invertible, thus by looking at 637 values you get the full state vector, at which point you can generate the next values as usual.
- axman6 13y ago
  That's a great answer, thanks for that!
  - tptacek 13y ago
    You should definitely actually try to clone an MT instance sometime. It's illuminating, and just tricky enough to be fun without being frustrating.
- adobriyan 13y ago
  624 values are enough.
Jach 13y ago
Even for RPG games, any given PRNG can often be too random for a game. You can make a lot more realistic and enjoyable behaviors by grabbing your random values from a distribution other than uniform 0.0-1.0. (Like a Gaussian distribution, which is everywhere in models of random things that are the sum of many other individual random processes.)
- eterm 13y ago
  random and uniform are different things. a PRNG isn't "too random", that doesn't make sense. If it's too uniform, sample from other distributions, but to do so usually requires taking output from a PRNG. Indeed using the inverse CDF of any distribution is a map from (0,1) to the desired sample space, following the distribution. As for which PRNG for RPG games, MT is very good because while it isn't cryptographically secure, it otherwise has a very long period and delivers very nicely distributed numbers as well as being very fast. For non-crypto applications such as monte-carlo, there's little reason to use much else.
  - Jach 13y ago
    By "too random" I mean that for games, one often wants "predictable randomness" rather than unpredictable randomness, and a stock PRNG or MT can be too unpredictable. (Which is generally good, but not always for games. Or for candy; the colors of M&M's aren't distributed equally.) Picking your random values from a distribution is one way to make them predictable and more life-like. e.g. if you have a target shooting AI, using a built-in rand() function to select an angle and radius on the target is probably okay for the angle, but using it on the radius will give you a bad-looking spread. Whereas a Gaussian-selected radius will look more natural with most of the shots clustered close to the center, and it lets you easily fine-tune the AI's accuracy by adjusting parameters of the Gaussian. Alternatively, some sets of random values don't look random to humans, so as a game developer you might need to tweak it and make it appear more random to the player. e.g. these are some truly random bits from Hotbits (not a PRNG: https://www.fourmilab.ch/hotbits/secure_generate.html https://www.fourmilab.ch/hotbits/secure_generate.html): '001101010011001011001000010100011010011111000001111101010011000111010000111000001011111000111011'. My pattern-matching human brain is annoyed by runs longer than 3 or 4 times, and patterns like 000111 and 111000. If you take time to filter out 'annoyances' you can make the player like your game more, and if you're careful you can do it without decreasing the entropy bits per byte too much.

by speeder 13y ago

mistercow 13y ago

> its author claim it is bad for crypto, Mersenne Twister, I don't remember why Because after observing a certain number of outputs, you can completely predict its subsequent outputs.

marshray 13y ago
Yep. Plus, MT uses a huge amount of memory. I don't see any reason to use it any more now that modern stream ciphers have gotten so fast.
- tptacek 13y ago
  It is the unfortunate de facto standard for built-in noncryptographic RNGs in high-level languages. PHP, Python, and Ruby all rely on MT generators (all 3 have real CSPRNGs too).
  - marshray 13y ago
    Quick, somebody start the NoTwister movement.

nikic 13y ago

MT is not suitable for crypto because after observing 637 values you can predict all further values. 637 is the size of MTs internal state vector and the output of MT are basically just values from that state vector run through a tempering function. That tempering function is invertible, thus by looking at 637 values you get the full state vector, at which point you can generate the next values as usual.

axman6 13y ago
That's a great answer, thanks for that!
- tptacek 13y ago
  You should definitely actually try to clone an MT instance sometime. It's illuminating, and just tricky enough to be fun without being frustrating.
adobriyan 13y ago
624 values are enough.

Jach 13y ago

Even for RPG games, any given PRNG can often be too random for a game. You can make a lot more realistic and enjoyable behaviors by grabbing your random values from a distribution other than uniform 0.0-1.0. (Like a Gaussian distribution, which is everywhere in models of random things that are the sum of many other individual random processes.)

eterm 13y ago
random and uniform are different things. a PRNG isn't "too random", that doesn't make sense. If it's too uniform, sample from other distributions, but to do so usually requires taking output from a PRNG. Indeed using the inverse CDF of any distribution is a map from (0,1) to the desired sample space, following the distribution. As for which PRNG for RPG games, MT is very good because while it isn't cryptographically secure, it otherwise has a very long period and delivers very nicely distributed numbers as well as being very fast. For non-crypto applications such as monte-carlo, there's little reason to use much else.
- Jach 13y ago
  By "too random" I mean that for games, one often wants "predictable randomness" rather than unpredictable randomness, and a stock PRNG or MT can be too unpredictable. (Which is generally good, but not always for games. Or for candy; the colors of M&M's aren't distributed equally.) Picking your random values from a distribution is one way to make them predictable and more life-like. e.g. if you have a target shooting AI, using a built-in rand() function to select an angle and radius on the target is probably okay for the angle, but using it on the radius will give you a bad-looking spread. Whereas a Gaussian-selected radius will look more natural with most of the shots clustered close to the center, and it lets you easily fine-tune the AI's accuracy by adjusting parameters of the Gaussian. Alternatively, some sets of random values don't look random to humans, so as a game developer you might need to tweak it and make it appear more random to the player. e.g. these are some truly random bits from Hotbits (not a PRNG: https://www.fourmilab.ch/hotbits/secure_generate.html https://www.fourmilab.ch/hotbits/secure_generate.html): '001101010011001011001000010100011010011111000001111101010011000111010000111000001011111000111011'. My pattern-matching human brain is annoyed by runs longer than 3 or 4 times, and patterns like 000111 and 111000. If you take time to filter out 'annoyances' you can make the player like your game more, and if you're careful you can do it without decreasing the entropy bits per byte too much.