DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2026.3

Hive Is PSPACE-Hard

Authors: Daniël I. Andel and Benjamin G. Rin

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

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.

Cite as

Daniël I. Andel and Benjamin G. Rin. Hive Is PSPACE-Hard. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andel_et_al:LIPIcs.FUN.2026.3,
  author =	{Andel, Dani\"{e}l I. and Rin, Benjamin G.},
  title =	{{Hive Is PSPACE-Hard}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.3},
  URN =		{urn:nbn:de:0030-drops-257221},
  doi =		{10.4230/LIPIcs.FUN.2026.3},
  annote =	{Keywords: Computational complexity, Combinatorial games, Hive, PSPACE-hardness, Formula Game, Generalized Geography}
}

Search Results

Documents authored by Andel, Daniël I.

Hive Is PSPACE-Hard

Abstract

Cite as

Thanks for your feedback!

Could not send message