arXiv Open Access 2025

Hive is PSPACE-Hard

Daniël Andel Benjamin Rin

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.CC

Penulis (2)

Daniël Andel

Benjamin Rin

Format Sitasi

APA MLA BibTeX

Andel, D., Rin, B. (2025). Hive is PSPACE-Hard. https://arxiv.org/abs/2506.03492

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓