Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-021 | 5th February 2015 16:06

Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games


Authors: Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf
Publication: 5th February 2015 16:30
Downloads: 684


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 NP. We exhibit a language of numeric games (specifically, black-white poset games) that is 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 PSPACE-complete.

In this vein, we also show that the game of Col played on general graphs is also 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 P$^{{\rm NP}[\log]}$. Finally, we show that the problem of determining the winner of black-white GraphNim is in P using a flow-based technique.

ISSN 1433-8092 | Imprint