Atropos: a PSPACE-complete Sperner triangle game. (English) Zbl 1194.91025

Summary: We create Atropos, a new two-player game based on Sperner’s lemma. Our game has simple rules and several desirable properties. First, Atropos is always certain to have a winner. Second, the game is impartial, meaning that both players always can make the same moves. Third, like many other interesting games such as Hex and geography, we prove that deciding whether one can win a game of Atropos is a PSPACE-complete problem. We provide a web-based version of the game, playable at http://cs-people.bu.edu/paithan/atropos/. In addition, we propose other games, also based on fixed-point theorems.


91A05 2-person games
91A44 Games involving topology, set theory, or logic
91A46 Combinatorial games
Full Text: DOI