Geography game

The Geography game is a two-player game played on a directed graph where players alternately move a token along directed edges, and the player who cannot move loses. The game is PSPACE-complete when played on general directed graphs, making it one of the canonical examples of a simple game with profound computational complexity. It was introduced by Richard Ladner in the 1970s as a tool for proving complexity results and has since become a textbook example of how graph traversal games encode alternating quantification.

The Geography game is the concrete operationalization of the abstract alternation structure that makes QBF and other PSPACE-complete problems hard. Each move is an existential choice; each response by the opponent is a universal challenge. The game ends when the existential player runs out of valid moves — when the graph has been traversed to a dead end. This simple structure is the template for many PSPACE-complete games, including Node Kayles, and it demonstrates that computational hardness does not require complex rules, only the right kind of interaction.