Combat Odds and RNG

[PieceOfMind]

Combat Odds and RNG
A discussion about what you need to understand about the two and how they are different.
Feel free to add your comments below or ask any questions.

First, I'd like the reader to first understand that a combat odds "calculator" and an "RNG" are completely separate things and perform very different functions. Yet in a lot of conversations these functions seem to be confused. The RNG's function is to provide a random number between 0 and N, pretty much. If you ask it for a random number between 0 and 99 it will give you one and you have no way of predicting what it could be.

Contrary to what many people seem to feel, streaks occur all the time from RNGs and statistically they are expected. Many people wrongly believe that a "fair" RNG (or a coin or die for that matter) must balance out toward the mean on a fairly short timescale. This is of course a fallacy because it implies the RNG or coin must possess some form of memory. In mathematical language this is called "independence". It means the result of each trial cannot and does not depend on the previous trial nor any part of its history.

Combat Odds Calculator:
The purpose of an odds calculator is to compute the probabilities of various outcomes occuring. Computing odds is something that people can do very well, as well as machines which are programmed to do so (as is the case with Civ4). Compare this with how notoriously bad people are at generating apparently random sequences of numbers i.e. performing the role of a RNG. When done properly odds are absolutely correct - they are not "fuzzy" or "rough" guesses, just as I can tell you that when you toss a coin you have 50% chance of getting tails. You don't have "roughly" 50% odds, you have exactly 50% odds (assuming a perfect unbiased coin of course!).

Is the odds calculator accurate?
In the very earliest versions of Civilization IV there existed one or a few errors in the combat odds calculation that were sometimes very obvious because you could supposedly have greater than 100% (e.g. 101%) odds of victory. Since it was fixed way back in vanilla, the standard odds calculator has been accurate ever since. Things like first strikes etc. are factored into the calculation absolutely correctly now. There are however two very specific situations in which the displayed combat odds are (or can be) wrong.
1. The first of these errors is due to what should probably be called a bug in the combat resolution code. Some units in Civ4 when they attack are not allowed to kill units (e.g. catapults, cannons etc.). These units have what is called a combat limit and cannot damage any unit beyond that damage amount, and they will instead be forced to withdraw. When in combat, if one of these units with a combat limit damages a defender to exactly the combat limit (e.g. a catapult damaging a unit down to exactly 25HP), then rather than retreating right away combat continues. Since combat continues, if the unit with the combat limit scores another hit it will do 0HP of damage and the combat will end with the unit withdrawing. This is not very intuitive and the way the combat odds calculator works assumes the opposite - that the unit would have withdrawn before it got to a situation where it could deal 0HP of damage. This has the effect of making the combat odds calculator usually over-estimate the unit's odds of withdrawal. The largest discrepency I've seen would be a unit that supposedly had about 67% chance of surviving (withdrawing) actually having only 50% chance. Usually the difference is smaller than that.
2. The second way the odds can be wrong relates solely to barbarian combat when a player has a number of barbarian free wins remaining. On Prince difficulty and below, a certain number of "barbarian free wins" are given to the player and whenever he wins a combat with a barbarian (including animals!) the counter is decreased by 1 each time, until it reaches 0. Before the counter reaches 0, there is a specific intervention in every barbarian combat that gives the player at least 90% odds in each combat round (and consequently 10% at most for the barbarian). Most often this results in overall combat odds of around 99%-ish so almost always these combats will be skewed enough so that the player wins (and his free win counter is then decreased). The reason the combat odds calculator is wrong here is that it ignores this intervention to the combat resolution and assumes the combat is done as normal. This means the odds calculator tends to under-estimate your odds of survival in such barbarian combats. It can be argued that this is not really an "error" per se but is intended to be hidden from the player, but in any case it is misleading IMO.
The two above potential errors have been rectified in Advanced Combat Odds. However the barb free wins info can be ignored with a particular setting if the player or modder wants the barb free wins to remain hidden to the player.

But something is not right with the odds. I lose way too many battles at X%.
I personally have verified independently (i.e. calculated the combat odds separately and then compared the algorithms) the correctness of the game's odds calculator and this was further verified by another mathematician from the forums (Roland Johansen). The RNG has also been confirmed (by DanF5771, ParadigmShifter and others) to be one that is usually called a Linear Congreuential Generator. Without going into too much of the specifics of how it works, it has a period of more than four billion. This means it would need to be called about as many times before it started repeating itself. LCG is the type of RNG that is used in many applications - especially games - because it is very fast (only a couple of integer operations for each output) and very easy to implement. Except for things like online casinos and so forth, the LCG is more than adequate for games. Most people without any statistical software would have no chance of telling apart a LCG's output and the output of a real random number generator (e.g. physically tossing a coin over and over).

The point is, the odds are correct. If you still feel something is wrong, you are either noticing a flaw of the LCG RNG or (more likely) making some wrong assumptions about how a good RNG is supposed to behave. Being suspicious of the RNG in civ is about as logical as being suspicious of the dice when playing monopoly. It sounds more like an excuse for poor planning.

Even when I fight battles at very high odds, like 99%, my units always seem to barely win, and they take more hits than the enemy does even though my units are much stronger!
Another complaint that is frequently made in relation to the odds calculator is how much units get injured even in the highest odds battles. This is a bit unfair because actually the default odds calculator does not even try to given you any information about how much damage your unit will take (Advanced Combat Odds, on the other hand, does!). It's not unusual at all to fight battles at high odds (e.g. 95%) where the average hitpoints after battle will be something like 50HP or less. This is a direct result of the fact that combat mechanics force battle outcomes into a "binomial" distribution. Only when units have a lot of first strikes do they have reasonable odds of surviving unscratched. In most other cases you can expect the victor of any battle to take a lot of damage.
As for the other complaint - that the enemy always seems to get more hits in - I would mainly put this down to selective memory or whatever other name people give to that these days. When you win battles with hardly any damage do you go and check the combat log in disbelief at how well you won? I doubt it. Yet when you lose battles or apparently "barely" win you are more likely to check how on Earth it happened. In these situations you would have to expect to find the enemy got in a larger number of hits. An example would be where two full HP units are fighting - your one does 25HP damage per hit, and the other does 15HP per hit. Your unit only needs to land 4 hits to kill the enemy. The enemy needs to land 7. Obviously if your unit wins but with significant damage then the enemy must have landed more hits. Even though the odds in each round of the enemy hitting you were low, because you are only checking the combat log after the "bad luck" happened you aren't really conducting an objective examination of the combat odds.

 

[dirtyparrot]

Great article as always PoM, but even after reading this I can't shake the feeling that there might be still a slight flaw in the RNG. I still have a suspicion that it's streakier than it should be even though in the long run, the odds will be accurate. Have you looked at the distribution to make sure that you're not getting a case of 20 straight heads and then 20 stright tails and getting the expected odds of 50% (just using an extreme example to illustrate what I'm saying).

 

[PieceOfMind]

Here's one of the tests I did some time ago - I couldn't objectively find anything wrong with the RNG based on a couple of statistical tests.

I've just finished doing the Runs test on the RNG using a bit string of length 2^28, which is one 16th of the full period. Using the RNG to produce random bits, it passed the Runs Test detailed in page K.4 of this document which I've been using as a reference for these tests.

This test confirms that the RNG produces as many runs of ones and zeroes as should be expected.

The LCG RNG used by the game is as follows:

unsigned short CvRandom::get(unsigned short usNum, const TCHAR* pszLog)
{
	...

	m_ulRandomSeed = ((RANDOM_A * m_ulRandomSeed) + RANDOM_C);

	unsigned short us = ((unsigned short)((((m_ulRandomSeed >> RANDOM_SHIFT) & MAX_UNSIGNED_SHORT) * ((unsigned long)usNum)) / (MAX_UNSIGNED_SHORT + 1)));

	return us;
}
with the defines 
#define RANDOM_A      (1103515245)
#define RANDOM_C      (12345)
#define RANDOM_SHIFT  (16)

as reported by DanF5771.

Turns out this LCG is pretty typical and is very common. I think the standard RAND function in C/C++ uses the same LCG. Its characteristics and flaws have been researched well and it is well known that is suffers mostly from correlation problems. The thing is, it's only going to be applications which have great sensitivity on the quality of the RNG that will be affected by this flaw. For example, some types of simulations (like a Monte Carlo simulation) will be adversely affected by an RNG which has even only slight correlation problems like this one.

My best guess would be that the flaws in this RNG are unlikely to be what is being observed by most who complain about it in the forums. It is, after all, the same RNG that is used in all other parts of the game yet combat (and perhaps GP births) are about the only areas that get the complaints, almost certainly because certain strategies depend a lot on their outcomes.

 

[Silu]

Great article as always PoM, but even after reading this I can't shake the feeling that there might be still a slight flaw in the RNG. I still have a suspicion that it's streakier than it should be even though in the long run, the odds will be accurate. Have you looked at the distribution to make sure that you're not getting a case of 20 straight heads and then 20 stright tails and getting the expected odds of 50% (just using an extreme example to illustrate what I'm saying).

That's a common cognitive bias in observing events with known probabilities. People associate evenness with randomness even though they are completely opposite things. A RNG system that doesn't generate streaks is not random at all.

 

[JujuLautre]

This is not exactly the same topic, but I was thinking you could perhaps mention the fact that, when choosing the "best" defender, the computer counts some more factor than just "the defender with the highest winning percentages". Especially in the case of first strikes, as we have seen not so long ago. This is not exactly about probabilities, but still about numbers in combat and a possible source of mistakes.

 

[Lynxx]

Nicely written, probably to long so the people that really need to understand how the combat odds work will not have the patience to read through it ...

I just posted this in the combat odds dealing with navy thread and I will be lazy enough to just re-post it here (it explains why we always have the feeling the game is cheating us, we avoid the low odds in favor of the high ones and thus get far more negative surprises than the positive ones):

Imagine the following:

One player has 5 archers and one 5 warriors standing next to one another on open grounds.

If the player had the archers he/she would attack the warriors. If the player instead had the warriors he/she would run away because of the bad odds. HOWEVER the archers have the exact same probabilities that they all would loose as that all of the warriors would all win!!! But because of the way we human beings think and choose what risks to take, we will never experience the extreme luck needed to win with all 5 warriors. We will experience the extreme bad luck needed to loose with the archers though as we DO attack at such great odds (odds are just odds after all). Sometimes the RNG decides its time to show its ugly face.

 

[PieceOfMind]

That's a common cognitive bias in observing events with known probabilities. People associate evenness with randomness even though they are completely opposite things. A RNG system that doesn't generate streaks is not random at all.

I agree with you of course. I think what dirtyparrot was really asking about was whether the statistical test/s that had been undertaken, whatever it/they may be, accounted for the occurrence of streaks.

In his example, the mean result looks ok of course, but the streaks do not. I reckon an interesting trick question to ask people would be this:

If a person tosses a coin 20 times in a row, which of the following results is the most likely?

A) HTHTHTHTHTHTHTHTHTHT
B) HHHHHHHHHHTTTTTTTTTT
C) HHHHHHHHHHHHHHHHHHHH
D) none of the above

This is not exactly the same topic, but I was thinking you could perhaps mention the fact that, when choosing the "best" defender, the computer counts some more factor than just "the defender with the highest winning percentages". Especially in the case of first strikes, as we have seen not so long ago. This is not exactly about probabilities, but still about numbers in combat and a possible source of mistakes.

That's a good idea actually. I've written a bit about that before, as you'd know, and I'm sure it would be worthwhile to include another bolded "frequently asked question" that relates to the bestdefender selection.

I'll get to that soon. And by the way, it is yet another thing that sorta gets mixed up with the RNG and combat odds discussions often.

 

[r_rolo1]

If a person tosses a coin 20 times in a row, which of the following results is the most likely?

A) HTHTHTHTHTHTHTHTHTHT
B) HHHHHHHHHHTTTTTTTTTT
C) HHHHHHHHHHHHHHHHHHHH
D) none of the above

That one is pretty evil Technically none of the awnsers is correct, to boot, due to the dubious english of the last option ( It should something closer of "They all have the same odds of happening" , that is has not exactly the same meaning as D) , that has a wording that implies that actually there is one "most likely result", but , by acident, is not any of the above )

 

[Silu]

I think it's the point that the correct answer is none of the proposed ones

 

[r_rolo1]

Well, true...

But it still leaves a door open for a eventual "most likely result" ... and that is also uncorrect . So the real awnser is

E) They all have the same odds of happening

 

[Silu]

One could also argue that each of A, B and C are correct since they're tied for most probable

I partly wish the combat odds were hidden. In every game that shows probabilities like this it inevitably leads to people whining about a rigged system.

Another one to ponder: do you feel more unlucky if you lose a 78% fight than lucky if you win 3 60% fights in a row?

 

[TheMeInTeam]

The point is, the odds are correct. If you still feel something is wrong, you are either noticing a flaw of the LCG RNG or (more likely) making some wrong assumptions about how a good RNG is supposed to behave. Being suspicious of the RNG in civ is about as logical as being suspicious of the dice when playing monopoly. It sounds more like an excuse for poor planning.

I don't like your analogy. Unlike in monopoly, at least you CAN plan for the RNG in civ (large forces, collateral, etc). In monopoly it's not hard to figure out a reasonably optimal path and then it all comes down to chance and who is willing to trade with you.

Also, knowing the behaviors of certain people I've played with, I trust the civ RNG far more than monopoly dice. At least, ever since someone tried to hand me a 6 sided dice with 2 instances of 1, 2, and 3 and none with 4, 5, or 6 on it .

Another one to ponder: do you feel more unlucky if you lose a 78% fight than lucky if you win 3 60% fights in a row?

Obviously not.

Hidden combat odds would be pretty foul though, unless they were also hidden from the AI it would require a balance change IMO. Also, we can just calculate them easily enough, making the argument for hiding it a very weak one (it just punishes newbies, and civ already has PLENTY of garbage mechanics/features that punish newbies).

 

[r_rolo1]

Well, even if there was not any odds calculator there would be this exact style of assumptions about the results of combats. See Civ III

And....

The odds os winning 3 60% battles in a row is IIRC (0,60)^3*100 % = 21,6 %. But most people would feel more unlucky to have 22% odds of losing than lucky for having 21,6% odds of winning anyway

 

[PieceOfMind]

Given that you can say, "None of the above are the most likely", I think D is a commpletely legit answer. Also, in the question it says which result is the most likely, not which results are, so A+B+C is not a correct answer.

I guess it boils down to how one interprets "most likely". If it happens that all of A, B and C are equally likely I don't think it would be correct to call any of them the "most likely" result. Anyway, I agree it's evil.

 

[PieceOfMind]

I don't like your analogy. Unlike in monopoly, at least you CAN plan for the RNG in civ (large forces, collateral, etc). In monopoly it's not hard to figure out a reasonably optimal path and then it all comes down to chance and who is willing to trade with you.

Given that it's easy to figure out you have a 1/6 chance of rolling a 7, a 1/6 chance of rolling a double etc., I don't think it's unreasonable to say you can plan to some extent for the RNG in monopoly. Backgammon is the game for mastering the odds of dice rolls IMO but monopoly possesses a very small amount of that same dice result planning.

 

[Silu]

The Civ RNG is almost guaranteed to work better than regular dice, since the extra notches on the higher numbers cause the 1-side to relatively weigh more and bias the results towards high numbers

Oh, and you can "load" plastic dice by storing them with the 6-side up... Plastic is an amorphous substance that slowly "melts" downwards Just store them for a century or two and you'll start to notice it.

I'll take a half-decent computer RNG over real world equivalents any day.

And rolo I guess you're correct in the mental weighing of winning/losing... Just that many people consider the RNG an enemy because they don't fight at crappy odds and still often lose... without realizing they can still be very lucky

 

[J-man]

I personally have verified independently (i.e. calculated the combat odds separately and then compared the algorithms) the correctness of the game's odds calculator and this was further verified by another mathematician from the forums (Roland Johansen).

It's nice to know that the RNG has been confirmed to be very correct (or should I say random). In previous debates on the forum several people always stated that the AI didn't cheat (which was checked in the code) but didn't focused on the RNG.

 

[TheMeInTeam]

Given that it's easy to figure out you have a 1/6 chance of rolling a 7, a 1/6 chance of rolling a double etc., I don't think it's unreasonable to say you can plan to some extent for the RNG in monopoly. Backgammon is the game for mastering the odds of dice rolls IMO but monopoly possesses a very small amount of that same dice result planning.

The thing is, whether you make your decision before or after the outcome of the dice doesn't matter in too many instances I can think of (if at all). You're going to get that outcome whether you plan for it or don't plan for it. You also get as much time as you need before or after the roll to make decisions; it's not like the turn ends after you roll.

To me planning in that context seems a little silly. Reacting to the dice outcome makes more sense IMO, since it limits the amount of outcomes on which one makes a decision without any clear penalty. There might be some consideration late in the game on whether to buy houses/hotels and make trade negotiations, but that's hardly something that a) is frequent or b) necessitates careful planning of the possible outcomes.

The same can't be said for civ. Things like collateral damage, air combat, first strikes, drill promotions against collateral, producing greater #'s, etc. are all methods to bypass being screwed by the RNG in one way or another.

 

[bestsss]

PoM, does the code preserve the remark to Knuth's "Random Numbers" chapter (Volume 2, 3.1.1)?
Adding such comments usually works better than the testing

Actually, making a "bad" random generator for a game is harder than getting it working in an ok way. My issue w/ random generator(s) in the games is the existence of the former not the performance (distribution, sequence length). I'd rather see a game w/ minimal random factor than having it at every possible step - say map generation and that's it.

 

[PieceOfMind]

The thing is, whether you make your decision before or after the outcome of the dice doesn't matter in too many instances I can think of (if at all). You're going to get that outcome whether you plan for it or don't plan for it. You also get as much time as you need before or after the roll to make decisions; it's not like the turn ends after you roll.

To me planning in that context seems a little silly. Reacting to the dice outcome makes more sense IMO, since it limits the amount of outcomes on which one makes a decision without any clear penalty. There might be some consideration late in the game on whether to buy houses/hotels and make trade negotiations, but that's hardly something that a) is frequent or b) necessitates careful planning of the possible outcomes.

The same can't be said for civ. Things like collateral damage, air combat, first strikes, drill promotions against collateral, producing greater #'s, etc. are all methods to bypass being screwed by the RNG in one way or another.

TMIT, the whole analogy to monopoly has gone off the point I think. My original point was simply that complaining about the RNG is like complaining about real dice, and monopoly was used as an example. When I said it's more an indication of poor planning I was referring more specifically to the situation in Civ4 rather than monopoly. Even still, I think you are ignoring much of the planning for dice outcomes because they are so trivial in most cases. Something as simple as knowing a 7 is much more likely than a 2 may be obvious or very intuitive to you but it is still used for planning to some extent. If you are two squares from Mayfair with a hotel on it, you can reasonably bet you aren't going to land on it this time round the board, for example. I've noticed when I've played monopoly that trade can depend a lot on where you are positioned on the board. If you are about to run over several hotels of other players they have a little bit more power over negotiations.