Article

Free access

The principal continuation and the killer heuristic

Authors:

Monroe M. NewbornAuthors Info & Claims

ACM '77: Proceedings of the 1977 annual conference

Pages 466 - 473

https://doi.org/10.1145/800179.810240

Published: 01 January 1977 Publication History

Abstract

An algorithm is presented for obtaining the principal continuation in trees searched by two-person game playing programs based on the Alpha-Beta algorithm. Moves saved while determining the principal continuation are shown to be good candidates for killer moves when the killer heuristic supplements the Alpha-Beta search.

References

[1]

J. von Neumann, "Zur Theorie der Gesellshaftsspiele", Math. Annalen, vol. 100, 1928, pp. 295-320.

[2]

C.E. Shannon, "Programming a computer for playing chess", Philosophical Magazine, ser. 7, vol. 41, No. 314, March 1950, pp. 256-275.

[3]

A.M. Turing, "Faster than thought", B.V. Bowden ed., London, Pitman, 1953, Chap. 25, pp. 288-295.

[4]

A. Bertstein and M. Roberts, "Computer v. Chess-Player", Scientific American, June 1958, pp. 96-105.

[5]

A. Newell, J.C. Shaw and H.A. Simon, "Chess playing programs and the problem of complexity", IBM J. Res. and Devel., 2, 1958, pp. 320 - 355.

Digital Library

[6]

A. Samuel, "Some studies in machine learning using the game of checkers", IBM J. Res. and Devel., 3, 1959, pp. 211 - 229.

Digital Library

[7]

A. Brudno, "Bounds and valuations for shortening and scanning of variations", in Russian, Problemy Kibernetiki, 10, 1963, pp. 141-150.

[8]

A. Samuel, "Some studies in machine learning using the game of checkers II - Recent Progress", IBM J. Res. and Devel., 11, 1967, pp. 601-617.

Digital Library

[9]

J.R. Slagle and J.K. Dixon, "Experiments with some programs that search game trees", J. ACM, 16, 1969, pp. 189-207.

Digital Library

[10]

J.J. Gillogly, "The technology chess program", Artificial Intelligence, 3, 1972, pp. 145-163.

Digital Library

[11]

D.E. Knuth, "An Analysis of alpha-beta pruning", Department of Computer Science Report, Stanford University, STAN CS-74-441, 64 pages, August 1974.

[12]

M.M. Newborn, "The Efficiency of the Alpha-Beta search on trees with branch-dependent terminal node scores", Artificial Intelligence, Vol. 8, pp. 137-153, 1977.

Digital Library

[13]

M.M. Newborn, "PEASANT: An endgame program for Kings and Pawns", Chess Skill in Man and Machine, Frey, P., Ed., Springer Verlag, pp. 119-130, 1977.

[14]

N. Nilsson, Problem Solving Methods in Artificial Intelligence, McGraw-Hill, 1971.

Digital Library

[15]

M.M. Newborn, Computer Chess, Academic Press, 1975.

Digital Library

Cited By

Hu YLv R(2021)Chess AI with Different Behavioral Tendencies and Its Application2021 2nd International Conference on Artificial Intelligence and Information Systems10.1145/3469213.3470698(1-5)Online publication date: 28-May-2021
https://dl.acm.org/doi/10.1145/3469213.3470698
Goerigk MHartisch M(2021)Multistage robust discrete optimization via quantified integer programmingComputers & Operations Research10.1016/j.cor.2021.105434135(105434)Online publication date: Nov-2021
https://doi.org/10.1016/j.cor.2021.105434
Hartisch M(2021)Adaptive Relaxations for Multistage Robust OptimizationPRICAI 2021: Trends in Artificial Intelligence10.1007/978-3-030-89188-6_36(485-499)Online publication date: 25-Oct-2021
https://doi.org/10.1007/978-3-030-89188-6_36
Show More Cited By

Index Terms

The principal continuation and the killer heuristic

Recommendations

Killer game programming in java
Application of the killer-tree heuristic and the lambda-search method to lines of action
Special issue: Heuristic search and computer game playing III

This paper investigates the application of the the killer-tree heuristic (KTH) and the λ¹-search method to the endgame of lines of action. Both techniques are developed to be used in the endgame of shogi. They are incorporated into two depth-first ...
Killer Game Programming in Java

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM '77: Proceedings of the 1977 annual conference

January 1977

505 pages

ISBN:9781450339216

DOI:10.1145/800179

Copyright © 1977 ACM.

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]

Sponsors

ACM: Association for Computing Machinery

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1977

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ACM '77

Sponsor:

ACM

October 16 - 19, 1977

Washington, Seattle

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
1,095
Total Downloads

Downloads (Last 12 months)122
Downloads (Last 6 weeks)8

Reflects downloads up to 03 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hu YLv R(2021)Chess AI with Different Behavioral Tendencies and Its Application2021 2nd International Conference on Artificial Intelligence and Information Systems10.1145/3469213.3470698(1-5)Online publication date: 28-May-2021
https://dl.acm.org/doi/10.1145/3469213.3470698
Goerigk MHartisch M(2021)Multistage robust discrete optimization via quantified integer programmingComputers & Operations Research10.1016/j.cor.2021.105434135(105434)Online publication date: Nov-2021
https://doi.org/10.1016/j.cor.2021.105434
Hartisch M(2021)Adaptive Relaxations for Multistage Robust OptimizationPRICAI 2021: Trends in Artificial Intelligence10.1007/978-3-030-89188-6_36(485-499)Online publication date: 25-Oct-2021
https://doi.org/10.1007/978-3-030-89188-6_36
Baier HKaisers M(2020)Guiding Multiplayer MCTS by Focusing on Yourself2020 IEEE Conference on Games (CoG)10.1109/CoG47356.2020.9231603(550-557)Online publication date: Aug-2020
https://doi.org/10.1109/CoG47356.2020.9231603
Hartisch MLorenz U(2020)A Novel Application for Game Tree Search - Exploiting Pruning Mechanisms for Quantified Integer ProgramsAdvances in Computer Games10.1007/978-3-030-65883-0_6(66-78)Online publication date: 20-Dec-2020
https://doi.org/10.1007/978-3-030-65883-0_6
Liu XWu JWei S(2019)Design and implementation of military chess game algorithm based on probability model and situation evaluation2019 Chinese Control And Decision Conference (CCDC)10.1109/CCDC.2019.8832525(6310-6314)Online publication date: Jun-2019
https://doi.org/10.1109/CCDC.2019.8832525
Akl S(2019)From Parallelism to Nonuniversality: An Unconventional TrajectoryProceedings of International Conference on Computational Intelligence and Data Engineering10.1007/978-3-030-15792-0_6(123-156)Online publication date: 17-Apr-2019
https://doi.org/10.1007/978-3-030-15792-0_6
Polk SOommen B(2018)Challenging state-of-the-art move ordering with Adaptive Data StructuresApplied Intelligence10.1007/s10489-017-1006-048:5(1128-1147)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10489-017-1006-0
Bueno LMuller BDirene A(2018)StratVision - A Framework for Strategic Vision FormalizationTrends and Advances in Information Systems and Technologies10.1007/978-3-319-77712-2_79(842-850)Online publication date: 17-May-2018
https://doi.org/10.1007/978-3-319-77712-2_79
Polk SOommen B(2016)Challenging Established Move Ordering Strategies with Adaptive Data StructuresTrends in Applied Knowledge-Based Systems and Data Science10.1007/978-3-319-42007-3_73(862-872)Online publication date: 14-Jul-2016
https://doi.org/10.1007/978-3-319-42007-3_73
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents