Straight Dope Message Board > Main Am I calculating these odds right? (multiple trials, uneven winning conditions)
 Register FAQ Calendar Mark Forums Read

#1
11-08-2004, 02:36 PM
 erislover Guest Join Date: Nov 2000
Am I calculating these odds right? (multiple trials, uneven winning conditions)

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(r) = nCr * pr * qn-r
where
P(r) 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.

Yes, I know about the existence of a CivIII calculator for this. The point is knowing the math. It is an interesting problem.
#2
11-09-2004, 08:49 AM
 Jurph Guest Join Date: Oct 2003
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.605). 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.605 * 0.402 = 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.403 = 6.4%

3 losses interrupted by a win - 3 occurrences, odds of 0.403*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%) + (5*3.11%) + (15*1.24%) / (21 + 35) = roughly 23%, rounded

The idea of enumerating all the different ways this can happen is the output of the nCr "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
11-09-2004, 10:41 AM
 ultrafilter Guest Join Date: May 2001
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
11-09-2004, 02:58 PM
 erislover Guest Join Date: Nov 2000
Quote:
 Originally Posted by Jurph 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.
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
11-09-2004, 03:14 PM
 Bryan Ekers Guest Join Date: Nov 2000
Quote:
 Originally Posted by erislover 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?
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:
Code:
```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
11-09-2004, 03:27 PM
 erislover Guest Join Date: Nov 2000
Quote:
 Originally Posted by Bryan Ekers 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.
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
11-09-2004, 07:29 PM
 ultrafilter Guest Join Date: May 2001
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}2 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
11-09-2004, 08:11 PM
 Jurph Guest Join Date: Oct 2003
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. nCr, or "n choose r" is the number of combinations of n objects, taken r at a time. Your formula,

P(r) = nCr * pr * qn-r

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
11-10-2004, 12:18 AM
 Chronos Charter Member Join Date: Jan 2000 Location: The Land of Cleves Posts: 47,954
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 H1 + H2 -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 H1 + H2 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.
__________________
Time travels in divers paces with divers persons.
--As You Like It, III:ii:328
#10
11-10-2004, 10:51 PM
 erislover Guest Join Date: Nov 2000
Quote:
 Originally Posted by Chronos Suppose that instead of ending the battle when one unit dies, we let each battle last for a number of rounds equal to H1 + H2 -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 H1 + H2 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.
This is exactly my reasoning, if you check the last paragraph of the OP and my further response to Jurph. It seems perfectly sound.

 Bookmarks

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Main     About This Message Board     Comments on Cecil's Columns/Staff Reports     Straight Dope Chicago     General Questions     Great Debates     Elections     Cafe Society     The Game Room     In My Humble Opinion (IMHO)     Mundane Pointless Stuff I Must Share (MPSIMS)     Marketplace     The BBQ Pit Side Conversations     The Barn House

All times are GMT -5. The time now is 08:44 AM.