Minimax Deep Dive, in depth: game values, exact solving with memoization, depth-aware scores, retrograde analysis and where minimax stops applying

What the minimax value promises

Write the game as states, a set of legal moves from each state, a terminal test, and a utility for terminal states measured from MAX's point of view. The value of a state is defined recursively. A terminal state is worth its utility. A non-terminal state where MAX moves is worth the maximum of its children's values, and one where MIN moves is worth the minimum. For a finite game this recursion always terminates. Evaluating it bottom-up is called backward induction.

Zermelo's theorem from 1913 is the consequence that matters. Every finite two-player game of perfect information with no chance moves has a determined value. In win-draw-loss games, either the first player can force a win, the second can, or both can force at least a draw. The minimax value says two things: MAX has a strategy reaching at least this value against any opponent, and MIN has one holding MAX to at most this value. It describes worst cases, not predictions; against a weak opponent a riskier move may win more.

In the tree above, MAX has three moves. After move b, MIN can reach 2. After move c, MIN can also reach 2, even though c contains the largest leaf, 14. A greedy player chasing 14 walks into c and gets 2. Minimax plays a and gets at least 3. That is the whole intuition: a branch is worth what the opponent lets you have, not the best thing in it.

Solving tic-tac-toe exactly

Tic-tac-toe is small enough to solve exactly, which makes it the right testbed for checking an implementation against known facts. The solver below scores a position from X's point of view, caches each position, and returns exact values. The board is a 9-character string and side to move is passed explicitly. In this game side to move can be derived from the board, but writing it into the cache key is the habit that keeps you safe in games where it cannot.

from functools import lru_cache

LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6),
         (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
WIN = 10

def winner(board: str):
    for a, b, c in LINES:
        if board[a] != "." and board[a] == board[b] == board[c]:
            return board[a]
    return None

@lru_cache(maxsize=None)
def value(board: str, to_move: str) -> int:
    """Exact minimax value from X's point of view; faster wins score higher."""
    ply = 9 - board.count(".")
    w = winner(board)
    if w == "X":
        return WIN - ply
    if w == "O":
        return ply - WIN
    if "." not in board:
        return 0
    nxt = "O" if to_move == "X" else "X"
    children = [value(board[:i] + to_move + board[i + 1:], nxt)
                for i in range(9) if board[i] == "."]
    return max(children) if to_move == "X" else min(children)

print(value("." * 9, "X"), value.cache_info().currsize)   # 0 5478

The root value is 0, so tic-tac-toe is a draw under best play. All nine first moves also score 0. The cache holds 5,478 entries, one per legal position including terminals. Without it the recursion visits 549,946 nodes, and there are 255,168 complete games. All three figures come from running the code and match published counts, which makes this game a good unit test.

Trees, graphs and sound memoization

The factor-of-100 saving comes from transpositions: move orders reaching the same position. A game tree is a graph of positions unrolled into a tree, and plain minimax re-solves every repeated subgraph. Memoizing on the position is dynamic programming on that graph, with work proportional to positions times branching factor.

Memoization is only sound if the value depends on the position alone. Anything else that affects legal moves or outcomes must be part of the key. That includes side to move, castling and en passant rights, repetition counts and move counters for draw rules, and the remaining depth when the search is depth-limited. Leaving one out produces the graph history interaction problem. A position cached as a draw by repetition along one path is reused on a path where no repetition occurred, and the engine misjudges a won position. If the key can't reasonably include the history, don't cache values that depend on it.

Depth-aware scores and the principal variation

The solver scores a win as 10 - ply, not a flat +1. With flat scores every winning move looks equal, and the engine may pick a slow win or one that makes no progress; with repetition it can loop forever while a win sits one move away. Depth-aware scoring prefers the fastest win and the slowest loss. Chess engines call it mate-distance scoring.

A concrete position shows it. Take board X.O.X..O. with X to move: X holds squares 0 and 4, O holds 2 and 7. The depth-aware solver scores square 8 at 5, an immediate win on the diagonal. Squares 3, 5 and 6 score 3, because they also win but two plies later, and square 1 scores -2, because it lets O win. With flat win scores, squares 3, 5, 6 and 8 all tie at +1, and a lowest-index tie-break plays 3, a slower win. Both versions win this position. In a larger game the flat version can fail to finish.

def best_moves(board: str, to_move: str):
    nxt = "O" if to_move == "X" else "X"
    scored = {i: value(board[:i] + to_move + board[i + 1:], nxt)
              for i in range(9) if board[i] == "."}
    target = max(scored.values()) if to_move == "X" else min(scored.values())
    return [i for i, v in scored.items() if v == target], scored

def principal_variation(board: str, to_move: str):
    line = []
    while winner(board) is None and "." in board:
        moves, _ = best_moves(board, to_move)
        i = moves[0]                      # deterministic tie-break: lowest index
        board = board[:i] + to_move + board[i + 1:]
        line.append(i)
        to_move = "O" if to_move == "X" else "X"
    return line, board

print(best_moves("X.O.X..O.", "X"))   # ([8], {1: -2, 3: 3, 5: 3, 6: 3, 8: 5})

The principal variation is the line both sides play when each picks a best move. If it contains an obviously bad reply, the evaluation or move generator is wrong. Break ties deterministically in tests and with a seeded random choice in play, so the engine is harder to predict.

Games with cycles: retrograde analysis

Recursion from the root needs the game graph to be acyclic, or a depth limit. Games with repeatable positions, such as chess endgames or many board games without capture-forced progress, have cycles, so a naive memoized recursion can recurse forever or cache half-computed values. Retrograde analysis solves such games exactly by working backwards from terminal positions. It is how endgame tablebases are built.

Every position starts as unknown, and every terminal position is labelled won or lost for the side to move. Keep, for each unknown position, a count of children not yet proven to be wins for the opponent. Process labelled positions from a queue. A parent with a move into a position that is lost for the opponent is a win. A parent whose counter reaches zero, because every move leads to an opponent win, is a loss. When the queue empties, every position still unknown is a draw, because neither side can force progress. Recording the step at which each label was set gives distance-to-win for free.

from collections import deque

def retrograde(positions, moves, predecessors, terminal_result):
    """terminal_result(p) -> 'WIN' | 'LOSS' | None, for the side to move at p."""
    label, dist = {}, {}
    remaining = {p: len(moves(p)) for p in positions}
    q = deque()
    for p in positions:
        r = terminal_result(p)
        if r is not None:
            label[p], dist[p] = r, 0
            q.append(p)
    while q:
        child = q.popleft()
        for parent in predecessors(child):
            if parent in label:
                continue
            if label[child] == "LOSS":            # parent can move into a lost position
                label[parent], dist[parent] = "WIN", dist[child] + 1
                q.append(parent)
            else:                                 # child is a win for the opponent
                remaining[parent] -= 1
                if remaining[parent] == 0:
                    label[parent], dist[parent] = "LOSS", dist[child] + 1
                    q.append(parent)
    return {p: label.get(p, "DRAW") for p in positions}, dist

Depth limits, evaluation and pathology

Most real games are too large to solve. Engines then search to a fixed depth and replace the true value at the frontier with an evaluation function, a heuristic estimate of the minimax value. Everything above the frontier is exact minimax over estimates, with three consequences. The horizon effect: an engine pushes an inevitable loss past its depth limit with delaying moves; quiescence search and extensions address it. Evaluation errors propagate upward, and a max over many noisy estimates is biased upward. And on some artificial trees studied by Nau and others, searching deeper makes decisions worse (minimax pathology). Real games rarely show it because nearby positions have correlated values.

Depth-limited values also make cache keys harder. A value computed with 3 plies remaining is not interchangeable with one computed with 7, so store the searched depth with the entry and reuse it only when it is at least the depth you need.

Where minimax stops applying

Minimax assumes exactly two players, strictly opposed interests, alternating turns, perfect information and no chance. Break any assumption and the algorithm needs a different shape. With dice or card draws, chance nodes take an expectation instead of a max or min (expectimax). Then the scale of utilities matters, not just their order. With more than two players, max-n backs up a vector of utilities, each player maximising its own; the paranoid variant assumes everyone else is allied against you. With simultaneous moves, von Neumann's minimax theorem gives a value in mixed strategies, found by linear programming, as in game theory, in depth. With hidden information, minimax over true states is unsound, because a player cannot condition on what it cannot see. Methods based on information sets, such as counterfactual regret minimization, take over.

The same min-max structure appears in machine learning. Adversarial training minimises model loss against a worst-case perturbation inside a budget. Robust optimization and GAN training are written as min-max problems too. There the inner maximisation is approximate (a few gradient steps), so the guarantee is weaker than in an exactly searched game tree.

Failure modes

Testing an implementation

Test a minimax implementation against facts rather than intuition. Solve a small game where results are known, check the root value and the number of positions visited, and confirm that pruning or caching changes the node count but never the value. Property tests help. For random positions, the value from the optimized search must equal the value from a slow, plain reference minimax. For games with symmetry, symmetric positions must get equal values. For a feel of the search order on graphs, the traversal mechanics in BFS and DFS and the memoization patterns in dynamic programming are the same building blocks.

What to do next

1. Implement the memoized tic-tac-toe solver and assert root value 0 and 5,478 cached positions.
2. Switch to depth-aware terminal scores and confirm the solver plays the immediate win in X.O.X..O..
3. Add a plain reference minimax and a property test that every optimization returns identical values.
4. List everything your game's value depends on beyond the board, and put it in the cache key.
5. If your game has cycles, solve its small endgames with retrograde analysis and use them as an oracle.
6. Move to depth-limited search with an evaluation function, then add the pruning and ordering from the game tree search article.
7. Before building, check the assumptions (two players, zero-sum, perfect information, no chance) and switch models if one fails.