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:

Turn	First Seed	MSB	LSB	Value
0	5deece66d	2ec82d1	6a6ca89	0.730
1	5deece66c	2ec6b55	cdc4e6	0.730
2	5deece66f	2ecb1c8	258d5cf	0.731
3	5deece66e	2ec9a4d	47fd02c	0.731
4	5deece669	2ec24e2	742b3fd	0.730
5	5deece668	2ec0d66	169ae5a	0.730
2046	5deece193	27a94ac	7c171ba	0.619
2047	5deece192	27a7d30	1e86c17	0.619
2048	5deecee6d	3a8606e	6d3e28c	0.914
2049	5deecee6c	3a848f2	fadce9	0.914

 

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 :-)