Alpha-Beta with Perfect Ordering Is O(b^{d/2})
Claim
Alpha-beta search on a uniform \(b\)-ary minimax tree of depth \(d\) with perfect move ordering — best move first at every node — examines
\[ T(d) = b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1 = O(b^{d/2}) \]
leaf nodes. This is the same asymptotic count as full minimax on a tree with branching factor \(\sqrt{b}\), effectively doubling the searchable depth for a fixed node budget (Knuth and Moore 1975).
Setup
A depth-\(d\) minimax tree alternates MAX and MIN levels, with \(b\) children at each internal node and \(b^d\) leaves. The root is a MAX node. “Perfect ordering” means: at every MAX node the child with the highest minimax value is examined first; at every MIN node the child with the lowest minimax value is examined first.
Define two leaf-count functions:
- \(T(d)\): leaves examined by alpha-beta on a depth-\(d\) MAX-rooted tree in a normal call (\(\alpha = -\infty\), \(\beta = +\infty\); the node’s true value lies in the window).
- \(R(d)\): leaves examined on a depth-\(d\) MAX-rooted tree in a refutation call (\(\alpha = v^*\), \(\beta = +\infty\); the subtree’s true value is \(\leq v^*\), so its exact value cannot improve the parent MIN’s decision).
Recurrence for R(d): the refutation cost
A MAX node of depth \(d\) in a refutation call (true value \(v' \leq \alpha = v^*\), \(\beta = +\infty\)):
- No beta cutoff is possible (\(\beta = +\infty\)), so the MAX node examines all \(b\) children.
- Each child is a MIN node of depth \(d-1\), also in a refutation role (true value \(\leq v' \leq v^*\)), called with (\(\alpha = v^*\), \(\beta = +\infty\)).
- Each such MIN node (depth \(d-1\)) examines its first child only. With perfect MIN ordering the first child is a MAX node of depth \(d-2\) whose true value equals the MIN node’s true value, i.e., \(\leq v^*\). This MAX child returns some \(w \leq v^* = \alpha\), immediately triggering an alpha cutoff at the MIN node (\(v \leq \alpha\)). Cost per MIN child = \(R(d-2)\).
Therefore:
\[ R(d) = b \cdot R(d-2), \qquad R(0) = 1,\; R(1) = b. \]
Solving: \(R(d) = b^{\lceil d/2 \rceil}\).
Recurrence for T(d): the full evaluation cost
A MAX node of depth \(d\) in a normal call (true value \(v^*\), \(\alpha = -\infty\), \(\beta = +\infty\)):
- First child (MIN, depth \(d-1\), best child under perfect MAX ordering): fully evaluated. Returns \(v^*\). Alpha is updated to \(\alpha = v^*\). Cost = \(T(d-1)\).
- Each remaining \(b-1\) children (MIN, depth \(d-1\), true value \(< v^*\)): called with \((\alpha = v^*, \beta = +\infty)\), i.e., in a refutation role. Each examines only its first child (MAX, depth \(d-2\)) before triggering an alpha cutoff. Cost = \(R(d-2)\) each.
Therefore:
\[ T(d) = T(d-1) + (b-1)\cdot R(d-2), \qquad T(0) = 1,\; T(1) = b. \]
Closed form by induction
Claim: \(T(d) = b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1\).
Base cases. \(T(0) = 1 = 1+1-1\). \(T(1) = b = b+1-1\). \(\checkmark\)
Inductive step. Assume the formula holds for \(d-1\) and \(d-2\). Then:
\[ T(d) = T(d-1) + (b-1)\cdot b^{\lceil(d-2)/2\rceil}. \]
Case \(d\) even (\(d = 2k\)):
\[ T(2k) = T(2k-1) + (b-1)\cdot b^{k-1} = \bigl(b^k + b^{k-1} - 1\bigr) + (b-1)b^{k-1} = b^k + b^{k-1} - 1 + b^k - b^{k-1} = 2b^k - 1 = b^k + b^k - 1. \checkmark \]
Case \(d\) odd (\(d = 2k+1\)):
\[ T(2k+1) = T(2k) + (b-1)\cdot b^k = (2b^k - 1) + (b-1)b^k = 2b^k - 1 + b^{k+1} - b^k = b^{k+1} + b^k - 1. \checkmark \]
In both cases \(T(d) = b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1 = O(b^{d/2})\). \(\square\)
Comparison with full minimax
Full minimax examines \(\Theta(b^d)\) leaves. Alpha-beta with perfect ordering examines \(O(b^{d/2})\): the same tree can be searched to depth \(2d\) in the same time budget. For \(b = 10\) (roughly chess), this means going from 5-ply to 10-ply search — a dramatic practical gain.
The factor \(b^{d/2}\) equals \((\sqrt{b})^d\): alpha-beta with perfect ordering behaves like full minimax on a tree with branching factor \(\sqrt{b}\) (Knuth and Moore 1975).