On this page

Game DP

Two players sit at a pile of 10 stones. They take turns removing 1, 3 or 4 stones. Whoever cannot move loses. Should you go first? Two players take coins from either end of a row, each trying to end up with more money. Can the first player guarantee a win, and by how much? A cat chases a mouse around a small graph. Does the mouse escape, get caught, or do they run in circles forever?

These are two-player, zero-sum, perfect-information games: two players alternate, one player's gain is the other's loss, and both see everything (no hidden cards, no dice). For such games a famous result (Zermelo, 1913) says every position has a definite value under perfect play: a forced win for the player to move, a forced loss, or (if infinite play is possible) a draw. Game DP is how you compute that value: treat each position as a DP state and fill the table with a rule that says, in effect, "I win if I have a move that leaves you in a losing position".

This lesson builds that rule from scratch, then applies it to take-away games, score games, game sums (the doorway to Sprague–Grundy theory), and games with cycles, where the ordinary DP order breaks and retrograde analysis (filling backwards from the end of the game) takes over.

It assumes DP Foundations (states, transitions, memoisation) and, for the cycles part, BFS and the in-degree idea from Topological Sort.

Why this exists

Games are the oldest testbed for "thinking ahead". To pick a move you imagine the opponent's best reply, then your best reply to that, and so on. Written as code, that is a recursion over positions, and the same positions come up again and again through different move orders. Memoising them is DP.

The history is rich and very concrete:

  • 1901: Charles Bouton solved Nim completely: a position is lost for the player to move exactly when the XOR of the pile sizes is 0.
  • 1913: Ernst Zermelo proved that chess-like games have a determined value. Every proof of this kind is an induction that looks exactly like a game DP.
  • 1935–1939: Roland Sprague and Patrick Grundy showed independently that every finite impartial game behaves like a single Nim pile, of a size now called its Grundy number.
  • 1970s–today: chess endgame tablebases are retrograde analysis at scale. Ken Thompson's 1986 paper computed some 5-piece endings; today's Syzygy tables cover every position with up to 7 pieces, and engines like Stockfish consult them during play.
  • 2007: checkers was solved (a draw with perfect play) by Jonathan Schaeffer's team, combining forward search with huge backward-computed endgame databases (Science 317, 2007).

In interviews and contests, game DP shows up as "Nim Game", "Stone Game I–IX", "Predict the Winner", "Can I Win" and "Cat and Mouse". They look different but are the same three or four ideas.

Pattern triggers

If the problem says or has…Think of…
"both players play optimally", "can the first player guarantee a win"Game DP over positions
"whoever cannot move loses", "takes the last stone wins"Win/lose table: winning iff some move reaches a losing position
Remove 1..k stones, or a fixed set of amountsSubtraction game; look for a period in the win/lose table
"take from either end of the row", "maximise your score"Score-difference interval DP: dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1])
"return true if player 1 wins or ties"Compute the score difference, compare with 0
Several independent piles/boards; a move is made in exactly oneSum of games: XOR of Grundy numbers (Sprague–Grundy)
Positions can repeat ("the game may go on forever", "draw if a position repeats")Retrograde analysis: BFS backwards from terminal states; unlabelled = draw
Two pieces chasing each other on a graph or gridState = (positions, whose turn), retrograde colouring
Small set of used numbers / cells ("numbers can't be reused")Bitmask state: Bitmask DP
Huge game tree (chess, Go), no table fitsMinimax with alpha-beta pruning, or Monte Carlo tree search
Dice or random events in the gameExpectiminimax: add average nodes (see Probability DP)

The meta-trigger: the outcome is decided by perfect play, and the state of the game is small enough to enumerate.

Intuition & first principles

The one rule

Call a position winning (W) if the player whose turn it is can force a win, and losing (L) if the player to move loses no matter what they do. (Notice: W and L are always from the point of view of the player to move.)

A position is W if at least one move leads to an L position. A position is L if every move leads to a W position, including the case where there are no moves at all.

Why? If you can move to a position that is losing for the player to move there, that player is your opponent, so you win. If every move hands your opponent a winning position, they win whatever you do.

An everyday picture: you are handing a hot potato across a room, and certain spots on the floor are "doomed". You want to throw it to a doomed spot for your opponent. A spot is doomed exactly when every throw from it lands on a non-doomed spot.

A tiny example you can hold in your head

Take-away game: a pile of stones, each turn take 1 or 2, whoever cannot move loses.

  • : no moves. L.
  • : take 1 → leaves 0 (L). So W.
  • : take 2 → leaves 0 (L). W.
  • : take 1 → 2 (W), take 2 → 1 (W). Every move gives the opponent a W. L.
  • : take 1 → 3 (L). W.

The pattern L W W L W W L W W … repeats with period 3: the multiples of 3 are losing. The strategy for the winner is to always leave a multiple of 3 (if your opponent takes 1, you take 2, and vice versa). LeetCode's "Nim Game" is this with "take 1 to 3", where the losing positions are the multiples of 4.

Why plain recursion is too slow, and why the DP is safe

Write the rule as a recursive function win(n) that tries every move. For moves {1, 3, 4}, win(30) calls win(29), win(27) and win(26), and those call overlapping sets again: the call tree grows exponentially (like for this move set, since the call count satisfies ), while there are only distinct positions. Memoise and it is linear.

The DP is safe because in a take-away game every move makes the pile smaller: positions form a DAG (a directed acyclic graph, no position can be revisited). So "fill from 0 upwards" guarantees every position you read is already final. When moves can lead back to earlier positions, that guarantee disappears, and we need retrograde analysis (section 6).

graph LR
    P4["4 stones W"] -->|"take 1"| P3["3 stones L"]
    P4 -->|"take 2"| P2["2 stones W"]
    P3 -->|"take 1"| P2
    P3 -->|"take 2"| P1["1 stone W"]
    P2 -->|"take 1"| P1
    P2 -->|"take 2"| P0["0 stones L"]
    P1 -->|"take 1"| P0

Read the arrows: 3 is L because both of its arrows go to W positions; 4 is W because one arrow reaches L.

Mechanics

1. Win/lose table for a subtraction game

A subtraction game has a fixed set of allowed take-amounts. Let us use , a classic example.

State: win[n] = is the position with stones winning for the player to move? Transition: win[n] = any(not win[n - s] for s in S if s <= n). Base: win[0] = False (no moves). In fact the general rule already gives that: any of nothing is False. Order:

nMoves → resulting position (its value)Some move reaches L?win[n]
0nonenoL
1−1 → 0 (L)yesW
2−1 → 1 (W)noL
3−1 → 2 (L), −3 → 0 (L)yesW
4−1 → 3 (W), −3 → 1 (W), −4 → 0 (L)yesW
5−1 → 4 (W), −3 → 2 (L), −4 → 1 (W)yesW
6−1 → 5 (W), −3 → 3 (W), −4 → 2 (L)yesW
7−1 → 6 (W), −3 → 4 (W), −4 → 3 (W)noL
8−1 → 7 (L), …yesW
9−1 → 8 (W), −3 → 6 (W), −4 → 5 (W)noL
10−1 → 9 (L), …yesW

The full string for (computed by the test code and checked against an un-memoised brute-force recursion for ):

n:     0123456789...
S={1,2}:    LWWLWWLWWLWWLWWLWWLWWL      period 3
S={1,3,4}:  LWLWWWWLWLWWWWLWLWWWWL      period 7: L at n mod 7 in {0, 2}
S={2,5,6}:  LLWWLWWWLWWLLWWLWWWLWW      period 11

So with 10 stones and moves {1, 3, 4}, go first: 10 is W, and the winning move is to take 1, leaving 9 (L).

2. Periodicity: why these tables always repeat

Look at how win[n] is computed: it reads only the previous entries. So the whole future is determined by the last values, a "window" of bits. There are only possible windows, so by the pigeonhole principle some window must repeat within the first positions, and from that point the sequence repeats forever. Every finite subtraction game is eventually periodic. (The period can in principle be long; in practice it is usually short, as above.)

This turns " up to " problems into "compute the table until it repeats, then use ". To find the period in code, compute a few hundred entries and search for the smallest such that the table matches itself shifted by (the implementation below does exactly that, also for Grundy numbers).

Eventually periodic, not always periodic from 0

Some subtraction sets have a pre-period: an irregular start before the repetition begins. Never assume the period starts at ; verify the match over a long range after your chosen start.

3. Minimax as DP: playing for a score

Win/lose is the special case where the only outcomes are "I win" and "I lose". Many games end with a score, and each player wants to maximise their own. In a zero-sum setting (what I gain, you lose) it is enough to track one number per position:

value(position) = (score of the player to move) − (score of the opponent), from this position to the end, under perfect play.

This is the negamax form of minimax: the player to move picks the move that maximises "what I gain now minus what the opponent will then achieve from the new position", and the opponent's achievement is the same function evaluated at the new position:

Two players, one function, because the game is symmetric: at every position, "the player to move" has the same goal.

graph TD
    R["value = max of gain minus child"] --> A["take left: gain a[i]"]
    R --> B["take right: gain a[j]"]
    A --> CA["opponent's value on the rest"]
    B --> CB["opponent's value on the rest"]

4. Score-difference DP: Predict the Winner

A row of numbers. Players alternately take one number from either end. Each wants to maximise their own total. Does player 1 finish with at least as much as player 2? (LeetCode 486; LeetCode 877 "Stone Game" is the same game with extra guarantees.)

State: dp[i][j] = best achievable (my total − opponent's total) for the player to move when the remaining row is a[i..j]. Transition: take the left end or the right end:

Base: dp[i][i] = a[i] (one number left: take it). Order: by increasing length , because each state reads two states of length one less. Answer: player 1 wins or ties iff dp[0][n-1] >= 0. Player 1's actual total is .

Why greedy fails. Row [3, 9, 1, 2]. Greedy "take the bigger end" takes 3. Player 2 greedily takes 9. Player 1 takes 2, player 2 takes 1: totals 5 vs 10, a loss. Now the DP. Exact numbers from the test script:

RangeTake left: a[i] − dp[i+1][j]Take right: a[j] − dp[i][j−1]dp
[0,0], [1,1], [2,2], [3,3]——3, 9, 1, 2
[0,1] = 3, 93 − 9 = −69 − 3 = 66
[1,2] = 9, 19 − 1 = 81 − 9 = −88
[2,3] = 1, 21 − 2 = −12 − 1 = 11
[0,2] = 3, 9, 13 − 8 = −51 − 6 = −5−5
[1,3] = 9, 1, 29 − 1 = 82 − 8 = −68
[0,3] = 3, 9, 1, 23 − 8 = −52 − (−5) = 77

Player 1 should take the 2 (the smaller end!). Whatever player 2 then takes from [3, 9, 1], the 9 becomes available to player 1. Totals: player 1 gets , player 2 gets 4.

The LeetCode examples: [1, 5, 2] gives −2 (player 1 loses), [1, 5, 233, 7] gives 222 (player 1 wins by taking 1, then grabbing 233).

graph TD
    F["[0,3] = 7"] -->|"take 3"| L1["[1,3] = 8"]
    F -->|"take 2"| R1["[0,2] = -5"]
    R1 -->|"take 3"| RL["[1,2] = 8"]
    R1 -->|"take 1"| RR["[0,1] = 6"]

The two-player trick: store the difference, not two totals

Storing "my score" and "your score" separately leads to a messy pair of DPs that call each other. The difference collapses both into one table, because the opponent faces the same kind of position with the same goal. This works for every zero-sum game with additive scores: Stone Game II, III, VII, AtCoder "Deque", and more.

Deeper: why Stone Game (LeetCode 877) is always a win for player 1

In 877 the row has an even length and an odd total. Colour positions alternately: even indices and odd indices. Player 1 can always take every even-indexed pile, or every odd-indexed pile: whenever it is their turn, both ends have different colours, and after their move the opponent sees two ends of the other colour, so the opponent can only ever take the colour player 1 is not collecting. One colour has a strictly larger total (the total is odd, so they cannot tie), so player 1 picks that colour and wins. The answer is return true. The DP is still the right tool when those guarantees are removed (LeetCode 486).

5. Nim, game sums and Grundy numbers

Nim: several piles; a move removes any positive number of stones from one pile; whoever cannot move loses. Bouton's theorem: the position is losing for the player to move iff the XOR of the pile sizes is 0. Piles 3, 4, 5: , so the first player wins (take 2 from the pile of 3, leaving 1, 4, 5 with XOR 0).

Now combine games. You play several subtraction games side by side, and each turn you move in one of them. The win/lose table of each game alone is not enough to decide the combined game (two W positions can make an L sum, or a W sum). What is enough is one number per position, the Grundy number (or nimber):

where (minimum excludant) of a set is the smallest non-negative integer not in it: , .

Two facts make this useful (Sprague–Grundy theorem):

  1. iff is losing. So the Grundy table contains the win/lose table.
  2. The Grundy number of a sum of games is the XOR of the Grundy numbers of the parts.

For , the Grundy numbers are (computed and checked by the test code):

n:  0 1 2 3 4 5 6 | 7 8 9 10 11 12 13 | 14 ...
g:  0 1 0 1 2 3 2 | 0 1 0  1  2  3  2 | 0 ...      period 7

Example: two piles of sizes 5 and 9 in the {1,3,4} game. : first player wins. (The test code confirms this by brute-forcing the two-pile game directly.) Notice that pile 9 alone is a loss for the player to move, yet the sum is a win: the win/lose bits alone could not have told you that.

The theory behind this, with proofs, misère play and many more games, belongs to Game Theory in the math module. For game DP, remember the recipe: compute Grundy numbers with the same DP as win/lose, replacing "is there an L child?" with "mex of the children's numbers".

6. Retrograde analysis: games with cycles and draws

So far, every move made the position "smaller". In many games it does not: pieces move back and forth on a board, and the same position can recur. Then:

  • The plain recursion can loop forever (a position asks about a position that asks about the first one).
  • There may be draws: positions from which neither side can force a win, and perfect play goes on forever (or until a repetition rule ends it).

Retrograde analysis solves this by working backwards from the positions whose value is known, the terminal positions, using BFS on the reversed move graph. It is the same idea as Kahn's algorithm in Topological Sort: keep a counter per position, and only decide a position when you have enough information.

The rules, for "the player who cannot move loses":

  1. Every position with no moves is L. Put them in a queue.
  2. Every other position starts unknown, with a counter remaining[u] = its number of moves.
  3. Pop a decided position . For each predecessor (a position with a move ) that is still unknown:
    • If is L: has a move to a losing position, so is W. Decide it, enqueue it.
    • If is W: one more of 's moves is known to be bad. Decrement remaining[u]. If it reaches 0, every move from leads to W, so is L. Decide it, enqueue it.
  4. When the queue empties, every position still unknown is a draw.

Example game graph (8 positions; arrows are moves; 3 and 7 have no moves):

graph LR
    N0["0"] --> N1["1"]
    N0 --> N2["2"]
    N1 --> N3["3 no moves"]
    N2 --> N3
    N2 --> N4["4"]
    N4 --> N5["5"]
    N5 --> N4
    N5 --> N6["6"]
    N6 --> N7["7 no moves"]

Retrograde trace (from the test script):

StepPopEffect on predecessorsNewly decided
0—positions 3 and 7 have no moves3 = L, 7 = L
13 (L)1 → 3 is a move to L; 2 → 3 is a move to L1 = W, 2 = W
27 (L)6 → 76 = W
31 (W)remaining[0]: 2 → 1—
42 (W)remaining[0]: 1 → 0, every move of 0 is to W0 = L
56 (W)remaining[5]: 2 → 1—
60 (L)no predecessors—
endqueue empty4 and 5 never decided4 = DRAW, 5 = DRAW

Result: 0 L, 1 W, 2 W, 3 L, 4 DRAW, 5 DRAW, 6 W, 7 L. Position 5 is the interesting one: it has a move to 6, but 6 is W (for the opponent), so that move loses. Its other move goes to 4, which can only go back to 5. The player at 5 avoids losing by shuttling 5 → 4 → 5 → … forever: a draw.

The test code checks this result, and 500 random graphs, against a brute-force definition: "the mover can force a win within moves" computed by depth-limited recursion with .

Why not just memoised DFS with a "visiting" flag?

A common attempt: mark a position "in progress" while recursing; if you reach an in-progress position, call it a draw. This is wrong: the value you assign depends on the order in which the DFS explores moves, and a position may be labelled a draw on one path when the correct value (found later through another move) is a win. Retrograde analysis never guesses: it only labels a position when the label is proven.

7. Cat and Mouse: retrograde colouring on (mouse, cat, turn)

LeetCode 913. An undirected graph. The mouse starts at node 1 and moves first, the cat starts at node 2, node 0 is a hole. Each turn the player to move must move along an edge; the cat may not enter the hole. The cat wins if it lands on the mouse; the mouse wins if it reaches the hole; if a position repeats, the game is a draw. Return 1 (mouse wins), 2 (cat wins) or 0 (draw).

State: (mouse node, cat node, whose turn). With nodes that is at most states. Terminal states: mouse at 0 → mouse wins; mouse and cat on the same node (not 0) → cat wins. Both regardless of whose turn. Retrograde: exactly section 6, with two twists:

  • Outcomes are "mouse wins" / "cat wins" instead of W/L, so "a move to a state good for the mover" decides the predecessor immediately; "a move to a state bad for the mover" decrements its counter.
  • The counter for a cat-to-move state is the cat's degree minus 1 if the cat is next to the hole (it may not go there).

Unreached states are draws. The "draw on repetition" rule in the statement matches "infinite play" here: if a player can force a win at all, they can force it without repeating a position, so the retrograde labels are exactly the answers. (A full Python solution is in the practice ladder.)

Example graph (adjacency lists)AnswerWhy
[[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]0 (draw)retrograde analysis never labels the start state: neither side can force a result
[[1,3],[0],[3],[0,2]]1 (mouse)the mouse at 1 is next to the hole and moves first
Deeper: the move-limit shortcut and why it is risky

Many solutions to Cat and Mouse use memoised recursion with a turn counter and declare a draw after "enough" turns (often ). That cut-off is a guess about how long a forced win can take. It needs a proof for the specific game, and a too-small limit produces wrong answers on adversarial graphs. Retrograde analysis needs no limit: it is linear in the number of (state, move) pairs, and its labels are proven correct by induction.

8. Alpha-beta pruning: when the table does not fit

For chess or Go there are far too many positions for a table. Programs search the game tree from the current position to a fixed depth with minimax, and use alpha-beta pruning to skip branches that cannot change the result: if you have already found a move that guarantees you , and the opponent has a reply to some other move that holds you below , you can stop examining that other move. With perfect move ordering, alpha-beta examines about leaves instead of (Knuth and Moore, 1975), which doubles the depth searchable in the same time.

Alpha-beta and DP combine: chess engines store already-searched positions in a transposition table (a hash map from position to value, i.e. memoisation), and look up endgame positions in retrograde-computed tablebases. A tiny negamax with alpha-beta on the Predict the Winner game:

import random


def minimax(a, i, j, counter):
    """Plain negamax: score difference for the player to move on a[i..j]."""
    counter[0] += 1
    if i > j:
        return 0
    return max(a[i] - minimax(a, i + 1, j, counter), a[j] - minimax(a, i, j - 1, counter))


def alphabeta(a, i, j, alpha, beta, counter):
    """Same value, but skips moves that cannot change the result."""
    counter[0] += 1
    if i > j:
        return 0
    best = float("-inf")
    for gain, ni, nj in ((a[i], i + 1, j), (a[j], i, j - 1)):
        # we need gain - child inside (alpha, beta), i.e. child inside (gain - beta, gain - alpha)
        val = gain - alphabeta(a, ni, nj, gain - beta, gain - alpha, counter)
        best = max(best, val)
        alpha = max(alpha, val)
        if alpha >= beta:                  # the opponent will never allow this line
            break
    return best


row = [3, 9, 1, 2, 7, 4, 8, 6, 5, 10]
plain, pruned = [0], [0]
v_plain = minimax(row, 0, len(row) - 1, plain)
v_ab = alphabeta(row, 0, len(row) - 1, float("-inf"), float("inf"), pruned)
assert v_plain == v_ab
assert plain[0] == 2 ** (len(row) + 1) - 1          # the full tree
assert pruned[0] < plain[0]
print("value", v_ab, "| minimax nodes", plain[0], "| alpha-beta nodes", pruned[0])
rng = random.Random(5)
for _ in range(200):
    r = [rng.randint(-10, 30) for _ in range(rng.randint(1, 10))]
    assert alphabeta(r, 0, len(r) - 1, float("-inf"), float("inf"), [0]) == minimax(r, 0, len(r) - 1, [0])

The window shifts by gain because the child's value is subtracted from gain: if the child must keep gain - child inside , then child must lie inside . Pruning gives the same value as plain minimax; it only skips work. For this 10-number row the full tree has 2,047 nodes and alpha-beta visits 1,004 of them (printed by the script). The DP has only 55 interval states. When the state space fits in memory, DP beats search; when it does not, search with pruning and memoisation is the tool.

The ladder: brute force → better → optimal

Problem: Predict the Winner on a row of numbers.

Rung 1: plain minimax recursion

best(i, j) = max(a[i] - best(i+1, j), a[j] - best(i, j-1)) with no memo. Each call branches twice and the depth is : time. For about a million calls; for , a trillion.

Rung 2: minimax with alpha-beta

Same recursion with pruning. Still exponential in the worst case (bad move ordering prunes nothing), roughly with perfect ordering. Useful when there is no small state to memoise.

Rung 3: memoised recursion over (i, j)

The only thing that matters about a position is which contiguous piece a[i..j] remains. There are such pieces, each computed once with work: time and space.

Rung 4: bottom-up interval table

Fill by increasing length (code in Implementation). time, no recursion.

Rung 5: one row

dp[i][j] reads dp[i+1][j] and dp[i][j-1]. Iterate i from down to 0 and j from i up: a single array dp[j] holds row i+1 before it is overwritten. space.

RungMethodTimeSpaceWhy it is better than the rung above
1Plain minimax stackBaseline; obviously correct
2Alpha-beta worst, ~ bestSkips provably irrelevant branches
3Memoised minimaxEach of the positions solved once
4Interval tabulationNo recursion, simple loops
5Rolling rowSame time, linear memory

For win/lose games on general graphs, the ladder is: plain recursion (may not terminate on cycles) → memoised recursion (correct only on DAGs) → retrograde analysis (, correct with cycles and draws).

Correctness

Win/lose rule on a DAG. Claim: the DP labels every position correctly. Induction on the length of the longest play from the position (finite on a DAG). A position with no moves is a loss for the mover by the rules. Otherwise, all successors have shorter longest plays, so by induction their labels are correct. If some successor is L, moving there leaves the opponent in a position they lose with perfect play, so the mover wins. If all successors are W, every move hands the opponent a position they win, so the mover loses. This is exactly Zermelo's backward-induction argument.

Score-difference DP. Claim: dp[i][j] is the optimal (mover − opponent) difference on a[i..j]. Induction on length. Taking a[i] gives the mover a[i] now; afterwards the opponent is the mover on a[i+1..j] and, playing optimally, achieves difference dp[i+1][j] from their point of view, which is -dp[i+1][j] from ours. The mover chooses the better of the two ends. Optimal substructure holds because the future depends only on the remaining interval, not on how the totals got there: differences add.

Periodicity. win[n] (and g[n]) is a function of the previous values. A window of booleans has possibilities (Grundy values are at most , so possibilities); by pigeonhole two windows coincide, and a deterministic recurrence repeats from then on.

Sprague–Grundy (sketch). Show L: from every move goes to a non-zero position (0 is not among the children, by definition of mex); from some move reaches a child with Grundy value 0 (mex is the smallest missing value, so 0 is present). This is the win/lose rule. The XOR property needs a separate argument (the same one Bouton used for Nim); see Game Theory or Winning Ways.

Retrograde analysis. Claim 1: every label it assigns is correct. Induction on the order of labelling. A terminal L is correct. A position labelled W has a move to an already-labelled L, correct by induction. A position labelled L has had all its moves counted off by already-labelled W successors, correct by induction. Claim 2: every unlabelled position is a draw. Take an unlabelled . It has no move to an L position (else it would be W), and at least one move to a non-W position (else its counter would reach 0); that non-W successor is unlabelled. So the mover at can always move to an unlabelled position, never into an L position, and from any unlabelled position the opponent likewise can never reach an L position for us. Neither side can force reaching a terminal loss for the other, so play can be kept infinite: a draw. Every position is pushed into the queue at most once and every edge is examined at most once from its head: .

Complexity

ProblemTimeSpaceNotes
Subtraction game, positions, moves, or rollingGrundy: same, plus mex in
Period detection over computed values naivethen per query via
Predict the Winner / Stone Game or interval DP
Nim with pilesXOR
Retrograde analysis positions, moves
Cat and Mouse ( nodes, edges) states; each state's predecessors come from one player's adjacency list
Minimax tree search, branching , depth alpha-beta: best case

The real limit of game DP is the number of positions. Tic-tac-toe has 5,478 legal positions, easy. Connect Four on the standard board has about (it was solved in 1988 with search plus knowledge, not a full table). Chess has around ; only endgames with few pieces fit in a table.

Implementation

Three complete programs: Predict the Winner (score-difference interval DP), a subtraction game with win/lose table, Grundy numbers and period detection, and retrograde analysis on a game graph with draws. Each block runs the lesson's examples as tests. They were also checked against brute force: exhaustive recursion for the first two, a depth-limited win/lose definition on 500 random graphs for the third.

Predict the Winner (score difference)

from typing import List


def score_difference(nums: List[int]) -> int:
    """Best (first player - second player) total when both take from either end optimally."""
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = nums[i]                       # one number left: take it
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(nums[i] - dp[i + 1][j],   # take the left end
                           nums[j] - dp[i][j - 1])   # take the right end
    return dp[0][n - 1]


def predict_the_winner(nums: List[int]) -> bool:
    return score_difference(nums) >= 0           # a tie counts as a win for player 1


def brute(nums: List[int]) -> int:
    if not nums:
        return 0
    return max(nums[0] - brute(nums[1:]), nums[-1] - brute(nums[:-1]))


if __name__ == "__main__":
    assert score_difference([1, 5, 2]) == -2 and not predict_the_winner([1, 5, 2])
    assert score_difference([1, 5, 233, 7]) == 222 and predict_the_winner([1, 5, 233, 7])
    assert score_difference([3, 9, 1, 2]) == 7
    assert score_difference([7]) == 7
    assert predict_the_winner([2, 2])            # tie
    import random
    rng = random.Random(1)
    for _ in range(300):
        row = [rng.randint(0, 20) for _ in range(rng.randint(1, 9))]
        assert score_difference(row) == brute(row)
    print("predict-the-winner tests passed")
public class PredictTheWinner {
    static int scoreDifference(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = nums[i];       // one number left
        for (int len = 2; len <= n; len++)
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j],     // take the left end
                                    nums[j] - dp[i][j - 1]);    // take the right end
            }
        return dp[0][n - 1];
    }

    static boolean predictTheWinner(int[] nums) {
        return scoreDifference(nums) >= 0;                      // a tie counts as a win
    }

    public static void main(String[] args) {
        check(scoreDifference(new int[]{1, 5, 2}) == -2 && !predictTheWinner(new int[]{1, 5, 2}));
        check(scoreDifference(new int[]{1, 5, 233, 7}) == 222 && predictTheWinner(new int[]{1, 5, 233, 7}));
        check(scoreDifference(new int[]{3, 9, 1, 2}) == 7);
        check(scoreDifference(new int[]{7}) == 7);
        check(predictTheWinner(new int[]{2, 2}));
        System.out.println("predict-the-winner tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

int scoreDifference(const vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) dp[i][i] = nums[i];          // one number left
    for (int len = 2; len <= n; len++)
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = max(nums[i] - dp[i + 1][j],             // take the left end
                           nums[j] - dp[i][j - 1]);            // take the right end
        }
    return dp[0][n - 1];
}

bool predictTheWinner(const vector<int>& nums) { return scoreDifference(nums) >= 0; }

int main() {
    assert(scoreDifference({1, 5, 2}) == -2 && !predictTheWinner({1, 5, 2}));
    assert(scoreDifference({1, 5, 233, 7}) == 222 && predictTheWinner({1, 5, 233, 7}));
    assert(scoreDifference({3, 9, 1, 2}) == 7);
    assert(scoreDifference({7}) == 7);
    assert(predictTheWinner({2, 2}));
    cout << "predict-the-winner tests passed\n";
    return 0;
}
function scoreDifference(nums: number[]): number {
  const n = nums.length;
  const dp: number[][] = Array.from({ length: n }, () => new Array<number>(n).fill(0));
  for (let i = 0; i < n; i++) dp[i][i] = nums[i]; // one number left
  for (let len = 2; len <= n; len++)
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]); // left end, right end
    }
  return dp[0][n - 1];
}

function predictTheWinner(nums: number[]): boolean {
  return scoreDifference(nums) >= 0; // a tie counts as a win for player 1
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

check(scoreDifference([1, 5, 2]) === -2 && !predictTheWinner([1, 5, 2]));
check(scoreDifference([1, 5, 233, 7]) === 222 && predictTheWinner([1, 5, 233, 7]));
check(scoreDifference([3, 9, 1, 2]) === 7);
check(scoreDifference([7]) === 7);
check(predictTheWinner([2, 2]));
console.log("predict-the-winner tests passed");

Subtraction game: win/lose table, Grundy numbers, period

from functools import lru_cache
from typing import List, Tuple


def subtraction_game(moves: List[int], limit: int) -> Tuple[List[bool], List[int]]:
    """win[n] and grundy[n] for n = 0..limit, when a move removes any amount in `moves`."""
    win = [False] * (limit + 1)
    grundy = [0] * (limit + 1)
    for n in range(limit + 1):
        children = [n - s for s in moves if s <= n]
        win[n] = any(not win[c] for c in children)      # W iff some move reaches an L
        seen = {grundy[c] for c in children}
        g = 0
        while g in seen:                                 # mex: smallest value not seen
            g += 1
        grundy[n] = g
    return win, grundy


def find_period(seq: List[int], start: int = 0) -> int:
    """Smallest p such that seq[i] == seq[i + p] for every i >= start in range."""
    for p in range(1, (len(seq) - start) // 2 + 1):
        if all(seq[i] == seq[i + p] for i in range(start, len(seq) - p)):
            return p
    return -1


def as_string(win: List[bool]) -> str:
    return "".join("W" if w else "L" for w in win)


if __name__ == "__main__":
    win, g = subtraction_game([1, 3, 4], 21)
    assert as_string(win) == "LWLWWWWLWLWWWWLWLWWWWL"
    assert g[:14] == [0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2]
    assert all((g[n] == 0) == (not win[n]) for n in range(22))   # g = 0 exactly at L
    assert find_period(subtraction_game([1, 3, 4], 300)[1]) == 7
    assert find_period(subtraction_game([1, 2], 300)[1]) == 3
    assert find_period(subtraction_game([2, 5, 6], 300)[1]) == 11

    @lru_cache(maxsize=None)
    def brute(n: int) -> bool:                           # exhaustive check, no table
        return any(n >= s and not brute(n - s) for s in (1, 3, 4))
    assert all(brute(n) == win[n] for n in range(22))

    @lru_cache(maxsize=None)
    def two_piles(a: int, b: int) -> bool:               # sum of two {1,3,4} games, brute force
        return any(not two_piles(a - s, b) for s in (1, 3, 4) if s <= a) or \
               any(not two_piles(a, b - s) for s in (1, 3, 4) if s <= b)
    _, g = subtraction_game([1, 3, 4], 30)
    assert all(two_piles(a, b) == ((g[a] ^ g[b]) != 0) for a in range(31) for b in range(31))
    assert two_piles(5, 9) and not win[9]                # 9 alone loses, 5 + 9 wins
    print("subtraction-game tests passed")
import java.util.Arrays;

public class SubtractionGame {
    static boolean[] win;
    static int[] grundy;

    static void solve(int[] moves, int limit) {
        win = new boolean[limit + 1];
        grundy = new int[limit + 1];
        for (int n = 0; n <= limit; n++) {
            boolean[] seen = new boolean[moves.length + 2];   // mex is at most moves.length
            for (int s : moves) {
                if (s > n) continue;
                if (!win[n - s]) win[n] = true;               // a move to an L position
                if (grundy[n - s] < seen.length) seen[grundy[n - s]] = true;
            }
            int g = 0;
            while (seen[g]) g++;
            grundy[n] = g;
        }
    }

    static int findPeriod(int[] seq, int start) {
        for (int p = 1; p <= (seq.length - start) / 2; p++) {
            boolean ok = true;
            for (int i = start; i + p < seq.length && ok; i++) ok = seq[i] == seq[i + p];
            if (ok) return p;
        }
        return -1;
    }

    public static void main(String[] args) {
        solve(new int[]{1, 3, 4}, 21);
        StringBuilder sb = new StringBuilder();
        for (boolean w : win) sb.append(w ? 'W' : 'L');
        check(sb.toString().equals("LWLWWWWLWLWWWWLWLWWWWL"));
        check(Arrays.equals(Arrays.copyOf(grundy, 14), new int[]{0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2}));
        for (int n = 0; n <= 21; n++) check((grundy[n] == 0) == !win[n]);
        check((grundy[5] ^ grundy[9]) == 3);                  // 5 + 9 is a first-player win
        solve(new int[]{1, 3, 4}, 300);
        check(findPeriod(grundy, 0) == 7);
        solve(new int[]{1, 2}, 300);
        check(findPeriod(grundy, 0) == 3);
        solve(new int[]{2, 5, 6}, 300);
        check(findPeriod(grundy, 0) == 11);
        System.out.println("subtraction-game tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Table {
    vector<bool> win;
    vector<int> grundy;
};

Table subtractionGame(const vector<int>& moves, int limit) {
    Table t{vector<bool>(limit + 1, false), vector<int>(limit + 1, 0)};
    for (int n = 0; n <= limit; n++) {
        vector<bool> seen(moves.size() + 2, false);           // mex is at most moves.size()
        for (int s : moves) {
            if (s > n) continue;
            if (!t.win[n - s]) t.win[n] = true;               // a move to an L position
            if (t.grundy[n - s] < (int)seen.size()) seen[t.grundy[n - s]] = true;
        }
        int g = 0;
        while (seen[g]) g++;
        t.grundy[n] = g;
    }
    return t;
}

int findPeriod(const vector<int>& seq, int start) {
    int len = seq.size();
    for (int p = 1; p <= (len - start) / 2; p++) {
        bool ok = true;
        for (int i = start; i + p < len && ok; i++) ok = seq[i] == seq[i + p];
        if (ok) return p;
    }
    return -1;
}

int main() {
    Table t = subtractionGame({1, 3, 4}, 21);
    string s;
    for (bool w : t.win) s += w ? 'W' : 'L';
    assert(s == "LWLWWWWLWLWWWWLWLWWWWL");
    vector<int> first14(t.grundy.begin(), t.grundy.begin() + 14);
    assert((first14 == vector<int>{0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2}));
    for (int n = 0; n <= 21; n++) assert((t.grundy[n] == 0) == !t.win[n]);
    assert((t.grundy[5] ^ t.grundy[9]) == 3);                 // 5 + 9 is a first-player win
    assert(findPeriod(subtractionGame({1, 3, 4}, 300).grundy, 0) == 7);
    assert(findPeriod(subtractionGame({1, 2}, 300).grundy, 0) == 3);
    assert(findPeriod(subtractionGame({2, 5, 6}, 300).grundy, 0) == 11);
    cout << "subtraction-game tests passed\n";
    return 0;
}
function subtractionGame(moves: number[], limit: number): { win: boolean[]; grundy: number[] } {
  const win: boolean[] = new Array(limit + 1).fill(false);
  const grundy: number[] = new Array(limit + 1).fill(0);
  for (let n = 0; n <= limit; n++) {
    const seen = new Set<number>();
    for (const s of moves) {
      if (s > n) continue;
      if (!win[n - s]) win[n] = true; // a move to an L position
      seen.add(grundy[n - s]);
    }
    let g = 0;
    while (seen.has(g)) g++; // mex
    grundy[n] = g;
  }
  return { win, grundy };
}

function findPeriod(seq: number[], start: number): number {
  for (let p = 1; p <= Math.floor((seq.length - start) / 2); p++) {
    let ok = true;
    for (let i = start; i + p < seq.length && ok; i++) ok = seq[i] === seq[i + p];
    if (ok) return p;
  }
  return -1;
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const t = subtractionGame([1, 3, 4], 21);
check(t.win.map((w) => (w ? "W" : "L")).join("") === "LWLWWWWLWLWWWWLWLWWWWL");
check(t.grundy.slice(0, 14).join(",") === "0,1,0,1,2,3,2,0,1,0,1,2,3,2");
for (let n = 0; n <= 21; n++) check((t.grundy[n] === 0) === !t.win[n]);
check((t.grundy[5] ^ t.grundy[9]) === 3); // 5 + 9 is a first-player win
check(findPeriod(subtractionGame([1, 3, 4], 300).grundy, 0) === 7);
check(findPeriod(subtractionGame([1, 2], 300).grundy, 0) === 3);
check(findPeriod(subtractionGame([2, 5, 6], 300).grundy, 0) === 11);
console.log("subtraction-game tests passed");

Retrograde analysis on a game graph

adj[u] lists the positions reachable in one move from u; the player with no move loses. Output per position: "WIN", "LOSE" or "DRAW" for the player to move.

import random
from collections import deque
from functools import lru_cache
from typing import List


def retrograde(adj: List[List[int]]) -> List[str]:
    n = len(adj)
    preds: List[List[int]] = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            preds[v].append(u)                       # reversed move graph
    result = ["DRAW"] * n                            # undecided until proven
    remaining = [len(a) for a in adj]                # moves of u not yet known to lose
    queue = deque()
    for u in range(n):
        if not adj[u]:
            result[u] = "LOSE"                       # no move: the mover loses
            queue.append(u)
    while queue:
        v = queue.popleft()
        for u in preds[v]:
            if result[u] != "DRAW":
                continue                             # already decided
            if result[v] == "LOSE":
                result[u] = "WIN"                    # u can move into a losing position
                queue.append(u)
            else:
                remaining[u] -= 1                    # this move hands the opponent a win
                if remaining[u] == 0:
                    result[u] = "LOSE"               # every move does
                    queue.append(u)
    return result


def brute(adj: List[List[int]]) -> List[str]:
    """Definition-based oracle: can the mover force a win / a loss within d plies?"""
    @lru_cache(maxsize=None)
    def wins(u: int, d: int) -> bool:
        return d > 0 and any(loses(v, d - 1) for v in adj[u])

    @lru_cache(maxsize=None)
    def loses(u: int, d: int) -> bool:
        if not adj[u]:
            return True
        return d > 0 and all(wins(v, d - 1) for v in adj[u])

    d = 2 * len(adj) + 2
    return ["WIN" if wins(u, d) else "LOSE" if loses(u, d) else "DRAW" for u in range(len(adj))]


if __name__ == "__main__":
    adj = [[1, 2], [3], [3, 4], [], [5], [4, 6], [7], []]
    want = ["LOSE", "WIN", "WIN", "LOSE", "DRAW", "DRAW", "WIN", "LOSE"]
    assert retrograde(adj) == want == brute(adj)
    assert retrograde([[0]]) == ["DRAW"]             # a lone self-loop: play forever
    rng = random.Random(2)
    for _ in range(500):
        n = rng.randint(1, 9)
        g = [sorted({rng.randrange(n) for _ in range(rng.randint(0, 3))}) for _ in range(n)]
        assert retrograde(g) == brute(g), g
    print("retrograde tests passed")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class RetrogradeAnalysis {
    static String[] retrograde(int[][] adj) {
        int n = adj.length;
        List<List<Integer>> preds = new ArrayList<>();
        for (int i = 0; i < n; i++) preds.add(new ArrayList<>());
        for (int u = 0; u < n; u++) for (int v : adj[u]) preds.get(v).add(u);
        String[] result = new String[n];
        Arrays.fill(result, "DRAW");                        // undecided until proven
        int[] remaining = new int[n];
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int u = 0; u < n; u++) {
            remaining[u] = adj[u].length;
            if (adj[u].length == 0) { result[u] = "LOSE"; queue.add(u); }
        }
        while (!queue.isEmpty()) {
            int v = queue.poll();
            for (int u : preds.get(v)) {
                if (!result[u].equals("DRAW")) continue;
                if (result[v].equals("LOSE")) {
                    result[u] = "WIN";                      // u can move into a losing position
                    queue.add(u);
                } else if (--remaining[u] == 0) {
                    result[u] = "LOSE";                     // every move hands the opponent a win
                    queue.add(u);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] adj = {{1, 2}, {3}, {3, 4}, {}, {5}, {4, 6}, {7}, {}};
        String[] want = {"LOSE", "WIN", "WIN", "LOSE", "DRAW", "DRAW", "WIN", "LOSE"};
        check(Arrays.equals(retrograde(adj), want));
        check(Arrays.equals(retrograde(new int[][]{{0}}), new String[]{"DRAW"}));
        System.out.println("retrograde tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <cassert>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;

vector<string> retrograde(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<vector<int>> preds(n);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) preds[v].push_back(u);       // reversed move graph
    vector<string> result(n, "DRAW");                     // undecided until proven
    vector<int> remaining(n);
    queue<int> q;
    for (int u = 0; u < n; u++) {
        remaining[u] = adj[u].size();
        if (adj[u].empty()) { result[u] = "LOSE"; q.push(u); }
    }
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : preds[v]) {
            if (result[u] != "DRAW") continue;
            if (result[v] == "LOSE") {
                result[u] = "WIN";                         // u can move into a losing position
                q.push(u);
            } else if (--remaining[u] == 0) {
                result[u] = "LOSE";                        // every move hands the opponent a win
                q.push(u);
            }
        }
    }
    return result;
}

int main() {
    vector<vector<int>> adj = {{1, 2}, {3}, {3, 4}, {}, {5}, {4, 6}, {7}, {}};
    vector<string> want = {"LOSE", "WIN", "WIN", "LOSE", "DRAW", "DRAW", "WIN", "LOSE"};
    assert(retrograde(adj) == want);
    assert(retrograde({{0}}) == vector<string>{"DRAW"});
    cout << "retrograde tests passed\n";
    return 0;
}
type Outcome = "WIN" | "LOSE" | "DRAW";

function retrograde(adj: number[][]): Outcome[] {
  const n = adj.length;
  const preds: number[][] = Array.from({ length: n }, () => []);
  for (let u = 0; u < n; u++) for (const v of adj[u]) preds[v].push(u); // reversed move graph
  const result: Outcome[] = new Array(n).fill("DRAW"); // undecided until proven
  const remaining = adj.map((a) => a.length);
  const queue: number[] = [];
  for (let u = 0; u < n; u++)
    if (adj[u].length === 0) {
      result[u] = "LOSE";
      queue.push(u);
    }
  for (let head = 0; head < queue.length; head++) {
    const v = queue[head];
    for (const u of preds[v]) {
      if (result[u] !== "DRAW") continue;
      if (result[v] === "LOSE") {
        result[u] = "WIN"; // u can move into a losing position
        queue.push(u);
      } else if (--remaining[u] === 0) {
        result[u] = "LOSE"; // every move hands the opponent a win
        queue.push(u);
      }
    }
  }
  return result;
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const adj = [[1, 2], [3], [3, 4], [], [5], [4, 6], [7], []];
check(retrograde(adj).join(",") === "LOSE,WIN,WIN,LOSE,DRAW,DRAW,WIN,LOSE");
check(retrograde([[0]]).join(",") === "DRAW");
console.log("retrograde tests passed");

Notes on the choices: the retrograde code uses the string "DRAW" as "undecided" during the run, which is exactly what undecided positions become at the end. A position with duplicate moves to the same successor would be counted twice in remaining and also twice in preds, so the counts stay consistent; the tests use sets of moves anyway. The TypeScript queue uses a moving head index instead of shift(), which is per call on arrays.

Real-world uses

  • Chess endgame tablebases. Retrograde analysis over all positions with few pieces, storing win/draw/loss and distance to mate (or to a zeroing move). Thompson's 1986 work, Nalimov's tables, and today's Syzygy 7-piece tables (probed by engines such as Stockfish) are all this algorithm at enormous scale (Thompson, "Retrograde analysis of certain endgames", ICCA Journal 1986).
  • Solving games. Checkers (Schaeffer et al., Science 2007: a draw), Connect Four (James D. Allen and Victor Allis independently, 1988: first player wins), and Awari (Romein and Bal, 2002–2003: a draw, computed by parallel retrograde analysis over about 900 billion positions).
  • Game engines. Minimax with alpha-beta, iterative deepening and transposition tables (memoisation keyed by a Zobrist hash) powered chess programs from the 1970s to Deep Blue and modern Stockfish's search.
  • Verification and controller synthesis. Model checkers solve reachability games ("can the controller force the system into a safe state whatever the environment does?") with the attractor computation, the same backwards fixed point as retrograde analysis. It is also the core step of Zielonka's algorithm for parity games.
  • Security and robustness. Worst-case (adversarial) analysis is minimax: the defender chooses, the attacker replies. Interval DP with min/max layers appears in robust scheduling and in the analysis of guessing games (LeetCode's "Guess Number Higher or Lower II" is the toy version).
  • Game design. Designers of puzzle and board games compute win/lose tables to check that a starting position is fair, or that a puzzle has a unique solution.

Pitfalls & edge cases

  • Mixing up whose point of view a value is from. W/L and score differences are for the player to move. When you look at a child, flip the sign or the label.
  • Forgetting the "no moves" case. any([]) is false, so "no moves → L" falls out of the rule; but if you special-case with return True or initialise win[0] = True by mistake, the whole table flips. Read the rules: does the player who takes the last stone win (normal play) or lose (misère play)?
  • Ties. Predict the Winner counts a tie as a win for player 1 (>= 0); other problems want "strictly more" or a three-way answer (Stone Game III returns "Tie").
  • Greedy. "Take the bigger end" loses [3, 9, 1, 2]. Interviewers expect you to show a counterexample.
  • Memoised DFS on graphs with cycles. Infinite recursion, or order-dependent wrong labels. Use retrograde analysis.
  • Draw by repetition vs infinite play. Different rules can change the answers in exotic games. For "player who cannot move loses" games and Cat and Mouse, the retrograde draws are correct.
  • Cat and Mouse details. The cat may not enter the hole (subtract that edge from the cat's counter), and both "mouse in hole" and "cat on mouse" are terminal for both turns.
  • Periodicity assumed from 0. Check for a pre-period; compute a long prefix and verify.
  • Grundy numbers vs win/lose bits in sums of games. Two L components XOR to L, but W components can XOR to anything. Use Grundy numbers whenever games are added.
  • Overflow in score games. Score differences can reach the full total; with values up to and (AtCoder "Deque"), use 64-bit integers.

Variations

  • Stone Game II/III (prefix choices). The mover takes the next 1..k piles from the front: dp[i] = max over x (sum(i..i+x-1) - dp[i+x]), often with an extra parameter ( in Stone Game II).
  • Interval minimax with a cost. "Guess Number Higher or Lower II": dp[i][j] = min over guess x of (x + max(dp[i][x-1], dp[x+1][j])). Same interval shape as Interval DP.
  • Bitmask games. "Can I Win": players pick unused numbers 1..m until a total is reached. State = set of used numbers: Bitmask DP.
  • Games on trees. Remove an edge and the component without the root disappears (Green Hackenbush on trees): Grundy numbers combine by the "colon principle", children's values plus one, XORed. See Tree DP.
  • Misère games. Last mover loses. Misère Nim has a small fix (play normally until all piles are 0/1); general misère theory is hard.
  • Partizan games. Players have different moves (chess, Hackenbush with colours). Values are surreal numbers rather than nimbers (Berlekamp, Conway, Guy, Winning Ways).
  • Games with chance. Add average nodes: expectiminimax, a cross between this lesson and Probability DP.
  • Huge games. Monte Carlo tree search (the core of AlphaGo-style programs) replaces the full table with sampled playouts and statistics.
  • The full theory of impartial games, Sprague–Grundy proofs, octal games and misère play: Game Theory.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Nim Game (LeetCode 292) — One pile, take 1 to 3, last stone wins. Teaches building the W/L table by hand and spotting the period.

Hint

The losing positions are multiples of 4: return n % 4 != 0. Verify by computing the table for .

2. Divisor Game (LeetCode 1025) — From , move to where is a proper divisor of . Teaches a W/L table with irregular moves.

Hint

DP over with all divisors as moves. The table turns out to be "W iff is even": an even player can always take 1 and leave odd; odd numbers have only odd divisors, so they always leave even.

3. Stick Game (CSES 1729) — Given a set of allowed removals, print W or L for every pile size . The subtraction-game table directly.

Solution
def stick_game(n, moves):
    win = [False] * (n + 1)
    for i in range(1, n + 1):
        win[i] = any(m <= i and not win[i - m] for m in moves)
    return "".join("W" if w else "L" for w in win[1:])


assert stick_game(10, [1, 3, 4]) == "WLWWWWLWLW"

4. Stones (AtCoder DP Contest K) — Same game with up to and a given move set; print who wins. Teaches the table.

Solution
def stones(moves, k):
    win = [False] * (k + 1)
    for i in range(1, k + 1):
        win[i] = any(a <= i and not win[i - a] for a in moves)
    return "First" if win[k] else "Second"


assert stones([2, 3], 4) == "First"
assert stones([2, 3], 5) == "Second"
assert stones([2, 3], 7) == "First"
assert stones([1, 2, 3], 20) == "Second"
assert stones([1, 2, 3], 21) == "First"
assert stones([1], 100000) == "Second"

5. Stone Game (LeetCode 877) — Even number of piles, odd total, take from either end. Teaches the interval DP and the parity proof that player 1 always wins.

Hint

Run the Predict the Winner DP to convince yourself, then read the "Deeper" box in section 4.

6. Predict the Winner (LeetCode 486) — Section 4. The Implementation is a full solution.

Hint

dp[i][j] = max(a[i] - dp[i+1][j], a[j] - dp[i][j-1]); return dp[0][n-1] >= 0.

7. Deque (AtCoder DP Contest L) — Same game, , print the score difference. Teaches 64-bit care and the -memory version.

Solution
def deque_game(a):
    n = len(a)
    dp = [0] * (n + 1)                      # dp[j] holds row i+1 while computing row i
    for i in range(n - 1, -1, -1):
        dp[i] = a[i]
        for j in range(i + 1, n):
            dp[j] = max(a[i] - dp[j], a[j] - dp[j - 1])   # dp[j] is still row i+1 here
    return dp[n - 1]


assert deque_game([10, 80, 90, 30]) == 10
assert deque_game([10, 100, 10]) == -80
assert deque_game([10]) == 10
assert deque_game([3, 9, 1, 2]) == 7

8. Nim Game I (CSES 1730) — Classic multi-pile Nim. Teaches Bouton's XOR rule.

Hint

First player wins iff the XOR of all pile sizes is non-zero. Prove it to yourself with the subtraction-game Grundy code: with "take any amount", .

9. Stone Game III (LeetCode 1406) — Take 1, 2 or 3 stones from the front of a row (values may be negative). Teaches suffix score-difference DP and three-way answers.

Solution

dp[i] = best difference for the mover on the suffix from i. Try taking 1, 2 or 3.

def stone_game_iii(vals):
    n = len(vals)
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        best, taken = float("-inf"), 0
        for x in range(1, 4):
            if i + x > n:
                break
            taken += vals[i + x - 1]
            best = max(best, taken - dp[i + x])
        dp[i] = best
    return "Alice" if dp[0] > 0 else "Bob" if dp[0] < 0 else "Tie"


assert stone_game_iii([1, 2, 3, 7]) == "Bob"
assert stone_game_iii([1, 2, 3, -9]) == "Alice"
assert stone_game_iii([1, 2, 3, 6]) == "Tie"

10. Stone Game II (LeetCode 1140) — Take the next piles with , then . Teaches an extra state parameter.

Hint

State (i, M); value = best stones the mover collects from suffix i = suffix_sum[i] - min over x of f(i + x, max(M, x)). Memoise; .

11. Can I Win (LeetCode 464) — Players pick unused numbers from 1..m; whoever makes the running total reach the target wins. Teaches bitmask states.

Hint

State = bitmask of used numbers (the running total follows from it). W iff some unused number either reaches the target or leads to an L state. Check the "sum of all numbers is below the target" edge case first.

12. Guess Number Higher or Lower II (LeetCode 375) — Minimum money that guarantees a win when each wrong guess costs . Teaches minimax over intervals (you minimise, the adversary maximises).

Hint

dp[i][j] = min over x in [i..j] of x + max(dp[i][x-1], dp[x+1][j]), with dp[i][i] = 0.

13. Cat and Mouse (LeetCode 913) — Section 7. Teaches retrograde colouring on a product state space.

Solution
from collections import deque


def cat_mouse_game(graph):
    n = len(graph)
    MOUSE_TURN, CAT_TURN = 0, 1
    DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2
    color = [[[DRAW] * 2 for _ in range(n)] for _ in range(n)]
    remaining = [[[0] * 2 for _ in range(n)] for _ in range(n)]
    for m in range(n):
        for c in range(n):
            remaining[m][c][MOUSE_TURN] = len(graph[m])
            remaining[m][c][CAT_TURN] = len(graph[c]) - (0 in graph[c])   # cat can't enter the hole
    queue = deque()
    for c in range(1, n):
        for turn in (MOUSE_TURN, CAT_TURN):
            color[0][c][turn] = MOUSE_WIN                 # mouse in the hole
            queue.append((0, c, turn))
            color[c][c][turn] = CAT_WIN                   # cat on the mouse
            queue.append((c, c, turn))
    while queue:
        m, c, turn = queue.popleft()
        result = color[m][c][turn]
        prev_turn = 1 - turn
        if prev_turn == MOUSE_TURN:
            parents = [(pm, c) for pm in graph[m]]
        else:
            parents = [(m, pc) for pc in graph[c] if pc != 0]
        for pm, pc in parents:
            if color[pm][pc][prev_turn] != DRAW:
                continue
            mover_wins = (prev_turn == MOUSE_TURN and result == MOUSE_WIN) or \
                         (prev_turn == CAT_TURN and result == CAT_WIN)
            if mover_wins:
                color[pm][pc][prev_turn] = result         # the mover picks this move
                queue.append((pm, pc, prev_turn))
            else:
                remaining[pm][pc][prev_turn] -= 1
                if remaining[pm][pc][prev_turn] == 0:     # every move loses for the mover
                    color[pm][pc][prev_turn] = result
                    queue.append((pm, pc, prev_turn))
    return color[1][2][MOUSE_TURN]


assert cat_mouse_game([[2, 5], [3], [0, 4, 5], [1, 4, 5], [2, 3], [0, 2, 3]]) == 0
assert cat_mouse_game([[1, 3], [0], [3], [0, 2]]) == 1

14. Cat and Mouse II (LeetCode 1728) — A grid version with jump lengths and food; the mouse loses after 1000 turns. Teaches retrograde analysis on a grid, with the turn limit turned into "unresolved = cat wins".

Hint

States (mouse cell, cat cell, turn); moves are straight-line jumps up to the jump length, stopping at walls. Run retrograde colouring; any state still undecided at the end is a mouse loss under this problem's rules.

Common mistakes & interview follow-ups

"Why not greedy?" Give [3, 9, 1, 2]: greedy takes 3 and loses 5 to 10; optimal takes 2 and wins 11 to 4.

"Can you do it in O(n) memory?" Yes: iterate i downwards and keep one array over j (the AtCoder "Deque" solution above).

"What if positions can repeat?" Explain why memoised DFS breaks, then retrograde analysis with counters, and that unlabelled states are draws. Mention .

"There are several independent piles." Grundy numbers and XOR. Show that win/lose bits are not enough (pile 9 alone loses, piles 5 and 9 together win, in the {1,3,4} game).

" is ." Compute the table until it becomes periodic, then index by (after any pre-period).

"How does a chess engine do this?" Too many positions for a table: depth-limited minimax with alpha-beta, a transposition table (memoisation), and retrograde-computed endgame tablebases.

Mistakes interviewers watch for: evaluating children from the wrong player's view; returning true for a tie when the problem wants strict; forgetting the cat-can't-enter-the-hole rule; integer overflow in score sums; infinite recursion on cyclic games.

Quick quiz

1. In the game "take 1 or 2 stones, last stone wins", which pile sizes up to 10 are losing?

Answer

0, 3, 6 and 9: the multiples of 3.

2. In the {1, 3, 4} game, why is 7 losing?

Answer

Its moves go to 6, 4 and 3, which are all winning (each has a move to 2 or 0, which are losing). No move from 7 reaches a losing position.

3. dp[i][j] for [1, 5] is 4. What does that mean?

Answer

The player to move on [1, 5] ends 4 points ahead: they take 5, the opponent gets 1.

4. In the retrograde trace, why is position 0 decided only after both 1 and 2 are popped?

Answer

0 is losing only if every move leads to a winning position. Its counter starts at 2 and drops by one for each successor proven W; it reaches 0 after both.

5. Two {1,3,4} piles of sizes 2 and 9. Who wins?

Answer

: the player to move loses.

6. In Cat and Mouse, why must the cat's counter exclude the edge to the hole?

Answer

The cat may not move to node 0, so that edge is not a move. If counted, the counter would never reach 0 for a cat next to the hole, and some forced cat losses would wrongly stay "draw".

Further reading / sources

  • Elwyn Berlekamp, John H. Conway and Richard K. Guy, Winning Ways for Your Mathematical Plays (2nd ed., 2001–2004) — impartial games, Grundy numbers, subtraction games, misère play.
  • Charles L. Bouton, "Nim, a game with a complete mathematical theory", Annals of Mathematics 3, 1901.
  • R. P. Sprague, "Über mathematische Kampfspiele", Tôhoku Mathematical Journal, 1935; P. M. Grundy, "Mathematics and games", Eureka 2, 1939.
  • Ken Thompson, "Retrograde analysis of certain endgames", ICCA Journal 9(3), 1986.
  • Jonathan Schaeffer et al., "Checkers is solved", Science 317(5844), 2007.
  • John W. Romein and Henri E. Bal, "Solving Awari with Parallel Retrograde Analysis", IEEE Computer 36(10), 2003.
  • Donald E. Knuth and Ronald W. Moore, "An analysis of alpha-beta pruning", Artificial Intelligence 6(4), 1975.
  • Stuart Russell and Peter Norvig, Artificial Intelligence: A Modern Approach (4th ed.), chapter on adversarial search.
  • cp-algorithms, Games on arbitrary graphs (retrograde analysis) and Sprague-Grundy theorem.
  • AtCoder Educational DP Contest, problem list — K (Stones) and L (Deque) are game DPs.

Lessons: previous — Probability & Expected-Value DP · next — Matrix Exponentiation · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: BFS in Depth · Topological Sort · Graph Modeling · Backtracking & Recursion · Bit Manipulation · Interval DP · Game Theory.