Home | Contents | Submissions, editors, etc. | Login | Search | EJP
 Electronic Communications in Probability > Vol. 10 (2005) > Paper 28 open journal systems 


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


Abstract
We consider minimax trees with independent, identically distributed leaf values that have a continuous distribution function FV being strictly increasing on the range where 0< FV <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: PDF

Pages: 273-281

Published on: December 21, 2005
Bibliography
  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
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | EJP

Electronic Communications in Probability. ISSN: 1083-589X