Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 63 ยท Strings and Games

Game Theory

Solve contest games: label winning and losing states, compute Grundy numbers, add independent games with XOR, recognize Nim variants and use symmetry strategies, all verified by brute force.

Game problems in contests have a recognizable form: two players alternate moves, both play perfectly, and you must say who wins from a given start, or which first move wins. Because play is perfect, there is no probability and no guessing, only a clean logical structure. The trick is to stop thinking about "what would a clever player do next" and start labeling positions. Once every position is labeled winning or losing for the player to move, the answer is a lookup.

This lesson covers the three tools that solve almost every contest game. First, winning and losing states and how to compute them by DP. Second, the Sprague-Grundy theorem, which lets you split a game into independent parts and combine them with XOR. Third, symmetry strategies, which sometimes prove a result without any computation. We always check theory against a brute force, the same discipline as in stress testing. The XOR facts used here are reviewed in bit tricks and XOR problems.

Winning and losing positions

We consider normal play: the player who cannot move loses. Every position then has exactly one label, determined by this rule:

  • A position is losing (for the player to move) if every move leads to a winning position, or if there are no moves.
  • A position is winning if at least one move leads to a losing position.
flowchart LR
  P0["0 stones<br/>no moves: LOSING"] --> W1["1 stone<br/>move to 0: WINNING"]
  W1 --> W2["2 stones<br/>moves to 1 only: LOSING"]
  W2 --> W3["3 stones<br/>move to 2: WINNING"]

Labels flow upward from the end of the game: a position that can reach a losing one is winning.

Take the subtraction game: a pile of n stones, and on each turn a player removes 1, 3 or 4 stones. For small n a table does the whole job. Compute positions in increasing order of n, since moves only go to smaller piles.

Python Win/lose table 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.

The losing positions are 0, 2, 7, 9, 14 and 16, and the pattern of labels repeats every 7 positions. In a contest with huge n you would find this pattern by printing the table, check it with a brute force, and then answer with n % 7. This "compute small cases, find the pattern" method is the one from ad hoc and constructive problems.

Nim and the XOR rule

Nim has several piles. A move removes any positive number of stones from a single pile. The player who takes the last stone wins. The theorem of Bouton says: XOR all pile sizes together. If the result is non-zero, the player to move wins; if it is zero, the player to move loses.

Why? From a position with XOR zero, any move changes exactly one pile, so the XOR becomes non-zero. From a position with a non-zero XOR, there is always a move that makes it zero: look at the highest set bit of the XOR, choose a pile that has that bit set, and reduce it to pile ^ xor. So zero-XOR positions only lead to non-zero ones and non-zero ones can reach a zero one, which is exactly the definition of losing and winning.

Grundy numbers and the Sprague-Grundy theorem

Nim is special only because it is the simplest case. Every impartial game (both players have the same moves from every position) behaves like some Nim pile. The size of that equivalent pile is the position's Grundy number:

grundy(position) = mex { grundy(next) for each move }

where mex (minimum excluded value) is the smallest non-negative integer missing from the set. A position is losing exactly when its Grundy number is 0. The powerful part is the sum rule: if a game is played on several independent components, where a move touches exactly one component, the Grundy number of the whole is the XOR of the components' numbers.

So the recipe for a multi-part game is: (1) compute the Grundy number of one component, (2) XOR the results, (3) non-zero means the first player wins.

Python Grundy numbers and a brute-force check of Nim

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.

For the subtraction set {1, 2, 3} the Grundy numbers are simply n % 4, which is why that game is won by leaving a multiple of 4. A different move set gives a different cycle, which is why you compute the table instead of guessing.

Nim variants

Contest authors disguise Nim in many ways. Learn to recognize the family.

  • Limited moves from one pile. If a move may take at most k stones, the single-pile Grundy number is n % (k + 1).
  • Splitting games. A move removes tokens and may split a pile into two independent piles. Kayles (knock down one pin or two neighboring pins from a row) is the classic. The Grundy number of a row of length n is the mex of g[a] ^ g[b] over every way to leave segments a and b.
  • Staircase Nim. Moving coins down a staircase reduces to Nim on the odd-numbered steps only, because the opponent can undo any move on an even step.
  • Misรจre Nim (the last mover loses) differs from normal play only when every pile has size 1 or 0. Otherwise play as in normal Nim.
  • Hidden reduction. Many problems are a set of independent subgames (rows, trees, cycles). Find the component, compute its Grundy number by brute force on small sizes, and XOR them.
Python Kayles: Grundy numbers confirmed by brute force

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.

Symmetry strategies

Sometimes no computation is needed. If the second player can always answer a move with a "mirror" move that restores a symmetric position, then the second player never runs out of moves before the first does, and wins.

A classic: coins are placed around a circular table of n coins, and on each turn a player removes either one coin or two adjacent coins. For n of 1 or 2 the first player simply takes everything. For n >= 3, after the first move the remaining coins form a single row, and the second player removes the one or two coins at the exact center so that two rows of equal length remain. From then on the second player copies every move on the opposite side. Since each first-player move can be mirrored, the second player takes the last coins.

flowchart TD
  S["Circle of n coins (n at least 3)"] --> F["First player removes 1 or 2<br/>leaving one row"]
  F --> C["Second player removes the center<br/>leaving two equal rows"]
  C --> M["Mirror every move on the other row"]
  M --> W["Second player makes the last move"]

Symmetry proves the second player wins without searching the game tree.

A proof by strategy should still be checked on small cases. This TryIt searches the circle game exhaustively.

Python Symmetry claim checked by exhaustive search

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 output matches the argument: the first player wins only for 1 and 2 coins, and the second player wins from 3 up. If your symmetry idea fails the exhaustive check, the mirror move is not always legal. Look for a position where it is missing, such as a move in the exact center that has no mirror image.

Games with scores: minimax as dynamic programming

Win/lose labels answer "who wins?". Many problems ask "what is the best score each player can force?" while both play optimally. The state then needs the part of the game that remains (a segment of an array, a number of stones, a pair of piles), and the value of a state is a score difference seen from the player to move.

The trick that keeps the recurrence short: define dp[state] as (mover's total) - (opponent's total) from this state onwards. If the mover takes an item worth x and leaves next_state, the opponent becomes the mover there and gains dp[next_state] over the original mover. So the mover's net result is x - dp[next_state], and the mover chooses the best option:

dp[state] = max over moves of (x - dp[next_state])

This one formula replaces two interleaved tables (one for each player) and works for every "players alternate, both play optimally, scores add up" game.

Recognizing the problem. Look for: two players taking turns, perfect play, a finite game whose states repeat (segments, counts), and a score or a yes/no result. Define the state by what is left, not by the history. Check that every move shrinks the state, so the table can be filled from small states to large ones; for segments, fill by increasing length.

The classic example is a row of coins where each player takes the leftmost or the rightmost coin. The state is the segment [l, r], and dp[l][r] = max(a[l] - dp[l+1][r], a[r] - dp[l][r-1]). The first player can force at least a tie exactly when dp[0][n-1] >= 0. The table has O(n^2) states and O(1) work per state. Compare with the Sprague-Grundy approach: that theory is for games where only "who wins" matters and the game splits into independent parts, while this DP is the tool when scores matter or the game is a single connected structure.

Python Optimal play with scores: coins from either end

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.

A workflow for game problems

  1. Define a position exactly (what information decides the future?).
  2. Write the brute-force win/lose search for tiny positions.
  3. Print a table of results and look for a pattern, a period, or a XOR structure.
  4. If the game splits into independent parts, compute Grundy numbers per part.
  5. Verify the final formula against the brute force with random small cases, as in stress testing.
  6. Only then write the fast solution, and watch for edge cases like n = 0, covered in edge cases and pitfalls.

If the game is not impartial (each player has different moves, as in chess), Sprague-Grundy does not apply. Then you usually need a direct DP over positions with the minimax rule, or the theory of partisan games, which is outside this lesson.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In normal-play Nim with piles 3, 5 and 6, who wins?

    3 ^ 5 = 6, and 6 ^ 6 = 0. A zero XOR is a losing position for the player to move, so the second player wins.
  2. 2. What is the Grundy number of a position whose moves lead to positions with Grundy numbers 0, 1 and 3?

    The mex is the smallest non-negative integer missing from {0, 1, 3}, which is 2.
  3. 3. Two independent games have Grundy numbers 5 and 5. What does the combined game look like for the first player?

    Independent components combine with XOR. 5 ^ 5 is 0, so the combined position is losing for the player to move.
  4. 4. Which condition must hold for the Sprague-Grundy theorem to apply?

    The theorem is about impartial games, where the available moves depend only on the position, not on whose turn it is.
  5. 5. Why should you verify a symmetry strategy by exhaustive search on small cases?

    The proof only holds if the mirror response is always available. A small exhaustive check quickly exposes positions where it is not.

Summary

  • Label positions by the rule: a position is winning if some move reaches a losing position, and losing otherwise (including having no moves).
  • Nim is won by the player who can make the XOR of the pile sizes zero; a zero XOR is losing for the player to move.
  • The Grundy number is the mex of the options' Grundy numbers; independent components combine with XOR.
  • Recognize Nim variants (limited moves, splitting games like Kayles, staircase Nim) and compute Grundy tables from a brute force.
  • Symmetry strategies can prove a winner with no computation; confirm them on small cases.
  • For any game problem, start with a brute force, find the pattern in a table, then verify the formula.

Next: Project: A Local Contest Judge