- Get link
- Other Apps
 |
| Credit: Colony of Gamers/Flickr |
My family settled down to a perfectly civil game of Risk this Christmas. At one stage my wife, who controlled most of Asia, challenged my total control of Australia by attacking my territory of Indonesia from her territory of South East Asia, with about 100 armies.
Attacks in Risk consist of a series of "battles". In the initial battles two armies are always lost: either two attackers, two defenders, or one of each. After enough battles either one defending army remains or two attackers. From this point on only one army is lost per battle. Eventually either the defender is completely obliterated or the attacker reduced to one army (which is needed to defend the originating territory) and the attack is over.
In the initial battles (when the attacker has at least 3 armies remaining - not including one set aside to defend the originating territory - and the defender at least 2) the attacker rolls 3 red dice and the defender 2 blue dice. Then the highest red die is paired up with the highest blue one and the next highest red with the next highest blue. For each pair, if the red die is higher a defender army is lost, otherwise an attacker army is lost.
After about 5 battles of my wife's unprovoked attack on the peace loving Australasians, my son got bored and suggested you could speed up this process by writing a program that did all the dice rolling for you. And in a short break from the game this is what he did! I am so proud. But it got me thinking, is there an analytic way to predict the outcome before commencing an attack?
Lanchester's equations are intended to describe the outcome of a battle between two armies. There are two laws, namely the "linear" law, and the more famous "square" law. Let's look at the square law first. Imagine armies of size $A$ and $B$ with "firepower" $\alpha$ and $\beta$, respectively. The definition of firepower in this context is the number of enemy each soldier can kill per unit time, and this reflects the types of weaponry available to each. In this idealized situation the following simultaneous differential equations hold:
$$
\begin{align}
\frac{dA}{dt} &= -\beta B\\
\frac{dB}{dt} &= -\alpha A\\
\end{align}
$$
The attack will result in a draw if the normalized losses are equal, as this will mean that the ratio $A/B$ does not change. Setting
$$
\frac{dA}{dt}/A = \frac{dB}{dt}/B
$$
leads to the "square" law:
$$
\left(\frac{A}{B}\right)^2 = \frac{\beta}{\alpha}
$$
Essentially, if army A has twice as many soldiers then each soldier of army B needs four times as much firepower to retain parity. Obviously, Lanchester's square law represents an idealized model of battlefield slaughter and does not always apply. (Perhaps it never applies!) For a start, it assumes that each soldier in A has a weapon that can be aimed at any soldier in B, and the only factors limiting their ability to kill are the accuracy and reload rate of their weapon. In real life there is likely to some limit on how many enemy soldiers are within range. For example, there may be a front line and the weapons may only be able to project a few km beyond it. In this case the range of the artillery and and the length of the front line defines the numbers actively involved at any one time. This is exactly the case during an attack in Risk (treating Risk's "armies" as Lanchester's "soldiers" and Risk's "battles" as Lanchester's unit time intervals). As described earlier, attacks are broken down into battles and in most of these exactly two armies are lost irrespective of how many armies are deployed in the two territories at war. In this case the equations become
Attacks in Risk consist of a series of "battles". In the initial battles two armies are always lost: either two attackers, two defenders, or one of each. After enough battles either one defending army remains or two attackers. From this point on only one army is lost per battle. Eventually either the defender is completely obliterated or the attacker reduced to one army (which is needed to defend the originating territory) and the attack is over.
In the initial battles (when the attacker has at least 3 armies remaining - not including one set aside to defend the originating territory - and the defender at least 2) the attacker rolls 3 red dice and the defender 2 blue dice. Then the highest red die is paired up with the highest blue one and the next highest red with the next highest blue. For each pair, if the red die is higher a defender army is lost, otherwise an attacker army is lost.
After about 5 battles of my wife's unprovoked attack on the peace loving Australasians, my son got bored and suggested you could speed up this process by writing a program that did all the dice rolling for you. And in a short break from the game this is what he did! I am so proud. But it got me thinking, is there an analytic way to predict the outcome before commencing an attack?
Lanchester's equations are intended to describe the outcome of a battle between two armies. There are two laws, namely the "linear" law, and the more famous "square" law. Let's look at the square law first. Imagine armies of size $A$ and $B$ with "firepower" $\alpha$ and $\beta$, respectively. The definition of firepower in this context is the number of enemy each soldier can kill per unit time, and this reflects the types of weaponry available to each. In this idealized situation the following simultaneous differential equations hold:
$$
\begin{align}
\frac{dA}{dt} &= -\beta B\\
\frac{dB}{dt} &= -\alpha A\\
\end{align}
$$
The attack will result in a draw if the normalized losses are equal, as this will mean that the ratio $A/B$ does not change. Setting
$$
\frac{dA}{dt}/A = \frac{dB}{dt}/B
$$
leads to the "square" law:
$$
\left(\frac{A}{B}\right)^2 = \frac{\beta}{\alpha}
$$
Essentially, if army A has twice as many soldiers then each soldier of army B needs four times as much firepower to retain parity. Obviously, Lanchester's square law represents an idealized model of battlefield slaughter and does not always apply. (Perhaps it never applies!) For a start, it assumes that each soldier in A has a weapon that can be aimed at any soldier in B, and the only factors limiting their ability to kill are the accuracy and reload rate of their weapon. In real life there is likely to some limit on how many enemy soldiers are within range. For example, there may be a front line and the weapons may only be able to project a few km beyond it. In this case the range of the artillery and and the length of the front line defines the numbers actively involved at any one time. This is exactly the case during an attack in Risk (treating Risk's "armies" as Lanchester's "soldiers" and Risk's "battles" as Lanchester's unit time intervals). As described earlier, attacks are broken down into battles and in most of these exactly two armies are lost irrespective of how many armies are deployed in the two territories at war. In this case the equations become
$$
\begin{align}
\frac{dA}{dt} &= -\beta\\
\frac{dB}{dt} &= -\alpha\\
\alpha + \beta &= 2\\
\end{align}
$$
Taking the first two of those and, as before, solving $\frac{dA}{dt}/A = \frac{dB}{dt}/B$ we get Lanchester's "linear" law:
$$
\left(\frac{A}{B}\right)^1 = \frac{\beta}{\alpha}
$$
which says that if player $A$ has twice as many armies then each army of player $B$ needs twice the firepower for parity. Finding $\alpha$ and $\beta$ should be easy as there are only $6^5=7776$ ways of rolling 5 dice. $\beta$ is simply the expected losses for $A$ per battle and $\alpha$ the expected losses for $B$. Let's define $A$ to be the attacker and $B$ the defender, and calculate $\alpha$ and $\beta$ using an exhaustive method
A_loss = 0 B_loss = 0 for red1 in range(1,7): for red2 in range(1,7): for red3 in range(1,7): for blue1 in range(1,7): for blue2 in range(1,7): reds=[red1,red2,red3] blues=[blue1,blue2] reds.sort() blues.sort() for i in range(2): max_red = reds.pop(-1) max_blue = blues.pop(-1) A_loss += int(max_red <= max_blue) B_loss += int(max_red > max_blue) print(f"alpha={B_loss/(6**5)}") print(f"beta={A_loss/(6**5)}")
The outcome is $\alpha=1.08$ and $\beta=0.92$ which means that the attacker has a slight advantage. For parity the defender needs $\alpha/\beta = 1.17$ times as many armies as the attacker. Or, equivalently, the attacker needs $0.85$ times as many armies as the defender.
It's all well and good to know that "on average" you have the winning hand, but you may want to know before you start a fight what the probability of winning or losing actually is. Well, we know that in a single battle (in which two armies are lost in total) the expected outcome is
$$
\begin{align}
E(B_{losses} - A_{losses}) &= \alpha - \beta \\
&= 0.16
\end{align}
$$
We can also find out (with a trivial mod to the above script) that
$$
\begin{align}
P(B_{losses} - A_{losses} = 2) &= 0.372 \\
P(B_{losses} - A_{losses} = 0) &= 0.336 \\
P(B_{losses} - A_{losses} = -2) &= 0.293 \\
\end{align}
$$
This gives a variance for $B_{losses} -A_{losses}$ of $2.63$. Now the variance over $N$ battles is $N$ times the variance over one battle, so for ten battles (in which 20 armies are lost) you'd have a variance of $26.3$, or a standard deviation of $5.1$ armies. We can also appeal to the Central Limit Theorem to claim that the distribution of $B_{losses} -A_{losses}$ over enough battles is approximately normal. For normal distributions 68% of the samples are within 1 s.d. of the mean, 95% within 2, and 99.7% within 3. So over ten battles we can provide 68% confidence intervals: the defender loses $10.8 \pm 5.1$ armies, and the attacker loses $9.2 \pm 5.1$ armies.
To create a memorable rule of thumb it is easier to think in terms of numbers of armies rather than numbers of battles. In this case we can divide the variance for one battle by two to get a standard deviation of $1.15$. This is the standard deviation in $B_{losses} - A_{losses}$ for an imaginary "half battle" between one attacker army and one defender army. If there are 100 armies facing each other you multiply this figure by 10 (the square root of 100) to get a standard deviation of $11.5$.
So the rule of thumb is
- For a 50% chance of winning you need 85% as many armies as the defender. Call this figure $N$
- For an 84% chance of winning you need 1 s.d. more than this, i.e. $1.15 \sqrt{N}$ more armies
- For a 97.5% chance of winning you need 2 s.d. more, i.e. $2.3 \sqrt{N}$ more armies
Comments
Post a Comment