Abstract
Amazons is a young board game with simple rules and a high branching factor, which makes it a suitable test-bed for planning research. This paper considers the computational complexity of Amazons puzzles and restricted Amazons endgames. We first prove the NP-completeness of the Hamilton circuit problem for cubic subgraphs of the integer grid. This result is then used to showthat solving Amazons puzzles is an NP-complete task and determining the winner of simple Amazons endgames is NP-equivalent.
Acknowledgement
Many thanks to John Tromp who found an error in an earlier version of this paper.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Buro. How machines have learned to play Othello. IEEE Intelligent Systems J.,14(6):12–14, 1999.
J. Culberson. Sokoban is PSPACE-complete. In Proceedings in Informatics 4, pages 65–76. arleton Scientific,Waterloo, Canada, 1999.
D. DeCoste. The significance of Kasparov versus Deep Blue and the future of computer chess. ICCA J., 21(1):33–43, 1998.
G.W. Flake and E.B. Baum. RushHour is PSPACE-complete, or why you should generously tip parking lot attendants. to appear in TCS, 2000.
M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman and Company NewYork, 1979.
A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter. Hamilton paths in grid graphs. SIAM J. Comput., 11(4):676–686, 1982.
G. Kant. Drawing planar graphs using the canonical ordering. Algorithmica, 16(1):4–32, 1996.
R. Korf. Finding optimal solutions to Rubik’s cube using pattern databases. Fourteenth National Conference on Artificial Intelligence Ninth Innovative Applications of Artificial Intelligence Conference, pages 700–705, 1997.
M. Müller. Computer Go: A research agenda. ICCA Journal, 22(2):104–112, 1999.
J. Plesnik. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Information Processing Letters, 8(4):199–201, 1979.
J. Schaeffer. One Jump Ahead: Challenging Human Supremacy in Checkers. SpringerVerlag, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buro, M. (2001). Simple Amazons Endgames and Their Connection to Hamilton Circuits in Cubic Subgrid Graphs. In: Marsland, T., Frank, I. (eds) Computers and Games. CG 2000. Lecture Notes in Computer Science, vol 2063. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45579-5_17
Download citation
DOI: https://doi.org/10.1007/3-540-45579-5_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43080-3
Online ISBN: 978-3-540-45579-0
eBook Packages: Springer Book Archive