article

Free access

Optimal Search on Some Game Trees

Author:

Michael TarsiAuthors Info & Claims

Journal of the ACM (JACM), Volume 30, Issue 3

Pages 389 - 396

https://doi.org/10.1145/2402.322383

Published: 01 July 1983 Publication History

PDF eReader

References

[1]

BAUDET, G.M.On the branching factor of the alpha-beta pruning algorithm. Artif. ImeU. 10 (1978), 173-199.

Google Scholar

[2]

FELLER, W. An Introduction to Probabdity Theory and Its Applications. Wiley, New York, 1968.

Google Scholar

[3]

FULLER, S.H., GxscrImG, J.G., AND GILLOGLY, J.J. AN analysis of the alpha-beta pruning algorithm. Department of Computer Science Pep., Came#e-Mellon Univ., Pittsburgh, Pa., 1973.

Google Scholar

[4]

KNUTH, D.E., A~rD MooR~, R.N.An analysis of alpha-beta pruning. Artif. IntelL 6 (1975), 293-326.

Google Scholar

[5]

PEARL, J.asymptotic properties of minimax trees and game-searching procedures. Artif lnteli 14, 2 (1980), 113-138.

Google Scholar

[6]

PEARL, J.The solution for the brartchmg factor of the alpha-beta prumng algorithm and its optimahty. Commun ACM 25, 8 (Aug. 1982), 559-564

Crossref

Google Scholar

[7]

SLAGLE, J.R, AND DIXON, J.K. Experiments with some programs that search game trees. Z A CM 2, 1969, 189-207.

Crossref

Google Scholar

[8]

STOCKMAN, G.A mmtmax algorithm better than alpha-beta? Art~ Intell. 12 (1979), 179-196

Google Scholar

Cited By

View all

Koutas DBismut EStraub D(2024)An investigation of belief-free DRL and MCTS for inspection and maintenance planningJournal of Infrastructure Preservation and Resilience10.1186/s43065-024-00098-95:1Online publication date: 29-Apr-2024
https://doi.org/10.1186/s43065-024-00098-9
Tanaka KPeng NPeng WLi W(2024)The equilibria of independent distributions on unbalanced game treesComputational and Applied Mathematics10.1007/s40314-024-02784-643:5Online publication date: 3-Jun-2024
https://doi.org/10.1007/s40314-024-02784-6
Ito F(2022)Uniqueness of optimal randomized algorithms for balanced AND-OR treesJSIAM Letters10.14495/jsiaml.14.2114(21-24)Online publication date: 2022
https://doi.org/10.14495/jsiaml.14.21
Show More Cited By

Index Terms

Optimal Search on Some Game Trees
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
      2. Game tree search
2. Mathematics of computing
  1. Discrete mathematics

Recommendations

Constructing Optimal Search Trees in Optimal Time

$(a,b)$-trees are an important class of search trees. They include 2-3 trees, 2-3-4 trees, and $B$-trees as subclasses. We show that a space-minimum $(a,b)$-tree is also height-minimum and present an optimal algorithm for constructing $(a,b)$-trees that ...
Self-adjustingk-ary search trees and self-adjusting balanced search trees
On optimal algorithms for solving bi-valued game trees
CSC '87: Proceedings of the 15th annual conference on Computer Science

Let each leaf in a bi-valued game tree have the same probability P_O of being labeled a WIN. Define a search algorithm D for a bi-valued game tree T to be directed if D consists of searching T by adhering to a predetermined ordering of the leaves of T, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 30, Issue 3

July 1983

297 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/2402

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1983

Published in JACM Volume 30, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
903
Total Downloads

Downloads (Last 12 months)84
Downloads (Last 6 weeks)28

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Koutas DBismut EStraub D(2024)An investigation of belief-free DRL and MCTS for inspection and maintenance planningJournal of Infrastructure Preservation and Resilience10.1186/s43065-024-00098-95:1Online publication date: 29-Apr-2024
https://doi.org/10.1186/s43065-024-00098-9
Tanaka KPeng NPeng WLi W(2024)The equilibria of independent distributions on unbalanced game treesComputational and Applied Mathematics10.1007/s40314-024-02784-643:5Online publication date: 3-Jun-2024
https://doi.org/10.1007/s40314-024-02784-6
Ito F(2022)Uniqueness of optimal randomized algorithms for balanced AND-OR treesJSIAM Letters10.14495/jsiaml.14.2114(21-24)Online publication date: 2022
https://doi.org/10.14495/jsiaml.14.21
Peng WPeng NTanaka K(2022)The Eigen-Distribution for Multi-Branching Weighted Trees on Independent DistributionsMethodology and Computing in Applied Probability10.1007/s11009-021-09849-724:1(277-287)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s11009-021-09849-7
Shigemizu MSuzuki TUsami K(2020)Independent distributions on a multi-branching AND–OR tree of height 2Discrete Applied Mathematics10.1016/j.dam.2020.05.007285(274-282)Online publication date: Oct-2020
https://doi.org/10.1016/j.dam.2020.05.007
Delattre SFournier N(2019)On Monte-Carlo tree search for deterministic games with alternate moves and complete informationESAIM: Probability and Statistics10.1051/ps/201800623(176-216)Online publication date: 1-May-2019
https://doi.org/10.1051/ps/2018006
Suzuki T(2019)Communication Interruption Between a Game Tree and Its LeavesTransactions on Engineering Technologies10.1007/978-981-32-9808-8_15(182-193)Online publication date: 11-Oct-2019
https://doi.org/10.1007/978-981-32-9808-8_15
Suzuki T(2018)Non-depth-first search against independent distributions on an AND–OR treeInformation Processing Letters10.1016/j.ipl.2018.06.013139(13-17)Online publication date: Nov-2018
https://doi.org/10.1016/j.ipl.2018.06.013
SUZUKI T(2017)Kazuyuki Tanaka's Work on AND-OR Trees and Subsequent DevelopmentsAnnals of the Japan Association for Philosophy of Science10.4288/jafpos.25.0_7925(79-88)Online publication date: 2017
https://doi.org/10.4288/jafpos.25.0_79
Peng WPeng NNg KTanaka KYang Y(2017)Optimal depth-first algorithms and equilibria of independent distributions on multi-branching treesInformation Processing Letters10.1016/j.ipl.2017.05.002125(41-45)Online publication date: Sep-2017
https://doi.org/10.1016/j.ipl.2017.05.002
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

Constructing Optimal Search Trees in Optimal Time

Self-adjustingk-ary search trees and self-adjusting balanced search trees

On optimal algorithms for solving bi-valued game trees

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

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