# Why is the number of examined nodes $O(b^{3d/4})$ in $\alpha$-$\beta$ pruning?

I'm taking a course 'Introduction to AI' and, in one of the tutorials, it was written that when pruning the game tree using $$\alpha$$-$$\beta$$ boundaries, the number of nodes that will be developed, when using random sort function for the children (i.e., in the average case) will be $$O(b^{3d/4})$$.

Since the proof is not in the scope of the course we weren't given one at the tutorial, so I tried looking for the proof online, but couldn't find anything, and I didn't think of anything myself. I wondered whether someone could give me a lead or refer me to some reading material that shows the full proof?

• I also found this claim in section 5.3.1 (p. 169) in Norvig and Russell's book (3rd edition), but there's also no proof. They just say that this holds for "moderate $b$".
– nbro
May 13, 2021 at 12:04