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

摘要

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 natural 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~(NP[log]). Finally, we show that the problem of determining the winner of black-white GRAPH NIM is in P using a flow-based technique.