Mersenne Whatsit?

I’ve had a few folks ask me why I implemented a custom Random Number Generator (Mersenne Twister) in my game, Heroic Adventure! This article explains why far better than I could.

From the Rec.Games.Roguelike.Development FAQ, section 37:

What’s wrong with the random number generator that came with my programming language?

Almost all programming environments come with random number generators that suck.  While they may be okay for casual use, the use of random numbers in roguelike games is anything but casual.

Most “default” PRNG’s suck by having only 32 or 64 bits of state, which means they generate a sequence of numbers either 2^32 or 2^64 long, and then repeat.

Most roguelike games feature a lot of “sequential rolling”, where further random rolls are made depending on the outcome of earlier rolls, and in this case each further roll reduces the number of possibilities for where in the cycle of numbers generated by the PRNG we happen to be.  It’s easy to literally “run out of numbers” in such a way that rolls made after a certain point in a sequence are always the same, or drawn from an artificially reduced set of possibilities, because there are a limited (or nonexistent) set of subsequences of the main PRNG sequence that could have resulted in the rolls being made.

Let’s see how this works in a dungeon scenario.  Say the player character turns over a rock.  You consult the random number generator to resolve a one in a thousand chance that there was something under the rock, and find that there is something there.

32 bits is about 4 billion numbers: that means that we are now in one of about 4 million number sequences where there would have been something under the rock.

So, what general category of item was under the rock? Back we go to our random number generator, to resolve possibilities like, it could be armor, or a weapon, or junk, or a magic item, or a treasure.  Most of what you find under rocks will be junk, but let’s say that about 2 percent of the time, including this time, it’s a magic item.  We’re now in one of just eighty thousand possible sequences out of the whole PRNG cycle that could have led to this point.

What kind of a magic item was it?  The next roll sends us to “rods, wands, and rings”, which was about ten percent likely.  Now we can tell by the fact that we’re here that we’re in one of just 8 thousand possible subsequences that could have led to this point.

Another roll sends us to the rings subtable.  Was that about 25 percent likely?  Okay, now we’re talking about one sequence chosen of about 2 thousand sequences in the cycle of 32-bit numbers that could have gotten us here.  A magic ring is under a rock.

Rings of speed are rare; let’s say that we find a ring of speed, and one ring out of every two hundred or so rings is a ring of speed.  That means there’s just ten (on average) possible sequences that could have gotten us to this point: A ring of speed is under a rock.

Finally, we roll to find the ring’s bonus.  But no matter how many possible results there are in our table, or what probabilities they’re assigned, there are only ten (approximately) 32-bit numbers that could follow all the other 32-bit numbers that have led here, thus only ten results are possible and all probability distribution on this table is in increments of ten percent, no matter what it says in your code.

You may think this example is contrived; but it’s not. In fact, it’s oversimplified, and most roguelikes will constrain things even further.  The problem here is with the short period of the PRNG.  It repeats after a cycle of just 2^32 trials, and when we are sequential rolling, we can quickly winnow out all possibilities of where on the cycle we are.

There’s another problem too; Lots of c-library PRNG’s suck in a particularly amazing way by having very short cycles in their low-order bits. When these are taken modulo small numbers, as is the naive approach for simulating die rolls, patterns quickly emerge and sequential rolling becomes ridiculous. For example, a coin toss simulated by taking the PRNG output modulo 2, if your PRNG has this bug, would give an endless series of alternating heads and tails, which don’t seem very random at all.  If you get a good PRNG to start with, the modulo construction shouldn’t hurt you; but if you are at all uncertain, use scaled division instead.

In fact, lots of roguelike games in the past have behaved so differently under different random number generators that the balance and playability, inadvertently tuned to a particular generator, was upset.

If you don’t want to have a problem running out of numbers after a long sequence of dependent rolls, then you need to provide a *GOOD* random number generator that takes a long time (way longer than 4 billion numbers) to cycle.

I like a lagged-fibonacci generator, as described in Knuth v2, as a pseudorandom generator that is fast, apparently avoids detectable patterns, and has a very long period.

The Mersenne Twister is almost as fast and its output is very good.  Lots of people prefer it because we can prove more about its properties.

But there’s lots of code for good PRNG’s floating around the net these days, much of it borrowed from the cryptography or simulations communities.  You don’t really need cryptographic PRNG’s, and they are mostly slow.  But there are some very good PRNG’s made for simulations (like the Mersenne Twister) that are both fast, and strong in precisely the ways we need PRNG’s for roguelike games to be strong.

Tinggalkan komentar