Preprocessing
Be sure to read superb_rain's excellent answer.
The following code is meant as a preprocessing. It simply iterates over every single attack & defense configuration, and calculates the cumulative probability that the attacker manages to kill 0, 1 or 2 defense soldiers.
It is slow, but it's not a problem since it's only supposed to run once and output a probability distribution that you can use in your code.
from itertools import product
from collections import Counter
D6 = [1, 2, 3, 4, 5, 6]
probabilities = {}
for n_atk_dice in range(1, 4):
for n_def_dice in range(1, 3):
attacker_kills = Counter()
for attack in product(D6, repeat=n_atk_dice):
attack = sorted(attack, reverse=True)
for defense in product(D6, repeat=n_def_dice):
defense = sorted(defense, reverse=True)
result = sum(1 for a,d in zip(attack, defense) if a > d)
attacker_kills[result] +=1
probabilities[(n_atk_dice, n_def_dice)] = [
attacker_kills[0],
attacker_kills[0] + attacker_kills[1],
attacker_kills[0] + attacker_kills[1] + attacker_kills[2]
]
import pprint
pprint.pprint(probabilities)
probabilities
is now:
{(1, 1): [21, 36, 36],
(1, 2): [161, 216, 216],
(2, 1): [91, 216, 216],
(2, 2): [581, 1001, 1296],
(3, 1): [441, 1296, 1296],
(3, 2): [2275, 4886, 7776]}
That's all the information you need, and you won't need to sort any array anymore. You could save the code in a separate script, and simply use this literal definition in your code. You can check the values with other sources (e.g. https://web.stanford.edu/~guertin/risk.notes.html).
Use
With random.choices
As an example, for 3 vs 2:
import random
random.choices([0, 1, 2], cum_weights=probabilities[(3, 2)])
# => Either [0], [1] or [2]
There will be a 2275/7776 chance that the attack loses 2 soldiers, a (4886 - 2275)/7776 chance that both sides lose 1 soldier, and a (7776-4886)/7776 chance that the defense loses 2 soldiers.
For 1 vs 2:
random.choices([0, 1, 2], cum_weights=probabilities[(1, 2)])
# => [0] or [1]
Since the cumulative weights are [161, 216, 216]
, there's 0% chance that the defense loses 2 soldiers. Either the attack loses a soldier (with a 161/216 probability) or the defense loses one (with a 55/216 probability).
With random.random()
You could also define probabilities
this way:
total = sum(attacker_kills.values())
probabilities[(n_atk_dice, n_def_dice)] = [
attacker_kills[0] / total,
(attacker_kills[0] + attacker_kills[1]) / total
]
The output becomes:
{(1, 1): [0.5833333333333334, 1.0],
(1, 2): [0.7453703703703703, 1.0],
(2, 1): [0.4212962962962963, 1.0],
(2, 2): [0.44830246913580246, 0.7723765432098766],
(3, 1): [0.3402777777777778, 1.0],
(3, 2): [0.2925668724279835, 0.628343621399177]}
You can then simply get a random number between 0.0 and 0.99999999999 (with random.random()
), and compare it to the two values.
- If the random number is smaller than the first number : defense loses no soldier.
- If the random number is between both numbers, defense loses 1 soldier.
- If the random number is larger than the second number : defense loses 2 soldiers.
If defense loses x
soldiers, the attacker loses min(n_atk_dice, n_def_dice) - x
soldiers.
Markov chains, part 1
Just for fun, I tried to use the non-cumulated probabilities to define a Markov chain:
# pip install PyDTMC
# see https://pypi.org/project/PyDTMC/
from pydtmc import MarkovChain, plot_graph
N = 30
probabilities = {
(1, 1): [0.5833333333333334, 0.4166666666666667, 0.0],
(1, 2): [0.7453703703703703, 0.25462962962962965, 0.0],
(2, 1): [0.4212962962962963, 0.5787037037037037, 0.0],
(2, 2): [0.44830246913580246, 0.32407407407407407, 0.22762345679012347],
(3, 1): [0.3402777777777778, 0.6597222222222222, 0.0],
(3, 2): [0.2925668724279835, 0.3357767489711934, 0.37165637860082307]}
states = [(a, b) for a in range(N) for b in range(N)]
#NOTE: A sparse matrix would be a good idea for large N
p = [[0 for _ in range(N * N + 2)] for _ in range(N * N + 2)]
p[-1][-1] = 1.0 # Absorbing state 'defense wins'
p[-2][-2] = 1.0 # Absorbing state: 'attack_wins'
def state_id(a, b):
return a * N + b
for a, b in states:
i = state_id(a, b)
if a == 0:
p[i][-1] = 1.0 # defense wins
elif b == 0:
p[i][-2] = 1.0 # attack wins
else:
a_dice = min(a, 3)
b_dice = min(b, 2)
d = min(a_dice, b_dice)
p0, p1, p2 = probabilities[(a_dice, b_dice)]
p[i][state_id(a-d,b)] = p0
p[i][state_id(a-(d-1),b-1)] = p1
if d == 2:
p[i][state_id(a-(d-2),b-2)] = p2
state_names = [f'{a} vs {b}' for a, b in states] + ['attack_wins', 'defense_wins']
mc = MarkovChain(p, state_names)
The resulting graphs are interesting:
import matplotlib.pyplot as plt
plt.rcParams['figure.figsize'] = [15, 10]
plot_graph(mc, nodes_type=False, dpi=200)

mc.absorption_probabilities
is a matrix containing the probabilities to win or lose depending on the initial state.
You can get the probability that the attacker wins for a given start (e.g. 10 vs 7), without any loop:
mc.absorption_probabilities[0][state_id(10, 7)]
# 0.7998329909591375
And by iterating over every initial state, it's possible to recreate the matrix presented in this answer:
import numpy as np
prob_matrix = np.array([[mc.absorption_probabilities[0][state_id(b,a)]
for a in range(N)] for b in range(N)])

It's also possible to see the intermediate steps during a random battle:
mc.walk(20, initial_state='12 vs 9')
It outputs:
['12 vs 7',
'11 vs 6',
'10 vs 5',
'10 vs 3',
'9 vs 2',
'8 vs 1',
'8 vs 0',
'attack_wins', ....
See this answer for more examples.