State-Space Complexity of RISK board game

Question

I want to calculate the (state-space) complexity of the RISK board game. Online I found a thesis that outlines that complexity (page 34). Here is the summary:

Let M denote the maximum number of armies on the gameboard, T the number of territories on the map and P the number of players participating in the game, then:

As an example with M=200, T=42 and P=4:

Unfortunately what I have quoted here from the thesis is basically all the explaination given, there are no more details how the author comes to this formula.

Now I am not a maths expert, so it's a bit hard for me to evaluate this formula. My basic question is: Does this formula make sense, and if so, could you please explain it to me? And if not, if this formula is not correct in the context of RISK: Could you please guide me to the right direction instead?

Answer 1

There is a combinatorial identity used to count the ways $n$ identical objects can be distributed among $k$ distinct boxes.

\begin{equation} \#d = \binom{n+k-1}{k-1} = \binom{n+k-1}{n} \end{equation}

To see this, imagine we line up the $n$ items in a long row. Now, we designate each item to a box in the following way:

1) Place $k-1$ dividers between the items like so:

$----|--|\,|---|-$

2) The items before the first divider are assigned to the first box, the items between the first and second to the second box and so on. In this way, our example assigns the following numbers of items to each box:

$\begin{array} &\text{box}& 1 & 2 & 3 & 4 & 5 \\ \hline \text{items}&4 & 2 & 0 & 3 & 1 \end{array}$

Now, for every distribution of items among boxes, there is a unique way of placing these dividers and vice versa, so we need to count how many ways there are of placing the dividers.

To do this, consider $n+k-1$ slots where either an item or a divider can be placed. Out of these slots, we need to choose exactly $k-1$ to be dividers. Therefore, there are exactly $\binom{n+k-1}{k-1}$ ways to distribute the dividers and so $\binom{n+k-1}{k-1}$ ways to distribute the $n$ identical items among $k$ distinct boxes.

Now, in the Risk example, this identity is used in the army distribution. First, one army must be placed in each territory. Next, we count the ways to distribute the remaining $A-T$ identical armies (items) armies among $T$ distinct territories (boxes). This is where we get

\begin{equation} \binom{T+(A-T)-1}{T-1} = \binom{T+(A-T)-1}{A-T} = \binom{A-1}{A-T} \end{equation}

For the territory distribution, he seems to be similarly distributing $T$ identical territories between $P$ distinct players, which is strange since the territories aren't identical. For example, in a very simple game with two territories and two players, even though in both cases they hold the same number of territories, player 1 holding province 1 and player 2 holding territory 2 is a different game state from player 1 holding territory 2 and player 2 holding territory 1 are different province distributions.

I would calculate the territory distribution in the following way:

1) Since the territories are distinct, order them in some way

2) Taking a territory one by one according to the order, assign one of the $P$ players to it.

Since this is done once for each of the $T$ territories, there are $P^T$ possible choices when distributing the territories between players.

Putting this all together gives the following: There are from $T$ to $M$ possible numbers of armies on the board. For each possible number of armies $A$, there are $\binom{A-1}{A-T}$ ways to distribute these armies over the board. For each of these army distributions, there are $P^T$ distributions of the provinces among players. Summing these quantities gives:

\begin{equation} \sum_{A=T}^M \binom{A-1}{A-T} P^T \end{equation}

I realise that this isn't the quantity in the paper, and I'm ready to be contested on this, but I'm pretty sure that the territory distribution among players is in fact what I have calculated.

Answer 2

This is a classic counting reasoning, although I'm not sure about how the thesis was done.

You want to compute the number of different states of the game. The way I see it:

• you sum on the total number of armies, because you need to have at least one army on each territory.
• you cannot have less armies than the number of territories, which is why you start the sum at T

• for a given number A of army, which lies between T and M the maximum number of army (not sure what that number is, maybe the number of pieces in the box or in the rules ?), you need to:

  • first arrange those armies on the territories (you leave out T of them which are the ones needed to have at least one soldier on each territory
  • you're left with (A-T) armies that you have to split any way you want between T territories; I think you have $T^{A-T}$ possibilities (imagine this as picking up the name of a territory and putting the name back in the urn, doing this for each army left)

• now you need to "color" your armies between the different players. If you have $p\leq P$ players, $P^T$. That includes having $p-1$ players on the board etc. If you want exactly $P$ players, you need to put P choose $T$ army first, then you can affect the remaining armies to whoever you want $P^{(T-P)}$.

so my formula would be:

$\sum_{A=T}^M T^{A-T} \times P ^T$. I see the game as a $T$-tuple of 2-tuples (player,number of armies), with the conditions above.

I hope this helps and that someone else can check the maths.