On the complexity of Hive

dc.rights.license	CC-BY-NC-ND
dc.contributor.advisor	Rin, B.G.
dc.contributor.author	Andel, D.I.
dc.date.accessioned	2020-06-03T18:00:14Z
dc.date.available	2020-06-03T18:00:14Z
dc.date.issued	2020
dc.identifier.uri	https://studenttheses.uu.nl/handle/20.500.12932/35905
dc.description.abstract	It is shown that for an arbitrary position of a Hive game where both players have the same set of N pieces it is PSPACE-hard to determine whether one of the players has a winning strategy. The proof is done by reducing the known PSPACE-complete set of true quantified boolean formulas to a game concerning these formulas, then to the game generalised geography, then to a version of that game with the restriction of having only nodes with maximum degree 3, and finally to generalised Hive. This thesis includes a short introduction to the subject of computational complexity.
dc.description.sponsorship	Utrecht University
dc.format.extent	2611439
dc.format.mimetype	application/pdf
dc.language.iso	en
dc.title	On the complexity of Hive
dc.type.content	Bachelor Thesis
dc.rights.accessrights	Open Access
dc.subject.keywords	Computational complexity; Board game; PSPACE
dc.subject.courseuu	Kunstmatige Intelligentie