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.

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, dating to von Neumann’s 1928 Zur Theorie der Gesellschaftsspiele (foundational paper of game theory) and the famous minimax theorem (every two-player zero-sum game has a unique value when both play optimally, equal to both the maximin and minimax of the payoff matrix).

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 (~10^45 states) it’s not, and Monte Carlo Tree Search + 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.

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)

The first player wins iff the XOR of all heap sizes is nonzero:

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

Proof sketch (Bouton 1901).

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'. Since a_i' ≠ a_i, the XOR is nonzero. So the player forced to move from a zero-XOR state hands the opponent a winning (nonzero) state.
2. From a nonzero-XOR state, there exists a move to a zero-XOR state. Let s = a_1 ⊕ ... ⊕ a_k ≠ 0. Let b be the highest bit of s. Some heap a_i has bit b set (because XOR’s bit b is 1). Then a_i ⊕ s < a_i (because the high-bit-b of a_i flips off). Reducing heap i to a_i ⊕ s makes the new XOR equal to s ⊕ (a_i ⊕ (a_i ⊕ s)) = s ⊕ s = 0. So we can always move to a zero-XOR state.
3. The losing state is all zeros (no stones, no moves), and 0 ⊕ 0 ⊕ ... ⊕ 0 = 0. The “lose” state is a zero-XOR state — consistent.

Combining: the player facing a zero-XOR state loses with optimal play. The first player wins iff the initial XOR is nonzero.

This is one of the most beautiful results in combinatorial game theory: a complete solution by a single XOR.

4.2 Sprague-Grundy Theorem — Generalizing Beyond Nim

Any impartial game (both players have the same moves, normal-play loser convention) is equivalent to a Nim heap of some size — the Grundy number (or nimber) of the position. Defined recursively:

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

Where mex(S) (Minimum EXcludant) is the smallest non-negative integer not in set S. Terminal (no-move) positions have Grundy number 0.

Sprague-Grundy theorem (Sprague 1936; Grundy 1939): Two impartial games played in parallel — i.e., on each turn the player picks one of the games and moves in it — has Grundy number equal to the XOR of the individual Grundy numbers:

Grundy(G1 ⊕ G2) = Grundy(G1) ⊕ Grundy(G2)

This is the combinatorial-game-theory factorization theorem. Once you know the Grundy numbers of all your subgames, the combined game is solved by XOR — exactly Bouton’s Nim formula generalized to arbitrary impartial games.

Practical application: Nim with restrictions, “Subtraction Games.” Players can remove 1, 3, or 4 stones (not arbitrary amounts) from a single heap. Compute Grundy numbers iteratively: 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, etc. The first player wins iff XOR of G(a_i) ≠ 0.

4.3 Why XOR? An Information-Theoretic Read

XOR is the operation “addition without carry” in binary. Two equal heaps cancel each other (a ⊕ a = 0); each player can “mirror” the other’s moves on the cancelled pair, ensuring the eventual loser is whoever started moving on the unmatched portion. The XOR formalism captures this mirroring strategy precisely.

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. Best case: explores only O(b^(d/2)) instead of O(b^d) nodes (where b = branching factor, d = depth) — a square root speedup.

5.4 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: O(b^(d/2)).

For competitive games like chess:

• State count ~10^45 precludes full DP.
• Alpha-beta + transposition tables (a memoization-flavored cache) + opening books + neural-net evaluation are the production combination.

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

Problem	LC #	Pattern
Nim Game	292	Closed form: n % 4 != 0
Stone Game	877	Score-difference DP; mathematical shortcut: even n ⇒ P1 wins
Stone Game II	1140	DP with (i, M) state — extra dimension for moves remaining
Stone Game III	1406	DP with score-difference, take 1-3 stones
Stone Game IV	1510	Boolean DP: can current player force a win?
Stone Game VII	1690	Score-difference with subarray-sum twist
Stone Game VIII	1872	Prefix-sum-based optimization
Predict the Winner	486	Score-difference DP, identical structure to Stone Game
Cat and Mouse	913	Multi-state with cyclical positions; DP with “draw” handling
Can I Win	464	Bitmask + boolean DP (combines bitmask DP with game DP)
Flip Game II	294	Bitmask + Sprague-Grundy on string positions
Guess Number Higher or Lower II	375	Minimax cost (worst-case-aware DP)
Optimal Strategy for a Game (GfG)	classic	Same as Predict the Winner
Kayles	research	Subtraction-game variant; Grundy numbers periodic
Wythoff’s Game	research	Two-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. Most theory (Sprague-Grundy) is for normal play. Misère analysis is significantly harder; even Nim has subtle differences in misère form.

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

Alpha-beta’s pruning effectiveness depends on move ordering. With moves explored in best-first order, alpha-beta achieves the O(b^(d/2)) ideal. With random ordering, it averages O(b^(3d/4)). Heuristic move ordering (capture moves first in chess, killer-move tables, principal variation search) is critical in production game-tree search.

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 (player who can’t move loses). Misère Nim (player who takes the last stone loses) has different optimal strategy at the endgame: when all heaps are size 1, the misère winner is whoever leaves an odd count of size-1 heaps. Most interview Nim is normal play; check the problem statement carefully.

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. 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.

13. See Also

• Memoization vs Tabulation — DP foundation
• DP State Identification — recognizing the right state for game DP
• Probability DP — sibling note; probabilistic transitions instead of adversarial choice
• Bitmask DP — combined with game DP for games over subsets (Can I Win, LC 464)
• Backtracking Framework — minimax can be implemented as backtracking + memoization
• Recursion Depth Limits — memoized recursion can hit limits on long games
• Off-By-One Errors — Survival Guide — terminal-state handling
• XOR Properties — the algebraic foundation of Nim
• Bit Manipulation Tricks — XOR-based game-theory optimizations
• Big-O Notation
• Iterative Deepening DFS — search-tree approach to games
• SWE Interview Preparation MOC