Phutball is PSPACE-hard

Abstract

We consider the $n\times n$ game of Phutball. It is shown that, given an arbitrary position of stones on the board, it is a PSPACE-hard problem to determine whether the specified player can win the game, regardless of the opponent's choices made during the game.

13 pages, 7 figures

References in corpus (3)

• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
• Phutball Endgames are Hard
• The Complexity of Clickomania