On the Optimality of Randomized $\alpha$-$\beta$ Search
Yanjun Zhang · SIAM Journal on Computing · 1995
It is shown that the expected number of leaves evaluated by randomized $\alpha$-$\beta$ search for evaluating uniform game trees of degree d and height h is $O((B_{d})^{h})$, where $B_{d} = d/2 + \ln d + O(1)$. It was shown by Saks and Wigderson [Proceedings of 27th Annual Symposium on Foundations of Computer Science (1986), pp. 29–38] that the optimal branching factor of randomized algorithms for evaluating uniform trees of degree d is $B_{d}^{*} = {(d - 1 + \sqrt {d^{2}+14d+1})} /{4 = {d/2}+O(1)}$. As $B_{d}/B_{d}^{*} = 1 + O(\ln d /d )$, randomized $\alpha$-$\beta$ search is asymptotically optimal for evaluating uniform game trees as the degree of tree increases.