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.