In my last blog posting, I talked about two techniques (Monte-Carlo simulation, Markov-Chain analysis) for calculating probabilities in the game of Chutes and Ladders.
Today, I want to take a look at the popular game of RISK®.
If you’ve not played the game, the core mechanic is based on the rolling of dice to determine wins/losses for armies attacking between territories. Battles occur in rounds, with an attacking player typically rolling (up to) 3 dice, and a defending player (up to) 2 dice. After rolling, dice are paired up (Highest rolled attacker die against highest rolled defender die, then next highest rolled pair if required). The highest rolled number wins (eliminating one opponent army), with ties resulting in a win by the defender.
Attacks by more than three armies are played in a series of rounds. After each round, armies from the losing team are removed from the board and the remaining pieces continue to duel.
The fact that it is the highest then the next highest die used for the two attacks makes a subtle twist in the probabilities. In more than a couple of internet searches I’ve found people have made mistakes in calculating the probabilities. So, how should we go about calculating the true probabilities?
Following on from the last blog posting, we could do a Monte-Carlo simulation, and roll millions of sets of dice. The problem with this approach, however, is that we’d only get an approximate answer, and we’d also be at the mercy of our random number generator.
First, we’ll look at the probabilities of a single round (with all permutations of possible attack and defence rolls). Later, we’ll apply this learning to multiple round battles.
Since there are a small (fixed) number of dice with a finite set out outcomes, we could create a probability tree and work out the probabilities by hand, but being honest, this is a lot of work, with multiple chances of making a mistake, and incredibly tedious.
When an attacker has three or more armies, he can roll up to three dice. (It’s pretty trivial to calculate that it’s always in the best interest of the attacker to roll as many dice as possible on each round, so this will be built in the calculations later). Similarly, it’s in the defenders interest to roll two dice where possible, and only rolling a single defence die when there is no option.
We still, however, need to calculate the probabilities for all five possible combinations of attack/defence combinations that could occur in a basic round: 3v2, 3v1, 2v2, 2v1, 1v2, 1v1.
Brute Force.The simple fact is that there aren’t that many combinations to examine. At worst case, there are only five dice rolled with a total of 7,776 combinations (6 x 6 x 6 x 6 x 6). We can simply loop through each possible combination of dice rolls and calculate the exact results.
There’s no reason to be a prima donna and say that brute force is cheesy programming. Many times, the simplest algorithm is the best.
Code for enumerating all combinations of dice is incredibly easy to write, easy to read, and very unlikely to contain logic errors (It honestly took me about two minutes to write code to generate the results). If I’d tried to do the calculation in a more "elegant" mathematical way (or even by hand) it would have probably taken two orders of magnitude longer to write and debug, and might still have had a logic or calculation error left in!
It’s also not as if this piece of code is going to be executed millions of times. It’s going to be run just once. As a good friend of mine pointed out, there are entire sites on the internet where people argue about the most efficient and elegant algorithms to solve certain problems, but practically, is the difference between a great solution and a perfect solution worth the extra week it takes to develop?
Academically these algorithm discussions are noble (and don’t get me wrong, very, very interesting); in some core cases, where performance or memory usage is paramount, the value of an efficient and elegant algorithm more than justifies the indulgence. But often, it is easy to forget that all you need is the answer in the effort to engineer a graceful solution.
It's all about Horses for Courses
There is no shame in the appropriate use of a brute-force algorithm.
Here's the pseudo code for the case of three attackers vs. two defenders:
For Attack1 = 1 to 6
For Attack2 = 1 to 6
For Attack3 = 1 to 6
AttackHigh = Highest (Attack1, Attack2, Attack3)
AttackMedium = Medium (Attack1, Attack2, Attack3)
For Defence1 = 1 to 6
For Defence2 = 1 to 6
DefenceHigh = Highest (Defence1, Defence2)
DefenceLow = Lowest (Defence1, Defence2)
Calculate_Win_Loss_Tie (AttackHigh, AttackMedium, DefenceHigh, DefenceLow)
That's pretty much all there is to it.
Here are the results of the brute force calculations for the various combinations of dice.
|Defender Rolls 2 Dice||Defender Rolls 1 Die|
Battles that occur when there are more than three attackers (or more than two defenders) are more complex to calculate e.g. A battle between seven attacking pieces and five defending pieces.
NOTE: When a player attacks, he must leave (at least) one army behind on the territory he is striking from. All my calculations are based on the number of characters doing the actual attacking, not the number of armies on the starting square.
The tree diagram below shows the various possible outcomes for the above example:
After the first round, the attacker could win both dice, reducing defending dice to three. or, both the attacker and defender could each lose an army, or the attacker could lose two armies. From the matrices above, the probabilities of these events happening are (respectively) 2890 / 7776, 2611 / 7776, 2275 / 7776. And, the probabilities of these events happening are based on probabilities of other events, and so on …
To calculate the actual probability of the attacker being totally successful, we have to work our way through the tree, calculating the probability of each event happening all the way until we reach the leaf nodes on the end, which will be one of the five basic cases we calculated with brute force.
There are many ways to calculate the sum of the tree probabilities, but one method that is easy to code, and easy to read is recursion. (See an earlier post of mine about creating spark effects using recusion.
We can create a function that returns the probability of an attacker winning the entire battle based on the number of attacker and number of defenders specified. This function will add up the three probabilities: attacker wins, tie, and defender wins, calling itself recursively with the adjusted parameters for each of these cases. This function will call itself again until one of the known five basic cases is encountered. This condition is the end-case for our recursion, and the actual probability for this event will be returned by the function which will then ripple all the way back to the inital calling values.
(Yes, yes, I know that recursion is far-and-away from being an optimal way of solving this problem. Infact it's harder to think of a less efficient algorithm for solving the problem! But, as above, if you only need to run it once, and get accurate results the first time, it's pretty hard to screw up the logic by writing the code in a recursive way. The entire function is just a few lines of code.)
Here are the results in tabular format for all combinations of attackers and defenders up to 20. The percentages show the probability that the attacker will win the territory.
The above numbers are hard to read (and interpret), so here they are presented in a more digestable way. The picture to the left shows the same data, but this time I've shaded the matrix with colour representing the probability of the attacker winning.
Where the percentage is >50% (advantage to the attacker), the square is shaded red. Where probability is to the advantage of the defender, the square is shaded blue.
The darker the shade of colour, the higher the percentage advantage to that player. Squares on the leading diagonal (where the number of attackers and defenders is the same, are boxed in yellow.
With just a quick glance at the graph, we can notice some very interesting results, which should help generate some tactics.
With just a small number armies on both sides, the defender has the advantage. This is because, in the result of a tie on the dice, the defender wins.
For battles where the number of attackers and defenders is the same 1v1, 2v2, 3v3, 4v4, then the defender has the mathematical advantage. However, once 5v5 has been reached, advantage swings to the attacker (because the benefit or being able to roll one extra die each round becomes more significant than losing on a tie.
This attacker advantage widdens the larger the attacking army (you can see on the graph above that the further to the right you go, the more the red colour seeps below the yellow leading diaganol).
STRATEGY TIP – It's better to attack then defend. Be aggressive.
STRATEGY TIP – Always attack with superior numbers to maximize the chances of your attack being successeful.
STRATEGY TIP – If attacking a region with the same number of armies as the defender, make sure that you have at least five armies if you want the odds in your favour (the more the better).
The image on the right shows the 95% confidence limits. All attacks in the top right gray area of the chart represent a victory for the attacker in at least 19/20 times.
Here's another way to look at the data. The chart below shows the curves for the percentage chance of the attacker being successful. There are five different curves corresponding to 5, 10, 15, 20, 25 defenders
At the start of each round of the game, players are given additional armies that they can use to reinforce territories that are already owned. What is the optimal strategy for placing these new armies?
If the aim is to defend one particular territory then, as we've already learned, safety is in numbers. The stronger your defending force, the better your chance of defending. But, once you've reached five armies or more on a region, an identically sized attacking army has the advantage.
The graph on the left shows the change (delta) in the percentage chance of the defender holding onto a territory if being attacked by 1 attacker.
The x-axis shows the new number of defenders, and the y-axis shows the change in percentage.
As you can see, moving from 1 defender to 2 defenders, results in an increase in percentage chance of survival of 31%. Increasing this to 3 defenders adds only another 8% survival chance, and increasing this to 4 defenders another 4%.
If you're only likely to be attacked by singletons, it's better to just double-up and use your extra armies elsewhere.
When defending against a potential attacking force of 5 attackers, the curve changes. The most "Bang for the Buck" is obtained by increasing the defence force to 5 (matching the attackers strength).
The smarter readers will realise that these efficiency curves represent the gradient of the sensitivity curves. The most efficient placement of defences is where the gradient of this curve is the steepest.
Similarly, when defending against a force of 10 attackers, the most efficient use of reinforcement is to get the number of defenders to the same level as the number of attackers.
(The graphs start to become more noticeably 'spikey' because of an odd/even parity effect caused by the difference to the attacker of having either two or three dice left towards the end of the battle).
Finally, an example of the changes in efficiency per defender based on being confronted by 15 attackers. Again, the biggest increase from adding a single defender is moving from 14 to 15 defenders.
STRATEGY TIP – It's better to double up defence on single territories than increase defences on large ones.
STRATEGY TIP – The most efficient reinforcement strategy is to try and get your regions up to the number of armies that you think your attacker will use against you.
RISK® is a product owned by Hasbro. You can find out more details about the product range, and buy products from their website
Check out other interesting blogarticles.