Game Theory, Nim, and Sprague-Grundy: Winning Combinatorial Games

Algorithm/Topic Statement#

Combinatorial game theory analyzes two-player games of perfect information with no chance, where players alternate moves and the last move determines the winner. The simplest example is Nim, in which several piles of stones sit on a table and each turn a player removes any positive number of stones from exactly one pile, with the last player to move declared the winner. The astonishing result is that the winner can be predicted without playing the game. The first player wins if and only if the bitwise XOR of all pile sizes is nonzero. The Sprague-Grundy theorem generalizes this to any impartial game by assigning each position a Grundy number, also called a nimber, equal to the mex of the Grundy numbers of all reachable positions. Composite games combine via XOR of their components.

Why This Topic Matters#

Game theory questions are a staple of competitive programming and quantitative interviews. Codeforces, ICPC, and Google Code Jam all feature Nim variants regularly. Even classic LeetCode problems like Stone Game, Predict the Winner, and Stone Game IV reduce to game theory once you spot the pattern. Beyond contests, the same techniques appear in algorithmic trading where you reason about adversarial play, in security where attacker and defender games are common, and in artificial intelligence where minimax forms the foundation of game-playing agents. Mastering game theory builds a powerful mental model: any deterministic two-player game with finite state has a winner-loser classification that can be computed bottom up, even when the game tree is huge.

The Core Insight (math intuition + proof sketch)#

The intuition behind Nim's XOR rule is symmetry. Every losing position, called a P-position, has XOR equal to zero. Every winning position, called an N-position, has XOR nonzero. The proof is by induction. Base case: the all-zero position has XOR zero and offers no moves, so it is a loss for the player to move. Inductive step: from any nonzero XOR position, you can find at least one move that produces an XOR-zero position, which by induction is a loss for the opponent. Conversely, from any zero XOR position every move produces a nonzero XOR position, so the opponent can always recover. The mechanism is that XOR of all piles after the move equals the original XOR XORed with the change in the chosen pile, and you can always choose a new pile size that cancels the original XOR.

The Sprague-Grundy theorem extends this to any impartial game. Define Grundy of state S as the mex, the minimum excludant, of the Grundy values of all states reachable in one move from S. The base position with no moves has Grundy zero. A position is a loss exactly when its Grundy value is zero. For a sum of independent games, the Grundy value of the combined game equals the XOR of the Grundy values of the components. The proof reduces every impartial game to a Nim pile of size equal to its Grundy value, allowing the standard XOR analysis to carry over. This abstraction is breathtaking: dozens of seemingly different games turn out to be the same game in disguise.

Visual Dry Run / Worked Example#

Consider Nim with three piles of sizes 3, 4, and 5. The XOR is 3 XOR 4 XOR 5. In binary, 3 is 011, 4 is 100, and 5 is 101. XOR them column by column to get 010, which equals 2. Since the XOR is nonzero, the first player wins. The optimal move makes the XOR zero. Look for any pile p such that p XOR 2 is less than p. Here, 5 XOR 2 equals 7, which is greater than 5, so we cannot reduce pile three. Try 4 XOR 2 equals 6, greater than 4, no good. Try 3 XOR 2 equals 1, less than 3, perfect. Reduce pile one from 3 to 1 and the new piles are 1, 4, 5 with XOR 1 XOR 4 XOR 5 equal to zero. Whatever the opponent does, the resulting XOR becomes nonzero again, and the first player keeps restoring it to zero until all piles are empty.

For a Grundy walkthrough, take the subtraction game where each turn you remove 1, 2, or 3 stones. Compute Grundy of n for small n. Grundy 0 is mex of empty set which is 0. Grundy 1 is mex of Grundy 0 which is 1. Grundy 2 is mex of Grundy 0, Grundy 1 which is 2. Grundy 3 is mex of Grundy 0, 1, 2 which is 3. Grundy 4 is mex of Grundy 1, 2, 3 which is 0. The pattern is Grundy n equals n mod 4. So a single pile of size n is a loss if and only if n is divisible by 4. This explains the LeetCode Nim Game answer: return n mod 4 not equal to zero.

Solution / Implementation#

Python (Nim, Grundy with mex, composite games)#

def nim_winner(piles):
    xor_sum = 0
    for p in piles:
        xor_sum ^= p
    return xor_sum != 0
 
def nim_optimal_move(piles):
    xor_sum = 0
    for p in piles:
        xor_sum ^= p
    if xor_sum == 0:
        return None
    for i, p in enumerate(piles):
        target = p ^ xor_sum
        if target < p:
            return i, target
    return None
 
def grundy_subtraction(state, allowed, memo=None):
    if memo is None:
        memo = {}
    if state in memo:
        return memo[state]
    reachable = set()
    for take in allowed:
        if take <= state:
            reachable.add(grundy_subtraction(state - take, allowed, memo))
    mex = 0
    while mex in reachable:
        mex += 1
    memo[state] = mex
    return mex
 
def composite_winner(states, grundy_fn):
    total = 0
    for s in states:
        total ^= grundy_fn(s)
    return total != 0

JavaScript#

function nimWinner(piles) {
  let x = 0;
  for (const p of piles) x ^= p;
  return x !== 0;
}
 
function grundySubtraction(state, allowed, memo = new Map()) {
  if (memo.has(state)) return memo.get(state);
  const reachable = new Set();
  for (const take of allowed) {
    if (take <= state) reachable.add(grundySubtraction(state - take, allowed, memo));
  }
  let mex = 0;
  while (reachable.has(mex)) mex++;
  memo.set(state, mex);
  return mex;
}
 
function canWinNim(n) {
  return n % 4 !== 0;
}

Computing the XOR or single Nim verdict is order n in pile count. Grundy memoization is order S times moves, where S is the state space and moves is the branching factor.

Common Mistakes#

Forgetting that Sprague-Grundy applies only to impartial games is a frequent error. If the two players have different move options, like white versus black in chess, you need a different framework called partizan game theory or Surreal Numbers. Another mistake is computing Grundy values without memoization on a recursive game with overlapping subproblems, which causes exponential blowup. Always cache. Many candidates also misapply the XOR rule to games that look like Nim but are not, for example games where the loser is the one who runs out of moves under misère convention. The classical XOR rule covers normal play; misère versions require small adjustments. Finally, when computing mex, do not forget the case where all reachable Grundy values are zero, which yields a Grundy of one, not zero.

Interview Tips#

When you see a two-player game with stones, piles, or tiles, immediately check whether it is impartial. If yes, suspect Sprague-Grundy. Sketch the smallest cases by hand to spot a Grundy pattern, like n mod something. If the pattern is regular, you have a closed-form answer; otherwise fall back to memoized recursion. For the Stone Game family on LeetCode, set up a minimax DP with state describing whose turn it is and the remaining piles. Always state the assumption of optimal play out loud. Mention misère versus normal play if the win condition is unusual. Demonstrating this fluency separates strong candidates from those who only know minimax.

Follow-up Questions#

How would you compute the misère Nim outcome, and why does it differ from normal Nim? Can you implement Grundy values for the game of Wythoff and explain its connection to the golden ratio? What changes in Sprague-Grundy when moves can leave more than one pile, like splitting? Could you analyze a game where players have private information using a different framework?

Key Takeaways#

• Nim is solved by XORing all pile sizes; the first player wins if and only if the XOR is nonzero.
• The Sprague-Grundy theorem assigns every impartial game position a Grundy number equal to the mex of reachable positions.
• A position is a loss exactly when its Grundy value is zero; composite games XOR their component Grundy values.
• Always memoize Grundy computations and watch for partizan or misère variants that need different theory.
• Spotting the Grundy pattern from small cases often yields closed-form answers in O(1).
• Game theory is required for competitive programming, quantitative interviews, and any adversarial reasoning task.