Adversarial Search and Game Theory

EveryEvery search algorithm covered on Divide and Conquer and its neighbouring pages assumes a single agent moving through a static problem. Adversarial search drops that assumption: an opponent is also choosing moves, and choosing them specifically to work against you. Claude Shannon's 1950 paper on programming a computer to play chess is where this idea entered computing directly — his proposal was to search a few moves ahead, score the resulting positions with an evaluation function, and assume the opponent would always pick their best available reply, not their worst¹.

Minimax

ThatThat assumption — the opponent always plays their best move — is exactly what minimax formalises. Build a game tree: your moves are choices at "max" levels (you pick whichever child has the highest score), the opponent's moves are choices at "min" levels (they pick whichever child has the lowest score, i.e. worst for you), and the value of any position is computed by working backward from the leaves — each min node takes the minimum of its children's values, each max node takes the maximum of its children's values.

Working this tiny tree bottom-up: node A is a MIN node, so it takes the smaller of its children, min(3, 5) = 3. Node B is also MIN, so min(-1, 2) = -1. The root is a MAX node, choosing the larger of its two children's values: max(3, -1) = 3, meaning the root should choose the branch leading to A, not B — even though B contains the single best outcome anywhere in the tree (+2 is better than the +3 branch's worst case... wait, 3 > 2, so A's guaranteed 3 genuinely beats B's guaranteed -1, which is the entire point: minimax picks the move with the best guaranteed outcome against a worst-case opponent, not the move with the best possible outcome against a lucky one.

Alpha-Beta Pruning

AA real game tree is far too large to search in full — chess has roughly 10¹²⁰ possible games, vastly more than minimax could ever fully explore. Alpha-beta pruning is an exact optimisation of minimax, not an approximation: it produces identical results while skipping branches that provably cannot affect the final decision. It tracks two bounds while searching — α, the best value the maximising player can already guarantee from moves explored so far, and β, the best value the minimising player can already guarantee — and the moment a branch's value would fall outside the α–β window (meaning neither player would ever actually let the game reach that branch), the rest of that branch is skipped entirely, because no further searching there could change the choice already available at the level above. This is why it's correct and not a heuristic shortcut: a pruned branch is one the optimal play from either side would never actually reach, so its true value — whatever it turns out to be — cannot change the answer.

Beyond Two-Player, Zero-Sum: Game Theory Proper

MinimaxMinimax is the special case of a much broader field. Von Neumann and Morgenstern's foundational treatment of game theory covers games with more than two players, games where one player's gain isn't automatically the other's exact loss (non-zero-sum games), and games of imperfect information, where a player doesn't get to see everything about the current state before choosing². The field's central solution concept, a Nash equilibrium, is a set of strategies — one per player — such that no single player could do better by unilaterally switching to a different strategy, given that everyone else keeps theirs fixed. Two-player, zero-sum, perfect-information minimax is a Nash equilibrium in this more general sense too, just one where the structure of the game happens to make it directly computable by searching a tree — real-world strategic situations (an auction, a negotiation, a market with multiple competing firms) usually lack that convenient structure and need the fuller machinery of game theory to analyse at all.

Where This Shows Up in Practice

TheThe clearest modern descendant of this whole line of work is reinforcement learning applied to games — a system like AlphaGo combines a learned evaluation function (replacing Shannon's hand-built one) with tree search (a modern descendant of minimax) — and, from a different angle again, the discriminator in a generative adversarial network is playing a genuinely adversarial, two-player game against the generator, in the same formal sense covered here, even though neither network is searching a tree.

References