Game DP

DP where two players alternate and both play optimally. The mechanics are ordinary DP; the twist is that the objective flips between levels.

Win/lose positions

For games where the loser is whoever cannot move:

A position is losing (for the player to move) iff every move leads to a winning position.
A position is winning iff some move leads to a losing position.

// win[s] = true if the player to move from s wins
bool solve(int s) {
    if (done[s]) return win[s];
    done[s] = true;
    win[s] = false;
    for (int t : moves(s))
        if (!solve(t)) { win[s] = true; break; }
    return win[s];
}

Terminal positions with no moves are losing under normal play, winning under misère play.

Score games — the advantage trick

When players accumulate scores, define dp[state] as the current player’s advantage (their eventual score minus the opponent’s). The recursion becomes uniform:

$dp[s]={\max }_{t\in \mathrm{moves}(s)}(\mathrm{gain}(s\to t)-dp[t]).$

The minus sign encodes the role swap — no separate min and max branches, no “whose turn is it” dimension.

// take from either end of an array
long long dp(int l, int r) {
    if (l > r) return 0;
    if (done[l][r]) return memo[l][r];
    done[l][r] = true;
    return memo[l][r] = max(a[l] - dp(l + 1, r), a[r] - dp(l, r - 1));
}
// player 1 wins iff dp(0, n-1) > 0; their score is (total + dp) / 2

Recovering the individual scores from the advantage $d$ and the total $T$: the first player gets $(T+d)/2$.

Minimax with an explicit turn

When the advantage trick does not apply (asymmetric goals, different move sets), carry the turn in the state:

int dp(int state, int turn) {
    if (terminal(state)) return value(state);
    if (turn == MAXIMIZER) { int best = -INF; for (t : moves) best = max(best, dp(t, MIN)); return best; }
    else                   { int best =  INF; for (t : moves) best = min(best, dp(t, MAX)); return best; }
}

For large search trees add alpha-beta pruning — see Minimax.

Impartial games — use Grundy instead

If both players have the same moves from every position (an impartial game), do not enumerate win/lose by hand. Compute Grundy numbers:

$G(s)=\mathrm{mex}\{G(t):t\in \mathrm{moves}(s)\},$

where $\mathrm{mex}$ is the smallest non-negative integer not in the set. Then $s$ is losing iff $G(s)=0$, and — crucially — a game that splits into independent sub-games has Grundy value equal to the XOR of the parts (Sprague-Grundy).

int grundy(int s) {
    if (done[s]) return g[s];
    done[s] = true;
    set<int> st;
    for (int t : moves(s)) st.insert(grundy(t));
    int m = 0; while (st.count(m)) m++;
    return g[s] = m;
}

This is a genuine superpower: a game on $k$ independent piles has $\prod$-many states, but Grundy reduces it to computing $k$ small values and XORing them.

Games with chance

Add expectation at chance nodes:

$dp[s]=\{\begin{array}{ll}{\max }_{t}dp[t]& \text{player’s move}\\ {\sum }_t{p}_{st}dp[t]& \text{chance node}\end{array}$

See Probability DP for handling self-loops and cyclic dependencies.

The checklist

1. Impartial? (same moves for both) → Grundy numbers and XOR.
2. Partizan but scored? → advantage DP with the minus trick.
3. Different objectives? → explicit minimax with a turn dimension.
4. Cyclic positions? → retrograde analysis: BFS backwards from terminal positions, counting each position’s remaining unresolved moves.
5. Huge state space? → alpha-beta or MCTS.

Retrograde analysis

When positions can repeat (so plain memoization loops), work backwards:

// deg[s] = number of moves out of s; process a queue of resolved positions
// if a successor is losing -> s is winning
// if all successors are winning (deg drops to 0) -> s is losing
// positions never resolved are DRAWS

This is the only correct approach when draws by infinite play are possible, and it is how endgame tablebases are built.

See also: Game Theory · Grundy Numbers · Interval DP