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?"

Elliot Avedon Virtual Museum of Games, Courtesy Canadian Museum of Civilization.

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.

Dice Distributions Revisited

Recent thoughts about calculating the distribution of the maximum sum of several dice (ex: roll 3, sum the highest 2) made me realize I needed a better tool for calculating the distribution of sums of dice in the first place. I first wrote about this some time ago in Dice Distributions, so I knew how to do it better, I just hadn't gotten around to doing it.

Tangent: While researching this I can across a great set of mathematical Dice Problems from Doctormatt (Web Page, Blog).

And now back to our story -

I first set up a spreadsheet to give me Pascal's Triangle, which looks like this:

This gets used in lookup functions to calculate (in a second worksheet) what I'm calling the "Dice Triangle", The number of dice [N] rolled is indicated in the column headers, and the sum of N D-sided dice [X] rolled in indicated in the first column. The number of ways to roll that sum is indicated in the table. The number of sides on the die [D] can be changed by entering a different value into the green shaded cell.

The first D rows of the table come directly from Pascal's Triangle. Subsequent rows are calculated from previous rows of this table. A few more details of how this is done in my earlier post (Dice Distributions), otherwise you can ask me, or dig into the spreadsheet for yourself (sorry, in a hurry today).

Here is the spreadsheet: Dice Distribution Calculator
I have not made this public, so you cannot change it directly online. You can download a copy for yourself (under the File dropdown) and play with it to your hearts content.

Maximums and Minimums of Dice Rolls

A week month a while back I received questions from Christian and a read post from Saxywolf on essentially the same question: What is the probability of rolling a given value on an D-sided die, if you roll N dice and take the highest (or the lowest).

Here's the trick:
The probability of rolling a 1 on 1 d6 is 1/6. (regular 6-sided dice)

For 2d6 the probability of rolling a 1 as the maximum is 1/6 times 1/6, or 1/(6*6) = 1/36.

For Nd6 the probability of rolling a 1 as the maximum is 1/6 times itself N times, or (1/6)^N.

For D-sided dice just substitute D for 6 above, so that the probability of rolling a 1 as the maximum of N D-sided dice is 1/D times itself N times, or (1/D)^N.

Now consider the problem of rolling 2-or less as the maximum. The probability of rolling 2-or-less is 2/D, and the probability of rolling a  2-or-less as the maximum is 2/D times itself N times, or (2/D)^N.
That's 2-or-less, but we really just want the probability of rolling 2, not 1 or 2.  BUT we already know the probability of rolling a 1 as the maximum on the same dice, so we can subtract that to get what we want:

The probability of rolling a 2 as the maximum is 2/D times itself N times, minus the probability of rolling 1 as the maximum, or (2/D)^N - (1/D)^N.

And that's it. Using the same math you can work the complete distribution of the maximum for any number of dice with any number of (equally likely) faces. Just start at 1 and work up. For minimums, just turn the problem around and find the probability of X-or-less.

Still too much math? Fear not for there is a spreadsheet to do the calculations for you:
 Link to Google Docs Spreadsheet

See the blue numbers in the green-shaded cells? Change those to the number of side on your dice and the number you want to roll, and it will calculate the distribution for you. It might even work inside the blog?Nope, but it was worth a try. The spreadsheet is now public and can be edited at the link above (also downloaded). Changes made there WILL show up here when the page is reloaded, which means you are looking at whatever was most recently entered.



And a chart to display the results:

This is a bit of an experiment, both linking to a shared spreadsheet, and adding the HTML code to it directly inside my blog post. One upshot of this is that when one person changes the spreadsheet, it will change it for everyone. Play nice! Let me know if it works too. [Fixed!]

Sword and Dragon Mission Matrix

Our local Battletech group has been playing through Starterbook: Sword and Dragon, and we are having a lot of fun doing it. Peter, my cohort in planning for team Fox's Teeth came up with this state diagram as a way to follow the possible mission tracks, to help us plan in advance:

Nifty, but very difficult to follow as many of the arrows are on top of one another. This put the idea in my head to redo it in matrix form. This entailed repeating most of the work Peter had already done, but in the process I gained a much better understanding of how the Warchest Point system works. I'd never paid much attention to this before, so it was worth the effort:

The left-hand side lists the possible current missions, along with prerequisites and Warchest Points (WP), number of 'Mechs in the scenario, and WP rewards for a successful mission. If you follow the row for the current mission over to the right-hand side you can see what missions are available following the current mission. There is a "1" in the cell if that mission can be played next, and blank otherwise. I also added color codes for missions that are only available to either Fox's Teeth or Sorenson's Sabres. This has been corrected for the published errata too, so if you are looking for the mysterious Probe or Holding Action missions, they have gone away. You can download this in spreadsheet format:

Download as Google Docs spreadsheet.
Download as Excel 2003 spreadsheet.
Download as Excel 2007 spreadsheet.

The Creative Commons license I apply to this blog obviously can not apply material derived from this Catalyst Game Labs product. However, I would appreciate being credited as author if you pass this on. The Mission Matrix form is an idea I will develop for my own purposes. Send any suggestions or comments along too, and I'll see about working them in.

I should probably blog about the play sessions too, because there is a lot going on there. Not tonight tho, it's late!

More Exploding Dice: T&T Saving Throws

I received a request from Christian Lindke, author of Cinerati, about the probability distribution of a different sort of "exploding" dice: Saving throws in Tunnels and Trolls. I have previously written about Exploding D10, and this is a closely related problem. I'll let Christian explain it ...

I am getting ready to do a few posts on Tunnels and Trolls.  Specifically, I will be proposing an alternate combat resolution system -- one based on an existing system within the game.  I want to play around with the concept of using T&T "Saving Throws" as the basis for all mechanical resolutions in the game.

In T&T the saving throws are resolved by comparing a statistic to a difficulty # and using the result as the basis for a 2d6 roll.  The actual equation is [15 + (level of challenge x 5)] - Statistic = Target Number.  So a character with a Luck of 12 attempting a 1st level challenge would need a result of (15+5-12=8) eight or better to succeed on the attempt.  Figuring out the probabilities on a basic 2d6 roll is a simple affair, but in T&T a player who rolls doubles keeps the result, re-rolls and adds the result to the prior sum until the player no longer rolls doubles.  It's an open ended doubles system.  What would be basic equation be to determine probabilities in this case.  Logically, given that the chance of doubles is 1/6, it seems that the probabilities would be the same as a normal open ended d6 roll for each die (which I believe produces an average of 4.3 per die), but I'd like an equation I can use to determine the game balance as characters advance etc.  I'd like to use the base probability of an "average" character of a given level attempting a task as the basis for my new system.

If you could be of assistance, it would be greatly appreciated.

A friend of mine had noted that asking me questions like this is like teasing a small child with a shiny toy, holding it just above my reach; You just know I'm going to jump up and try to get it - and I did. ;-)

As I said, this is very similar to how the probability for Exploding D10 work in the MechWarrior 3rd edition RPG. With D10X you count the roll if is in the range 1-9, and if it is a "10" you count the 10 and roll again (that the explosion). Rinse and repeat until done. In T&T we have a 2d6 roll that explodes if a tie is rolled on the two dice instead of the highest value on either one.

As with D10X, this breaks down into two three parts - which are a geometric series, the value of rolling ties tie, and the value of rolling no-ties.

The probability of rolling a ties on 2d6 is 1/6, so the geometric series starts of like this:
0 ties with probability = 5/6 = 0.8333
1 tie with probability = (1/6)*(5/6) = 5/36 = 0.1389
2 ties with probability = (1/6)*(1/6)*(5/6) = 5/216 =0.02315
3 ties with probability = (1/6)*(1/6)*(1/6)*(5/6) = 5/1296 = 0.003858

... and so on out to infinity. The average number of ties in a series is (1/6)*1/(5/6) = 1/5 = 0.2, which is nice it you only want to know the average 2d6X roll (which is 8.4, btw), but we need the entire probability distribution.

Now there are six different ways to roll a ties, and they have values of 2,4,6,8,10,12, all with 1/6 probability, which is just the same as 2 times the value of a 1d6 roll. I will note this as 2*1d6. Combining this with the geometric series, we get this:

a "0" with probability = 5/6 = 0.8333

a 2*1d6 roll with probability = (1/6)*(5/6) = 5/36 =0.1389
a 2*2d6 roll with probability = (1/6)*(1/6)*(5/6) = 5/216 = 0.02315
a 2*3d6 roll with probability = (1/6)*(1/6)*(1/6)*(5/6) = 5/1296 = 0.003858
... and so on out to infinity.

NOTE: The probability of zero ties is really 0.8333 (the first bar); I chopped off the graph to show the what ties actually add in, which really isn't very much. I calculated the probabilities out to 6 consecutive ties, which is only a little bit of overkill. It could go on forever, but unless you are infinitely lucky (and have a lot of spare time on your hands) your streak of ties will eventually come to an end, where you add the sum of the the final not-tied dice to your previous total. That probability is a modification of the usual discrete triangular 2d6 distribution, and it looks like this (2d6-ties):

The final step to pull this all together is a bit messy, so pardon my hand-waving over the details (if you really want the nitty-gritty, look in the accompanying spreadsheet). You multiply each probability in the geometric series with each the probabilities in the 2d6-ties distribution and sum up  the corresponding values of the roll, then tally up the total probability for all combinations with the same sum. It looks like this:

This looks a lot like the 2d6 distribution with a long "tail" tacked onto the right hand side. Here's the cumulative probability:

Finally, a table of the rolls and cumulative probabilities, though if you really want to numbers it's probably easier to grab them from the spreadsheet. Again, the table theoretically should go to infinity, but in practice you will only rarely see any rolls greater than 20.

I'm curious to see what Christian does with this, and I'll link to his post(s) on the topic when he has them up.

Have fun rolling the dice!


[Edit: Typo corrected, added decimal probabilities.]
[Edit2: Added link to spreadsheet, which I swear I did once already.]

Improved Dice Test

In response to a question about the "Fair Dice" test, I have updated my spreadsheet for the Chi-Square test of homogeneity (Fair Dice) so that it will recognized the number of "sides" being tested for any number up to 20. I think this is fairly self-explanatory, just leave that green shaded cells blank if you don't need them. I have not tested this extensively, so if it gives you any troubles let me know.

Houston, we have a problem

[This is something of a failed post - a cool idea that was too complex for a simple demonstration, and a false start on the correct solution. I've been sitting on it for almost two weeks now and haven't had time to rework it. I'll post it anyway, and maybe someone can help me fix it.]

Having discussed a simple graph paper race game, and mentioning that it would be fairly easy to turn it into a "space race" sort of game, I set out to do so. Further, I'm writing this as I'm working out how the game works in an Excel spreadsheet (does this count as live blogging?). Here is my progress so far (This may be a bit cryptic, but this is also a test for me to see if I can convey these sorts of ideas to my readers via a spreadsheet, without going into painstaking detail. Question? Please ask, and I'll try to do better.):
The green shaded cells on row 2 (turn 0) allow you to enter starting conditions for the game. The first six values are ddX/ddY, dX/dY , X/Y are for acceleration, starting vector, and starting position (all initially zero). The next six are "goal" parameters, X-Y coordinates that define the "race course" for this game, here the point (5,10), (10,5), and (15,15). The "ship" must pass within a distance of one from each of these points to successfully complete the course, which is indicate here by the first three gold shaded cells, which are "1" is the goal has been acheived and "0" otherwise. The final gold shaded cell is the number of turns needed to acheive the third and final goal.
In the green shaded columns ddX/ddY I have entered a starting condition, a series of moves that acheive each of the three goals. You can see it tool my ship 14 turns to reach the 3rd goal, and I'd like to do better. Tinkering with this by hand I could probably come up with a good solution, but I want to do this another way. Excel has an "Add-in" tool which used Newton's Method to find the solutions to mathematical formulations that meet certain criteria. This is why I set the goals in the spreadsheet, so I could use the goal to allow the Solver to help me find the best solution. So now I use Tools --> Solver ... and discovered I left something out. I need to be able to limit the thrust (ddX/ddY) to a maximum of one. I'll add this in, but it's now going to turn out a little differently than I expected. Here is the new starting solution: And now I can use the solver ... ok ... more problems ... try to imagine me banging my head on the keyboard ...
... banging my head because the solver fails and goes off to a nonsense solution, ignoring the course after the first goal. This problem trickier than I had realized, and so I have not set it up in a way that Newton's method can find the best answer, or even any answer at all.

Uncle - I give up - for now at least. I do not mind that this problem escapes me for the moment, because I had fun trying. I have a good idea of what I did wrong, so I'll think on it and try again later.

Here is the spreadsheet if you want to try it yourself.

[Epilogue]
Since I wrote that a few evenings weeks ago I came back and made another effort. It turns out my goals were a really bad way to formulate the problem. I made some marginal improvements, but nothing really worth showing off. I've made this work before, and the method deserve a better demonstration that I've given it here.

A Random Walk Down Monopoly Lane

Since my Candyland post seemed to get a good response, I thought I'd take a stab at a few other games everybody knows. "How about Monopoly?", I thought. [Let's do this right at least once: it's Monopoly®.] A small amount of research revealed a wealth of material on probabilities of landing on each square, expected incomes, expected payback times, probability of landing in jail and much much more. Most of those links take you to the superb Probabilities in the Game of Monopoly page by Truman Collins. Since Truman and others have already done such a good job on this topic, and I already discussed the idea of a Markov chain earlier, I decided I needed a different angle on this game.

Describing the probabilities of landing on each square as a Markov process is useful information, and you might easily use that to improve your play, but it doesn't describe the actual progress of the game. Unlike Candyland, Monopoly isn't about what square you are on and getting to the end, it's about accumulating wealth. ALL the wealth. A full description of how this works in Monopoly would be quite long, but we might learn a bit by constructing a much simpler sort of game which just keeps track of wealth.

Consider a game where two players, call them P1 and P2, start with equal amounts of money, and each turn they trade some random amount of money to the other player. If we think about the difference in wealth between Players 1 and 2 (P1 $ minus P2 $), and plot this value over a series of turns, it might look something like this (to right). Here I set up a spreadsheet where each player randomly gives the other player between $0 and $19 each turn. This sort of series is known as a Random Walk.

Here is another plot with ten similar random walks. In these instances P1 is behind P2 in wealth at turn 200 (the difference is negative) more often than not. This just random variation, and if we looked at many such plots, we expect should expect that P1 will be winning (wealthier than P2) 50% of the time. In this respect the game is fair; it is completely random and no player has any advantage.

"Now what?", you say. I created a really boring game that no one would ever play. Let's make the game, which I will now refer to as "Monopoly-Walk", a little more complicated by adding or changing some rules that make it a little bit more like the original Monopoly:

1) Let each player start with $2000.
2) Let each player gain $20 per turn.
3) On each turn both players randomly give each other a randomly determined amount of money between 0% and 6% of the other player's wealth.
4) When one player controls all the wealth, the game is over.

Rules #1 and #2 are similar to Monopoly; each player starts with equal wealth, and gain wealth over time. My version has a fixed income every turn for simplicity.
Rule #3 is our random walk, but this time it's different, because if one player gains greater wealth the other will probably end up paying them more money. Neither player starts with any advantage, but sooner or later one player gains a big advantage. This is a big simplification from the original game, but it still captures the essential element of Monopoly: THE RICH GET RICHER.
Rule #4 is identical to our original Monopoly game.

So here are two plots of a game of Monopoly-Walk. These are identical plots, just a different time scales to better show what is going on. This "walk" (red line) looks much smoother than the random walks above, but the scale on the y-axis is much greater and so the difference do not look as jagged. The blue "cone" line represents the total wealth in the game (or maximum difference in wealth) as both positive and negative values. When the red line touches one of the blue, the game is over and one player has won (P1 is the difference is positive, P2 if it is negative).
In this example the players are nearly equal in wealth for the first 60 turns (difference is ~0), but then player 2 gains a small advantage which eventually leads to a win about turn 125.

Here is the spreadsheet I used to create the plots: Monopoly2.xls. You can try adjusting the starting values and see how that changes the game (See my comments for more explanation). If you don't want to try that, here are some more plots you can look at to get a better idea what is going on.


You can see here that the game usually remains somewhat "flat" at first, with no big swings in wealth. Later one, when one player has more than a tiny advantage, that advantage quickly translates into a win. Let's think a bit more about the remaining differences between this simple game and Monopoly. Monopoly has properties which must be purchased, thus reducing a player's wealth. The properties give small rent payments at first, but later on are developed (also reducing wealth) to allow greater rents, earning the owner a greater share of the other player's money on future turns. These things are a delaying effects between first acquiring wealth and turning that wealth into higher rents, and so the game remains essentially random for a longer time before one player gains a decisive advantage. Monopoly also has "taxes" that remove wealth from a player and the total wealth available in the game. This serves as another sort of delay to a player gaining that decisive advantage. These taxes also add additional randomness, making the game even less predictable. Add in three or more players and gentle random walk turns into a wild roller-coaster ride governed by luck and player moxie.

So that's my angle on the game Monopoly. I doubt it will help anyone play better, but it may allow the opportunity to appreciate a different sort of mathematical process, one that also happens to be a lot of fun.

PS: If one reader would try my spreadsheet and report success or failure, that would be appreciated.