De Econometrist

De Econometrist neemt een statistische kijk op de wereld.

Risk
Overig Wiskunde

Who will conquer the world?

 

Risk has been one of the most beloved board games since its release more than sixty years ago. With this classic board game, a fun evening with your friends or family can soon turn into an hours-long war where alliances are forged, troops are lost and battles are won. This family game has brought a lot of joy as well as quarrels and has produced many victors over the years. But what exactly is the best way to conquer the world? Is there a way to ensure your victory? In this article I will analyze the game of Risk from a mathematical point of view focusing on two main game elements: the battles decided by the roll of the dice and the occupation of different continents.

The rules of the game

Risk is a game of chance and strategy. One can win by conquering territories and by doing so, destroying the armies of your opponents. Since its release, there have been many versions and adaptations of the game, but the basic rules have stayed the same. The map is divided into 6 continents and 42 territories as shown below. Players may attack adjacent territories, as well as the territories separated by water but connected by a red line (additionally Alaska and Kamchatka are also connected). At the beginning of the game, the territories are divided among the players and the players decide how to position their armies. Once a player has his or her turn, they can choose to receive new troops to reinforce their army (the number of which is determined by their current armies on the board). Or a player can choose to attack another player by trowing with the dice, after which their opponent has the opportunity to defend themselves. The final stage of a player’s turn is the troop movement stage, where a player is allowed to move some of his armies to different territories.

Source: Garrett Robinson / MIT

Being victorious in Risk is a combination of luck and strategy. The most important task to win the game is of course to conquer territories from other players. This is done using dice, which makes it very accessible for statistical analysis. When a player attacks another player, he can choose to throw with one, two, or three dice depending on the number of troops used for the attack. In his turn, the defender is allowed to use one or two dice, also depending on the number of troops at the current territory. The attacker must throw first, after which the defender can choose how many dice they want to throw. To decide which army loses the battle, the players compare the highest die rolled by each. If the attackers die is higher, the defender loses one army from the territory under attack. If each player rolled more than one die, they also compare the two next-highest dice and repeat the process. In case of an equal throw, the defender is the winner.

Source: UltraBoardGames

Battles between two players

In a paper by professor Jason A. Osborne, he analyzes the stochastic progress of a battle between two players for any of the 42 territories using a Markov Chain. His analysis is as follows. Let us denote the number of attacking armies prior to the battle by A, and the number of defending armies by D. Consequently the state after the n^{th} roll of the dice is denoted by X_n = (a_n, d_n). Since the state at time n+1 is completely determined by its predecessor, we have a Markov Chain:

    \[P(X_{n+1} = (a_{n+1}, d_{n+1}) |x_n,..., x_0) = P(X_{n+1} = (a_{n+1}, d_{n+1}) |x_n).\]

The states of this Markov process can be ordered. All states where both a and d are positive are transient states. Thus the probability that, starting in state i, the process will ever reenter state i is smaller than 1. However, the states where either a=0 or d=0 are absorbing, once these states are entered they are never left again. Naturally, this is the case since in such states the battle is over, and either the defender has lost all its armies in the corresponding territory or the attacker has lost all armies they used to attack the desired territory. The corresponding probability matrix can be given by

    \[P = \begin{bmatrix} Q & R\\ 0 & I \end{bmatrix},\]

where Q is the (A \cdot D) \times (A \cdot D) matrix containing the probabilities of going from one transient state to another, and R is the (A \cdot D) \times (A + D) matrix containing the probabilities of going from a transient state into an absorbing state. Now, let \pi_{ijk} denote the probability that the defender loses k armies when rolling j dice against an attacker rolling i dice, e.g. \pi_{320} is the probability that the defender loses zero armies when trowing with two dice against the attacker who throws with three dice. There are only 14 of such probabilities, which can be seen in the table displaying the probabilities which make up the probability transition matrix. We denote the unordered outcome when rolling three dice by Y_1, Y_2, Y_3, and the unordered outcome when rolling two dice by Z_1, Z_2. In general, Y_1, Y_2, Y_3 denote the outcomes of the rolls of the attacker, while the Z_1 and Z_2 represent the outcomes of the rolls of the defender. For the roll of a dice we have of course a discrete uniform distribution with possible integers values from 1 until 6:

    \[P(Y_j = y) = \left\{ \begin{array}{ll} \frac{1}{6} & \text{ for } y = 1, 2, 3, 4, 5, 6\\ 0 & \text{ else.} \end{array} \right. \]

To calculate the probabilities in the transition matrix P we use the ordered statistics of the outcomes such that Y^{(1)} \geq Y^{(2)} \geq Y^{(3)} and Z^{(1)} \geq Z^{(2)}, e.g. Y^{(1)} represents the highest die of the throw, Y^{(2)} the second to highest throw, and Y^{(3)} to lowest of the three.
When rolling three dice we have,

    \[P(Y^{(1)} = y^{(1)},Y^{(2)} = y^{(2)}) =\left\{ \begin{array}{ll} \frac{3y^{(1)} - 2}{216} & \text{ for } y^{(1)}=y^{(2)}\\ \frac{6y^{(2)} - 3}{216} & \text{ for } y^{(1)} > y^{(2)}\\ 0 & \text{ else.} \end{array} \right.\]

While when rolling two dice, we obtain

    \[P(Z^{(1)} = z^{(1)},Z^{(2)} = z^{(2)}) =\left\{ \begin{array}{ll} \frac{1}{36} & \text{ for } z^{(1)}=z^{(2)}\\ \frac{2}{36} & \text{ for } z^{(1)} > z^{(2)}\\ 0 & \text{ else.} \end{array} \right.\]

We can use these joint distributions to calculate the the transition probabilities. For example, we would calculate \pi_{320}, the probability that the defender loses zero armies when trowing with two dice against the attacker who throws with three dice, by

    \begin{align*} \pi_{320} & = P(Z^{(1)} \geq Y^{(1)}, Z^{(2)} \geq Y^{(2)})\\ & = \sum_{y_1 = 1}^6 \sum_{y_2 = 1}^{y_1} P(Z^{(1)} \geq y_1, Z^{(2)} \geq y_2)\cdot P(Y^{(1)} = y_1, Y^{(2)} = y_2)\\ & = \sum_{y_1 = 1}^6 \sum_{y_2 = 1}^{y_1} \sum_{z_1 = y_1}^6 \sum_{z_2 = y_2}^{z_1} P(Z^{(1)} = y_1, Z^{(2)} = y_2)\\ &  \quad \quad \quad \quad \cdot P(Y^{(1)} = y_1, Y^{(2)} = y_2)\\ & = \frac{2275}{7776}\\ & = 0.293. \end{align*}

Similarly, the other probabilities can be calculated, which are shown in the table below:

However, in most cases, the battle won’t be over after one throw of the dice. A series of throws is performed until either one of the players has lost all their armies, or the attacker decides to cease the attack due to unforeseen losses. Thus, Osborne continues his analysis. Let

    \[f_{ij}^{(n)} = P(X_n = j, X_k \neq j \text{ for } k = 1, ..., n | X_0 = i)\]

denote the probability that the first and thus last visit from a transient state i to an absorbing state j is in n turns. Let F^{(n)} = Q^{n-1}R denote the matrix containing these transition probabilities. The total probability that the system goes from transient state i to absorbing state j is simply the sum of the probabilities for each n, e.g. f_{ij} = \sum_{n=1}^\infty f_{ij}^{(n)}. And similarly we find

    \[F = \sum_{n=1}^\infty F^{(n}) = \sum_{n=1}^\infty Q^{n-1}R = (I-Q)^{-1} R, \]

a matrix of the form (A\cdot D) \times (D+A). If the system ends in one of the last A absorbing states from this matrix then the attacker wins, but if the system ends in one of the first D absorbing states, the defender wins. Then if we let the initial state of the battle i again be defined by the number of attacking armies and the number of defending armies, i.e. i = A \cdot D, we find

    \begin{align*} P(\text{ Attacker wins }|X_0 = (A, D)) = \sum_{j=D+1}^{D+A} f_{AD, j}\\ P(\text{ Defender wins }|X_0 = (A, D)) = \sum_{j=1}^{D} f_{AD, j}\\ \end{align*}

And hence we find the following probabilities:

Source: Jason Osbourne / NCSU

Which continent?

However, one cannot win a game of Risk by only focusing on single battles. To become victorious you also need a strategy with regards to which territories and thus which continents you are going to invade. This is because, at the beginning of each turn, a player receives a bonus for each complete continent they possess. When a player completely occupies one continent, they are rewarded in the form of extra troops, depending on the specific continent. The following figure depicts each continent more clearly, including its vulnerabilities such as the number of entries and the number of territories where a continent can be entered.

Source: Garret Robinson/MIT

An overview of this information is given in the table below:

From the table, one can see that Europe receives by far the highest bonus per territory, namely 0.714 bonus per territory. While Africa, Australia, and South America have the lowest bonus per territory of 0.5. However, the number of territories might not be as important as it may seem. A successful strategy in Risk is not just about ensuring that you get the maximum bonus per territory, it’s also about minimizing the probability that your opponents invade one of your territories. Thus the ratio of armies rewarded per number of entries in a continent, and even more important, the ratio of armies rewarded per number of border territories should be an important determinant of your strategy. And of course, as any experienced Risk player might already expect, we see that Australia has the highest ratios in both categories, with only one entry and one border territory rewarded with a bonus of two troops. It also becomes evident that Europe might not be as strategic as the bonus over the number of territories ratio indicated. It also follows that, in general, North America will be relatively easy to defend, compared to other continents with a high bonus. While the most difficult to defend continents, relative to their bonus, are in fact Africa and South America.

The winning strategy

Of course, there is not one specific strategy to win in a game of Risk. Your chances are highly dependent on the choices and strategies of your opponents, and naturally also your luck when it comes to rolling the dice. There are, however, some strategic moves that will significantly increase your chances of winning the game. In general, when you try to take a continent make sure you have enough troops to hold the continent for another round until it is your turn again and you can reinforce your troops. Otherwise, the chance is high that other players will recognize your weak position and will attack. And also remember that troops that are placed within a continent are useless. Furthermore, your best chances to win a single battle are when you as an attacker have three dice, while your opponent only has one. Thus, at the beginning of the game, establishing your stronghold at territories where your opponents have a weak position will enlarge your chances at gaining the continent while ensuring the fewest casualties. With regards to continents, as expected, try to occupy Australia, since the bonus per border territory ratio is most favorable. On the other hand, Europe gives the highest bonus per territory, but comes at a larger risk, since many of Europe’s territories are border territories. Hence another safe choice, with a relatively high bonus and promising ratios, is North America. From our analysis, it also became visible, that as the number of armies increases, the probability that the attacker wins also increases. Osborne also depicts this in the following figure:

Source: Jason Osborne/NCSU

When you and your opponent both have five armies or higher, the attacker already has a slight advantage. Also, when the difference in armies equals two or more, the chances of winning an attack are significantly large that it is worth a try in most cases. Finally, in a “standard” game, where the attacker has three dice and the defender has two, the attacker also has a slight advantage. Thus, next time when you play a game of Risk with your friends or family, remember these tips, and completely annihilate your opponents.

References

Osborne, J. A. (2003). Markov Chains for the RISK Board Game Revisited. Mathematics Magazine,  76(2), 129.

Robinson, G. (n/a). The Strategy of Risk. MIT, https://web.mit.edu/sp.268/www/risk.pdf


This article is written by Fenna Beentjes

Deel dit artikel:

By Daniele Zedda • 18 February

← PREV POST

By Daniele Zedda • 18 February

NEXT POST → 34
Share on