Odds in the game of Risk 3

[karluk]

The "conquer the world" board game, Risk, decides the result of an attack on one territory from another by tossing dice. The attacker gets to toss as many as three dice, while the defender is limited to no more than two. To partly compensate for this advantage, the defender wins all ties.

So, in a typical attack, the attacker will roll three dice and pick out the biggest two numbers showing. The defender rolls only two dice and keeps both numbers. The attacker and defender then compare numbers, high vs. high and low vs. low. There are two armies at stake. If the attacker's high number is bigger than the defender's high number, the attacker wins one army. Otherwise the defender wins one army. Similarly, the comparison of attacker's low number vs. defender's low number also results in a win or loss of one army, depending on how low numbers compare.

The problem for your consideration is to calculate the odds of the attacker winning in a three vs. two dice attack in the game of Risk. This means the attacker's long term odds of success from repeated three vs. two attacks.

When I was in college, I took the trouble to calculate these odds by hand. I haven't worked on the problem since then. Risk is well-enough known that I'm sure it's easily possible to find the odds on the internet, but obviously you are supposed to figure it out yourself.

Unless I missed a possible simplification, the calculations required are difficult to perform by hand, but easily done by computer. I will be interested in seeing if the odds I caculated in college are confirmed or disproven by the members of this forum.

 

[kwbMitel]

As it turns out it was a pretty minor thing. In those cases where the attacker was only throwing 1 die, while the defender was throwing 2, I had placed a marker of X for the Attackers second throw. As it turns out, X is considered greater then digits 1 to 6 and was being registered as a loss for the defender. This is now corrected. I'm still trying to wrap my head around why this caused the remainder to always be odd but lucky that it did or I wouldn't have seen the error.

This does not significantly change my stats except for the defender remaining armies when the defender wins.

I also spotted 1 other minor error in that I was counting the rolls incorrectly. The limits are actually 8-18 for rolls not 10-20

So This is the updated data after these corrections:

Average amount of rolls - 13.23 (high = 18, Low = 8)
Average remaining armies for Attacker - 4.0847 (high 16, Low 1)
Average remaining armies for Defender - 2.3815 (high 16, Low 0)
Average Wins for Attacker - 54.77%
Average Wins for Defender - 45.23%

Note: I had to run 20000 to get a result of 16 remaining armies for the defender. Result was 2 in 20000 vs 10 in 20000 for the attacker. This seems about right.

Does anyone have a formula to see how close the numbers above are?

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

Re-running the numbers for lowest Equal Match where the odds favor the attacker, 11 no longer makes the cut.

12 appears to be the lowest.

The other part about starting with 1 less requires a much higher number apparently. Still working on that.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[kwbMitel]

Secondly, what is the minimum number of armies (A) the attacker must have, so that even if the defender has one more army (A + 1), the odds still favor the attacker?

It appears that that number is 19 (to defenders 20)

**********************************************
What's most important is that you realise ... There is no spoon.

 

[karluk]

In order to get precise results for an n vs. n battle, we need to calculate the exact probability of each outcome for each possible dice combination. I have done this, although I have not yet double-checked my results. The numbers are:

for three attacking dice vs. two defending dice
2-0 win for attacker - 2890/7776
1-1 split - 2611/7776
0-2 win for defender - 2275/7776

for two attacking dice vs. two defending dice
2-0 win for attacker - 295/1296
1-1 split - 420/1296
0-2 win for defender - 581/1296

for three attacking dice vs. one defending die
1-0 win for attacker - 855/1296
0-1 win for defender - 441/1296

for two attacking dice vs. one defending die
1-0 win for attacker - 125/216
0-1 win for defender - 91/216

for one attacking die vs. two defending dice
1-0 win for attacker - 55/216
0-1 win for defender - 161/216

for one attacking die vs. one defending die
1-0 win for attacker - 15/36
0-1 win for defender - 21/36

 

[kwbMitel]

Confirming I get the same answers for:

3 vs 2 - Yes
3 vs 1 - Yes
2 vs 2 - Yes
2 vs 1 - Yes
1 vs 2 - Yes
1 vs 1 - Yes

Double check completed

**********************************************
What's most important is that you realise ... There is no spoon.

 

[karluk]

Ok, using the above probabilities, I get the following inflection points where the advantage switches from the defender to the attacker:

equal armies:
11 vs. 11 - 49.40%
12 vs. 12 - 50.65%

attacker has one fewer army:
17 vs. 18 - 49.42%
18 vs. 19 - 50.39%

attacker has two fewer armies:
23 vs. 25 - 49.87%
24 vs. 26 - 50.69%

attacker has three fewer armies:
29 vs. 32 - 49.82%
30 vs. 33 - 50.54%

attacker has four fewer armies:
34 vs. 38 - 49.46%
35 vs. 39 - 50.13%

attacker has five fewer armies:
40 vs. 45 - 49.45%
41 vs. 46 - 50.01%

attacker has six fewer armies:
46 vs. 52 - 49.74%
47 vs. 53 - 50.30%

 

[karluk]

By the way, these results, although unverified, were actually quite easy to calculate. That's because the possible states of a Risk battle comprise a Markov chain. Suppose that P(i,j) denotes the probability that the attacker will win a battle starting with the attacker having i armies and the defender having j armies. If I want to calculate P(12, 12), for example, I need to have only a few facts at hand. The only possible results of a 3-attack vs. 2-defend dice roll are 10 vs. 12, 11 vs. 11, and 12 vs. 10. So, suppose I'm lucky enough to know the actual values of P(10, 12), P(11, 11) and P(12, 10). I have already calculated the odds of getting from 12 vs. 12 to 10 vs. 12, 11 vs. 11, and 12 vs. 10, so

P(12, 12) = 2275/7776 * P(10, 12) + 2611/7776 * P(11, 11) + 2890/7776 * P(12, 10)

In other words, I know P(12, 12) in terms of the odds of various outcomes of a dice roll, combined with the outcomes of a few other battles. This type of calculation lends itself extremely naturally to a spreadsheet, and in fact I calculated the above odds using an Excel spreadsheet. Roughly speaking, I calculated the contents of row 12, column 12 of the spreadsheet by multiplying the contents of row 10, column 12 by 2275/7776, then adding the contents of row 11, column 11 multiplied by 2611/7776, and finally adding the contents of row 12, column 10 multiplied by 2890/7776.

This technique of determining an unknown probability by following a Markov chain down through simpler cases is widely used in probability theory. It could be used, I believe, to calculate the exact odds of getting a multiple of nine in SidYuca's "guess the missing digit" puzzle. The Markov chains in that puzzle are more complicated and lengthy than those in the game of Risk, but the same type of calculation would work.

 

[kwbMitel]

The Even Armies 12 vs 12 agrees with my simulator (or the other way around)

The simulator said 19 vs 20 was required for 1 less army.

50.1%

**********************************************
What's most important is that you realise ... There is no spoon.

 

[karluk]

The simulator said 19 vs 20 was required for 1 less army.

Yes, I noticed the same discrepancy when I posted my results. I suspect that my results are accurate, mostly because I have taken the liberty to do an internet search and found a site that confirms my calculations. One also has to take into consideration that simulations have an inherent margin for error, since they only claim to approximate the true odds, not to compute them exactly.

Here is a link to a Risk odds calculator

http://www.dandrake.com/risk.html

 

[kwbMitel]

Regarding approximation in simulators. This is why I run so many trials. 20000 in the last case. I find the variation cancels out and you end up with a number you can be confident in. As long as you do enough trials anyway.

In this case, 20000 may just not be enough.

I'll try to make my simulator more efficient so that I can manage more trials more quickly.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[karluk]

It's possible to glean all sorts of other interesting tidbits from my spreadsheet. Suppose, for example, the attacker is unwilling to attack without a 90% probability of success. How big of an invading force is needed for various sized defending forces? I get the following results:

three army advantage required
4 vs. 1

five army advantage required
7 vs. 2
8 vs. 3

six army advantage required
10 vs. 4
11 vs. 5
12 vs. 6

seven army advantage required
14 vs. 7
15 vs. 8
16 vs. 9
17 vs. 10
18 vs. 11

eight army advantage required
20 vs. 12 through 31 vs. 23

nine army advantage required
33 vs. 24 through the limit of my spreadsheet at 50 vs. 41

 

[kwbMitel]

Ok, I made the simulator more efficient.

I can now run a million trials in less time that the previous 10,000.

It did make a difference.

18 vs 19 now comes in @ 50.3259%

Close enough for me.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[karluk]

Thank you very much for being so willing to run your simulations, kwbMitel. Now that I've calculated the exact odds, the simulations provide mostly just reassurance that there's no glaring error in my calculations. But earlier in this thread they provided a major motivation to me to go out and compute the exact odds. I knew that my original reasoning that the advantage switches to the attacker at 16 vs. 16 wasn't precise enough to rule out the findings of your simulator. But, I would have guessed that your estimate of a switch-over at 12 vs. 12 was way too low. So I knew I needed to get more accurate odds to be able to confirm whether your simulations were accurate. As it turned out, you were 100% correct on that one.

It looks to me as if the number of different ways to to toss dice grows exponentially as the number of armies increases. That's probably why you were able to get accurate results with 10,000 trials at 12 vs. 12, but needed 1,000,000 trials at 18 vs. 19.