Probability of Winning Risk: 1 vs. 1, 2 Defenders

[Big-Daddy]

Homework Statement

The game of Risk follows these rules: (skip if you are already familiar with Risk and the casting of the dice)

---------------------------------------------------

Rules of Risk:

a) An attacker attacks, and a defender defends. The attacker can attack with any number of pieces less than or equal to how many he has, and a defender defends with all the pieces he has.

b) When the attacker attacks, he rolls with 1 die (if he is attacking with 1 piece), 2 dice (if he is attacking with 2 pieces) or 3 dice (if he is attacking with 3 pieces or more). When the defender defends, he rolls with 1 die (if he has one piece) or 2 dice (if he has 2 or more pieces). The roll of the attacker, and the roll of the defender, are independent of one another, i.e. they essentially occur simultaneously.

c) Of the rolls of the attacker's die/dice, align them in order from highest roll to lowest roll. e.g. {2,5,5} should be aligned {5,5,2}. Of the rolls of the defender's die/dice, align them in order from highest roll to lowest roll. e.g. {5,1}. Now compare the attacker's first, highest score to the defender's first, highest score: if the attacker's is higher, the defender loses a piece; if the defender's is higher or the same as the attacker's, the attacker loses a piece. Then compare the attacker's second score to the defender's scond score: if the attacker's is higher, the defender loses a piece; if the defender's is higher or the same as the attacker's, the attacker loses a piece. In my example, 5v5 so the defender wins the first, but 2v1 so the attacker wins the second, and the net result is that each side loses 1 piece. Note that, the defender having 2 dice total maximum, the attacker can only lose a maximum of 2 pieces per turn, and same for the defender.

d) The next turn, the defender proceeds with his new number of pieces, and the attacker with his new number of pieces, and the same thing happens again. This continues until one side runs out of pieces.

---------------------------------------------

What is:

a) the probability of an attacker winning on a given turn where a Attackers and 1 Defender are present [teacher later added the adendum that you may consider cases where a=1, a=2 and a≥3 separately],
b) the probability of an attacker winning overall when a Attackers battle 1 Defender [same adendum as a)]
c) the probability of an attacker winning on a given turn where a Attackers and 2 Defenders are present [same adendum],
d) the probability of an attacker winning on a given turn where a Attackers and 2 Defenders are present [same adendum],

Homework Equations

No clue. Obviously the probability of a single roll on either part is (1/6).

The Attempt at a Solution

My teacher likes to set general problems, which suggests it would be foolish to try and tackle a case as general as d Defenders all at once, when the problem says 1 and 2 defenders.

a) seems ok for a=1, as it'll just be (18+6)/36=2/3. That's just about the only case I can handle here.

 

[Simon Bridge]

(a) asks for the case of a attackers - so your probability should be a relation with an "a" in it.
If the number of defenders is 1 - then the attacker gets a tries to defeat a single die roll, at least one of which needs to be higher than the defender's.

(b) maybe look at a tree - turn 1 probability of win/loss ... follow the branches for turn two etc.

It can help to consider the converse:
i.e. (a,d)=(3,1) there is only one way the attacker loses overall right?
If d=1, and a=n, then how many times must the attacker lose a turn in order to lose over all.

Note: when I played Risk, the attack had to stop when there was one piece left since there needs to be one piece to occupy the defeated territory.

 

[haruspex]

a) The attacker can attack with any number of pieces less than or equal to how many he has.

As I recall, the number of dice the attacker rolls must be strictly less than the number of pieces in the attacking territory. (This achieves the requirement Simon mentions that the territory from which the attack is launched must not be left vacant in consequence. The victorious attacker is obliged to move in at least as many pieces as dice in his last roll.) You can handle that within what you have already done merely by defining the size of the attacking force, a, to be always less than the number in the attacking territory (contrary to what it says in (a) above). Note that the attacker can elect to attack with fewer.

a) seems ok for a=1, as it'll just be (18+6)/36=2/3.

Rolling one die each, the defender has the advantage, so it must be < 1/2.

 

[Big-Daddy]

(a) asks for the case of a attackers - so your probability should be a relation with an "a" in it.
If the number of defenders is 1 - then the attacker gets a tries to defeat a single die roll, at least one of which needs to be higher than the defender's.

How can I work out the probability for cases where the attacker has multiple dice? I think I got it right for when the attacker has only 1 die, defender has 1. P(A win)=(18-6)/36=1/3 (as haruspex pointed out below, my original estimate is the wrong way around) As I wrote it probably should be split up into considering 2v1 and then ≥3v1.

(b) maybe look at a tree - turn 1 probability of win/loss ... follow the branches for turn two etc.

It can help to consider the converse:
i.e. (a,d)=(3,1) there is only one way the attacker loses overall right?
If d=1, and a=n, then how many times must the attacker lose a turn in order to lose over all.

Yes, maybe: 1) seek to work out P(D wins overall), so that P(A wins overall)=1-P(D wins overall); 2) the only way this can happen is for A to keep losing; 3) if P(A wins turn) is constant for a≥3, I could do 1-P(A wins turn), and raise this to the power of some number of turns. Maybe we can come back to this after I've done a), but thanks, it is clearer now.

Note: when I played Risk, the attack had to stop when there was one piece left since there needs to be one piece to occupy the defeated territory.

Yeah I think this is a rule too, my teacher seems to neglect it. I think though that all we have to keep in mind to modify for the real game of Risk is that a≤(Pieces on Attacker's Square)-1.

 

[Big-Daddy]

As I recall, the number of dice the attacker rolls must be strictly less than the number of pieces in the attacking territory. (This achieves the requirement Simon mentions that the territory from which the attack is launched must not be left vacant in consequence. The victorious attacker is obliged to move in at least as many pieces as dice in his last roll.) You can handle that within what you have already done merely by defining the size of the attacking force, a, to be always less than the number in the attacking territory (contrary to what it says in (a) above). Note that the attacker can elect to attack with fewer.

Yup, I think that's ok. What happens in the aftermath of the battle (i.e. how many pieces the attacker moves in) we can probably ignore for the purpose of this question. And yes, Attackers≤(Pieces on Attacker's Square)-1. That's useful for when we're actually playing Risk but for the problem itself we can work purely with the number of pieces actually attacking.

Rolling one die each, the defender has the advantage, so it must be < 1/2.

Of course, sorry. I wrote the probability of the defender winning by accident. I thought the probability of the attacker winning is P(A wins turn, 1v1)=(18-6)/36=1/3.

This guess was poor. I just tried it by mapping out the possibilities, and it turns out that (out of 36) the attacker has 5+4+3+2+1=15 ways of winning, so P(A wins turn, 1v1)=15/36=5/12. The defender has 6+5+4+3+2+1=21 ways of winning so P(D wins turn, 1v1)=21/36.

How to come up with estimates for 2v1, ≥3v1?

 

[haruspex]

How to come up with estimates for 2v1, ≥3v1?

For a:1, the defender wins if all of the a are <= the defender's throw. If the defender rolls an r, what is the probability of that?

 

[Big-Daddy]

For a:1, the defender wins if all of the a are <= the defender's throw. If the defender rolls an r, what is the probability of that?

Clever method. Thanks, I've now reached this answer.

Part A: P(k Attacking Dice vs 1 Defending Die, Attackers win turn)=1-(1/6)*Ʃ(from r=0 to r=6)[(r/6)^k]

Part B: P(a Attackers vs 1 Defender, Attackers win overall)=(1/6)*Ʃ(from r=0 to r=6)[(r/6)] for a=1
P(a Attackers vs 1 Defender, Attackers win overall)=1-((1/6)*Ʃ(from r=0 to r=6)[(r/6)^3])^a-2*((1/6)*Ʃ(from r=0 to r=6)[(r/6)^2])*((1/6)*Ʃ(from r=0 to r=6)[(r/6)]) for a≥2

There might be a more comprehensive way of doing it for Part B, using sigma, which covers both possibilities in one, which may be necessary when we move on to later parts. If so please correct me.

Next, part c). How do I model the two defender scenario?

 

[haruspex]

Part A: P(k Attacking Dice vs 1 Defending Die, Attackers win turn)=1-(1/6)*Ʃ(from r=0 to r=6)[(r/6)^k]

Yes, though you don't need r=0.

Part B: P(a Attackers vs 1 Defender, Attackers win overall)=(1/6)*Ʃ(from r=0 to r=6)[(r/6)] for a=1

You lost the 1- and the raising to the power of a.

P(a Attackers vs 1 Defender, Attackers win overall)=1-((1/6)*Ʃ(from r=0 to r=6)[(r/6)^3])^a-2*((1/6)*Ʃ(from r=0 to r=6)[(r/6)^2])*((1/6)*Ʃ(from r=0 to r=6)[(r/6)]) for a≥2

Didn't follow the logic of that. Looks strange. Is that what you meant to write?

Next, part c). How do I model the two defender scenario?

It gets messier. See if you can get a recurrence relation.

 

[Big-Daddy]

You lost the 1- and the raising to the power of a.

Yup, I need the 1-. Raising to the power of a is pointless as that relation occurs only for a=1.

Didn't follow the logic of that. Looks strange. Is that what you meant to write?

Yup. Maybe if I put it like this it will make more sense.

We seek P(Defender Wins Overall). The probability the defender wins 1 turn where the attacker has k=3 is (1/6)*Ʃ(from r=0 to r=6)[(r/6)^3]; let this be p₃. The probability the defender wins 1 turn where the attacker has k=2 is (1/6)*Ʃ(from r=0 to r=6)[(r/6)^2]; let this be p₂. The probability the defender wins 1 turn where the attacker has k=1 is (1/6)*Ʃ(from r=0 to r=6)[(r/6)]; let this be p₁.

Now imagine that the attacker has a high number of pieces, a, with which to attack. For the defender to win overall, he must win every turn until k=a=2 (which will be a-2 turns), and then one turn where k=2, then one turn where k=1. So P(Defender Wins Overall)=p₃^a-2*p₂*p₁. Thus P(Attacker Wins Overall)=1-p₃^a-2*p₂*p₁ If a more rigorous way of doing this occurs to you I would love to hear because it might be necessary for the two-dice solution (but keep in mind that k is capped at 3, so for all a≥3, k=3, k cannot go higher).

It gets messier. See if you can get a recurrence relation.

I imagined it would be harder. There are a few different cases to look at now: P(Attacker wins 2 on Turn); P(Attacker wins 1, Defender wins 1); P(Defender wins 2 on Turn). Should I try doing it case by case?

 

[haruspex]

Yup. Maybe if I put it like this it will make more sense.

No, it's ok, I was misreading it. It's good.

I imagined it would be harder. There are a few different cases to look at now: P(Attacker wins 2 on Turn); P(Attacker wins 1, Defender wins 1); P(Defender wins 2 on Turn). Should I try doing it case by case?

What point are you trying to get to? I went through an analysis of this 40 years ago (yes, the game's that old), and what I wanted to work out was the expected losses of the attacker in a campaign through a series of countries with various numbers of defenders. For that purpose, you just have to build up a table of probabilities for various contexts (like, 3:2 with a result of 1 off each) by whatever grunt means then solve the recurrence relations that emerge.
E.g. for a country with one defender and a sufficiently large attacking force you get the probability that defender survives one round is about 1/3, so if E is the expected loss for the attacker in taking the country we get E = (1+E)/3, so E = 0.5.

 

[haruspex]

I wrote a spreadsheet with a 36x36 array for each of the cases two off attacker, two off defender, for the 3 dice against 2 scenario. It gives me:
2 off attacker: 0.29
2 off defender: 0.37
1 off each: 0.34
So at each roll, expected losses are 0.46 and 0.54. With A attacking D, A >> D >> 1, expected losses for attacker are (46/54) * D, or about 85% * D.

 

[Big-Daddy]

What point are you trying to get to? I went through an analysis of this 40 years ago (yes, the game's that old), and what I wanted to work out was the expected losses of the attacker in a campaign through a series of countries with various numbers of defenders.

That's monstrous! All I want is to solve part c) and d). Which are (I wrote part d wrong on the OP):

c) the probability of an attacker winning on a given turn where a attacking dice and 2 Defenders are present [cases are a=1, a=2, a=3],
d) the probability of an attacker winning overall when a Attackers and d Defenders engage over many turns [cases are a=1, a=2, a≥3],

It would be lovely to be able to find the probability of the attacker suffering k losses in a scenario such as that in d). From this we could find the expected value of k. But that would be an extension problem.

For that purpose, you just have to build up a table of probabilities for various contexts (like, 3:2 with a result of 1 off each) by whatever grunt means then solve the recurrence relations that emerge.
E.g. for a country with one defender and a sufficiently large attacking force you get the probability that defender survives one round is about 1/3, so if E is the expected loss for the attacker in taking the country we get E = (1+E)/3, so E = 0.5.

Ah so there's no streamlined way of doing it. That's ok.

OK, so I'm to count the number of events in which each outcome (Attacker wins 2, Defender wins 2, Each win 1) occur and that gives me the probability of each of these happening for a given time. Can you give me the results in terms of fractions for each of the 6 cases then (the 3 outcomes mentioned above, for 3v2, and for 2v2)? Or explain if there's some easier way of writing this than going down a 216x36 Excel spreadsheet (7,776 cells!) and filling in A2, D2, AD, then doing the same on a 36x36?

That would take care of part c), leaving only part d).

 

[haruspex]

I reduced it to a 21x21 array. I attach the spreadsheet for the two-off-attacker case.
(I use OpenOffice, which allows me to save the file as .xls but not as .xlsx. The PF upload doesn't accept .xls, so I renamed it from .xls to .xlsx. This seems to work, but if you have a problem download it and rename back to .xls.)
The first two columns give the top two of the attacker's throw, the first two rows are the defenders throw. The third column counts the ways in which the attacker's two best dice can arise. The body of the array counts the ways in which it can mean two off the attacker.
To get two off defender, copy the sheet and change the logic of the cells in the body of the array.

 

[Big-Daddy]

I reduced it to a 21x21 array. I attach the spreadsheet for the two-off-attacker case.
(I use OpenOffice, which allows me to save the file as .xls but not as .xlsx. The PF upload doesn't accept .xls, so I renamed it from .xls to .xlsx. This seems to work, but if you have a problem download it and rename back to .xls.)
The first two columns give the top two of the attacker's throw, the first two rows are the defenders throw. The third column counts the ways in which the attacker's two best dice can arise. The body of the array counts the ways in which it can mean two off the attacker.
To get two off defender, copy the sheet and change the logic of the cells in the body of the array.

Thank you for the spreadsheet. :)

Now, let me define the probabilities in an abstract way so I can calculate them all at the end. The probability of 3 attacking dice versus 2 defending dice resulting in the attacker winning both for a turn is given by P(3A:2D, Aw2); 3 attacking dice versus 2 defending dice resulting in the defender winning both for that turn is P(3A:2D, Dw2); 2 attacking dice versus 2 defending dice resulting in one loss each is P(2A:2D, AD1). I hope this notation is clear.

What, then, are the recursive relations we need to solve part d)? The issue is that 3 outcomes seem possible per turn (2 for some turns, but 3 for most turns) and obviously having factor-3 branching will produce good results.

 

[haruspex]

Now, let me define the probabilities in an abstract way so I can calculate them all at the end. The probability of 3 attacking dice versus 2 defending dice resulting in the attacker winning both for a turn is given by P(3A:2D, Aw2); 3 attacking dice versus 2 defending dice resulting in the defender winning both for that turn is P(3A:2D, Dw2); 2 attacking dice versus 2 defending dice resulting in one loss each is P(2A:2D, AD1). I hope this notation is clear.

What, then, are the recursive relations we need to solve part d)? The issue is that 3 outcomes seem possible per turn (2 for some turns, but 3 for most turns) and obviously having factor-3 branching will produce good results.

If you don't mind I'll abbreviate your notation a little: P(a, d; m, n) = prob that a roll of 3 dice against two results in m off attacker, n off defender.
Let A(x, y; z) be prob of an attacking army of x against y being reduced to z.
For x >= 4 and y >= 2:
A(x, y; z) = P(3, 2; 2, 0)*A(x-2, y; z) + P(3, 2; 1, 1)*(x-1, y-1; z) + etc.
with boundary conditions like A(1, y; 1) = 1.

 

[Big-Daddy]

I reduced it to a 21x21 array. I attach the spreadsheet for the two-off-attacker case.
(I use OpenOffice, which allows me to save the file as .xls but not as .xlsx. The PF upload doesn't accept .xls, so I renamed it from .xls to .xlsx. This seems to work, but if you have a problem download it and rename back to .xls.)
The first two columns give the top two of the attacker's throw, the first two rows are the defenders throw. The third column counts the ways in which the attacker's two best dice can arise. The body of the array counts the ways in which it can mean two off the attacker.
To get two off defender, copy the sheet and change the logic of the cells in the body of the array.

I've gone over the spreadsheet now and I'm a little confused. Can I ask what the final values, in terms of fractions (if available), you got were for the three-attacker versus two-defender case? i.e. probability that attacker wins 2, probability that each win 1, probability that the defenders win 2.

 

[haruspex]

Two off attacker: 2275/6⁵; two off defender: 2890/6⁵.

 

[Big-Daddy]

Two off attacker: 2275/6⁵; two off defender: 2890/6⁵.

Thanks very much. Which would leave a 2611/6⁵ probability of both attacker and defender losing one. Can I ask how confident you are in these figures? I'm still trying to come up with an efficient way to tabulate the whole thing for 3v2.

Can I check some figures for the 2 attackers vs 2 defenders scenario?
Two off attacker: 581/6⁴
Two off defender: 295/6⁴
One off attacker, one off defender: 420/6⁴

And do you have the fractional probabilities for the 1 attacker vs 2 defenders scenario?

 

[Big-Daddy]

I've got the turn-by-turn transition probabilities.

Could you tell me if you have, say, a table of the exact fractional values calculated for probability of attacker (or defender) winning overall for a attackers vs d defenders?