Sprague-Grundy numbers

Why this matters when you build with AI

Many AI products run several small tasks in parallel: a planner that books a room, a second agent that checks a document, a third that sends a message. Each task has its own state and its own moves, and the tasks do not interact. A question you will meet is "given the state of every task, can the system still reach a finished state no matter what the other side does?" This is a two-player question, and the answer for a sum of independent parts can be computed without searching the combined state.

The method in this lesson is the Sprague-Grundy theory. It gives each single task one number, its Grundy value, and says that the whole system is a losing position for the player to move exactly when the XOR of those numbers is 0. XOR is the bitwise exclusive-or of two numbers, written ^ in C++ and Python. The gain is speed: you add up small numbers instead of searching every combination of tasks.

The risk is treating the shortcut as a fact about any game. The rule only holds for games where the parts are independent, every move is in one part, and the game ends. If the parts share a resource, the shortcut can give a confident wrong answer. In the mistakes section you will see a wrong rule that broke on 187 of 819 small cases in my test. Always check a shortcut against a brute-force search on small inputs before you trust it.

The idea: mex and Grundy values

Start with the rules that make a game. Two players take turns. A move changes the position. A player who cannot move loses. This is called normal play. A position is a P-position when the player to move loses with best play, and an N-position when the player to move wins. The last lesson of this module covers winning and losing positions in detail, so here we only need the two words.

The Grundy value of a position is computed from its options. An option is any position you can reach in one move. The Grundy value is the mex of the option values, where mex means "minimum excluded value": the smallest non-negative integer that is not among the option values.

Some examples of mex:

• mex{} is 0. A position with no moves has no options, so its value is 0.
• mex{0} is 1. The value 0 is taken, so the smallest free value is 1.
• mex{1, 0, 3} is 2. Values 0 and 1 are taken, and 2 is missing.
• mex{1, 2} is 0. The value 0 is missing, so it is the answer.

A position with Grundy value 0 is a P-position. Its options all have a value different from 0, so each of them is a win for the opponent. A position with a nonzero value has an option of value 0, which is a losing move for the opponent. This is the whole idea. The rest of the lesson shows that it still works when many independent games are added together.

A worked example: take-and-split

Here is a game I made for this lesson, called take-and-split. You have a heap of n stones. One move is one of the following:

• (a) take 1 stone, leaving n - 1;
• (b) take 2 stones, leaving n - 2;
• (c) take 2 stones and split the other n - 2 stones into two non-empty heaps a and b, with a + b = n - 2.

A heap with 0 stones has no move. Option (c) needs at least 4 stones, because each of the two new heaps needs one stone.

To find g(n), list the option values of n, then take the mex. Work through the first few heaps by hand:

• g(0) = 0. No moves.
• g(1). Option (a) leaves 0, with value 0. Options: {0}. Mex is 1. So g(1) = 1.
• g(2). Option (a) leaves 1 (value 1). Option (b) leaves 0 (value 0). Options: {1, 0}. Mex is 2. So g(2) = 2.
• g(3). Option (a) leaves 2 (value 2). Option (b) leaves 1 (value 1). Option (c) needs 4 stones, so none. Options: {2, 1}. Mex is 0. So g(3) = 0.
• g(4). Option (a) leaves 3 (value 0). Option (b) leaves 2 (value 2). Option (c) splits 2 stones into 1 and 1, with value g(1) ^ g(1) = 0. Options: {0, 2}. Mex is 1. So g(4) = 1.
• g(5). Option (a) leaves 4 (value 1). Option (b) leaves 3 (value 0). Option (c) splits 3 stones into 1 and 2, with value g(1) ^ g(2) = 1 ^ 2 = 3. Options: {1, 0, 3}. Mex is 2. So g(5) = 2.

The split option does not have a single value. Its value is the XOR of the two new heaps, because the two heaps are independent games. This is the first place where the XOR rule shows up, and the next section proves it.

The table for n from 0 to 5 is 0 1 2 0 1 2. The program below prints the table up to 30, and the same numbers come out of the Python snippet at the end of the next section.

Why a sum of games adds with XOR

A sum of games is a position made of several independent games. A move changes exactly one of them, and the player who cannot move loses. Let the Grundy values of the parts be x_1, ..., x_k. Let S be their XOR.

Claim. The sum is a P-position if and only if S = 0.

The proof uses two facts about mex.

Fact 1. A value is never an option value of a position with the same value. The Grundy value of a position is the mex of its options, so it is not in the option set.

Fact 2. Every value smaller than the mex is an option value. That is the meaning of "smallest excluded".

Part A: from S = 0, every move leads to S != 0. Suppose the total XOR is 0. A move changes one part, say part i, from value x_i to an option value y. By Fact 1, y differs from x_i. The new XOR is S' = y ^ x_i ^ S = y ^ x_i, which is nonzero because y != x_i. So no move keeps the XOR at 0.

Part B: from S != 0, some move leads to S = 0. Let b be the highest bit set in S. Some part value x_i has bit b set, because otherwise bit b would be 0 in S. Let R be the XOR of the other parts. Then S = x_i ^ R. Set v = x_i ^ S = R. Bit b is set in x_i and cleared in v, and the bits above b are the same in both. So v < x_i. By Fact 2, v is an option value of part i, so there is a move in part i that makes its value v. The new total XOR is v ^ R = 0.

Conclusion. The game is finite, so we can use induction on the number of moves that remain. A sum with S = 0 has no move to another S = 0 sum (Part A), and every move leads to S != 0. A sum with S != 0 has a move to S = 0 (Part B). With no moves left, the sum has S = 0 and the player to move loses. So the sum is a P-position exactly when S = 0.

This proof is about who wins, not about the Grundy value of the sum itself. The full theorem also says the Grundy value of the sum is the XOR of the parts, and the same mex argument proves that. This lesson only needs the winner, so it does not go further.

A plain example: two heaps with values 2 and 2 give XOR 0, so the player to move loses. Any move changes one heap, and the heap's new value differs from 2, so the XOR becomes nonzero. Whatever the opponent does, the first player can restore XOR 0 with one move.

Finding the winner and a winning move

Given heaps h_1, ..., h_k, the solver does three steps:

1. Compute S, the XOR of g(h_i) over all heaps.
2. If S = 0, print second. The player to move loses.
3. Otherwise, find a heap i with target = g(h_i) ^ S smaller than g(h_i). Then find an option of h_i with value target. Making that move gives a total XOR of 0.

The bit argument from Part B says such a heap always exists. The test target < g(h_i) is how you find the heap that carries the top bit. For a heap that fails the test, the target is larger, and there may be no option with that value, so the solver must not try it.

Worked problem: take-and-split sums

Statement (my own). The input has k heaps, with 1 <= k <= 3 and each heap size from 0 to 200. Print second if the player to move loses with best play. Otherwise print first, followed by one winning move in the form heap i (size n) becomes ..., where the pieces are the sizes after the move. A zero piece means the heap disappears.

Input format. The first line is k. The second line has the k heap sizes.

Sample run. The program below was compiled with g++ -std=c++17 -O2 -Wall -Wextra and run in my scratch folder. Output for the inputs in the comments:

$ ./sum_winner table
g(0) = 0
g(1) = 1
g(2) = 2
g(3) = 0
g(4) = 1
g(5) = 2
g(6) = 3
...
g(29) = 0
g(30) = 1
 
$ printf "1\n5\n" | ./sum_winner        # g(5) = 2
first
heap 1 (size 5) becomes 3
 
$ printf "2\n5 3\n" | ./sum_winner     # g(5) = 2, g(3) = 0, XOR = 2
first
heap 1 (size 5) becomes 3
 
$ printf "3\n1 2 3\n" | ./sum_winner   # 1 ^ 2 ^ 0 = 3
first
heap 2 (size 2) becomes 1
 
$ printf "2\n4 4\n" | ./sum_winner     # 1 ^ 1 = 0
second

Lines g(7) to g(28) are left out of the listing above. Running the program prints all of them. For the sum 2 5 3, the move to size 3 gives heaps 3 and 3, with XOR 0. For the sum 4 4 the program prints second, which matches the rule.

// Take-and-split game: Grundy table and winner of a sum of heaps.
// Moves on one heap of n stones:
//   (a) take 1 stone        -> n - 1
//   (b) take 2 stones       -> n - 2
//   (c) take 2 stones and split the other n - 2 into two non-empty heaps a and b
// Usage:
//   ./sum_winner table          prints g(n) for n = 0..30
//   ./sum_winner                reads k, then k heap sizes; prints first/second and a winning move
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 200;
int g[MAXN + 1];
 
// Smallest non-negative integer that is not in vals.
int mex(const vector<int>& vals) {
    vector<char> seen(vals.size() + 2, 0);
    for (int v : vals)
        if (v < (int)seen.size()) seen[v] = 1;
    int m = 0;
    while (seen[m]) ++m;
    return m;
}
 
// Collects the Grundy value of every option of a heap of size n.
void option_values(int n, vector<int>& vals) {
    vals.clear();
    if (n >= 1) vals.push_back(g[n - 1]);
    if (n >= 2) vals.push_back(g[n - 2]);
    int r = n - 2;  // stones left after taking 2 for a split
    for (int a = 1; a <= r - 1; ++a) {
        int b = r - a;
        vals.push_back(g[a] ^ g[b]);
    }
}
 
void build() {
    g[0] = 0;
    vector<int> vals;
    for (int n = 1; n <= MAXN; ++n) {
        option_values(n, vals);
        g[n] = mex(vals);
    }
}
 
// Finds one option of a heap of size n whose Grundy value is target.
bool find_move(int n, int target, vector<int>& pieces) {
    if (n >= 1 && g[n - 1] == target) {
        pieces = {n - 1};
        return true;
    }
    if (n >= 2 && g[n - 2] == target) {
        pieces = {n - 2};
        return true;
    }
    int r = n - 2;
    for (int a = 1; a <= r - 1; ++a) {
        int b = r - a;
        if ((g[a] ^ g[b]) == target) {
            pieces = {a, b};
            return true;
        }
    }
    return false;
}
 
int main(int argc, char** argv) {
    build();
    if (argc > 1 && string(argv[1]) == "table") {
        for (int n = 0; n <= 30; ++n) printf("g(%d) = %d\n", n, g[n]);
        return 0;
    }
    int k;
    if (!(cin >> k)) return 0;
    vector<int> h(k);
    for (auto& x : h) cin >> x;
    int s = 0;
    for (int x : h) s ^= g[x];
    if (s == 0) {
        printf("second\n");
        return 0;
    }
    for (int i = 0; i < k; ++i) {
        int target = g[h[i]] ^ s;
        if (target < g[h[i]]) {
            vector<int> pieces;
            if (find_move(h[i], target, pieces)) {
                printf("first\n");
                printf("heap %d (size %d) becomes", i + 1, h[i]);
                bool any = false;
                for (int p : pieces)
                    if (p > 0) {
                        printf("%s %d", any ? " and" : "", p);
                        any = true;
                    }
                if (!any) printf(" nothing (heap removed)");
                printf("\n");
                return 0;
            }
        }
    }
    printf("internal error\n");
    return 1;
}

Testing. I checked the solver in two ways. The table matches the mex definition, computed separately in Python for n from 0 to 30. Then I compared every ordered input with 1 to 3 heaps and sizes from 0 to 8, which is 819 inputs. A brute-force search over all positions gave the winner, and for every first answer I checked that the printed move leads to a position the brute force marks as losing for the opponent. The solver had 0 mismatches. This covers small inputs only. It does not show the table is right for sizes near 200, though the same code runs there.

Python version

For a table up to 200 the Python version is fast enough. The snippet below has no input and runs as is. Its output for the first 31 values is:

Real output on my machine (Python 3.14):

0 1 2 0 1 2 3 1 2 3 4 0 3 4 2 1 3 2 1 0 2 1 4 5 1 4 5 1 2 0 1

The values are the same on every machine, because the computation uses only integers.

Hands-on exercise

Do this on your own machine. You need g++ with C++17 and Python 3.

1. Save the C++ program above as sum_winner.cpp. Compile it with g++ -std=c++17 -O2 -Wall -Wextra -o sum_winner sum_winner.cpp.
2. Run ./sum_winner table. Its output must match the table in the Python section. If one line differs, check the option list for that n first.
3. Run printf "2\n6 10\n" | ./sum_winner. The answer must be first, followed by a move that leaves heaps 6 and 9.
4. Write a Python script that runs over every ordered tuple of 1 to 3 heaps with sizes 0 to 8. For each tuple, decide the winner by a full search of the game tree, and compare it with the program. Count the mismatches. A correct program gives 0 on these 819 inputs.

If you use an AI assistant for step 4, give it this prompt, then run the comparison yourself:

Write a C++17 program that computes Grundy values for this game: from n stones you may take 1 stone, take 2 stones, or take 2 stones and split the remaining n - 2 stones into two non-empty heaps. Take the mex of the option values, where a split option's value is the XOR of its two parts. Print g(0) to g(30). Then write a Python brute force that decides whether the first player wins a sum of 1 to 3 heaps, sizes 0 to 8, by searching the game tree. Run both on every input and report the number of mismatches with the real output.

A good answer computes the sum of heaps with XOR, not with +, and prints a move for every first-player win. It also reports the mismatch count from a real run. Check that the brute force searches every move, and that the move the program prints leads to a losing position for the opponent.

Complexity

Building the table needs, for each heap size n, a list of about n option values and a mex over that list. The total work is O(N^2) for N heaps, which is about 40,000 steps for N = 200. Finding a winner over k heaps takes O(k) table lookups for the XOR, plus one scan of a heap's options, which is O(n). Both are far below any time limit a contest would set for this size.

Common mistakes

Adding Grundy values instead of XOR-ing them. This is the most common mistake, and the one I checked. A version that tests sum(g) != 0 instead of XOR(g) != 0 gave the wrong winner in 187 of the 819 exhaustive cases. For example, heaps of 4 and 4 have values 1 and 1. The sum rule computes 1 + 1 = 2, which is not zero, so it prints first. The correct answer is second. The fix is the ^ operator, and the exhaustive test above is what catches the bug.

Forgetting the split option, or building it wrong. A split must use the XOR of the two new heap values, not the value of the total. A split with an empty piece is not a legal move, so the loop must start at a = 1 and stop at r - 1. A loop that starts at a = 0 adds a move that does not exist, and the table then differs from the rule.

Choosing a heap whose target is larger. The heap you change must satisfy target < g(h_i). A heap whose target is larger may not have any option with that value, and the code then fails to find a move.

Treating a zero piece as a heap. A move that leaves n - 2 = 0 must print that the heap is removed, not a heap of size 0 with a Grundy value. The solver handles this by skipping zero pieces in the printed line.

Using a mex over the wrong set. The mex must be taken over the option values only. Including the current value of the position, or treating a missing value as present, changes the table.

Practice problems

1. The mex of a set

Compute mex{0, 1, 3, 4} and mex{2}.

Show the answer

mex{0, 1, 3, 4} is 2, because 0 and 1 are taken and 2 is missing. mex{2} is 0, because 0 is missing.

2. Option values of n = 6

List the option values of a heap of 6 stones and give g(6).

Show the answer

Option (a) leaves 5, value 2. Option (b) leaves 4, value 1. Option (c) splits 4 stones into (1, 3), (2, 2) or (3, 1), with values 1 ^ 0 = 1, 2 ^ 2 = 0 and 0 ^ 1 = 1. The set is {2, 1, 0}, so g(6) = 3, which matches the table.

3. The P-positions below 30

List every heap size from 0 to 30 whose Grundy value is 0. Then say what that means for a single heap of that size.

Show the answer

The sizes are 0, 3, 11, 19 and 29. A single heap of one of those sizes is a P-position: the player to move loses. Run ./sum_winner table to check the list.

4. Winner of a sum

Decide the winner of the sum of heaps 5, 7 and 9, and give a winning move if there is one.

Show the answer

g(5) = 2, g(7) = 1 and g(9) = 3. The XOR is 2 ^ 1 ^ 3 = 0, so the player to move loses. The program prints second. There is no winning move.

5. Winning move in a sum

Find a winning move for the sum of heaps 6 and 10, and check it.

Show the answer

g(6) = 3 and g(10) = 4. The XOR is 7, which is nonzero, so the first player wins. For heap 6 the target is 3 ^ 7 = 4, which is not smaller than 3, so heap 6 is not the one to change. For heap 10 the target is 4 ^ 7 = 3, which is smaller than 4. Taking 1 stone leaves 9, with value 3. The move "take 1 from heap 10" leaves heaps 6 and 9, with XOR 3 ^ 3 = 0. The program prints heap 2 (size 10) becomes 9.

Checklist

• Give each position its mex of option values, and check that the value of 0 means no moves.
• Combine independent parts with ^, never with + or max.
• Check the rule against brute force on every input with a few small heaps before you trust the table.
• To find a winning move, look for a part whose target value is smaller than its own value, and then find an option with that target.
• Keep every move legal: no empty heaps, and no moves that the rule does not allow.
• Keep the table, the move generator and the brute force in one test file, so a change to one is caught by the others.

Summary

A position's Grundy value is the mex of the values of its options. In a sum of independent games, the sum is a P-position exactly when the XOR of the parts' Grundy values is 0. Winning from a nonzero XOR means finding a part whose value can be lowered to the XOR of the rest, and moving there. The take-and-split game gave values from 0 to 5 in its first 24 heaps, and the solver matched brute force on all 819 small inputs I tested.