Testing Civ4's Random Number Generator

[ruff_hi]

There has been talk about the Civ4 Combat Odds and RNG

http://forums.civfanatics.com/showthread.php?t=336088

However, the whole discussion is based on the assumption that the random number generator is 'good'. As mentioned in the thread above, any series of numbers is as random as any others. The following coin toss sequences each have exactly the same probability of occurrance ...

• HHTTHTTH
• TTHHTHTT
• HHTTHHHH
• THTTHTHT

Over time, there is the expectation that the number of heads and the number of tails will balance out. There is no single statistical test that we can use to determine if a series of numbers is random or not. However, there are ways of judging if a series of numbers appears to be non-random. Lets see how Civ4's random number generator (RNG) does.

I used the following code (in BUG's logger) to generate 5000 pairs of random numbers ...

for i in range(1,5001):
    i1 = gc.getASyncRand().get(1000, "")
    i2 = gc.getASyncRand().get(1000, "")
    message = "%i, %i, %i" % (i, i1, i2)
    Logger.writeLog(message)

Then I dumped the resulting numbers into excel and generated some graphs.

Test 1 - is the observed average close to the expected average?
I calculated a moving average over 250 numbers. The expectation is that the average will be 500. Here is the result ...



You'll note that the average is quite lumpy but it does bounce around the 500 mark ... sometimes a little low, sometimes a little high. If anything, the blue line is probably on the low side more than the high side. Looking over 250 random numbers for an average is probably not sufficient (too much noise / randomness).

An Aside About Random Number Generators
Computers are good at generating lots and lots of numbers. Give them a formula, plug in the inputs and you get the output. Change the input and you change the output. Put in the same inputs and you get the same output. So ... how are random number sequences generated? Well, there are a number of methods that I will not cover here, but the interested person can check wikipedia (http://en.wikipedia.org/wiki/Random_number_generation). A summary of the computational method is that the random sequence can be thought of as a very very long chain of numbers that loops around to the starting position. You provide a seed to the RNG - a starting link in the chain - and then go from there, 1 chain at a time until you loop back to your starting position. Most RNGs have very long return periods. Ideally, each link the chain will be a number such that the series of numbers appears random.

Right - enough of the lesson, back to the graphs. Here is the same graph as above, but using a moving average of 750 numbers ...



You'll notice that the lines are much smoother, closer to 500 but still are not exactly equal to 500 all the time. Again, the blue line looks a little low.

Examining these two graphs, there is nothing to say that the series of 500 pairs do not appear non random. I would have to say that Civ4's RNG passes Test 1.

Test 2 - Is there a pattern between 1 number and the next?
The way to test this is to create a scatter plot of one number v the next number. If there is a relationship, then you will see clumping in the scatter plot.



Note: that this is a 1000 v 1000 plot (and the x axis is longer than the y axis - stupid excel) that only has 5,000 plots (out of 1,000,000). Based on this data, I cannot see any pattern between one number and the next.

Test 3 - Runs of numbers
I counted the number of sub-500 numbers (or over-500 numbers) in a row. Effectively, this is the same as counting Head and Tail runs in a coin toss. If I toss a H, then I have a 50/50 chance that the next toss is a T. This means that I will have a 'run' of 1 head. So, the probability of getting a run of 1 H is 50%. The probability of me getting a run of 2 Hs or 2 Ts is 50% x 50% or 25%. 3 in a row is 50% ^ 3, etc.



You certainly cannot say that the Civ4 RNG fails this test.

 

[PieceOfMind]

Some labels on the graphs would be nice! (just kidding)

In test 1, what is the difference between the blue and purple line?

Technically speaking, Test 1 does not appear to be a statistical test but a visual test. Correct?

Test 2 is very nice to see. That is usually where LCG is most likely to have problems. It's usually called the Correlation test I think.

In test 3, what are R1 and R2? Are they two separate tests?

By the way, I'd be careful with your approach to the first graph and how you present it. I noticed you called the average lumpy in some places. The sort of data produced in that graph is very hard to judge visually and it might give some people reason to believe it's streakier than it's meant to be. Anyway, I'd be careful drawing any conclusion at all from that test, even if it is only a loose one.

EDIT...
One more thing. Regarding the first graph, do you realise that in theory it will be scale invariant? What that means is that if you did the test with more numbers (e.g. 10,000) then plotted the lot the graph would still look the same. This is not exactly intuitive as most would probably expect the "moving average" to level out eventually. In absolute terms that is sort of true - the distance from the average should approach zero. But the more trials that are done, the more opportunities there are for the "moving average" to deviate further from the mean. In other words, the probability that the moving average reaches any particular value at some point will approach 1 as the number of trials approaches infinity. I think that's right anyway - I'll have to check up on the theory.

 

[ruff_hi]

In test 1, what is the difference between the blue and purple line?

In test 3, what are R1 and R2? Are they two separate tests?

I used the following code (in BUG's logger) to generate 5000 pairs of random numbers ...

I produced 5000 pairs of random numbers (R1, R2). They produced the blue and purple lines.

One more thing. Regarding the first graph, do you realise that in theory it will be scale invariant?

Totally. It is the length of the moving average that will govern the 'lumpiness' of the resulting graph. A short length and it will jump around quite a lot ... a long average and it will become smoother.

 

[PieceOfMind]

OK a couple of things...

Firstly, I think I was mistaken about the scale invariance thing - I think it only works if the variable was normally distributed.

Regarding the first and second graphs now, it's a bit weird to pair off the numbers because you could potentially hide (or expose) fine correlation issues from the RNG. Really the sequence that came off the RNG was x1,y1,x2,y2,x3,y3,... etc.

To avoid this you could have used two for loops rather than 1.

for i = 1 to n
create R1 list

for i = 1 to n
create R2 list

 

[JonathanStrange]

Ok, something I need to examine more closely because I've often wondered about the RNG too...

 

[ruff_hi]

Regarding the first and second graphs now, it's a bit weird to pair off the numbers because you could potentially hide (or expose) fine correlation issues from the RNG. Really the sequence that came off the RNG was x1,y1,x2,y2,x3,y3,... etc.

Your list as they roll of the RNG is correct. It doesn't really matter what the step is when pulling numbers off a RNG chain. Obviously a step of 1 has a longer return period than a step of 2. If a string of sequential RNG numbers appears to have a relationship, then a string of RNG numbers separated by a constant amount (ie every 3rd number) will also appear to have a relationship (the flip side is also correct - if every 3rd number has appears to have a relationship, then every number will also appear to have a relationship).

Taking every third number from a 'good' RNG will also yield a string of apparently random numbers. This is important, because there are some transformations that require 2 [0:1] random numbers to generate a random number from a different statistical distribution (IIRC normal being one).

 

[TheMeInTeam]

It looks more and more like it is thoroughly impossible/impractical for a human to detect non-random occurrences in the civ IV RNG via empirical evidence in-game.

I did find the way LCG works interesting though, especially the concept of a "master" string with several sets of other strings to choose an ultimate value by. That would indeed produce a result that seems random if executed properly and as I believe PoM mentioned elsewhere, is frequently used due to the simple/effective result.

 

[Silu]

Glad the "streakiness bias" is empirically proven false. Not that I ever thought there's anything wrong with the RNG, it's the a) simplest thing to code b) thing most prone to see whine about.

 

[PieceOfMind]

Actually, can I just get one thing clarified? What exactly is meant by a moving average?

 

[Silu]

Actually, can I just get one thing clarified? What exactly is meant by a moving average?

Moving average is the average of the latest (250 and 750 in the OP) values in a sequence. So it creates "walking" sequences like the ones in the first pictures as it doesn't respond quickly to change.

 

[bestsss]

the game doesn't use "getASyncRand", though...

On a side note: Moving averages (and moving anything) is used extensively in technical analysis of trading. The periods are far shorter.

 

[PieceOfMind]

the game doesn't use "getASyncRand", though...

On a side note: Moving averages (and moving anything) is used extensively in technical analysis of trading. The periods are far shorter.

Do you know how it's different to Soren's RNG?

 

[ruff_hi]

the game doesn't use "getASyncRand", though...

Do you know how it's different to Soren's RNG?

My understanding is that the underlying RNG is exactly the same. The difference is that the synchronized Rand function maintains MP synchronization (it must dole out the random numbers in order when Civ is played MP) while the non-synchronized version doesn't care if it provides the same random number to two different players. BUG uses the non-synchronized version version when producing the fake 'margin for error' in the BUG election pole.

 

[ruff_hi]

Moving average is the average of the latest (250 and 750 in the OP) values in a sequence.

The version of 'moving average' that I am using looks at the 250 values that straddle the number in question. So, the 250 moving average at observation 125 is the average from observation 1 to observation 249.