Generalized Hex is PSPACE-complete

Hex: two players (Red, Blue) place stones on a hex grid; Red tries to connect top to bottom, Blue connects left to right. Standard Hex is determined (first player wins) but finding the winning move is non-trivial.

• Hex is determined but the winning move is hard to find. Strategy-stealing proves Red wins; finding the move is PSPACE-complete.
• The game tree is exponential in size but polynomial in depth. n² total moves → polynomial-depth tree. PSPACE rather than EXPTIME.
• Generalised vs 11×11 Hex. 11×11 Hex (the standard size) is technically finite-decidable in O(1). PSPACE-completeness only applies to n×n generalisation.

• Q1. Why is Hex always determined?
  Strategy-stealing argument: if Blue (second player) had a winning strategy, Red (first player) could "steal" it — play an arbitrary first move, then follow Blue's strategy pretending the extra stone doesn't exist. The extra stone never hurts in Hex, so this gives Red a winning strategy. Contradiction. So Red wins; never a draw.
• Q2. Why PSPACE and not EXPTIME?
  Each move places one stone; total moves ≤ n². Polynomial-depth game tree. The tree may have exponentially many nodes, but minimax evaluation only needs polynomial space (depth-first traversal stores only the current path). PSPACE.
• Q3. Can you find Red's optimal move efficiently?
  Not in polynomial time (under standard assumptions). PSPACE-completeness is the formal "no fast algorithm" statement. Even though we know Red has a winning strategy by strategy-stealing, finding it is hard.
• Q4. What other board games are PSPACE-complete?
  Generalised Geography, generalised checkers, generalised chess (with bounded moves), generalised Reversi, Amazons. EXPTIME without move bounds: chess, Go (without ko), Shogi.

Sipser: §8.3 (PSPACE-complete games). Even–Tarjan 1976 for the Hex proof. Lecture notes: Module 6 slide 3. Companion problems: P38 (geography), P40 (chess).