Battles aren't random, they're scripted

[dguichar]

..one thing:

Dies (ideal ones) do NOT have memory, they don't remember which was the face they showed upwards before.
Of course computer dies are not ideal ones... so maybe they DO have memory.

Keep civilized

David

 

[HuckFinn]

Cool, someone else has noticed the predictable battles too. It's been a fun thread to read. Now, don't get me wrong, I've read enough of Knuth's programming bibles to understand quite well what a random number generator is. However, Civilization does repeatedly give me the impression that a battle is fated to go in some direction after a few hits. The most typical sequence is that my attacker beats the defender down to 1 hp while taking rather minor damage himself, and then the defender stages a miraculous comeback and whacks my attacker to pieces.

I don't claim to know what causes this phenomenon -- the feeling is very real, even if most probably it is merely an illusion. Also it is fascinating that a lot of people seem to be getting these vibes from the game...

 

[ukrneal]

I think it's fascinating too. But I think most of it is because we remember those times better. It makes more of an impression that we almost killed it, but not quite. This will be espcially true if we took just enough for the attack, but due to a couple unlucky turns, the city remains an enemy city. Then we get upset and blame the computer for not being random because surely my 10 cav should take out 3 riflemen and a spear. And becuase 10 in this example might seem overwhelming, we remember it even more. In reality, you will lose fairly often in this example.

 

[TheNiceOne]

Originally posted by HuckFinn
Cool, someone else has noticed the predictable battles too. It's been a fun thread to read. Now, don't get me wrong, I've read enough of Knuth's programming bibles to understand quite well what a random number generator is. However, Civilization does repeatedly give me the impression that a battle is fated to go in some direction after a few hits. The most typical sequence is that my attacker beats the defender down to 1 hp while taking rather minor damage himself, and then the defender stages a miraculous comeback and whacks my attacker to pieces.

From someone who don't believe for a second that this pattern is anything else than imagination:

I can make a scenario containing 50 units ready for battle. I will then perform all battles and write down all attack results and post the 2 (3-4?) first combat rounds of each battle. Anyone who believes there is a predictable pattern can post the expected remaining combat rounds of each battle.

I will then post the actual results, and the scenario for control, and we'll see if anyone managed to predict much more than 50%.

Is anyone interested?

 

[Park Ranger]

Originally posted by TheNiceOne

I will then post the actual results, and the scenario for control, and we'll see if anyone managed to predict much more than 50%.

I don't understand...if I know the first 2 rounds, then I can predict what statistically is likely to be the outcome. Assuming the combats you set up are 50-50 for attacker at the outset, if one side wins the first 2 battles, I'll bet on that side. I should be able to do better than 50%, right?

Or do you want round by round predictions? That's basically what the pattern-seers should be able to do, if indeed there is a pattern.

 

[TheNiceOne]

I was thinking of per round prediction. But I'm willing to set it up and test whatever anyone means he can predict. It's just a matter of having enough tests, and checking if players can predict the results any better than pure statistical based prediction will do.

I.e., if a person only wants to predict the final outcome, that's fine with me. If as you say, one side has won the two first rounds, so there is 2HP-4HP left, then there is a 81.25% chance that the 4HP unit wins (assuming each round is 50%). Thus a person who claims the battles are not random must guess correct in more than 81.25% of the time to be believed.

 

[Park Ranger]

Originally posted by TheNiceOne
I was thinking of per round prediction.

Eh, no thanks then. Sounds like a sucker's game to me.

For those who think the civ3 RNG is broken, however, there's an easy test you can do with dice to show the wide variability in combat results. Take the 2:2 odds of a vet archer vs. a vet spear, for example. Take four dice, roll them all at once. 1-3 is a miss, 4-6 is a hit. Re-roll any hits, count misses as hp lost to the archer and set those dice aside. Continue until no dice are left or you get four hits. It's fast, and easy to record the hp left to the victor. Do that a hundred times, keep a tally of the 8 different possible results (not just who wins, but how many hp left to survivor). Plot the distribution on a graph, connect the dots and see the rough resemblance to a bell curve.

Then set up a test in civ3, or ask TNO nicely to do so for you. Make sure all your battles take place in open terrain that offers no defesive bonuses, and that no defenders are fortified. Make another tally sheet, another graph, compare. Because in civ3 defender gets a 10% bonus, don't expect them to match perfectly. But I predict the extreme ends of both curves (defender or attacker winning with full hp) will have about 6 occurences each, out of 100 battles total.

See, I'm psychic too.

 

[Hygro]

After reading this thread I've watched my battles more closely. I still can often tell the outcome, but most of that is understanding that if I don't see my guy take damage, I know in a split second the defender will. Often things will seem scripted but I have also realized that many of my wars involve one or two unit types fighting about two differant unit types on maybe a total of 3 differant terrains (including whether its a city on grassland, or a town on a hill, or whatever).

This results in many of that battles having units losing life in the same order.

What's funny about this is that the consistency seems too consistent, until your modern armor gets slaughter by a rifleman out of the blue.

 

[Sirp]

Hygro is right that they make it that your guy takes damage at the animation stage when he gets hit by the other guy, so you can predict that someone is about to take a hit, because a split second before the other guy didn't.

As for there being 'patterns' , this is simply because we're talking essentially binary numbers, and there just aren't that many possibilities. I'm a computer programmer, and I've studied many binary strings in my day. They tend to look like they have patterns. Like 1010 or 1100 and so forth, but really, it's just a combination of there not being so many possibilities, and the way your brain works.

Additionally, if battles were 'scripted', then surely there are some battle outcomes that can' take place because there are no scripts for them. Say for instance a regular archer attacks a regular spearman. There are 20 possible ways the battle could go. These being:

AAA
SAAA
ASAA
AASA
SSAAA
ASSAA
AASSA
SASAA
SAASA
ASASA

('A' means the archer wins, 'S' means the spearman wins)

and the logical 'not' of these: replace 'S' with 'A' and 'A' with 'S'.

Now, if there is a finite set of 'scripts' that the battles run off, then I assume that not all 20 of these possibilities can happen, since only the possibilities covered by the set of scripts can occur. If so, would someone like to tell me which of these sequences cannot occur?

Note though that if the battle is lopsided: one side has an advantage over the other, then some sequences will be much more likely to occur than others. Maybe that is what gives creed to this 'script' theory.

I don't buy a bar of this 'scripts' thing, however, I will say that Civilization III's random number generator can be called into question. Lots of players complain about 'streaky' results; even players with lots of credibility, like Sirian.

Further, it is certainly known that it is far more likely for a scientific civilization to get Monotheism and Nationalism at the start of each age. I believe I recall seeing Firaxis admit that this was an unintended feature of the game. This does call into question the integrity of the RNG.

But, I'm sure Firaxis wouldn't want to have a crappy RNG in their game, and I doubt it'd be a difficult thing to fix. The C runtime supplies a random number generator which would work fine.

Testing if the Civilization III RNG is 'fair' isn't too hard, you can do it with a scenario. To see how 'streaky' it is is harder; much harder.

-Sirp.

 

[Park Ranger]

Originally posted by Sirp
I don't buy a bar of this 'scripts' thing, however, I will say that Civilization III's random number generator can be called into question. Lots of players complain about 'streaky' results; even players with lots of credibility, like Sirian.

The thing is, whenever this subject has come up in the past no one has been able to confirm a problem with the RNG in a scientific test. Indeed the opposite; all tests so far have shown that combat results are pretty much what would be expected with random numbers.

About the free tech for scientific civs: that one may work differently because the RNG selects from a list of results. In combat the RNG just has to return a number, then results are calculated. Now, if the combats were scripted, then the problem would be similar. But that makes no sense to me, because as you point out there are 20 different ways a battle could play out in just a reg vs. reg unit. Consider the number of scripts you'd need to cover ALL the hp possiblities (conscript vs reg, reg vs. vet., elite vs vet. etc). Now add armies, and all the different numbers of hp an army can have (anything up to 20, right?). And then there's the possibilities that come up with modding, which has been done. I'm suspicious that programming sequences for all those possibilities and then randomly selecting one is easier than just repeating a random roll for each HP.

Sirp makes a really good point about certain sequences being more likely when battles are lopsided. When the attacker has a 4:1 advantage (not very common, I admit), you're going to see a lot more of those sequences that begin with "A" (80%), and quite a few that begin with "AA" (64%).

 

[Sirp]

Park Ranger: I have only seen tests which test that over a substantial set of combats, the results match what would be expected of random numbers. However, this doesn't take into account the possibility of the numbers being streaky, and not conforming to the general characteristics of random numbers.

For instance, let's suppose that I made a program that simulated flipping a coin, and we wanted to test if it matched the characteristics of a real coin. Suppose now that the test was that we would run the program 1000 times, and would expect there to be around 500 tails and 500 heads. We run the program, and find say, 502 heads, and 498 tails come up. From the test, it seems that the program matches the characteristics of a real coin fairly well.

This is the only type of test I know of to test Civilization III combat results.

Suppose that I did a more detailed test, and found that if a result was a head, 75% of the time the following result was also a head. Likewise for tails, in reverse. The coin is still 'biased' neither way, and is going to be likely to give close to 50% heads, but this more detailed test has showed that it doesn't match the characteristics of a real coin.

The second test requires far more detail and analysis, especially when dealing with results more complicated than coin flipping, such as civilization III combat.

So what does this show? That a contrived example can prove anything. Oh oops! That's not what I meant

I'm not saying that the Civ3 RNG is dodgy. In fact I tend to doubt it is. I'm just saying that it is a possibility which *hasn't* been verified in any tests as far as I know.

As for the free tech, it will generate a random number, to select one of the techs. Same as for combat, the main difference is that one would probably end up as a floating point number, and the other an integer. However, I wasn't bringing this up to somehow say there 'must' be a problem with the combat RNG, I am just pointing out that there *have* been shown problems with the RNG in certain contexts, so thinking there might also be in battle is not so unreasonable or far-fetched.

-Sirp.

 

[Park Ranger]

Sirp: OK, I see what you're getting at now. Looks like we're both pretty skeptical, but you thought of a way that the CFC tests to date could be overlooking a problem.

In your coin example, you show how there could be streakiness in the results. So if you flip heads first, you're likely to be stuck on heads for a while, until you flip tails and then you're stuck with tails for a bit. But overall you still get 50/50. So how do you test for this?

I'm thinking that first you need to establish what the average length of streaks (continuous wins by one side) would be with an unbiased coin over those 1000 flips. Now going beyond my basic (high school) understanding of probability mathematics.

I'll ponder this for a bit, see if there's some way to detect this sort of this by looking at battle results without documenting each and every combat round....

Meanwhile, it might be easier for me to stand on Occam's Razor (ouch!) and point out that the simpler explanation (that the human brain likes to see patterns where they ain't) is more likely the case.

I'd also like to know more about this random tech problem...if the RNG checks each tech in a list in turn then it makes sense that the first in the list would be favoured. What other problems with the RNG have been *shown* to exit?

 

[Zachriel]

* In a long enough random sequence there will be streaks of arbitrary length (for instance 100 heads in a row). If you don't see such streaks, then the numbers are not random.

* There are apparent patterns in random sequences, but they are meaningless and non-repeating.

* Computer are digital, deterministic machines and are not capable of creating true random numbers. However, standard PRNG's (Pseudo-Random Number Generators) are easy to create and with modern methods are virtually indistinguishable from truly random numbers.

* PRNG's start with a seed and create the sequence from this seed using one of various algorithms. Even though the sequence created appears random, it can be recreated exactly from the same seed. This is like a huge, shuffled deck of cards. The sequence is pre-determined, but nevertheless random. The sequence is created as needed and not stored in memory.

* Analytic tests of PRNG's include not just average results, but distribution of those results, and unpredictability of results. Flaws in any decent PRNG's are only apparent after thousands or millions of results. (These flaws can sometimes be detected by humans when presented in certain formats, such as very large tables, or as an audio steam.)

* It is possible to start with a good PRNG sequence and "screw it up" when programming. This is usually due to modulus errors in software logic. However, this will usually just "slant" the results slightly in favor of the attacker or defender. It will not produce predictable sequences.

* People always see patterns even in truly random distributions. This is inherent in the way the brain works. Not so surprisingly, the reported "flawed" sequences almost invariably favor the AI over the human. However, even if the RPNG were flawed, it would probably not favor any particular player.

* No one has been able to demonstrate any flaw in Civ3's RPNG.

 

[Hurricane]

Look at the list Sirp provided. I have marked sequenses that seem to follow a pattern with bold.

Originally posted by Sirp
AAA
SAAA
ASAA
AASA
SSAAA
ASSAA
AASSA
SASAA
SAASA
ASASA

As you can see, almost half of the patterns look "streaky". So the streaks you see in the game are, in fact, exactly what you would expect from a well working RNG.

 

[Hurricane]

Originally posted by Sirp
For instance, let's suppose that I made a program that simulated flipping a coin, and we wanted to test if it matched the characteristics of a real coin. Suppose now that the test was that we would run the program 1000 times, and would expect there to be around 500 tails and 500 heads. We run the program, and find say, 502 heads, and 498 tails come up. From the test, it seems that the program matches the characteristics of a real coin fairly well.

This is the only type of test I know of to test Civilization III combat results.

Suppose that I did a more detailed test, and found that if a result was a head, 75% of the time the following result was also a head. Likewise for tails, in reverse. The coin is still 'biased' neither way, and is going to be likely to give close to 50% heads, but this more detailed test has showed that it doesn't match the characteristics of a real coin.

The second test requires far more detail and analysis, especially when dealing with results more complicated than coin flipping, such as civilization III combat.

Did you read the post by vulture, which I quoted on page 2? He did excactly the test you are asking for, and found nothing suspicious.

 

[Erik Mesoy]

Just making a rebuttal here

If there were 50 combat rounds and 25 wins/25 losses, then the most even distribution would be win-loss-win-loss etc. The most uneven distribution would be 25 wins followed by 25 losses. A true random distribution would be somewhere in the middle

Nope. win-loss-win-loss to the end is just as unlikely as 25 wins-25 losses.

There is a joke about this. A teacher asks several pupils to flip a coin 100 times and note the results. The teacher can see who very probably cheated, because none of them ever had more than 4 of the same in a row. Flipping a coin 100 times, the probability for a streak of length 7 is around 50%. (last figure not accurate. The rest is confirmable)

I reccomend the book Arithmetic of Life for thsoe of you who haven't read it already.
Streaks happen. Streaks are part of nature. Streaks are more common than pure even randomness. But over time the Law of Averages always wins.

 

[Sultan Bhargash]

I am always in agreement that the AI has a sense of the dramatic, and that this is not entirely random.

 

[Hygro]

Page 4 of this thread seems to be the most convincing. I see now what is meant by the appearant sequences. Because many times your battle conditions will not change drestically, you stastically will see very similiar battle results, which looks like a pattern. When I first replied to this thread I agreed in the sense that things looked scripted.

I always knew the battles were dterming dandomly, not by a script. However, with those 20 posibilites for a regular archer vs a regular spearman, it appears to pull from 20 different scripts.

 

[danwhit]

I feel confident that it is not scripted. And I just wanted to point out that the three so-called streaky patterns that hurricane pointed out above are merely the most dramatic/memorable outcomes. Think about it: your archer destroys a spearman without taking a hit(whoo-hoo!, I rock), AASSS(WTH, I was doing so well), ASASA(that was strange). Also, as it has undoubtedly been pointed out, given the few number of hp a unit has there are a limited number of outcomes. This is noticeable in battles vs. barbarians(probably the situation that people think is scripted). I myself was annoyed by this at first. And that if one unit misses(and you see the unit miss on screen) the other will hit.

 

[etj4Eagle]

Originally posted by TheNiceOne

I have now searched hard and long for a thread I remember I read half a year ago or so, where some players had tested the raw output from the civ3 Rng and found it to behave as it should regarding streaks and patterns. I could not find the correct thread so my defense is weakened, but I found a few other interesting threads though.

TNO I think I know of the thread you are referring to, it is the one in which Dan gave us a combat test map: Dan's Combat Test Map Thread. I had searched for this post some months back and this time remembred to search for "DIEHARD" and then look for a statistical thread in the results. I didn't see this piece brought up in this discussion, so I will copy and paste the post by hwinkles to the bottom of my post.

But for those who believe that the Civ3 RNG is streaky, hwinkles was able to use a debugger to access Civ3's RNG. (This is also how we know it uses a linear congruential RNG, not that I know what that is). He then proceeded to run the RNG through a industry standard statistical test suite, which does test to ensure that the sequence has the correct amount of streakyness. And it passed those tests, hence the RNG is not broken.

and here is the post by hwinkle on Feb 2, 2002:

Civ III RNG Analysis
Using a debugger I determined that Civ III uses a linear congruential RNG. Actually, it's a pseudo-random number generator, but I digress. The fundamental formula for updating the seed is given by the following formula which is done every time the base random number routine is called:

seed = (seed * 1103515245) + 12345

There's a suite of tests called DIEHARD that have become the de facto standard for evaluating RNG's. I ran the DIEHARD suite of tests on several data sets of output values from the Civ III RNG. Each data set had about 20 million numbers in it. DIEHARD has 15 different test routines in it, and with the exception of 1 of those (OPSO, OQSO and DNA are considered one test), the results were good. The OPSO, OQSO and DNA results were very bad, however, so I ran further tests.

For combat purposes, Civ III asks for a random number between 0 and 1023. I simulated the exact same mechanism used by the game to generate numbers in this range, and ended up with a data set of over 64,000 numbers. A histogram analysis of the results showed that the distribution of values was pretty even. I repeated this test several times and the results were consistently good. There was no noticable bias favoring any particular output.

I conclude that the RNG used in Civ III for determining the outcome of battles is pretty solid. If there are any problems with combat outcomes, they must lie elsewhere. And, of course, there's plenty of "elsewhere" to consider. For each battle, a number is calculated for the defending unit (I have no idea how that number is calculated). Then, for each whack that the attacker takes against the defender, a random number is generated in the range 0 .. 1023. If the resulting number is greater than the number calculated for the defender, then the attacker scores a "hit" and the defender's Hit Points get lowered by 1. Otherwise, the defender scores the "hit" and the attacker's Hit Points are lowered by 1. First one to 0 loses the battle. All this obviously depends on exactly how the defender's threshhold value is calculated by the game. If there's a problem with battle results, then that is most likely the area where the cause of the problem lies. It's not in the RNG.

The RNG uses several floating-point calculations which are deadly in terms of performance. The programmers could have achieved the exact same results without having to resort to floating point calculations. As a result, the calculation of random numbers takes anywhere from 4 to 6 times longer than is necessary. I don't know how often the RNG gets called on during the AI turns, but it would be interesting to see how much those late-game turns could be speeded up by eliminating all the floating point conversions in the RNG routine. It's used for much more than just determining who wins battles. It might not make any difference at all, but then again it just might. I'm going to try and replace the RNG routines in my copy of the game and see if there's any appreciable difference.

Summary: The algorithm used by the RNG in Civ III is good, and the numbers it produces pass most statistical tests with flying colors. The implementation of that algorithm is poor, unnecessarily impacting the performance of the game. They could have and should have done a much better job in that respect. It ain't rocket science. If I have any success in replacing the game's RNG routines with my own - and there's anything significant to report - I'll let you know.

Edit: I was able to substitute my no-floating-point RNG in the game. There was no noticeable difference in late-game slow-turn performance. Therefore, I'd like to back off my statement above that using a FP RNG was a bad implementation by the developers. In the grand scheme of things that tend to slow the game down, the RNG apparently is not a big factor.