v. Game DP, Minimax and Game Search

Two players alternate and both play optimally. The mechanics are ordinary DP or tree search; the twist is that the objective flips between levels. Pure win/lose impartial games are better handled by Grundy numbers; games with repeated positions by retrograde analysis.

Zermelo’s theorem (1913) is why any of this is well-defined: every finite, deterministic, perfect-information two-player game is determined — from every position exactly one of “the player to move can force a win,” “the opponent can force a win,” or “the player to move can force at least a draw” holds, and backward induction (minimax on the finite game tree, bottom-up) always finds which. Finiteness and perfect information both matter: infinite games can fail to be determined at all (without the axiom of choice’s weaker forms), and hidden information turns the problem into one over belief states, not positions.

Proof: Zermelo's theorem

Induction on the height of the game tree (finite, since the game terminates). A terminal position has a defined outcome by definition. At an internal position, by induction every child’s outcome is determined. If the mover has a child that is a forced win for them, moving there forces a win. Otherwise every child is either a forced win for the opponent or (at best) a forced draw; if some child is a forced draw, the mover can force at least a draw by moving there; if every child is a forced win for the opponent, every move hands the opponent a forced win, so the position itself is a forced win for the opponent. Exactly one case applies, so the position’s outcome is determined too, and the minimax value computed bottom-up is exactly this outcome. $■$

Situation	Method
impartial, win/lose only	Grundy numbers and XOR
win/lose, small state space	memoized W/L recursion (Combinatorial Games): terminal positions lose under normal play, win under misère
scored game (both maximize their own total)	advantage DP $dp[s]={\max }_t(\text{gain}(s\to t)-dp[t])$
different objectives per player	explicit minimax with a turn dimension
chance nodes	expectiminimax (expectation at chance nodes): Expected Value DP for cyclic dependencies
positions repeat (draws)	retrograde analysis
large tree, good evaluation function	alpha-beta with move ordering, iterative deepening, transposition table
large tree, no evaluation function	MCTS with UCT
proving a forced win	proof-number search (df-pn)

Score games: the advantage trick

Let $dp[s]$ be the current player’s advantage (their eventual score minus the opponent’s). Then $dp[s]={\max }_t(\text{gain}(s\to t)-dp[t])$: the minus sign encodes the role swap, so there is no separate min branch and no “whose turn” dimension. With total $T$ and root advantage $d$, the first player scores $\frac{T+d}{2}$. Example: take a coin from either end of a row (Coins in a Row).

ll takeEndsAdvantage(const vector<ll>& a) {             // first player's (own - opponent) with optimal play, O(n^2)
    int n = sz(a); vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 0));   // dp[l][r]: coins l..r-1 left
    for (int len = 1; len <= n; len++) for (int l = 0; l + len <= n; l++) {
        int r = l + len;
        dp[l][r] = max(a[l] - dp[l + 1][r], a[r - 1] - dp[l][r - 1]);
    }
    return dp[0][n];
}

When the players have asymmetric goals or move sets, carry the turn in the state: $V(s,\text{max})={\max }_{t}V(t,\text{min})$, $V(s,\text{min})={\min }_{t}V(t,\text{max})$. With chance nodes, $V(\text{chance})={\sum }_t{p}_{t}V(t)$ (expectiminimax); alpha-beta prunes poorly through expectations (“star” pruning variants exist), so for games with chance MCTS is the usual practical answer.

Proof: the advantage recurrence

Induction on the remaining game. If the player to move goes to $t$, they gain $\text{gain}(s\to t)$, and from $t$ the opponent, now to move, ends with an advantage $dp[t]$ over them (by induction, under optimal play from $t$). The mover’s final advantage is therefore $\text{gain}(s\to t)-dp[t]$, and they choose the best $t$. This is minimax on the zero-sum quantity “my score minus yours”, since what one player gains the other loses in this difference. If $A+B=T$ and $A-B=d$ then $A=\frac{T+d}{2}$. Checked against a plain minimax over all move sequences for rows of up to 12 coins.

Minimax, negamax and alpha-beta

Minimax: $V(s)=\text{eval}(s)$ at terminal nodes or at the depth limit, ${\max }_{t}V(t)$ when the maximizer moves, ${\min }_{t}V(t)$ when the minimizer moves. Negamax expresses every value from the point of view of the player to move, so $\min (a,b)=-\max (-a,-b)$ collapses the two cases into one code path (and removes a class of sign errors). Alpha-beta passes a window $(\alpha ,\beta )$: at a node where the mover already has $\alpha \ge \beta$, the opponent above would never allow this line, so the remaining children are pruned. The functions below search an explicit tree (ch[v] children, leaf[v] value for the player to move at leaf v); in an engine, replace the loops by generating moves and calling apply / undo.

struct GameTree { vector<vector<int>> ch; vector<int> leaf; ll visited = 0; };
 
int negamax(GameTree& T, int v) {
    T.visited++;
    if (T.ch[v].empty()) return T.leaf[v];
    int best = INT_MIN;
    for (int c : T.ch[v]) best = max(best, -negamax(T, c));
    return best;
}
 
int alphabeta(GameTree& T, int v, int alpha, int beta) {   // fail-hard: result clamped to [alpha, beta]
    T.visited++;
    if (T.ch[v].empty()) return max(alpha, min(beta, T.leaf[v]));
    for (int c : T.ch[v]) {
        alpha = max(alpha, -alphabeta(T, c, -beta, -alpha));
        if (alpha >= beta) break;                             // cutoff
    }
    return alpha;
}
 
int negascout(GameTree& T, int v, int alpha, int beta) {   // principal variation search
    T.visited++;
    if (T.ch[v].empty()) return max(alpha, min(beta, T.leaf[v]));
    bool first = true;
    for (int c : T.ch[v]) {
        int score;
        if (first) score = -negascout(T, c, -beta, -alpha), first = false;
        else {
            score = -negascout(T, c, -alpha - 1, -alpha);     // null window: is this move better than alpha?
            if (alpha < score && score < beta) score = -negascout(T, c, -beta, -score);   // yes: re-search
        }
        alpha = max(alpha, score);
        if (alpha >= beta) break;
    }
    return alpha;
}

With perfect move ordering alpha-beta visits about $b^{\lceil d/2\rceil }+b^{\lfloor d/2\rfloor }-1$ leaves instead of $b^d$ (Knuth and Moore, 1975): the reachable depth roughly doubles. With random ordering the gain is much smaller, which is why move ordering matters more than any other optimization. Worst case remains $O(b^d)$; space $O(d)$.

Move ordering	Idea
iterative deepening	search depth $1,2,3,\dots$; use each result to order the next; costs only a factor $\approx \frac{b}{b-1}$ more
transposition table	cache positions by hash; the stored best move is tried first
killer moves	moves that caused a cutoff at the same ply elsewhere
history heuristic	a global per-move score from past cutoffs
domain heuristics	captures first (MVV-LVA in chess), checks, central squares

Refinement	Idea
negamax	one code path instead of separate min / max
NegaScout / PVS	full window for the first move, null window $[\alpha ,\alpha +1]$ for the others, re-search on fail-high; 10–20% fewer nodes with good ordering, worse with bad ordering (re-searches)
MTD(f)	all searches are null-window, driven by bisection on the root value; elegant but needs a good transposition table, so PVS is the robust default most engines use
aspiration windows	start with a narrow window around the previous iteration’s score
quiescence search	extend past the depth limit on “noisy” positions (captures) to avoid the horizon effect
null-move pruning	give the opponent a free move; if still winning, prune
late move reductions	search later (presumably worse) moves at reduced depth

Zobrist hashing. Assign a random 64-bit number to every (square, piece) pair; the hash of a position is the XOR of the numbers of its occupied squares. A move updates it in $O(1)$: XOR the piece out of the old square and into the new one. This makes transposition tables practical, and the same trick hashes any set that changes by single-element updates.

struct Zobrist {                                         // hash of a board of `cells` cells with `kinds` piece types
    vector<vector<ull>> z; ull h = 0;
    Zobrist(int cells, int kinds, ull seed = 0x9e3779b97f4a7c15ULL) : z(cells, vector<ull>(kinds)) {
        mt19937_64 rng(seed); for (auto& r : z) for (auto& x : r) x = rng();
    }
    void toggle(int cell, int kind) { h ^= z[cell][kind]; }   // place or remove a piece
};

Proof: negamax, alpha-beta and PVS return the minimax value

Negamax. By induction, negamax(v) is the minimax value from the mover’s perspective: the mover maximizes over children, and a child’s value for the opponent is the negative of its value for the mover (zero-sum), so ${\max }_c(-\text{negamax}(c))$ is the minimax value.

Alpha-beta (fail-hard). Claim: for $\alpha <\beta$, alphabeta(v, α, β) returns $\mathrm{clamp}(m(v),\alpha ,\beta )$, where $m$ is the negamax value. Induction. At a leaf this is the code. At an internal node let the children be $c_1,c_2,\dots$ and keep the invariant ${\alpha }_k=\mathrm{clamp}(\max ({\alpha }_0,{\max }_{i\le k}-m(c_i)),{\alpha }_0,\beta )$, where ${\alpha }_0$ is the original $\alpha$. The call on $c_{k+1}$ with window $(-\beta ,-{\alpha }_k)$ returns $\mathrm{clamp}(m(c_{k+1}),-\beta ,-{\alpha }_k)$, so its negation is $\mathrm{clamp}(-m(c_{k+1}),{\alpha }_k,\beta )$ and the invariant is maintained. If ${\alpha }_k$ reaches $\beta$, the clamped maximum is $\beta$ whatever the remaining children are, so the cutoff returns the right value. At the end $\alpha$ is $\mathrm{clamp}(m(v),{\alpha }_0,\beta )$. With the window $(-\infty ,\infty )$ the result is exactly $m(v)$.

PVS. A null-window call $(\alpha ,\alpha +1)$ returns $\le \alpha$ iff $m\le \alpha$ (integer values), so a refuted move is correctly ignored; if it fails high and the score is below $\beta$, the move is re-searched with a proper window, whose clamped result equals the alpha-beta result. So PVS returns the same value as alpha-beta. Iterative deepening: with $b$ moves per node the iterations up to depth $d-1$ cost ${\sum }_{i<d}{b}^i<\frac{b^d}{b-1}$, a factor $\frac{1}{b-1}$ of the last iteration. All three functions were checked to agree with negamax on random trees (and alpha-beta and PVS never visited more nodes than negamax).

Proof-number search

A best-first search for proving or disproving a binary goal (“can White force a win?”). Every node carries a proof number pn (minimum number of leaves that must be proven true to prove it) and a disproof number dn.

Node	pn	dn
proven true	0	$\infty$
proven false	$\infty$	0
unknown leaf	1	1
OR node (the mover needs one winning child)	${\min }_c\mathrm{pn}(c)$	${\sum }_c\mathrm{dn}(c)$
AND node (every child must win)	${\sum }_c\mathrm{pn}(c)$	${\min }_c\mathrm{dn}(c)$

Loop: from the root, descend to the child with minimal pn at OR nodes and minimal dn at AND nodes until a leaf (the most-proving node: proving it advances the proof of the root most, and disproving it advances the disproof most); expand it, update pn/dn back to the root; stop when the root’s pn or dn is 0. Unlike alpha-beta, which searches to a uniform depth, PNS follows the shape of the tree and dives into narrow forced sequences, which is ideal for endgames and puzzles. Checkers was solved (Schaeffer et al., 2007) with proof-number variants as a major component.

// Proof-number search on an explicit AND/OR tree: kids[v] children, isOr[v], at leaves value[v] (true / false).
// Expands one node per iteration (children become visible only when expanded). Returns the proven root value.
bool proofNumberSearch(const vector<vector<int>>& kids, const vector<char>& isOr, const vector<char>& value) {
    const ll INF = LLONG_MAX / 4; int n = sz(kids);
    vector<ll> pn(n, 1), dn(n, 1); vector<char> expanded(n, 0); vector<int> par(n, -1);
    auto setLeaf = [&](int v) { if (kids[v].empty()) { pn[v] = value[v] ? 0 : INF; dn[v] = value[v] ? INF : 0; } };
    auto recompute = [&](int v) {
        ll a = isOr[v] ? INF : 0, b = isOr[v] ? 0 : INF;
        for (int c : kids[v]) {
            if (isOr[v]) a = min(a, pn[c]), b = min(INF, b + dn[c]);
            else a = min(INF, a + pn[c]), b = min(b, dn[c]);
        }
        pn[v] = a; dn[v] = b;
    };
    setLeaf(0);
    while (pn[0] != 0 && dn[0] != 0) {
        int v = 0;
        while (expanded[v]) {                                // descend to the most-proving node
            int best = -1;
            for (int c : kids[v]) if (best < 0 || (isOr[v] ? pn[c] < pn[best] : dn[c] < dn[best])) best = c;
            v = best;
        }
        expanded[v] = 1;
        for (int c : kids[v]) par[c] = v, setLeaf(c);
        recompute(v);
        for (int u = par[v]; u != -1; u = par[u]) recompute(u);
    }
    return pn[0] == 0;
}

Variant	Improvement
PN²	a second-level PN search at each leaf; much less memory
df-pn (depth-first PN)	depth-first with thresholds, linear memory: the standard modern version
PDS	proof and disproof number iterative deepening
weak PNS	initialise unknown leaves with heuristic pn/dn instead of 1/1
lambda search	combines PN search with threat-space search

Plain PNS keeps the whole tree in memory, its main weakness. Uses: endgame solvers for checkers, Go life-and-death, shogi tsume, Hex, connect-6, and any “is this position winnable?” puzzle. The transferable idea for contests: when searching for a witness, expand the node that is cheapest to resolve rather than searching uniformly (the same philosophy as branch and bound).

Proof: proof-number search returns the true value

The pn/dn rules are exact for proven subtrees: an OR node is proven iff some child is (pn $=\min =0$) and disproven iff all children are (dn $=\sum =0$), and dually for AND nodes, with $\infty$ for the impossible side. Each iteration expands one unexpanded node of the finite tree, so after finitely many iterations either the root is resolved or every node is expanded, in which case all values are exact and the root is resolved too. The descent always reaches an unexpanded node with finite pn and dn: it starts at the unresolved root (both finite), and an unresolved OR node has a child with finite pn equal to its pn (the minimum) and all children’s dn finite or it would be resolved; the analogous statement holds for AND nodes. Hence the loop terminates with the root’s minimax value. (The “most-proving node” optimality is Allis’s theorem, 1994.) Checked against direct evaluation on random AND/OR trees.

Monte Carlo tree search and UCT

MCTS chooses good moves without any evaluation function, from random playouts; it is the algorithm behind AlphaGo. Each iteration: (1) selection, descend from the root by a tree policy (UCT) while nodes are fully expanded; (2) expansion, add one child for an untried move; (3) simulation, play to the end with a fast default policy (uniformly random in the basic version); (4) backpropagation, add the result to the visit count $N$ and value sum $W$ of every node on the path, flipping the result at each level. At the end play the move with the most visits (more robust than the best average).

UCT (Kocsis and Szepesvári, 2006) treats each node’s children as a multi-armed bandit and picks the child maximizing
$\frac{W_i}{N_i}+C\sqrt{\frac{\ln N}{N_i}},$
exploitation plus an exploration bonus that shrinks as a child is sampled; unvisited children have infinite priority. UCB1 has $O(\log n)$ regret, optimal up to constants (Auer, Cesa-Bianchi and Fischer, 2002); a game tree is a recursive bandit, and UCT’s value estimates converge to minimax, the probability of a suboptimal root move tending to zero.

// MCTS with UCT for a game given by moves(state) and a terminal result, on integer states (for illustration:
// any game where the player who cannot move loses). Returns the index of the chosen move at the root.
struct MCTS {
    function<vector<int>(int)> moves; double C = 1.41; mt19937 rng{7};
    struct Node { int state, parent; vector<int> kids, untried; double W = 0; int N = 0; };
    vector<Node> T;
    int rollout(int s) {                                 // 1 if the player to move at s wins the random playout
        int turn = 0;
        while (true) { auto m = moves(s); if (m.empty()) return turn; s = m[rng() % m.size()]; turn ^= 1; }
    }
    int search(int root, int iterations) {
        T.clear(); T.push_back({root, -1, {}, moves(root)});
        for (int it = 0; it < iterations; it++) {
            int v = 0;
            while (T[v].untried.empty() && !T[v].kids.empty()) {                       // selection
                int best = -1; double bv = -1e18, lg = log((double)T[v].N);
                for (int c : T[v].kids) { double u = T[c].W / T[c].N + C * sqrt(lg / T[c].N); if (u > bv) bv = u, best = c; }
                v = best;
            }
            if (!T[v].untried.empty()) {                                                // expansion
                int s = T[v].untried.back(); T[v].untried.pop_back();
                T.push_back({s, v, {}, moves(s)}); T[v].kids.push_back(sz(T) - 1); v = sz(T) - 1;
            }
            double r = 1 - rollout(T[v].state);         // value for the player who moved INTO v
            for (int u = v; u != -1; u = T[u].parent) { T[u].N++; T[u].W += r; r = 1 - r; }  // backpropagation
        }
        int best = -1; for (int c : T[0].kids) if (best < 0 || T[c].N > T[best].N) best = c;
        return T[best].state;
    }
};

$C$	Behaviour
$0$	pure greedy: locks onto the first line that looks good, often badly wrong
$0.2$–$0.7$	exploitative: good when rollouts are informative and the tree is deep
$\sqrt{2}\approx 1.41$	theoretical default for rewards in $[0,1]$
$>2$	nearly uniform search, wastes budget

Tune $C$ empirically against a fixed opponent; it matters more than most other parameters.

	Minimax + alpha-beta	MCTS
needs an evaluation function	yes, and this is the hard part	no
search shape	uniform depth	asymmetric, selective
anytime	no (needs a full ply)	yes
best for	chess, checkers (good evaluators exist)	Go, Hex, general game playing
branching factor	poor beyond $b\approx 50$	good
tactical sharpness	excellent	can miss narrow forced lines

Improvements. RAVE / AMAF (share statistics between moves that appear anywhere in a playout; a large early speed-up in Go), domain-specific rollout policies (even a weak heuristic beats uniform random), neural guidance (AlphaZero: a value network replaces rollouts and PUCT $\frac{W_i}{N_i}+c_{\text{puct}}{P}_i\frac{\sqrt{N}}{1+N_i}$ with a learned prior $P_i$ replaces uniform exploration, which is most of why it searches so few nodes), UCB1-Tuned (uses the empirical variance), progressive bias (a decaying heuristic term $\frac{H_i}{N_i+1}$), progressive widening (expand children gradually for large or continuous action spaces), tree reuse (keep the subtree of the move actually played). Beyond games: A/B testing and online advertising (the original bandit setting), hyperparameter search (successive halving and Hyperband are bandit algorithms), heuristic contest problems (UCT-style selection over neighbourhood moves as an alternative to simulated annealing), Monte Carlo planning in MDPs and reinforcement learning.

Proof: what the MCTS code guarantees

The code maintains, for every node, $N$ = the number of iterations whose path went through it and $W$ = the number of those whose random playout was won by the player who made the move into the node (the result is flipped once per level, so each node scores from the correct side). Every child is visited before any child is selected by UCT (untried moves are expanded first), so the UCT expression is always defined. The convergence of UCT to the minimax move as the number of iterations grows is the theorem of Kocsis and Szepesvári (2006); the code itself was tested on Nim: with $2\cdot 10^4$ iterations it returned a winning move (to nim-sum 0) from every winning position with three heaps of size at most 3. On the subtraction game “take 1, 2 or 3” from heaps up to 40 it misses the winning move in about one case in five: long forced lines with uninformative random playouts are exactly the “can miss narrow forced lines” weakness in the table.

Related notes

• Combinatorial Games and Nim
• Interval DP (game DP on intervals)
• A*, IDA* and Branch and Bound
• Heuristic Optimization