I am trying to understand the derivation of a time complexity for an alpha-beta pruning algorithm but up till now have not found any reasonable recourse.
Many recourses claim that if you take a full tree with a branching factor $b$ and the depth $d$, you end up evaluating the approximately the following number of leaves:
- $O(b^{\frac{d}{2}})$ for the best case (when the can order the moves based on their strength)
- $O(b^{\frac{3d}{4}})$ for a case where the values of the leaves are selected at random
Wikipedia and Artificial intelligence: a modern approach book back this up either with believe me this is a case or with a handwaving.
I hope that because this is effectively a mathematical problem about the expected number of leaves one should check in a full tree, there would be some smart mathematicians who can explain me the concept with less handwaving.
$\endgroup$ 41 Answer
$\begingroup$A formal proof for the best-case scenario can be found in:
- Donald Knuth, Ronald W. Moore (1975). An Analysis of Alpha-Beta Pruning. Artificial Intelligence, Vol. 6, No. 4, pp 293–326. (PDF)
I will not reproduce the complete proofs here since they might as well just be read from the original publication, but I will try to clarify how the proofs relate to the two cases mentioned in your question.
In Section 6, they provide and prove the following theorem:
Theorem 1. Consider a game tree for which the value of the root position is not $\pm \infty$, and for which the first successor of every position is optimum; i.e.,
$$F(a_1 \dots a_l) = \begin{cases} f(a_1 \dots a_l) & \textit{if } a_1 \dots a_l \textit{ is terminal,} \\ -F(a_1 \dots a_l) & \textit{otherwise.} \end{cases}$$
The alpha-beta procedure F2 examines precisely the critical positions of this game tree.
In this theorem:
- The equation is a "mathematically formal" way of stating that the best move is the first move we look at for every state in the game tree. This means that we're looking at the best case scenario for alpha-beta pruning here, i.e. the first case in your question.
- "The alpha-beta procedure F2" simply refers to pseudocode earlier in the paper, so they're simply talking about the search algorithm with alpha-beta pruning as commonly understood.
- The theorem (proof not reproduced from the paper here) states that in this scenario (best-case scenario for alpha-beta pruning), the algorithm has to examine (= evaluate) all "critical positions" of the game tree, and nothing else.
At the bottom of this post I added a section to explain how these critical positions are defined. That is important to understand if you want to be able to follow along the entire proof in the paper. However, for this answer, this is not crucial to understand, because later in the paper they move on (based on the theorem above) to the following corollary:
Corollary 1. If every position on levels $0, 1, \dots, l - 1$ of a game tree satisfying the conditions of Theorem 1 has exactly $d$ successors, for some fixed constant $d$, then the alpha-beta procedure examines exactly
$$d^{ \lfloor l / 2 \rfloor } + d^{ \lceil d / 2 \rceil} - 1$$
positions on level $l$.
This corollary addresses the specific situation of a fixed branching factor, which is also assumed in your question. Note that they use $l$ to denote the depth level, and $d$ to denote the branching factor. Using your notation (which I suppose is much more common in "modern" times), the result would be that the algorithm examines (= evaluates) precisely $b^{ \lfloor d / 2 \rfloor } + b^{ \lceil d / 2 \rceil} - 1$ nodes in the best-case scenario at every depth level $d$. Note that (unless I'm reading the corollary wrong here), this only specifies the number of positions evaluated at a particular depth level $d$, not the number of evaluations across all depth levels together in the entire tree. Such details get absorbed by the big-$O$ notation though, so using big-$O$ notation we still get the same result as stated in your question.
For the case with random leaf node values, note that Russel and Norvig's book says that the asymptotic complexity is $O((b / \log b)^d)$, rather than $O(b^{\frac{3d}{4}})$. This matches what we find in Theorem 5 in Knuth and Moore's paper linked above, which states that the number of evaluations $r(b)$ (that's how they denote the number of evaluations we're looking for in this case) is bounded as follows:
$$C_3 \frac{b}{\log b} \leq r(b) \leq C_4 \frac{b}{\log b},$$
where $C_3$ and $C_4$ are "certain positive constants" (which get absorbed and disappear in the big-$O$ notation). The proof for this can be found in the paper again. Note: the paper actually uses $d$ instead of $b$ for branching factor.
However, Russel and Norvig do state in their book that this asymptotic analysis only becomes accurate for unreasonably large branching factors $b > 1000$, which does not occur in the kinds of games that we use alpha-beta pruning for in practice, and that for low $b$ a more accurate approximation tends to be given by $O(b^{\frac{3d}{4}})$. This claim is likely based on the complete analysis in pages 19-29 of Knuth and Moore's paper, where various claims like $O(b^{0.75d})$ and $O(b^{0.76d})$ are discussed.
In the paper, they use a sequence of integers $a_1 \dots a_l$ to uniquely identify any position in the game tree at a depth level $l$. How they do this is best explained with an example; the sequence $1231$ is used to describe the position reached when we take the $1^{st}$ move, followed by the $2^{nd}$ move, followed by the $3^{rd}$ move, and finally followed by the $1^{st}$ move. So, every digit in the sequence denotes the move selected at the corresponding depth level. Then, they say that a position $a_1 \dots a_l$ is critical if and only if at least one of the following two conditions holds:
- $a_i = 1$ for all even depth levels $i$, OR
- $a_i = 1$ for all odd depth levels $i$
