Archived from groups: rec.games.roguelike.development (
More info?)
Ray Dillinger wrote:
> neokosmos@gmail.com wrote:
> > If you are only working with 32 or 64 bit integers, a linear
> > congruential generator would probably work well enough. A linear
> > congruential generator is one that satisfies the following
recurrence:
> >
> > x_n+1 = ax_n + b mod m.
>
> This is false. Roguelikes use numbers in sequences; With a LCG,
> the sequence repeats too quickly. In practical terms, if you
> have a lot of "layered" probability rolls, then you will quickly
> "run out of numbers" and your probabilities will become skewed
> or, in the worst case, predetermined.
>
> Use the Mersenne Twister code, or even a lagged-fibonacci generator
> with a long period.
>
> See the "what's wrong with the Random Number Generator that came
> with my system?" part of the FAQ.
I have two comments about the FAQ.
1. It took forever to find it searching Google groups, mostly due to a
certain poster/Genrogue creator having the string "FAQ" in his .sig.
At the very least, I'd suggest the author or current maintainer make a
monthly posting so it shows up highly ranked on such a search.
2. The section on RNG's is pure hogwash.
I don't think 1 will generate a lot of controversy, so I'll focus on 2.
First, let me concede that, as far as theoretical properties of the
output stream go, MT is going to kick the pants off of x_n+1 = 16807
x_n + 2147483647. Where the LCG is going to win is in speed and ease
of implementation, because it's so simple.
I'd also like to correct a mistaken assertion in my previous post.
While this LCG does have a period of 2**31-1, it is *not* suitable for
generating 32-bit pseudorandom numbers. The reason is that, since it
has period 2**31-1 and the outputs range from 0..2**31-1, you can never
get a repeating subsequence such as "1, 1", which is something you
would want from a PRNG! Proper use of this generator would be to take
the top 16 bits and use it as a 16-bit PRNG (which would still have a
period of 2**31-1).
Now, on directly to the FAQ entry.
Let's say we have a particularly bad system PRNG with a period of
2**31-1 (and, thus, 32 bits of state). Essentially, what this means is
that there are 2**31-1 possible games that your roguelike's code can
produce, modulo user actions. (Obviously, for example, choosing to be
one class versus being another class can significantly affect the
outcome and unfolding of a game.)
Let me think. When was the last time I played a game 2**31-1 times?
How about... never?
What if the PRNG did repeat on me? The significance of the value
0xDEAD is going to be quite different in the context of the level
generation algorithm than in the context of the combat system.
Furthermore, even with a period of 2**31-1, it'll take an awful long
time to get the PRNG to repeat. If, calling the PRNG takes 1
microsecond (10**-6 sec), in order to make it repeat, you'd have to
spend 35 minutes doing nothing but calling the PRNG and discarding the
result.
What is the PRNG used in nethack? On Linux, cygwin, windows, and
MacOS, by default (that is, if you don't edit any header files other
than #defining the appropriate system platform macro), it's... lrand48,
a LCG with modulus 2**48. I have not verified it, but, assuming the
constant terms are chosen correctly, its period should be 2**48. Now,
nethack does have some random number generation problems, but those
problems are really in how the generator is used rather than the
generator itself. When was the last time you saw a post on
r.g.r-l.nethack saying the PRNG was "too predictable"?
In principle, the FAQ entry is correct, though. If I knew all the
probabilities involved, and which PRNG algorithm was being used, there
is the possibility I could deduce where in the pseudorandom number
stream the generator currently was, and, therefore, predict the future
output of the generator. The size of this problem is inversely
proportional to the length of the PRNG period. That is, using a simple
LCG with period 2**31-1, I'm more likely to be able to, in principle,
carry out this operation, than if I am using the MT algorithm with a
period of 2**19937-1. It's a simple consequence of the fact that the
MT's period is 10**5992 times longer.
(Note: one can mitigate this (theoretical) problem quite a bit by using
several independently seeded PRNGs for different subsystems of the
game. For example, one can use a combat PRNG, a level-generation PRNG,
an item-generation PRNG, etc. It's also quite possible to construct a
LCG with period 2 ** 19937-1, but I don't know how its efficiency would
compare to MT.)
Has anyone done this analysis for nethack? Why? Because it's too hard
to be worth it. There are easier ways to cheat.
Various people over time have created patches for nethack which replace
the PRNG with a stronger one, such as MD4. None have made it into the
3.4.3 source tree. Why? Because lrand48 is generally good enough.
Finally, if you want a REALLY long period PRNG, MT is small potatoes.
There exist efficient, well-tested PRNGs with periods up to 2**131086.
[3] I'll provide the C source here (credit to Dr. Marsaglia):
static unsigned long Q[4096],c=362436;
unsigned long CMWC4096(void){
unsigned long long t, a=18782LL;
static unsigned long i=4095;
unsigned long x,r=0xfffffffe;
i=(i+1)&4095;
t=a*Q
+c;
c=(t>>32); x=t+c; if(x<c){x++;c++;}
return(Q=r-x); }
In summary: If you're doing Monte Carlo simulations that sample from a
random variate hundreds of billions of times, don't use a LCG. If
you're writing a roguelike, feel free to use lrand48, or the system RNG
(which is probably lrand48 on most common systems, anyway.)
References:
[1] Knuth, _The Art of Computer Programming_, vol. 2 has discussion of
PRNGs.
[2] Nethack source (rnd.c, unixconf.h, and ntconf.h)
[3] http://groups-beta.google.com/group/sci.math/msg/9959175f66dd138f ,
a message by Dr. George Marsaglia, a well-known PRNG researcher, who
compares choosing the "best" PRNG to picking a "best" in the Miss
America contest. 
Also the source for the C source posted above.
[4] http://www.paulm.org/random.html . Additional discussion of
criteria for choosing PRNGs.
Facebook
Twitter
Instagram