Probability of Winning Battles in Risk

I did a small visualization of the outcomes of battles in Risk. You can find the visualization here. This post explains the different elements of the visualization and the math to calculate the probabilities.

Legend and Example

Here’s an example for 5 attackers vs. 3 defenders:

legend-1.jpg

Since the attacker needs to always leave one unit behind, his army is divided into the unit staying behind (A) and the units attacking (B). The defender can use all his units (C). To increase the number of attackers or defenders click on plus (D). The maximum army size is 30. To decrease the number press minus (E).

The first bar shows the probability that the attacker (F) or defender (G) will win the battle, i.e., eliminate all opposing units. In the case shown the attacker has a 76.9% chance of winning over the defender.

After the large bar the expected number of losses for the attacker (H) and defender (I) is shown. For example, the attacker has a 20.8% chance of losing exactly 1 unit. The chance of losing all units corresponds to the probability that the opponent wins the battle. In our case, the attacker has a 23.1% chance of losing all five attackers (G) which corresponds to the probability of the defender winning the battle.

Finally, the expected number of units lost is shown for both parties. For example, the attacker will lose 2.18 (J) units on average when attacking with 5 vs 3 units., while the defender loses 2.54 units on average (K).

Math

The visualization is based on the Markov chain from the paper Markov Chains for the RISK Board Game Revisited by Jason A. Osborne. The calculation was done with the following Python script:

import numpy as np
import argparse
from collections import namedtuple

def transition_prop(start, end):
    # from absorbing states
    if start.attackers == 0 or start.defenders == 0:
        return (start.attackers == end.attackers and 
               start.defenders == end.defenders)

    # from transient states
    i = 3 if start.attackers >= 3 else start.attackers
    j = 2 if start.defenders >= 2 else start.defenders
    k = start.defenders - end.defenders # how many units defender loses
    l = start.attackers - end.attackers # how many units attacker loses
    if i == 1 and j == 1 and l == 0 and k == 1:
        return 15/36.0
    if i == 1 and j == 1 and l == 1 and k == 0:
        return 21/36.0
    if i == 1 and j == 2 and l == 0 and k == 1:
        return 55/216.0
    if i == 1 and j == 2 and l == 1 and k == 0:
        return 161/216.0
    if i == 2 and j == 1 and l == 0 and k == 1:
        return 125/216.0
    if i == 2 and j == 1 and l == 1 and k == 0:
        return 91/216.0
    if i == 2 and j == 2 and l == 0 and k == 2:
        return 295/1296.0
    if i == 2 and j == 2 and l == 1 and k == 1:
        return 420/1296.0
    if i == 2 and j == 2 and l == 2 and k == 0:
        return 581/1296.0
    if i == 3 and j == 1 and l == 0 and k == 1:
        return 855/1296.0
    if i == 3 and j == 1 and l == 1 and k == 0:
        return 441/1296.0
    if i == 3 and j == 2 and l == 0 and k == 2:
        return 2890/7776.0
    if i == 3 and j == 2 and l == 1 and k == 1:
        return 2611/7776.0
    if i == 3 and j == 2 and l == 2 and k == 0:
        return 2275/7776.0
    return 0

def init_states(A, D):
    State = namedtuple('state', ['attackers', 'defenders'])
    states = []
    # transient states
    for a in range(1, A+1):
        for d in range(1, D+1):
            states.append(State(a,d))
    # absorbing states
    for d in range(1, D+1):
        states.append(State(0, d))
    for a in range(1, A+1):
        states.append(State(a, 0))

    return states

def calc_P(A, D):
    states = init_states(A, D)
    n = len(states)
    P = np.zeros(shape=(n,n))
    for i in range(n):
        for j in range(n):
            p = transition_prop(states[i], states[j])
            P[i,j] = p
    return P

def calc_F(A, D):
    P = calc_P(A, D)
    Q, R = P[:A*D, :A*D], P[:A*D:, A*D:]
    I = np.identity(Q.shape[0])
    inv = np.linalg.inv(I-Q)
    return np.dot(inv, R)

def calc_winning_prob(A, D):
    F = calc_F(A, D)
    WinProb = namedtuple('win_probility', ['attacker', 'defender'])
    pa, pd = 0,0
    for j in range(D, D+A):
        pa += F[A*D-1, j]
    for j in range(0, D):
        pd += F[A*D-1, j]
    
    return WinProb(pa,pd)

def dist_mean(dist):
    res = 0
    for i, v in enumerate(dist):
        res += i*v
    return res

def calc_loss(A, D):
    F = calc_F(A, D)
    ExpectedLoss = namedtuple('expected_loss', ['attacker', 'defender'])
    LossDist = namedtuple('loss_distribution', ['attacker', 'defender'])

    # probabilities of losing some
    al, dl = (A+1)*[0], (D+1)*[0] 
    for k in range(1, D+1):
        dl[D-k] = F[A*D-1, k-1]
    for k in range(1, A+1):
        al[A-k] = F[A*D-1, D+k - 1]

    # probability of losing all
    winning_prob = calc_winning_prob(A, D)
    al[A] = winning_prob.defender
    dl[D] = winning_prob.attacker
    eal = dist_mean(al)
    edl = dist_mean(dl)
    return ExpectedLoss(eal, edl), LossDist(al, dl)

def _print_loss_info(exp, dist, who):
    print("The {} will lose the following number of units:".format(who))
    for i, v in enumerate(dist):
        print("{:>2}: {:>3.1f}%".format(i, v*100))
    print("(the expected loss is {:.2f})".format(exp))
    
    
if __name__=="__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument('--full', help="create matrix", action="store_true")
    parser.add_argument('attackers', help="(maximum) nr of attackers", type=int)
    parser.add_argument('defenders', help="(maximum) nr of defenders", type=int)
    args = parser.parse_args()
    
    A = args.attackers
    D = args.defenders
    txt = "{0} attackers have a {2:.1f}% winning chance vs {1} defenders"
    print(txt.format(A, D, calc_winning_prob(A,D).attacker*100))
    exploss, lossdist = calc_loss(A, D)
    _print_loss_info(exploss.attacker, lossdist.attacker, "attacker")
    _print_loss_info(exploss.defender, lossdist.defender, "defender")

Example:

> risk_probabilities_slim.py 5 3
5 attackers have a 76.9% winning chance vs 3 defenders
The attacker will lose the following number of units:
 0: 24.5%
 1: 20.8%
 2: 17.5%
 3: 9.7%
 4: 4.5%
 5: 23.1%
(the expected loss is 2.18)
The defender will lose the following number of units:
 0: 6.4%
 1: 10.4%
 2: 6.2%
 3: 76.9%
(the expected loss is 2.54)

The entire project, including the visualization and Python script, can be found on my GitHub page.

comments powered by Disqus