Game Solver Code

Game Solver Code#

This is the game solver program we will run. We need to supply it’s code to Python because it is not a native function. The command cell below will become familiar as we use it in every notebook to initialize Python and load the packages we need for it to work properly in this context.

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

%matplotlib inline
import matplotlib.pyplot as plots
plots.style.use('fivethirtyeight')
import numpy as np
import scipy as sp
from scipy.optimize import linprog

Matrix Games#

Suppose we have the following game matrix:

\(\begin{array}{rr}2&4\\3&1\end{array}\)

To enter that matrix into python, we must the function np.array().

game = np.array([[2,4],[3,1]])
game

array([[2, 4],
       [3, 1]])

Zero Sum Matrix Game Solver Code#

The code below will create a function that is active only in this notebook called solver().

def solver(payoff_matrix):
    payoff_matrix = np.array(payoff_matrix)
    row_counts, col_counts = payoff_matrix.shape
# 1. Shift matrix to ensure all values are positive
# This ensures the game value V > 0
    shift = abs(payoff_matrix.min()) + 1
    A_shifted = payoff_matrix + shift
# 2. Solve for Row Player (Maximizer)
# We minimize 1/V = sum(p_i/V). Let x_i = p_i/V
# Objective: min (1 * x1 + 1 * x2 + ...)
    c_row = np.ones(row_counts)
# Constraints: A_shifted.T * x >= 1  =>  -A_shifted.T * x <= -1
    A_ub_row = -A_shifted.T
    b_ub_row = -np.ones(col_counts)
    res_row = linprog(c_row, A_ub=A_ub_row, b_ub=b_ub_row, method='highs')
# Game Value V = 1 / sum(x_i)
    v_shifted = 1 / res_row.fun
    row_strategy = res_row.x * v_shifted
# 3. Solve for Column Player (Minimizer) using the Dual
# Objective: max (1 * y1 + 1 * y2 + ...) => min (-1 * y1 - 1 * y2)
    c_col = -np.ones(col_counts)
# Constraints: A_shifted * y <= 1
    A_ub_col = A_shifted
    b_ub_col = np.ones(row_counts)
    res_col = linprog(c_col, A_ub=A_ub_col, b_ub=b_ub_col, method='highs')
    col_strategy = res_col.x * (1 / abs(res_col.fun))
# Final Game Value
    game_value = v_shifted - shift
    print(f"Game Value: {np.round(game_value,3)}")
    print(f"Rose Strategy: {np.round(row_strategy,3).tolist()}")
    print(f"Colin Strategy: {np.round(col_strategy,3).tolist()}")
    return None

Testing the Code#

Using the game above, we run the function:

solver(game)

Game Value: 2.5
Rose Strategy: [0.5, 0.5]
Colin Strategy: [0.75, 0.25]

Example#

Suppose the game we wish to analyze is the following:

\[\begin{split}\begin{array}{cc}&\textbf{Colin}\\\textbf{Rose}&\begin{array}{r|rr}&A&B&C\\\hline A&1&4&2\\B&5&3&1\end{array}\end{array}\end{split}\]

We create the game matrix in python:

game2 = np.array([[1,4,2],[5,3,1]])

Solving the game:

solver(game2)

Game Value: 1.8
Rose Strategy: [0.8, 0.2]
Colin Strategy: [0.2, 0.0, 0.8]

We see that only Colin’s A and C strategies are active. The value of the game is 1.8 which means that the expected value of the game is Rose winning 1.8 on average and Colin winning -1.8 on average. This is due to the fact we are playing a zero sum game. If Rose wins \(\$1\), Colin must lose that much.

Contents