When Random isn't as Random as expected

I like to write computer games and games tend to be more fun with some random chance throw in. However I also like to write unit tests and unit tests and random behavior don’t mix very well. Fortunately is the java.util.Random class a pseudo random generator and as long as you put in the same initial value (the so called seed) you get the same sequence of ‘random’ numbers.

Perfect for use in unit tests and to have repeatable random behavior in a game.

Recently I have been developing a turn based game (MuAsDe) and for each turn I re-initialize the Random generator with that turns number as a seed, assuming that each seed value will produce a different series of numbers.

Or that’s what I thought..

It appears that an increment of one on the seed value has doesn’t always have
a dramatic impact on the sequence generated by consecutive nextDouble() calls.

In this game there is a 10% chance that the stock markets will crash this turn.
So I wrote a unit test that plays turns waiting for this to happen. To my great
surprise it took over 2000 turns for it to happen once.

Strange. That’s when I decided to have a closer look at the random generator.
I wrote a little program that produces a matrix of the turn number and the first
20 numbers produced by the Random number generator initialized with the turn
number as a seed.

The first number produced for seed values 0..2047 is always approximately 0.73
then the next numbers vary greatly, as you would expect, but at random number 10
suddenly the numbers stay around 0.90 changing slightly every new seed. After that
its all random again.

Oh dear.

If you take a closer look at the Random class the cause of this slightly less
than randomness becomes apparent. For each new random set of bits one multiplication
and addition is done (in next(int)). So a small change in seed is not guaranteed to have
a significant change in the next value. If you print those numbers in hexadecimal, you’ll see
that the most significant bits remain about the same. Let me show you:

TurnFirst SeedMSBLSBValue


Ok, so from left to right you see the turn, which gets its initial transformation into
the First seed, then when nextDouble() is called two calls are made, the first for the
most significant bits (MSB) of the double. The second for the least significant bits (LSB).
The final column holds the resulting of the ‘random’ value. The values in bold the bits
that are the same. Yes those are the first 10 bits.

Ironically the LSB appears quite random.

The conclusion? Well, I’ve stopped creating a new generator for each turn. Now I just use one
random number generator for the whole game. Its still deterministic so the
unit tests will like it, but there is no initial value blues (or, only in the first turn:)

And even when you do that, for some people java.util.Random is not random enough: Sun redefines randomness.

Those people use java.security.SecureRandom :-)

No comments:

Post a Comment