A Limit Law for the Root Value of Minimax Trees

Tämur Ali Khan (Johann Wolfgang Goethe Universität, Germany)
Luc Devroye (McGill University, Canada)
Ralph Neininger (Wolfgang Goethe Universität, Germany)


We consider minimax trees with independent, identically distributed leaf values that have a continuous distribution function $F_V$ being strictly increasing on the range where $0 < F_V < 1$. It was shown by Pearl that the root value of such trees converges to a deterministic limit in probability without any scaling. We show that after normalization we have convergence in distribution to a nondegenerate limit random variable.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 273-281

Publication Date: December 21, 2005

DOI: 10.1214/ECP.v10-1168


  1. Ali Khan, T. and Neininger, R. Probabilistic analysis for randomized game tree evaluation. Mathematics and computer science. III , 163-174, Trends Math., Birkhäuser, Basel, 2004. Math. Review 2005g:68148
  2. Devroye, L. and Kamoun, O. Random minimax game trees. Random discrete structures (Minneapolis, MN, 1993) , 55-80, IMA Vol. Math. Appl., 76, Springer, New York, 1996. Math. Review 97b:68203
  3. Karp, R.M. and Zhang, Y. Bounded branching process and AND/OR tree evaluation. Random Structures Algorithms 7 (1995), 97-116. Math. Review 97d:60136
  4. Knuth, D.E. and Moore, R.W. An analysis of alpha-beta pruning. Artificial Intelligence 6 (1975), 293-326. Math. Review 52 #9714
  5. Nau, D.S. The last player theorem. Artificial Intelligence 18 (1982), 53-65. Math. Review 83f:68109
  6. Nau, D.S. An investigation of the causes of pathology in games. Artificial Intelligence 19 (1982), 257-278. Zentralblatt MATH 0503.68070
  7. Nau, D.S. Pathology on game trees revisited, and an alternative to minimaxing. Artificial Intelligence 21 (1983), 221-244. Math. Review 84k:68058
  8. Pearl, J. Asymptotic properties of minimax trees in game-searching procedures. Aritificial Intelligence 14 (1980), 113-126. Math. Review 81i:90208
  9. Saks, M. and Wigderson, A. Probabilistic boolean decision trees and the complexity of evaluating game trees. Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science , 29-38, Toronto, Ontario, 1986.
  10. Snir, M. Lower bounds on probabilistic linear decision trees. Theor. Comput. Sci. 38 (1985), 69-82. Math. Review 87g:68028
  11. Zhang, Y. The variance of two game tree algorithms. J. Algorithms 28 (1998), 21-39. Math. Review 99b:68169

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.