Solving chess means finding an optimal strategy for the game of

chess Chess is a board game for two players, called White and Black, each controlling an army of chess pieces in their color, with the objective to checkmate the opponent's king. It is sometimes called international chess or Western chess to dist ...

, that is, one by which one of the players ( White or Black) can always force a victory, or either can force a draw (see

solved game A solved game is a game whose outcome (win, lose or draw) can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full inform ...

). It also means more generally solving ''chess-like'' games (i.e. combinatorial games of perfect information), such as

Capablanca chess Capablanca chess (or Capablanca's chess) is a chess variant invented in the 1920s by World Chess Champion José Raúl Capablanca. It incorporates two new pieces and is played on a 10×8 board. Capablanca believed that chess would be played out i ...

and infinite chess. According to Zermelo's theorem, a determinable optimal strategy must exist for chess and chess-like games. In a weaker sense, ''solving chess'' may refer to proving which one of the three possible outcomes (White wins; Black wins; draw) is the result of two perfect players, without necessarily revealing the optimal strategy itself (see indirect proof). No complete solution for chess in either of the two senses is known, nor is it expected that chess will be solved in the near future. There is disagreement on whether the current

exponential growth Exponential growth is a process that increases quantity over time. It occurs when the instantaneous rate of change (that is, the derivative) of a quantity with respect to time is proportional to the quantity itself. Described as a function, a ...

of computing power will continue long enough to someday allow for solving it by " brute force", i.e. by checking all possibilities. Progress to date is extremely limited; there are tablebases of perfect endgame play with a small number of pieces, and several reduced chess-like variants have been solved at least weakly. Calculated estimates of game tree complexity and state-space complexity of chess exist which provide a bird's eye view of the computational effort that might be required to solve the game.

Partial results

Endgame tablebases

Endgame tablebase An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of chess endgame positions. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysin ...

s are computerized databases that contains precalculated exhaustive analysis positions with small numbers of pieces remaining on the board. Tablebases have solved chess to a limited degree, determining perfect play in a number of

endgame Endgame, Endgames, End Game, End Games, or similar variations may refer to: Film * ''The End of the Game'' (1919 film) * ''The End of the Game'' (1975 film), short documentary U.S. film * ''Endgame'' (1983 film), 1983 Italian post-apocalyptic f ...

s, including all non-trivial endgames with no more than seven pieces or pawns (including the two kings). One consequence of developing the seven-piece endgame tablebase is that many interesting theoretical chess endings have been found. One example is a "mate-in-546" position, which with perfect play is a forced checkmate in 546 moves, ignoring the 50-move rule. Such a position is beyond the ability of any human to solve, and no chess engine plays it correctly, either, without access to the tablebase.

Chess variants

A variant first described by Shannon provides an argument about the game-theoretic value of chess: he proposes allowing the move of “pass”. In this variant, it is provable with a

strategy stealing argument In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game ...

that the first player has at least a draw thus: if the first player has a winning move, let him play it, else pass. The second player now faces the same situation owing to the mirror image symmetry of the board: if the first player had no winning move in the first instance, the second player has none now. Therefore the second player can at best draw, and the first player can at least draw, so a perfect game results in the first player winning or drawing. Some chess variants which are simpler than chess have been solved. A winning strategy for black in Maharajah and the Sepoys can be easily memorised. The 5×5 Gardner's Minichess variant has been weakly solved as a draw. Although Losing chess is played on an 8x8 board, its forced capture rule greatly limits its complexity and a computational analysis managed to weakly solve this variant as a win for white. The prospect of solving individual, specific, chess-like games becomes more difficult as the board-size is increased, such as in large chess variants, and infinite chess.

The complexity of chess

Information theorist Information theory is the scientific study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. ...

Claude Shannon Claude Elwood Shannon (April 30, 1916 – February 24, 2001) was an American mathematician, electrical engineer, and cryptographer known as a "father of information theory". As a 21-year-old master's degree student at the Massachusetts Inst ...

in 1950 outlined a theoretical procedure for playing a perfect game (i.e. solving chess): Shannon then went on to estimate that solving chess according to that procedure would require comparing some 10 possible game variations, or having a "dictionary" denoting an optimal move for each of the approximately 10 possible board positions (currently known to be about 5x10 ). The number of mathematical operations required to solve chess, however, may be significantly different than the number of operations required to produce the entire game-tree of chess. In particular, if White has a forced win, only a subset of the game-tree would require evaluation to confirm that a forced-win exists (i.e. with no refutations from Black). Furthermore, Shannon's calculation for the complexity of chess assumes an average game length of 40 moves, but there is no mathematical basis to say that a forced win by either side would have any relation to this game length. Indeed, some expertly played games (grandmaster-level play) have been as short as 16 moves. For these reasons, mathematicians and game theorists have been reluctant to categorically state that solving chess is an intractable problem.

Predictions on when or if chess will be solved

In 1950, Shannon calculated, based on a game tree complexity of 10 and a computer operating at one megahertz (a big stretch at that time: the UNIVAC 1 introduced in 1951 could perform ~2000 operations per second or 2 kilohertz) that could evaluate a terminal node in 1 microsecond would take 10 years to make its first move. Solving chess would therefore seem beyond any possible technology at that time.

Hans-Joachim Bremermann Hans-Joachim Bremermann (1926–1996) was a German-American mathematician and biophysicist. He worked on computer science and evolution, introducing ideas of how mating generates new gene combinations. Bremermann's limit, named after him, is the m ...

, a professor of mathematics and

biophysics Biophysics is an interdisciplinary science that applies approaches and methods traditionally used in physics to study biological phenomena. Biophysics covers all scales of biological organization, from molecular to organismic and populations. ...

at the

University of California at Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant uni ...

, further argued in a 1965 paper that the "speed, memory, and processing capacity of any possible future computer equipment are limited by specific physical barriers: the '' light barrier'', the ''quantum barrier'', and the ''thermodynamical barrier''. These limitations imply, for example, that no computer, however constructed, will ever be able to examine the entire tree of possible move sequences of the game of chess." Nonetheless, Bremermann did not foreclose the possibility that a computer would someday be able to solve chess. He wrote, "In order to have a computer play a perfect or nearly perfect game, it will be necessary either to analyze the game completely ... or to analyze the game in an approximate way and combine this with a limited amount of tree searching. ... A theoretical understanding of such heuristic programming, however, is still very much wanting." Recent scientific advances have not significantly changed these assessments. The game of

checkers Checkers (American English), also known as draughts (; British English), is a group of strategy board games for two players which involve diagonal moves of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers ...

was (weakly) solved in 2007, but it has roughly the square root of the number of positions in chess. Jonathan Schaeffer, the scientist who led the effort, said a breakthrough such as quantum computing would be needed before solving chess could even be attempted, but he does not rule out the possibility, saying that the one thing he learned from his 16-year effort of solving checkers "is to never underestimate the advances in technology".

References

External links

"Infinite Chess, PBS Infinite Series"
Infinite Chess, PBS Infinite Series. {{Game theory, state=collapsed Chess theory Game theory