Stonehenge: Outcome of All First Moves and PSPACE-Completeness

Article type: Research Article

Authors: Takenaga, Yasuhiko¹ | Mori, Hikari^{1; 2} | Iwata, Shigeki¹

Affiliations: Tokyo, Japan

Note: [1] Department of Computer Science, The University of Electro-Communications. Email: takenaga@cs.uec.ac.jp; hikari@np.cs.uec.ac.jp; iwata@cs.uec.ac.jp

Note: [2] Presently, Konami Digital Entertainment Co., Ltd.

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.

DOI: 10.3233/ICG-2010-33104

Journal: ICGA Journal, vol. 33, no. 1, pp. 34-41, 2010