Hive is PSPACE-Hard

Abstract

Hive is an abstract strategy game played on a table with hexagonal pieces. First published in 2001, it was and continues to be highly popular among both casual and competitive players. In this paper, we show that for a suitably generalized version of the game, the computational problem of determining whether a given player in an arbitrary position has a winning strategy is PSPACE-hard. We do this by reduction from a variant of Generalized Geography we call Formula Game Geography.

20 pages, 17 figures. This replacement of the previous arXiv version is a substantial update. The proof is simplified. The diagrams and language are improved. The paper is markedly shorter without sacrificing content. This version of the article matches with the version now published in: LIPIcs Vol. 366, pp. 3:1-3:2 (2026) (DOI: 10.4230/LIPIcs.FUN.2026.3)