Advertisement
Published in:
2015 | OriginalPaper | Chapter
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games
Authors : Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his color on his turn.
We first show that some black-white versions of combinatorial games can only assume combinatorial game values that are numbers, which indicates that the game has many nice properties making it easier to solve. Indeed, numeric games have only previously been shown to be hard for \(\mathsf{NP}\). We exhibit a language of natural numeric games (specifically, black-white poset games) that is \(\mathsf{PSPACE}\)-complete, closing the gap in complexity for the first time between these numeric games and the large collection of combinatorial games that are known to be \(\mathsf{PSPACE}\)-complete.
In this vein, we also show that the game of Col played on general graphs is also \(\mathsf{PSPACE}\)-complete despite the fact that it can only assume two very simple game values. This is interesting because its natural black-white variant is numeric but only complete for \(\mathsf{P}^{\mathsf{NP}[\log ]}\). Finally, we show that the problem of determining the winner of black-white Graph Nim is in \(\mathsf{P}\) using a flow-based technique.