Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
1  
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
1  
This was my final project in a calculus class! We calculated the probabilities using Markov chains. –  smackcrane Nov 29 '11 at 22:29

2 Answers 2

up vote 12 down vote accepted

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}$.

Cube representing possible attacker rolls

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}$$

share|improve this answer
    
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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.