Winning Games with Python
Using Recursion to analyze games
(Find the previous related article here)
Last we left of, we had derived the probabilities of any given Risk battle scenario:
We found that the best odds for the attacker are when there are 3 active attackers.
However, this only describes the probabilities of 1 battle — 1 round of dice rolls.
Imagine that the attacker has 4 attacking units and the defender has 2, and the attacker seeks to keep attacking until all the defending units are defeated or he is no longer able to attack (for simplicity, we shall call this a death match), we can map out all the possible scenarios as such:
It would intuitively seem that there are more scenarios in which the attacker would win — but by how much? To calculate this, we would have to calculate the probability of each end-state occurring, which we can do by multiplying the probabilities that we have obtained in the previous article!
We can find the probability of each end-node by multiplying the probabilities of the branches leading down to it — for example, to calculate the “3v0” end node, you can multiply 0.336 (at the first level) by 0.660 (at the 2nd level), giving us 0.336 * 0.660 = 0.2218.
To figure out the total probability of winning, we would have to sum the probabilities of all the winning end nodes — 0.372 + 0.2218 + 0.07205 + 0.02185 + 0.06680 + 0.03959 = 0.794.
Almost a 4 in 5 chance of winning!
Calculating the probabilities of winning — programmatically
When we calculated the probabilities of winning manually, we had to calculate the probabilities of each of the end states, and subsequently sum them all up.
What we could do programmatically is to figure out for the top node state, what the probabilities of each of the subsequent states are. If the subsequent state is an end state, our job is done and we can add that to our final sum; but if it isn’t, we will have to check what the probabilities of each of the subsequent states are. In pseudocode, this would look like:
Notice that we are calling the function itself again — we are calling find_end_state_prob within itself to solve the same problem for a sub-node. This is an idea in computer science known as recursion.
Recursion
The idea of a function calling itself is something that can be pretty confusing for someone not familiar with programming/computer science. In this context, I feel that it is helpful to think about manually solving this problem -
If we were seeking to calculate manually the possible outcomes of this 4v2 battle, we will start by constructing the tree, and realizing that we have the same subproblem, only for a smaller case this time.
We could then perhaps call a friend (say Alice) and say “Hey, can you help me calculate the probability of winning a 3v1 deathmatch?”
Alice would then construct the tree and then ask her friend (say Bob) if he could help her calculate the probability of winning a 2v1 deathmatch. When Bob returns Alice the probabilities for 2v1, she can then compute the probability of the 3v1 deathmatch problem.
The key idea is to solve the big problem by breaking it down into smaller subproblems!
Recursion in Risk…
Properly implementing the pseudocode presented earlier — we have:
A lot of comments have been added to this function for easy following.
This function, in addition to being recursive (calling itself), also uses a helper function:
There’s quite a lot to take in for this recursive function — I would highly recommend you to try writing your own version of this recursive function as practice!
Some Results
Let’s find out and visualize the probabilities associated with a 10v10 deathmatch:
The x-axis of the distribution represents the various possible end-states, with negative numbers indicating that the defender wins (-10 refers to when a defender wins with 10 defenders remaining).
An interesting observation to note — the probability distribution is actually bimodal. We can also obtain some basic statistics from formatted_results as such:
The first is the expected value — that is, the expected amount of units we will have left (in this case just about 1). The probability of winning is also significantly above 50% (at 56.8%) for a 10v10 battle.
How much different would it be if it was 10v9 instead?
We have a significantly higher probability of winning (65%) and an expected value of almost 2 (1.96).
Let’s do a sensitivity analysis around the 10v10 death match
So it seems that even the slightest change in numbers one way or the other can have a drastic effect on the probability of winning a deathmatch!
Conclusion
The moral of the story still seems to be — Attack whenever you have numerical superiority! Just a small edge changes the probabilities by a significant extent!
In this article, we’ve explored probabilities trees (mathematics/probability concept) as well as tried our hand at implementing them in Python using recursion!
Some of you may recognize probability trees in a different context (binomial/trinomial models in mathematical finance) and if so, you may be interested in seeing a more formal mathematical treatise of the problem here!
Till next time!
