Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games
verfasst von : Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
Erschienen in: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.