Hive is PSPACE-Hard
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917510460211200 |
|---|---|
| author | Andel, Daniël Rin, Benjamin |
| author_facet | Andel, Daniël Rin, Benjamin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03492 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Hive is PSPACE-Hard Andel, Daniël Rin, Benjamin Computational Complexity 91A46 (Primary) 68Q17 (Secondary) F.1.3; F.2.2 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. |
| title | Hive is PSPACE-Hard |
| topic | Computational Complexity 91A46 (Primary) 68Q17 (Secondary) F.1.3; F.2.2 |
| url | https://arxiv.org/abs/2506.03492 |