Wesnoth's RNG has statistical weaknesses

All of the people playing Battle for Wesnoth complaining about Wesnoth’s random number generator (RNG) having problems were right.

There is a test used called the “minimum distance” test which tests a random number generator by filling up a volume of space with points determined by the random number generator and determining the minimum distance between any two points. Or, in other words, we take a cube, fill it with points “randomly” by using the RNG we are testing, and make spheres of each point and the point closest to that point. The smallest such sphere is our minimum distance. We do this a number of times.

There is a range of minimum distances we should have. But, with Wesnoth’s random number generator, we don’t get that, especially in four dimensions (it also fails in three dimensions) [1]. A good randomness tester like Dieharder can readily distinguish Wesnoth’s RNG from a good RNG (such as RadioGatún).

The reason for this is because Wesnoth’ random number generator is as follows:

static int32_t state;
uint32_t mask;

state = (state * 1103515245) + 12345;
mask = (state >> 16) & 0x7fff;
return mask;

(The actual code uses division and modulo where I use a shifter and a logical and above).

This is a very simple Linear congruential generator, and is considered a rather poor RNG.

One of these years, I should submit a patch to replace Wesnoth’s junk RNG with RadioGatún. Although I have a feeling the developers will not accept it. It would, after all, be a pretty big blow to their pride to admit the RNG Wesnoth has been using for years has significant, measurable problems.

I should, before signing out, point out that Wesnoth is an excellent game and I appreciate all of the hard work done on it. I just wish the Wesnoth FAQ would stop pretending the random number generator is any good with nonsense like “programmers have examined the random number generator. No flaws have been found”. Because I found significant flaws in under an hour with Dieharder.

I should probably point out that Wesnoth’s RNG also flunks the “Diehard DNA test”.

[1] To properly test Wesnoth’s random number generator in three dimensions with Dieharder, I had to modify the random number generator to use a 32-bit unsigned integer and take the top 16 bits from the generator state (instead of using a 31-bit integer and taking 15 bits). The stream is identical if we remove the high bit from these 16-bit numbers to make them 15-bit numbers.