Am I calculating these odds right? (multiple trials, uneven winning conditions)

Factual Questions
1

In the PC game Civilization III, combat units can engage in, well, combat. We will define a battle as a set of rounds where the loser has no more hit points remaining. Each round forces someone to lose one hit point.

In CivIII, ignoring unnecessary complications, the odds of winning a round are based on the units in combat. Each unit has attack and defend values, as well as already mentioned hit points. The odds of the attacker winning any particular round of battle is “own attack points / (own attack points + other defend points)”. To use a real example, suppose a Cavalry (attack 6 defend 3) is fighting a Musketman (attack something defend 4). The cavalry intitiates battle, making it the attacker, and it thus has a probability of winning any round of battle as 6/(6+4) = 60%. Simple enough.

But remember I said that the rounds go on until someone is out of hit points. Intuitively, if the defender has, say, five hit points, and the attacker has only 3, then the odds of the defender winning the battle should be better than the odds of him winning any one round, because he can see more rounds than the attacker can.

So what I did was pick up a prob&stat book and found this formula:

P® = [sub]n[/sub]C[sub]r[/sub] * p[sup]r[/sup] * q[sup]n-r[/sup]
where
P® is the probability of getting exactly r wins in n trials, where p is the probability of a win and q is the probability of a loss (1-p) in each individual trial.

When I did the math, I got the result of about 25% for the attacker. In other words, even though the attacker would win 60% of the rounds in general, his lack of hit points means he will only end up winning battles like this 25% of the time.

If I messed up the math for 25%, that’s one thing, I’m going to go home later and work things out in excel where these calculations are not as error-prone as using a calculator and writing down numbers. But the question is, is this the right formula? And can I only use it from the perspective of a unit with the least amount of hit points? It almost seems that this is not the right formula because in some scenarios we never get to see all 7 trials (always attack’s hit points + defender’s hit points - 1) because the attacker wins five in a row or the defender wins three in a row, etc. But then I think, like I said, pick the unit with the most hit points and calculate from his perspective. So you can see I’m just a little confused on the matter.

Hopefully this is actually clear.

[sub]Yes, I know about the existence of a CivIII calculator for this. The point is knowing the math. It is an interesting problem.[/sub]

2

I’m going to jump in quickly and hopefully make this a little more intuitive. I’ll assume that you have the mechanics of the game described properly. A defender with five hit points is going to be relatively safe when attacked by a similar unit with only three hit points. That’s the logic behind assigning veteran and elite units more hit points (as opposed to attack or defense bonuses). Here’s why:

For the attacker to win, he needs to win at least five times without losing more than twice. You can express the scenarios as combinations of wins and losses. By adding the probability of each scenario (multiplied by the number of different ways each can happen, divided by total outcomes) we get the total probability of all possible victories.

Start simple: five wins in a row (one of the scenarios you mentioned where “we don’t see all seven trials”) has a probability of about 7.77% (0.60[sup]5[/sup]). There is only one permutation of that: WWWWW.

Five wins interrupted by one loss (WWLWWW etc.) is our next case. There exist five ways to do this. You may be thinking of a sixth (WWWWWL) but that’s really the first case, because who’s left to lose that last trial? The probability of a loss is 0.40, so we chain that together with the five wins and get 3.11%.

Lastly, we have the exhaustive battle: five wins interrupted by two losses. There are fifteen ways to do this. The probability of its occurrence is very small however: 0.60[sup]5[/sup] * 0.40[sup]2[/sup] = 1.24%

So there are 21 ways to win this battle, each with a weighted probability. The number of ways to lose are as follows:

3 straight losses - 1 occurrence, odds of 0.40[sup]3[/sup] = 6.4%

3 losses interrupted by a win - 3 occurrences, odds of 0.40[sup]3[/sup]*0.60 = 3.84%

3 losses interrupted by 2 wins - 6 occurrences, odds of 2.304%

3 losses interrupted by 3 wins - 10 occurrences, odds of 1.382%

3 losses interrupted by 4 wins - 15 occurrences, odds of 0.829%

So there are 35 ways to lose, each with their own probability.

So, to get the total probability of a win:

(1 * 7.77%) + (53.11%) + (151.24%) / (21 + 35) = roughly 23%, rounded

The idea of enumerating all the different ways this can happen is the output of the [sub]n[/sub]C[sub]r[/sub] “choose” function. So I’ve basically built up that equation for you from scratch. You need to be careful not to examine any cases where a dead unit gets to take a swing from beyond the grave - so use caution when selecting the numbers to use in the “choose” function - but otherwise, I think you’ve got the right formula.

3

This is the sort of problems that Markov chains were designed for. I don’t have time to work out an example right now, but that’ll give you something to google on.

4

The thing is, I can’t see a situation where this happens and it results in an improper tally. Consider 5HP versus 2 HP from the perspective of the 5HP… I can’t create a “winning” combination that is not a true win. I guess that’s part of the question: is this formula’s use actually limited in some way I’m not seeing?

Take a smaller set of possibilities, where we examine every permuation of a 3HP and 1 HP battle. At most, there can be only three rounds, meaning
WWW
WWL
WLW
WLL
LWW
LWL
LLW
LLL

Of those, from the perspective of the 1HP guy, he wins only once, and though he does “swing from beyond the grave”, such swings never result in a win… so I should be safe, right?

From the perspective of the 3HP guy, he wins every other time… even when the guy does take a swing from beyond the grave.

Ps – thanks ultrafilter, I’ll dig up the info later when I’m at home.

5

I don’t understand. The victory of the 1HP piece depends on the last possibility, and there’s no “beyond the grave” aspect to it. Restating that results:


WWW - attacker wins on first attack,
       making second and third attack moot
WWL - ditto
WLW - ditto
WLL - ditto
LWW - attacker wins on second attack,
       after taking one hit, making third attack moot
LWL - ditto
LLW - attacker wins on third attack,
       after taking two hits
LLL - defender wins

Assuming all odds equal, the attacker wins the battle 87.5% of the time. When subsequent rounds are made moot (i.e. one party has been reduced to zero), the battle is over.

Of course, it’s still an improvement over Civ I, when I attacked a phalanx with a battleship and lost.

6

I didn’t suggest the perspective. The same permutations exist for either party. If we look at it from the perspective of the defender, the first permutation is the only victory for him. If we look at it from the perspective of the attacker, the last permutation is the only loss for him. Just a matter of perspective.

7

The general form of the solution is probably beyond my ability to find, but here’s how to go about it.

Let x be the hit points of the unit with higher hit points, and let y be the hit points of the other. Let a be the probability that the unit with higher hit points loses a hit point in a given round.

Of course, if x = y, you should assign them arbitrarily.

Define a function P from {1, …, (x + 1)(y + 1) - 1}[sup]2[/sup] to [0, 1] as follows:

sum( P(i, j), j ) = 1

If n > y and n does not divide y + 1, P(n, n - y - 1) = a and P(n, n - 1) = 1 - a. Otherwise, P(n, n) = 1.

Now we need a second function p(k) from {1, …, (x + 1)(y + 1) - 1} to [0, 1] with the following constriant:

sum( P(i, j)p(j), j ) = p(i)

The probability that the unit with higher hit points wins is sum( p(k), k|(y + 1) ), and the probability that the unit with lower hit points wins is sum( p(k), 1 < k < y ).

To calculate that in general, you need to be able to solve a system of (x + 1)(y + 1) - 1 equations in as many variables. Good luck.

8

I think ultrafilter is proving this very formally – not that there’s anything wrong with that – but I also think you’re already near the solution. [sub]n[/sub]C[sub]r[/sub], or “n choose r” is the number of combinations of n objects, taken r at a time. Your formula,

P® = [sub]n[/sub]C[sub]r[/sub] * p[sup]r[/sup] * q[sup]n-r[/sup]

is correct for calculating the odds of n wins given exactly r trials; however, as I did above, you need to take into account how likely it is to have r trials at all.

The idea of using Markov chains is useful, since it is a good way to discuss the inevitable steady state of a system influenced by static probabilities. This page goes into more detail, but it’s been almost seven years since I took linear algebra.

9

On the “shots from the grave” thing… Suppose that instead of ending the battle when one unit dies, we let each battle last for a number of rounds equal to H[sub]1[/sub] + H[sub]2[/sub] -1. At one hitpoint lost per round, this guarantees that one unit will run out of hitpoints (because there’s no way to distribute that many hitpoints nonlethally), and also guarantees that we won’t see both units die (because that would require at least H[sub]1[/sub] + H[sub]2[/sub] rounds). Thus, extending the battle this long will not change the outcome at all, even if (as is likely) shots are fired from beyond the grave. I’m assuming here, incidentally, that all hitpoints are healed before the next battle.

10

This is exactly my reasoning, if you check the last paragraph of the OP and my further response to Jurph. It seems perfectly sound.