Chapter 3 · Directed Graphs
Games on Directed Graphs
Positions, moves, and the winning/losing labelling that solves every impartial finite game.
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.
On a DAG of positions, define
i.e. v is winning iff you can move to a losing position; a terminal vertex (no moves) is losing.
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.
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. ∎
// 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; }
}Draws exist once cycles are allowed. Use the retrograde algorithm:
- mark terminal vertices **L**;
- 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); - 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.
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:
g(v) = mex{g(u) : v → u}, where mex is the smallest non-negative integer not in the set. A position is losing ⇔ g = 0, and g of a sum is the xor of the parts (Sprague–Grundy).
The reduction is why "Nim with heaps a1..ak" 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 ≤ 512, say) is an exercise in bounding the state, not in game theory.
- 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 mod 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).