Skip to content
Tutorials Center
My learning

Topics

Lesson 203 of 225 Β· Advanced Topics

Game Theory: Nim and Sprague-Grundy

Solve two-player games in Python with winning and losing positions, minimax, Nim and the XOR rule, and Grundy numbers with mex for sums of games.

Many interview and contest problems are really small games: two players take turns, both play perfectly, and you must say who wins. "Take 1 to 3 stones from a pile", "remove a number from either end of an array", "split a pile into two". The surprise is that you rarely have to simulate the whole game tree. A few ideas, winning and losing positions, minimax, the Nim XOR rule and Grundy numbers, solve a huge family of them in a few lines.

In this lesson we only consider impartial, finite games with perfect information: both players have the same moves available from any position, nobody hides information, nothing is random, and the game must end. The player who cannot move loses (this is called normal play). The tools build on recursion, memoization and bit manipulation.

Winning and losing positions

Label every position from the point of view of the player about to move:

  • A position is losing (a P-position, "previous player wins") if every move leads to a winning position for the opponent. A position with no moves is losing.
  • A position is winning (an N-position, "next player wins") if at least one move leads to a losing position.

That is a recursive definition, and it is easy to turn into code with a cache. Let us solve the "take 1, 2 or 3 stones" game.

flowchart LR
    S0["0 stones<br/>LOSE"] --> S1["1<br/>WIN"]
    S0 --> S2["2<br/>WIN"]
    S0 --> S3["3<br/>WIN"]
    S1 --> S4["4<br/>LOSE"]
    S2 --> S4
    S3 --> S4

From 4 stones every move leaves 1, 2 or 3, all winning for the opponent, so 4 is losing.

Python Take 1, 2 or 3 stones

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The losing piles are the multiples of 4. The pattern is a strategy: always take enough to leave a multiple of 4. Whenever a game has a simple answer like this, brute force on small inputs is the fastest way to discover it.

Minimax: when the game has a score

Sometimes players do not just win or lose, they collect points. Then each player tries to maximize their own advantage while the other tries to minimize it. Define best(position) as "my score minus the opponent's score if I move first". After my move the roles swap, so the opponent's best is subtracted:

TEXT
best(state) = max over moves of ( gain(move) - best(next_state) )

This negamax form is minimax written once for both players. A classic example: two players take numbers from either end of an array, and each wants the larger total.

Python Taking from either end of an array

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

There are only O(n^2) intervals (lo, hi), so the memoized recursion runs in O(n^2) time rather than the O(2^n) of the raw game tree. It is the same shape as interval DP.

Nim and the XOR rule

Nim is the mother of impartial games. There are several piles of stones. A move removes any positive number of stones from one pile. The player who takes the last stone wins.

Charles Bouton proved in 1901 that the position is losing for the player to move if and only if the XOR of all pile sizes is 0 (the nim-sum). The intuition has two halves:

  1. If the nim-sum is 0, any move changes exactly one pile, so the nim-sum becomes non-zero.
  2. If the nim-sum s is non-zero, look at the highest set bit of s. Some pile has that bit set; shrinking that pile to pile ^ s makes the nim-sum 0 again, and pile ^ s < pile, so it is a legal move.

So the winner is decided by one XOR, and the winning move can be computed directly.

Python Nim: who wins and what to play

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check [1, 2, 3]: 1 ^ 2 ^ 3 is 0, so the player to move loses, whatever they do.

Grundy numbers and the mex

Most games are not plain Nim, but many of them behave like Nim piles. The Sprague-Grundy theorem says every position of an impartial game is equivalent to a single Nim pile of some size, its Grundy number (or nim-value):

TEXT
grundy(position) = mex { grundy(next) for every move }

mex ("minimum excluded value") is the smallest non-negative integer that is not in the set. A position with no moves has Grundy number 0 (mex of the empty set). A position is losing exactly when its Grundy number is 0.

The real power is for sums of games. If a game splits into independent parts (several piles, several boards), the Grundy number of the whole is the XOR of the Grundy numbers of the parts. You compute each part separately and XOR, exactly as in Nim.

Python Grundy numbers for a subtraction game

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Grundy values of a subtraction game are often periodic, so for huge piles you can compute a prefix, spot the period, and answer in O(1).

A game that is not a plain subtraction

The same recipe handles other move rules. In "split a pile into two different non-empty piles", a move from size n produces two piles, and the Grundy number of the result is the XOR of the two parts. You just put grundy(a) ^ grundy(b) into the mex set.

Python Splitting piles into unequal parts

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two identical piles always XOR to 0, a fact known as the mirror strategy: whatever your opponent does in one copy, you repeat in the other.

A recipe for game problems

  1. Define the state and what a move does. Make sure the game ends.
  2. Decide whether the game is plain win/lose (use the winning/losing recursion or Grundy numbers) or scored (use negamax).
  3. Brute-force small sizes with memoization and print the table. Look for periodicity or a simple formula.
  4. If the game falls apart into independent pieces, compute a Grundy number per piece and XOR them.
  5. For misère games (the player who takes the last stone loses) the rules change slightly: Nim-sum logic still works with a small correction when all piles are of size 1, but Grundy theory does not apply directly.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. In a normal-play impartial game, when is a position winning for the player to move?

    A winning position has at least one move into a losing position. A position whose moves all lead to winning positions (or that has no moves) is losing.
  2. 2. The piles in a Nim game are 5, 6 and 3. Who wins with perfect play?

    5 ^ 6 = 3 and 3 ^ 3 = 0. The nim-sum is 0, so the player to move loses with perfect play by the opponent.
  3. 3. What is mex({0, 1, 3})?

    The mex is the smallest non-negative integer not in the set. 0 and 1 are present, 2 is missing.
  4. 4. A game consists of two independent boards with Grundy numbers 5 and 5. What is the Grundy number of the whole game?

    The Grundy number of a sum of games is the XOR of the parts. 5 ^ 5 = 0, so the player to move loses (the second player can mirror).

Summary

  • A position is losing if every move leads to a winning one (no moves counts as losing); it is winning if some move reaches a losing position. Memoize the recursion.
  • For scored games use negamax: best = max(gain - best(next)), often as interval DP.
  • Nim: the player to move loses exactly when the XOR of the pile sizes is 0; the winning move reduces a pile p to p ^ s.
  • Grundy number = mex of the Grundy numbers of the next positions; 0 means losing.
  • A sum of independent games has Grundy number equal to the XOR of its parts.
  • Tabulate small cases first and look for a pattern or period.

Next: Celebrity Problem and Skyline, two classic elimination and sweep-line puzzles.