Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 3 / c

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^{\prime }/2})$ leaves at depth $d^{\prime }$. More precisely, for a complete uniform game tree, the best leaf count is $b^{\lceil d^{\prime }/2\rceil }+b^{\lfloor d^{\prime }/2\rfloor }-1$. Equating the dominant costs givesConstant factors and rounding affect the exact horizon. Poor move ordering can leave the cost at $\Theta (b^{d^{\prime }})$, giving no asymptotic depth improvement. For $b=1$, there is no branching to prune and the doubling argument does not apply.^[ref]