Lab 14 — Game Theory: Sprague-Grundy

Goal

Analyze impartial games — Nim, mex/Grundy numbers, XOR composition of independent subgames — and produce actual winning strategies (which move to make), not just win/lose answers.

Background

N/P positions. Under normal play (last player to move wins), a position is P (Previous player wins — i.e., the player to move loses) iff every move leads to an N position; N iff some move leads to a P position. Terminal positions are P.

Bouton’s theorem (1901): in multi-pile Nim, the player to move wins iff the XOR of pile sizes ≠ 0. Constructive: let x = XOR of all piles; find a pile p with p ^ x < p (one exists — take the pile with the highest set bit of x) and reduce it to p ^ x, restoring XOR = 0.

Sprague-Grundy theorem: every finite impartial game under normal play is equivalent to a Nim pile of size g(state), where g = mex (minimum excludant) of the Grundy values of successor states. A sum of independent games has Grundy value equal to the XOR of the components’ Grundy values. g = 0 ⟺ P position.

Misère play (last to move loses) is the trap: the theory only transfers for Nim when all piles are ≤ 1 (play Bouton except leave an odd number of 1-piles). General misère games are genuinely hard — no clean analogue exists.

Interview Context

  • Codeforces / ICPC: regular; Div 2 D/E staple
  • Quant firms (Jane Street, SIG brainteasers): Nim variants appear in first rounds
  • Game/simulation companies: occasionally
  • Standard FAANG: rare — LC 292 (trivial Nim) and minimax DP show up; full Grundy theory almost never
  • LC anchors: 292 (Nim Game — the trivial n % 4 one), 1908 (Game of Nim, premium — actual multi-pile Nim), 294 (Flip Game II — Grundy on segments), 1510 (Stone Game IV — subtraction game)

When to Skip This Topic

Skip if any of these are true:

  • You aren’t targeting competitive programming or quant interviews
  • You haven’t mastered minimax with memoization (phase-05 game DP) — that solves 90% of interview game problems
  • You confuse “optimal play” with “greedy play”

If Stone Game I–III aren’t reflexive yet, do those first. Grundy is the 10x tool for the 1x-frequency problem.

Problem Statement

Three parts, one theory:

(a) Multi-pile Nim (LC 1908). Given pile sizes, decide if the first player wins — and if so, return a winning move (pile index, new size).

(b) Flip Game II (LC 294). String of + and -; a move flips some "++" to "--"; player unable to move loses. Decide if the current player can guarantee a win.

(c) Generic engine. Given any impartial game as a moves(state) → successors function, compute g(state) via memoized mex.

Constraints

  • Nim: up to 10^4 piles, sizes up to 10^9 — Bouton must be O(n), no game search
  • Flip game: string length up to 10^5 (LC caps at 60; the Grundy solution doesn’t care)
  • Generic engine: reachable state space small enough to memoize (≤ ~10^6 states)

Clarifying Questions

  1. Normal or misère play? (Normal — last player to move wins. Misère changes everything.)
  2. Is the game impartial — same moves available to both players? (Yes; otherwise Grundy theory does not apply.)
  3. Both players play optimally? (Yes.)
  4. Do you need the winning move or just win/lose? (Move for Nim; win/lose for flip game.)
  5. Is the game finite and acyclic? (Yes — every move strictly reduces something.)

Examples

Nim [3, 4, 5]: XOR = 2 ≠ 0 → first player wins.
Move: 3 ^ 2 = 1 < 3 → reduce pile 0 from 3 to 1, leaving [1, 4, 5], XOR = 0.

Nim [1, 2, 3]: XOR = 0 → first player loses.

"++++"     one run of 4:  g(4) = 2 ≠ 0        → win
"+++++"    one run of 5:  g(5) = 0             → lose
"++-++++"  runs 2 and 4:  g(2) ^ g(4) = 1 ^ 2 = 3 → win
"++-++"    runs 2 and 2:  g(2) ^ g(2) = 0      → lose

Brute Force

Full-game minimax with memoization: win(state) = any(not win(next)). Correct for any game, impartial or not — but the state is the entire position. Flip game on n chars has up to 2^n reachable states; Nim state space is the product of pile sizes. Composition is invisible to minimax: it re-explores the cross product of subgames.

Brute Force Complexity

  • Time: O(states × moves) — exponential in the number of independent components
  • Space: O(states) memo

Optimization Path

  1. Verify impartial + normal play (the two preconditions — check them out loud).
  2. Decompose the position into independent subgames (Nim piles; maximal + runs in flip game).
  3. Compute g per subgame: mex over successor Grundy values, memoized. A flip in a run of k at offset i splits it into runs of i and k − i − 2 → successor value g(i) ^ g(k − i − 2).
  4. XOR all component Grundy values; nonzero → N position (win).
  5. For pure Nim, skip step 3: g(pile) = pile size, and Bouton gives the move in O(n).

Final Expected Approach

def mex(s):
    g = 0
    while g in s:
        g += 1
    return g

def grundy(state, moves, memo):
    """Generic Sprague-Grundy: moves(state) -> iterable of successor states."""
    if state in memo:
        return memo[state]
    memo[state] = mex({grundy(nxt, moves, memo) for nxt in moves(state)})
    return memo[state]

def nim_winning_move(piles):
    """Bouton: return (pile_index, new_size), or None if this is a P position."""
    x = 0
    for p in piles:
        x ^= p
    if x == 0:
        return None                      # every move loses; no winning move
    for i, p in enumerate(piles):
        if p ^ x < p:                    # p has the highest set bit of x
            return (i, p ^ x)            # after the move, XOR of all piles = 0

FLIP = {0: 0, 1: 0}                      # runs of 0 or 1 '+' have no moves
def flip_run_grundy(k):
    """Grundy number of a maximal run of k consecutive '+' (LC 294)."""
    if k not in FLIP:
        FLIP[k] = mex({flip_run_grundy(i) ^ flip_run_grundy(k - i - 2)
                       for i in range(k - 1)})
    return FLIP[k]

def can_win_flip_game(s):
    """LC 294: True iff the current player has a winning strategy."""
    g, run = 0, 0
    for c in s + '-':                    # sentinel flushes the last run
        if c == '+':
            run += 1
        else:
            g ^= flip_run_grundy(run)
            run = 0
    return g != 0

def nim_first_player_wins(piles):
    """LC 1908 / LC 292-general: N position iff XOR != 0."""
    x = 0
    for p in piles:
        x ^= p
    return x != 0

Grundy values for flip-game runs 0..15: 0 0 1 1 2 0 3 1 1 0 3 3 2 2 4 0 — no obvious period; memoize, don’t guess a formula.

Data Structures

  • Dict memo: state → Grundy value (state must be hashable/canonical)
  • Set of successor Grundy values per state (for mex)
  • Pile array for Bouton — no tree, no search

Correctness Argument

  • mex gives Nim-equivalence: from g(s) = k you can move to every value 0..k−1 (mex guarantees they occur among successors) and never stay at k — exactly the move set of a Nim pile of size k. Moves to values > k exist but don’t help: opponent moves back.
  • XOR for sums (copying strategy): if the XOR of component Grundy values is 0, any move breaks the balance in one component and the opponent restores XOR = 0 (Bouton’s constructive move applied to Grundy values); P positions are preserved, terminal is P, so XOR = 0 characterizes P positions.
  • Bouton is the special case g(pile) = pile size.

Complexity

  • Bouton Nim: O(n) time, O(1) space
  • Flip game: g(k) needs k − 1 successor XORs (O(1) each once smaller values are memoized) plus an O(k) mex → O(L²) total for max run length L, then O(n) to scan the string
  • Generic engine: O(states × branching) time, O(states) space

Implementation Requirements

  • Terminal states must get g = 0 (mex of empty set) — verify your recursion hits this
  • Canonicalize state before memoizing (sort piles; tuples not lists)
  • mex via set membership loop, not min/max
  • Winning move must be validated: resulting XOR = 0
  • Recursion depth: run lengths up to 10^4 need iterative or increased limit in Python

Tests

  • Nim [3,4,5] → win, move (0, 1); [1,2,3] → lose, move is None
  • Exhaustive: all flip-game strings of length ≤ 12 vs memoized minimax on the raw string — must agree
  • Exhaustive: all 3-pile Nim positions with sizes ≤ 6 vs minimax — XOR rule must agree
  • Every winning move returned by Bouton, when applied, yields a brute-force loss for the opponent
  • Generic engine on single Nim pile: g(n) = n; on subtraction game {1,2,3}: g(n) = n mod 4 (LC 292)
  • LC 294: “++++” → True, “+” → False

Follow-up Questions

  • Why XOR and not addition? → XOR is Nim addition: it’s the unique operation making the copying strategy work. From XOR = 0, any move to one component makes XOR ≠ 0; from XOR = x ≠ 0, Bouton’s move restores 0. Addition fails: [1,1] sums to 2 but is a P position.
  • What if you used min or max instead of mex? → min breaks the “reach every smaller value” property; max breaks “can’t stay equal.” mex is exactly what makes g(s) behave as a Nim pile — both directions of the equivalence are needed.
  • Does this work for chess or checkers? → No — those are partisan games (players have different moves). The theory there is Conway’s surreal numbers / combinatorial game theory (On Numbers and Games, Winning Ways). Grundy requires impartiality.
  • Staircase Nim? → Coins on stairs, move coins down one step. Only odd-indexed stairs matter: XOR those pile sizes. Moves on even stairs are mirrored by the opponent.
  • Wythoff’s game? → Two piles; take from one pile or equally from both. P positions are (⌊kφ⌋, ⌊kφ²⌋) — golden ratio. Famous because it’s NOT plain XOR; mex tables reveal the Beatty sequence.
  • When should you skip Grundy and just do minimax? → Small state space, partisan moves, or scoring objectives. Stone Game I/II/III maximize score difference — that’s minimax DP (phase-05), and Grundy theory says nothing about scores.

Product Extension

  • Game AI for turn-based games: endgame solvers and perfect-play databases
  • Puzzle apps: hint engines that must produce a move, not just “you’re losing”
  • CS education platforms: auto-graders for game-theory assignments need reference strategies
  • Combinatorial auction / mechanism toy models occasionally reduce to game values

Language/Runtime Follow-ups

  • Python: functools.lru_cache on a tuple state is idiomatic; recursion limit bites at depth ~1000 — precompute run Grundy values bottom-up for large inputs.
  • C++: memo via unordered_map or flat arrays; mex via a boolean scratch array is faster than a set.
  • Java: HashMap<Long, Integer> with packed state; watch autoboxing in hot loops.
  • All: XOR of pile sizes up to 10^9 fits any 64-bit int; no overflow concerns.

Common Bugs

  1. mex computed as min or max: the classic. mex({1, 2}) = 0, not 1 or 2.
  2. XORing raw sizes in non-Nim games: g(state) equals the pile size only in pure Nim. In flip game, XOR the Grundy values of runs, never the run lengths.
  3. Terminal position mishandled: mex(∅) = 0 must fall out naturally; special-casing it to −1 or 1 poisons everything upstream.
  4. Misère treated as normal play: “last player to move loses” flips the answer only near the end — for Nim, deviate from Bouton only when the move would leave all piles ≤ 1.
  5. Split off-by-one: flipping at offset i in a run of k leaves runs of i and k − i − 2 (the two flipped chars vanish), for i in 0..k−2. Writing k − i − 1 passes small cases and fails at k = 4.
  6. Non-canonical memo keys: memoizing [2,1] and [1,2] separately wastes memory; memoizing a mutated list corrupts the cache.

Debugging Strategy

  • Print the Grundy table g(0..20) for each subgame type; check g = 0 exactly at hand-verified P positions
  • Diff Grundy-predicted win/lose against raw minimax on every instance small enough to enumerate — this catches all composition bugs
  • Validate every claimed winning move by applying it and asserting the resulting position has XOR 0
  • If Grundy values look periodic, test the conjectured period 3× further before relying on it

Mastery Criteria

  • State and prove Bouton’s theorem (both directions) in ≤ 10 min
  • Implement the generic mex/Grundy engine from scratch in ≤ 15 min
  • Solve LC 294 via segment decomposition in ≤ 25 min
  • Produce the winning Nim move, not just the verdict, in ≤ 5 min
  • Correctly classify a new game as impartial-normal (Grundy), misère (careful), or partisan/scoring (minimax) in ≤ 3 min
  • Explain why Stone Game I–III are NOT Grundy problems