ML Anthology

Generalized Amazons Is PSPACE-Complete

Timothy Furtak, Masashi Kiyomi, Takeaki Uno, Michael Buro
IJCAI 2005 pp. 132-137
/ijcai/2005/furtak2005ijcai-generalized/

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. 1

PDF Semantic Scholar

Cite

Text

Furtak et al. "Generalized Amazons Is PSPACE-Complete." International Joint Conference on Artificial Intelligence, 2005.

Markdown

[Furtak et al. "Generalized Amazons Is PSPACE-Complete." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/furtak2005ijcai-generalized/)

BibTeX

@inproceedings{furtak2005ijcai-generalized,
  title     = {{Generalized Amazons Is PSPACE-Complete}},
  author    = {Furtak, Timothy and Kiyomi, Masashi and Uno, Takeaki and Buro, Michael},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2005},
  pages     = {132-137},
  url       = {https://mlanthology.org/ijcai/2005/furtak2005ijcai-generalized/}
}