Solving chess

src: i.amz.mshcdn.com

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 (see Solved game). It also means more generally solving chess-like games (i.e. combinatorial games of perfect information), such as infinite chess. According to Zermelo's theorem, a hypothetically determinable optimal strategy does 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 of computing power will continue long enough to someday allow for solving it by "brute force", i.e. by checking all possibilities.

Video Solving chess

Partial results

Endgame tablebases have solved chess to a limited degree, determining perfect play in a number of endgames, including all non-trivial endgames with no more than seven pieces or pawns (including the two kings).

One consequence of developing the 7-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.

Such a position is beyond the ability of any human to solve, and indeed no chess engine plays it correctly (unless the engine itself is designed to have access to the tablebase).

Finding positions such as this can make one speculate what other interesting chess situations will be found, as more chess positions are solved. Unfortunately, adding only one single new piece to a chess position expands the complexity of the game-tree by such a vast amount, that the development of an 8-piece endgame tablebase is currently considered an intractable problem.

Maps Solving chess

Predictions on when/if chess will be solved

Grandmaster Jonathan Rowson 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 10¹²⁰ possible game variations, or have a "dictionary" denoting an optimal move for each of the about 10⁴³ possible board positions. It is thus theoretically possible to solve chess, but the time frame required (according to Shannon, 10⁹⁰ years on a 1 MHz processor) puts this possibility beyond the limits of any "feasible" (as of 1950) technology.

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.

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, 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 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".

src: i.amz.mshcdn.com

Larger chess-like games

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.

src: i.ytimg.com

See also

• Shannon number (a calculation of the lower bound of the game-tree complexity of chess)
• First-move advantage in chess (chess-players' speculations on whether white has a slight advantage due to making the first move)

src: i.ytimg.com

References

src: pbs.twimg.com

External links

• The Final Theory of Chess
• "Infinite Chess, PBS Infinite Series" Infinite Chess, PBS Infinite Series.

Source of article : Wikipedia