14.6. Other PSPACE-complete problems


Generalized Checkers

Some problems related to games are PSPACE-complete because the alternation of moves is similar to the alternating quantifiers in TQBF.

One such problem is Generalized Checkers. If you don't know how to play checkers, this will not make sense to you.

Checkers is normally played on an 8×8 board, but we need to generalize that to an n×n board. Some red and black kings have been placed on the board. It is red's move. The question is, does red have a winning strategy from that board configuration?


Generalized Go

Another PSPACE-complete game is Generalized Go. Go is a game played by placing small white and black stones on the intersections of a grid. Each player can capture the other player's stones by surrounding them.

When generalized to an n×n board, the problem of determining if the white player has a winning strategy from a particular initial configuration is PSPACE-complete.