Combinatorial Games

June 2026 · 25 min read

Game theory in competitive programming is one of the most elegant intersections of mathematics and algorithms. At its core lies the theory of combinatorial games — deterministic two-player games with perfect information where every position is either winning or losing. This post develops the rigorous foundations you'll need for Sprague-Grundy theory, Nim, and the entire game-theoretic toolkit used across Codeforces and ICPC.

What Are Combinatorial Games

Formally, a combinatorial game is a pair $G = (X, F)$ where $X$ is the set of all positions and $F : X \to \mathcal{P}(X)$ is the move function mapping each position to its set of reachable successors. A position $x$ is terminal if $F(x) = \emptyset$.

The game graph $(X, E)$ has edges $E = \{(x, y) : y \in F(x)\}$. The finiteness axiom guarantees that this graph is a directed acyclic graph (DAG) — there are no cycles.

Other classic examples include Nim (multiple piles, remove any number from one pile), Chomp (breaking a chocolate bar), and Wythoff's game. Notice that chess, checkers, and Go are also combinatorial games, although their state spaces are far too large for complete analysis.

Impartial vs Partizan Games

The most critical classification in combinatorial game theory divides all games into two families.

The distinction determines which mathematical tools we can apply:

Why the distinction matters in CP: Nearly every game theory problem on competitive programming platforms involves impartial games. This is because Sprague-Grundy theory gives us a complete, algorithmic solution: reduce the game to Grundy values and XOR them. Partizan games require far more sophisticated analysis and appear only in advanced research problems.

For the remainder of this series, unless stated otherwise, we focus on impartial games under normal play convention.

N-Positions and P-Positions

The central concept in combinatorial game analysis is the classification of every position as either a winning position for the Next player or a winning position for the Previous player. This binary classification completely determines optimal play.

The labeling is determined recursively from the terminal positions:

Equivalently, using set notation:

The intuition is beautifully simple: from an N-position, the next player can "escape" to a P-position, passing the burden to the opponent. From a P-position, every move leads to an N-position — you're trapped.

Interactive: Game Tree Labeling

Below is the game tree for the subtraction game with pile sizes $0$ through $7$ and subtraction set $S = \{1, 2, 3\}$. Click Step to watch the labeling algorithm propagate from terminal positions upward. Notice how position $0$ is P (terminal loss), positions $1, 2, 3$ are N (can reach $0$), position $4$ is P (all moves go to N), and the pattern repeats with period $4$.

After the full labeling, the pattern emerges: $\text{type}(n) = P$ iff $n \equiv 0 \pmod{4}$. This periodicity is no coincidence — it follows from the structure of the subtraction set and is a special case of the Sprague-Grundy theorem (covered in the next post).

The Fundamental Theorem

We now prove that the labeling algorithm is well-defined and exhaustive: every position in a finite combinatorial game is exactly one of N or P.

The proof gives us more than just existence — it provides a constructive algorithm. Process positions in topological order (terminal nodes first), applying the three rules. This runs in $O(|X| + |E|)$ time, where $|E|$ is the number of edges in the game graph.

Computing Positions

We now translate the theory into practical C++ code. There are two primary approaches: backward induction (topological sort) and recursive memoization.

Approach 1: Backward Induction via Topological Sort

Process positions from terminal nodes upward using BFS. This is the most efficient approach and mirrors the proof of the fundamental theorem.

#include <bits/stdc++.h>
using namespace std;

vector<char> computePositions(int n, const vector<int>& S) {
    vector<vector<int>> radj(n + 1);
    vector<int> outdeg(n + 1, 0);
    for (int i = 0; i <= n; i++)
        for (int s : S)
            if (i - s >= 0) { radj[i - s].push_back(i); outdeg[i]++; }

    vector<char> pos(n + 1, '?');
    queue<int> q;
    for (int i = 0; i <= n; i++)
        if (outdeg[i] == 0) { pos[i] = 'P'; q.push(i); }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : radj[u]) {
            if (pos[v] != '?') continue;
            if (pos[u] == 'P') { pos[v] = 'N'; q.push(v); }
            else if (--outdeg[v] == 0) { pos[v] = 'P'; q.push(v); }
        }
    }
    return pos;
}

int main() {
    int n, k; cin >> n >> k;
    vector<int> S(k);
    for (int& s : S) cin >> s;
    auto pos = computePositions(n, S);
    for (int i = 0; i <= n; i++)
        cout << i << ": " << pos[i] << "\n";
}

Time: $O(n \cdot |S|)$  |  Space: $O(n \cdot |S|)$

Approach 2: Recursive Memoization (DFS)

For implicit game graphs (defined by rules rather than adjacency lists), DFS with memoization is cleaner:

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, bool> memo;
vector<int> S;

bool isNPosition(int n) {
    if (n == 0) return false;
    auto it = memo.find(n);
    if (it != memo.end()) return it->second;
    bool result = false;
    for (int s : S) {
        if (n - s >= 0 && !isNPosition(n - s)) { result = true; break; }
    }
    return memo[n] = result;
}

int main() {
    int n, k; cin >> n >> k;
    S.resize(k);
    for (int& s : S) cin >> s;
    cout << (isNPosition(n) ? "First" : "Second") << "\n";
}

Time: $O(n \cdot |S|)$  |  Space: $O(n)$

Key insight for CP: The BFS approach is preferred when you need to classify all positions (answer multiple queries). The DFS approach is better for a single starting position in a large state space. For general DAGs, the same BFS logic applies with $O(V + E)$ time.

Classic Examples

Example 1: Subtraction Game Analysis

Consider the subtraction game with $S = \{1, 3, 4\}$. Let's compute the first few positions:

Verification for $n = 2$: $F(2) = \{1\}$. Since type(1) = N, all successors are N → type(2) = P. For $n = 7$: $F(7) = \{6, 4, 3\}$, all N-positions → type(7) = P. The pattern $P, N, P, N, N, N, N$ repeats with period 7.

Example 2: Simple Nim (Single Pile)

Nim with a single pile of $n$ stones (remove $\geq 1$ stones): $n = 0$ is a P-position (no moves); $n \geq 1$ is an N-position (take all). The real power emerges with multiple piles — the Sprague-Grundy theorem shows $(n_1, n_2, \ldots, n_k)$ is a P-position iff $n_1 \oplus n_2 \oplus \cdots \oplus n_k = 0$.

Practice Problems

Apply the concepts from this post to these problems, roughly ordered by difficulty:

1. CF 1537D — Deleting Divisors — Direct N/P position analysis.
2. CF 1194D — 1-2-3 — Subtraction game with multiple piles.
3. CF 859C — Pie Rules — Game analysis with backward induction.
4. CF 1451D — Circle Game — 2D position analysis with N/P labeling.

What's next: In Part 2, we cover the Sprague-Grundy theorem — Grundy values, XOR decomposition for game sums, and multi-component game analysis.