37.04Intermediate / Advanced4 topics17 min4 interactive animations

Graph games

Two players move a token along the arrows of a graph; positions are winning or losing for the player to move, and DP from the end of the game (on a DAG) or retrograde analysis (with cycles) decides them, with minimax for games that score points.

Learning goals

Label positions of a loop-free game as winning or losing
Use retrograde analysis to handle games that can cycle, including draws
Change the rule for terminal positions
Compute minimax values on a DAG

Prerequisites

DAG DP patternsTopological sortQueues

Games such as Nim variants, 'take a path along the arrows', and board puzzles are graphs: positions are vertices and moves are arrows. If both players play perfectly, every position has a fixed outcome that dynamic programming can compute.

37.04.1

Winning/losing states on DAG

The rule: the player who cannot move **loses**. A position is **winning** for the player to move if at least one move leads to a losing position (for the opponent). It is **losing** if every move leads to a winning position, which includes the case of no moves. If the moves form a DAG the game must end, and the positions can be decided from the last to the first, in reverse topological order.

Open the first preset of the game animation. The sinks are losing, then each earlier position takes its value from the positions it can move to. The code below returns true for winning positions.

Java

1static boolean[] winsDag(int n, int[][] moves) {                    // true when the player to move wins; the moves must be acyclic
2    List<Integer>[] g = new List[n];
3    int[] indeg = new int[n];
4    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
5    for (int[] m : moves) { g[m[0]].add(m[1]); indeg[m[1]]++; }
6    Deque<Integer> queue = new ArrayDeque<>();
7    List<Integer> order = new ArrayList<>();
8    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);
9    while (!queue.isEmpty()) { int u = queue.poll(); order.add(u); for (int v : g[u]) if (--indeg[v] == 0) queue.add(v); }
10    boolean[] win = new boolean[n];
11    for (int i = n - 1; i >= 0; i--) {                              // successors are decided before their predecessors
12        int v = order.get(i);
13        for (int w : g[v]) if (!win[w]) win[v] = true;              // a move to a losing position wins
14    }
15    return win;
16}

Games on a graph: winning and losing positions, retrograde analysis, minimax

Interactive · edit the input

directed graph · 6 vertices · 7 edges

Win for the player to moveLoss for the player to moveBeing decidedDraw (never decided)

position state (W = win, L = loss)

Setup

The player who cannot move loses. A position is a win if some move leads to a loss for the opponent, and a loss if every move leads to a win (or there is no move). Because the moves have no cycle, decide positions in reverse topological order: 0 → 1 → 2 → 3 → 4 → 5.

Step 1 / 8

Java

1static int[] solveGame(int n, int[][] moves) {   // moves {from, to}; 1 = player to move wins, -1 loses, 0 draw
2    List<Integer>[] back = new List[n];
3    int[] left = new int[n];                          // moves not yet known to lead to a winning position
4    for (int i = 0; i < n; i++) back[i] = new ArrayList<>();
5    for (int[] m : moves) { back[m[1]].add(m[0]); left[m[0]]++; }
6    int[] state = new int[n];
7    Deque<Integer> queue = new ArrayDeque<>();
8    for (int v = 0; v < n; v++) if (left[v] == 0) { state[v] = -1; queue.add(v); }   // no move: the player to move loses
9    while (!queue.isEmpty()) {
10        int v = queue.poll();
11        for (int p : back[v]) {
12            if (state[p] != 0) continue;
13            if (state[v] == -1) { state[p] = 1; queue.add(p); }          // p can move to a lost position: p wins
14            else if (--left[p] == 0) { state[p] = -1; queue.add(p); }    // every move of p leads to a won position: p loses
15        }
16    }
17    return state;                                    // positions never decided are draws
18}
19static boolean[] winsDag(int n, int[][] moves) {  // true when the player to move wins; the moves must be acyclic
20    List<Integer>[] g = new List[n];
21    int[] indeg = new int[n];
22    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
23    for (int[] m : moves) { g[m[0]].add(m[1]); indeg[m[1]]++; }
24    Deque<Integer> queue = new ArrayDeque<>();
25    List<Integer> order = new ArrayList<>();
26    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);
27    while (!queue.isEmpty()) { int u = queue.poll(); order.add(u); for (int v : g[u]) if (--indeg[v] == 0) queue.add(v); }
28    boolean[] win = new boolean[n];
29    for (int i = n - 1; i >= 0; i--) {                // successors are decided before their predecessors
30        int v = order.get(i);
31        for (int w : g[v]) if (!win[w]) win[v] = true;   // a move to a losing position wins
32    }
33    return win;
34}

Live state

0 positions decided

order

[0, 1, 2, 3, 4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L19	order=[0, 1, 2, 3, 4, 5]	The player who cannot move loses. A position is a win if some move leads to a loss for the opponent, and a loss if every move leads to a win (or there is no move). Because the moves have no cycle, decide positions in reverse topological order: 0 → 1 → 2 → 3 → 4 → 5.
2	L31	v=5 state=L	Position 5 has no move: the player to move loses.
3	L31	v=4 state=W	Position 4: the move to 5 leaves the opponent in a lost position, so 4 is a win.
4	L31	v=3 state=W	Position 3: the move to 5 leaves the opponent in a lost position, so 3 is a win.
5	L31	v=2 state=L	Position 2: every move (3, 4) leads to a won position for the opponent, so 2 is a loss.
6	L31	v=1 state=L	Position 1: every move (3) leads to a won position for the opponent, so 1 is a loss.
7	L31	v=0 state=W	Position 0: the move to 1 leaves the opponent in a lost position, so 0 is a win.
8	L33	return=[W, L, L, W, W, L]	Position 0 is a win for the player to move.

37.04.2

Retrograde analysis

If the moves can form a cycle, the game can go on forever and there is no last-to-first order. **Retrograde analysis** works backwards from the known end: positions with no move are lost. Whenever a position is found lost, each position that can move to it is **won**. Whenever a position is found won, each predecessor loses one "possible escape"; when a position has none left (all its moves lead to won positions) it is **lost**.

Positions that are never decided are **draws**: neither player can force a win, and both can keep moving around a cycle. The *Retrograde: a draw appears* preset shows two such positions. The queue-based code visits each arrow once, O(n + m).

Java

1static int[] solveGame(int n, int[][] moves) {                      // moves {from, to}; 1 = player to move wins, -1 loses, 0 draw
2    List<Integer>[] back = new List[n];
3    int[] left = new int[n];                                        // moves not yet known to lead to a winning position
4    for (int i = 0; i < n; i++) back[i] = new ArrayList<>();
5    for (int[] m : moves) { back[m[1]].add(m[0]); left[m[0]]++; }
6    int[] state = new int[n];
7    Deque<Integer> queue = new ArrayDeque<>();
8    for (int v = 0; v < n; v++) if (left[v] == 0) { state[v] = -1; queue.add(v); }   // no move: the player to move loses
9    while (!queue.isEmpty()) {
10        int v = queue.poll();
11        for (int p : back[v]) {
12            if (state[p] != 0) continue;
13            if (state[v] == -1) { state[p] = 1; queue.add(p); }          // p can move to a lost position: p wins
14            else if (--left[p] == 0) { state[p] = -1; queue.add(p); }    // every move of p leads to a won position: p loses
15        }
16    }
17    return state;                                                    // positions never decided are draws
18}

Games on a graph: winning and losing positions, retrograde analysis, minimax

Interactive · edit the input

directed graph · 6 vertices · 7 edges

Win for the player to moveLoss for the player to moveBeing decidedDraw (never decided)

position state (W = win, L = loss)

Setup

Step 1 / 8

Java

1static int[] solveGame(int n, int[][] moves) {   // moves {from, to}; 1 = player to move wins, -1 loses, 0 draw
2    List<Integer>[] back = new List[n];
3    int[] left = new int[n];                          // moves not yet known to lead to a winning position
4    for (int i = 0; i < n; i++) back[i] = new ArrayList<>();
5    for (int[] m : moves) { back[m[1]].add(m[0]); left[m[0]]++; }
6    int[] state = new int[n];
7    Deque<Integer> queue = new ArrayDeque<>();
8    for (int v = 0; v < n; v++) if (left[v] == 0) { state[v] = -1; queue.add(v); }   // no move: the player to move loses
9    while (!queue.isEmpty()) {
10        int v = queue.poll();
11        for (int p : back[v]) {
12            if (state[p] != 0) continue;
13            if (state[v] == -1) { state[p] = 1; queue.add(p); }          // p can move to a lost position: p wins
14            else if (--left[p] == 0) { state[p] = -1; queue.add(p); }    // every move of p leads to a won position: p loses
15        }
16    }
17    return state;                                    // positions never decided are draws
18}
19static boolean[] winsDag(int n, int[][] moves) {  // true when the player to move wins; the moves must be acyclic
20    List<Integer>[] g = new List[n];
21    int[] indeg = new int[n];
22    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
23    for (int[] m : moves) { g[m[0]].add(m[1]); indeg[m[1]]++; }
24    Deque<Integer> queue = new ArrayDeque<>();
25    List<Integer> order = new ArrayList<>();
26    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);
27    while (!queue.isEmpty()) { int u = queue.poll(); order.add(u); for (int v : g[u]) if (--indeg[v] == 0) queue.add(v); }
28    boolean[] win = new boolean[n];
29    for (int i = n - 1; i >= 0; i--) {                // successors are decided before their predecessors
30        int v = order.get(i);
31        for (int w : g[v]) if (!win[w]) win[v] = true;   // a move to a losing position wins
32    }
33    return win;
34}

Live state

0 positions decided

order

[0, 1, 2, 3, 4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L19	order=[0, 1, 2, 3, 4, 5]	The player who cannot move loses. A position is a win if some move leads to a loss for the opponent, and a loss if every move leads to a win (or there is no move). Because the moves have no cycle, decide positions in reverse topological order: 0 → 1 → 2 → 3 → 4 → 5.
2	L31	v=5 state=L	Position 5 has no move: the player to move loses.
3	L31	v=4 state=W	Position 4: the move to 5 leaves the opponent in a lost position, so 4 is a win.
4	L31	v=3 state=W	Position 3: the move to 5 leaves the opponent in a lost position, so 3 is a win.
5	L31	v=2 state=L	Position 2: every move (3, 4) leads to a won position for the opponent, so 2 is a loss.
6	L31	v=1 state=L	Position 1: every move (3) leads to a won position for the opponent, so 1 is a loss.
7	L31	v=0 state=W	Position 0: the move to 1 leaves the opponent in a lost position, so 0 is a win.
8	L33	return=[W, L, L, W, W, L]	Position 0 is a win for the player to move.

37.04.3

Terminal states

Everything depends on what a **terminal position** (no move) means. In *normal play* the player who cannot move loses, which is what we used. In *misère play* the player who cannot move **wins**. The rest of the recurrence is the same, but the base case flips, and so do many results.

Other games give terminals a score instead (the next item). Always read the rule for the end of the game before writing the base case; a wrong base case turns every answer upside down. The code takes the rule as a parameter.

Java

1static boolean[] winsDagWithRule(int n, int[][] moves, boolean misere) {   // misere: the player who cannot move wins
2    List<Integer>[] g = new List[n];
3    int[] indeg = new int[n];
4    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
5    for (int[] m : moves) { g[m[0]].add(m[1]); indeg[m[1]]++; }
6    Deque<Integer> queue = new ArrayDeque<>();
7    List<Integer> order = new ArrayList<>();
8    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);
9    while (!queue.isEmpty()) { int u = queue.poll(); order.add(u); for (int v : g[u]) if (--indeg[v] == 0) queue.add(v); }
10    boolean[] win = new boolean[n];
11    for (int i = n - 1; i >= 0; i--) {
12        int v = order.get(i);
13        if (g[v].isEmpty()) { win[v] = misere; continue; }          // the base case is the rule of the game
14        for (int w : g[v]) if (!win[w]) win[v] = true;
15    }
16    return win;
17}

Games on a graph: winning and losing positions, retrograde analysis, minimax

Interactive · edit the input

directed graph · 6 vertices · 7 edges

Win for the player to moveLoss for the player to moveBeing decidedDraw (never decided)

position state (W = win, L = loss)

Setup

Step 1 / 8

Java

1static int[] solveGame(int n, int[][] moves) {   // moves {from, to}; 1 = player to move wins, -1 loses, 0 draw
2    List<Integer>[] back = new List[n];
3    int[] left = new int[n];                          // moves not yet known to lead to a winning position
4    for (int i = 0; i < n; i++) back[i] = new ArrayList<>();
5    for (int[] m : moves) { back[m[1]].add(m[0]); left[m[0]]++; }
6    int[] state = new int[n];
7    Deque<Integer> queue = new ArrayDeque<>();
8    for (int v = 0; v < n; v++) if (left[v] == 0) { state[v] = -1; queue.add(v); }   // no move: the player to move loses
9    while (!queue.isEmpty()) {
10        int v = queue.poll();
11        for (int p : back[v]) {
12            if (state[p] != 0) continue;
13            if (state[v] == -1) { state[p] = 1; queue.add(p); }          // p can move to a lost position: p wins
14            else if (--left[p] == 0) { state[p] = -1; queue.add(p); }    // every move of p leads to a won position: p loses
15        }
16    }
17    return state;                                    // positions never decided are draws
18}
19static boolean[] winsDag(int n, int[][] moves) {  // true when the player to move wins; the moves must be acyclic
20    List<Integer>[] g = new List[n];
21    int[] indeg = new int[n];
22    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
23    for (int[] m : moves) { g[m[0]].add(m[1]); indeg[m[1]]++; }
24    Deque<Integer> queue = new ArrayDeque<>();
25    List<Integer> order = new ArrayList<>();
26    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);
27    while (!queue.isEmpty()) { int u = queue.poll(); order.add(u); for (int v : g[u]) if (--indeg[v] == 0) queue.add(v); }
28    boolean[] win = new boolean[n];
29    for (int i = n - 1; i >= 0; i--) {                // successors are decided before their predecessors
30        int v = order.get(i);
31        for (int w : g[v]) if (!win[w]) win[v] = true;   // a move to a losing position wins
32    }
33    return win;
34}

Live state

0 positions decided

order

[0, 1, 2, 3, 4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L19	order=[0, 1, 2, 3, 4, 5]	The player who cannot move loses. A position is a win if some move leads to a loss for the opponent, and a loss if every move leads to a win (or there is no move). Because the moves have no cycle, decide positions in reverse topological order: 0 → 1 → 2 → 3 → 4 → 5.
2	L31	v=5 state=L	Position 5 has no move: the player to move loses.
3	L31	v=4 state=W	Position 4: the move to 5 leaves the opponent in a lost position, so 4 is a win.
4	L31	v=3 state=W	Position 3: the move to 5 leaves the opponent in a lost position, so 3 is a win.
5	L31	v=2 state=L	Position 2: every move (3, 4) leads to a won position for the opponent, so 2 is a loss.
6	L31	v=1 state=L	Position 1: every move (3) leads to a won position for the opponent, so 1 is a loss.
7	L31	v=0 state=W	Position 0: the move to 1 leaves the opponent in a lost position, so 0 is a win.
8	L33	return=[W, L, L, W, W, L]	Position 0 is a win for the player to move.

37.04.4

Minimax on DAG

In a game with scores, a terminal position has a value. One player (the maximiser) wants the largest final value, the other (the minimiser) the smallest. At each position, the player to move picks the move with the best resulting value, so value[v] = max over successors for the maximiser and min for the minimiser, evaluated from the terminals backwards.

Here even-numbered positions belong to the maximiser and odd-numbered to the minimiser. Real implementations speed this up with alpha-beta pruning, which skips moves that cannot change the result. The third option of the game animation shows the values.

Java

1static int[] minimaxDag(int n, int[][] moves, int[] terminalValue) {   // even vertices maximise, odd vertices minimise
2    List<Integer>[] g = new List[n];
3    int[] indeg = new int[n];
4    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
5    for (int[] m : moves) { g[m[0]].add(m[1]); indeg[m[1]]++; }
6    Deque<Integer> queue = new ArrayDeque<>();
7    List<Integer> order = new ArrayList<>();
8    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);
9    while (!queue.isEmpty()) { int u = queue.poll(); order.add(u); for (int v : g[u]) if (--indeg[v] == 0) queue.add(v); }
10    int[] value = new int[n];
11    for (int i = n - 1; i >= 0; i--) {
12        int v = order.get(i);
13        if (g[v].isEmpty()) { value[v] = terminalValue[v]; continue; }   // a terminal: its score
14        int best = v % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
15        for (int w : g[v]) best = v % 2 == 0 ? Math.max(best, value[w]) : Math.min(best, value[w]);
16        value[v] = best;
17    }
18    return value;
19}

Games on a graph: winning and losing positions, retrograde analysis, minimax

Interactive · edit the input

directed graph · 6 vertices · 7 edges

Win for the player to moveLoss for the player to moveBeing decidedDraw (never decided)

position state (W = win, L = loss)

Setup

Step 1 / 8

Java

1static int[] solveGame(int n, int[][] moves) {   // moves {from, to}; 1 = player to move wins, -1 loses, 0 draw
2    List<Integer>[] back = new List[n];
3    int[] left = new int[n];                          // moves not yet known to lead to a winning position
4    for (int i = 0; i < n; i++) back[i] = new ArrayList<>();
5    for (int[] m : moves) { back[m[1]].add(m[0]); left[m[0]]++; }
6    int[] state = new int[n];
7    Deque<Integer> queue = new ArrayDeque<>();
8    for (int v = 0; v < n; v++) if (left[v] == 0) { state[v] = -1; queue.add(v); }   // no move: the player to move loses
9    while (!queue.isEmpty()) {
10        int v = queue.poll();
11        for (int p : back[v]) {
12            if (state[p] != 0) continue;
13            if (state[v] == -1) { state[p] = 1; queue.add(p); }          // p can move to a lost position: p wins
14            else if (--left[p] == 0) { state[p] = -1; queue.add(p); }    // every move of p leads to a won position: p loses
15        }
16    }
17    return state;                                    // positions never decided are draws
18}
19static boolean[] winsDag(int n, int[][] moves) {  // true when the player to move wins; the moves must be acyclic
20    List<Integer>[] g = new List[n];
21    int[] indeg = new int[n];
22    for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
23    for (int[] m : moves) { g[m[0]].add(m[1]); indeg[m[1]]++; }
24    Deque<Integer> queue = new ArrayDeque<>();
25    List<Integer> order = new ArrayList<>();
26    for (int v = 0; v < n; v++) if (indeg[v] == 0) queue.add(v);
27    while (!queue.isEmpty()) { int u = queue.poll(); order.add(u); for (int v : g[u]) if (--indeg[v] == 0) queue.add(v); }
28    boolean[] win = new boolean[n];
29    for (int i = n - 1; i >= 0; i--) {                // successors are decided before their predecessors
30        int v = order.get(i);
31        for (int w : g[v]) if (!win[w]) win[v] = true;   // a move to a losing position wins
32    }
33    return win;
34}

Live state

0 positions decided

order

[0, 1, 2, 3, 4, 5]

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L19	order=[0, 1, 2, 3, 4, 5]	The player who cannot move loses. A position is a win if some move leads to a loss for the opponent, and a loss if every move leads to a win (or there is no move). Because the moves have no cycle, decide positions in reverse topological order: 0 → 1 → 2 → 3 → 4 → 5.
2	L31	v=5 state=L	Position 5 has no move: the player to move loses.
3	L31	v=4 state=W	Position 4: the move to 5 leaves the opponent in a lost position, so 4 is a win.
4	L31	v=3 state=W	Position 3: the move to 5 leaves the opponent in a lost position, so 3 is a win.
5	L31	v=2 state=L	Position 2: every move (3, 4) leads to a won position for the opponent, so 2 is a loss.
6	L31	v=1 state=L	Position 1: every move (3) leads to a won position for the opponent, so 1 is a loss.
7	L31	v=0 state=W	Position 0: the move to 1 leaves the opponent in a lost position, so 0 is a win.
8	L33	return=[W, L, L, W, W, L]	Position 0 is a win for the player to move.

Practice ladder

Now try it yourself

Easy

Nim Game

Medium

Stone Game
Predict the Winner
Can I Win

Advanced

Cat and Mouse
Stone Game III

Key takeaways

A position is winning if some move reaches a losing position; losing if all moves reach winning positions (or none exist).
On a DAG decide positions in reverse topological order; with cycles use retrograde analysis and expect draws.
The meaning of a terminal position (normal or misere, or a score) is the base case.
Minimax alternates max and min from the terminal values backwards.