Solving chess
Encyclopedia
Solving chess means finding an optimal strategy for playing chess
, i.e. one by which one of the players (White or Black) can always force a victory, or both can force a draw.
In a weaker sense, solving chess may refer to a proof which 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 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
of computing power will continue long enough to someday allow for solving it by "brute force", i.e. by checking all possibilities.
s have solved chess to a limited degree, determining perfect play in a number of endgames, including all non-trivial endgames with no more than six pieces or pawns (including the two kings). It is probable that seven-piece endgames will be solved by the end of 2015.
has speculated that "in principle it should be possible for a machine to ... develop 32-piece tablebases. This may take decades or even centuries, but unless runaway global warming
or nuclear war
gets in the way, I think it will eventually happen."
However, information theorist
Claude Shannon has argued that it is not feasible for any computer to actually do this, since it would either need to compare some 10120 possible game variations, or have a "dictionary" denoting an optimal move for each of the about 1043 possible board positions.
It is thus theoretically possible to solve
chess, but the time frame required (according to Shannon, 1090 years on a 1 MHz processor) puts this possibility beyond the limits of any "feasible" (as of 1950) technology.
Hans-Joachim Bremermann
, a professor of mathematics
and biophysics
at the University of California at Berkeley, 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 [of chess] 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 that assessment. The game of checkers was 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". Assuming computational power continues to increase exponentially, chess would be solved "before 2250".
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
, i.e. one by which one of the players (White or Black) can always force a victory, or both can force a draw.
In a weaker sense, solving chess may refer to a proof which 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 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
Moore's Law
Moore's law describes a long-term trend in the history of computing hardware: the number of transistors that can be placed inexpensively on an integrated circuit doubles approximately every two years....
of computing power will continue long enough to someday allow for solving it by "brute force", i.e. by checking all possibilities.
Partial results
Endgame tablebaseEndgame tablebase
An endgame tablebase is a computerized database that contains precalculated exhaustive analysis of a chess endgame position. It is typically used by a computer chess engine during play, or by a human or computer that is retrospectively analysing a game that has already been played.The tablebase...
s have solved chess to a limited degree, determining perfect play in a number of endgames, including all non-trivial endgames with no more than six pieces or pawns (including the two kings). It is probable that seven-piece endgames will be solved by the end of 2015.
Predictions on when/if chess will be solved
Grandmaster Jonathan RowsonJonathan Rowson
Jonathan Rowson is Scotland's third chess Grandmaster, after Paul Motwani and Colin McNab, and has played first board at recent Chess Olympiads. He is also a chess author.-Career:...
has speculated that "in principle it should be possible for a machine to ... develop 32-piece tablebases. This may take decades or even centuries, but unless runaway global warming
Global warming
Global warming refers to the rising average temperature of Earth's atmosphere and oceans and its projected continuation. In the last 100 years, Earth's average surface temperature increased by about with about two thirds of the increase occurring over just the last three decades...
or nuclear war
Nuclear warfare
Nuclear warfare, or atomic warfare, is a military conflict or political strategy in which nuclear weaponry is detonated on an opponent. Compared to conventional warfare, nuclear warfare can be vastly more destructive in range and extent of damage...
gets in the way, I think it will eventually happen."
However, information theorist
Information theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
Claude Shannon has argued that it is not feasible for any computer to actually do this, since it would either need to compare some 10120 possible game variations, or have a "dictionary" denoting an optimal move for each of the about 1043 possible board positions.
It is thus theoretically possible to solve
Solved game
A solved game is a game whose outcome can be correctly predicted from any position when each side plays optimally. Games which have not been solved are said to be "unsolved"...
chess, but the time frame required (according to Shannon, 1090 years on a 1 MHz processor) puts this possibility beyond the limits of any "feasible" (as of 1950) technology.
Hans-Joachim Bremermann
Hans-Joachim Bremermann
Hans-Joachim Bremermann was a German-American mathematician and biophysicist. He worked on computer science and evolution, introducing new ideas of how mating generates new gene combinations...
, a professor of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and biophysics
Biophysics
Biophysics is an interdisciplinary science that uses the methods of physical science to study biological systems. Studies included under the branches of biophysics span all levels of biological organization, from the molecular scale to whole organisms and ecosystems...
at the University of California at Berkeley, 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
Speed of light
The speed of light in vacuum, usually denoted by c, is a physical constant important in many areas of physics. Its value is 299,792,458 metres per second, a figure that is exact since the length of the metre is defined from this constant and the international standard for time...
, 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 [of chess] 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 that assessment. The game of checkers was solved in 2007, but it has roughly the square root of the number of positions in chess. Jonathan Schaeffer
Jonathan Schaeffer
Jonathan Herbert Schaeffer is a Canadian researcher and professor at the University of Alberta and the Canada Research Chair in Artificial Intelligence....
, 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". Assuming computational power continues to increase exponentially, chess would be solved "before 2250".