Solving Police vs. Guerrillas

Solving Police vs. Guerrillas#

The functions below will create the correct game matrix and will calculate the winning percentages of the various strategies. First, we initialize python in the code block below. Then, we can generate several version of Police vs. Guerrillas.

Hide code cell source

 
## Do not change this cell, only execute it. 
## This cell initializes Python so that pandas, numpy and scipy packages are ready to use.

import random
from IPython.display import display, Markdown
import pandas as pd
%matplotlib inline
import matplotlib.pyplot as plots
plots.style.use('fivethirtyeight')
import numpy as np
import scipy as sp
import math
import scipy.stats as stats
from fractions import Fraction

Functions that Create the Game Matrix#

Hide code cell source

 
def create_player_dict(name, anchor_val):
    strat = np.arange(math.ceil(anchor_val / 2), anchor_val + 1)
    index = np.arange(len(strat))
    strat_name = [f"{x} - {anchor_val - x}" for x in strat]
    return {
        'player': name,
        'index': index,
        'strat': strat,
        'strat_name': strat_name
    }

def game_matrix(player1, player2):
   # Create an empty DataFrame with specified index and columns
   res = pd.DataFrame(1/2, index=player1['strat_name'], columns=player2['strat_name'], 
                       dtype='object')
   return res

def play(p_max, g_max, p_strat, g_strat):
   A_0 = p_strat ; B_0 = p_max - A_0
   A = np.random.choice([A_0, B_0])
   B = p_max - A 
   reps = 10000
   win_pct_ema = 0.5
   for k in range(reps):
      a_0 = g_strat ; b_0 = g_max - a_0
      a = np.random.choice([a_0, b_0])
      b = g_max - a
      if ( ( a > A ) or ( b > B ) ):
         v = 0
      else:
         v = 1
      # Update the EMA instead of appending to a list
      alpha = min( 0.5 , ( 2 / ( k + 1 ) ) )
      win_pct_ema = (v * alpha) + (win_pct_ema * (1 - alpha))
   temp = win_pct_ema
   if temp <= 0.015:
      t = Fraction(0)
   elif temp >= 0.985:
      t = Fraction(1)
   else:
      t = Fraction(temp).limit_denominator(12)
   ## uncomment line below to help with debugging the init() function.
   #   print(f"police play ({A},{B}) while guerrillas play ({a},{b})")
   return t

Given that all three toolkit functions are working properly, the following code will generate any Police versus Guerrillas example game matrix we wish.

Example 1: 8P vs. 6G#

p = 8
g = 6
P = create_player_dict('P', p)
G = create_player_dict('G', g)
results = game_matrix(P,G)
for i in P['index']:
   for j in G['index']:
      results.loc[P['strat_name'][i],G['strat_name'][j]] = play(p,g, int(P['strat_name'][i][0]),int(G['strat_name'][j][0]))

results.style.set_caption(f"<b>{p} Police vs. {g} Guerrillas</b>").format(precision=1)
8 Police vs. 6 Guerrillas
  3 - 3 4 - 2 5 - 1 6 - 0
4 - 4 1 1 0 0
5 - 3 1 1/2 1/2 0
6 - 2 0 1/2 1/2 1/2
7 - 1 0 0 1/2 1/2
8 - 0 0 0 0 1/2

Example 1: Reducing by Doominance#

Notice that Police 6 - 2 dominates 7 - 1 and 8 - 0. After these two rows are deleted, then Guerrillas 6 - 0 dominates 5 - 1 and 4 - 2. This leaves:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|cc} & \textbf{3 - 3} & \textbf{6 - 0}\\ \hline \textbf{4 - 4} & 1 & 0 \\ \textbf{5 - 3} & 1 & 0 \\ \textbf{6 - 2} & 0 & \frac{1}{2} \end{array} \end{array}\end{split}\]

With Police 4 - 4 and 5 - 3 equally effective, we can choose either one to retain while deleting the other, so we have the following:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|cc} & \textbf{3 - 3} & \textbf{6 - 0}\\ \hline \textbf{4 - 4} & 1 & 0 \\ \textbf{6 - 2} & 0 & \frac{1}{2} \end{array} \end{array}\end{split}\]

The solution by oddments: both players oddments will be \(1\) and \(\frac{1}{2}\), so the players optimal strategy sets (including all original strategies) will be as follows:

\[\begin{split}\begin{align}\vec r &= \left[\frac{1}{3},0,0,\frac{2}{3}\right]\\ \vec c &= \left[\frac{1}{3},0,\frac{2}{3},0,0\right]\\v &=\frac{1}{3}\end{align}\end{split}\]

Example 2: 10P vs. 8G#

p = 10
g = 8
P = create_player_dict('P', p)
G = create_player_dict('G', g)
results = game_matrix(P,G)
for i in P['index']:
   for j in G['index']:
      results.loc[P['strat_name'][i],G['strat_name'][j]] = play(p,g, int(P['strat_name'][i][0]),int(G['strat_name'][j][0]))

results.style.set_caption(f"<b>{p} Police vs. {g} Guerrillas</b>").format(precision=1)
10 Police vs. 8 Guerrillas
  4 - 4 5 - 3 6 - 2 7 - 1 8 - 0
5 - 5 1 1 0 0 0
6 - 4 1 1/2 1/2 0 0
7 - 3 0 1/2 1/2 1/2 0
8 - 2 0 0 1/2 1/2 1/2
9 - 1 0 0 0 1/2 1/2
10 - 0 0 0 0 1/2 1/2

Example 2: Reduction by Dominance#

After seeing that Police 8 - 2 dominates 9 - 1 and 10 - 0, and then that Guerrillas 8 - 0 dominates 7 - 1 and 6 - 2, we are left with the follwing:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|ccc} & \textbf{4 - 4} & \textbf{5 - 3} & \textbf{8 - 0}\\ \hline \textbf{5 - 5} & 1 & 1 & 0\\ \textbf{6 - 4} & 1 & \frac{1}{2} & 0 \\ \textbf{7 - 3} & 0 & \frac{1}{2} & 0\\ \textbf{8 - 2} & 0 & 0 & \frac{1}{2}\end{array} \end{array}\end{split}\]

Police 5 - 5 dominates 6 - 4 and 7 - 3 which gives the following:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|ccc} & \textbf{4 - 4} & \textbf{5 - 3} & \textbf{8 - 0}\\ \hline \textbf{5 - 5} & 1 & 1 & 0\\ \textbf{8 - 2} & 0 & 0 & \frac{1}{2}\end{array} \end{array}\end{split}\]

The Guerrillas now have \(2\) identical strategies and therefore we have the following:

\[\begin{split}\begin{array}{cc}&\textbf{Guerrillas}\\\textbf{Police}& \begin{array}{r|cc} & \textbf{4 - 4} & \textbf{8 - 0}\\ \hline \textbf{5 - 5} & 1 & 0\\ \textbf{8 - 2} & 0 & \frac{1}{2}\end{array} \end{array}\end{split}\]

Solution#

As we have seen before, the oddments are \(\frac{1}{3}\) and \(\frac{2}{3}\) for both players while the value is \(\frac{1}{3}\).

Example 3: 11P vs. 9G#

p = 11
g = 9
P = create_player_dict('P', p)
G = create_player_dict('G', g)
results = game_matrix(P,G)
for i in P['index']:
   for j in G['index']:
      results.loc[P['strat_name'][i],G['strat_name'][j]] = play(p,g, int(P['strat_name'][i][0]),int(G['strat_name'][j][0]))

results.style.set_caption(f"<b>{p} Police vs. {g} Guerrillas</b>").format(precision=1)
11 Police vs. 9 Guerrillas
  5 - 4 6 - 3 7 - 2 8 - 1 9 - 0
6 - 5 1 1/2 0 0 0
7 - 4 1/2 1/2 1/2 0 0
8 - 3 0 1/2 1/2 1/2 0
9 - 2 0 0 1/2 1/2 1/2
10 - 1 0 0 0 1/2 1/2
11 - 0 0 0 0 1/2 1/2

The solution to 11P vs. 9G is quite similar to the work shown above.

Contents