P38 · Generalized Geography

🔊 Listen

1 · Generalised Geography · the canonical PSPACE-complete game

Generalised Geography (GG) abstracts the children's word game "Geography" (each next word starts with the previous word's last letter) into a graph game:

Rules

Given a directed graph G and starting vertex s. A token is placed at s. Players alternate turns. On your turn, you move the token to an unvisited successor of its current position. If you can't move (the token's successors are all already visited), you lose.

The decision problem

GG = {⟨G, s⟩ : Player 1 has a winning strategy on G starting at s}.

PSPACE-complete (Sipser Theorem 8.11)

In PSPACE: recursive minimax evaluation uses O(n) stack depth and stores only the current path's visited set. PSPACE-hard: TQBF reduces to GG via gadget construction (Problem 39).

The "no vertex repeats" rule is what makes the game terminate. Without it, players could move in cycles forever, and the question "does player 1 win?" would have no well-defined answer.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

"Player 1 wins" means optimal play. The question is whether a winning strategy exists, not whether player 1 actually wins under random play.
The "no repeat" rule is essential. Without termination, the game state space is infinite. With termination, the game tree has ≤ |V|! distinct branches but only |V| depth.
Generalised geography ≠ the word game. The word version restricts moves by letters; the generalised version uses arbitrary graphs. This generalisation makes it PSPACE-complete.

🔊 Listen

4 · Q&A defence notes

Q1. Why does the no-vertex-repeat rule matter?
Without that rule, players could move in cycles forever and the game would never terminate. With it, the game ends in at most |V| moves (each vertex visited at most once), so winning strategies are well-defined and computable.
Q2. How does the PSPACE-completeness proof work?
Reduce TQBF₃ to GG. Build a graph with gadgets: a "diamond" for each variable that lets the responsible player choose true/false; a "clause chain" that ∀-player traverses to falsify; the connection makes the game tree mirror the QBF evaluation tree. Sipser Theorem 8.11.
Q3. Time vs space for the minimax algorithm?
Exponential time (the game tree has 2^O(n) nodes in the worst case), but polynomial space (depth-first with reuse stores only the current path, O(n) cells). This is why GG is in PSPACE but not known to be in P.
Q4. Are real-world games PSPACE-complete?
Generalised chess on n×n boards is PSPACE-complete (assuming polynomial moves). Generalised Go is at least PSPACE-hard. Most natural board games end up at least PSPACE-hard under generalisation.

🔊 Listen

5 · Where to read more

Sipser: §8.3, Theorem 8.11. Lecture notes: Module 6 slide 3. Companion problems: P36 (TQBF), P39 (TQBF → geography), P40 (chess hardness).