Stonehenge: Outcome of All First Moves and PSPACE-Completeness

Abstract

Stonehenge is a two-player game in which players alternately place a piece on an intersection of the lines drawn on the game board. The player who dominates more than half of the lines wins the game. In this note, we first present the result of exhaustive computations of Stonehenge: for all first moves, the winner of the game is computed, and the results show that the first player has a winning strategy. Second, we consider Generalized Stonehenge played on a hypergraph and prove its PSPACE-completeness.