2026-07-23T05:17:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25722 2026-06-23T12:45:13Z ddc:004 open_access

Hive Is PSPACE-Hard Andel, Daniël I. Rin, Benjamin G. Computational complexity Combinatorial games Hive PSPACE-hardness Formula Game Generalized Geography 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniël I. Andel and Benjamin G. Rin 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.3 urn:nbn:de:0030-drops-257221 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode