29 September 2022, The Utrecht Logic in Progress Series (TULIPS), Benjamin Rin

Abstract: Arimaa is a two-player strategy game played on an 8 x 8 board. Like chess, checkers, and Go, it is a perfect-information, deterministic, turn-based game in which there is at most one winner. Arimaa has been a focus of much attention in applied AI research, as it was originally designed purposely to be difficult for computers to play.

This talk considers the more theoretical question, "Given a position in Arimaa and specified player, does that player have a winning strategy?" As with chess and checkers, this question is trivially solvable in constant time if the game is played on a standard 8 x 8 board (albeit for an impractically large constant). Accordingly, we focus instead on the question for the generalized case of an n x n board. For the aforementioned strategy games, the corresponding question is known to be PSPACE-hard. That is, solving (n x n) chess, checkers, etc. is at least as complex as any computational task in PSPACE--the class of problems solvable by Turing machines using an amount of space (memory) that grows as a polynomial function of the input size n. We prove in this talk that the same is true for Arimaa. Thus Arimaa is about as computationally complex as these other (classic) games. We prove this result by reduction from the known PSPACE-hard problem Generalized Geography, adapting a technique of Storer’s in his 1983 paper originally showing the PSPACE-hardness of (n x n) chess.

(Joint work with A. Schipper.)