article

Free access

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

Author:

Judea PearlAuthors Info & Claims

Communications of the ACM, Volume 25, Issue 8

Pages 559 - 564

https://doi.org/10.1145/358589.358616

Published: 01 August 1982 Publication History

PDF eReader

References

[1]

Baudet, G.M. On the branching factor of the alpha-beta pruning algorithm. Artificial Intelligence 10, 2 (April 1978), 173-199.

Digital Library

Google Scholar

[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).

Google Scholar

[3]

Knuth, D.E., and Moore, R.N. An analysis of alpha-beta pruning. Artificial Intelligence 6 (1975), 293-326.

Crossref

Google Scholar

[4]

Kuczma, M. Functional Equations in a Single Variable. Polish Scientific Publishers, Warszawa, (1968), p. 141.

Google Scholar

[5]

Pearl, J. Asymptotic properties of minimax trees and gamesearching procedures. Artificial Intelligence 14, 2 (Sept. 1980), 113-138,

Crossref

Google Scholar

[6]

Pearl, J. A space-efficient on-line method of computing quantile estimates J. of Algorithms 2, 2 (June 1981) 24-28.

Google Scholar

[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).

Google Scholar

[8]

Slagle, J.R., and Dixon, J.K. Experiments with some programs that search game trees. JACM 16, 2 (April 1969) 189-207.

Digital Library

Google Scholar

[9]

Stockman, G. A minimax algorithm better than alpha-beta? Artificial Intelligence 12, 2 (Aug. 1979), 179-196.

Crossref

Google Scholar

[10]

Tarsi, M. Optimal searching of some game trees. UCLA-ENG- CSL-8108, Cognitive Systems Laboratory, University of California, Los Angeles, (1981). (To appear in JA CM.)

Digital Library

Google Scholar

Cited By

View all

Li W(2024)Optimizing with Attractor: A TutorialACM Computing Surveys10.1145/364835456:9(1-41)Online publication date: 15-Feb-2024
https://dl.acm.org/doi/10.1145/3648354
Cleaver NNeshatian K(2023)Transfer Learning in Monte Carlo Tree Search2023 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)10.1109/CSDE59766.2023.10487142(1-7)Online publication date: 4-Dec-2023
https://doi.org/10.1109/CSDE59766.2023.10487142
Liu PZhou JLv J(2023)Exploring the first-move balance point of Go-Moku based on reinforcement learning and Monte Carlo tree searchKnowledge-Based Systems10.1016/j.knosys.2022.110207261:COnline publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1016/j.knosys.2022.110207
Show More Cited By

Index Terms

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

Recommendations

Improved Speedup Bounds for Parallel Alpha-Beta Search

In this paper we investigate the ``mandatory-work-first'' approach to parallel alpha-beta search first proposed by Akl, Barnard, and Doran. This approach is based on a version of alpha-beta search without deep cutoffs and a two-stage evaluation process, ...
Distributed tree search and its application to alpha-beta pruning
AAAI'88: Proceedings of the Seventh AAAI National Conference on Artificial Intelligence

We propose a parallel tree search algorithm based on the idea of tree-decomposition in which different processors search different parts of the tree. This generic algorithm effectively searches irregular trees using an arbitrary number of processors ...
Improved Alpha-Beta Pruning of Heuristic Search in Game-Playing Tree
CSIE '09: Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering - Volume 02

The game playing is an import domain of heuristic search, and its procedure is represented by a special and/or tree. Alpha-beta pruning is always used for problem solving by searching the game-playing-tree. In this paper, the plan which child nodes are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 25, Issue 8

Aug 1982

84 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/358589

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1982

Published in CACM Volume 25, Issue 8

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
2,279
Total Downloads

Downloads (Last 12 months)263
Downloads (Last 6 weeks)56

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li W(2024)Optimizing with Attractor: A TutorialACM Computing Surveys10.1145/364835456:9(1-41)Online publication date: 15-Feb-2024
https://dl.acm.org/doi/10.1145/3648354
Cleaver NNeshatian K(2023)Transfer Learning in Monte Carlo Tree Search2023 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE)10.1109/CSDE59766.2023.10487142(1-7)Online publication date: 4-Dec-2023
https://doi.org/10.1109/CSDE59766.2023.10487142
Liu PZhou JLv J(2023)Exploring the first-move balance point of Go-Moku based on reinforcement learning and Monte Carlo tree searchKnowledge-Based Systems10.1016/j.knosys.2022.110207261:COnline publication date: 15-Feb-2023
https://dl.acm.org/doi/10.1016/j.knosys.2022.110207
Li WLi W(2023)Analysis of the Attractor-Based Search SystemThe Traveling Salesman Problem10.1007/978-3-031-35719-0_4(37-82)Online publication date: 9-Jul-2023
https://doi.org/10.1007/978-3-031-35719-0_4
(2022)Introduction by Judea PearlProbabilistic and Causal Inference10.1145/3501714.3501722(57-60)Online publication date: 28-Feb-2022
https://dl.acm.org/doi/10.1145/3501714.3501722
Li WOgden CGamess E(2022)A new approach to the traveling salesman problemProceedings of the 2022 ACM Southeast Conference10.1145/3476883.3524046(52-59)Online publication date: 18-Apr-2022
https://dl.acm.org/doi/10.1145/3476883.3524046
Torres LBarriga N(2022)Adversarial Search Algorithms Performance in the Yote Game2022 IEEE International Conference on Automation/XXV Congress of the Chilean Association of Automatic Control (ICA-ACCA)10.1109/ICA-ACCA56767.2022.10006178(1-5)Online publication date: 24-Oct-2022
https://doi.org/10.1109/ICA-ACCA56767.2022.10006178
Navaneeth ADileep M(2022)Upshot and Disparity of AI Allied Approaches Over Customary Techniques of Assessment on Chess—An ObservationEmerging Research in Computing, Information, Communication and Applications10.1007/978-981-19-5482-5_12(127-135)Online publication date: 13-Dec-2022
https://doi.org/10.1007/978-981-19-5482-5_12
Li W(2021)How to Solve the Traveling Salesman ProblemTheory of Complexity - Definitions, Models, and Applications [Working Title]10.5772/intechopen.96129Online publication date: 9-Feb-2021
https://doi.org/10.5772/intechopen.96129
Liu CYan JMa YZhao TZhang QWei X(2020)An Adversarial Search Method Based on an Iterative Optimal StrategyMathematics10.3390/math80916238:9(1623)Online publication date: 19-Sep-2020
https://doi.org/10.3390/math8091623
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Improved Speedup Bounds for Parallel Alpha-Beta Search

Distributed tree search and its application to alpha-beta pruning

Improved Alpha-Beta Pruning of Heuristic Search in Game-Playing Tree

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations