An efficient pool evaluation algorithm
In general, if the function that scores a pool (or in this case, a pair of pools) is allowed to depend on the entire ordered rolled sequence, then the function would have to be evaluated on all possible such sequences, the number of which is exponential in the number of dice. Even if we restrict ourselves to functions that only depend on unordered rolled sequences (or equivalently, the sequence after sorting each pool), the number of such sequences grows as a high order polynomial (this can be derived from e.g. comments on this answer to another question).
However, it turns out that if we can phrase the pool scoring function as a state transition over tuples (outcome, number of dice in each pool that rolled that outcome) with not too many states, we can reduce the time complexity to a polynomial of reasonable order. Here's a fuller explanation of the algorithm. This RISK-like scoring can indeed be expressed like this.
Expressing a single stage
I implemented this approach as part of my hdroller Python library. You can try this computation in your
browser using this JupyterLite notebook.
The first step is to express a single stage of a RISK-like pool evaluation as a state transition function as defined above. Given the number of dice on each side, this computes the distribution of the number of remaining dice on each side after a single stage.
class EvalRiskAttrition(hdroller.EvalPool):
def next_state(self, state, outcome, a, b):
if state is None:
score_a, score_b, advantage = 0, 0, 0
else:
score_a, score_b, advantage = state
# Advantage is the number of unpaired dice that rolled a previous (higher) number.
# If positive, it favors side A, otherwise it favors side B.
# We pair them off with newly-rolled dice of the disadvantaged side.
if advantage > 0:
score_a += min(b, advantage)
elif advantage < 0:
score_b += min(a, -advantage)
advantage += a - b
return score_a, score_b, advantage
def final_outcome(self, final_state, pool_a, pool_b):
score_a, score_b, advantage = final_state
if score_a == 0 and score_b == 0:
# No change. Eliminate this outcome to prevent infinite looping.
# This is equivalent to rerolling the contest until at least one die is removed.
return hdroller.Reroll
# Each side loses dice equal to the other's hits.
# The result is the number of remaining dice on each side.
return pool_a.num_dice() - score_b, pool_b.num_dice() - score_a
def direction(self, *_):
# See outcomes in descending order.
return -1
eval_risk = EvalRiskAttrition().bind_dice(hdroller.d6, hdroller.d6)
Finding the fixed point
Since we reroll each stage until at least one die is eliminated, the number of stages is bounded by the total number of dice. Therefore we can then repeatedly apply this attrition until everything reaches an absorbing state. We could compute the maximum number of stages explicitly, or just look for a fixed point.
def risk_attrition(a, b):
if a == 0 or b == 0:
# If one side has run out of dice, no more rolling is necessary.
return a, b
else:
# Otherwise, run the contest.
return eval_risk(a, b)
# 4 dice vs. 3 dice.
a = 4
b = 3
# Construct a die that always rolls the tuple (4, 3).
# Then, apply the risk_attrition function recursively until reaching a fixed point.
result = hdroller.Die((a, b)).sub(risk_attrition, max_depth=None, denominator_method='reduce')
# The result is how many dice are remaining at the end.
# The loser has 0 dice, and the winner has 1 or more dice.
print(result)
Denominator: 350190883979307611136000
| Outcome[0] |
Outcome[1] |
Weight |
Probability |
| 0 |
1 |
11215262070269292175045 |
3.202614% |
| 0 |
2 |
26208104640905472978960 |
7.483948% |
| 0 |
3 |
44739780296050462334400 |
12.775827% |
| 1 |
0 |
11215262070269292175045 |
3.202614% |
| 2 |
0 |
28634396560615778884510 |
8.176797% |
| 3 |
0 |
60745546693229402315592 |
17.346410% |
| 4 |
0 |
167432531647967910272448 |
47.811790% |
If you just want to know the winner:
print(result.sub(lambda a, b: 'a' if a > 0 else 'b').reduce())
Denominator: 2244741412001587200
| Outcome |
Weight |
Probability |
| a |
1718071452659096719 |
76.537611% |
| b |
526669959342490481 |
23.462389% |
This can compute a dozen dice on each side without much issue, though the denominator can get quite massive.
Best Answer
No need to apply brute force. Let's calculate the probability that the highest die is $k$ when $n$ dice are thrown. Let's name this probability $P_n(h=k)$
We know that $P_1(h=k) = \frac16, \;\forall\ k \in\{1,2,3,4,5,6\}$
What if we throw two dice? To find $P_2(h=6)$ it's easier to calculate the complementary probability that the highest die is not $6$. $$P_2(h<6) = \left({\frac56}\right)^2 \implies \\ P_2(h=6) = 1- \left({\frac56}\right)^2$$
In general for any $n$: $$P_n(h=6) = 1-\left({\frac56}\right)^n$$
Similarly: $$P_n(h<5) = \left({\frac46}\right)^n \implies\\ P_n(h=5) = 1- \left({\frac46}\right)^n - P_n(h=6)$$
In general for any $n$ and any $i$: $$P_n(h<k) = \left({\frac{k-1}6}\right)^n$$ and $$\begin{aligned} P_n(h=k) &= 1 - P_n(h<k) -P_n(h>k)\\ &=1-P_n(h<k) -P_n(h \ge k+1)\\ &=1-P_n(h<k) - (1- P_n(h < k+1))\\ &= P_n(h < k+1) - P_n(h < k)\\ &= \left({\frac{k}6}\right)^n - \left({\frac{k-1}6}\right)^n = \frac{k^n - (k-1)^n}{6^n}\\ \end{aligned}$$
Just to get a numerical sense, here are the values for $P_3(h=i)$: $$\begin{aligned} P_3(h = 6) &= \frac{91}{216} \approx 0.421 \\ P_3(h = 5) &= \frac{61}{216} \approx 0.282 \\ P_3(h = 4) &= \frac{37}{216} \approx 0.171 \\ P_3(h = 3) &= \frac{19}{216} \approx 0.088 \\ P_3(h = 2) &= \frac{7}{216} \approx 0.032 \\ P_3(h = 1) &= \frac{1}{216} \approx 0.004 \\ \end{aligned} $$ So let's compute the probability of the attacker winning if the attacker throws $3$ dice and the defender $2$. Let's denote the attacker's highest value as $A$ and the defender's highest value as $D$. We want to compute $P(A>D)$.
$$\begin{aligned} P(A>D) =& \sum_{k=1}^6 P_3(A = k) \cap P_2(D<k) \\ =&\sum_{k=1}^6 P_3(A = k) \cdot P_2(D<k) &&\text{(because throws are independent)}\\ =& \sum_{k=1}^6 \frac{k^3 - (k-1)^3}{6^3} \cdot \frac{(k-1)^2}{6^2} =& \frac{3667}{7776} \approx 0.471 \end{aligned}$$
Sum computed with WolframAlpha
Interesting to know that the attacker is slightly more probably to lose, even with three dice against the defender's two. Ties going to the defender does the job :)
If the attacker throws three dice and the defender only one then we get: $P(A>D) =\frac{95}{144} \approx 0.66$