Locality of Plays

When I'm looking at a game for the first time, before I think about strategies and analysis there are two properties I first consider. First, is the game partisan or impartial? Second, can moves be made anywhere, or not? The answers to these help package the game into one of four buckets.

Though I may not have that many game complexity results under my belt, I can't even fathom how else to begin hoping to prove a relationship between games. Those shown links between relationships are always amazing to me.

Consider the computational complexity of determining who will win a game and then narrow your gaze further towards those games which are PSPACE-complete (no one has complained yet that I talk too much about this...). The basic PSPACE problem of satisfying quantified boolean formulae (QBF) is the setting for a game: players alternate choosing boolean values for the variables, starting with 1 and going up to n. In the end, if the formula is satisfied, then "there exists" player wins, otherwise the "for all" player wins. To say this differently (and more correctly), if the last (nth) quantifier is "there exists" then the last player wins exactly if the formula is satisfied. If it is instead "for all", then the last player wins exactly if it is not satisfied.

This game falls into the impartial-and-restricted box: the identity of the current player doesn't matter, but moves are restricted in that you can't choose the value of any variable: only the next one in the list.

Thomas Schaefer made a big jump in his collection of game complexity results (On the Complexity of Some Two-Person Perfect-Information Games) by showing that Kayles is PSPACE-complete. Yes, it is true that both games are impartial, but he uses the QBF game to show that Kayles is hard, despite the fact that general Kayles does not enforce any restrictions on where a player can move.

In his proof, Schaefer creates a reduction to Kayles that simulates the forcing, making players take specific nodes or immediately lose. This is one of those beautiful jumps that opens things up for everyone else. Personally, I would always look at Kayles first if I hoped to prove an unrestricted game to be complete for PSPACE.

Are there other excellent jump examples? Do you think other properties deserve this? I considered planarity, but it doesn't seem difficult to overcome this.