DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.27

Arimaa Is PSPACE-Hard

Authors: Benjamin G. Rin and Atze Schipper

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

Arimaa is a strategy board game developed in 2003 by Omar Syed, designed to be hard for AI to win because of its large branching factor. In this paper, its theoretical complexity is considered. We prove that Arimaa (suitably generalized to an n × n board) is PSPACE-hard. This result is found by reducing a known PSPACE-hard variant of Generalized Geography to a variant of Arimaa that we call Arimaa^′, which in turn is then reduced to (n × n) Arimaa. Since the game is easily seen to be solvable in exponential time, it follows that its complexity lies somewhere between being PSPACE-complete and EXPTIME-complete.

Cite as

Benjamin G. Rin and Atze Schipper. Arimaa Is PSPACE-Hard. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{rin_et_al:LIPIcs.FUN.2024.27,
  author =	{Rin, Benjamin G. and Schipper, Atze},
  title =	{{Arimaa Is PSPACE-Hard}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{27:1--27:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.27},
  URN =		{urn:nbn:de:0030-drops-199359},
  doi =		{10.4230/LIPIcs.FUN.2024.27},
  annote =	{Keywords: Arimaa, complexity theory, PSPACE-hardness, board games, Generalized Geography}
}

Search Results

Documents authored by Schipper, Atze

Arimaa Is PSPACE-Hard

Abstract

Cite as