Alpha beta search time complexity

Question

I understand the basics of minimax and alpha-beta pruning. In all the literature, they talk about the time complexity for the best case is O(b^(d/2)) where b = branching factor and d = depth of the tree, and the base case is when all the preferred nodes are expanded first.

In my example of the "best case", I have a binary tree of 4 levels, so out of the 16 terminal nodes, I need to expand at most 7 nodes. How does this relate to O(b^(d/2))?

I don't understand how they come to O(b^(d/2)).

Please, can someone explain it to me? Thanks a lot!

Answer 1

In the worst case, where there is no node to be pruned, the full tree will be examined (or the complete tree up to the cutoff at a depth d). Alpha-beta pruning saves, but how much? In the best-case scenario, each node will examine 2b-1 grandchildren to decide on its value. But in the worst-case scenario, the node will examine b^2 grandchildren. Logically this means that the overall algorithm examined O( b^(d/2) ) nodes, the same as a worst-case algorithm whose cutoff is half of d.

For more information regarding the Best-Case Analysis of Alpha-Beta Pruning, refer the following link: http://www.cs.utsa.edu/~bylander/cs5233/a-b-analysis.pdf

If you are looking to learn more about Artificial Intelligence then you visit Artificial Intelligence(AI) Tutorial. Also, if you are appearing for job profiles of AI Engineer or AI Expert then you can prepare for the interviews on Artificial Intelligence Interview Questions.