Generalized Amazons is PSPACE-Complete
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 132-136.
Abstract
Amazons is a perfect information board game with simple rules and large branching factors. Two players alternately move chess queen-like pieces and block squares on a 10×10 playing field. The player who makes the last move wins. Amazons endgames usually decompose into independent subgames. Therefore, the game is a natural testbed for combinatorial game theory. It was known that determining the winner of simple generalized Amazons endgames is NP-equivalent. This paper presents two proofs for the PSPACEcompleteness of the generalized version of the full game.
@inproceedings{ijcai2005p158,
title = {Generalized Amazons is PSPACE-Complete},
author = {Furtak, Timothy and Kiyomi, Masashi and Uno, Takeaki and Buro, Michael},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {132--136},
year = {2005},
url = {https://ijcai.org/proceedings/2005/158},
}
TY - CPAPER TI - Generalized Amazons is PSPACE-Complete AU - Furtak, Timothy AU - Kiyomi, Masashi AU - Uno, Takeaki AU - Buro, Michael T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 132 EP - 136 UR - https://ijcai.org/proceedings/2005/158 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
