Alpha-Beta Returns the Minimax Value
Claim
Alpha-beta search returns the same value at the root as full minimax search. Pruned subtrees do not affect the answer (Knuth and Moore 1975).
The Window Invariant
The proof proceeds by establishing a three-case invariant on what ALPHABETA\((s, \alpha, \beta)\) returns relative to the true minimax value \(V(s)\).
Invariant. ALPHABETA\((s, \alpha, \beta)\) returns a value \(r\) such that: - (In-window): \(r = V(s)\) when \(\alpha < V(s) < \beta\). - (Fail-high): \(r \ge \beta\) when \(V(s) \ge \beta\). - (Fail-low): \(r \le \alpha\) when \(V(s) \le \alpha\).
A fail-high value signals to the MIN parent that this MAX node is too good — MIN won’t choose it. A fail-low value signals to the MAX parent that this MIN node is too bad — MAX won’t choose it. In both cases the parent’s decision is unaffected by the exact value of \(r\).
Corollary. At the root, the call is ALPHABETA\((s, -\infty, +\infty)\), so \(-\infty < V(s) < +\infty\) always holds. The in-window case applies and the algorithm returns exactly \(V(s)\).
Proof of the Invariant
By structural induction on the depth \(d\) of the tree.
Base case (\(d = 0\), leaf). ALPHABETA returns EVAL\((s) = V(s)\), satisfying all three cases. \(\checkmark\)
Inductive step, MAX node at depth \(d \ge 1\). The algorithm iterates through children \(a_1, \ldots, a_b\), maintaining a running maximum \(v\) (initialized to \(-\infty\)) and updating \(\alpha \leftarrow \max(\alpha, v)\) after each child that does not trigger a cutoff.
Case: \(V(s) \ge \beta\) (fail-high). Some child \(a_j\) satisfies \(V(a_j) \ge V(s) \ge \beta\). When \(a_j\) is processed, it is a MIN node called with some window \((\alpha', \beta)\) where \(V(a_j) \ge \beta\). By the inductive hypothesis (fail-high for MIN nodes, symmetric argument), ALPHABETA\((a_j, \alpha', \beta)\) returns \(r_j \ge \beta\). The MAX node sets \(v \leftarrow \max(v, r_j) \ge \beta\) and triggers the beta cutoff, returning \(v \ge \beta\). \(\checkmark\)
Case: \(V(s) \le \alpha\) (fail-low). All children satisfy \(V(a_i) \le V(s) \le \alpha\). For each child \(a_i\) (MIN node), the current \(\alpha'\) at call time satisfies \(\alpha' \ge \alpha\) (because \(\alpha' = \max(\alpha, v)\) and \(\alpha\) only increases). Since \(V(a_i) \le \alpha \le \alpha'\), the inductive hypothesis gives ALPHABETA\((a_i, \alpha', \beta)\) returns \(r_i \le \alpha' \le \alpha'\). In particular \(r_i < \beta\) (as \(\alpha' \le v \le V(s) \le \alpha < \beta\)), so no beta cutoff fires. The running maximum \(v = \max_i r_i\) remains \(\le \max_i V(a_i) = V(s) \le \alpha\). Returned value \(\le \alpha\). \(\checkmark\)
Case: \(\alpha < V(s) < \beta\) (in-window). Let \(a_j\) be a child with \(V(a_j) = V(s)\) (the best child). We show the algorithm returns \(V(s)\).
First, no beta cutoff fires before \(a_j\) is processed: any earlier child \(a_i\) has \(V(a_i) \le V(s) < \beta\), so by induction (in-window or fail-low) its return value \(r_i \le V(a_i) < \beta\), so \(v < \beta\) throughout.
Second, when \(a_j\) is processed, the current window is \((\alpha_j, \beta)\) with \(\alpha_j = \max(\alpha, v_{\text{before }j}) \le \max(\alpha, V(s)) = V(s)\) (since each earlier \(r_i \le V(a_i) \le V(s)\), so \(v_{\text{before }j} \le V(s)\), and \(\alpha \le V(s)\)). If \(\alpha_j < V(a_j) = V(s) < \beta\), induction gives ALPHABETA\((a_j, \alpha_j, \beta)\) returns \(V(a_j) = V(s)\); if \(\alpha_j = V(s)\), some earlier child already returned \(V(s)\) and \(v = V(s)\).
Either way, \(v\) reaches \(V(s)\) by the time \(a_j\) is processed or earlier. After \(a_j\), \(\alpha \leftarrow V(s)\). All later children \(a_i\) (\(i > j\)) have \(V(a_i) \le V(s) = \alpha\), so by the fail-low case their returns \(\le \alpha\), leaving \(v = V(s)\). Final return \(= V(s)\). \(\checkmark\)
Inductive step, MIN node. The argument is symmetric, with \(\beta\) playing the role of \(\alpha\), alpha cutoffs playing the role of beta cutoffs, and \(\min\) replacing \(\max\). \(\square\)
Why Pruned Subtrees Don’t Matter
A beta cutoff at a MAX node fires when \(v \ge \beta\): the MAX node has already found a child worth at least \(\beta\), so its true value \(V(s) \ge \beta\). The parent MIN node set \(\beta\) equal to its current best value; since MIN will not choose a child with value \(\ge \beta\) when it already has a child \(\le \beta\), the exact value of this MAX node is irrelevant. The remaining children are safely skipped.
Alpha cutoffs are symmetric. In both cases the cutoff is not an approximation — it is a deduction that the subtree’s value falls outside the window where the parent would ever select it.