Sam's Blog

The Zombie Uprising (and how to win)

Today I'm tackling the riddler question from fivethirtyeight. It goes like this: At a pivotal moment in an epic battle between the living and the dead, the Night King, head of the army of the dead, raises all the fallen (formerly) living soldiers to join his ranks. Each army lines up single file, facing the other army. One soldier steps forward from each line and the pair duels — half the time the living soldier wins, half the time the dead soldier wins. If the living soldier wins, he goes to the back of his army’s line, and the dead soldier is out (the living army uses dragonglass weapons, so the dead soldier is dead forever this time). If the dead soldier wins, he goes to the back of their army’s line, but this time the (formerly) living soldier joins him there. (Reanimation is instantaneous for this Night King.) The battle continues until one army is entirely eliminated.

What starting sizes of the armies, living and dead, give each army a 50-50 chance of winning?

An astute reader might observe that the smallest battle for such an outcome would have 1 living soldier and 1 dead soldier. In this situation, there's a 50% chance that the living soldier will win which will leave 1 living soldier and 0 dead soldiers. There's also a 50% chance the dead soldier will win which will leave 2 dead soldiers and no living soldiers. However, what kind of battle would only be one on one? That's usually reserved for the final battle scene and I don't think we're there yet. Or are we? Full disclosure, I don't really follow Game of Thrones.

In fact, there are many potential combinations of army sizes, the only requirement is that if there are n dead soldiers, there must be n^2 living soldiers. Allow me to demonstrate:

In [1]:

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

First, we need to generate a range of outcomes. Let's assume the number of soldiers on each side looks like the following: {number of living soldiers (L), number of dead soldiers (D)}. After every battle, there's a 50% chance of the new number of soldiers being either (L, D-1) or (L-1, D+1). Once there are 0 living or 0 dead army members, the battle ends and one side gets to declare themselves the winner.

If we pick some starting number for the number of dead soldiers then we can use a multiplier to set what the number of living soldiers will be. Once we have the number of living and dead soldiers, we can simulate any number of battles to see what the outcome will be for that combination. I've chosen dead army sizes of 5, 10, 15, and 20 with a living army 10% to 25x bigger than the dead army. For each combination I simulate 100 battles and take note of which army won.

In [2]:

outcome_list = []
for i in range(1,250):
    multiplier = i/10
    for d_size in range(5,21,5):
        for j in range(0,100):
            dead = d_size
            live = round(dead * (multiplier))
            while True:
                outcome_options = [[live-1, dead+1],[live, dead-1]]
                outcome = np.random.choice([0,1], p =[.5,.5])
                [live,dead] = outcome_options[outcome]        
                if live <= 0 or dead <=0:
                    outcome_list.append([d_size, multiplier, live,dead])
                    break

Now that we have a list of all outcomes for all combinations of army sizes, we can aggregate the number of wins each side achieved for the given army sizes.

In [3]:

outcome_array = pd.DataFrame(outcome_list)
outcome_array.columns = ['size_of_dead_army','multiplier','live_army','dead_army']
outcome_array['live_army_win'] = np.where(outcome_array['live_army']==0,0,1)
outcome_array['dead_army_win'] = np.where(outcome_array['dead_army']==0,0,1)
grouped = outcome_array.groupby(by=['multiplier','size_of_dead_army']).sum().reset_index()

Once we've counted the number of wins, we can chart them. Each chart shows the number of wins each army won given 100 battles at the different army size. The chart title lists the size of the dead army, and the multiple indicates what multiple is applied to generate the living army size.

In [23]:

fig, ax = plt.subplots(2,2, sharex='col', sharey='row')
size= 0
for i in range(0,2):    
    for j in range(0,2):
        size+=5
        temp=grouped.loc[grouped['size_of_dead_army']==size]
        ax[i,j].scatter(temp['multiplier'], temp['dead_army_win'],marker ='.', color='b')
        ax[i,j].scatter(temp['multiplier'], temp['live_army_win'],marker ='.', color='r')
        ax[i,j].set(title = 'Starting dead army size: %d' %(size))

ax[1,0].set(xlabel = 'Live army multiple of dead army',
           ylabel = 'Number of victories')
ax[1,1].set(xlabel = 'Live army multiple of dead army')
ax[0,0].set(ylabel = 'Number of victories')
ax[0,0].legend(loc='best')
fig.set_figheight(10)
fig.set_figwidth(15)

The point in which victory for either side is equally likely comes when the the scatter plots both hit the 50 mark. This indicates that out of 100 battles, each side is equally likely to win 50. In every chart, that intersection happens roughly when the multiple of the dead army used to generate the living army, is equal to the size of the dead army. If n represents the size of the dead army, the size of the living army can be generalized as n * n or n^2. Therefore it doesn't matter what size the dead army is, as long as the army of the living is n^2, each side has an equal chance of winning.

There are comments.

Page 1 / 1

blogroll

social