Turning Tiles is PSPACE-complete
Kanae Yoshiwatari, Hironori Kiya, Koki Suetsugu, Tesshu Hanaka, Hirotaka Ono · arXiv (Cornell University) · 2023
In combinatorial game theory, the winning player for a position in normal play is analyzed and characterized via algebraic operations. Such analyses define a value for each position, called a game value. A game (ruleset) is called universal if any game value is achievable in some position in a play of the game. Although the universality of a game implies that the ruleset is rich enough (i.e., sufficiently complex), it does not immediately imply that the game is intractable in the sense of computational complexity. This paper proves that the universal game Turning Tiles is PSPACE-complete.