Anzeige
Erschienen in:
2001 | OriginalPaper | Buchkapitel
Simple Amazons Endgames and Their Connection to Hamilton Circuits in Cubic Subgrid Graphs
verfasst von : Michael Buro
Erschienen in: Computers and Games
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.