You may know the apparent paradox: apps and media present chess as enormously complex, then you open an app, play a reasonable move and receive an engine correction with a line you could not find alone.
Can this really be reduced to formulas? Do mathematics and computing offer partial answers, or is complexity merely a story we tell? There are two distinct points: exhaustive exploration of the full game space is beyond current practical resources, while selective search, evaluation, pruning and learning can produce performance exceeding human match results.
No complete solution from the initial position is known. Nevertheless, programs can beat leading humans without possessing a proof of perfect play: choosing strong moves against an actual opponent is a different task.
The board from within: a state graph
For mathematics and computing, chess has precise, public and deterministic rules. A knight follows its defined jump; a bishop remains on its colour. Human choices may be uncertain to you, but the rules themselves contain no random draw deciding whether a move works.
- A sufficiently specified position, including pieces, side to move, castling, en passant and relevant history, is a state.
- A legal move transitions to another state.
- A game is a trajectory through states.
Represent this as a directed graph: nodes are states and edges legal moves. From a fixed state, an exploration tree keeps different move sequences separate. Game theory in chess explores the framework, while opening equilibria distinguishes formal results from preparation.
The move tree: what “I calculated everything” leaves out
At a club, you may hear “I calculated everything”. Sometimes a local forced sequence can be checked completely. Across a complex position’s full game tree, however, players normally examine a selected subset of continuations.
Let (b) be a branching factor, (d) depth in half-moves, or plies, and (N(b,d)) an approximate leaf count in a uniform model. The simple model gives exponential growth:
Adding depth multiplies work rather than adding a small fixed amount. That is why finite time and memory matter even on fast machines. Real branching varies, and a search can merge transpositions, prune or use other methods; the formula is not an exact count of every engine’s work.
A middlegame illustration often uses 30–40 legal moves. With (b=35), depths six, ten and sixteen already differ enormously. Human players and programs select possibilities, though that shared description does not establish identical cognitive and computational mechanisms.
The methods below cut, estimate and order moves to make useful search practical.
Shannon’s number: an order of magnitude
Claude Shannon, a founder of information theory, considered computer chess in his 1950 article. His famous (10^{120}) estimate, the Shannon number, conveys the scale of a game tree under simplifying assumptions.
It is not an exact list or count of distinct reachable positions. The large estimate helps explain the impracticality of naive exhaustive traversal; it does not prove that no other method could determine the game’s value.
Why chess is not solved, and why an engine can still win
“Solved” can mean different levels of result. A weak solution determines the initial position’s outcome under perfect play and supplies the necessary strategy; a strong solution covers all relevant positions. Game theory, including work associated with John von Neumann, provides tools for reasoning about rational choices and Nash equilibrium. Chess’s perfect-information structure is central here.
| Game | Solved? | Comment |
|---|---|---|
| Tic-tac-toe | Yes | A small game with a known optimal strategy |
| English draughts, or checkers | Yes | Its initial position is a draw under perfect play |
| Chess | No | No complete proof of the initial perfect-play outcome |
| Go | No from the standard initial position | AlphaGo demonstrated strong match performance, a separate achievement |
“Unsolved” does not mean an engine can never be certain about any local position. A forced mate or tablebase-covered endgame can supply exact information under its rules. To beat a human, the engine does not need to solve the starting position. The existence framework is discussed in Zermelo’s paradox.
EXPTIME-complete: be careful with generalisation
Fraenkel and Lichtenstein (1981) study deciding who can win from an arbitrary position in a generalisation of chess on an board. That problem is EXPTIME-complete. The authors note that the result says little directly about 8×8 chess.
It is worst-case complexity for a family whose input size varies. It gives neither an imposed computing time for every position nor proof that solving the usual initial position is physically impossible. Fixed-size chess under termination rules remains finite; “undecidable” does not mean merely too expensive in practice.
What a traditional engine does: minimax without naivety
The architecture of traditional engines such as Stockfish can be introduced through three functions:
- Search: explore a tree of moves.
- Evaluation: estimate which side is better.
- Optimisations: avoid spending the budget on unhelpful branches.
Minimax chooses the best guaranteed outcome against the opponent’s best replies. In a simplified two-ply recurrence:
In club terms: do not choose a move that works only if the opponent fails to respond well. This is a worst-case model, not a guarantee against tilt or a measured description of your mind.
Unoptimised minimax grows quickly. Fortunately, branches can sometimes be skipped while preserving the result of a fixed evaluated tree. Minimax in chess develops negamax, null-move pruning and transposition tables while distinguishing exact reformulations from selective heuristics.
Alpha-beta: cutting without changing the fixed-tree value
Alpha-beta pruning optimises minimax traversal. It skips work that cannot affect a choice already available to an ancestor.
Using one score perspective, alpha is an available lower bound for MAX and beta an available upper bound through MIN. When alpha is at least beta, the branch can be cut. At identical tree, depth and evaluations, exact alpha-beta preserves the minimax value. Tied moves may still be selected differently.
As an analogy, you may stop exploring a tactical line once you establish it cannot improve on another available plan. Good move ordering can substantially reduce explored nodes and allow deeper search within the budget. Extra selective pruning has different guarantees from exact alpha-beta.
Evaluation: estimating without calculating everything
At a depth cutoff, a nonterminal position still needs a value estimate. Traditional hand-written evaluations use criteria such as:
- Material.
- Pawn structure.
- Piece activity.
- King safety.
- Controlled squares and other features.
This is not merely adding fixed piece points. Engines combine tuned features and search. Stockfish announced NNUE neural evaluation in 2020 while retaining alpha-beta search, showing that learning and this search family can be combined.
Estimating a promising position without calculating mate resembles a familiar practical task. That analogy does not prove a human mechanism in the engine. Chaos theory in chess similarly distinguishes tactical instability as an analogy from mathematical chaos.
AI: learning to evaluate and select
Rather than write every evaluation feature by hand, a system can learn from data or self-play. Neural networks and machine learning can support two tasks:
- Evaluating a position through a learned representation.
- Proposing promising candidates to guide exploration.
That does not mean every learned system follows one architecture or always searches less. It means selection and evaluation can change how a computing budget is used.
Strong human players also select candidates before calculating, but this is an analogy at the level of the task, not proof that network training reproduces human intuition.
Self-play provides a training loop:
- Generate experience through games.
- Learn predictions about outcomes and promising moves.
- Update selection and evaluation using those results.
- Repeat.
Researchers still define representations, architectures, training objectives and procedures. Learned preferences can emerge without manually specifying each strategic concept; the process is not free of engineering.
IBM and Kasparov: a historic match without solving chess
In 1997, Deep Blue beat Garry Kasparov, then world chess champion, using an IBM system designed specifically for chess. It demonstrated the power of specialised hardware, search and evaluation.
Winning that match did not solve chess. A machine can outperform the leading human in a match without a perfect strategy from the initial position. Subsequent engine advances do not abolish that mathematical distinction.
Strategic models: what game theory contributes
Game theory connects chess to models in economics, decision support and automated calculation where choices respond to other agents.
For a club player, distinguish deterministic rules from uncertainty about another person’s choices. A game can have no random rule and still leave you unsure how the opponent will reply.
Proofs and subproblems. Work on endgames and other restricted settings yields exact results within stated coverage. No proof currently fixes the initial perfect-play outcome of full chess. Naive exhaustive exploration is impractical with current methods.
Decidability and algorithmic complexity address different questions. A finite problem can be theoretically decidable without a practical exhaustive solution. That distinction makes claims about impossibility more precise.
“Hard to solve” does not mean unusable
Chess offers analogies for modern problems such as:
- Computer security: interacting attack and defence.
- Strategy: anticipating another agent.
- Optimisation: deciding where to spend computing effort.
- Decisions when not everything can be examined at once.
The lesson is not that AI is magic. Strong performance comes from how search, evaluation and resources interact, rather than an exhaustive view of every possibility.
For your own play, you can learn to choose what to examine more carefully. This is a practical idea, not evidence that the board reveals your whole personality or that each result measures your worth.
What changes for you as a player
Try it. Open a position in an analysis tool with Stockfish locally or in the browser. Observe depth, score and lines. Changing resources may change a non-proven evaluation; follow the variation rather than treating every number as a theorem.
On the blog:
Chess is beyond current naive full traversal, yet useful decisions are possible through selection, evaluation and pruning. Match strength does not prove complete solution, and a large estimated tree does not exclude every future proof method.
Further reading: chessprogramming.org, ICGA and arXiv.
After reading: in a training review, find the first move where your idea and the engine’s differ by more than half a pawn under stated analysis settings. Revisit that position three times if useful, examining the concrete line. The threshold and repetition count are exercise choices, not a validated universal prescription.
Sources
- Shannon, C. E. (1950), Programming a Computer for Playing Chess, Philosophical Magazine, 41, 256–275, original article: the combinatorial estimate discussed above.
- Fraenkel, A. S. and Lichtenstein, D. (1981), Computing a Perfect Strategy for n×n Chess Requires Time Exponential in n, Journal of Combinatorial Theory, Series A, 31, 199–214, authors’ text.
- Russell, S. and Norvig, P. (undated), Adversarial Search, textbook chapter, text: minimax, alpha-beta and search limits.
- Stockfish team (2020), Introducing NNUE Evaluation, official announcement.
- IBM (undated), Deep Blue, company archives, 1997 match history.
Comments