Testing the civ3 random number generator

[Zachriel]

Originally posted by Theseus
I had a discussion with Carver re the 'nature' of the PRNG in a game like Civ3.

Is it not the case that within your 100M set, there would, in fact, be streaks, and that they would be balanced by counter-streaks?

Think blackjack and card-counting.

Card counting only applies with a finite deck. The PRNG is an (essentially) infinite deck. There is no process to even out the results other than the properties of random numbers. In a random distribution, streaks and counter-streaks will be of arbitrary length and randomly placed.

[Theseus]

Can that be right? Is this not non-random, as the results must, over a large sample, adhere to the predicted combat results?

[Zachriel]

Originally posted by SpencerH
. Of course better labs will repeat the experiment, but not always. HIV experiments have been published in Nature with results from 2 chimps.

However, it is possible that even a single result can be significant. For instance, if a disease were 100% fatal, and someone survived, that could be important.

On the other hand, 100 million repetitions of a poorly designed experiment may have no meaning whatsoever. (This does not apply to vulture's well-thought out experiment.)

[Zachriel]

Originally posted by Theseus
Can that be right? Is this not non-random, as the results must, over a large sample, adhere to the predicted combat results?

Toss a coin. By chance, the first five are heads. That does not mean the next five will be tails to compensate. Every coin flip is 50-50. However, over the long run, it will even out. Interestingly, the chance after a million flips of having exactly 50-50 is virtually zero.

[Theseus]

Duh... my head's fuzzy.

I had a subconscious assumption that the game designers were not strictly depending on statistics, but had introduced some kind of modifier to correct for streaks (?? finite sample, based on the number of combat iterations an individual player would likely see in a moderate period of time??).

So the game just depends on straight-out stats; an early streak in one direction will be 'balanced' over a very large sample simply be random and distributed events in the other direction.

And within the context of gameplay (small sample), que sera sera.

Got it, thanks.

[vulture]

Originally posted by Zachriel


Toss a coin. By chance, the first five are heads. That does not mean the next five will be tails to compensate. Every coin flip is 50-50. However, over the long run, it will even out. Interestingly, the chance after a million flips of having exactly 50-50 is virtually zero.

To take that a bit further, saying that in the long run it evens out is possibly a bit misleading. If your first five flips give heads, then after a further million flips the single most likely outcome is that you have 500,005 heads and 500,000 tails (after a total 0f 1,000,005 flips). On average you still end up with an excess of 5 heads, but the excess is absolutely negligible when you have that many trials (the variations in the 1,000,000 subsequent flips will be larger than the 5 excess by a long way, but on average the excess will still be there. That's how the law of averages works, not because there is some kind of counter-streak to balance the initial excess of heads.

[Zachriel]

Originally posted by vulture
To take that a bit further, saying that in the long run it evens out is possibly a bit misleading.

Thanks for the clarification of my admittedly clumsy description. Perhaps I should have phrased it as "over the long run, the results will tend to even out in proportion to the number of flips." Those five lucky heads just don't seem significant after a thousand years of flipping coins.

Five in a row may seem like a lot in five or ten flips, but in a million flips you will typically see very long streaks of heads (or tails). Indeed, you can expect streaks of arbitrarily large length in a long enough random sequence.

[Theseus]

Thanks for the clarification.

Is there a stock answer that can be devised for all the whines?

E.g.,

"Look, there are over a million people who have bought Civ3. Let's say 100,000 of them have played an average of 2 hours a week, over 10 months, and there are 50 combat events per hour, for a total of > 400 million combat events. The odds of a streak of 1 Spear holding off a 5 Knights in a row, with 0 damage, NOT happening, are X."

[vulture]

Originally posted by Theseus
Thanks for the clarification.

Is there a stock answer that can be devised for all the whines?

E.g.,

"Look, there are over a million people who have bought Civ3. Let's say 100,000 of them have played an average of 2 hours a week, over 10 months, and there are 50 combat events per hour, for a total of > 400 million combat events. The odds of a streak of 1 Spear holding off a 5 Knights in a row, with 0 damage, NOT happening, are X."

I really doubt that anything will stop people complaining about perceived injustices in the PRNG. However, for those that might listen to arguments, it could be worth pointing out the 'prosecutors fallacy' effect.

Suppose you suffer some unlikely sequence - losing 20 fights in a row for instance - for which you (correctly) calculate that the odds of it happening are 1 in 50,000 for any given 20 fights. The fallacy is due to the fact that you've calculated the right answer to the wrong question. The question isn't "What is the chance of getting 20 losses in a row?", but "Given that I have lost 20 fights in a row, what is the probability that this is due to chance alone?". The answers can be very different, and unfortunately, sometimes impossible to calculate exactly for the latter question.

I don't know if the 'prosecutors fallacy' name came from DNA testing results in court cases, but that's where I came across it. The odds of having a false positive identification with DNA testing (taking an innocent person, comparing their DNA to that taken from a crime scene, and getting an accidental match) is 1 in 20,000,000 (I'm making the numbers up in case you hadn't noticed). But given someone in court with no evidence against them apart from the DNA match, what are the odds that they are innocent? It depends a great deal on the method used to find the person who matches. The odds can vary from 1 in 20,000,000 (the same as the first question) to a 90% (or more) likelihood of innocence.

Applying the same in civ3, you may figure out that there is a 1 in 50,000 chance of getting the results you saw, but that can still translate to a virtual certainty that it is purely due to random chance, rather than any conspiracy or bias.

I can't give short answers, can I...

[Theseus]

I guess you're right... perception is reality.

(hehe, leading by example...)

[Blake]

Going ever so slightly off topic here, I was musing on how to improve on random stuff (like leader generation). I figured it would be fairer, and people would see less patterns (and thus like the random generator more...), if the randomness was indeed rigged (by this I actually mean the odds are rigged).

For example Leader generation: Each elite combat attack has a 1/16 chance of generating a leader. How about if it was rigged like this:
The chances of generating a leader start very bad, for the first elite combat about 1/128.
Each combat which doesn't generate a leader, the odds improve, until at about 8 combats it is 1/12. At around 16 combats it's about 1/6 and so on until the odds are capped at around 1/2.
As soon as a leader is generated the sequence resets and it's back to bad odds.

What this would mean is there would be a really really really good chance of getting a leader if you say did 20 elite combats, in fact it would be virtually guaranteed.
Likewise the chance of getting two leaders in a row would be very very small (I once got two leaders in a row, after fighting about 20 elite battles and getting no leaders....)

Thoughts? I think this would be fairer, but what about more enjoyable?

[Theseus]

That's actually what I meant in assuming that the designers had tweaked 'randomness,' rather than depending on large sample statistical outcomes.

It would have been a good middle ground design choice between the games where unit stats interact absolutely, and the relatively wide range of results from a PRNG.

And the GL thing is a meaningful example, as the overall sample set for an individual player is so much smaller (well, maybe not for some of us warmonger types ).

I think it would be both fairer and more enjoyable.

[Blake]

Yeah, I chose GL generation as an example because it's the thing that possibly bothers me most... I can live with the occasional pikeman beating a tank, or an archer attacking a tank and causing it to retreat, but it's rather bothersome to think that given 20 elite combats, it would be quite reasonable to expect to get maybe 2 GL's (10 combats gives a 50% chance of getting a leader), but it would also be fairly reasonable to expect to get no GL's. The difference between 2 GL's and no GL's over your first 20 elite combats, is somewhat greater than the impact of losing a single tank to a single spearman.

Incidentely the chance of not getting a GL over 20 combats is 27%, so you can reasonably expect to get a GL, but if you were given a 30% chance of dying in an operation you wouldn't be too confident about it .

Basically I think the GL generation is messed up, using a totally random system was totally wrong, a rigged odds system, or something like elite units getting a better chance of generating a leader for every battle they win (1st battle, 1/32, 2nd battle 1/16, 3rd battle 1/8, 4th battle 1/4, all subsequent battles 1/2...). Basically SOMETHING, ANYTHING the player can work with to improve their odds, other than just having more elite units.

[Theseus]

You know, this is the first 'change' idea I've felt really passionate about in a long time...

I can;t believe that it would be too hard to insert an if-then statement into PTW that says if you don't get a GL within 39 elite victories, you get it on the 40th.

Your idea, Blake... you mind if I try getting Firaxis' attention?

[Blake]

*Shrug* go for it. But we may as well discuss the method for best rigging the odds for fairness.

Personally I think the odds should be calculated like this:
Start with the basic chance of losing the battle. (1 - chance of destroying enemy from civulator)
(This is to encourage "normal" use of elites).

Divide by a number determined by how many battles since the last elite was generated, I'll call it K.
K = 16 (initially)

Each elite victory which doesn't generate a leader, K is reduced by 10%.
ie 16 -> 14.4 -> 13 -> 11.7 -> 10.5 -> 9.4

Once a leader is generated, reset K to 16.

1st elite battle: 0.5 / 16 = 1/32
25th elite battle: 0.5 / 1.15 = ~1/2

At around 33rd combat the chance of gaining a leader would become guaranteed (for a 50% chance of victory).

Obviously numbers need to be tweaked... (and prefferably put in the scenerio editor!)

IMHO it would be more enjoyable to be able to use your elites to crack open tough targets, and know you'll have a better chance of generating a leader than having to treat your elites like glass...
Ofcourse with the simple system of any elite battle which is won improving odds of getting a GL in the next battle it could be exploited by say doing 16 "cheap" elite fights (knight vs archer...) then start doing the real battles (if need be, this can be remedied by factoring in the "hardness" of a battle in improving odds of the next battle generating a GL...)