Yesterday I enjoyed some rounds of RISK: Global Domination with a friend from university. It is a long-running in-joke that “True Random” is the cause of winning and losing certain battles.
Our matches intrigued me to understand the exact mechanisms of dice rolls in the game and trying to find an exact formula for the involved probabilities. I managed to find a calculator, implemented in JavaScript. Since the script and all calculations are done locally, I have spent my day trying to understand how these calculations are made.
We can define a sequence of dice rolls as follows:
- We first must define the battle state. Let the state be $(A, D)$ where
$A_t \in \{0, 1, 2, \cdots \})$ is the number of attacking troops that may still attack at time $t$ (the code uses $A_t = n-1$ if $n$ is the total attacker troops on the territory).
$D_t \in \{0, 1, 2, \cdots \}$ is the number of defending troops at time $t$.
We define a stopping time by $\tau := \inf \{t \ge 0 : A_t=0 \text{ or } D_t=0 \}$. The process stops when either the attacker can no longer attack $(A_t = 0)$ or the defenders are eliminated $D_t = 0$.
Define the Bernoulli random variable $$W = \mathbf{1}_{D_\tau = 0},$$
so that $W = 1$ if the attacker eventually eliminates all defenders (attacker wins the battle), and $W = 0$ otherwise.
The chance for the attacker to eventually win the battle can then be formally expressed as
$$\mathbb E\left[W \mid (A_0, D_0) = (A, D) \right] = \mathbb P(A, D) = \mathbb P\left( W = 1 \mid (A_0, D_0) = (A, D) \right).$$
The battle mechanics that I can infer from the code is the following:
In each round of the battle the attacker rolls up to $r = \min(3, A)$ dice and the defender rolls up to $s = \min(2, D)$ dice.
We sort attacker dice and the defender dice descending. We then compare the top $\ell = \min(r, s)$ pairs element-wise. For each comparison the higher die wins and the loser loses one troop. Ties go to the defender (standard RISK), i.e. ties count as defender wins.
So for example, if $\ell = 2$ the outcomes are: attacker loses 2 troops $(2, 0)$, attacker and defender each lose 1 troop $(1, 1)$, or defender loses 2 troops $(0, 2)$. Note for these tuples that $i + j = \ell$ since every comparison one side always loses exactly one troop.
Apart from the standard game mode, we also have the apocalypse (ties goes to the attacker instead) and the capital game mode (defender may roll 3 dice, so we allow for $\ell \leq 3$). The capital game mode can be used when someone attacks the "home province" (capital) of another player.
Call the pair $(x, y) \in \{1, \dots, 6\}^{r}\times \{1, \dots, 6\}^{s}$ an $(i, j)$-pair if that set of $r$-attacking-and-$s$-defending dice rolls results in the attacker losing $i$ troops and the defender loses $j$ troops, when the battle ends. We call the set of all $(i, j)$-pairs, subject to $(r, s)$, by $A_{i, j}^{(r, s)}$.
Now the code seems to, for a fixed dice count $(r ,s)$, define the per-computed per-round outcome probabilities
$$p_{i, j}^{(r, s)} = \displaystyle\frac{\left| A_{i, j}^{(r, s)} \right|}{6^{r + s}}$$
for $1 \leq r, s \leq 3$ and storing them.
For example:
$$p^{(1,1)}_{0,1} = \frac{15}{36},\qquad p^{(1,1)}_{1,0} = \frac{21}{36}$$
since the attacker wins the single comparison in 15 of the 6² = 36 ordered pairs, and ties + attacker loss make the other 21.
This makes
$$\sum_{i, j} p_{i, j}^{(r, s)} = 1 \text{ for all tuples } (r, s).$$
Finally it calculates the probability by recursion:
$$\mathbb P(A,D) = \sum_{(i,j) \in \Delta(r,s)} p^{(r,s)}_{i,j}\, \mathbb P(A - i, D - j)$$
with boundary conditions
$$P(A, 0) = 1 \text{ for all } A \ge 0, \qquad P(0, D) = 0\text{ for all } D \ge 1.$$
Here we sum over the set of possible (allowed) tuples $\Delta(r,s)$, for example $\Delta(3,2)=\{ (2, 0), (1, 1), (0, 2) \}$.
(The code fills a table of $\mathbb P(\cdot, \cdot)$ using the pre-computed $p^{(r,s)}_{i,j}$ and the base cases.)
Here are my two questions:
1. Is there any closed form formula that does not rely on a recursive calculation?
If we let $\{\mathbb X_t)_{t \ge 0} = \{ (A_t, D_t) \}_{t \ge 0}$ be the Markov chain on $\left(\mathbb{Z}_{\ge 0}\right)^2$, then all tuples with either $A_t = 0$ or $D_t = 0$ are absorbing states. Otherwise the state $(A_t \geq 0, D_t \geq 0)$ is transient. What is the the full Markov transition matrix in this case? Knowing this matrix can get us the probabilities via the the fundamental matrix.
Is there a reason the code opts for a DP solution?
2. How does the Balanced Blitz mode work? The code defines the method
makeBalanced() { const bbCalc = (Math.pow(this.value, 1.3) / (Math.pow(this.value, 1.3) + Math.pow((1 - this.value), 1.3)) - 0.1) / 0.8; this.value = Math.max(0, Math.min(1, bbCalc)); } So this code suggests we define a transformation
$$g_\alpha(p) = \frac{p^\alpha}{p^\alpha + (1-p)^\alpha}, \qquad \alpha=1.3$$
and clips the probabilities to $[0, 1]$ by
$$f(p) = \operatorname{clip}_{[0,1]} \Big( \frac{g_\alpha(p) - 0.1}{0.8}\Big).$$
What does the magic numbers $0.1$ and $0.8$ do?
