Chess is Hard

Theorem

Chess is EXPTIME-complete is saying that the decision problem for generalized chess is: "Given an $n \times n$ chess position with chess pieces following the standard move set, does White have a forced win?" This is the $n \times n$ generalized version of chess. A regular chess board is $8 \times 8$, a technically finite game, such that deciding the winner is $O(1)$. The estimated number of legal chess positions or configs is $\approx 4.8\times 10^{44}$. This means theoretically you can build a giant computation table to make finding the winning config constant time.

The 50-move chess rule states that a player can claim a draw if 50 consecutive moves pass for both sides without a single pawn move or capture. With these rules, the problem is in PSPACE because you can search positions up to a polynomial-length game tree. To generalize the problem, Fraenkel and Lichtenstein took the game of chess but made the board $n \times n$ size and got rid of the drawing rule. They wanted to consider "can White force a win in some unbounded number of moves" without bounding the number. Storer (1983) showed that mate-in-$k$ for $k$ polynomial in $n$ is PSPACE-complete.

What does "forced win" mean for an unbounded game?

In a finite game, "White has a forced win" is straightforward: there is a strategy that wins from the starting position no matter what Black does. But once we drop the 50-move rule, generalized chess can have infinitely long games, and "wins" needs more care. The standard definition is the least fixed point of the win relation on the position graph.

A position is a Black win by the symmetric definition. Any position that is neither a White win nor a Black win under this fixed point is a draw, and infinite play falls into this bucket. White has a forced win iff the starting position is in the White win set. This is the definition the EXPTIME-complete decision problem actually decides. So "decide chess" really means "decide membership in the least fixed point", not "play out the game and see who wins", which would not terminate.

For example, take the $K + Q$ vs $K$ endgame: White has a king and queen, Black has only a king. From any non-stalemate starting position, White can force checkmate within at most 10 moves, so this position is in the White win set under the fixed point. A competent player demonstrates the witness by walking through the standard ladder mate. By contrast, $K + B$ vs $K$ (king and lone bishop versus king) is in the draw set, there is no checkmate sequence no matter what either side does.

Background

PSPACE

For chess intuition: imagine playing through a game with a 50-move rule, only writing down the current board position and which moves you have explored so far. The board itself is $O(n^2)$ symbols, and the move stack is at most $\mathrm{poly}(n)$ deep because the 50-move rule caps total game length. So the entire computation fits in polynomial space. This is exactly why $8 \times 8$ chess with the 50-move rule lives in PSPACE.

EXPTIME

The reason EXPTIME-completeness is a strong lower bound and not conditional like NP-completeness is becuase of the time hierarchy theorem. We know by the THT that $\mathrm{P} \subsetneq \mathrm{EXPTIME}$. Therefore, EXPTIME-completeness gives an unconditional lower bound. Another intuitive reason why games are in EXPTIME is because they mimic the same structure of an alternating Turing machine. By Stockmeyer's theorem APSPACE = EXPTIME, alternating polynomial space equals deterministic exponential time. A two player game of polynomial position size, where players alternate moves, is essentially an alternating polynomial space computation. So games are the EXPTIME problems the same way that SAT is an NP problem.

For chess intuition: from the starting position, White has 20 legal first moves. For each, Black has roughly 20 replies. After just 4 plies (2 moves each side) we are looking at $\approx 20^4 = 160{,}000$ leaves, and after 40 plies (a typical game) we are at $\approx 20^{40} \approx 10^{52}$ leaves. The game tree blows up exponentialy in the depth, and without a length bound the depth itself can grow with the board size. That is the EXPTIME nature of unbounded chess.

Alternating Turing Machine

A nondeterministic TM is the special case of an ATM with no universal states. So acceptance is no longer a property of a single computation path but of a tree of computation paths.

The reason ATMs matter for games is that the two state types map directly onto the two players. Existential states are the moves of the player trying to win (call her Eve, or White). Universal states are the moves of the player trying to prevent the win (call him Adam, or Black). Eve wins from a position iff she has at least one move leading to a position from which she still wins. Adam wins from a position iff all of Eves moves lead to positions where Adam still wins. This is exactly the existential and universal acceptance rule of an ATM. So an ATM accepts an input iff Eve has a forced winning strategy in the corresponding game tree.

A concrete chess walkthrough: suppose the ATM is evaluating whether White wins from the starting position. White is to move, so the ATM enters an existential state and branches on all 20 of White's legal first moves. Pick the branch where White plays $1.\,e4$. Now it is Black's turn, so the ATM enters a universal state and branches on all 20 of Black's legal replies ($1\dots e5$, $1\dots c5$, $1\dots e6$, and so on). The branch accepts only if every one of those Black replies leads to a position where White still wins. So the existential branching is "White picks a line that works", and the universal branching is "Black tries every defense". This is exactly how a chess engine's minimax search is structured, and it is exactly what an ATM does natively.

We measure ATM resources the same way as ordinary TMs. $\mathrm{ATIME}(f(n))$ is the class of problems decidable by an ATM in time $f(n)$, and $\mathrm{ASPACE}(f(n))$ is the class decidable by an ATM in space $f(n)$. The Chandra-Kozen-Stockmeyer (CKS) 1981 theorem gives the relationship between alternating and deterministic resources:

• $\mathrm{ATIME}(f(n)) \subseteq \mathrm{DSPACE}(f(n)) \subseteq \mathrm{ATIME}(f(n)^2)$
• $\mathrm{ASPACE}(f(n)) = \mathrm{DTIME}(2^{O(f(n))})$ for $f(n) \geq \log n$

The second equality is the one we use. Setting $f(n) = \mathrm{poly}(n)$ gives $\mathrm{APSPACE} = \mathrm{EXPTIME}$. So any decision problem that an ATM can solve in polynomial space is in deterministic exponential time, and vice versa. Generalized chess fits the left side trivially, a chess position is $\mathrm{poly}(n)$ bits, and simulating play is an alternation between Whites existential moves and Blacks universal moves. So chess sits inside APSPACE, hence inside EXPTIME, and we get the upper bound for free without counting positions.

Gadgets

When we reduce problem $A$ to problem $B$, we usually do not encode all of $A$ at once. Instead, we break $A$ into small pieces (a variable, a clause, a wire, an AND, a checkmate condition) and build one gadget per piece in the language of $B$. Then we glue the gadgets together so that the global behavior of the gadgets simulates a run of $A$.

A gadget has three parts:

• Schematic. What the gadget is supposed to do logically. The interface and the truth table.
• Realization. How the gadget is actually built inside problem $B$. For chess, this is a small region of board with a fixed piece configuration.
• Forcedness. Why the simulation is faithful. If a player deviates from the intended behavior of the gadget, they immediately lose. In chess this usually means the deviation walks into a mate-in-$O(1)$.

For a gadget reduction to work, the total construction must have size polynomial in the source instance. Each gadget is constant size or grows polynomially, and the number of gadgets is polynomial in the source. So the chess position built from a G3 or 2CL instance has size $\mathrm{poly}(|G3|)$ or $\mathrm{poly}(|2CL|)$. Therefore, gadget reductions preserve EXPTIME-hardness.

A chess example helps fix intuition. A "wire" gadget in chess is a corridor of empty squares between two pawn walls, like a hallway. A queen sits at one end. The schematic says the wire propagates a one-bit signal from the sender to the receiver. The realization is the corridor itself. The forcedness is that the pawn walls are reinforced by defenders so any attempt to leave the corridor or capture the queen walks into a mate in 1 or mate in 2. So the gadget is "forced" in the sense that the only thing the queen can do is slide along the wire, and the only thing the opponent can do is leave the wire alone.

2CL

A move flips the direction of a single edge, but only if the resulting orientation is still legal. In 2CL, edges are partitioned between White and Black, players alternate, and White wins if a designated target edge ever points in a designated target direction.

By analogy to chess: think of each edge as a piece you can flip back and forth, like flipping the orientation of a rook from one side of a square to another. Flipping an edge is a "move", and the legality constraint at each vertex is the equivalent of "your move cannot put your own king in check". Each player can only flip edges of their own color, just as in chess you can only move your own pieces. White wins not by capturing the king, but by getting one specific edge to point in a specific direction, which is the 2CL analog of checkmate.

The reason 2CL is the right hardness source for spatial games like chess is that its primitives are graph-theoretic. AND vertices, OR vertices, wires, and crossovers are local structures that map directly onto local board regions. G3, by contrast, is a Boolean game, where the formula and the variable assignments are global objects. Encoding a global Boolean formula in chess is what forces the FL81 proof to use long clock channels spanning the whole board to keep variables synchronized. With 2CL, faithfulness can be enforced inside each gadget independently, which is why the modern proof is much shorter.

The complexity of constraint logic depends on the number of players and the length bound:

We use the unbounded 2CL row for chess, since generalized chess has no length bound.

G3

G3 was proved EXPTIME-complete in Stockmeyer's 1979 paper "Provably difficult combinatorial games". This is like QBF on steroids.

• Ordinary Quantified Boolean Formula: a syntactic object, a Boolean formula with quantifiers ($\forall, \exists$) over its variables. The only difference between QBF and TQBF is that QBF can be true or false. We know QBF is PSPACE-complete because each variable is assigned once.
• G3 is played on a Boolean formula where two players alternate, each controlling some of the variables, and each move flips the value of one of their variables. Because variables can be revisited and changed many times, the game can run for exponentially many distinct global states. This pushes G3 from PSPACE to EXPTIME.

On Player I's turn, they must flip exactly one variable in $X$. The game then transitions to Player II, who must flip one variable in $Y$. The losing condition is that Player I loses if $\mathrm{I\text{-}LOSE}(X, Y)$ becomes true after their move. The same holds for Player II with $\mathrm{II\text{-}LOSE}(X, Y)$. Deciding whether Player I has a forced win in G3 is EXPTIME-complete. The reason G3 is hard is that with $n$ variables, the assignment space has size $2^n$ and players can revisit assignments, so the game tree has exponential depth. The 12-DNF restriction is a normal form that is enough to encode alternating computations.

A loose chess analogy. Think of each variable as a piece on the board, where it's truth value (TRUE or FALSE) is the side of the square the piece is on. Player I owns the white pieces and can only flip her own. Player II owns the black pieces and can only flip his. The losing formula is like a "your king is in checkmate" condition, it is a Boolean predicate over all the piece positions, and if your predicate evaluates to true after your move you lose. The crucial difference is that in chess each piece has many possible squares, while in G3 each variable has only two values, but variables can be flipped over and over. This is what makes G3 unbounded in length even with finite variables.

The Original Fraenkel-Lichtenstein Reduction

The reduction takes a G3 instance and builds an $n \times n$ chess position (with $n$ polynomial in $p + q + m$) such that "White has a forced win in chess $\iff$ Player I has a forced win in G3". The chess position is built from gadgets:

• Boolean controller gadgets: one per variable. Holds the variable's current truth value.
• Channels: vertical corridors connecting controllers to clause gadgets above.
• Clock mechanisms: Normal Clock (NC) and Rapid Clock (RC). Enforce timing.
• Clause gadgets: one per clause of I-LOSE and II-LOSE. Test whether the clause is satisfied.
• Checkmate gadgets: at the top of the construction. Reaching one wins the game.

Gadget Encoding

Build a giant chess gadget so that a G3 instance becomes a chess position where White-to-move wins iff the corresponding G3 player wins. The encoding is the following:

• Most of the board is locked. Pawns and minor pieces are placed in mutual zugzwang so almost no peripheral piece can move without losing material immediately.
• A few pieces per variable are alive. For each Boolean variable in the G3 instance, 1 rook and 2 queens can actually move. Their position encodes the truth value of that variable.
• Channels. The frozen walls leave narrow corridors open. Figure 2, the cleaner schematic, shows these channels topologically: "W CLOCK-CHANNEL", "B CLOCK-CHANNEL", "W DETOUR ROUTE", and so on. A queen entering one of these channels can only slide along that predefined route, because everywhere else it would be blocked or captured.
• Rooks act as switches. Where a rook sits decides which channel is open and which is closed. So when a player tries to march a queen toward the opponent's king, the queen's available path is determined by the current configuration of rooks.
• Winning. A queen reaching the enemy king delivers checkmate. The G3 win condition (the formula evaluates to TRUE/FALSE) is encoded as: there exists a sequence of channels through which a queen can travel to deliver checkmate. Whether the path exists depends on whether the variable assignment satisfies the formula.
• Clock channels keep the players synchronized so neither side can stall or skip ahead. Each tick forces a move on the other player's side, mirroring the strict alternation of G3.

Boolean Controller in Depth

The boolean controller is the heart of the FL81 reduction. There is exactly one controller per variable in the G3 instance, and the controller's job is to remember the variable's current truth value and expose that value to the rest of the construction.

Schematic. A boolean controller has two stable internal states ("variable is TRUE" or "variable is FALSE") and one input from the player who controls the variable. On the controller's player's turn, the player either flips the controller (changing TRUE to FALSE or vice versa) or leaves it alone. The controller exposes its current state to a vertical channel that runs upward toward the clause gadgets.

Realization. Each variable $x_i$ has a small region of board reserved for it. Inside this region:

• One rook sits on one of two designated squares. The square it sits on encodes the truth value: left square means TRUE, right square means FALSE (or any analogous binary encoding).
• Two queens sit at the bottom of two parallel channels rising upward. One queen serves the TRUE channel and the other serves the FALSE channel.
• The rest of the region is filled with pawns and minor pieces in mutual zugzwang.

When the rook sits on the TRUE square, it physically blocks the FALSE channel, so the FALSE queen has nowhere to go. The TRUE queen can slide upward freely. When the rook sits on the FALSE square, the situation reverses. So the rook position controls which queen has access to its channel, and that queen's accessibility is the literal interpretation of the variable's truth value.

Forcedness. Three things have to be enforced for the controller to faithfully encode a G3 variable:

1. Only the right player can flip the rook. The rook is assigned to either Player I or Player II based on which set ($X$ or $Y$) the variable belongs to. Pieces of the wrong color cannot reach the rook's two squares without losing material immediately. Defender pieces are pre-positioned so any wrong-player attempt to interact with the rook walks into mate-in-$O(1)$.
2. The rook can only sit on its two designated squares. If the rook's controlling player tries to move the rook anywhere else (a third square, a far file), the rook is immediately captured by a defender. So the controller has exactly two stable states and no third option.
3. The queens cannot leave their channels. The pawn walls of each channel are arranged so the queens can only move along their channel. Any sideways move walks into mate. So the only thing a queen can do is slide up its channel toward a clause gadget, and only if the rook is in the right position.

Connecting to G3. When Player I has to flip a variable in $X$ on her turn, the clock channel forces a move in the controller region, and the only legal move there is to flip the rook between its two squares. So flipping the rook in chess corresponds exactly to flipping the variable in G3. Whether the rook ends up TRUE or FALSE is the player's choice, mirroring the player's choice in G3 of which way to flip the variable. The clause gadgets above read these signals through the channels and decide whether the I-LOSE or II-LOSE formula has become true.

The controller is the FL81 analog of the wire-and-AND/OR primitives in 2CL. It is the unit that turns a player's move into a one-bit signal that the rest of the construction can consume. The reason FL81 needs the global clock channels at all is that the controllers cannot enforce alternation by themselves: nothing in the controller stops Player I from flipping two variables in a row, or from refusing to flip any variable, except the threat of losing mate elsewhere on the board. The clocks impose that threat globally. In the modern 2CL proof, the equivalent of this restriction is enforced locally inside each gadget, which is why we can drop the clocks entirely.

Thus, chess is in EXPTIME because of the the upper bound (counting positions), and G3 is EXPTIME-hard, and the gadget construction has size polynomial in the G3 instance. Therefore chess is EXPTIME-hard too, hence EXPTIME-complete.

A Modern Proof for Generalized Chess is EXPTIME-complete

The result is the same but the proof is much shorter and more modular compared to the original gadget construction.

Chess $\in$ EXPTIME using APSPACE

Chess $\in$ EXPTIME by Stockmeyer's 1981 theorem that APSPACE = EXPTIME. The class of problems decidable by an alternating Turing machine in polynomial space is exactly the class of problems decidable by a deterministic Turing machine in exponential time. An alternating Turing machine is like a nondeterministic Turing machine but with two types of branching: existential states and universal states. Existential states correspond to one player's choices and universal states to the other player's. The CKS theorem says that for game-like problems, deterministic exponential time and alternating polynomial space are the same resource bound. Chess is in APSPACE, hence in EXPTIME.

Define an alternating Turing machine $M$ as the following. The tape stores the current chess position. A position consists of:

• The contents of each of the $n^2$ squares (each square is empty or holds one piece-color combination, drawn from an alphabet of size 13).
• The active player (1 bit).
• Castling rights and en passant flags ($O(\log n)$ bits, since these depend on piece count and location bounded by $\mathrm{poly}(n)$).

The total position size is $O(n^2 \log n) = \mathrm{poly}(n)$. Therefore, the tape uses polynomial space. $M$ operates as follows. From the current position, if it is White's turn, $M$ enters an existential state where it nondeterministically guesses a White move and updates the tape. If it is Black's turn, $M$ enters a universal state. It branches on every legal black move. At each leaf of the alternating tree, $M$ checks whether the position is checkmate against Black (accept) or against White (reject). Each move modifies a constant number of squares, so each transition uses $O(1)$ extra workspace beyond the position itself. The total space at any point in the computation is then $\mathrm{poly}(n)$. The depth of the alternation tree may be exponential. Chess games can be exponentially long without drawing rules, but alternating space complexity does not depend on depth. It depends on the working memory at each node. Therefore $\text{Chess} \in \mathrm{APSPACE} = \mathrm{EXPTIME}$ by CKS.

A concrete example of one node of $M$. Suppose the tape encodes the Italian Game position after $1.\,e4\, e5\, 2.\,Nf3\, Nc6\, 3.\,Bc4$. It is Black's turn, so $M$ enters a universal state. The branches are all of Black's legal third moves: $3\dots Bc5$ (Italian Game proper), $3\dots Nf6$ (Two Knights Defense), $3\dots Be7$ (Hungarian Defense), and so on, roughly 30 options. For $M$ to accept this position, every single one of those Black branches must lead to a position where White still wins. The tape memory used at this node is just the encoded position, around $O(n^2 \log n)$ bits, regardless of how deep the recursion goes. Each move only flips a constant number of squares, so updating the tape between branches is cheap. The exponential blowup is in the depth of the tree, not in the memory at any single node, which is the magic of APSPACE = EXPTIME.

Compared to the 1981 upper bound, Fraenkel argued the upper bound by counting positions and applying backward induction on the game graph. The APSPACE argument is more generic and gives EXPTIME containment for any generalized game with unbounded length, polynomial size positions, and finite local move computation. Replacing a game-specific counting argument with an alternating argument does not constrain the proof just to chess.

EXPTIME-Hard using 2CL

A 2CL instance consists of:

• A constraint graph $G$ with a satisfied initial orientation.
• A labeling of each edge as White-controlled or Black-controlled.
• A designated target edge $e^*$ and target direction.

Players alternate, starting with White. On her turn, the player to move chooses one of her own edges and reverses its orientation, subject to the requirement that the resulting orientation still satisfies $G$. If no legal move exists, the player to move loses. White wins if the target edge ever becomes oriented in its target direction. By the Hearn theorem (2005), deciding whether White has a forced win in 2CL is EXPTIME-complete. This gives a generic EXPTIME-hard game to reduce to generalized chess, and its primitives are graph-theoretic rather than Boolean, which is a much better fit for spatial games like chess.

Gadget Construction

Given a 2CL instance ($G$, edge labels, target edge $e^*$) we build an $n \times n$ chess position $P$ such that White has a forced win in $P$ $\iff$ White has a forced 2CL win on $G$. We promise that $|P| = \mathrm{poly}(|G|)$. For each AND vertex of $G$, place an AND gadget in $P$. For each OR vertex of $G$ (constraint 2, three blue edges), place an OR gadget in $P$. Connect gadgets with wire corridors matching $G$'s edge structure. At each crossing of two wires in the planar embedding, place a CROSSOVER gadget. Label each edge gadget as White-controlled or Black-controlled, matching $G$. Connect the target edge's wire to a checkmate gadget that fires when the target edge attains its target direction.

We give chess realizations of the AND vertex, OR vertex, CROSSOVER, wire, and checkmate primitives. Each gadget is presented in three parts: schematic, realization, and forcedness.

The schematic specifies what the gadget does logically. The realization specifies how chess implements it. Forcedness specifies why deviation loses. All gadgets share a common construction style. Each gadget sits inside a region whose periphery is locked: pawns and minor pieces are placed in mutual zugzwang so no peripheral piece can move without losing material immediately. Inside the locked periphery, a small number of designated pieces, typically one or two rooks per controllable edge plus a queen per signal-carrying wire, are mobile. These mobile pieces encode and propagate the gadget's logical state.

Wire

Schematic. A wire is a directed channel that propagates a one-bit signal (edge "in" or "out") between gadgets, with a sender end and a receiver end.

Realization. A corridor of empty squares running along a file, rank, or diagonal, bounded on both sides by pawn walls. A queen at the sender end can slide along the wire to the receiver end, but only if a designated rook is in its "open" position. If the rook is "closed", the queen's path is blocked.

Forcedness. The pawn walls are arranged so any attempt to capture the queen or push a pawn into the corridor walks into a mate-in-$O(1)$ by a pre-positioned defender. The wire's logical state is determined entirely by the rook's position.

AND Vertex Gadget

Schematic. Three incident edges: two red (weight 1) and one blue (weight 2), with vertex constraint 2. The constraint is satisfied iff the blue edge points in OR both red edges point in.

Realization. Three input wires meet at a junction region. At the junction sit three rooks, one per incoming wire, whose positions encode their edges' orientations. A queen entering from a fourth output corridor finds a clear path iff the AND condition holds: blue rook "in", or both red rooks "in". In every other rook configuration, a defender pawn or rook blocks the path.

Forcedness. Each rook can be moved only by the player who controls the corresponding 2CL edge. Any attempt by the wrong player to flip the rook walks into mate-in-$O(1)$ by a perimeter bishop or queen. Any attempt by the controlling player to flip a rook in a way that violates the 2CL constraint (e.g., flipping the blue rook to "out" when both red rooks are also "out") is similarly punished. So the rook positions in the chess gadget faithfully track the edge orientations in the 2CL graph.

OR Vertex Gadget

Schematic. Three blue edges with vertex constraint 2. The constraint is satisfied iff at least one blue edge points in.

Realization. Symmetric to AND but with three blue rooks at the junction. The queen's path opens whenever any one of the three rooks is "in".

Forcedness. Same as AND. Each rook is controlled by exactly one player, and deviation is punished by mate-in-$O(1)$.

CROSSOVER Gadget

Schematic. Two wires cross without interaction. The orientation of either wire is unaffected by the other.

Realization. Two corridors intersecting at right angles. At the intersection, an interlocking pawn structure separates the two signal-carrying queens onto disjoint paths, where one passes horizontally and the other vertically. A pinned piece (typically a knight or bishop) occupies the central square so they cannot interfere.

Forcedness. The pinned piece is held by mate threats from defenders on both sides. Any attempt to move it triggers a mate-in-$O(1)$.

Checkmate Gadget

Schematic. A target signal that, when activated, ends the game in White's favor.

Realization. A small region (5 to 10 squares wide) containing the Black king surrounded by Black pawns in mutual zugzwang. The king has no legal moves. A White queen entering from the target wire's output corridor delivers checkmate: no escape, no interpose, no capture. This is exactly Zhang's redrawing of the FL81 figure, the one chess-specific construction we inherit unchanged from the original proof.

Comparison

In FL81, simulation faithfulness is enforced globally by the clock channels that span across the whole board. In this proof, faithfulness is enforced locally where each gadget has its own way of punishment. There is no global timing structure. This shortens the proof, since the clocks consume much of the FL81 argument. Chess is in EXPTIME by the alternation (APSPACE) argument and EXPTIME-hard by reduction from 2CL with chess realizations of AND, OR, CROSSOVER, and checkmate gadgets. Therefore, chess is EXPTIME-complete.

Here is a comparison of the techniques used in the Fraenkel-Lichtenstein proof versus the modern techniques.

Implications

Chess engines can not be exponentially improved. Stockfish, AlphaZero, and other chess engines are all heuristic search algorithms. EXPTIME-completeness tells us that no algorithm can acheive perfect play on $n \times n$ chess in polynomial time. Games with polynomial bounded length are PSPACE-complete. Games with unbounded length jump to EXPTIME-complete for generalized games like generalized chess and generalized checkers. Actual $8\times 8$ chess has a finite game tree. Checkers on an $8\times 8$ board has been solved, where it is a draw under perfect play.

Real Chess vs Theoretical Chess

There is a gap between "chess is EXPTIME-complete" and "humans and engines play chess very well in practice". Both are true, but they live in different universes. The theoretical result is about the asymptotic behavior of $n \times n$ chess as $n$ grows. Real chess is a fixed $8 \times 8$ instance with finite game tree size, and the entire history of competitive play happens inside that one instance.

Why strong play does not refute EXPTIME-completeness

Top players and engines do not need to "solve" chess to play well. They need to play better than the opposition. This is a heuristic problem, not a decision problem. EXPTIME-hardness applies to the decision problem "does White have a forced win from this position", not to "can a player play strong chess in practice". Pattern recognition, calculation depth, and positional intuition are all heuristics. They are very good heuristics but they make no claim of perfect play. The same is true for engines. So the theoretical lower bound and practical performance are talking past each other.

Chess openings as a partial solution

Chess openings are the most studied region of the game tree. The first 10 to 15 moves of common lines (Sicilian Defense, Ruy Lopez, Queen's Gambit, and so on) have been analyzed by humans for centuries and by engines for decades. An opening book is essentially a memorized fragment of the chess game graph: from the starting position, a tree of "best" moves and responses, branching down to positions where engine analysis takes over. In the deepest, most-played lines, opening theory now extends to move 20 or beyond.

In a meaningful sense, opening theory is a partial solution of the early game tree. It is constructed by combining human judgement with billions of engine evaluations. But this partial solution does not contradict EXPTIME-hardness for two reasons:

1. The opening book covers only the most popular lines. The full game tree from the starting position branches to roughly $10^{120}$ leaves (Shannons number). Opening theory has explored a vanishingly small fraction.
2. Even the explored fraction is not provably optimal. Opening evaluations are engine evaluations, which are heuristic. We believe the Najdorf Sicilian is sound, we have not proven it.

So opening theory is a beautiful example of the gap between "we can play this well" and "we have decided the problem". Top players often steer games into less analyzed lines specifically to escape opponents preparation, which is itself a sign that even the heavily studied openings are not "solved" in the formal sense.

Why engines plateau

Stockfish and AlphaZero are heuristic search algorithms. Stockfish uses alpha beta pruning over hand tuned evaluation functions, and Lc0 / AlphaZero combine Monte Carlo Tree Search with neural network evaluations. Both search to a depth of 30 to 50 ply in a typical position. EXPTIME-completeness tells us why these engines plateau: there is no algorithm that achieves perfect play on $n \times n$ chess in polynomial time, so any engine is necessarily approximating. Improvements to Stockfish or Lc0 are improvements to the heuristic, not to the asymptotic complexity. The lower bound says we can not expect a polynomial time algorithm that suddenly "solves" chess. The best we can do is search smarter and deeper.

Endgame tablebases as a true solution

The one place where chess actually has been solved is endgames with few pieces. The Syzygy and Lomonosov tablebases store optimal play for all positions with up to 7 pieces. These are exact, not heuristic, and they are finite database lookups. Tablebases work because the position count for $\leq 7$ pieces is small enough to enumerate. They are not in tension with EXPTIME-completeness because they only solve one fixed instance ($8 \times 8$, $\leq 7$ pieces), not the asymptotic family.

So the practical chess landscape is: a heuristic opening book at the start, heuristic engine and human play in the middlegame, and an exact tablebase at the end. The theoretical EXPTIME-hardness governs the middle, where we cannot do exponentially better than searching.

Companion Results

The same EXPTIME-complete pattern shows up across many generalized games. The general lesson is that any two-player game with polynomial-size positions and unbounded length is a candidate for EXPTIME-completeness. The hardness sources differ in primitives, but the alternation upper bound and the gadget hardness lower bound are reused.

Go

Robson (1983) proved that generalized $n \times n$ Go with Japanese ko rules is EXPTIME-complete. Go is in EXPTIME by the same APSPACE argument as chess. A Go position is $O(n^2)$ stones plus a constant number of ko bits, so positions are polynomial size and the alternating Turing machine simulating play uses polynomial space. The hardness reduction goes from a variant of G3 directly into Go positions. Robson builds Go gadgets that simulate variable assignments and clauses using ladder races and ko fights, which are the spatial primitives Go offers. Without ko, the bound drops to PSPACE, since the lack of position repetition limits game length polynomially. So the unboundedness of game length, induced by ko, is exactly what pushes Go from PSPACE to EXPTIME, mirroring the role of the missing 50-move rule in generalized chess.

Checkers

Robson (1984) proved that generalized $n \times n$ checkers is EXPTIME-complete, also using a reduction from G3. As with chess, the unboundedness of game length is what pushes the complexity from PSPACE to EXPTIME. If a no progress drawing rule is added (mirroring the 50-move rule in chess), checkers drops to PSPACE-complete. Schaeffer et al. (2007) later solved actual $8 \times 8$ checkers, showing that the game is a draw under perfect play. This is a finite computation since the $8 \times 8$ board has a finite game tree, but it took 18 years of compute and roughly $5 \times 10^{20}$ positions analyzed. The contrast with chess is informative: Schaeffer's result is consistent with the EXPTIME-hardness of the generalized version, since solving one fixed instance ($8 \times 8$) does not contradict the asymptotic lower bound on the family ($n \times n$).

Othello, Hex, and others

Generalized Othello (Reversi) on $n \times n$ boards is PSPACE-complete (Iwata and Kasai 1994), not EXPTIME-complete, because the game length is bounded by $n^2$ moves. So Othello sits with bounded chess and bounded checkers in PSPACE. Generalized Hex is also PSPACE-complete (Reisch 1981). The pattern is consistent, bounded length puts you in PSPACE, unbounded length opens the door to EXPTIME.

Hearn-Demaine Zoo

The Hearn and Demaine NCL/2CL framework unified hardness proofs for a large class of games and puzzles. The same constraint-logic primitives (AND, OR, CROSSOVER, wire) are reused across many target problems:

• PSPACE-complete (single player or polynomial-bounded length): Rush Hour, Sokoban, sliding-block puzzles, Lemmings, Bounded 2CL.
• EXPTIME-complete (two player, unbounded length): Generalized chess, Go (with ko), checkers (no draw rule), 2CL.
• RE-complete (two player, unbounded, private information): Team 2CL, Magic: The Gathering (Churchill, Biderman, Herrick 2019).

The frameworks value is that once you have constraint-logic gadgets in your target problem, you get hardness for free. Building wire, AND, OR, and CROSSOVER gadgets in a new game immediately gives PSPACE-hardness (single player) or EXPTIME-hardness (two player), depending on which constraint-logic variant you reduce from. This is exactly what the modern chess proof exploits, and it is the reason the same proof template now applies to alot of games that each previously required a custom reduction.

Links

1. Naomi Cebula's Medium Post: medium.com/smith-hcv/computational-complexity-of-a-game-of-nxn-chess
2. Computing a perfect strategy for $n \times n$ chess requires time exponential in $n$: sciencedirect.com
3. G3: epubs.siam.org

References

1. Fraenkel, A. S., & Lichtenstein, D. (1981). Computing a perfect strategy for $n \times n$ chess requires time exponential in $n$. Journal of Combinatorial Theory, Series A, 31(2), 199 to 214.
2. Stockmeyer, L. J., & Chandra, A. K. (1979). Provably difficult combinatorial games. SIAM Journal on Computing, 8(2), 151 to 174.
3. Chandra, A. K., Kozen, D. C., & Stockmeyer, L. J. (1981). Alternation. Journal of the ACM, 28(1), 114 to 133.
4. Hearn, R. A., & Demaine, E. D. (2005). PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1, 2), 72 to 96.
5. Hearn, R. A., & Demaine, E. D. (2009). Games, Puzzles, and Computation. A K Peters / CRC Press.
6. Storer, J. A. (1983). On the complexity of chess. Journal of Computer and System Sciences, 27(1), 77 to 100.
7. Zhang, Z. (2022). A note on the computational complexity of selfmate and reflexmate chess problems. arXiv:2208.05376.
8. Schaeffer, J., et al. (2007). Checkers is solved. Science, 317(5844), 1518 to 1522.
9. Robson, J. M. (1983). The complexity of Go. Information Processing, 83, 413 to 417.
10. Robson, J. M. (1984). $N$ by $N$ checkers is EXPTIME complete. SIAM Journal on Computing, 13(2), 252 to 267.
11. Iwata, S., & Kasai, T. (1994). The Othello game on an $n \times n$ board is PSPACE-complete. Theoretical Computer Science, 123(2), 329 to 340.
12. Reisch, S. (1981). Hex ist PSPACE-vollständig. Acta Informatica, 15, 167 to 191.
13. Churchill, A., Biderman, S., & Herrick, A. (2019). Magic: The Gathering is Turing complete. arXiv:1904.09828.