The solution for the branching factor of the alpha-beta pruning algorithm and its optimality

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

The solution for the branching factor of the alpha-beta pruning algorithm and its optimality

Full text

Pdf (532 KB)

Source

Communications of the ACM archive
Volume 25 , Issue 8 (August 1982) table of contents

Pages: 559 - 564

Year of Publication: 1982

ISSN:0001-0782

Author

Judea Pearl

Univ. of Califorina, Los Angeles, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 89, Citation Count: 15

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/358589.358616 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Baudet, G.M. On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence 10, 2 (April 1978), 173-199.
	2	Fuller, S.H., Gaschnig, J.G., and Gillogly, J.J. An analysis of the alpha-beta pruning algorithm. Department of Computer Science Report, Carnegie-Mellon University, (1973).
	3	Knuth, D.E., and Moore, R.N. An analysis of alpha-beta pruning. Artificial Intelligence 6 (1975), 293-326.
	4	Kuczma, M. Functional Equations in a Single Variable. Polish Scientific Publishers, Warszawa, (1968), p. 141.
	5	Pearl, J. Asymptotic properties of minimax trees and gamesearching procedures. Artificial Intelligence 14, 2 (Sept. 1980), 113-138,
	6	Pearl, J. A space-efficient on-line method of computing quantile estimates J. of Algorithms 2, 2 (June 1981) 24-28.
	7	Roizen, I. On the average number of terminal nodes examined by alpha-beta. UCLA-ENG-CSL-8108, Cognitive Systems Laboratory, University of California, Los Angeles, (1981).
	8	James R. Slagle , John E. Dixon, Experiments With Some Programs That Search Game Trees, Journal of the ACM (JACM), v.16 n.2, p.189-207, April 1969 [doi>10.1145/321510.321511]
	9	Stockman, G. A minimax algorithm better than alpha-beta? Artificial Intelligence 12, 2 (Aug. 1979), 179-196.
	10	Michael Tarsi, Optimal Search on Some Game Trees, Journal of the ACM (JACM), v.30 n.3, p.389-396, July 1983 [doi>10.1145/2402.322383]

CITED BY 15

	Bruce Abramson, Control strategies for two-player games, ACM Computing Surveys (CSUR), v.21 n.2, p.137-161, Jun. 1989
	Andrei Z. Broder , Anna Karlin , Prabhakar Raghavan , Eli Upfal, On the parallel complexity of evaluating game trees, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.404-413, January 28-30, 1991, San Francisco, California, United States
	Harold W. Martin , Terrance L. Seethoff, On optimal algorithms for solving bi-valued game trees, Proceedings of the 15th annual conference on Computer Science, p.254-260, February 1987, St. Louis, Missouri, United States
	Michael Tarsi, Optimal Search on Some Game Trees, Journal of the ACM (JACM), v.30 n.3, p.389-396, July 1983
	Harold W. Martin, Polynomial evaluations of bi-valued game trees, Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.319-326, February 1986, Cincinnati, Ohio, United States
	Yanjun Zhang, The variance of two game tree algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.268-277, January 05-07, 1997, New Orleans, Louisiana, United States
	Guo-Jie Li , Benjamin W. Wah, Computational Efficiency of Parallel Combinatorial OR-Tree Searches, IEEE Transactions on Software Engineering, v.16 n.1, p.13-31, January 1990
	Claude G. Diderich, A bibliography on minimax trees, ACM SIGACT News, v.24 n.4, p.82-89, Dec. 1993
	R. M. Karp , Y. Zhang, On parallel evaluation of game trees, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.409-420, June 18-21, 1989, Santa Fe, New Mexico, United States
	Eduardo Sany Laber, A randomized competitive algorithm for evaluating priced AND/OR trees, Theoretical Computer Science, v.401 n.1-3, p.120-130, July, 2008
	ChenGuang Liu , Kazuyuki Tanaka, Eigen-distribution on random assignments for game trees, Information Processing Letters, v.104 n.2, p.73-77, October, 2007
	Matthew L. Ginsberg, GIB: imperfect information in a computationally challenging game, Journal of Artificial Intelligence Research, v.14 n.1, p.303-358, January 2001
	Judea Pearl, Heuristic search theory: survey of recent results, Proceedings of the 7th international joint conference on Artificial intelligence, p.554-562, August 24-28, 1981, Vancouver, BC, Canada
	Aske Plaat , Jonathan Schaeffer , Wim Pijls , Arie De Bruin, Best-first fixed-depth game-tree search in practice, Proceedings of the 14th international joint conference on Artificial intelligence, p.273-279, August 20-25, 1995, Montreal, Quebec, Canada
	Igor Roizen , Judea Pearl, A minimax algorithm better than alpha-beta? Yes and No, Artificial Intelligence, v.21 n.1-2, p.199-220, March, 1983