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 Formula Game, which is first reduced to an intermediate problem
we call Formula Game Geography, after which the latter is reduced to our decision problem.
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 Formula Game, which is first reduced to an intermediate problem
we call Formula Game Geography, after which the latter is reduced to our decision problem.
| Original language | English |
|---|---|
| Title of host publication | 13th International Conference on Fun with Algorithms (FUN 2026) |
| Publisher | Dagstuhl Publishing |
| Pages | 13:1–13:20 |
| Publication status | E-pub ahead of print - 2026 |
Publication series
| Name | Leibniz International Proceedings in Informatics |
|---|---|
| ISSN (Print) | 1868-8969 |
Bibliographical note
Forthcoming, 2026Keywords
- Computational complexity
- Combinatorial games
- Hive
- PSPACE-hardness
- Formula Game
- Generalized Geography
Fingerprint
Dive into the research topics of 'Hive is PSPACE-Hard'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver