Testing the civ3 random number generator

[Hurricane]

Originally posted by Myrddin
One pattern that I've convinced myself that I see (whether or not it exists) is that the the first defender in a city has some extra bonus ie the first defender seems more likely to cause damage to attackers than subsequent defenders, even if the defending units appear identical - has anyone else seen this?

Hey, this is a good thread where someone for a break tries to bring in some facts into this never-ending debate. I would suggest we keep the superstitious posts out of here.

[Blake]

Originally posted by SwitchMoO
BTW, nice work with the RNG. It's nice to know that it's just the limits of programming and not a bug or AI cheat causing these streaks.

"It's nice to know it's just sheer programmer incompetence in choosing a RNG and not a bug or AI cheat causing these streaks "

Okay okay... that's not exactly a constructive post, btw where is the original thread mentioned in the first post?

[vulture]

Originally posted by Zachriel

That would require the PRNG to "know" that the call was for such a specific game event. The PRNG "knows" nothing about the purpose to which the result will be used. Only if the programmer made the result of the first round affect succeeding rounds would that be relevant. In other words, even if the PRNG were streaky, the streaks would be randomly applied to each round. So sometimes the streak would start at the beginning of the unit's combat, other times not.

People see patterns where none exist. They see faces in the clouds and animal shapes in the stars. That's just the way the mind works.

I know. Even though I don't think that there is anything obviously wrong with the PRNG, I just mentioned that to point out that its still very easy to think you see a pattern (and maybe that pattern is real, but just due to chance rather than systematic effects in the PRNG). Even if I reverse engineered the whole civ3 code, tested it to exhaustion and convinced myself that the numbers were entirely indistinguishable from random to any test, I'm sure I'd still be finding patterns in the combat results (and I say this as someone who plays a lot of backgammon with some very high quality PRNGs).

There is a small rounding error in the attack modifers, factored in after the PRNG. This could slightly change the ratio of A/D. However, it would not increase streakiness, just the ratio.

I used that info in my test. Anyone paying very close attention might have noticed that the results I quote are consistent with an attack of 6.0 vs. a defence of 2.739687... rather than 2.75. The probability of the defender winning (def_str / (def_str + att_str)) was multiplied by 1024 and converted to an integer, creating this small rounding error. The numbers for a strength of exactly 2.75 would be noticably different at the precision I quoted.

[vulture]

Originally posted by Blake


"It's nice to know it's just sheer programmer incompetence in choosing a RNG and not a bug or AI cheat causing these streaks "

I read a good story about an on-line poker site that used a 32 bit PRNG (which is bad enough) and then did something silly with seeding it with the time of the day in milliseconds in some manner. So they had 86,400,000 possible seeds (and therefore that mand possible permutations of the deck of cards - thats about 2^26 rather than the 2^32 the PRNG is capable of, and noticably less than the 52! (2^226) possible states of a deck of cards. Since they published the PRNG code to show everyone how good it was, it meant that once you'd seen three cards, you could search the possible permutations in real time and know exactly what cards were where within a few seconds. Now *that* is a serious ****-up.

Okay okay... that's not exactly a constructive post, btw where is the original thread mentioned in the first post?

The post mentioning the PRNG code is somewhere near post 40-50 of the The dangerous sea... thread, which references a thread on the other civ site which can be found here, somewhere near the bottom of the page. The info comes from somebody called hwinkels (is that Zachriel's name on the other site by any chance?)

[Kampus majore]

Originally posted by Gen.Dragolen
These results usually happen at the very start of a game, where despite a promising starting location, you loose all of your archers attacking warriors in open ground, and your enemey's warrior takes your capital despite being defended by a spearman on the walls and behind a river, or when the AI Civ benfits when you are trying to take out that one last infantryman in a target city, and you are down to your last unit while the rest of your forces are destroyed or have minimal hit points.

Too many times you see the defender down to his last hit point and your unit still has full hit points, only to have your unit destroyed before combat ends, and the next unit to attack will destroy the defender, even if the defender has healed to full strength again. Hence my impression of the streak.

Our passions and comprehension of reality are too easily offended when the improbable occurs in a game like this one. I just have to keep reminding myself all the time that it's just a game.

D.

I fully agree with this statement. It is just frustrating to see you're units be defeated, but when the same funny effect happens to your opponents, you're happy with it!

[vulture]

Originally posted by SwitchMoO


What do you mean? Astrophysics sounds bad?
Are you a practical or theoretical physisist? I just love physics, especially astro-.

Most theoretical high energy astrophysics (active galaxies), but also some experimental stuff - I'm involved in gamma-ray astronomy, and also some optical astronomy. Endless minutes of fun

[WarpStorm]

From experience at work on PRNGs, we decided that the Mersenne Twister algorithm was the best for our purposes (Monte Carlo simulations involving millions of events, a minor flaw in the stability of a PRNG shows up in that many samples). It is faster than the standard C rand() function and has a period of 2**19937-1. I'd recommend it for just about any PRNG use (except cryptography).

Mike B, y'all ought to consider it, that would put an end to most any complaints if you did.

[Zachriel]

Originally posted by vulture
I know.

I know you know.

Anyway, as one who sees faces in the clouds and animal shapes in the stars, I try to keep an open mind. However, the scientific method has brought us very far since Galileo asserted that the Earth does indeed move.

Thanks for the data.

[vulture]

Originally posted by SpencerH



100,000,000 combats is a small number ? Since my small experience with stats is in small numbers say 5-10 subjects/group with 3-4 groups maybe I have an advantage in looking at anomolies

Shoot me for a cynic, but I'd have thought your chances of finding anything statistically significant in groups that small has to be pretty slim (say the guy who just gave a talk on the significance of the detection of 4 photons...) 100M combats isn't a small number, but any real effect that would show up in 1000 combats would show up much more strongly in 100M combats; all you get at 1000 combats is more statistical noise, and any anomolies you see are very probably random (especially the ones that disappear as you do more trials).

Some kinds of bias would show up by doing many groups of 1000 combats, that wouldn't show up in the kind of analysis I did; namely the possibility that e.g. the 2^1000 possible sequences of battle results may not be randomly distributed (the probability of the defender winning 530 combats (rather than the expected 390 (or whatever) might be too high), but this has to be balanced quite precisely against other biases to keep the overall probability of winning (as tested by the first set of tests I did) the same). I hope I've got my brackets sorted out there.

To test for that kind of bias I've run a few tests, looking at much shorter sequences than 1000 fights. First test was to look at the 70 possible sequences that make up one of the combats in the original post (e.g. there is only one sequence of hits that leaves the defender dead and the attacker on 4 hp - WWWW (W is a win for the attacker in that round, L is a win for the defender), but there are 4 that leave the attacker on 3 hp - WWWLW, WWLWW, WLWWW, LWWWW). As it happens, the distribution of such sequences for 1,2 or 3 successive combats is indistinguishable from what would be expected.

To test longer sequences of combats, it is no longer possible to track individual blows in the combat, but just look at the combat results themselves, and count the sequences of attacker wins fight (W) vs. defender wins fight (L). The only anomoly that has showed up was the chance for the attacking side to win 4 straight battles in a row (in 4 separate battles of infantry attacking fortified spearman on plane). I think that this was enough to rate as statistically significant, but no-one is ever going to notice it IMHO. If you fought 10,000 sets of those 4 attacks, you would expect the attackers to win all 4 5,366 times, and instead they would only manage it 5,365 times out of 10,000. Given random fluctuations (and the fact that combats in civ3 cover a wide range of attack/defense strength combinations) there is no way anyone is ever going to notice that just by playing the game. I had to fight 1 billion battles just to get it to show up with marginal significance in a test that was looking for that kind of effect.

So, the most significant failure of the PRNG (assuming it wasn't a random oddity, which is still possible) is something that would make absolutely no discernable difference to your games if you played civ3 from now until the end of your life without pause. I'm pretty confident that whatever is causing dodgy results (or the perception of dodgy results IMHO) is not caused by and problems with the PRNG. It is not producing any noticably streaky results.

To quote HHGTTG "We have achieved normality. Anything you can still not cope with is therefore your own problem" (paraphrase, from memory).

[Zachriel]

Originally posted by WarpStorm
From experience at work on PRNGs, we decided that the Mersenne Twister algorithm . . .

Mike B, y'all ought to consider it, that would put an end to most any complaints if you did.

I am certain that you are incorrect. People will still see patterns. Why? Because that is the way people are designed (God bless them!). The "patterns" people are detecting in the current PRNG are not real patterns caused by some sort of deficiency in the algorithm.

Use a quantum-RNG and people will still say that the fix is in.

[vulture]

Originally posted by WarpStorm
From experience at work on PRNGs, we decided that the Mersenne Twister algorithm was the best for our purposes (Monte Carlo simulations involving millions of events, a minor flaw in the stability of a PRNG shows up in that many samples). It is faster than the standard C rand() function and has a period of 2**19937-1. I'd recommend it for just about any PRNG use (except cryptography).

That's the one I use as well for my Monte Carlo runs, mostly 'cos its period is nice and long (and it passes just about every test of randomness AFAIK). In one of my PRNG tests I cycled around the period of the generator 10 times, which doubtless has screwed up the results somewhat (since that was the test that showed up the discrepancy I mentioned above), although it isn't as bad as it could have been since each individual result was a sequence of 22 or so PRNG calls, so the chances of all the sets of 22 starting at the same point in the PRNG cycle are pretty small. But still, it will have introduced some effect.

[SpencerH]

Originally posted by vulture


Shoot me for a cynic, but I'd have thought your chances of finding anything statistically significant in groups that small has to be pretty slim

What I'm describing is the kind of groups you can see published in virtually any biological journal (and they'll often use a t-test to calculate p values . Of course better labs will repeat the experiment, but not always. HIV experiments have been published in Nature with results from 2 chimps.

Two thoughts:

Could the random seed number for that turn (that's used to generate the random numbers for combat) cause clustering? Could human starting-stopping-starting of games alter the "randomness" of the random seed and therefore cause clustering?

[vulture]

Originally posted by SpencerH


What I'm describing is the kind of groups you can see published in virtually any biological journal (and they'll often use a t-test to calculate p values . Of course better labs will repeat the experiment, but not always. HIV experiments have been published in Nature with results from 2 chimps.

I generally remain rather cynical of some of the studies I've seen in biology and sociology/psychology reports. I guess we usually have the luxury of being able to gather better stats under better conditions on the whole in physics.

Two thoughts:

Could the random seed number for that turn (that's used to generate the random numbers for combat) cause clustering? Could human starting-stopping-starting of games alter the "randomness" of the random seed and therefore cause clustering?

Good point, which hadn't occured to me. For those of us who use the 'save random seed' option, the seed is saved in the save file, and the pauses in the program are entirely transparent to the PRNG, so it makes no difference (proviso - there may be issues coming from the choice of seed at the beginning of the game; I would hope that the PRNG at the end of one game is saved and stored for the start of the next game).

BUT

For those who don't save the random seed, an awful lot depends on how the PRNG is re-seeded. One way that ought to work is to have a second PRNG that generates seeds for the first one, with the second one saving its sequence between sessions. Other (hopefully) reasonable ways would be to use a selection of bits of system information to generate the seed in some way (one thing I like about Linux is that there is always a source of 'genuine' randomness available which is produced by a complex procedure involving user activities etc.). A very bad method would be to use something like the system time, which, depending on the implementation, could limit the seed to a very small fraction of the possible values, and possibly lead to some strings of results being over-represented at a noticable level (I have no idea how likely that is).

Anyone from Firaxis want to enlighten us on how the seed is determined for the start of games / savs without the seed saved?

[SpencerH]

Originally posted by vulture


I generally remain rather cynical of some of the studies I've seen in biology and sociology/psychology reports. I guess we usually have the luxury of being able to gather better stats under better conditions on the whole in physics.

Well I'm a cellular micobiologist and I'm pretty cynical about them too

[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.