Game Theory, in depth: computing winning moves and equilibria, from Grundy numbers to linear programs and regret matching

Four kinds of game, four algorithms

The rows differ in two things: whether players move in turn with full knowledge of the state, and whether one player's gain is the other's loss. Sequential games with perfect information always have a solution in pure moves; simultaneous games generally need randomised, or mixed, strategies, because any predictable choice can be exploited.

Choosing the algorithm

Impartial games and Grundy numbers

In an impartial game both players have the same moves from every position, and under normal play the player who cannot move loses. Every position is a win or a loss for the player about to move, and the Sprague-Grundy theorem says more: each position is equivalent to a single Nim heap of some size, its Grundy number. A position with Grundy number 0 is a loss for the player to move.

The Grundy number is the mex (minimum excluded value) of the Grundy numbers of the positions you can move to. Computing it is dynamic programming over positions in order of size.

def grundy(n, moves):
    g = [0] * (n + 1)
    for i in range(1, n + 1):
        reachable = {g[i - m] for m in moves if m <= i}
        k = 0
        while k in reachable:      # mex
            k += 1
        g[i] = k
    return g

print(grundy(20, (1, 3, 4)))
# [0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2]

For the subtraction game where a move removes 1, 3 or 4 tokens, the sequence repeats with period 7: 0, 1, 0, 1, 2, 3, 2. Losing positions are those with remainder 0 or 2 modulo 7. Periodicity like this is common in subtraction games and lets you answer for huge heaps, but verify the period by computation rather than assuming it.

Sums of games: Nim and the XOR rule

The power of Grundy numbers is composition. When a game is a sum of independent components and a move is made in exactly one of them, the Grundy number of the whole is the XOR of the components' numbers. Nim is the base case: a heap of size h has Grundy number h.

Take Nim heaps 3, 4 and 5. Their XOR is 3 xor 4 xor 5 = 2, nonzero, so the player to move wins. A winning move makes the XOR zero: find a heap h with h xor 2 < h and reduce it to h xor 2. Only heap 3 qualifies (3 xor 2 = 1); heaps 4 and 5 would have to grow to 6 and 7. So the unique winning move is to reduce the 3-heap to 1.

Now mix games. Suppose the position is a subtraction-game heap of 10 tokens (Grundy number 1 from the table) next to a Nim heap of 2. The total is 1 xor 2 = 3, a win. One winning move reduces the Nim heap from 2 to 1, making 1 xor 1 = 0; another takes 4 tokens from the subtraction heap, reaching 6, whose Grundy number is 2, making 2 xor 2 = 0. The code below finds such moves for any sum.

from functools import reduce

def winning_moves(components):
    # components: list of (position, options_fn, grundy_fn)
    total = reduce(lambda a, b: a ^ b, (gf(pos) for pos, _, gf in components), 0)
    if total == 0:
        return []                       # losing: every move hands the opponent a win
    moves = []
    for i, (pos, options, gf) in enumerate(components):
        target = gf(pos) ^ total
        for nxt in options(pos):
            if gf(nxt) == target:
                moves.append((i, pos, nxt))
    return moves

Game trees, briefly

Partisan games, where the players have different moves, do not reduce to Nim heaps. For these, minimax evaluates the game tree: the value of a position is the maximum over the mover's options of the minimum over the opponent's replies, recursively. Alpha-beta pruning skips branches that cannot change the result, and with good move ordering it searches roughly the square root of the nodes that plain minimax does. Memoising positions in a transposition table turns the tree into a graph. For games small enough to enumerate every position, retrograde analysis works backwards from terminal positions and labels everything, which is how endgame tables are built. Deep game-tree search has its own pages; the rest of this article is about the case minimax cannot handle: simultaneous moves.

Zero-sum matrix games as a linear program

In a two-player zero-sum matrix game the row player picks a row and the column player picks a column at the same time; the entry is what the column player pays the row player. Consider this matrix.

Check for a pure solution first. The row player's guaranteed payoff with a pure row is the row minimum: -1 and -2, so the best is -1. The column player's guaranteed loss limit with a pure column is the column maximum: 3, 4 and 2, so the best is 2. Since -1 is not 2 there is no saddle point, and both players must randomise.

Von Neumann's minimax theorem says there is a value v and mixed strategies achieving it. The row player's problem is a linear program: choose probabilities p and a number v to maximise v subject to every column giving the row player at least v.

import numpy as np
from scipy.optimize import linprog

def solve_row(A):
    m, n = A.shape
    cost = np.zeros(m + 1); cost[-1] = -1          # maximise v
    A_ub = np.hstack([-A.T, np.ones((n, 1))])      # v - sum_i p_i A[i, j] <= 0
    A_eq = np.zeros((1, m + 1)); A_eq[0, :m] = 1   # probabilities sum to 1
    res = linprog(cost, A_ub=A_ub, b_ub=np.zeros(n), A_eq=A_eq, b_eq=[1],
                  bounds=[(0, None)] * m + [(None, None)], method="highs")
    return res.x[:m], res.x[-1]

A = np.array([[3, -1, 2], [-2, 4, 1]], dtype=float)
p, v = solve_row(A)        # p = [0.6, 0.4], v = 1.0
q, w = solve_row(-A.T)     # column player: q = [0.5, 0.5, 0.0], -w = 1.0
print(p @ A)               # [1.0, 1.0, 1.6]: no column pays the row player less than 1
print(A @ q)               # [1.0, 1.0]: both rows earn exactly 1 against q

The solver returns row strategy 0.6 and 0.4, column strategy 0.5, 0.5 and 0, and value 1. Verify it the way you should verify any equilibrium: against p, the columns pay 1, 1 and 1.6, so no column does better for the column player than 1; against q, both rows earn exactly 1, so the row player has nothing to gain by deviating. Column 3 gets probability zero because against p it costs the column player 1.6. The column player's problem is the same program on the negated transpose, and the two values match, which is LP duality in action.

Regret matching when the matrix is implicit

When the matrix is too large to write down, or the game is only available as a simulator, learning dynamics replace the LP. Regret matching is the simplest: each player tracks, for every action, how much better it would have done than its actual mixed play, and plays each action with probability proportional to its positive accumulated regret. In a two-player zero-sum game the average strategies converge to an equilibrium; the current strategies need not.

def regret_matching(A, T):
    m, n = A.shape
    rr, rc = np.zeros(m), np.zeros(n)          # accumulated regrets
    sp, sq = np.zeros(m), np.zeros(n)          # strategy sums
    for _ in range(T):
        pp = np.maximum(rr, 0); pp = pp / pp.sum() if pp.sum() > 0 else np.ones(m) / m
        qq = np.maximum(rc, 0); qq = qq / qq.sum() if qq.sum() > 0 else np.ones(n) / n
        sp += pp; sq += qq
        u_row = A @ qq                         # each pure row against qq
        u_col = -(pp @ A)                      # each pure column against pp
        rr += u_row - pp @ u_row
        rc += u_col - qq @ u_col
    pa, qa = sp / T, sq / T
    gap = (A @ qa).max() - (pa @ A).min()      # duality gap of the averages
    return pa, qa, gap

The quality measure is the duality gap of the average strategies: the best payoff the row player could get against the column average, minus the worst the column player could inflict against the row average. It is zero exactly at an equilibrium. On the matrix above the gap was 1.2996 after 10 iterations, 0.4063 after 100, 0.1045 after 1,000 and 0.0360 after 10,000, with the averages at about 0.593 and 0.407 for the rows and 0.501, 0.499 and 0.0001 for the columns. That slow, roughly inverse-square-root convergence is typical. Counterfactual regret minimisation applies the same update at every information set of an extensive-form game, which is how large poker abstractions were solved.

General-sum games and why they are hard

When payoffs are not opposite, equilibria multiply and stop being interchangeable. In Battle of the Sexes, two players prefer to meet but disagree on where: both at opera pays 3 and 2, both at football pays 2 and 3, and failing to meet pays 0 to both. There are two pure equilibria, one at each venue, and a mixed one found by indifference: the row player goes to opera with probability 3/5 so the column player is indifferent (2 times 3/5 equals 3 times 2/5), and the column player goes to opera with probability 2/5 for the same reason. Each player's mixed-equilibrium payoff is 1.2, worse for both than either pure equilibrium.

For small games, support enumeration tries each pair of supports, solves the indifference equations and checks that no action outside the support pays more. Lemke-Howson follows a path to one equilibrium of a two-player game. In general, computing a Nash equilibrium is PPAD-complete even for two players, so no polynomial algorithm is expected. Correlated equilibria, where a mediator recommends actions, are different: they are the solutions of a linear program and are polynomial to compute, and when every player runs a no-regret learner such as regret matching, the empirical distribution of joint play converges to the set of coarse correlated equilibria.

Failure modes

• Wrong model for the game. Minimax on a simultaneous-move game assumes the opponent sees your choice, which overstates their advantage.
• Sign conventions in the LP. Payoffs to the row player versus losses of the column player; check the solution with the two best-response products every time.
• Reading the last iterate. Regret matching and fictitious play converge on average; the current strategy can cycle forever.
• Ties in floating point. Supports found with an equality test break on 0.30000000000000004; use tolerances and exact rationals for small games.
• Treating an equilibrium as a forecast. In general-sum games there can be several, and real players may coordinate on none.
• Assuming periodicity. Grundy sequences for some games become periodic only after a long preperiod; compute far enough to confirm.

Trade-offs

The exact LP is fastest and most reliable when the matrix fits in memory, and it gives a certificate in the dual. Regret-based learning needs only payoff queries, scales to extensive-form games through CFR and parallelises well, but delivers approximate answers whose accuracy you must measure with the gap. Grundy tables cost memory linear in the number of states and are exact; when the state space is too large, look for periodicity or algebraic structure. For general-sum games, prefer correlated equilibrium when a mediator or shared signal is plausible, because it is tractable and can give higher welfare.

What to do next

1. Classify your game: sequential or simultaneous, perfect or imperfect information, zero-sum or general-sum.
2. For impartial games, write the mex recurrence, compute a table, and test the XOR rule on sums by brute force for small sizes; dynamic programming covers the recurrence pattern.
3. For zero-sum matrix games, solve the LP for both players and assert that the values agree and both best-response checks hold; linear and integer programming explains the solver side.
4. If the matrix is implicit, run regret matching and report the duality gap, not just the strategy.
5. For general-sum games, enumerate equilibria for small cases and decide which solution concept your application needs before computing anything.
6. For multi-agent LLM systems, read game theory for LLM agents to see these concepts applied to debate and negotiation.