[+] 0 and 2player games. 0player games: Conway's Game of Life is undecidable, Deterministic Constraint Logic (DCL) is PSPACEcomplete. Bounded 2player games are PSPACEcomplete: impartial/partizan game/avoid/seek SAT, Kayles, Geography, Reversi/Othello, bounded 2player Constraint Logic (Bounded 2CL).  
We've proved hardness of a lot of puzzles, which can be viewed as 1player games — the player represents the nondeterminism in move choices. This lecture is about games involving fewer or more players. Zeroplayer games are essentially simulations, like a regular computer. The prototypical example here is Conway's Game of Life, which is PSPACEcomplete or undecidable depending on whether you bound the board. A more modern example is Deterministic Constraint Logic, a version of constraint logic where edgereversal order is deterministically defined (but many edges reverse in parallel), which is still PSPACEcomplete. In multiplayer games, we want to know whether a player (say, the first) has a winning strategy. In the worst case, all other players collude as a single entity, so the game reduces to two players. Thus we obtain 2player games. We'll see many typical starting points for proving hardness of 2player games, from QSAT itself to impartial/partizan game/seek/avoid SAT (from another amazing Schaefer paper). PSPACEhard 2player graph games include Kayles (essentially 2player independent set), Geography (essentially 2player longest path), Reversi/Othello, and bounded 2player Constraint Logic (Bounded 2CL). 
Handwritten notes, page 1/6 •
[previous page] •
[next page] •
[PDF]
Handwritten notes, page 1/6 • [previous page] • [next page] • [PDF] 

Slides, page 1/39 •
[previous page] •
[next page] •
[PDF]
Slide from Lecture 1. http://erikdemaine.org/papers/GPC/ Slides, page 1/39 • [previous page] • [next page] • [PDF] 