Game Theory

Core Concepts

Combinatorial game — a two-player, perfect-information, deterministic game with no draws, where players alternate moves and the player who cannot move loses (normal play convention).

P-position (Previous player wins) — the player who just moved wins; the player whose turn it is will lose under optimal play. Terminal positions (no moves available) are always P-positions.

N-position (Next player wins) — the player whose turn it is can reach at least one P-position in one move, so they win under optimal play.

Impartial game — both players have exactly the same set of available moves from any position (e.g., Nim, stone removal games). Sprague-Grundy theory applies.

Partisan game — the move sets differ by player (e.g., Chess, Go). Sprague-Grundy does not apply directly; minimax or direct DP is used instead.

Optimal play — both players always choose the best move for themselves; standard assumption unless stated otherwise.

Grundy value (nimber / nim-value) — g(pos) = mex of the Grundy values of all positions reachable in one move. Terminal positions have g = 0. Two positions are equivalent iff they share the same Grundy value.

mex (minimum excludant) — the smallest non-negative integer not in a set. mex({0, 1, 3}) = 2.

Nim — the canonical impartial game: multiple piles of stones; each turn remove any positive number from exactly one pile. XOR of all pile sizes = 0 → current player loses (P-position).

Normal play convention — the player who makes the last move wins. Misère convention: the player who makes the last move loses. Most LeetCode problems use normal play.

Game sum — playing two independent games simultaneously; each turn choose which game to move in. Grundy value of the sum = XOR of the individual Grundy values.

Types / Variants

Key Algorithms

XOR (Nim) Rule

XOR all pile sizes. Result = 0 → current player loses; result ≠ 0 → current player wins.

Key insight: from any XOR-nonzero position there exists a move that zeros the XOR; from any XOR-zero position every move produces a nonzero XOR. Applies to classic Nim and any game provably equivalent to Nim.

Time O(n), space O(1).

Sprague-Grundy Theorem

Compute g(pos) = mex({g(next) for next in moves(pos)}) for every reachable position. Use XOR of Grundy values to resolve composite games.

from functools import lru_cache
mex = lambda s: next(i for i in range(len(s) + 1) if i not in set(s))

Time O(states × branching), space O(states). Use when you need to combine sub-games or when simple P/N labeling is insufficient.

P/N Position DP

Label game states directly without computing full Grundy values:

• No moves available → P-position.
• Any successor is a P-position → N-position.
• All successors are N-positions → P-position.

Sufficient when the question is win/loss only (not game composition). Time O(states × branching), space O(states).

Score Difference DP

For two-player scored games on a sequence, dp[i][j] = maximum score the current player gains over the opponent from subarray [i..j].

dp[i][j] = max(val[i] - dp[i+1][j], val[j] - dp[i][j-1])

First player wins iff dp[0][n-1] >= 0. Time O(n²), space O(n²) reducible to O(n) with rolling array.

Minimax DP

For partisan or variable-score games: current player maximizes, opponent minimizes. Memoize on (i, j) for interval games or (state, turn) for general games.

The score-difference formulation above is equivalent and avoids tracking whose turn it is — prefer it for interval games.

Can-I-Win (Bitmask DP)

Pool of distinct integers ≤ 20; players alternate picking any unpicked number; first to reach cumulative target wins.

@lru_cache(None)
def can_win(used):
    total = sum(i + 1 for i in range(n) if used >> i & 1)
    if total >= target: return False  # previous player already won
    return any(not can_win(used | 1 << i) for i in range(n) if not used >> i & 1)

Time O(2^n · n), space O(2^n). Infeasible for n > 20.

Staircase Nim

Only odd-indexed stairs (1, 3, 5, …) contribute. Current player wins iff XOR of values at odd-indexed stairs ≠ 0.

Why: moving stones from an even stair to stair 0 is irrelevant; the opponent can mirror any move on even stairs back to odd stairs, preserving the XOR.

Pattern / Closed-Form Detection

For games where n can be huge, compute outcomes for small n (10–20 values), identify the repeating period p, then return outcome[n % p]. Applies when the game has no memory of prior moves.

Advanced Techniques

Grundy XOR for Composite Games

When a problem has multiple independent sub-games played simultaneously (each turn pick any sub-game and move in it), XOR the Grundy values of the sub-games. The composite position is a P-position iff the XOR is 0.

When to use: problem explicitly has multiple heaps, multiple rows, or multiple game boards. Do not use for a single-game win/loss question — P/N DP is simpler and sufficient.

Complexity: O(sum of individual sub-game state spaces).

Symmetry / Pairing Argument

If the game state is symmetric (even-length sequence, palindrome, symmetric 2D board), the second player can always mirror the first player's move to restore symmetry. This proves the second player always wins without any DP.

When to use: game structure is provably symmetric, and you need to argue one player wins regardless of the opponent's play. Much faster than DP when applicable. Do not use if the symmetry is broken by the game rules (e.g., different endpoints matter).

Misère Nim Adjustment

Play as normal Nim until only piles of size ≤ 1 remain, then leave an odd number of remaining piles (so the opponent takes the last stone). Winning condition: (XOR ≠ 0 and at least one pile > 1) OR (all piles ≤ 1 and even number of piles).

When to use: problem says the player who takes the last stone loses. Do not apply to restricted-move or staircase variants — each has its own misère adjustment.

Problem Taxonomy

By Problem Category

Problem Signal → Technique

Common Patterns

Edge Cases & Pitfalls

• DP state mixes player perspectives — dp[i][j] must always mean "current player's best outcome from [i..j]", not "player 1's outcome". Mixing perspectives silently produces wrong results because the recurrence relies on the current player being consistent at every level.

• Applying Nim XOR to restricted-move games — the XOR rule is only correct for classic Nim. For games where only 1, 2, or 3 stones may be removed, use Grundy values; the pattern n % 4 = 0 → lose is a consequence of Grundy, not a separate axiom.

• Bitmask DP base case order — check if desiredTotal ≤ 0 (previous player already won) before checking remaining moves; otherwise you return a move-based result for an already-decided game.

• Off-by-one: "reach exactly N" vs "first to exceed N" — the base case and transition differ. Read the problem statement carefully and verify with n = target − 1 and n = target.

• Hardcoding first player always wins — LeetCode stone-game problems often guarantee first-player wins for specific constraints (even length, all positive), but the general form does not. Only return True unconditionally when you have proven it for the given constraints.

• Misère adjustment applied universally — Staircase Nim, Wythoff, and subtraction games each have their own misère adjustments. The simple Nim misère rule does not transfer.

• mex on a non-set or unsorted collection — mex requires iterating from 0 upward over a set. Computing mex on a list without deduplication or from a sorted list without a set lookup causes incorrect Grundy values.

• Recursion depth in deep game trees — for games with O(n) depth and n ≈ 10^4, Python's default limit of 1000 stack frames will crash. Use sys.setrecursionlimit or convert to iterative DP.

Implementation Notes

• Python @lru_cache(None) handles memoized game recursion cleanly; use tuple state for multi-parameter positions.
• Bitmask DP: n = 20 → ~10^6 states (fine); n = 25 → ~3×10^7 (borderline); n > 25 is too slow.
• Interval DP can be computed bottom-up by filling diagonals (length 1, 2, …, n) or top-down with memoization — both are correct; top-down is simpler to write.
• For scored games, the rolling-array optimization reduces interval DP from O(n²) to O(n) space by reusing the previous diagonal's values.
• Grundy value computation for subtraction games typically cycles within max(S) + 1 steps — compute until the period repeats twice to confirm it.
• math.gcd appears in GCD-based game variants (Euclid's game, GCD subtraction); always check if the game reduces to a number-theory result before implementing DP.

Cross-Topic Relations

Interview Reference

Must-Know Problems

Nim / XOR / closed-form

• 292. Nim Game — n % 4 == 0 → lose; classic entry point
• 1025. Divisor Game — math; n even → first player wins
• 319. Bulb Switcher — perfect-square counting disguised as a game

Score-difference interval DP

• 486. Predict the Winner — canonical score-difference DP
• 877. Stone Game — symmetry argument then general DP
• 375. Guess Number Higher or Lower II — minimax; minimize worst-case cost over interval

Bitmask DP

• 464. Can I Win — bitmask on chosen numbers; watch edge cases

Stone game sequence (interval / prefix-sum DP)

• 1406. Stone Game III — take 1/2/3 per turn; score-difference DP
• 1140. Stone Game II — parameterized M; interval DP
• 1510. Stone Game IV — remove perfect-square count; Grundy / P-N DP
• 1690. Stone Game VII — interval DP with prefix sums

Sprague-Grundy

• 294. Flip Game II — Grundy values on string positions

Clarification Questions to Ask

• Normal play or misère (who wins — last to move, or last to move loses)?
• Can both players see all game state (perfect information assumed unless stated)?
• Is the move set the same for both players (impartial) or player-specific (partisan)?
• Are values bounded? (Determines whether closed-form, bitmask DP, or interval DP applies.)
• Does "win" mean reaching exactly the target or first to meet or exceed the target?
• Are all values positive, or can zeros / negatives appear?

Common Interview Mistakes

• Writing full recursive minimax without memoization — produces exponential time when polynomial DP suffices.
• Returning absolute player-1 score from the interval DP instead of the score difference from the current player's perspective — breaks the recurrence at alternating levels.
• Applying the Nim XOR rule to a restricted-move game (e.g., remove 1 or 2) without verifying equivalence to Nim — wrong for any non-Nim move set.
• Missing the O(1) symmetry argument for even-length stone games and implementing O(n²) DP instead.
• Forgetting to short-circuit can_win when desiredTotal > sum(1..maxChoosable) — unreachable target means the current player always loses; without this check the bitmask DP returns a spurious True.

Typical Follow-Up Escalations

• "Now you can take at most k stones per pile" → Restricted Nim; Grundy values cycle with period k + 1.
• "Now there are multiple independent game boards played simultaneously" → XOR of individual Grundy values (Sprague-Grundy).
• "Now the player who takes the last stone loses" → Misère Nim adjustment to the win condition.
• "Can you reduce the space from O(n²) to O(n)?" → Rolling-array on interval DP; process diagonal by diagonal, reuse arrays.
• "What if there are 10^9 stones in one pile?" → Closed-form or period mod; enumerate small cases, identify the pattern.