Arimaa Is PSPACE-Hard
Publication date
2024-06
Authors
Rin, Benjamin G.
Schipper, Atze
Editors
Broder, Andrei Z.
Tamir, Tami
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
No license information available
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.
Keywords
Arimaa, board games, complexity theory, Generalized Geography, PSPACE-hardness, Software
Citation
Rin, B G & Schipper, A 2024, Arimaa Is PSPACE-Hard. in A Z Broder & T Tamir (eds), 12th International Conference on Fun with Algorithms, FUN 2024., 27, Leibniz International Proceedings in Informatics, LIPIcs, vol. 291, Dagstuhl Publishing, 12th International Conference on Fun with Algorithms, FUN 2024, Sardinia, Italy, 4/06/24. https://doi.org/10.4230/LIPIcs.FUN.2024.27, conference