The paper "On the complexity of chess" by James A Storer is available online, and it’s fairly readable. It demonstrates that deciding the winner in chess (expanded to NxN boards, with correspondingly more pieces) is PSPACE-complete.
He proves a reduction from “Generalized Geography” to generalized chess, via a couple of intermediate steps.
Generalized Geography (GG) is a two player game in which the players, called White and Black, move alternately, subject to the following conditions:
Board. Directed graph with a distinguished node called the start node, and with all nodes having nonzero outdegree.
Initial Configuration. White places a marker on the start node, and it is Black’s turn.
Move Rule. A player may place a marker on any node that has an incoming edge, coming from the last node played.
Win Rule. A player loses by placing a marker on a node that already contains one.
Generalized Geography was proved to be PSPACE-complete via a reduction from the decision problem on quantified Boolean formulas.
First he shows that Generalized Geography, played on an arbitrary graph, can be reduced to playing on a grid graph, yielding the PSPACE-complete game “Array Generalized Geography” or AGG. Then that is reduced to “Nonstandard AGG” in which the graph contains only the following sorts of nodes (plus the start node and dead-end nodes) in the orientations shown:
(All figured from the paper linked above.)
This is the problem that is ultimately reduced to generalized chess.
The reduction requires two sorts of widgets: widgets that implement Nonstandard AGG moves on the nodes shown above, and widgets that ensure the winner of the AGG game is also the winner of the chess game.
These widgets are constructed entirely with pawns and queens. Here is the widget that traps the White king:
A queen on square x or y checkmates. White will need at least four moves to avoid checkmate in this situation (by moving his pawns up, or escaping on the diagonal.) So, the construction must ensure that Black must be able to get a queen to x or y in time if White attempts to escape, and that the winner of the game gets a queen free that can move to x or y. (Black’s king is trapped in a similar wall of pawns.)
The other widgets are given schematically rather than piece by piece. The lines are walls of pawns at least two thick; W represents a White queen; P represents a Black pawn, and B represents a Black queen. Here is the widget representing the “fork” node shown above:
The bulk of the paper is chess analysis showing that these constructions correctly implement the pieces of a Nonstandard AGG game, and that neither player can do better than by playing the embedded game.
This construction is, of course, highly artificial. But it is a polynomial reduction, so there is “only” a polynomial blowup in the number of pieces and the running time required. Any actual reduction from another problem in PSPACE is likely to be unimaginably large. (On the other hand, as a chess position the reduction is actually “simple” in that it is quite structured, has no long-range interactions, and consists only of pawns and queens!)
We also need to show that generalized chess is contained in PSPACE; the assumption in the paper is that the maximum move depth is polynomially bounded by some P(N). (Otherwise exponentially-long games are possible.) With that assumption, we can do a depth-first search through the game tree, requiring only about P(N) N^2 log^4 N space.
Originally answered on Quora: https://www.quora.com/How-do-you-prove-that-the-chess-game-is-a-PSPACE-complete-problem-the-hardest-kind-of-problems-in-PSPACE-complexity-class/answer/Mark-Gritter
