---
title: "Games on Directed Graphs"
summary: Positions, moves, and the winning/losing labelling that solves every impartial finite game.
difficulty: hard
tags: [games, DP, retrograde]
time: n + m
prereq: [directed/dag-toposort]
see: [complexity/npc-graphs, directed/cycles]
---

A finite two-player game with perfect information *is* a graph: vertices are positions, edges are legal moves, and the player unable to move loses (normal play). The whole theory then fits in one labelling rule.

:::definition label="Win/lose states"
On a DAG of positions, define
$$W(v) = \begin{cases} \text{true} & \text{if } \exists\, u : v \to u \text{ with } W(u) = \text{false} \\ \text{false} & \text{otherwise} \end{cases}$$
i.e. $v$ is winning iff you can move to a losing position; a terminal vertex (no moves) is losing.
:::

:::theorem title="Correctness and the strategy"
The labelling is well defined on a DAG, $W(v)$ is true exactly when the player to move at $v$ has a forced win, and along a winning vertex the strategy "move to a losing successor" is closed: every reply lands in a winning-for-you position again.
:::

:::proof
Induct on the height of $v$ in the DAG. If some successor is losing, moving there hands your opponent a position where every move goes to a winning position — by induction they lose. Conversely, if all successors are winning, every move you make gives the opponent a forced win, so you lose. Termination is guaranteed because the graph is acyclic: the token cannot revisit a position. ∎
:::

```cpp win-lose.cpp
// process in reverse topological order: O(n + m)
for (int u : reverse_topo_order()) {
    win[u] = false;
    for (int v : g[u]) if (!win[v]) { win[u] = true; move_to[u] = v; break; }
}
```

:::note title="Graphs with cycles: three colours, not two"
Draws exist once cycles are allowed. Use the retrograde algorithm:
1. mark terminal vertices **L**;
2. iterate a queue: a vertex with an $L$ successor becomes $W$; a vertex whose *all* successors are $W$ becomes $L$ (maintain `remaining[v]` = count of unlabelled successors);
3. whatever is still unlabelled when the queue empties is **D** — both players can avoid losing forever, and the unlabelled set is closed under "there is an escape".
Same $O(n+m)$, one extra array.
:::

```cpp retrograde.cpp
queue<int> q;
for (int v = 0; v < n; v++) if (deg[v] == 0) { state[v] = L; q.push(v); }
while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int p : rev[v]) {
        if (state[p] != UNK) continue;
        if (state[v] == L) state[p] = W;                       // can move to a loss
        else if (--rem[p] == 0) state[p] = L;                   // every move is a win for them
        if (state[p] != UNK) q.push(p);
    }
}
// state[v] == UNK  <=>  draw
```

## Composing games: Sprague–Grundy
When the position is a *disjoint sum* of independent subgames (several heaps, several boards), the right value is not "win/lose" but a number:

:::definition label="Nim-value"
$g(v) = \operatorname{mex}\{g(u) : v \to u\}$, where $\operatorname{mex}$ is the smallest non-negative integer not in the set. A position is losing $\iff g = 0$, and $g$ of a sum is the xor of the parts (Sprague–Grundy).
:::

The reduction is why "Nim with heaps $a_1..a_k$" is answered by `a1 ^ a2 ^ …`: each heap is a path graph, its $g$ value is its size, and disjointness turns xor into the composition law. Computing $g$ on a DAG is one reverse-toposort sweep, so any game whose state space is small ($g \le 512$, say) is an exercise in bounding the state, not in game theory.

:::example title="One graph, three problems"
- Board with a token, moves as in a knight's tour, no repeats → DAG of (cell, visited) is hopeless, but with repeats allowed you need the 3-colour retrograde.
- Several piles of stones, take $1..3$ → path graph, $g(n) = n \bmod 4$.
- Green Hackenbush / geography on a tree → the XOR of subtree values; on a general graph, "Geography" is PSPACE-complete (this is the standard example of a graph game that is *not* solvable by labelling).
:::

:::problems
- [[CSES 1730]] Nim Game I | https://cses.fi/problemset/task/1730 | easy | xor
- [[CSES 1729]] Stick Game | https://cses.fi/problemset/task/1729 | core | Sprague-Grundy
- [[CSES 2207]] Grundy's Game | https://cses.fi/problemset/task/2207 | hard | mex, splitting games
- [[CSES 1099]] Stair Game | https://cses.fi/problemset/task/1099 | hard | invariant
:::