Combinatorial Game Theory | Set 4 (Sprague - Grundy Theorem)

Combinatorial game theory is a fascinating area of mathematics that deals with games with perfect information, no chance elements, and two players who take turns making moves. In such games, the Sprague - Grundy Theorem is a fundamental result. It provides a way to analyze complex games by breaking them down into simpler sub - games. This blog post will explore the Sprague - Grundy Theorem in detail, including its definition, how it works, and its applications.

Table of Contents#

  1. What is the Sprague - Grundy Theorem?
  2. Grundy Numbers (Nimbers)
  3. How the Sprague - Grundy Theorem Works
  4. Example Usage
  5. Common Practices and Best Practices
  6. References

1. What is the Sprague - Grundy Theorem?#

The Sprague - Grundy Theorem states that every impartial combinatorial game (a game where the available moves depend only on the position and not on which player is moving) is equivalent to a Nim heap. In other words, any such game can be assigned a non - negative integer value called the Grundy number (or Nimber), and the outcome of a sum of such games (where players can move in any of the component games on their turn) can be determined by the XOR (exclusive - OR) of the Grundy numbers of the component games.

2. Grundy Numbers (Nimbers)#

The Grundy number (g(x)) of a position (x) in a game is defined recursively.

  • For a terminal position (a position where no moves are possible), (g(x)=0).
  • For a non - terminal position (x), (g(x)) is the mex (minimum excludant) of the Grundy numbers of all positions reachable from (x) in one move. The mex of a set (S) of non - negative integers is the smallest non - negative integer not in (S).

For example, consider the game of Kayles. In Kayles, we have a row of pins, and a move consists of knocking down one or two adjacent pins. Let's find the Grundy number for a single pin.

  • The only move from a single pin is to knock it down (resulting in a terminal position). So, the set of reachable positions is ({0}). The mex of ({0}) is (1). So, (g(1) = 1).

For two adjacent pins, the possible moves are:

  • Knock down one pin (resulting in a single pin with (g = 1))
  • Knock down two pins (resulting in a terminal position with (g=0)) The set of reachable Grundy numbers is ({0,1}). The mex of ({0,1}) is (2). So, (g(2)=2)

3. How the Sprague - Grundy Theorem Works#

Let's say we have two games (G_1) and (G_2) with Grundy numbers (g_1) and (g_2) respectively. When we play the sum of these two games (a player can make a move in either (G_1) or (G_2) on their turn), the Grundy number of the combined game is (g_1\oplus g_2) (where (\oplus) is the XOR operation).

The key idea is that if the XOR of the Grundy numbers of all component games is non - zero, the first player has a winning strategy. If it is zero, the second player has a winning strategy.

4. Example Usage#

Example: Nim - like Game Suppose we have three piles of stones: pile (A) with (3) stones, pile (B) with (4) stones, and pile (C) with (5) stones. In the game of Nim, a move consists of taking any number of stones from a single pile.

  • The Grundy number of a pile with (n) stones in Nim is (n) itself.
  • The XOR of the Grundy numbers: (3\oplus4\oplus5=(011)_2\oplus(100)_2\oplus(101)_2=(010)_2 = 2) (in binary). Since the result is non - zero ((2\neq0)), the first player has a winning strategy.

Example: Combining Games Let's consider a game that is a combination of Kayles and Nim. Suppose we have a row of (3) pins (Kayles part) with (g_{Kayles}(3)) (we need to calculate it first). Let's assume (g_{Kayles}(3) = 3) (after proper calculation using the mex rule). And we have a Nim pile with (2) stones ((g_{Nim}(2)=2)). The combined game's Grundy number is (3\oplus2=(11)_2\oplus(10)_2=(01)_2 = 1). So, the first player can win if they play optimally.

5. Common Practices and Best Practices#

  • Calculating Grundy Numbers:
    • For simple games, use the recursive mex definition. For more complex games, look for patterns or use dynamic programming.
    • Memoization is a best practice. Store the calculated Grundy numbers for positions to avoid redundant calculations.
  • Analyzing Game Sums:
    • Always check the XOR of the Grundy numbers of component games.
    • When teaching or learning, start with small, simple games (like Nim with a few piles) to build intuition.

6. References#

  • Combinatorial Game Theory by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy.
  • Online resources like the Combinatorial Game Theory section on the Wikipedia and various math blogs dedicated to game theory.
2026-07