# Who has the upper hand in a generalized game of Risk?

So, I played a game of Risk the other day for the first time since I was very little. I was frustrated to discover that I couldn't compute (at least not in my head) whether the attacker or the defender has the upper-hand in large battles. Based on how the game unfolded, I guessed that the attacker has the advantage, and later I verified this by calculating the expected number of casualties in a round of "combat". But, my approach was just to brute-force the computation in a spreadsheet. I'm curious whether there is a more elegant approach and also I thought it might be nice to ask a more general question.

Let $A$ and $B$ be two players. Let $a,b,n,k$ be positive integers with $k \leq a,b$. The game is as follows. Person $A$ has $a$ dice. Person $B$ has $b$ dice. All dice have $n$ sides labelled $1,2,\ldots,n$. Both players roll all of their dice, extract their $k$ highest rolls (with repetition) and sort them in (weakly) decreasing order. Say $a_1,\ldots,a_k$ are $A$'s $k$ best rolls and $b_1,\ldots,b_k$ are $B$'s $k$ best rolls. $A$ suffers one "casualty" for each index $i \in \{1,2,\ldots,k\}$ with $a_i \leq b_i$. $B$ suffers one "casualty" for each index $i \in \{1,2,\ldots,k\}$ with $a_i > b_i$. Note that player $B$ wins when the rolls are tied.

What are the expected number casulties that $A$ suffers in terms of $a,b,n,k$? Note by linearity of expectation, the expected number of casualties that $A$ suffers plus the expected number of casualties that $B$ suffers sum to $k$.

-
By the way, in a large battle in a game of actual Risk the parameters are $a=3,b=2,n=6,k=2$. – Mike F Nov 26 '11 at 1:16
I did this calculation once (for actual Risk), and I think the rule-of-thumb answer was that the attacking army will lose about 3/4 of the number of defenders. – Greg Martin Nov 26 '11 at 23:39
@Greg: Something like that. By Alex's computation, the defenders should lose $2-7161/6^5 \approx 1.08$ troops per roll. So it would take about $N/1.08$ rolls for an attacker to wipe out $N$ defending armies. During this time, the attacker loses about $(N/1.08) \times (7161/6^5) \approx 0.85 N$ troops. – Mike F Nov 27 '11 at 6:44
It's generally a better idea to consider the entire distribution of $Y$ (the number of armies the defender loses in a battle) rather than $E(Y)$ (the expected value of $Y$). That will lead to more detailed information about what might happen after $N$ rolls using a trinomial distribution. – alex.jordan Nov 29 '11 at 18:58
This was my final project in a calculus class! We calculated the probabilities using Markov chains. – smackcrane Nov 29 '11 at 22:29

For an actual game of Risk, where the attacker has 3 armies and the defender has 2, I worked it out this way. I think you can generalize easily for other values of $a$ and $n$. Other values of $b$ will make the counting slightly more difficult, but still within reach (I think). Other values of $k$ however will make my counting method a lot more difficult (I think).

If we view the three attacker's dice as distinguished, then the space of possible rolls for the attacker has size $6^3$. It's like a giant $6\times6\times6$ cube itself - one dimension for each die. For example, the attacker's roll might be a $(2,5,4)$ or a $(4,6,6)$. Each such roll has the same probability: $\frac{1}{6^3}$.

We can break this cube into shells that I will try to define. The smallest shell contains the singleton $(1,1,1)$. The next shell contains all possible rolls where the high die is a 2. (This shell therefore has $7$ elements - surrounding $(1,1,1)$.) Continue in this way up to the outermost shell, which will contain all possible rolls where the highest die is a 6. Geometrically, this last shell is three faces of the cube. Each previous shell can also be viewed as having three faces (with the possible exception of $S_1$.) To be more precise, $$S_i = \{(a,b,c)|\max\{a,b,c\}=i\}$$ for $i =1\ldots6$. The probability of tossing into shell $i$ is $$P(S_i)=\frac{i^3-(i-1)^3}{6^3}$$ Each shell $S_i$ has subsets $S_{i,j}$ where $j$ is the second highest roll (possibly equal to $i$). Geometrically, $S_{i,j}$ is composed of line segments running along the three faces of $S_i$. $S_{i,i}$ is composed of the three edges converging to the main corner in $S_i$. For $j$ less than $i$, $S_{i,j}$ is composed of three "arrows", one along each face of $S_i$, each pointing to the main corner of $S_i$. The image below illustrates the cube of possilbe attacker rolls, $S_6$, $S_{6,6}$, and $S_{6,3}$.

We find that for the attacker's roll, with $j$ less than $i$, \begin{align*} P(S_{i,i}) & = \frac{3i-2}{i^3-(i-1)^3}\frac{i^3-(i-1)^3}{6^3}=\frac{3i-2}{6^3}\\ P(S_{i,j}) & = \frac{6j-3}{i^3-(i-1)^3}\frac{i^3-(i-1)^3}{6^3}=\frac{6j-3}{6^3}\ \end{align*}

Now we begin to consider the defender's tosses, conditional upon what $S_{i,j}$ the attacker has rolled into. Similar to the cube that we envisioned for the attacker, the defender has a $6\times 6$ square of possible rolls.

Let's start counting the number of armies that the attacker loses. Let $X$ be this random variable, which can take values $0$, $1$, or $2$.

Suppose the attacker has rolled into $S_{i,i}$. If both the defender's dice are less than $i$ (which will happen with $P=\frac{(i-1)^2}{6^2}$), the attacker will lose zero armies. If both of the defender's dice are $\geq i$ (which will happen with $P=\frac{(7-i)^2}{6^2}$) the attacker will lose two armies. In all other situations ($P=\frac{2(i-1)(7-i)}{6^2}$), each player loses one army.

Now suppose that the attacker has rolled into $S_{i,j}$ with $j<i$. The attacker loses no armies if the defender's highest die is less than $i$ and the other die is less than $j$. This defines an "L" shaped region of the defender's square of possibilities. This region has $P=\frac{(i-1)^2-(i-j)^2}{6^2}$. Similarly, the attacker will lose two armies exactly when the defender has his high die at least $i$ and other die at least $j$. This defines an "L" shaped region on the other side of the square. ($P=\frac{(7-j)^2-(i-j)^2}{6^2}$). This leaves three rectangular regions on the square where each player loses one army ($P=\frac{2(j-1)(7-i)+(i-j)^2}{6^2}$).

Altogether now, the probabilities for each value of $X$ can be compute via summation: \begin{align*} P(X=0)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{(i-1)^2}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{(i-1)^2-(i-j)^2}{6^2}\right)\\ &=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{(i-1)^2}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{(i-1)^2-(i-j)^2}{6^2}\right)\\ P(X=1)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{2(i-1)(7-i)}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{2(j-1)(7-i)+(i-j)^2}{6^2}\right)\\ &=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{2(i-1)(7-i)}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{2(j-1)(7-i)+(i-j)^2}{6^2}\right)\\ P(X=2)&=\sum_{i=1}^6\left(P(S_{i,i})\frac{(7-i)^2}{6^2}+\sum_{j=1}^{i-1}P(S_{i,j})\frac{(7-j)^2-(i-j)^2}{6^2}\right)\\ &=\sum_{i=1}^6\left(\frac{3i-2}{6^3}\frac{(7-i)^2}{6^2}+\sum_{j=1}^{i-1}\frac{6j-3}{6^3}\frac{(7-j)^2-(i-j)^2}{6^2}\right)\\ \end{align*}

Each of these can be reduced using the sum formulas \begin{align*} \sum_{n=1}^m\ 1& =m\\ \sum_{n=1}^m\ n&=\frac{1}{2}m(m+1)\\ \sum_{n=1}^m\ n^2&=\frac{1}{6}m(m+1)(2m+1)\\ \sum_{n=1}^m\ n^3&=\frac{1}{4}m^2(m+1)^2\\ \sum_{n=1}^m\ n^4&=\frac{1}{30}m(m+1)(2m+1)(3m^2+3m-1) \end{align*}

After applying these, we find: \begin{align*} P(X=0)&=\frac{2890}{6^5}\\ P(X=1)&=\frac{2611}{6^5}\\ P(X=2)&=\frac{2275}{6^5} \end{align*}

These agree with the decimal probabilities reported here. Thus the expected number of casualties is $$0\frac{2890}{6^5}+1\frac{2611}{6^5}+2\frac{2275}{6^5}=\frac{7161}{6^5}$$

-
Wow! Thank you for going to all of that effort, +1. – Mike F Nov 27 '11 at 6:31
@Mike Several years ago some friends and I started playing Risk again and I had fun working this all out. I'd love to know if you have success generalizing to other $a$, $b$, $n$, and $k$. – alex.jordan Nov 27 '11 at 18:10

Here's an answer. It's not very pretty, but it is exact. Let the random variable $C_A$ denote the number of Player $A$ (the attacker)'s casualties. Then

\begin{align} E[C_A] = &\sum_{j=0}^{k-1} \sum_{i=1}^n \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 - \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} - \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\ & \times \left(1 - \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}. \end{align}

Derivation:

In a particular random roll of the dice, we order $A$'s dice from largest to smallest and $B$'s dice from largest to smallest. This is equivalent to taking two random samples - of size $a$ in $A$'s case and size $b$ in $B$'s case - from the discrete uniform distribution on $\{1, 2, \ldots, n\}$ and computing their order statistics.

If $X_{(j)}$ and $Y_{(j)}$ denote the order statistics from $A$'s dice rolls and from $B$'s dice rolls, respectively, then $A$ suffers a casualty each time $X_{(a-j)} \leq Y_{(b-j)}$, for $0 \leq j \leq k-1$. Let $I_j$ be $1$ if $X_{(a-j)} \leq Y_{(b-j)}$, and $0$ otherwise. Then $C_A = \sum_{j=0}^{k-1} I_j$, and so $$E[C_A] = \sum_{j=0}^{k-1} E[I_j] = \sum_{j=0}^{k-1} P(X_{(a-j)} \leq Y_{(b-j)}).$$

Since $A$'s rolls and $B$'s rolls are independent, so are their order statistics. Conditioning on the value of $Y_{(b-j)}$, then, we have $P(X_{(a-j)} \leq Y_{(b-j)}) = \sum_{i=1}^n P(Y_{(b-j)} = i) P(X_{(a-j)} \leq i).$ There are known formulas for $P(Y_{(b-j)} = i)$ and $P(X_{(a-j)} \leq i)$: $$P(Y_{(b-j)} = i) = \sum_{l=0}^j \binom{b}{l} \left( \left(1 - \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} - \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right),$$ $$P(X_{(a-j)} \leq i) = \sum_{m=0}^j \binom{a}{m} \left(1 - \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}.$$

Putting this all together, we obtain

\begin{align} E[C_A] = &\sum_{j=0}^{k-1} \sum_{i=1}^n \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 - \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} - \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\ & \times \left(1 - \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m}. \end{align}

A comment on implementation:

For simplicity, the formula uses the convention that $0^0 = 1$, which occurs when $i = n$. If you try to use the formula in some computer algebra system that doesn't have that convention, like Mathematica, you will need to consider the case $i = n$ separately from the rest of the sum on $i$. This would be

\begin{align} E[C_A] = &\sum_{j=0}^{k-1} \Bigg(\sum_{i=1}^{n-1} \sum_{l=0}^j \sum_{m=0}^j \binom{b}{l} \binom{a}{m} \left( \left(1 - \frac{i}{n}\right)^l \left( \frac{i}{n}\right)^{b-l} - \left(1- \frac{i-1}{n}\right)^l \left(\frac{i-1}{n}\right)^{b-l} \right) \\ & \times \left(1 - \frac{i}{n}\right)^m \left(\frac{i}{n}\right)^{a-m} + \left(1-\sum_{l=0}^j \binom{b}{l}\left(1-\frac{n-1}{n}\right)^l \left(\frac{n-1}{n}\right)^{b-l}\right) \Bigg). \end{align}

Example:

In the case of standard Risk, with $n = 6, a = 3, b = 2, k = 2$ case, the formula yields $\frac{2387}{2592} = \frac{7161}{6^5}$, in agreement with alex.jordan's answer.

In[1]:= f[n_, a_, b_, k_] :=
Sum[Sum[Binomial[b, l]*((1 - i/n)^l*(i/n)^(b - l) - (1 - (i - 1)/n)^l*
((i - 1)/n)^(b - l))*Binomial[a, m]*(1 - i/n)^m*(i/n)^(a - m),
{i, 1, n - 1}, {l, 0, j}, {m, 0, j}] +
(1 - Sum[Binomial[b, l]*(1 - (n - 1)/n)^l*((n - 1)/n)^(b - l), {l, 0, j}]),
{j, 0, k - 1}]

In[2]:= f[6, 3, 2, 2]
Out[2]= 2387/2592

In[3]:= N[%]
Out[3]= 0.9209104938271605

In[4]:= N[7161/6^5]
Out[4]= 0.9209104938271605

-