P40 · Generalized Chess

🔊 Listen

1 · Why chess is hard · the generalisation

Standard 8×8 chess has a finite game tree — it's decidable in O(1) time (with an enormous constant). Generalisation to n×n boards with scaled piece counts gives us a problem family whose complexity grows with n. This is the only way to talk about chess's complexity meaningfully.

Fraenkel–Lichtenstein (1981)

Generalised chess on n×n boards is EXPTIME-complete. The reduction encodes TM computations using chess pieces as state markers and moves as transitions.

Bounded-move variant is PSPACE-complete

If the rules include a polynomial move bound (e.g., "draw after 50·n moves without capture"), the problem drops to PSPACE-complete. The bound prevents exponentially-long games.

This is part of a broader pattern: generalised Go is EXPTIME-complete (without ko rule) or PSPACE-complete (with bounded moves). Most natural games on n×n boards land at PSPACE-hard at minimum.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

Standard chess isn't EXPTIME-complete. 8×8 is finite, decidable in O(1). The complexity class only makes sense for generalised n×n versions.
EXPTIME-completeness ≠ unsolvable in practice. Computer chess engines play 8×8 chess at superhuman level. The complexity class is about worst-case asymptotic — it doesn't say strong opening books and pruning are useless.
50-move rule matters for complexity, not for play. The bounded-move variant flips the class from EXPTIME to PSPACE. The rule's existence in real chess is for practical termination, not complexity-theory.

🔊 Listen

4 · Q&A defence notes

Q1. Why does standard 8×8 chess have an O(1) solution?
A finite board has finitely many configurations (bounded by 10⁴³ or so). The game tree is finite. Brute-force minimax decides any starting position in constant time, dependent only on the board's size. The huge constant doesn't change the class.
Q2. What changes between PSPACE and EXPTIME?
Without a move bound, games can last exponentially long (the game tree depth is unbounded), pushing the problem into EXPTIME. A polynomial move bound truncates the tree to polynomial depth, dropping the problem to PSPACE.
Q3. What else is EXPTIME-complete?
Generalised Go (without ko rule), Shogi, generalised Othello, generalised Reversi — most games on n×n boards. EXPTIME-completeness is a kind of "natural ceiling" for game complexity.
Q4. Where in the complexity hierarchy do real games sit?
P-easy ones (perfect-play tic-tac-toe, hex on small boards). PSPACE-complete: bounded-move chess, TQBF games. EXPTIME-complete: full chess. AI-impossible: games whose state space is infinite, like Magic: The Gathering.

🔊 Listen

5 · Where to read more

Sipser: §8.3 discussion. Fraenkel–Lichtenstein 1981 for the chess proof. Lecture notes: Module 6 slide 3. Companion problems: P38 (geography), P39 (TQBF → geography).