PSPACE-Complete Two-Color Placement Games

Abstract

We show that three placement games, Col, NoGo, and Fjords, are PSPACE-complete on planar graphs. The hardness of Col and Fjords is shown via a reduction from Bounded 2-Player Constraint Logic and NoGo is shown to be hard directly from Col.

16 Pages, 16 figures

References in corpus (1)

• Playing Games with Algorithms: Algorithmic Combinatorial Game Theory