Optimal Search on Some Game Trees
Michael Tarsi · Journal of the ACM · 1983
It is proved that the dlrecUonal algorithm for solving a game tree is optimal, in the sense of average run trine, for balanced trees (a family containing all uniform trees).This result implies that the alpha-beta pruning method is asymptotJcally opttmal among all game searching algorithms. Categones and Subject