25 July 2011

Taking a RISK - the distribution of armies lost

I came across the following question at boardgames.stackexchange.com:
How can I estimate my chances to win a Risk battle?
Elliot Avedon Virtual Museum of Games, Courtesy Canadian Museum of Civilization.
Now there is already plenty of material on the web about probability in the popular boardgame RISK*, but maybe I can add just a little bit more.

Most people already know that, given the choice, the Attacker should always 3 dice and the Defender should always roll 2, since this always gives the best results (a Nash equilibrium). Since it's always the Attackers choice to roll an attack or not, the relevant question seem to be "How many armies [X] will the Attacker lose if they make [N] attack rolls?"




Using some probabilities from a RISK FAQ for the probabilities of losses, I calculated the average attacker losses (about 0.921 per roll) and standard deviation (~0.81). It's not possible to lose 0.9 armies in RISK! as the attacker losses vary between 0, 1, and 2 per roll. However, as the results of many attack rolls are added up, the losses will begin to resemble the normal distribution. We can plug the average and standard deviation into a normal approximation formula, and get back a probability for losses in a fairly simple calculation. For a given number of attack rolls "A" and number of attacking armies lost "K",
Z = (K - 0.921*A) / (0.811*sqrt(K))
where Z is a standard normal variable (mean 0, standard deviation 1), and the probability of K-or-fewer losses in A attack rolls can be evaluated with the standard normal probability CDF function, otherwise known as the NORMSDIST(Z) function in Excel. That's pretty much it, except maybe for some graphs to show off the results.


Cumulative probability of K attacking armies lost in 25 attack rolls

The blue line shows the cumulative probability of K losses in A attack rolls (vertical red line). The yellow triangles show an approximate 50% confidence interval, meaning that your actual losses should be within this range 50% of the time. The red diamonds show a 90% interval for the same. These intervals are actually slightly wider than the stated 50%/90%; because I rounded outwards to the nearest whole number of armies, and there is no other good way to do it.

Cumulative probability of K attacking armies lost in 35 attack rolls

Recall this is an approximation, and it depends on there being lots of independent random events (dice rolls!) for the approximation to work well. It should start to work very well somewhere between 20-30 attack rolls, and depending on how fussy you are may give usefully accurate results for as few as 10-15 rolls. For smaller battles, or deciding whether or not you should attack just one more time, you might consider more accurate methods (look here, for starters).

Cumulative probability of K attacking armies lost in 70 attack rolls

You can think of this in terms of Defender losses too. Two armies are lost with every attack (between the attacker and defender), so if there are A attack rolls and K attacking armies are lost, that means the defender will be losing 2*A - K armies. For instance, in 25 attack rolls a total of 50 armies are lost; the probability of the attacker losing 20 armies the same as the probability of the defender losing 30.

Cumulative probability of K attacking armies lost in 50 attack rolls

Nostalgic Tangent: Calculating the probabilities of losses for the attacker and defender was one of my first mathematical efforts to figure out a game. I didn't know how to do the calculation, but I wrote a program on my Apple II+ to roll lots of electronic dice for me, and calculated the probabilities that way. Later I learned that this technique is called Monte Carlo simulation, and statisticians do this regularly to examine the properties of new statistical methods.

*** There WILL BE a link to the spreadsheet for these calculations, but it's getting late, so I'll have to add that in tomorrow. ***


Having written this, I realized that I haven't quite answered the question. I've given the probability for a given number of attacks/losses, but the question is "How many armies will it cost me to win?"

There is another approximation to answer that, but it's much less well known. I guess I'll have to write a part 2. Stay tuned!

---------------------------------------------------------------------------------
* RISK is a registered trademark of HASBRO, Inc., of course.

Footnote: The RISK! game images used in this post are from Elliott Avedon's Virtual Game Museum, and are used with permission of the Canadian Museum of Civilization. The Virtual Game Museum has much more interesting game related information, and I may be posting about it again.

No comments: