The PDF file you selected should load here if your Web browser has a PDF reader plug-in installed (for example, a recent version of Adobe Acrobat Reader).

Alternatively, you can also download the PDF file directly to your computer, from where it can be opened using a PDF reader. To download the PDF, click the Download link below.

If you would like more information about how to print, save, and work with PDFs, Highwire Press provides a helpful Frequently Asked Questions about PDFs.

Download this PDF file Fullscreen Fullscreen Off


  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.