= Solution
\b[With excellent <move ordering>, the new horizon is approximately $2d$; without a <move ordering> assumption, no doubling is guaranteed.] For $b>1$, a full <minimax search> to depth $d$ visits $\Theta(b^d)$ <search nodes>, so the budget $n$ has $d\approx\log_b n$. Perfectly ordered <alpha-beta pruning> evaluates only about $\Theta(b^{d'/2})$ leaves at depth $d'$. More precisely, for a complete uniform <game tree>, the best leaf count is $b^{\lceil d'/2\rceil}+b^{\lfloor d'/2\rfloor}-1$. Equating the dominant costs gives
$$
b^{d'/2}\approx n\approx b^d,\qquad \boxed{d'\approx2\log_b n\approx2d.}
$$
Constant factors and rounding affect the exact horizon. Poor <move ordering> can leave the cost at $\Theta(b^{d'})$, giving no asymptotic depth improvement. For $b=1$, there is no branching to prune and the doubling argument does not apply.<CS 188 minimax notes>[§3.2.1, dependence of pruning efficiency on child order]{ref}
Back to article page
