Games on graphs

Why this matters when you build with AI

Many AI systems run a loop: a model picks a tool, the tool returns a state, and the model picks again. The state space is a graph. Each state is a vertex, and each allowed step is an edge. Some states are final, some lead back to earlier states, and some cycles never end. A question you can ask about such a graph is "from this state, can the agent always reach a finish, whatever the environment does?" That question is a two-player game on a graph, and it has an exact answer that a program can compute.

The method is retrograde analysis. You start from the states that are already decided, such as a finished state, and walk the edges backwards to label earlier states. The walk is cheap: it touches each edge once. It also gives a third answer that many people miss. On a graph with cycles, some states are neither wins nor losses, because play can go on forever. The method labels those as draws.

The risk is a loop that the code cannot see. A search that follows edges without remembering visited states never stops on a cycle. A label that assumes every game ends can call a looping state a loss. When you ask an assistant for graph search code, check the output on a small graph with a cycle, where you know the answer by hand, before you trust the program on real data.

The idea: moving a token

Put a token on a vertex. On your turn you move the token along one outgoing edge. A player who cannot move loses. This is normal play, the same rule as in the Sprague-Grundy lesson. For each vertex v we want the outcome for the player who must move when the token is on v:

W (win): the player to move can force a win.
L (lose): the player to move loses against any reply.
D (draw): neither player can force a win or a loss, so play goes on forever with best play.

A vertex with no outgoing edges is an L. The player to move has no move and loses.

The two rules that define the labels are short:

A vertex is W if some successor is L. The player moves there and wins.
A vertex is L if every successor is W. Every move gives the opponent a win.

Anything left over is a D. This is the part that needs care, because a vertex can have a successor that is still undecided. It may become W or L later, or it may stay undecided forever.

Part one: graphs without cycles

If the graph has no cycles it is a DAG, a directed acyclic graph. Every token game on a DAG ends, so there are no draws. Each vertex gets a Grundy value, computed exactly as in the Sprague-Grundy lesson: the mex of the Grundy values of its successors. A sink, a vertex with no successor, has value 0.

A worked example

Take this DAG with six vertices and six edges. The edges are 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, 2 -> 4 and 4 -> 5.

The order that matters is reverse topological. A topological order lists each vertex before its successors. The reverse of that order lists each vertex after all its successors, so when we reach a vertex, every successor already has its value. One valid topological order is 0, 2, 4, 5, 1, 3. Its reverse is 3, 1, 5, 4, 2, 0, and we work through that list:

3 is a sink. g(3) = 0.
1 has successor 3. Values {0}, mex is 1. g(1) = 1.
5 is a sink. g(5) = 0.
4 has successor 5. Values {0}, mex is 1. g(4) = 1.
2 has successors 3 and 4. Values {0, 1}, mex is 2. g(2) = 2.
0 has successors 1 and 2. Values {1, 2}, mex is 0. g(0) = 0.

So the values are 0 1 2 0 1 0 for vertices 0 to 5. A single token on vertex v is a W exactly when g(v) != 0. Vertex 0 has value 0, so it is an L for the player to move.

Sums of tokens

Put one token on each of several vertices of the same DAG, and let each player move one token per turn. Each token is an independent game, so the Sprague-Grundy result applies. The sum is a win for the player to move exactly when the XOR of the token values is nonzero.

Two tokens at vertices 1 and 4 have values 1 and 1, so the XOR is 0. The player to move loses. Two tokens at vertices 0 and 2 have values 0 and 2, so the XOR is 2. The player to move wins by moving the token on vertex 2 to vertex 3, which has value 0. The Python snippet below computes these values for the same DAG:

Python · editable

Real output on my machine (Python 3.14):

[0, 1, 2, 0, 1, 0]

Part two: graphs with cycles

Now allow cycles. The Grundy method no longer works directly, because a vertex on a cycle may depend on itself. We need the three labels W, L and D, and the rules from the idea section.

The smallest example with a draw is two vertices with edges 0 -> 1 and 1 -> 0. From 0 the only move goes to 1, and from 1 the only move goes back to 0. Neither vertex has a sink to reach, so neither player can force an end. Both are D. If you play this game on paper, you see the two players pass the token back and forth.

A larger example shows all three labels. It is the graph with seven vertices and seven edges used in the program below: 0 -> 1, 1 -> 2, 2 -> 1, 2 -> 3, 4 -> 0, 4 -> 5 and 6 -> 6, where the last edge is a self-loop. The expected labels are W L W L W L D.

Retrograde analysis: labelling backwards

The method starts from what is known and extends it:

Every sink is L. Put each sink in a queue.
Take a labelled vertex u from the queue. Look at each predecessor p, a vertex with an edge p -> u.
If u is L, then p can move to a losing vertex, so p is W. If p is not labelled yet, label it W and add it to the queue.
If u is W, then one of p's moves is no longer useful to p, because it hands the opponent a win. Keep a counter cnt[p] of the moves of p that have not been shown to lead to a W. Start it at the out-degree of p. Each time a successor of p becomes W, decrease the counter. If it reaches 0, every move of p leads to a W, so p is L. Label it and add it to the queue.
When the queue is empty, every vertex still unlabelled is a draw.

The counter is an in-degree count in the reversed graph. In the reversed graph, the edges point from u to p, so the number of edges into p is the number of moves of p in the original graph.

A worked trace

Here is the seven-vertex graph traced by hand. Out-degrees are: 0 has 1, 1 has 1, 2 has 2, 3 has 0, 4 has 2, 5 has 0 and 6 has 1.

Sinks 3 and 5 are L. Queue: 3, 5.
Pop 3. Its predecessor is 2. Label 2 W. Queue: 5, 2.
Pop 5. Its predecessor is 4. Label 4 W. Queue: 2, 4.
Pop 2. Its predecessor is 1. 2 is W, so decrease cnt[1] from 1 to 0. Label 1 L. Queue: 4, 1.
Pop 4. It has no predecessors.
Pop 1. Its predecessors are 0 and 2. Vertex 1 is L, so label 0 W. Vertex 2 is already labelled, so skip it. Queue: empty after this.
Vertex 6 was never labelled. It is a D.

The result is 0 W, 1 L, 2 W, 3 L, 4 W, 5 L, 6 D. Vertex 6 is the self-loop, which can be played forever.

Implementation

The program below reads the graph and prints one letter per vertex. It runs in time proportional to the number of vertices plus edges. The DAG program is the Part one method, using a topological order.

// Win / lose / draw for a token-moving game on a directed graph (cycles allowed).
// Input:  n m, then m lines "u v" (a move from u to v).
// Output: one character per vertex: W (the player to move wins), L (loses), D (draw).
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> rev(n);   // rev[v] lists u for every edge u -> v (with repeats)
    vector<int> cnt(n, 0);        // moves of v not yet known to lead to a WIN vertex
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        rev[v].push_back(u);
        cnt[u]++;
    }
 
    // 0 = not decided yet (stays 0 at the end means draw), 1 = WIN, 2 = LOSE.
    vector<int> label(n, 0);
    queue<int> q;
    for (int v = 0; v < n; ++v)
        if (cnt[v] == 0) {        // no legal move: the player to move loses
            label[v] = 2;
            q.push(v);
        }
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int p : rev[u]) {    // p has a move to u
            if (label[p] != 0) continue;
            if (label[u] == 2) {  // p can move to a LOSE vertex, so p is WIN
                label[p] = 1;
                q.push(p);
            } else if (--cnt[p] == 0) {  // u is WIN, and it was p's last unchecked move: p is LOSE
                label[p] = 2;
                q.push(p);
            }
        }
    }
 
    for (int v = 0; v < n; ++v) putchar(label[v] == 1 ? 'W' : label[v] == 2 ? 'L' : 'D');
    putchar('\n');
    return 0;
}

Output on the seven-vertex example, from the sample input 7 7 followed by the seven edges above:

WLWLWLD

The second sample is the two-vertex cycle 0 -> 1, 1 -> 0. Its output is DD.

The DAG program uses Kahn's algorithm for the topological order, then processes vertices in reverse order:

// Grundy values of every vertex of a DAG, and the winner of a sum of tokens.
// Input:  n m, then m lines "u v"; then k, then k token positions.
// Output: the Grundy value of every vertex on one line, then "first" or "second"
//         for the sum of the k tokens (first = the player to move wins).
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> out(n);
    vector<int> indeg(n, 0);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        out[u].push_back(v);
        indeg[v]++;
    }
 
    // Kahn's algorithm gives a topological order (every edge goes forward in it).
    vector<int> order;
    queue<int> q;
    for (int v = 0; v < n; ++v)
        if (indeg[v] == 0) q.push(v);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : out[u])
            if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() != n) {
        printf("graph has a cycle\n");
        return 1;
    }
 
    // Reverse topological order: every successor of v is finished before v.
    vector<int> g(n, 0);
    for (int idx = n - 1; idx >= 0; --idx) {
        int v = order[idx];
        vector<char> seen(out[v].size() + 2, 0);
        for (int w : out[v])
            if (g[w] < (int)seen.size()) seen[g[w]] = 1;
        int mex = 0;
        while (seen[mex]) ++mex;
        g[v] = mex;
    }
    for (int v = 0; v < n; ++v) printf("%d%c", g[v], v + 1 < n ? ' ' : '\n');
 
    int k;
    cin >> k;
    int x = 0;
    for (int i = 0; i < k; ++i) {
        int t;
        cin >> t;
        x ^= g[t];
    }
    printf("%s\n", x == 0 ? "second" : "first");
    return 0;
}

Output on the six-vertex DAG with tokens at 0 and 2, from the sample input 6 6, the six edges, then 2 and 0 2:

0 1 2 0 1 0
first

Output with tokens at 1 and 4 gives second, which matches the hand calculation above.

Testing

I tested both programs against reference code I wrote in Python, on random inputs.

Labels. The reference repeats the two rules over all vertices until nothing changes. It is slower than the queue, but it is a plain fixpoint, so it is easy to check by reading. I ran 3,000 random graphs with 1 to 7 vertices and 0 to 14 edges. Loops and repeated edges were allowed. The labels seen across those runs were W 2099, L 4133 and D 5713. The program matched the reference on every graph.
DAG values and sums. I generated 600 random DAGs with 1 to 7 vertices, with the vertex order shuffled so the input is not already sorted. For each DAG I computed Grundy values by the mex rule, and the win or loss of 1 to 3 tokens by full game search. The program matched on all 600.

These tests use small graphs only. They show the rules are applied correctly, not that the program is fast on large inputs. The complexity section covers speed.

Hands-on exercise

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

Save the labelling program above as graph_outcome.cpp and compile it with g++ -std=c++17 -O2 -Wall -Wextra -o graph_outcome graph_outcome.cpp.
Run printf "2 2\n0 1\n1 0\n" | ./graph_outcome. The output must be DD. Then run the seven-vertex example with 7 7 and its seven edges. The output must be WLWLWLD.
Write a Python fixpoint that repeats the two rules over all vertices until nothing changes. Generate 500 random graphs with 1 to 7 vertices and 0 to 14 edges, loops and repeated edges allowed. Run both and count mismatches. A correct program gives 0.
Change one line so each predecessor is stored once, as in the mistakes section, and count the mismatches again. This shows how a small bug in the reverse list changes results.

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

Write a Python function that labels every vertex of a directed graph as W (the player to move wins), L (loses) or D (draw), where a sink is L. A vertex is W if some successor is L, and L if every successor is W. Everything else is D. Use a plain loop that repeats the two rules until no label changes. Then generate 500 random graphs with 1 to 7 vertices, loops and repeated edges allowed, and compare it with a C++ queue-based program that you also write. Report the number of mismatches from a real run, and show two graphs where the labels include a D.

A good answer reads the edges as moves from u to v, and treats a sink as L. It also keeps repeated edges, which matter for the counter. Check that the random test uses the real output of both programs, and that a draw is actually produced on some inputs.

Complexity

The labelling program looks at each vertex and each edge a constant number of times. Its running time is O(n + m) for n vertices and m edges. The memory is also O(n + m).

The DAG program does the same: a pass for the topological order and a pass for the mex of each vertex. The mex step builds a list of size equal to the out-degree plus 2, so the total is O(n + m).

Common mistakes

Counting multi-edges once. If the graph has two edges from p to u, then p has two moves to u. When u becomes W, the counter for p must go down by 2. A version that stores each predecessor once, but still counts every edge, fails. I wrote that version to check. On my 3,000 random graphs it gave the wrong labels 65 times. The smallest case is 3 3 with edges 0 1, 0 1, 1 2. The correct labels are LWL, and the wrong version printed DWL, because vertex 0 never reached a counter of 0. The fix is to keep every edge in the reverse list, and the random test catches the bug.

Labelling a sink as W. A vertex with no moves is a loss for the player to move. Labelling it W reverses the outcome of every vertex that depends on it. The worked trace above starts from the sinks for this reason.

Stopping too early and calling undecided vertices L. A vertex whose successors are all undecided is not an L. It can still become W or L later, or it can be a draw. Only the counter reaching 0 makes a vertex L, and only a successor labelled L makes a vertex W. Everything else stays unlabelled and becomes D at the end.

Recursing on cycles. A depth-first search that does not mark visited vertices never returns on a cycle. The queue method avoids this, because a vertex is labelled only when a rule forces it.

Using the Grundy method on a graph with cycles. The mex needs the Grundy values of successors. On a cycle, a value may depend on itself, so the mex is not defined in the same way. The program in Part one rejects a cycle for this reason. A loopy generalisation exists, but this lesson does not use it, and I did not test it.

Practice problems

1. Labels on a three-vertex graph

Label the graph with vertices 0, 1 and 2 and edges 0 -> 1, 1 -> 0 and 1 -> 2.

Show the answer

Vertex 2 is a sink, so it is L. Vertex 1 has the successor 2, which is L, so 1 is W. Vertex 0 has only the successor 1, which is W, so the counter for 0 reaches 0 and 0 is L. The labels are LWL. Running graph_outcome on this input prints LWL.

2. A three-cycle

Label a cycle 0 -> 1, 1 -> 2, 2 -> 0 with no exit.

Show the answer

No vertex has a sink to reach and no vertex has an edge out of the cycle. Each vertex has one successor, which is undecided, so no rule fires. All three are D. The output is DDD.

3. Predict the output with multi-edges

Predict the output for 3 3 with edges 0 1, 0 1 and 1 2. Then run the program and the buggy version that stores each predecessor once.

Show the answer

Vertex 2 is a sink, so it is L. Vertex 1 has the successor 2, so it is W. Vertex 0 has two moves, both to 1, so its counter starts at 2. When 1 becomes W, both edges from 0 are in the reverse list, so the counter goes down twice, from 2 to 0, and 0 is L. The correct output is LWL. The buggy version keeps only one edge in the list, so the counter goes down once, stays at 1, and 0 stays unlabelled. It prints DWL.

4. A winning move in a sum

The DAG from the worked example has tokens on vertices 0 and 2. Give a winning move.

Show the answer

The values are g(0) = 0 and g(2) = 2. The XOR is 2, so the first player wins. The token on vertex 2 has value 2, and its target is 2 ^ 2 = 0, which is smaller than 2. Vertex 2 has an option of value 0, namely vertex 3. Moving the token from 2 to 3 leaves tokens at 0 and 3, with values 0 and 0. The program prints first, and the move is 2 to 3.

5. Why draws need the queue to finish

Explain why a vertex on a cycle is not labelled until the queue is empty, and what goes wrong if you label it earlier.

Show the answer

A vertex on a cycle may have a successor that is labelled later in the process. If you label it early, you assume a result that the rules do not yet force. For example, a vertex whose only successor is still unlabelled is not yet an L, because that successor may later become an L and make the vertex a W. The queue labels a vertex only when a rule has forced it, so anything still unlabelled at the end has no forced result, and it is a draw.

Checklist

Put every sink in the queue as L before you start.
Keep every edge in the reverse list, including repeated edges and self-loops.
For each predecessor of a WIN vertex, decrease its counter once per edge.
For each predecessor of a LOSE vertex, label it WIN if it is not already labelled.
Leave everything unlabelled at the end as D, and test that on a two-vertex cycle.
Check the program against a plain fixpoint on random small graphs before you trust it on a large one.
On a DAG, use the reverse topological order for the mex. Reject the input if the topological order does not cover every vertex.

Summary

On a token-moving game, each vertex is a win, a loss or a draw for the player to move. On a DAG, Grundy values give the answer, and sums of tokens follow the XOR rule. On a graph with cycles, backward labelling with a counter finds the wins and losses, and whatever is left is a draw. The program runs in time proportional to vertices plus edges, and it matched a plain fixpoint on 3,000 random graphs and a full game search on 600 random DAGs.