vault

Game Theory DP

49 min read

Game Theory DP

Game theory dynamic programming is the family of DP algorithms for two-player zero-sum games with perfect information, where the state encodes the game position plus whose turn it is, and the recurrence is a minimax alternation: at your turn you maximize your reward; at the opponent’s turn the opponent minimizes your reward (equivalently, maximizes their own reward, which is the negation in a zero-sum game). The classical worked examples are Nim (closed-form solution via XOR; Bouton 1901), Stone Game (LC 877; LC 1140; LC 1406), and Predict the Winner (LC 486). The deepest theoretical result is the Sprague-Grundy theorem (Sprague 1936, Grundy 1939), which says that every impartial game — one where both players have the same moves available, with the player who cannot move losing — is equivalent to a Nim heap of some size, the Grundy number (or nimber), and that the Grundy number of a sum of independent games is the XOR of their individual Grundy numbers. This factorization theorem reduces analysis of complex impartial games to evaluating each independent component separately. Game-theory DP is structurally identical to deterministic DP except the recurrence alternates between max and min — once you internalize this, problems that look intricate (“two players play optimally; who wins?”) collapse to template DPs. The key recognition signal: “two players take turns… both play optimally… determine the winner / score difference / outcome.” For interviews, the canonical templates are: (1) score-difference DP for zero-sum scoring games, (2) win/lose DP for impartial combinatorial games, and (3) minimax with alpha-beta pruning for the search-tree perspective when DP doesn’t fit naturally.

Relationship to Backward Induction — cross-linked, deliberately not merged

Backward Induction covers the same post-order tree traversal from the game theory side, and the two notes were read against each other rather than assumed distinct. The traversal is shared; almost nothing else is.

This note (Game Theory DP)Backward Induction
Payoffstwo-player zero-sum: one scalar, so the operator alternates max/mingeneral-sum payoff vector per node; every node is a max, on a different coordinate; no min anywhere
Ownsthe recurrence, state design, memoisation, complexity, pruning, and impartial-game theory (Nim-values, Sprague–Grundy) — none of which appears in the siblingthe solution concept: what the traversal presupposes about the agents, and what happens when those presuppositions are false
Canonical exampleStone Game, Nim, tic-tac-toethe centipede game, Selten’s chain store, the finitely repeated Prisoner’s Dilemma
Failure mode it studieswrong state, missing sign flip, Sprague–Grundy applied to a partisan gamerational play predicted at nodes reachable only through irrational play; lab subjects who do not take at node 1

The concrete test: in the centipede game both players strictly prefer passing to the backward-induction outcome, so there is no scalar on which to alternate max and min, and nothing in this note applies to it. Conversely, Backward Induction contains no Nim-values, no mex, no complexity analysis and no state-space design — the material that occupies §4, §6, §7 and §10 here. Read this note for the algorithm, that one for the concept. See also Extensive-Form Games and Subgame Perfect Equilibrium.

1. Intuition — Two Players, Alternating, Both Optimal

Single-player DP optimizes from one perspective: you pick the action that maximizes your outcome. Two-player DP has two perspectives that alternate: at your turn you maximize your outcome; at the opponent’s turn the opponent (also playing optimally) maximizes their outcome — which, in a zero-sum game where the players’ outcomes sum to a constant, is the same as minimizing your outcome.

The recurrence pattern, generically:

value(state, my_turn) =
    max over actions a of: reward(state, a) + value(next_state(state, a), not my_turn)   # if my_turn
    min over actions a of: reward(state, a) + value(next_state(state, a), not my_turn)   # if opponent's turn

This is the minimax recurrence. It is conventionally traced to von Neumann’s 1928 Zur Theorie der Gesellschaftsspiele and the minimax theorem, but that lineage needs care — the minimax theorem is a statement about mixed strategies in simultaneous-move games, and the recurrence above needs neither. §1.1 disentangles the two, and §1.2 does the same for the “Zermelo’s theorem” attribution, because both are stated wrongly in most write-ups of this topic.

A real-world analogy: imagine you and an opponent are alternating chess moves, and you want to compute the outcome of perfect play. At your turn, you survey all your legal moves and pick the one leading to the best outcome — assuming the opponent will respond optimally. The opponent’s optimal response is computed the same way: surveying their moves and picking the one leading to the best outcome for them (worst for you). Recursing all the way to terminal positions (checkmate, stalemate, draw) gives the game’s “true value” under perfect play.

The DP version: cache value(state, turn) so we don’t re-explore the same position from two different paths. For games with relatively small state spaces — Nim with a few heaps, Stone Game on n ≤ 100 stones, Connect Four (~10^13 states; tractable with effort) — the DP is feasible. For chess it is not — the current statistical estimate is (4.82 ± 0.03) × 10⁴⁴ legal positions (Tromp, ChessPositionRanking; see §12) — and Monte Carlo Tree Search plus neural nets (AlphaZero) take over.

The key intellectual move: alternation between max and min reflects the fact that the players have opposing objectives. Both are optimizing — one upward, one downward — and the recurrence threads through their alternating choices.

1.1 The Minimax Theorem, Stated Correctly

The parenthetical above needs unpacking, because the sentence “the minimax theorem says the maximin equals the minimax of the payoff matrix” is false as stated for pure strategies and is the single most common error made when importing game-theory vocabulary into an algorithms discussion.

Take Matching Pennies: each player independently shows heads or tails, and the row player wins +1 if the pennies agree and −1 otherwise. The payoff matrix, rows for the row player, is A = ( +1 −1 / −1 +1 ). Its pure maximin is max_i min_j A[i][j] = −1 (whichever side you commit to, the opponent beats it); its pure minimax is min_j max_i A[i][j] = +1. They are not equal, and no amount of optimal play makes them equal, because there is no optimal pure strategy — the game has no pure Nash equilibrium at all. See Matching Pennies and Games Without Pure Equilibria.

Von Neumann’s 1928 minimax theorem is a statement about mixed strategies: allowing each player to randomise over their rows or columns, max_p min_q pAq = min_q max_p pAq, and that common number is the value of the game. The modern algorithmic proof is a pair of dual linear programs — the row player’s “maximum safe value, the maximum value he or she can guarantee to win by playing a mixed strategy p that will be known to the column player”, and the column player’s minimum safe value — whose optima coincide and form a Nash equilibrium (Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory, Ch. 1, Theorem 1.11). The same book gives a second, entirely different proof in Chapter 4, from the existence of no-regret learning algorithms: “we can use the existence of external regret minimization algorithms to prove the minimax theorem of two-player zero-sum games.” See Zero-Sum Games and the Minimax Theorem and Mixed Strategies.

So why does everything in this note get away with pure max and min? Because none of it is a normal-form game. Every problem here is an extensive-form game of perfect information with alternating moves: the players do not choose simultaneously, and the mover always knows the entire history. In that setting a pure-strategy value exists for a far more elementary reason than von Neumann’s theorem — the game tree is finite, so induct from the leaves — and randomisation buys nothing, because a player who can see the whole position has no secret to protect. Matching Pennies has no pure value precisely because the moves are simultaneous; make them sequential and the second mover wins outright.

That is the boundary of this note’s technique, and it is worth stating as a rule: max/min alternation on a scalar is valid exactly when the game is (i) two-player, (ii) zero-sum, and (iii) perfect-information with alternating moves. Drop (ii) and you need payoff vectors and there is no min anywhere — see Backward Induction. Drop (iii) and you need mixed strategies, belief states, and eventually Counterfactual Regret Minimization.

1.2 What Zermelo Actually Proved

Almost every textbook — and an earlier revision of this note’s source list — attributes the trichotomy “every finite two-player perfect-information game is a win for White, a win for Black, or a draw”, and often the backward-induction method itself, to Ernst Zermelo’s 1913 paper Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. Schwalbe and Walker went back to the German original and found that most modern statements of “Zermelo’s theorem” are wrong, including the attribution of the method. Their finding, stated flatly: “Note that in Zermelo’s paper, contrary to what is often claimed, no use is made of backward induction. The first time a proof by backward induction is used seems to be in von Neumann and Morgenstern (1953). The first mention of Zermelo in connection with induction was in Kuhn (1953).” (Schwalbe & Walker, Zermelo and the Early History of Game Theory — the copy fetched here is the 15-page version that includes their full English translation of Zermelo’s paper, which was read directly for this section.)

What Zermelo did do, in his own words as translated:

  • He worked set-theoretically, not inductively. For a position q he defines the set Q of all “endgames” (play sequences) starting at q, then a subset U(q) ⊆ Q of continuations by which White forces a win regardless of Black, and a subset V(q) by which White at least postpones loss indefinitely. His conclusion: “If U(q) is different from 0, then White can force a win… If U(q) = 0 but V(q) ≠ 0, then White can at least force a draw… However, if V(q) vanishes also and the opponent plays correctly, White can postpone the loss up until the σth move at best.”
  • He explicitly allowed infinite plays. “Such a possible endgame q can find its natural end either in a ‘checkmate’ or in a ‘stalemate’ position but could also — at least theoretically — go on forever in which case the game would without doubt have to be called a draw.” The restriction to finite games is von Neumann and Morgenstern’s.
  • He did not prove that the first mover has an advantage, and the popular “in a finite game the first mover cannot lose” version is contradicted by his own case analysis: the third branch above is White losing.
  • His actual focus was quantitative — if White can force a win, in how many moves? He claimed a bound of t, the number of positions, and argued by non-repetition: “every endgame q = (q, q₁, …, q_n) with n > t would have to contain at least one position q_α = q_β a second time and White could have played at the first appearance of it in the same way as at the second.” That argument is incomplete — it fixes one line of play rather than all of Black’s replies — and König (1927) repaired it, at von Neumann’s suggestion, using what is now König’s lemma.
  • His closing sentence is the one to remember, because it shows what he thought he had and had not settled: “The question as to whether the starting position p₀ is already a ‘winning position’ for one of the parties is still open. Would it be answered exactly, Chess would of course lose the character of a game at all.”

Corroboration from a completely independent direction: when Shannon set out the same trichotomy in 1950, he cited it to “(von Neumann and Morgenstern, 1944)” and to page 125 of Theory of Games and Economic Behavior — not to Zermelo (Shannon, Programming a Computer for Playing Chess, Phil. Mag. Ser. 7, 41(314), 1950). The misattribution post-dates him.

For the full treatment of the provenance, the epistemic assumptions, and the games that break them, see Backward Induction and Zermelo’s Theorem and Solved Games. What this note takes from it is narrow and practical: the algorithm you are about to write is von Neumann and Morgenstern’s, the determinacy result licensing it is Zermelo’s, and the two are not the same thing.

2. Score-Difference Trick — The Pythonic Minimax

For scoring games (Stone Game, Predict the Winner), instead of tracking each player’s score separately, define dp[state] = the maximum score difference (current player’s score minus opponent’s score) achievable from state, assuming both play optimally.

dp[state] = max over actions a of: reward(state, a) - dp[next_state(state, a)]

The subtle move: dp[next_state] is the score difference from the opponent’s perspective once it’s their turn. Subtracting it converts to “my score” perspective. The max is over the current player’s actions.

This collapses the alternation into a single sign flip, eliminating the need to track turns explicitly. The whose-turn-is-it information is implicit in the parity of the state’s path from the root.

Symbol-by-symbol unpacking:

  • state: encodes the game position (e.g., (left, right) indices into a stones array).
  • reward(state, a): the score the current player gets from action a.
  • next_state(state, a): the state after action a.
  • dp[next_state]: best score difference from the perspective of whoever moves next. Subtracting it gives “what I lose to them.”
  • The - sign reflects the alternation: their gain is my loss in zero-sum games.

For Predict the Winner: dp[i][j] = max score difference for whoever plays first when the array is nums[i..j]. Recurrence:

dp[i][j] = max(nums[i] - dp[i+1][j],     # take left, opponent now plays on (i+1..j)
               nums[j] - dp[i][j-1])     # take right, opponent now plays on (i..j-1)

Player 1 wins iff dp[0][n-1] >= 0. Beautiful and compact.

3. Tiny Worked Example — Predict the Winner (LC 486)

Problem. Given nums = [1, 5, 2], two players alternate. On each turn, the current player picks either the leftmost or rightmost number, adds it to their score, and removes it. Player 1 wins iff their final score is ≥ Player 2’s. Determine the winner under optimal play.

3.1 Game Tree By Hand

Let’s expand the full game tree with explicit score-difference reasoning:

State [1, 5, 2], P1’s turn:

  • P1 takes 1 → state [5, 2], P1 score = 1.
    • P2 takes 5 → state [2], P2 score = 5.
      • P1 takes 2 → state [], P1 = 3, P2 = 5. P1 - P2 = -2.
    • P2 takes 2 → state [5], P2 score = 2.
      • P1 takes 5 → state [], P1 = 6, P2 = 2. P1 - P2 = 4.
    • P2 plays optimally: P2 wants to minimize P1 - P2, equivalently maximize P2 - P1. P2 picks max(P2-P1) over its options: max(5 - 3, 2 - 6) = max(2, -4) = 2. So P2 takes 5, leaving final P1-P2 = -2.
  • P1 takes 2 → state [1, 5], P1 score = 2.
    • P2 takes 1 → state [5], P2 score = 1.
      • P1 takes 5 → state [], P1 = 7, P2 = 1. P1 - P2 = 6.
    • P2 takes 5 → state [1], P2 score = 5.
      • P1 takes 1 → state [], P1 = 3, P2 = 5. P1 - P2 = -2.
    • P2 plays optimally: max(P2 - P1) = max(1 - 7, 5 - 3) = max(-6, 2) = 2. So P2 takes 5, leaving P1-P2 = -2.
  • P1 plays optimally: P1 picks max(P1 - P2) = max(-2, -2) = -2. P1 - P2 = -2 under optimal play.

P1 loses (final difference is -2 < 0). Or, since the problem says “P1 wins iff P1 ≥ P2,” P1 technically wins iff difference ≥ 0; here it’s -2, so P2 wins.

3.2 Same Result Via The DP Recurrence

Let dp[i][j] = max score difference for whoever moves first on nums[i..j].

Base case: dp[i][i] = nums[i] (one element left, current player takes it).

Compute upward by length:

  • Length 1: dp[0][0] = 1, dp[1][1] = 5, dp[2][2] = 2.
  • Length 2: dp[0][1] = max(nums[0] - dp[1][1], nums[1] - dp[0][0]) = max(1 - 5, 5 - 1) = max(-4, 4) = 4. dp[1][2] = max(nums[1] - dp[2][2], nums[2] - dp[1][1]) = max(5 - 2, 2 - 5) = max(3, -3) = 3.
  • Length 3: dp[0][2] = max(nums[0] - dp[1][2], nums[2] - dp[0][1]) = max(1 - 3, 2 - 4) = max(-2, -2) = -2.

dp[0][2] = -2. P1’s score minus P2’s score under optimal play is -2, so P2 wins by 2. Matches the hand-trace.

The DP collapses what was a 6-leaf game tree into a 3 × 3 table with O(n²) work. For larger n, the savings are dramatic.

4. Worked Example — Nim (Bouton’s Theorem and Sprague-Grundy)

Nim. Two players take turns. There are k heaps of stones, with sizes a_1, a_2, ..., a_k. On each turn, a player picks one heap and removes any positive number of stones from it. The player who cannot move (because all heaps are empty) loses. (This is the normal-play convention; misère Nim flips the win/lose condition for one heap of size 1.)

4.1 Bouton’s Closed-Form Solution (1901), Read in the Original

Before the formula, it is worth knowing what Bouton actually wrote, because two details of the modern presentation are anachronisms.

Bouton’s Nim has exactly three piles. His opening description: “Upon a table are placed three piles of objects of any kind, let us say counters. The number in each pile is quite arbitrary… The players play alternately, and the player who takes up the last counter or counters from the table wins.” The generalisation to k piles is his §5, added afterwards. He also names the game in the paper — “It has been called Fan-Tan, but as it is not the Chinese game of that name, the name in the title is proposed for it” (Bouton, Nim, A Game with a Complete Mathematical Theory, Annals of Mathematics 2nd Ser. 3 (1901–1902), 35–39).

Bouton does not use XOR, and the word “nim-sum” is not his. He defines a safe combination by column parity: “Write the number of the counters in each pile in the binary scale of notation, and place these numbers in three horizontal lines so that the units are in the same vertical column. If then the sum of each column is 2 or 0 (i.e. congruent to 0, mod. 2), the set of numbers forms a safe combination.” That is bitwise XOR = 0, expressed in the vocabulary available in 1901. His example is 9, 5, 12 (1001, 0101, 1100), and he immediately notes the closure property that makes it a “combination” at all: “if any two numbers be given, a third is always uniquely determined which forms a safe combination with the two given numbers.”

With that in hand, the modern statement. The first player wins iff the XOR of all heap sizes is nonzero:

P1 wins   ⇔   a_1 ⊕ a_2 ⊕ ... ⊕ a_k ≠ 0

Proof (Bouton’s, in modern notation).

  1. From a zero-XOR state, every move leads to a nonzero-XOR state. Suppose a_1 ⊕ ... ⊕ a_k = 0. Removing stones from heap i changes its size to some a_i' < a_i. The new XOR is 0 ⊕ a_i ⊕ a_i' = a_i ⊕ a_i', which is nonzero because a_i' ≠ a_i. So a player forced to move from a zero-XOR (“safe”) state hands the opponent an unsafe one.
  2. From a nonzero-XOR state, there exists a move to a zero-XOR state. Let s = a_1 ⊕ ... ⊕ a_k ≠ 0 and let b be the highest set bit of s. Some heap a_i has bit b set, because the XOR’s bit b is 1. Then a_i ⊕ s < a_i (bit b of a_i flips off, and no higher bit changes), so reducing heap i to a_i ⊕ s is a legal move, and it makes the new XOR s ⊕ a_i ⊕ (a_i ⊕ s) = 0.
  3. The terminal state is safe. All heaps empty gives XOR 0, and the player to move has lost.

Combining: the player facing a zero-XOR state loses under optimal play, so the first player wins iff the initial XOR is nonzero. Step 2 is the part worth internalising for interviews, because it is not just an existence claim — it is a constructive winning move, a_i → a_i ⊕ s, computable in O(k).

Bouton’s misère rule, from his §6, is not “flip the answer”. He is careful about this: “The safe combinations are the same as before, except that an odd number of piles, each containing one, is now safe, while an even number of ones is not safe.” In other words: play normal Nim while any heap has ≥ 2 stones; once every heap has size ≤ 1, leave your opponent an odd number of one-stone heaps. Bouton also notes, with evident amusement, that this variant “seems to be more widely known than that first described, but its theory is not quite so simple.” §11.4 and §10.1 return to this.

4.2 Sprague-Grundy Theory — What Sprague Actually Proved

Any impartial game (both players have the same moves available at every position, normal-play convention: the player who cannot move loses) is equivalent to a Nim heap of some size — the Grundy number (or nimber) of the position. The usual modern definition is a formula:

Grundy(state) = mex { Grundy(next_state) for all legal moves }

where mex(S) (minimum excludant) is the smallest non-negative integer not in S, and terminal positions have Grundy number 0.

Sprague’s 1936 paper states it differently, and the difference is instructive. He calls the value the Rang (“rank”) and characterises it by two properties rather than defining it by a formula (Sprague, Über mathematische Kampfspiele, Tôhoku Mathematical Journal 41 (1936), 438–444 — the German original, read directly):

Satz I. In every game of bounded length, non-negative integers can be assigned to positions as “rank” such that A) no position has a successor of the same rank, and B) every position of rank R > 0 has, for each prescribed integer less than R, a successor of that rank.

Those two conditions are exactly mex, and seeing why is the whole point. Condition (A) says Grundy(s) is not among the Grundy values of s’s successors — i.e. it is excluded. Condition (B) says every value strictly below Grundy(s) is achieved by some successor — i.e. nothing smaller is excluded. Together: Grundy(s) is the minimum excluded value. Sprague’s version is the better one to carry around, because (B) is the property you actually use when playing: from a position of rank R, you can move to a position of any smaller rank you like, in particular to rank 0, which is a loss for your opponent.

The decomposition theorem is his Satz II: “A position of the combined game is a G or a V according as the ranks a, b, c, … of the individual positions form a G or a V in Nim” — where G (Gewinnstellung) is a position won by the player to move and V (Verluststellung) is one won by the other, a classification Sprague credits to Emanuel Lasker’s 1931 book Brettspiele der Völker, from which the term “mathematische Kampfspiele” also comes. Sprague draws the conclusion in one line: “Mit Rücksicht auf diesen Satz erscheint jedes Gesamtspiel als ein verallgemeinertes Nim” — in light of this theorem, every combined game appears as a generalised Nim.

Only then does the XOR appear, as his Satz III, and he is explicit that the criterion is Bouton’s, not his: writing a, b, c, … in binary one under another, “the digits of R are 0 or 1 according as the corresponding column of the scheme shows an even or an odd number of ones. The value of R is the rank of the position `a, b, c, … in Nim.” So the modern one-liner

Grundy(G₁ + G₂) = Grundy(G₁) ⊕ Grundy(G₂)

is the composition of two separately-earned facts: Sprague’s — every impartial game reduces to Nim — and Bouton’s — Nim is solved by binary column parity. Patrick Grundy reached the same results independently in 1939 (Mathematics and games, Eureka 2, 6–8; bibliographic only, not retrieved here), which is why the theorem carries both names.

Practical application: subtraction games. Players may remove 1, 3, or 4 stones (not arbitrary amounts) from a single heap. Compute Grundy numbers bottom-up: G(0) = 0, G(1) = mex{G(0)} = 1, G(2) = mex{G(1)} = 0, G(3) = mex{G(0), G(2)} = mex{0, 0} = 1, G(4) = mex{G(3), G(1), G(0)} = mex{1, 1, 0} = 2, and so on. The first player wins iff the XOR of G(aᵢ) over the heaps is nonzero. Subtraction games with a finite move set always have eventually periodic Grundy sequences (the {1,3,4} game has period 7 — see the computed output in §6.4), which is what makes them tractable for large heaps: precompute one period, then index modulo it.

flowchart LR
    B["Bouton 1901<br/>Nim is solved by<br/>binary column parity"]
    L["Lasker 1931<br/>names 'mathematische Kampfspiele';<br/>splits positions into G and V"]
    S1["Sprague Satz I<br/>every position has a rank<br/>(A) no successor of equal rank<br/>(B) all smaller ranks reachable<br/>= mex"]
    S2["Sprague Satz II<br/>a sum of games behaves as<br/>Nim on the ranks"]
    S3["Sprague Satz III<br/>Nim rank = binary column parity<br/>(explicitly Bouton's criterion)"]
    G["modern one-liner<br/>Grundy(G1 + G2) = Grundy(G1) XOR Grundy(G2)"]
    L --> S1
    S1 --> S2
    B --> S3
    S2 --> G
    S3 --> G

What this diagram shows. How the theorem you memorise decomposes into the results that were actually proved, and by whom. The insight to take away: the XOR is not the theorem. Bouton’s XOR solves Nim; Sprague’s contribution is that every impartial game is Nim in disguise, which is what lets you apply the XOR at all. If you only remember “XOR the Grundy numbers”, you will apply it to a partisan game one day and get a confidently wrong answer — see §11.6.

Uncertain

Verify: (a) that Grundy’s 1939 Eureka note reaches the same results as Sprague independently, and in what form; (b) the exact statement of von Neumann’s 1928 minimax theorem in Zur Theorie der Gesellschaftsspiele; (c) Lasker’s 1931 G/V classification. Reason: none of these three originals was retrieved from this machine. Sprague’s 1936 paper was read in the German original (J-STAGE serves Tôhoku Math. J. First Series open-access) and is the basis for everything attributed to Sprague above, including his own credit to Lasker and to Bouton. Grundy’s Eureka 2 (1939) 6–8 has no online copy that was locatable; von Neumann’s 1928 Math. Annalen paper likewise. The minimax-theorem statement in §1.1 is therefore sourced to Algorithmic Game Theory, Ch. 1 and Ch. 4, which was read, rather than to von Neumann. To resolve: obtain the Eureka reprint (it is reproduced in Eureka 27, 1964, 9–11) and the Math. Annalen volume, or Bagemihl’s 1959 English translation of the latter. #uncertain

4.3 Why XOR? The Mirroring Read

XOR is “addition without carry” in binary, and the reason that operation and not ordinary addition is the right one has a concrete game-theoretic reading: two equal heaps cancel (a ⊕ a = 0), because whatever your opponent takes from one you can take from the other, keeping them equal until both hit zero and handing your opponent the empty position. Bouton singles out precisely this case as the base of the induction — “A particular safe combination which is used later is that in which two piles are equal and the third is zero” — and the whole XOR criterion is the statement that a general position decomposes, bit by bit, into such mirrorable pairs.

Reading it column by column: a position is safe exactly when, in every binary column independently, the number of heaps with that bit set is even. Each column is therefore its own tiny mirroring game, and they do not interact — which is exactly why the criterion is a bitwise operation rather than an arithmetic one. Carrying would couple the columns and destroy the independence. This is the same structural reason the Sprague-Grundy sum in §4.2 is an XOR of nim-values rather than a sum: independent components must combine by an operation under which each component is its own involution.

The connection to XOR Properties worth carrying away: ⊕ makes the non-negative integers an abelian group of exponent 2 (a ⊕ a = 0, so every element is its own inverse), and “every element is its own inverse” is the algebraic form of “I can mirror your move”.

5. Pseudocode

5.1 Score-Difference DP (Predict the Winner Template)

predict_winner(nums):
    n := len(nums)
    dp := 2D array of size n × n
    for i := 0 to n-1:
        dp[i][i] := nums[i]
    for length := 2 to n:
        for i := 0 to n - length:
            j := i + length - 1
            dp[i][j] := max(nums[i] - dp[i+1][j],
                            nums[j] - dp[i][j-1])
    return dp[0][n-1] >= 0

5.2 Pure Minimax (Search Tree)

minimax(state, my_turn):
    if state is terminal:
        return outcome(state)
    if my_turn:
        best := -INF
        for action in legal_actions(state):
            value := minimax(next_state(state, action), not my_turn)
            best := max(best, value)
        return best
    else:
        best := +INF
        for action in legal_actions(state):
            value := minimax(next_state(state, action), not my_turn)
            best := min(best, value)
        return best

With memoization on state, this becomes a DP. Without memo, it’s exponential search.

5.3 Alpha-Beta Pruning

alphabeta(state, alpha, beta, my_turn):
    if state is terminal: return outcome(state)
    if my_turn:
        for action in legal_actions(state):
            value := alphabeta(next(state, action), alpha, beta, not my_turn)
            alpha := max(alpha, value)
            if alpha >= beta: break       # beta cutoff: opponent won't allow this branch
        return alpha
    else:
        for action in legal_actions(state):
            value := alphabeta(next(state, action), alpha, beta, not my_turn)
            beta := min(beta, value)
            if alpha >= beta: break       # alpha cutoff: I won't enter this branch
        return beta

Alpha-beta prunes branches that cannot affect the final decision, and Knuth and Moore proved exactly how much it prunes in the best case. Theorem 1 of their paper characterises the nodes visited under perfect move ordering (the first successor of every position is optimal) as the critical positions, and Corollary 1 counts them: if every position on levels 0 … l−1 has exactly d successors, alpha-beta examines

d^⌊l/2⌋ + d^⌈l/2⌉ − 1

positions on level l (Knuth & Moore 1975). For even l that is 2·d^{l/2} − 1, which is the familiar “square-root speedup” — you can search twice the depth in the same node budget. Two caveats the folklore drops, both of which Knuth and Moore state explicitly:

  • The root value must not be ±∞. They point out that earlier authors (Levin 1961, and the Hart–Edwards memo, which justified the result by saying “For a convincing personal proof using the new heuristic hand waving technique, see the author of this theorem”) all omitted this hypothesis. If the root is a forced win the count is d^⌊l/2⌋, if a forced loss d^⌈l/2⌉: “Roughly speaking, we gain a factor of 2 when the root value is ±∞.”
  • This is the best case, not the typical case. It assumes you already know the best move at every node — which is what you were searching for. §10.6 gives the actual bound without that assumption, and it is not b^{3d/4}.

5.4 Negamax — One Procedure Instead of Two, and Where It Comes From

The pseudocode in §5.2 and §5.3 carries two nearly identical branches, one for the maximiser and one for the minimiser. Every serious implementation collapses them, and the collapse has a name and a primary source: it is procedure F2 in Knuth and Moore’s analysis (Knuth & Moore, An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6 (1975), 293–326).

The trick is to evaluate every position from the perspective of the player to move, so that the value of a position is the negation of the value of the position your opponent faces after your move. Knuth and Moore give the reason for preferring it before they give the procedure: the negamax convention is used “because we don’t have to deal with two (or sometimes even four or eight) separate cases when we want to establish our results.” That is a proof-engineering argument, and it applies verbatim to code: half the branches means half the places to put the sign wrong.

integer procedure F2(position p, integer alpha, integer beta):
    determine the successor positions p₁, …, p_d
    if d = 0 then
        F2 := f(p)                       # static evaluation, from p's mover's view
    else
        m := alpha
        for i := 1 step 1 until d do
            t := −F2(pᵢ, −beta, −m)      # ← the whole idea is on this line
            if t > m then m := t
            if m ≥ beta then goto done   # cutoff
        done: F2 := m

Walking that one line symbol by symbol. F2(pᵢ, −beta, −m) evaluates the child from the child’s mover’s perspective. Because the game is zero-sum, that number is the negation of what the child is worth to us, hence the leading −. The window flips with it: our lower bound m is the opponent’s upper bound −m, and our upper bound beta is the opponent’s lower bound −beta. Swap-and-negate, always both.

Knuth and Moore also state the correctness conditions that make F2 a legitimate replacement for full minimax rather than an approximation. F2 is only required to satisfy three inequalities — it returns something ≤ alpha if the true value is ≤ alpha, exactly F(p) if the value lies strictly inside the window, and something ≥ beta if the value is ≥ beta — from which the theorem that matters follows: F2(p, −∞, ∞) = F(p). A windowed call is not guaranteed to return the true value; only a full-window call is. This is exactly why you must not cache a windowed result in a transposition table without also recording whether it was an exact value, a lower bound, or an upper bound. It is the most common source of “my engine plays differently with the hash table on”.

The conversion back to the textbook minimax convention is given explicitly in the paper: the minimax-convention value “equals −F2(p, −beta, −alpha)”. So the two formulations are not merely similar, they are related by an exact identity, and any disagreement between your negamax and your minimax implementations is a bug in one of them and not a modelling difference.

flowchart TD
    A["node A · P1 to move<br/>minimax value +4<br/>negamax value +4"]
    B["node B · P2 to move<br/>minimax value +4<br/>negamax value −4"]
    C["leaf · P1 to move<br/>static eval +4<br/>negamax value +4"]
    A -->|"F2(B, −β, −m)<br/>then negate"| B
    B -->|"F2(C, −β, −m)<br/>then negate"| C

What this diagram shows. The same three-node path under both conventions. Under minimax, the value +4 is carried unchanged up the tree and the operator alternates between max and min. Under negamax, the operator is always max and the sign alternates instead. The insight to take away: these are the same computation with the alternation moved from the code into the data. Minimax puts the alternation in a branch you can forget to write; negamax puts it in a − you can see on every recursive call — which is why every production engine uses it, and why §11.1’s missing-minus-sign bug is so much easier to spot in the negamax form.

5.5 Sprague-Grundy Computation

grundy(state):
    if state is terminal: return 0
    seen := {}
    for action in legal_actions(state):
        seen.add(grundy(next_state(state, action)))
    return mex(seen)

# mex(S) = smallest non-negative int not in S
mex(S):
    i := 0
    while i in S: i += 1
    return i

For combined games (Sprague-Grundy theorem):

combined_grundy = G1 ⊕ G2 ⊕ ... ⊕ G_k
first_player_wins = (combined_grundy != 0)

6. Python Implementations

6.1 LC 486 — Predict the Winner

def PredictTheWinner(nums: list[int]) -> bool:
    n = len(nums)
    # dp[i][j] = max score difference for whoever plays first on nums[i..j]
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = nums[i]
    # Fill by increasing subarray length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(nums[i] - dp[i + 1][j],
                           nums[j] - dp[i][j - 1])
    return dp[0][n - 1] >= 0
 
 
# Test
print(PredictTheWinner([1, 5, 2]))     # False (P1 loses by 2; matches our trace)
print(PredictTheWinner([1, 5, 233, 7])) # True (P1 takes 1, then ahead)

Time: O(n²). Space: O(n²), optimizable to O(n) with rolling arrays.

6.2 LC 877 — Stone Game (variant where Alice always wins)

def stoneGame(piles: list[int]) -> bool:
    n = len(piles)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(piles[i] - dp[i + 1][j],
                           piles[j] - dp[i][j - 1])
    return dp[0][n - 1] > 0
 
 
# Mathematical observation: with even n and integer total, Alice always wins
# by choosing colors (taking only even-indexed or only odd-indexed piles).
# DP confirms it for any input; the closed-form proof is even nicer.

LC 877 famously has a return True solution because of a parity argument, but the DP works regardless.

6.3 LC 292 — Nim Game (Closed-Form)

def canWinNim(n: int) -> bool:
    """Standard 1-2-3 take-away Nim with one heap.
    First player loses iff n is divisible by 4."""
    return n % 4 != 0
 
 
# Why? Compute Grundy numbers:
# G(0) = 0
# G(1) = mex{G(0)} = mex{0} = 1
# G(2) = mex{G(0), G(1)} = mex{0, 1} = 2
# G(3) = mex{G(0), G(1), G(2)} = mex{0, 1, 2} = 3
# G(4) = mex{G(1), G(2), G(3)} = mex{1, 2, 3} = 0
# G(5) = mex{G(2), G(3), G(4)} = mex{2, 3, 0} = 1
# ... pattern repeats with period 4: G(n) = n % 4
# First player wins iff G(n) != 0, i.e., n % 4 != 0.

The closed form falls out of the Grundy-number analysis. This is the kind of insight that turns a DP problem into a one-liner.

6.4 General Sprague-Grundy Computation

from functools import lru_cache
 
def grundy_subtraction_game(n: int, allowed_moves: tuple) -> int:
    """Grundy number for the take-away game where you can remove any
    amount in `allowed_moves` from a heap of `n`."""
    @lru_cache(maxsize=None)
    def g(k):
        if k == 0:
            return 0
        seen = set()
        for m in allowed_moves:
            if k - m >= 0:
                seen.add(g(k - m))
        # mex
        i = 0
        while i in seen:
            i += 1
        return i
    return g(n)
 
 
# Subtraction game: remove 1, 3, or 4 stones
print([grundy_subtraction_game(k, (1, 3, 4)) for k in range(15)])
# [0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, 0]
# Period 7. P1 wins from heap of size n iff g(n) != 0.
 
# Multi-heap version: P1 wins iff XOR of Grundy numbers is nonzero
def first_player_wins(heaps, allowed_moves):
    xor_sum = 0
    for h in heaps:
        xor_sum ^= grundy_subtraction_game(h, allowed_moves)
    return xor_sum != 0

7. Complexity

The complexity follows the same template as deterministic DP: O(states · transitions) time, O(states) space.

For LC 486 / LC 877:

  • States: (i, j) with 0 ≤ i ≤ j < n. Count: O(n²).
  • Transitions: 2 per state.
  • Total: O(n²) time, O(n²) space (or O(n) with rolling).

For Nim with k heaps each up to size M:

  • Grundy numbers: O(k · M · |moves|) precomputation.
  • Final XOR: O(k).

For minimax without DP:

  • Branching factor b, depth d: O(b^d).
  • With memoization: O(unique_states · branching_factor) — the DP advantage.
  • With alpha-beta on perfectly ordered moves: exactly b^⌊d/2⌋ + b^⌈d/2⌉ − 1 nodes on level d, provided the root value is finite (§5.3).
  • With alpha-beta on randomly ordered moves and no deep cutoffs: branching factor Θ(b/log b), not b^{3/4} (§10.6).

For competitive games like chess:

  • The state count — an estimated (4.82 ± 0.03) × 10⁴⁴ legal positions — precludes full DP by a margin no hardware improvement will close.
  • Alpha-beta + transposition tables (memoization under another name) + opening books + neural-net evaluation are the production combination. §12 covers what that means in practice, including the correctness trap in caching alpha-beta’s windowed return values.

8. Diagram — The Minimax Game Tree

flowchart TD
    Root["state: nums=[1,5,2]<br/>(P1 max)<br/>value = -2"]
    L["state: [5,2], P1 took 1<br/>(P2 min)<br/>value = -2"]
    R["state: [1,5], P1 took 2<br/>(P2 min)<br/>value = -2"]

    LL["state: [2], P2 took 5<br/>(P1 max)<br/>value = -2"]
    LR["state: [5], P2 took 2<br/>(P1 max)<br/>value = +4"]
    RL["state: [5], P2 took 1<br/>(P1 max)<br/>value = +6"]
    RR["state: [1], P2 took 5<br/>(P1 max)<br/>value = -2"]

    LLL["[], P1 took 2<br/>P1=3, P2=5<br/>diff = -2"]
    LRL["[], P1 took 5<br/>P1=6, P2=2<br/>diff = +4"]
    RLL["[], P1 took 5<br/>P1=7, P2=1<br/>diff = +6"]
    RRL["[], P1 took 1<br/>P1=3, P2=5<br/>diff = -2"]

    Root -->|"P1 takes 1"| L
    Root -->|"P1 takes 2"| R
    L -->|"P2 takes 5 (better for P2)"| LL
    L -.-|"P2 takes 2 (worse for P2)"| LR
    R -.-|"P2 takes 1 (worse for P2)"| RL
    R -->|"P2 takes 5 (better for P2)"| RR
    LL --> LLL
    LR --> LRL
    RL --> RLL
    RR --> RRL

    style Root fill:#ffcccc
    style L fill:#ccccff
    style R fill:#ccccff
    style LL fill:#ffcccc
    style LR fill:#ffcccc
    style RL fill:#ffcccc
    style RR fill:#ffcccc

What this diagram shows. The full minimax game tree for Predict the Winner on [1, 5, 2]. Pink nodes are P1’s turn (maximizing P1 - P2); blue nodes are P2’s turn (minimizing P1 - P2). Solid arrows are the moves chosen under optimal play; dashed arrows are alternatives that the player rejects because they’re worse from that player’s perspective. Bottom-up evaluation: terminal leaves are scored directly (P1’s accumulated score minus P2’s). At blue (P2’s) nodes, P2 minimizes the value — picks the smaller of the children’s values. At pink (P1’s) nodes, P1 maximizes — picks the larger. The root value -2 propagates from the leaves through the alternating min/max selection. P1 cannot avoid losing by 2 when P2 plays optimally. The DP collapses this tree by caching (i, j) pairs (the subarray bounds) so each (i, j) is evaluated once instead of being expanded across multiple paths. The game tree visualizes what minimax does; the DP table is the efficient implementation. The visual takeaway is that minimax alternation perfectly captures adversarial play, and that the DP saves work by recognizing when two different play paths reach the same game position.

9. Common Interview Problems

ProblemLC #Pattern
Nim Game292Closed form: n % 4 != 0
Stone Game877Score-difference DP; mathematical shortcut: even n ⇒ P1 wins
Stone Game II1140DP with (i, M) state — extra dimension for moves remaining
Stone Game III1406DP with score-difference, take 1-3 stones
Stone Game IV1510Boolean DP: can current player force a win?
Stone Game VII1690Score-difference with subarray-sum twist
Stone Game VIII1872Prefix-sum-based optimization
Predict the Winner486Score-difference DP, identical structure to Stone Game
Cat and Mouse913Multi-state with cyclical positions; DP with “draw” handling
Can I Win464Bitmask + boolean DP (combines bitmask DP with game DP)
Flip Game II294Bitmask + Sprague-Grundy on string positions
Guess Number Higher or Lower II375Minimax cost (worst-case-aware DP)
Optimal Strategy for a Game (GfG)classicSame as Predict the Winner
KaylesresearchSubtraction-game variant; Grundy numbers periodic
Wythoff’s GameresearchTwo-pile Nim; closed form via golden ratio

The recognition signal: “two players take turns… both play optimally… determine outcome / score / winner.” The state captures the game position; the recurrence alternates max and min (or uses score-difference with sign flip).

10. Variants and Sub-Patterns

10.1 Misère Convention

In normal play, the player who cannot move loses. In misère play, that player wins. All of Sprague-Grundy theory as stated in §4.2 is normal-play theory, and this is not a technicality — the Sprague-Grundy theorem is false under misère play, and there is no drop-in replacement for the nim-value.

Nim itself is the easy case, and Bouton solved it in the same 1901 paper (§4.1): play normal Nim until every heap has size ≤ 1, then leave your opponent an odd number of one-stone heaps. Note what this costs — the misère strategy is not a function of a single nim-value any more; it needs a case split on the shape of the position.

Beyond Nim it gets genuinely hard, and the reason is worth stating precisely: under normal play, two positions with the same Grundy value are interchangeable in any sum, which is what makes a single number sufficient. Under misère play that interchangeability fails — Conway’s remark, quoted at the head of the modern treatment, is that misère “restive games are ambivalent Nim-heaps, which choose their size (g₀ or g) according to their company”, and he adds “it would be very interesting to have some general theory for them” (On Numbers and Games, Ch. 12). The general theory arrived only in 2005, as misère quotients: a commutative semigroup obtained by quotienting the free commutative semigroup on single-heap positions by the game’s indistinguishability congruence. Plambeck introduces it as “the long-sought natural generalization of the normal-play Sprague-Grundy theory to misere play”, and the payoff is that games with “an infinity of ever-more complicated canonical forms amongst their position sums may nevertheless possess a relatively simple, even finite misere quotient” (Plambeck, Taming the Wild in Impartial Combinatorial Games, arXiv:math/0501315).

What to do in an interview: read the problem statement twice for which convention it uses, then check whether it is Nim-shaped enough for Bouton’s rule. If it is a general misère game, say out loud that Sprague-Grundy does not apply and that you will compute win/lose states directly — that is both correct and the answer the interviewer wants.

10.2 Partisan Games

In impartial games, both players have the same legal moves at each position (Nim, Go-Moku in some variants). In partisan games, the players have different moves (chess: white moves white pieces, black moves black). Sprague-Grundy applies only to impartial games. Partisan games are analyzed with surreal numbers (Conway 1976) — a much richer framework.

10.3 Games With Draws

Pure two-player zero-sum minimax assumes terminal positions are scored numerically (or labeled win/lose). When draws are possible (chess, tic-tac-toe), the recurrence must include a “draw” outcome, often valued at 0. The DP table holds {WIN, DRAW, LOSE} instead of numerical scores in some implementations.

10.4 Imperfect Information / Stochastic Games

Probability DP (see Probability DP) merges with game-theory DP for games with chance nodes (backgammon: dice rolls). Each “chance node” averages over outcomes weighted by probability; max/min nodes still alternate. Algorithm: expectimax (replacing one of the min/max with weighted-average).

For imperfect-information games (poker), DP doesn’t suffice — you need belief-state tracking and Counterfactual Regret Minimization (CFR). Beyond interview scope but worth knowing exists.

10.5 Games With Memoryless Strategy (Ramsey-Style)

Some games have strategies that depend only on a subset of state (e.g., the current turn count modulo some period). Recognizing these reduces the DP state space dramatically.

10.6 Alpha-Beta with Move Ordering — and the b^{3d/4} Myth

Alpha-beta’s pruning effectiveness depends almost entirely on move ordering. With moves explored in best-first order it achieves the exact count in §5.3 — effectively a branching factor of √d. The interesting question is what happens with random ordering, and here the widely-repeated figure is wrong.

The claim “with random ordering alpha-beta averages O(b^{3d/4})” traces to an empirical fit, and Knuth and Moore — who produced the fit — warn against believing it in the same paragraph. Their words: plotting their computed branching factors on log-log paper “seem[s] to be approaching a straight line, suggesting that it is approximately of order d^{0.75}. In fact, a least-squares fit for 10 ≤ d ≤ 30 yielded d^{0.76} as an approximate order of growth”, and Fuller et al. had independently estimated d^{0.72}. Then the correction: “However, we shall see that the true order of growth… as d → ∞ is really d/log d.”

That is their Theorem 5: the branching factor r(d) = lim_h T(d, h)^{1/h} of alpha-beta without deep cutoffs on a random uniform game tree of degree d satisfies c₃·d/log d ≤ r(d) ≤ c₄·d/log d for positive constants c₃, c₄. And they draw the moral explicitly: “If we didn’t know the theoretical asymptotic growth, we would be quite content to think of it as d^{0.75} when d is in a practical range. The formula d/log d seems much worse than d^{0.75} until we realize the magnitude of log d in the range of interest… On the basis of this theory we may well regard the approximation d^{0.72} in [7] with some suspicion.”

So the honest statement is: the asymptotic branching factor under random ordering is Θ(d/log d); d^{0.75} is a curve fit that happens to be good for d between 10 and 30 and is not a theorem. An earlier revision of this note quoted the fit as a result.

Knuth and Moore also list what their model deliberately gets wrong, all in the pessimistic direction — “(a) the deep cutoffs are not considered; (b) the ordering of successor positions is random; (c) the terminal positions are assumed to have distinct values; (d) the terminal values are assumed to be independent of each other” — so real engines do better than d/log d. That is exactly the gap that heuristic move ordering (captures first, killer-move tables, principal variation search, history heuristics) is engineered to exploit, and it is why §10.7’s iterative deepening pays for itself.

10.7 Iterative Deepening for Games

Like Iterative Deepening DFS, game tree search benefits from iterative deepening: search to depth 1, then 2, then 3… With move-ordering memoized from the previous depth, each iteration’s pruning is much better than a single deep search. Standard chess engine technique.

11. Pitfalls

11.1 Forgetting the Sign Flip in Score-Difference DP

dp[state] = max( reward(a) - dp[next_state(a)] )   # CORRECT: subtract opponent's diff
dp[state] = max( reward(a) + dp[next_state(a)] )   # WRONG: this is single-player DP

The minus sign is the alternation. Forgetting it computes the maximum cooperative outcome, not the adversarial one.

11.2 Mistaking “Optimal Play” for “Greedy Play”

P1 optimally picking the largest current pile is not optimal in general — they must consider future implications. The DP correctly computes optimal-with-lookahead; greedy heuristics fail on adversarial inputs.

11.3 Not Memoizing the Turn Indicator

If the recurrence is value(state, turn), both arguments must be in the memo key. A common bug: memoizing only state, getting incorrect answers when the same position occurs at different turns. The score-difference trick avoids this issue elegantly by encoding the turn implicitly in the sign.

11.4 Confusing Misère and Normal Play

Standard Nim assumes normal play (the player who cannot move loses). Misère Nim (the player who takes the last stone loses) has a different optimal strategy at the endgame, and Bouton states it exactly: “The safe combinations are the same as before, except that an odd number of piles, each containing one, is now safe, while an even number of ones is not safe” (Bouton 1901, §6) — so leave your opponent an odd number of size-1 heaps. Most interview Nim is normal play; check the problem statement carefully, and see §10.1 for why the misère case does not generalise.

11.5 Forgetting Terminal States

Terminal states must be explicitly handled in the recurrence — usually dp[terminal] = 0 for score-diff games or dp[terminal] = LOSE for win/lose games. Off-by-one in the terminal case is a frequent bug.

11.6 Misapplying Sprague-Grundy to Partisan Games

Sprague-Grundy applies only to impartial games. Applying XOR-of-Grundy-numbers to chess (a partisan game) is wrong. Test: do both players have exactly the same legal moves at every position? If no, S-G doesn’t apply.

11.7 Recursion Depth on Long Games

Memoized recursion on long games can hit Python’s recursion limit. See Recursion Depth Limits. Convert to bottom-up iteration if depth could exceed ~1000.

11.8 Floating-Point in Score-Difference DP

Score-difference DPs typically use integers; no precision issues. Probability-flavored variants (expected-value game DP) revert to floating-point and inherit those concerns; see Probability DP.

11.9 Dependencies in Multi-Player Games

The recurrence max - dp[next] works for exactly two players. For three or more players, you need explicit per-player score tracking and argmax_player_i(...) style recurrences. Beyond standard interview scope.

11.10 Confusing Min/Max with Pruning Bounds

In alpha-beta, alpha is the best value max-player can guarantee so far; beta is the best min-player can guarantee. Confusing alpha and beta in the cutoff logic gives wrong results. The convention is alpha < beta always at the top of any recursive call; if alpha >= beta after an update, prune.

12. Production Notes — What This Looks Like Outside an Interview

The numbers that motivated the whole field are Shannon’s, and they are still the right ones to quote. In the paper that founded computer chess, Shannon estimated “of the order of 30 legal moves” in a typical position (averaged from De Groot’s data over master games), a game length of about 40 moves, and therefore “10¹²⁰ variations to be calculated from the initial position. A machine operating at the rate of one variation per micro-second would require over 10⁹⁰ years to calculate the first move!” He also considered and dismissed the lookup-table approach, estimating the number of positions as “roughly 10⁴³” (Shannon 1950). The modern statistical estimate of legal chess positions is (4.82 ± 0.03) × 10⁴⁴ at 95% confidence, obtained by uniform sampling over a bijective ranking of positions and hand-verifying legality of the samples (Tromp, ChessPositionRanking) — so Shannon’s order of magnitude was low by about one and a half decimal places, which for a 1950 back-of-envelope is remarkable. This note previously said ~10⁴⁵, which is in the right neighbourhood but was unsourced; the figure above is.

Shannon’s other lasting contribution is the distinction that still organises engine design: a type A strategy searches all continuations to a fixed depth and evaluates — “the type A strategy has certain basic weaknesses”, chiefly that it stops mid-capture — while a type B strategy searches selectively and extends unstable lines. Modern engines are type A with quiescence search and heavy reductions, which is a type B admission wearing type A clothes.

Transposition tables are memoisation, and they are where the DP in “game DP” actually lives in production. A chess engine reaches the same position by many move orders; a table keyed on a Zobrist hash of the position turns the tree into a DAG, exactly as caching (i, j) does in §3. Two cautions carry over from §5.4 and §11.3.

First, store what kind of bound each entry is. Plaat, Schaeffer, Pijls and de Bruin set out the three cases precisely: a call alphabeta(G, α, β) returning g with α < g < β gives the true minimax value; returning g ≤ α (“failing low”) gives only “an upper bound on the minimax value”; returning g ≥ β (“failing high”) gives only a lower bound (Plaat et al., SSS* = α-β + TT, University of Alberta TR 94-17, 1994). Cache a fail-low value as if it were exact and your engine will play differently with the hash table on — the classic symptom of this bug. Their paper’s larger result is worth knowing for its own sake: SSS*, long taught as a fundamentally different and asymptotically better best-first algorithm, “can be reformulated to use well-known technology, as a special case of the Alpha-Beta procedure enhanced with transposition tables”, and “does not need an OPEN list; a familiar transposition table performs as well.” The same reformulation is what yields MTD(f), the null-window driver that most modern engines use.

Second, make sure the key captures everything the value depends on — in chess: side to move, castling rights, and en-passant file. That is the game-engine form of §11.3’s “not memoizing the turn indicator”, and it fails the same way: silent wrong answers rather than crashes.

Iterative deepening is not a workaround, it is the move-ordering mechanism. Because alpha-beta’s efficiency is entirely a function of ordering (§10.6), and because the best move at depth d−1 is an excellent guess for the best move at depth d, searching to depth 1, 2, 3, … and using each iteration’s principal variation to order the next is faster than going straight to depth d, despite re-searching. See Iterative Deepening DFS.

Where this technique stops. Every algorithm in this note assumes the mover sees the whole position. Poker does not satisfy that, and the failure is not one of scale — no amount of compute makes minimax correct on an imperfect-information game, because the value of a position depends on beliefs, and playing a “best response to the position” is exploitable by definition. The replacement is regret minimisation over information sets: see Counterfactual Regret Minimization and Imperfect Information and Information Sets.

13. Open Questions

  • Can game-theory DP handle stochastic terminal outcomes? Yes — combine with probability DP via expectimax. The recurrence becomes max/min/avg depending on node type.
  • Is there a “convex-hull-trick”-style optimization for score-difference DPs with monotonic structure? Yes, in some cases — see Stone Game VIII, which uses prefix-sum monotonicity. Not as universal as deterministic DP optimizations.
  • How does game-theory DP relate to reinforcement learning? RL is the modern generalization: arbitrary states, arbitrary policies, neural function approximation. Minimax DP is RL with two opposed agents and exact tabular representation. The Bellman equation in MDPs is the single-player analog of the minimax recurrence.
  • When does symmetric-game DP have a closed-form? Wythoff’s game (golden ratio), Nim (XOR), 1-2-3 take-away (mod 4) all have closed forms. The general problem of “find a closed form for game G” is itself open in many cases — Conway’s research program.

14. See Also

Graph View

Backlinks