Game Theory
Three piles of stones: 3, 4 and 5. Two players take turns; a move removes any number of stones from one pile; whoever takes the last stone wins. Should you move first, and if so, what is the winning move? The answer takes one line of arithmetic: , where is bitwise XOR, so yes, and you take 2 stones from the pile of 3.
Now replace the piles with something stranger. Each move splits a pile into two unequal piles. Or moves coins down a staircase. Or chops edges off a drawing of a tree. Or plays any number of different games side by side, where on your turn you pick one of them to move in. Remarkably, all of these reduce to the same XOR, once each component is replaced by a single number, its Grundy value. That is the Sprague–Grundy theorem, and it is the core of the first half of this lesson.
The second half leaves the tidy world of "last move wins". In chess the outcome is a score, the two players want different things, and the game is far too big to solve. There you search a tree with minimax and prune it with alpha-beta, the algorithm at the heart of every classical chess engine. Finally, when players move simultaneously (rock-paper-scissors, penalty kicks, sealed-bid auctions), there is no best pure move at all, and the right answer is a mixed strategy: a probability distribution, computed by linear programming.
This lesson builds on Game DP, which shows how to compute win/lose tables, score-difference DPs (Predict the Winner), first Grundy numbers, retrograde analysis and a first look at alpha-beta. Here we go deeper on the mathematics: the proofs behind Nim and Sprague–Grundy, the families of games those theorems unlock, a careful treatment of alpha-beta's pruning and move ordering, and the matrix games that begin classical game theory.
Why this exists
Games are the cleanest model of adversarial computation: you choose, then someone who wants you to lose chooses, and so on. That model fits more than board games. A compiler's register allocator against the worst-case program, a load balancer against the worst-case traffic, an algorithm against the worst-case input, a defender against an attacker: whenever you reason "for every move of theirs, I have a reply that…", you are doing game theory.
The subject has two roots that grew mostly apart.
Combinatorial game theory studies games of perfect information with no chance: Nim, Go endgames, Hackenbush. Charles Bouton solved Nim in 1901. Ernst Zermelo proved in 1913 that in chess either White can force a win, Black can force a win, or both can force at least a draw: every finite game of perfect information is determined, though nobody knows which case holds for chess. Roland Sprague (1935) and Patrick Grundy (1939) independently proved that every impartial game is equivalent to a single Nim pile. Berlekamp, Conway and Guy's Winning Ways (1982) turned the field into a toolkit.
Classical game theory studies strategic choice under conflict, usually with simultaneous moves and payoffs. John von Neumann proved the minimax theorem for zero-sum games in 1928; Theory of Games and Economic Behavior (von Neumann and Morgenstern, 1944) launched economics' use of games; John Nash (1950) proved that every finite game has an equilibrium in mixed strategies.
Computer science meets both. Claude Shannon's 1950 paper "Programming a Computer for Playing Chess" proposed depth-limited minimax with an evaluation function; alpha-beta pruning followed in the late 1950s, and Knuth and Moore's 1975 analysis showed how much it saves. Today, alpha-beta powers Stockfish, Monte Carlo tree search powers AlphaZero, linear programming solves zero-sum games, and auction theory decides how search ads and radio spectrum are sold.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "two players alternate, both play optimally, who wins?" | P/N positions; for small state spaces a Game DP table |
| "several piles", "remove any number from one pile" | Nim: first player wins iff XOR of pile sizes is non-zero |
| "several independent games, on each turn move in one of them" | Sprague–Grundy: XOR of the components' Grundy values |
| "remove 1, 3 or 4 stones", any fixed set of allowed removals | Subtraction game: Grundy table, eventually periodic |
| "split a pile into two", "remove a pin and its neighbours" | Splitting (octal) games: Grundy value of a split = XOR of the parts |
| "move coins one step down a staircase", "move tokens left on a line" | Staircase Nim: only odd positions count |
| "the player who takes the last stone loses" | Misère play; for Nim: normal rule unless all piles are at most 1 |
| "remove from one pile, or the same amount from both piles" | Wythoff's game: golden-ratio P-positions |
| "cut edges of a tree/graph rooted at the ground" | Green Hackenbush: colon principle, then XOR |
| "maximise your score minus the opponent's", huge game tree | Minimax with alpha-beta pruning |
| "both choose at the same time", "rock-paper-scissors", "guess the side" | Zero-sum matrix game: mixed strategy, solved by LP or 2×2 formula |
| Positions can repeat (cycles), draws possible | Retrograde analysis (Game DP) |
| up to in a one-pile game | Compute Grundy values, find the period, index by |
Intuition & first principles
What counts as a combinatorial game
For the first half of the lesson, a game means:
- Two players, who alternate moves.
- Perfect information: both see the whole position.
- No chance: no dice, no hidden cards.
- Finite: every sequence of moves ends (there are no cycles and no infinite play).
- Normal play: the player who cannot move loses. (Equivalently, the player who makes the last move wins.) The opposite convention, where the last mover loses, is misère play.
A game is impartial if both players have the same moves from every position: Nim, where either player may take from any pile. It is partisan if the moves depend on who is moving: chess (White moves white pieces), Go, checkers. The Sprague–Grundy theory below is for impartial games; partisan games need the minimax ideas later in the lesson, or Conway's theory of surreal numbers (see Variations).
P-positions and N-positions
Because the game is finite and has no chance, every position is a forced win for exactly one of the players (Zermelo's argument, by backward induction). Name positions by who wins:
- An N-position is a win for the Next player, the one about to move.
- A P-position is a win for the Previous player, the one who just moved. The player to move loses, whatever they do.
Two rules label every position, starting from the end:
- A position with no moves is a P-position (the player to move cannot move, so loses).
- A position is an N-position iff at least one move leads to a P-position. Otherwise (every move leads to an N-position) it is a P-position.
In words: you want to hand your opponent a P-position. If you can, you are winning. If every move hands them an N-position, you are losing.
Tiny example. One pile; a move removes 1 or 2 stones. Position 0: no moves, P. Position 1: move to 0 (P), so N. Position 2: move to 1 or 0; 0 is P, so N. Position 3: moves to 2 and 1, both N, so P. The pattern repeats with period 3: the P-positions are the multiples of 3. Your strategy from an N-position: always leave a multiple of 3.
flowchart RL
S5["5: N"] -->|"take 2"| S3["3: P"]
S5 -->|"take 1"| S4["4: N"]
S4 -->|"take 1"| S3
S4 -->|"take 2"| S2["2: N"]
S3 --> S2
S3 --> S1["1: N"]
S2 --> S1
S2 -->|"take 2"| S0["0: P"]
S1 -->|"take 1"| S0
Every N-position has an arrow into a P-position; every arrow out of a P-position lands on an N-position. That is the whole definition, and Game DP computes exactly this table for any game whose positions fit in memory.
Why a win/lose table is not enough
The trouble starts when a position is a sum of independent games: several piles, several boards, several regions of a Go board. On your turn you choose one component and move in it. The number of combined positions is the product of the components' sizes, which explodes. Worse, knowing whether each component is P or N does not tell you whether the sum is: two N-positions can sum to a P-position (Nim piles 1 and 1) or to an N-position (piles 1 and 2).
We need a richer label than one bit per position. That label is the Grundy value, and the simplest game where it shows up is Nim.
Mechanics
1. Nim and Bouton's theorem
Nim: several piles of stones; a move removes any positive number of stones from one pile; normal play.
Bouton's theorem (1901). A Nim position with piles is a P-position iff
where is bitwise exclusive-or (see Bit Manipulation). The XOR of the piles is called the nim-sum.
Proof. We check the two labelling rules for the set of positions with nim-sum 0.
- The terminal position is in . All piles are 0, and the XOR of zeros is 0.
- Every move from leaves . A move changes exactly one pile from to some . The new nim-sum is , because only when .
- From every position outside there is a move into . Let the nim-sum be and let be the position of its highest set bit. Some pile has bit set (otherwise bit of the XOR would be 0). Let . In , bit flips from 1 to 0 and no higher bit changes, so : reducing to is a legal move. The new nim-sum is .
So satisfies exactly the rules that define P-positions, and by induction on the number of stones it is the set of P-positions.
Trace: piles 3, 4, 5.
| Pile | Binary (bits 2 1 0) |
|---|---|
| 3 | 0 1 1 |
| 4 | 1 0 0 |
| 5 | 1 0 1 |
| XOR | 0 1 0 = 2 |
The nim-sum is 2, so the first player wins. The highest set bit of 2 is bit 1. Only the pile 3 has bit 1 set, so the winning move is : take 2 stones from the pile of 3. The new position has . ✓ Piles 4 and 5 have bit 1 clear, so and are not legal.
Sometimes several moves win. For piles the nim-sum is 1, every pile has bit 0 set, and all three moves , , win.
Brute-force check. Our code computes the win/lose table of three-pile Nim directly (memoised search over all positions with piles up to 7) and confirms Bouton's rule on every one of the 120 sorted positions; an earlier check covered all ordered positions with piles up to 5.
Why XOR and not addition?
Think of each pile as a sum of distinct powers of two (its binary digits). The XOR is 0 exactly when every power of two appears an even number of times across the piles. The second player can then mirror: whatever power-of-two "pairs" the first player breaks, the second player re-pairs. The proof above is the precise form of that intuition.
2. Mex and Grundy values
The mex (minimum excludant) of a set of non-negative integers is the smallest non-negative integer not in it:
The Grundy value (or nimber, or SG value) of a position in an impartial game is defined recursively:
Terminal positions have .
Two properties follow straight from the definition:
- iff is a P-position. If , no option has value 0 (0 is missing from the set), so every move goes to a position with . If , then 0 is in the set, so some move reaches . These are the P/N rules with "" playing the role of "P".
- From a position of value , you can move to a position of every value (that is what "mex" means), and you cannot move to a position of value itself. You may be able to move to some larger values.
Property 2 says a position with Grundy value behaves like a Nim pile of size , which can be reduced to any smaller size. The extra moves to larger values do not help: if you move up, the opponent can move straight back down to . That observation is the heart of the next theorem.
3. The Sprague–Grundy theorem
The sum of games. Given games and , the sum is played by moving, on each turn, in exactly one of the components. It ends when no component has a move.
Theorem (Sprague 1935, Grundy 1939).
- Every position of an impartial normal-play game is equivalent to a single Nim pile of size .
- The Grundy value of a sum is the XOR of the components' values: .
So the sum is a P-position iff . Bouton's theorem is the special case where every component is a Nim pile with .
Proof of part 2. Let , and . We show that the set of values reachable from contains every and does not contain ; then its mex is . Induction on the total game size lets us assume the formula for all positions reachable from .
- is not reachable. A move goes to or . Say ; it has (a position cannot reach its own value), so . Same for .
- Every is reachable. Let and let be the highest set bit of . Because , bit is 1 in and 0 in . Since bit of is 1, it is 1 in exactly one of , say . Then (bit cleared, higher bits unchanged), so by property 2 there is a move with . The new sum has value .
This is Bouton's step 3 again, applied to Grundy values instead of pile sizes. Part 1 then follows: a single game with value and a Nim pile of size have the same value, so adding either to any third game gives the same outcome.
flowchart LR
G1["Game 1<br/>position p1"] -->|"Grundy DP"| V1["g(p1)"]
G2["Game 2<br/>position p2"] -->|"Grundy DP"| V2["g(p2)"]
G3["Game 3<br/>position p3"] -->|"Grundy DP"| V3["g(p3)"]
V1 --> X["XOR"]
V2 --> X
V3 --> X
X -->|"0"| L["Player to move loses"]
X -->|"not 0"| W["Player to move wins:<br/>move one game to g XOR total"]
The practical effect is enormous. Three components with 1,000 positions each have combined positions, but only Grundy values to compute.
4. Subtraction games: computing Grundy values
A subtraction game is played on one pile: a move removes exactly stones for some , if the pile has at least that many. Nim is the subtraction game with .
Take . The Grundy table is a one-dimensional DP: .
| moves to | values of options | ||
|---|---|---|---|
| 0 | — | {} | 0 |
| 1 | — | {} | 0 |
| 2 | 0 | {0} | 1 |
| 3 | 1 | {0} | 1 |
| 4 | 2 | {1} | 0 |
| 5 | 3, 0 | {1, 0} | 2 |
| 6 | 4, 1, 0 | {0} | 1 |
| 7 | 5, 2, 1 | {2, 1, 0} | 3 |
| 8 | 6, 3, 2 | {1} | 0 |
| 9 | 7, 4, 3 | {3, 0, 1} | 2 |
| 10 | 8, 5, 4 | {0, 2} | 1 |
| 11 | 9, 6, 5 | {2, 1} | 0 |
Continuing (the implementation prints it):
n: 0 1 2 3 4 5 6 7 8 9 10 | 11 12 13 14 15 16 17 18 19 20 21
g: 0 0 1 1 0 2 1 3 0 2 1 | 0 0 1 1 0 2 1 3 0 2 1
The sequence repeats with period 11.
A sum of three piles. In , piles have values , and : the player to move loses. Piles have values with XOR : a win. To find the move, look for a pile whose value can be changed to : pile 4 has , target 1, and has . Take 2 from the pile of 4, leaving with values . The implementation finds this move and confirms the XOR rule against a brute-force search over all 455 three-pile positions with piles up to 12.
Periodicity. With a finite move set, depends only on the previous values, and each value is at most (a mex of at most numbers). So there are finitely many possible "windows", and by the pigeonhole principle the sequence must eventually repeat. Some examples, computed to :
| pre-period, period | ||
|---|---|---|
| {1, 2, 3} | 0 1 2 3 0 1 2 3 … () | 0, 4 |
| {1, 2, 4} | 0 1 2 0 1 2 … | 0, 3 |
| {1, 4} | 0 1 0 1 2 0 1 0 1 2 … | 0, 5 |
| {1, 3, 4} | 0 1 0 1 2 3 2 0 … | 0, 7 |
| {2, 3, 5} | 0 0 1 1 2 2 3 0 … | 0, 7 |
| {2, 5, 6} | see above | 0, 11 |
| {2, 4, 7} | 0 0 1 1 2 2 0 3 1 0 2 1 0 2 1 … | 8, 3 |
The last row shows that a pre-period can occur: settles into the pattern only from . To answer queries for , compute until you detect the period (a repeated window of values), then index into it. Game DP shows this for win/lose bits.
5. Splitting games: Grundy's game and Kayles
In a splitting game a move may replace one pile by several piles. The result is a sum, so its Grundy value is an XOR, and the mex runs over XORs.
Grundy's game. A move splits one pile into two non-empty piles of different sizes. Piles of size 1 and 2 cannot be split.
Trace for small :
| splits | XORs | ||
|---|---|---|---|
| 1, 2 | none | {} | 0 |
| 3 | 1+2 | 1 | |
| 4 | 1+3 | 0 | |
| 5 | 1+4, 2+3 | 0, 1 | 2 |
| 6 | 1+5, 2+4 | 2, 0 | 1 |
| 7 | 1+6, 2+5, 3+4 | 1, 2, 1 | 0 |
| 8 | 1+7, 2+6, 3+5 | 0, 1, 3 | 2 |
Computed further: = 0, 0, 0, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 3, 2, 1, 3, 2, 4, 3, 0. The P-positions (value 0) up to 3,000 are 0, 1, 2, 4, 7, 10, 20, 23, 26, 50, 53, 270, 273, 276, 282, 285, 288, 316, 334, 337, 340, 346, 359, 362, 365, 386, 389, 392, 566, 630, 633, 636, 639, 673, 676, 682, 685, 923, 926, 929, 932 and 1222. Extensive computer searches have found no P-position after 1222, and it is conjectured (not proven) that the Grundy sequence is eventually periodic.
Kayles (Dudeney, 1908). A row of bowling pins; a move knocks down one pin or two adjacent pins, which may split the row into two rows. A move removing pin(s) leaves rows of sizes and with or :
The values start Guy and Smith (1956) proved the sequence is periodic with period 12 from onwards; our table to agrees, with the last exception at . Splitting games with rules given by digit codes like Kayles (".77" in the notation of Winning Ways) are called octal games; whether every finite octal game is eventually periodic is a famous open problem.
6. Staircase Nim
Coins sit on the steps of a staircase, numbered (the floor) to . A move takes one or more coins from step and moves them down to step . The player who cannot move loses.
Theorem. The position is a P-position iff the XOR of the coin counts on the odd steps is 0. The even steps do not matter.
Why. Treat the odd steps as Nim piles. Moving coins from an odd step to the even step is exactly removing from a Nim pile. Moving coins from an even step to the odd step adds coins to a pile, but the opponent can immediately move those same coins from step down to step (even), restoring all the odd piles. Such a reversible move can never help the player in a losing position, so the winner plays Nim on the odd steps and answers every even-step move by pushing the same coins one more step. Coins on the floor (step 0, even) are out of the game.
Our brute-force search over every staircase with steps 1–4 holding 0–3 coins each (256 positions) agrees with the odd-step XOR rule. CSES "Stair Game" numbers the floor as step 1, so there it is the even-numbered steps that count.
The same idea solves many disguised games. Moving tokens left on a line toward a wall without passing each other is staircase Nim on the gaps between consecutive tokens; "Poker Nim" (you may also add chips to a pile, a bounded number of times) is plain Nim, because additions are reversible.
7. Misère Nim
Same moves as Nim, but the player who takes the last stone loses.
Rule (Bouton, 1901). Play exactly as in normal Nim until your move would leave only piles of size 0 or 1. At that moment, leave an odd number of 1-piles instead of an even number. Equivalently, the player to move wins misère Nim iff:
- some pile has size at least 2 and the nim-sum is non-zero, or
- every pile has size at most 1 and the nim-sum is 0 (an even number of 1-piles).
Why. First, the endgame: with only 1-piles left, every move removes one pile, so the players simply alternate and the parity of the number of piles decides who takes the last stone. You want to hand over an odd number of 1-piles.
Second, the middle game. Suppose some pile is at least 2 and you play the normal Nim strategy (leave nim-sum 0). A position with nim-sum 0 never has exactly one pile of size : that pile would have a set bit above bit 0 that no other pile could cancel. So whenever your opponent faces nim-sum 0, there are either no big piles (an even number of 1-piles, which loses for them in misère, as we want) or at least two, and their move leaves at least one big pile. Eventually you face a position with exactly one big pile. Now deviate: reduce that pile to 0 or to 1, whichever leaves an odd number of 1-piles. From there the parity argument wins.
Brute force over all three-pile positions with piles up to 5 agrees with the rule. In general misère games are much harder than normal-play games: the Sprague–Grundy theorem fails for misère sums, and Conway and Plambeck's misère quotients are the modern tool. Nim is a rare case with a simple misère answer.
8. Green Hackenbush (optional)
A Hackenbush picture is a graph drawn on the ground. A move deletes one edge, and any part no longer connected to the ground falls away. In Green Hackenbush every edge can be cut by either player, so it is impartial.
- A stalk (a path of edges standing on the ground) is a Nim pile of size : cutting the -th edge from the bottom leaves edges.
- A tree rooted at the ground reduces by the colon principle: branches meeting at a vertex can be replaced by a single stalk whose length is the XOR of the branches' values. Recursively, a rooted tree's value is , where is the value of the subtree hanging from child and the accounts for the edge to it.
Example: a "Y" (one edge from the ground to a fork, then two single-edge branches). The two branches have value , so the fork is worth , and the whole tree is : equivalent to a single edge. We checked the colon principle against a full Grundy search on all 200 rooted trees with at most 7 edges. For graphs with cycles, the fusion principle shrinks cycles to loops; see Winning Ways, chapter 7.
9. Wythoff's game
Two piles. A move removes any positive number of stones from one pile, or the same positive number from both. Normal play. (Equivalently, a chess queen on a board moves toward the corner; whoever reaches the corner wins.)
Theorem (Wythoff, 1907). The P-positions are the pairs and with
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 3 | 4 | 6 | 8 | 9 | 11 | 12 | 14 | 16 | 17 | |
| 0 | 2 | 5 | 7 | 10 | 13 | 15 | 18 | 20 | 23 | 26 | 28 |
A brute-force win/lose search over every pair with both piles below 30 found exactly these twelve P-positions, matching the formula.
Why the golden ratio. Build the P-positions greedily: is the smallest number not used in any earlier pair, and (each pair has a new difference, because two P-positions with the same difference would be one diagonal move apart). Each positive integer appears in exactly one pair, so and split the positive integers. Two Beatty sequences and split the positive integers exactly when (Rayleigh's theorem); combined with that gives .
Wythoff's game is impartial, so its positions also have Grundy values, but unlike Nim they follow no known formula; you can still compute them by DP for sums of Wythoff games.
10. Partisan games and minimax
Now drop impartiality and "last move wins". In chess or checkers the players have different pieces, the result is win/draw/loss or a score, and the game tree is astronomically large: Shannon estimated about possible chess games.
Minimax. Give each terminal position a value from the point of view of the first player, MAX (higher is better for MAX, worse for MIN). Then
This is the same backward induction as P/N labelling, with numbers instead of bits. For games whose positions fit in memory you memoise it (Predict the Winner, Stone Game in Game DP). For chess you cannot, so engines search to a fixed depth and call a heuristic evaluation function at the frontier, as Shannon proposed.
Negamax is the same algorithm written once: value for the player to move . It works because the game is zero-sum.
11. Alpha-beta pruning
Alpha-beta computes the same value as minimax while skipping subtrees that cannot affect it. It carries a window :
- = the best value MAX is already guaranteed elsewhere on the path to the root;
- = the best value MIN is already guaranteed elsewhere.
If, while searching a node, its value is proven to be outside the window, the players will never let play reach it, and the remaining children can be skipped. At a MAX node, once its value reaches (MIN has a better alternative higher up), stop: a beta cut-off. At a MIN node, once its value drops to , stop: an alpha cut-off.
Trace. A binary tree of depth 3; MAX at the root, MIN below, MAX below that; leaves left to right are .
flowchart TD
R["Root MAX = 5"] --> A["A MIN = 5"]
R --> B["B MIN, at most 2"]
A --> A1["A1 MAX = 5"]
A --> A2["A2 MAX, at least 6"]
B --> B1["B1 MAX = 2"]
B --> B2["B2 pruned"]
A1 --> L1["3"]
A1 --> L2["5"]
A2 --> L3["6"]
A2 --> L4["9 pruned"]
B1 --> L5["1"]
B1 --> L6["2"]
B2 --> L7["0 pruned"]
B2 --> L8["-1 pruned"]
style L4 stroke-dasharray: 5 5
style B2 stroke-dasharray: 5 5
style L7 stroke-dasharray: 5 5
style L8 stroke-dasharray: 5 5
| Step | Node | Window on entry | What happens | Result |
|---|---|---|---|---|
| 1 | A1 (MAX) | leaves 3, 5; rises to 5 | A1 = 5 | |
| 2 | A (MIN) | after A1, | ||
| 3 | A2 (MAX) | leaf 6: value , beta cut-off, skip leaf 9 | A2 | |
| 4 | A (MIN) | A = 5 | ||
| 5 | Root (MAX) | |||
| 6 | B1 (MAX) | leaves 1, 2 | B1 = 2 | |
| 7 | B (MIN) | value , alpha cut-off, skip B2 | B | |
| 8 | Root (MAX) | 5 |
Five of the eight leaves are evaluated. In step 3, MIN at A already holds a reply worth 5 (go to A1), so any A2 worth 6 or more will never be chosen and its exact value is irrelevant. In step 7, MAX at the root already holds 5 (go to A), so a B worth at most 2 will never be chosen.
Correctness invariant. For a call with window and true minimax value : if the call returns exactly ; if it returns some value ; if it returns some value . The root is called with , so it returns the exact value. (The version in our code is "fail-soft": the bound it returns may lie beyond the window, which gives callers a tighter bound for free.)
How much does it save? Move ordering is everything. On a 27-leaf tree (branching , depth , leaves 3, 12, 8, 2, 4, 6, 14, 5, 2, 5, 7, 9, 1, 0, 11, 6, 13, 4, 8, 3, 10, 2, 9, 1, 7, 15, 5, value 9):
| Child order | Leaves evaluated (of 27) |
|---|---|
| Best move first at every node | 11 |
| Order as given | 21 |
| Worst move first at every node | 27 (no pruning at all) |
Knuth and Moore (1975) proved that with perfect ordering alpha-beta evaluates exactly
leaves, the minimal tree. For that is , matching the table; for it is 127 of 4,096, and for it is 199 of 10,000 (both confirmed by our search with best-first ordering). Since , perfect ordering lets you search twice as deep in the same time. With random ordering the savings are smaller: on 200 random trees with , , alpha-beta evaluated 21,517 of 48,600 leaves (44%). Asymptotically, with random leaf values the effective branching factor is about (Pearl, 1982).
Real engines therefore spend much of their cleverness on ordering:
- Iterative deepening: search depth 1, 2, 3, …; the best move from depth is tried first at depth . The repeated shallow searches cost little (a geometric series) and supply excellent ordering.
- Transposition table: a hash map from position (via Zobrist hashing) to its last search result and best move. It is memoisation for search, and it also supplies the first move to try.
- Killer moves and the history heuristic: moves that caused cut-offs at the same depth or elsewhere are tried early.
- Captures first, ordered by "most valuable victim, least valuable attacker".
- Narrow windows: principal variation search (PVS, also called NegaScout) searches the first move with a full window and the rest with a null window , re-searching only when a move turns out better. Aspiration windows start the root search with a narrow window around the previous iteration's value.
Two warnings. Alpha-beta prunes only when the evaluation is a deterministic, exact minimax over a tree; with chance nodes (backgammon) you need expectiminimax and much weaker pruning. And depth-limited search has a horizon effect (a disaster just beyond the search depth is invisible), which engines patch with quiescence search: keep searching captures until the position is quiet.
12. Zero-sum matrix games and mixed strategies
So far players moved in turn and saw everything. Now both choose simultaneously. A two-player zero-sum matrix game is a matrix : the row player picks a row , the column player picks a column , and the column player pays the row player (negative means the row player pays).
Pure saddle points. The row player can guarantee (the maximin); the column player can hold the row player to (the minimax). Always maximin ≤ minimax. If they are equal, the entry where they meet is a saddle point and both players should play it. In , row minima are 2 and 1 (maximin 2), column maxima are 4 and 2 (minimax 2): the saddle point is row 1, column 2, value 2.
Matching pennies has no saddle point. Each player shows heads or tails; if they match, Row wins 1; otherwise Column wins 1:
Maximin is , minimax is . Any pure choice can be exploited. The fix is to randomise: a mixed strategy is a probability distribution over rows (or columns).
Von Neumann's minimax theorem (1928). For every matrix game there are mixed strategies (rows) and (columns) and a number , the value, such that guarantees Row an expected payoff of at least against every column strategy, and guarantees Column pays at most against every row strategy:
Solving a 2×2 game without a saddle point. At the optimum each player makes the other indifferent: if Row plays row 1 with probability , Column's two columns must give Row the same expected payoff (otherwise Column would pick the worse one for Row). For with no saddle point:
where is Column's probability of column 1.
Worked example. .
| Step | Computation | Result |
|---|---|---|
| Saddle point? | maximin ; minimax | none, so mix |
| Row indifference | , i.e. | |
| Column indifference | , i.e. | |
| Value | ||
| Check | Row's mix earns against column 1 and against column 2; Column's mix concedes against either row | ✓ |
Row plays row 1 three times in seven and on average wins per round, however Column plays. (A grid search over Row's probability in steps of also peaks at exactly , value .)
Matching pennies by the formula: , value . Rock-paper-scissors with payoffs :
has the uniform strategy for both players and value 0: against the uniform mix, each of Column's three choices earns Row exactly .
Larger games are linear programs. Row maximises subject to for every column , , . Column's problem is the LP dual, and LP duality is the minimax theorem. So zero-sum games are solvable in polynomial time; see Linear Programming.
Nash equilibrium. In a non-zero-sum game the players' interests are not exactly opposed. A Nash equilibrium is a pair of strategies where neither player can gain by changing only their own. Nash (1950) proved one always exists in mixed strategies. The classic example is the Prisoner's Dilemma: each of two suspects can stay silent or confess; whatever the other does, confessing is better for you, so (confess, confess) is the unique equilibrium, even though both staying silent would be better for both. Unlike the zero-sum case, computing a Nash equilibrium of a general two-player game is believed to be hard (it is PPAD-complete: Daskalakis, Goldberg and Papadimitriou 2006; Chen and Deng 2006).
The ladder: brute force → better → optimal
The question: who wins a game of Nim-like piles, each of size at most ?
Rung 1: plain game-tree search
Recursively try every move; a position is winning iff some move reaches a losing one. Without memoisation the same positions are re-explored along every move order, so the cost is exponential in the total number of stones.
Rung 2: DP over combined positions
Memoise on the whole position (sorted pile sizes, since order does not matter). There are about sorted positions, each with up to moves. For , that is 455 positions, fine; for , it is about . This is the Game DP approach, correct for any game but blind to its structure.
Rung 3: Sprague–Grundy decomposition
Compute the Grundy value of a single pile for every size ( for a subtraction game, for a splitting game), then XOR the values. Total : polynomial instead of exponential, because the theorem lets us treat components independently.
Rung 4: closed form
For Nim, , so the answer is the XOR of the sizes in , no table at all. For a subtraction game with a known period, (after any pre-period) answers sizes up to .
| Rung | Time | Memory | Works for |
|---|---|---|---|
| Plain search | exponential | anything, tiny inputs | |
| DP over combined positions | any finite game whose positions fit in memory | ||
| Sprague–Grundy | sums of impartial normal-play games | ||
| Closed form / period | or | Nim, games with known formulas or periods |
For partisan games the ladder is different: plain minimax → alpha-beta ( with good ordering) → alpha-beta plus transposition table and iterative deepening → retrograde analysis or full DP when the state space fits.
Correctness
P/N labelling (Zermelo). By induction on the length of the longest remaining play: terminal positions are P; a position is N iff some move leads to P. Finiteness guarantees the induction terminates, so every position gets exactly one label and the player to move in an N-position has a strategy that always leaves P-positions until the opponent is stuck.
Grundy value iff P. Shown in section 2, by the same induction.
Bouton and Sprague–Grundy. Proved in sections 1 and 3. The key step in both is the same bit trick: if , the highest bit of is set in some component , and .
Staircase Nim. The odd-step XOR is a strategy-stealing argument: moves on odd steps are Nim moves; moves from even steps can be immediately reversed. Formally, the set of positions with odd-step XOR 0 contains the terminal position, every move from either changes one odd pile (XOR becomes non-zero) or adds coins to one odd pile (also non-zero), and from outside a Nim move on the odd piles returns to .
Misère Nim. Case analysis in section 7, checked exhaustively for small positions.
Alpha-beta. By induction on depth, using the invariant in section 11. A cut-off at a MAX node happens only when its value is already , so the true value is and the caller (a MIN node that already has available) will not choose it; the returned bound is enough.
Minimax theorem. Follows from LP duality, or from Brouwer/Kakutani fixed-point theorems for Nash's generalisation. For 2×2 games without a saddle point, the indifference equations have a unique solution with , and it is optimal because any deviation by one player can be punished by a pure response of the other.
Complexity
| Task | Time | Space |
|---|---|---|
| Nim (Bouton) | ||
| Grundy table, subtraction game up to | , or for a sliding window | |
| Grundy table, split-into-two game up to | ||
| Grundy values of a general game graph with positions, moves | (topological order, mex with a small marker array) | |
| Winning move in a sum of games | extra | |
| Minimax, branching , depth | ||
| Alpha-beta, best case | leaves | |
| Alpha-beta, worst case (bad ordering) | ||
| 2×2 matrix game | ||
| zero-sum matrix game | polynomial (LP) |
Mex in practice. A position with options has Grundy value at most , so a boolean array of size (or a bitmask) computes the mex in , faster than a hash set.
Implementation
Grundy values of a subtraction game, nim-sum decision and winning move
The program computes the Grundy table for , decides positions by XOR, finds a winning move, and then brute-forces every three-pile position with piles up to 12 (and plain Nim with piles up to 7) to confirm that the XOR rule agrees with a direct win/lose search. Expected output:
g for S={2,5,6}: 0 0 1 1 0 2 1 3 0 2 1 0 0 1 1 0 2 1 3 0 2 1
piles [4, 7, 9]: nim-sum 1 -> winning move (0, 2)
brute force agrees on 575 positions
(Java and TypeScript print the table and the move as arrays.)
from functools import lru_cache
def grundy_table(moves: list[int], limit: int) -> list[int]:
"""g[n] for a subtraction game: from a pile of n you may remove any s in moves (s <= n)."""
g = [0] * (limit + 1)
for n in range(1, limit + 1):
seen = {g[n - s] for s in moves if s <= n}
m = 0
while m in seen: # mex: smallest value not reachable
m += 1
g[n] = m
return g
def nim_sum(piles: list[int], g: list[int]) -> int:
x = 0
for p in piles:
x ^= g[p]
return x
def winning_move(piles: list[int], moves: list[int], g: list[int]):
"""Return (pile index, amount to remove) that leaves nim-sum 0, or None if losing."""
x = nim_sum(piles, g)
if x == 0:
return None
for i, p in enumerate(piles):
target = g[p] ^ x # this pile must move to Grundy value target
for s in moves:
if s <= p and g[p - s] == target:
return i, s
raise AssertionError("Sprague-Grundy guarantees a move exists")
def brute_force_first_player_wins(piles: tuple[int, ...], moves: list[int]) -> bool:
@lru_cache(maxsize=None)
def win(state: tuple[int, ...]) -> bool:
for i, p in enumerate(state):
for s in moves:
if s <= p:
nxt = tuple(sorted(state[:i] + (p - s,) + state[i + 1:]))
if not win(nxt): # a move to a losing position
return True
return False # no move, or every move lets them win
return win(tuple(sorted(piles)))
def main() -> None:
moves = [2, 5, 6]
g = grundy_table(moves, 30)
print("g for S={2,5,6}:", g[:22])
assert g[:22] == [0, 0, 1, 1, 0, 2, 1, 3, 0, 2, 1, 0, 0, 1, 1, 0, 2, 1, 3, 0, 2, 1]
assert nim_sum([7, 9, 10], g) == 0 # 3 ^ 2 ^ 1 = 0: the player to move loses
assert winning_move([7, 9, 10], moves, g) is None
mv = winning_move([4, 7, 9], moves, g) # 0 ^ 3 ^ 2 = 1: a win
print("piles [4, 7, 9]: nim-sum", nim_sum([4, 7, 9], g), "-> winning move", mv)
assert mv == (0, 2) # 4 -> 2 has g = 1, and 1 ^ 3 ^ 2 = 0
# Brute force over every 3-pile position with piles up to 12.
checked = 0
for a in range(13):
for b in range(a, 13):
for c in range(b, 13):
assert brute_force_first_player_wins((a, b, c), moves) == (nim_sum([a, b, c], g) != 0)
checked += 1
# Plain Nim is the subtraction game where every amount is allowed.
nim_moves = list(range(1, 8))
gn = grundy_table(nim_moves, 7)
assert gn == list(range(8)) # g(n) = n in Nim
for a in range(8):
for b in range(a, 8):
for c in range(b, 8):
assert brute_force_first_player_wins((a, b, c), nim_moves) == ((a ^ b ^ c) != 0)
checked += 1
print("brute force agrees on", checked, "positions")
if __name__ == "__main__":
main()
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Main {
/** g[n] for a subtraction game: from a pile of n you may remove any s in moves (s <= n). */
static int[] grundyTable(int[] moves, int limit) {
int[] g = new int[limit + 1];
for (int n = 1; n <= limit; n++) {
boolean[] seen = new boolean[moves.length + 2]; // mex is at most moves.length
for (int s : moves)
if (s <= n && g[n - s] < seen.length) seen[g[n - s]] = true;
int m = 0;
while (seen[m]) m++; // mex: smallest value not reachable
g[n] = m;
}
return g;
}
static int nimSum(int[] piles, int[] g) {
int x = 0;
for (int p : piles) x ^= g[p];
return x;
}
/** {pile index, amount to remove} leaving nim-sum 0, or null if the position is losing. */
static int[] winningMove(int[] piles, int[] moves, int[] g) {
int x = nimSum(piles, g);
if (x == 0) return null;
for (int i = 0; i < piles.length; i++) {
int target = g[piles[i]] ^ x; // this pile must move to Grundy value target
for (int s : moves)
if (s <= piles[i] && g[piles[i] - s] == target) return new int[] {i, s};
}
throw new AssertionError("Sprague-Grundy guarantees a move exists");
}
static long key(int[] sortedPiles) {
long k = 0;
for (int p : sortedPiles) k = k * 64 + p;
return k;
}
static boolean bruteWin(int[] piles, int[] moves, Map<Long, Boolean> memo) {
int[] state = piles.clone();
Arrays.sort(state);
long k = key(state);
Boolean cached = memo.get(k);
if (cached != null) return cached;
boolean result = false;
outer:
for (int i = 0; i < state.length; i++) {
for (int s : moves) {
if (s <= state[i]) {
int[] next = state.clone();
next[i] -= s;
if (!bruteWin(next, moves, memo)) { result = true; break outer; }
}
}
}
memo.put(k, result);
return result;
}
static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
int[] moves = {2, 5, 6};
int[] g = grundyTable(moves, 30);
System.out.println("g for S={2,5,6}: " + Arrays.toString(Arrays.copyOf(g, 22)));
check(Arrays.equals(Arrays.copyOf(g, 22),
new int[] {0, 0, 1, 1, 0, 2, 1, 3, 0, 2, 1, 0, 0, 1, 1, 0, 2, 1, 3, 0, 2, 1}), "table");
check(nimSum(new int[] {7, 9, 10}, g) == 0, "7 9 10 loses");
check(winningMove(new int[] {7, 9, 10}, moves, g) == null, "no winning move");
int[] mv = winningMove(new int[] {4, 7, 9}, moves, g);
System.out.println("piles [4, 7, 9]: nim-sum " + nimSum(new int[] {4, 7, 9}, g)
+ " -> winning move " + Arrays.toString(mv));
check(mv[0] == 0 && mv[1] == 2, "4 -> 2");
int checked = 0;
Map<Long, Boolean> memo = new HashMap<>();
for (int a = 0; a < 13; a++)
for (int b = a; b < 13; b++)
for (int c = b; c < 13; c++) {
check(bruteWin(new int[] {a, b, c}, moves, memo) == (nimSum(new int[] {a, b, c}, g) != 0), "brute");
checked++;
}
int[] nimMoves = {1, 2, 3, 4, 5, 6, 7};
int[] gn = grundyTable(nimMoves, 7);
for (int n = 0; n <= 7; n++) check(gn[n] == n, "nim g(n) = n");
Map<Long, Boolean> memoNim = new HashMap<>();
for (int a = 0; a < 8; a++)
for (int b = a; b < 8; b++)
for (int c = b; c < 8; c++) {
check(bruteWin(new int[] {a, b, c}, nimMoves, memoNim) == ((a ^ b ^ c) != 0), "nim brute");
checked++;
}
System.out.println("brute force agrees on " + checked + " positions");
}
}
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <map>
#include <set>
#include <utility>
#include <vector>
using std::vector;
// g[n] for a subtraction game: from a pile of n you may remove any s in moves (s <= n).
vector<int> grundyTable(const vector<int>& moves, int limit) {
vector<int> g(limit + 1, 0);
for (int n = 1; n <= limit; n++) {
std::set<int> seen;
for (int s : moves)
if (s <= n) seen.insert(g[n - s]);
int m = 0;
while (seen.count(m)) m++; // mex: smallest value not reachable
g[n] = m;
}
return g;
}
int nimSum(const vector<int>& piles, const vector<int>& g) {
int x = 0;
for (int p : piles) x ^= g[p];
return x;
}
// {pile index, amount to remove} leaving nim-sum 0, or {-1, -1} if the position is losing.
std::pair<int, int> winningMove(const vector<int>& piles, const vector<int>& moves, const vector<int>& g) {
int x = nimSum(piles, g);
if (x == 0) return {-1, -1};
for (int i = 0; i < static_cast<int>(piles.size()); i++) {
int target = g[piles[i]] ^ x; // this pile must move to Grundy value target
for (int s : moves)
if (s <= piles[i] && g[piles[i] - s] == target) return {i, s};
}
assert(false && "Sprague-Grundy guarantees a move exists");
return {-1, -1};
}
bool bruteWin(vector<int> state, const vector<int>& moves, std::map<vector<int>, bool>& memo) {
std::sort(state.begin(), state.end());
auto it = memo.find(state);
if (it != memo.end()) return it->second;
bool result = false;
for (size_t i = 0; i < state.size() && !result; i++)
for (int s : moves)
if (s <= state[i]) {
vector<int> next = state;
next[i] -= s;
if (!bruteWin(next, moves, memo)) { result = true; break; }
}
memo[state] = result;
return result;
}
int main() {
vector<int> moves = {2, 5, 6};
vector<int> g = grundyTable(moves, 30);
std::printf("g for S={2,5,6}:");
for (int n = 0; n < 22; n++) std::printf(" %d", g[n]);
std::printf("\n");
vector<int> expected = {0, 0, 1, 1, 0, 2, 1, 3, 0, 2, 1, 0, 0, 1, 1, 0, 2, 1, 3, 0, 2, 1};
assert(vector<int>(g.begin(), g.begin() + 22) == expected);
assert(nimSum({7, 9, 10}, g) == 0);
assert(winningMove({7, 9, 10}, moves, g).first == -1);
auto mv = winningMove({4, 7, 9}, moves, g);
std::printf("piles [4, 7, 9]: nim-sum %d -> winning move (%d, %d)\n", nimSum({4, 7, 9}, g), mv.first, mv.second);
assert(mv == std::make_pair(0, 2));
int checked = 0;
std::map<vector<int>, bool> memo;
for (int a = 0; a < 13; a++)
for (int b = a; b < 13; b++)
for (int c = b; c < 13; c++) {
assert(bruteWin({a, b, c}, moves, memo) == (nimSum({a, b, c}, g) != 0));
checked++;
}
vector<int> nimMoves = {1, 2, 3, 4, 5, 6, 7};
vector<int> gn = grundyTable(nimMoves, 7);
for (int n = 0; n <= 7; n++) assert(gn[n] == n);
std::map<vector<int>, bool> memoNim;
for (int a = 0; a < 8; a++)
for (int b = a; b < 8; b++)
for (int c = b; c < 8; c++) {
assert(bruteWin({a, b, c}, nimMoves, memoNim) == ((a ^ b ^ c) != 0));
checked++;
}
std::printf("brute force agrees on %d positions\n", checked);
return 0;
}
// g[n] for a subtraction game: from a pile of n you may remove any s in moves (s <= n).
function grundyTable(moves: number[], limit: number): number[] {
const g = new Array<number>(limit + 1).fill(0);
for (let n = 1; n <= limit; n++) {
const seen = new Set<number>();
for (const s of moves) if (s <= n) seen.add(g[n - s]);
let m = 0;
while (seen.has(m)) m++; // mex: smallest value not reachable
g[n] = m;
}
return g;
}
function nimSum(piles: number[], g: number[]): number {
let x = 0;
for (const p of piles) x ^= g[p];
return x;
}
// [pile index, amount to remove] leaving nim-sum 0, or null if the position is losing.
function winningMove(piles: number[], moves: number[], g: number[]): [number, number] | null {
const x = nimSum(piles, g);
if (x === 0) return null;
for (let i = 0; i < piles.length; i++) {
const target = g[piles[i]] ^ x; // this pile must move to Grundy value target
for (const s of moves) {
if (s <= piles[i] && g[piles[i] - s] === target) return [i, s];
}
}
throw new Error("Sprague-Grundy guarantees a move exists");
}
function bruteWin(piles: number[], moves: number[], memo: Map<string, boolean>): boolean {
const state = [...piles].sort((a, b) => a - b);
const key = state.join(",");
const cached = memo.get(key);
if (cached !== undefined) return cached;
let result = false;
for (let i = 0; i < state.length && !result; i++) {
for (const s of moves) {
if (s <= state[i]) {
const next = [...state];
next[i] -= s;
if (!bruteWin(next, moves, memo)) { result = true; break; }
}
}
}
memo.set(key, result);
return result;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error("check failed: " + msg);
}
const moves = [2, 5, 6];
const g = grundyTable(moves, 30);
console.log("g for S={2,5,6}:", g.slice(0, 22).join(" "));
check(g.slice(0, 22).join(",") === "0,0,1,1,0,2,1,3,0,2,1,0,0,1,1,0,2,1,3,0,2,1", "table");
check(nimSum([7, 9, 10], g) === 0, "7 9 10 loses");
check(winningMove([7, 9, 10], moves, g) === null, "no winning move");
const mv = winningMove([4, 7, 9], moves, g);
console.log(`piles [4, 7, 9]: nim-sum ${nimSum([4, 7, 9], g)} -> winning move ${JSON.stringify(mv)}`);
check(mv !== null && mv[0] === 0 && mv[1] === 2, "4 -> 2");
let checked = 0;
const memo = new Map<string, boolean>();
for (let a = 0; a < 13; a++)
for (let b = a; b < 13; b++)
for (let c = b; c < 13; c++) {
check(bruteWin([a, b, c], moves, memo) === (nimSum([a, b, c], g) !== 0), "brute");
checked++;
}
const nimMoves = [1, 2, 3, 4, 5, 6, 7];
const gn = grundyTable(nimMoves, 7);
for (let n = 0; n <= 7; n++) check(gn[n] === n, "nim g(n) = n");
const memoNim = new Map<string, boolean>();
for (let a = 0; a < 8; a++)
for (let b = a; b < 8; b++)
for (let c = b; c < 8; c++) {
check(bruteWin([a, b, c], nimMoves, memoNim) === ((a ^ b ^ c) !== 0), "nim brute");
checked++;
}
console.log(`brute force agrees on ${checked} positions`);
Alpha-beta on a game tree, verified against minimax
The tree is complete with branching factor and stored as a flat list of leaves: the children of node (depth, index) are (depth - 1, index * b + k). The program runs the trace example from section 11, the 27-leaf example, and 200 random trees from a shared xorshift32 generator, asserting that alpha-beta always returns the minimax value. All four languages print exactly:
binary depth 3: value 5, minimax leaves 8, alpha-beta leaves 5
ternary depth 3: value 9, minimax leaves 27, alpha-beta leaves 21
200 random trees (b=3, depth 5): 21517 of 48600 leaves evaluated
"""Alpha-beta on a complete game tree stored as a flat list of leaves.
Node (depth, index) has children (depth - 1, index * b + k) for k in 0..b-1;
at depth 0, index is a position in `leaves`. MAX moves at the root.
"""
import math
class Search:
def __init__(self, leaves: list[int], b: int) -> None:
self.leaves = leaves
self.b = b
self.visited = 0 # leaves evaluated
def minimax(self, depth: int, index: int, maximizing: bool) -> int:
if depth == 0:
self.visited += 1
return self.leaves[index]
values = [self.minimax(depth - 1, index * self.b + k, not maximizing) for k in range(self.b)]
return max(values) if maximizing else min(values)
def alphabeta(self, depth: int, index: int, alpha: float, beta: float, maximizing: bool) -> float:
"""Exact value whenever it lies strictly inside (alpha, beta)."""
if depth == 0:
self.visited += 1
return self.leaves[index]
if maximizing:
best = -math.inf
for k in range(self.b):
best = max(best, self.alphabeta(depth - 1, index * self.b + k, alpha, beta, False))
alpha = max(alpha, best)
if alpha >= beta: # MIN above will never let play reach here
break # beta cut-off
return best
best = math.inf
for k in range(self.b):
best = min(best, self.alphabeta(depth - 1, index * self.b + k, alpha, beta, True))
beta = min(beta, best)
if alpha >= beta: # MAX above already has something better
break # alpha cut-off
return best
def solve(leaves: list[int], b: int, depth: int) -> tuple[int, int, int, int]:
plain = Search(leaves, b)
v1 = plain.minimax(depth, 0, True)
pruned = Search(leaves, b)
v2 = pruned.alphabeta(depth, 0, -math.inf, math.inf, True)
return v1, int(v2), plain.visited, pruned.visited
def xorshift32(x: int) -> int:
x ^= (x << 13) & 0xFFFFFFFF
x ^= x >> 17
x ^= (x << 5) & 0xFFFFFFFF
return x
def main() -> None:
small = [3, 5, 6, 9, 1, 2, 0, -1] # binary tree, depth 3
v, va, full, seen = solve(small, 2, 3)
print(f"binary depth 3: value {va}, minimax leaves {full}, alpha-beta leaves {seen}")
assert (v, va, full, seen) == (5, 5, 8, 5)
tree27 = [3, 12, 8, 2, 4, 6, 14, 5, 2, 5, 7, 9, 1, 0, 11, 6, 13, 4, 8, 3, 10, 2, 9, 1, 7, 15, 5]
v, va, full, seen = solve(tree27, 3, 3)
print(f"ternary depth 3: value {va}, minimax leaves {full}, alpha-beta leaves {seen}")
assert (v, va, full, seen) == (9, 9, 27, 21)
# Random trees: alpha-beta must always return the minimax value.
x = 2463534242
total_full = total_seen = 0
for _ in range(200):
leaves = []
for _ in range(3 ** 5):
x = xorshift32(x)
leaves.append(x % 100)
v, va, full, seen = solve(leaves, 3, 5)
assert v == va and seen <= full
total_full += full
total_seen += seen
print(f"200 random trees (b=3, depth 5): {total_seen} of {total_full} leaves evaluated")
if __name__ == "__main__":
main()
public class Main {
/** Complete game tree stored as a flat array of leaves. MAX moves at the root. */
static final class Search {
final int[] leaves;
final int b;
int visited = 0; // leaves evaluated
Search(int[] leaves, int b) { this.leaves = leaves; this.b = b; }
int minimax(int depth, int index, boolean maximizing) {
if (depth == 0) { visited++; return leaves[index]; }
int best = maximizing ? Integer.MIN_VALUE : Integer.MAX_VALUE;
for (int k = 0; k < b; k++) {
int v = minimax(depth - 1, index * b + k, !maximizing);
best = maximizing ? Math.max(best, v) : Math.min(best, v);
}
return best;
}
/** Exact value whenever it lies strictly inside (alpha, beta). */
int alphabeta(int depth, int index, int alpha, int beta, boolean maximizing) {
if (depth == 0) { visited++; return leaves[index]; }
if (maximizing) {
int best = Integer.MIN_VALUE;
for (int k = 0; k < b; k++) {
best = Math.max(best, alphabeta(depth - 1, index * b + k, alpha, beta, false));
alpha = Math.max(alpha, best);
if (alpha >= beta) break; // beta cut-off
}
return best;
}
int best = Integer.MAX_VALUE;
for (int k = 0; k < b; k++) {
best = Math.min(best, alphabeta(depth - 1, index * b + k, alpha, beta, true));
beta = Math.min(beta, best);
if (alpha >= beta) break; // alpha cut-off
}
return best;
}
}
/** {minimax value, alpha-beta value, minimax leaves, alpha-beta leaves}. */
static int[] solve(int[] leaves, int b, int depth) {
Search plain = new Search(leaves, b);
int v1 = plain.minimax(depth, 0, true);
Search pruned = new Search(leaves, b);
int v2 = pruned.alphabeta(depth, 0, Integer.MIN_VALUE, Integer.MAX_VALUE, true);
return new int[] {v1, v2, plain.visited, pruned.visited};
}
static int xorshift32(int x) {
x ^= x << 13;
x ^= x >>> 17;
x ^= x << 5;
return x;
}
static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
int[] r = solve(new int[] {3, 5, 6, 9, 1, 2, 0, -1}, 2, 3);
System.out.printf("binary depth 3: value %d, minimax leaves %d, alpha-beta leaves %d%n", r[1], r[2], r[3]);
check(r[0] == 5 && r[1] == 5 && r[2] == 8 && r[3] == 5, "binary");
int[] tree27 = {3, 12, 8, 2, 4, 6, 14, 5, 2, 5, 7, 9, 1, 0, 11, 6, 13, 4, 8, 3, 10, 2, 9, 1, 7, 15, 5};
r = solve(tree27, 3, 3);
System.out.printf("ternary depth 3: value %d, minimax leaves %d, alpha-beta leaves %d%n", r[1], r[2], r[3]);
check(r[0] == 9 && r[1] == 9 && r[2] == 27 && r[3] == 21, "ternary");
int x = (int) 2463534242L;
long totalFull = 0, totalSeen = 0;
for (int t = 0; t < 200; t++) {
int[] leaves = new int[243];
for (int i = 0; i < 243; i++) {
x = xorshift32(x);
leaves[i] = Integer.remainderUnsigned(x, 100);
}
r = solve(leaves, 3, 5);
check(r[0] == r[1] && r[3] <= r[2], "random tree");
totalFull += r[2];
totalSeen += r[3];
}
System.out.printf("200 random trees (b=3, depth 5): %d of %d leaves evaluated%n", totalSeen, totalFull);
}
}
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cstdio>
#include <vector>
// Complete game tree stored as a flat array of leaves. MAX moves at the root.
struct Search {
const std::vector<int>& leaves;
int b;
int visited = 0; // leaves evaluated
Search(const std::vector<int>& l, int branching) : leaves(l), b(branching) {}
int minimax(int depth, int index, bool maximizing) {
if (depth == 0) { visited++; return leaves[index]; }
int best = maximizing ? INT_MIN : INT_MAX;
for (int k = 0; k < b; k++) {
int v = minimax(depth - 1, index * b + k, !maximizing);
best = maximizing ? std::max(best, v) : std::min(best, v);
}
return best;
}
// Exact value whenever it lies strictly inside (alpha, beta).
int alphabeta(int depth, int index, int alpha, int beta, bool maximizing) {
if (depth == 0) { visited++; return leaves[index]; }
if (maximizing) {
int best = INT_MIN;
for (int k = 0; k < b; k++) {
best = std::max(best, alphabeta(depth - 1, index * b + k, alpha, beta, false));
alpha = std::max(alpha, best);
if (alpha >= beta) break; // beta cut-off
}
return best;
}
int best = INT_MAX;
for (int k = 0; k < b; k++) {
best = std::min(best, alphabeta(depth - 1, index * b + k, alpha, beta, true));
beta = std::min(beta, best);
if (alpha >= beta) break; // alpha cut-off
}
return best;
}
};
struct Result { int value, abValue, fullLeaves, abLeaves; };
Result solve(const std::vector<int>& leaves, int b, int depth) {
Search plain(leaves, b);
int v1 = plain.minimax(depth, 0, true);
Search pruned(leaves, b);
int v2 = pruned.alphabeta(depth, 0, INT_MIN, INT_MAX, true);
return {v1, v2, plain.visited, pruned.visited};
}
uint32_t xorshift32(uint32_t x) {
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return x;
}
int main() {
Result r = solve({3, 5, 6, 9, 1, 2, 0, -1}, 2, 3);
std::printf("binary depth 3: value %d, minimax leaves %d, alpha-beta leaves %d\n", r.abValue, r.fullLeaves, r.abLeaves);
assert(r.value == 5 && r.abValue == 5 && r.fullLeaves == 8 && r.abLeaves == 5);
std::vector<int> tree27 = {3, 12, 8, 2, 4, 6, 14, 5, 2, 5, 7, 9, 1, 0, 11, 6, 13, 4, 8, 3, 10, 2, 9, 1, 7, 15, 5};
r = solve(tree27, 3, 3);
std::printf("ternary depth 3: value %d, minimax leaves %d, alpha-beta leaves %d\n", r.abValue, r.fullLeaves, r.abLeaves);
assert(r.value == 9 && r.abValue == 9 && r.fullLeaves == 27 && r.abLeaves == 21);
uint32_t x = 2463534242u;
long long totalFull = 0, totalSeen = 0;
for (int t = 0; t < 200; t++) {
std::vector<int> leaves(243);
for (int i = 0; i < 243; i++) {
x = xorshift32(x);
leaves[i] = static_cast<int>(x % 100);
}
r = solve(leaves, 3, 5);
assert(r.value == r.abValue && r.abLeaves <= r.fullLeaves);
totalFull += r.fullLeaves;
totalSeen += r.abLeaves;
}
std::printf("200 random trees (b=3, depth 5): %lld of %lld leaves evaluated\n", totalSeen, totalFull);
return 0;
}
// Complete game tree stored as a flat array of leaves. MAX moves at the root.
class Search {
visited = 0; // leaves evaluated
private leaves: number[];
private b: number;
constructor(leaves: number[], b: number) {
this.leaves = leaves;
this.b = b;
}
minimax(depth: number, index: number, maximizing: boolean): number {
if (depth === 0) { this.visited++; return this.leaves[index]; }
let best = maximizing ? -Infinity : Infinity;
for (let k = 0; k < this.b; k++) {
const v = this.minimax(depth - 1, index * this.b + k, !maximizing);
best = maximizing ? Math.max(best, v) : Math.min(best, v);
}
return best;
}
// Exact value whenever it lies strictly inside (alpha, beta).
alphabeta(depth: number, index: number, alpha: number, beta: number, maximizing: boolean): number {
if (depth === 0) { this.visited++; return this.leaves[index]; }
if (maximizing) {
let best = -Infinity;
for (let k = 0; k < this.b; k++) {
best = Math.max(best, this.alphabeta(depth - 1, index * this.b + k, alpha, beta, false));
alpha = Math.max(alpha, best);
if (alpha >= beta) break; // beta cut-off
}
return best;
}
let best = Infinity;
for (let k = 0; k < this.b; k++) {
best = Math.min(best, this.alphabeta(depth - 1, index * this.b + k, alpha, beta, true));
beta = Math.min(beta, best);
if (alpha >= beta) break; // alpha cut-off
}
return best;
}
}
// [minimax value, alpha-beta value, minimax leaves, alpha-beta leaves]
function solve(leaves: number[], b: number, depth: number): number[] {
const plain = new Search(leaves, b);
const v1 = plain.minimax(depth, 0, true);
const pruned = new Search(leaves, b);
const v2 = pruned.alphabeta(depth, 0, -Infinity, Infinity, true);
return [v1, v2, plain.visited, pruned.visited];
}
function xorshift32(x: number): number {
x ^= x << 13;
x ^= x >>> 17;
x ^= x << 5;
return x >>> 0;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error("check failed: " + msg);
}
let r = solve([3, 5, 6, 9, 1, 2, 0, -1], 2, 3);
console.log(`binary depth 3: value ${r[1]}, minimax leaves ${r[2]}, alpha-beta leaves ${r[3]}`);
check(r.join(",") === "5,5,8,5", "binary");
const tree27 = [3, 12, 8, 2, 4, 6, 14, 5, 2, 5, 7, 9, 1, 0, 11, 6, 13, 4, 8, 3, 10, 2, 9, 1, 7, 15, 5];
r = solve(tree27, 3, 3);
console.log(`ternary depth 3: value ${r[1]}, minimax leaves ${r[2]}, alpha-beta leaves ${r[3]}`);
check(r.join(",") === "9,9,27,21", "ternary");
let x = 2463534242;
let totalFull = 0;
let totalSeen = 0;
for (let t = 0; t < 200; t++) {
const leaves: number[] = [];
for (let i = 0; i < 243; i++) {
x = xorshift32(x);
leaves.push(x % 100);
}
r = solve(leaves, 3, 5);
check(r[0] === r[1] && r[3] <= r[2], "random tree");
totalFull += r[2];
totalSeen += r[3];
}
console.log(`200 random trees (b=3, depth 5): ${totalSeen} of ${totalFull} leaves evaluated`);
Implementation notes:
- Sentinels. Java and C++ use
Integer.MIN_VALUE/INT_MINas . That is safe here because we never negate them; in a negamax implementation,INT_MINoverflows, so use a large finite bound such as instead. - Fail-soft versus fail-hard. Our search returns
best, which can lie outside . A fail-hard version clamps the result to the window. Both give the exact root value; fail-soft gives better bounds to transposition tables. - Sorted state keys in the brute force exploit that pile order does not matter, which shrinks the memo by a factor of up to .
Real-world uses
- Chess engines. Stockfish, the strongest open-source engine, is an alpha-beta searcher: principal variation search with iterative deepening, aspiration windows, a transposition table, null-move pruning, late-move reductions and quiescence search. Since Stockfish 12 (2020) its evaluation function is an efficiently updatable neural network (NNUE). IBM's Deep Blue, which beat Kasparov in 1997, was alpha-beta on custom hardware searching on the order of 100–200 million positions per second (Campbell, Hoane and Hsu, 2002).
- AlphaZero and Monte Carlo tree search. AlphaZero (Silver et al., Science, 2018) replaced alpha-beta with MCTS guided by a neural network that proposes moves and evaluates positions, learned entirely from self-play. It searched tens of thousands of positions per second against Stockfish's tens of millions (80 thousand versus 70 million in the 2017 preprint), compensating with a far better evaluation. Leela Chess Zero is the open-source descendant; Stockfish's NNUE and Leela's MCTS now compete at the top.
- Solved games and endgame tablebases. Checkers was weakly solved as a draw by the Chinook project (Schaeffer et al., 2007) using alpha-beta proofs plus retrograde-computed databases; chess endgames with up to 7 pieces are solved by retrograde analysis (Syzygy/Lomonosov tablebases). See Game DP.
- Poker. Imperfect-information games need mixed strategies. Libratus (2017) and Pluribus (2019, six-player) beat top professionals using counterfactual regret minimisation, an iterative method that converges to an equilibrium (Brown and Sandholm, Science, 2018 and 2019).
- Auctions and mechanism design. Designing the rules of a game so that self-interested players produce a good outcome. In a Vickrey (second-price sealed-bid) auction, bidding your true value is a dominant strategy (Vickrey, 1961). Search ads have long been sold with the generalized second-price auction (Edelman, Ostrovsky and Schwarz, 2007; Varian, 2007), and the U.S. FCC has auctioned radio spectrum with simultaneous multiple-round auctions since 1994, a design for which Milgrom and Wilson shared the 2020 economics Nobel.
- Security games. Randomised patrol schedules computed as Stackelberg equilibria were deployed at Los Angeles International Airport (the ARMOR system, Pita et al., 2008) and by the U.S. Coast Guard; mixed strategies make patrols unpredictable to an attacker who observes them.
- Networks and routing. Selfish routing can make everyone worse off (Braess's paradox); Roughgarden and Tardos (2002) proved that with linear latency functions selfish routing costs at most of the optimum (the "price of anarchy").
- Go endgames. Late in a Go game the board splits into independent regions, and Berlekamp and Wolfe (Mathematical Go, 1994) used combinatorial game sums (the partisan generalisation of Sprague–Grundy) to play endgames perfectly; on specially constructed endgame positions, their method found winning lines that professional players missed.
Pitfalls & edge cases
- Adding instead of XOR-ing Grundy values, or XOR-ing pile sizes in a game that is not Nim. XOR the Grundy values; only in Nim are they the sizes.
- Misère versus normal. "The player who takes the last stone loses" changes everything. Check the statement.
- Applying Sprague–Grundy to partisan games. If the players have different moves (one may only take from red piles), Grundy values are meaningless; you need minimax or Conway's partisan theory.
- Moves that touch several components (take from all piles at once, as in CSES "Another Game") break the sum structure. Find the invariant directly or brute-force small cases.
- Cycles. Sprague–Grundy as stated needs finite play. Games with repeated positions need retrograde analysis or the generalised (loopy) Grundy theory of Smith and Fraenkel.
- Mex bound. Allocating a fixed-size "seen" array smaller than the number of options + 1 silently computes a wrong mex.
- Splitting into two identical piles has Grundy value . That is correct, not a bug, and it is why Grundy's game forbids equal splits (otherwise every even pile would be a trivial win).
- Alpha-beta with a non-deterministic or stateful evaluation. If evaluation depends on search order (side effects, random noise), pruning decisions are not reproducible and the "same value as minimax" guarantee is lost.
- Negamax sign errors at the window: the child's window is , not .
- Mixed strategies are about expectation. Playing the optimal mix can lose a particular round; the guarantee is on average, and against an exploitable opponent a non-equilibrium strategy may earn more.
Variations
- Partisan combinatorial games and surreal numbers. Conway's On Numbers and Games (1976) gives every partisan game a value; some are numbers (Blue Hackenbush), others "hot" games like Go endgames. Red-Blue Hackenbush is the standard introduction.
- Moore's Nim. Remove from up to piles at once: P-positions are those where, written in binary, every bit column sum is divisible by .
- Nim with a pass, Lasker's Nim, Fibonacci Nim, Euclid's game. Each has a neat closed form; Fibonacci Nim's strategy uses the Zeckendorf representation.
- Green Hackenbush on graphs via the fusion principle; Red-Blue-Green Hackenbush mixes partisan and impartial edges.
- Loopy games (positions can repeat): values include "loony" and "draw"; computed by retrograde analysis.
- Expectiminimax for games with dice, with *-minimax pruning (Ballard, 1983).
- Monte Carlo tree search with UCT (Kocsis and Szepesvári, 2006): grows the tree toward promising moves using random playouts and confidence bounds; no evaluation function needed.
- Extensive-form games with imperfect information (poker): solved by counterfactual regret minimisation or sequence-form LPs.
- Correlated equilibria and evolutionary game theory; repeated games (tit-for-tat in the iterated Prisoner's Dilemma).
Practice ladder
Each problem is described in my own words; follow the link for the full statement.
1. Nim Game (LeetCode 292) — One pile, take 1 to 3, last stone wins. Teaches P-positions (multiples of 4).
Hint
return n % 4 != 0. The Grundy value of the subtraction game is .
2. Nim Game I (CSES 1730) — Plain multi-pile Nim, many test cases. Teaches Bouton's theorem.
Solution
def nim_game_1(piles: list[int]) -> str:
x = 0
for p in piles:
x ^= p
return "first" if x else "second"
assert nim_game_1([5, 7, 3]) == "first"
assert nim_game_1([1, 2, 3]) == "second"
3. Nim Game II (CSES 1098) — Nim where each move removes 1, 2 or 3 sticks from one heap. Teaches Sprague–Grundy with a subtraction game.
Solution
Each heap is the subtraction game with . XOR those.
def nim_game_2(piles: list[int]) -> str:
x = 0
for p in piles:
x ^= p % 4
return "first" if x else "second"
assert nim_game_2([4, 8]) == "second"
assert nim_game_2([5, 4]) == "first"
4. Nimble Game (HackerRank) — Coins on numbered squares; a move slides one coin from square to any lower square. Teaches seeing a Nim pile in disguise.
Hint
A coin on square is a Nim pile of size (it can move to any smaller index). Coins on the same square cancel in pairs, so XOR the indices of squares with an odd number of coins. Checked against brute force for small boards.
5. Poker Nim (HackerRank) — Nim where a player may also add chips to a pile, a limited number of times. Teaches reversible moves.
Hint
Adding chips can always be undone by the opponent removing them, and the bounded number of additions keeps the game finite. The answer is plain Nim on the pile sizes.
6. Misère Nim (HackerRank) — Nim where taking the last stone loses. Teaches the misère exception.
Solution
def misere_nim(piles: list[int]) -> str:
x = 0
for p in piles:
x ^= p
if max(piles) == 1: # only 1-piles: parity decides
return "First" if x == 0 else "Second"
return "First" if x != 0 else "Second"
assert misere_nim([1, 1]) == "First" # take one, opponent must take the last
assert misere_nim([1]) == "Second"
assert misere_nim([2, 1, 3]) == "Second" # nim-sum 0 with a big pile
7. Stair Game (CSES 1099) — Balls on stairs ; a move takes balls from stair down to stair . Teaches Staircase Nim.
Solution
Stair 1 is the floor here, so the stairs at odd distance from it are the even-numbered ones.
def stair_game(balls: list[int]) -> str: # balls[0] is stair 1
x = 0
for k in range(2, len(balls) + 1, 2):
x ^= balls[k - 1]
return "first" if x else "second"
assert stair_game([0, 2, 1]) == "first"
assert stair_game([3, 1, 4, 1]) == "second" # stairs 2 and 4 hold 1 and 1: XOR 0
(Checked against brute force over every 5-stair position with 0–2 balls per stair.)
8. Stone Game IV (LeetCode 1510) — One pile; a move removes a positive square number of stones. Teaches a subtraction game with a growing move set (no period to exploit).
Hint
win[i] = any(not win[i - k*k] for k with k*k <= i). for .
9. Another Game (CSES 2208) — Heaps of coins; a move takes one coin from each heap in any non-empty set of heaps. Teaches finding the invariant when the sum structure breaks.
Hint
The first player wins iff some heap is odd. From an all-even position every move makes some heap odd; from a position with odd heaps, take one coin from each odd heap to make all even. (Brute force on three heaps up to 4 agrees.)
10. Grundy's Game (CSES 2207) — One heap of up to coins; a move splits a heap into two unequal heaps. Teaches splitting games and using computed data.
Hint
Compute with the split recurrence for up to about 2,000. The last P-position found by computer search is 1222, so for larger the first player wins. This relies on a computed fact (published computations go far beyond without finding another zero), not on a proof.
11. Interval Game 2 (AtCoder ABC 206 F) — Players alternately choose one of the given half-open intervals that does not overlap any chosen interval. Teaches Grundy values over sub-intervals (an interval DP).
Hint
Choosing inside the free segment splits it into and , two independent games. So over intervals inside . Coordinates are small, so an memoised DP fits.
Common mistakes & interview follow-ups
"Who wins Nim with piles 3, 4, 5, and how?" First player: XOR is 2; take 2 from the 3-pile.
"Why XOR?" Sketch the three-step proof: terminal is 0; any move from 0 makes it non-zero; from non-zero, the highest bit gives a move back to 0.
"Several different games played side by side?" Sprague–Grundy: compute each game's Grundy value by mex DP, XOR them.
" up to ?" Subtraction games with finite are eventually periodic: compute until a window of values repeats.
"What if the last mover loses?" Misère; for Nim, normal strategy until only 1-piles remain, then leave an odd number of them.
"How does a chess engine decide?" Depth-limited minimax with alpha-beta, iterative deepening, transposition tables, quiescence search, and an evaluation function (NNUE in Stockfish). AlphaZero instead uses MCTS with a neural network.
"How much does alpha-beta save?" With perfect ordering leaves, about the square root of the full tree, so double the depth. With bad ordering, nothing.
"Rock-paper-scissors: best strategy?" Uniform mix, value 0; any predictable deviation can be exploited.
Mistakes interviewers watch for: XOR-ing sizes instead of Grundy values; forgetting that mex of the empty set is 0; treating a partisan game with Grundy numbers; swapping and in negamax; claiming alpha-beta changes the result (it never does).
Quick quiz
1. ?
Answer
2. Nim piles 1, 2, 3. Who wins?
Answer
: the player to move loses.
3. In the subtraction game , piles 5 and 9. Who wins?
Answer
: the player to move loses.
4. Grundy's game: why is a pile of 7 a P-position?
Answer
Its splits are 1+6, 2+5 and 3+4 with XORs , , . The set does not contain 0, so .
5. Is a P-position of Wythoff's game?
Answer
Yes: , , .
6. With perfect move ordering, how many leaves does alpha-beta evaluate on a tree with , ?
Answer
of 10,000.
7. Solve as a zero-sum game.
Answer
No saddle point (maximin 0, minimax 1). , , value .
Further reading / sources
- Elwyn Berlekamp, John H. Conway and Richard K. Guy, Winning Ways for Your Mathematical Plays (2nd ed., A K Peters, 2001–2004) — Nim, Sprague–Grundy, octal games, Kayles, Hackenbush, misère play.
- Charles L. Bouton, "Nim, a game with a complete mathematical theory", Annals of Mathematics 3, 1901.
- R. P. Sprague, "Über mathematische Kampfspiele", Tôhoku Mathematical Journal 41, 1935; P. M. Grundy, "Mathematics and games", Eureka 2, 1939.
- W. A. Wythoff, "A modification of the game of Nim", Nieuw Archief voor Wiskunde 7, 1907.
- R. K. Guy and C. A. B. Smith, "The G-values of various games", Proc. Cambridge Philosophical Society 52, 1956 (Kayles periodicity).
- Thomas S. Ferguson, Game Theory (UCLA lecture notes; Part I, impartial combinatorial games) — the clearest free introduction to P/N positions, Sprague–Grundy and matrix games.
- Donald E. Knuth and Ronald W. Moore, "An analysis of alpha-beta pruning", Artificial Intelligence 6(4), 1975.
- Judea Pearl, "The solution for the branching factor of the alpha-beta pruning algorithm and its optimality", Communications of the ACM 25(8), 1982.
- Claude E. Shannon, "Programming a Computer for Playing Chess", Philosophical Magazine 41, 1950.
- Murray Campbell, A. Joseph Hoane Jr. and Feng-hsiung Hsu, "Deep Blue", Artificial Intelligence 134, 2002.
- David Silver et al., "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play", Science 362, 2018.
- Jonathan Schaeffer et al., "Checkers is solved", Science 317, 2007.
- John von Neumann, "Zur Theorie der Gesellschaftsspiele", Mathematische Annalen 100, 1928; John F. Nash, "Equilibrium points in n-person games", PNAS 36, 1950.
- Noam Nisan, Tim Roughgarden, Éva Tardos and Vijay Vazirani (eds.), Algorithmic Game Theory (Cambridge, 2007) — equilibria, complexity, mechanism design, price of anarchy.
- Stockfish documentation and source, stockfishchess.org and the Chess Programming Wiki (alpha-beta, PVS, move ordering, NNUE).
- cp-algorithms, Sprague-Grundy theorem. Nim and Games on arbitrary graphs.
Lessons: module — Math for Algorithms · previous — Computational Geometry · next — Math Capstone · course — DSA: Zero to Mastery.
Related Archon pages: Game DP · Bit Manipulation · Interval DP · Backtracking & Recursion · Probability & Expected Value for Algorithms · Randomized Algorithms · Topological Sort.