First-move Advantage in Chess - Solving Chess

Solving Chess

Endgame tablebases have solved a very limited area of chess, 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 all seven-piece endgames will be solved by the end of 2015.

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 argued that it is not feasible for any computer to actually do this. In his 1950 paper "Programming a Computer for Playing Chess" he writes:

With chess it is possible, in principle, to play a perfect game or construct a machine to do so as follows: One considers in a given position all possible moves, then all moves for the opponent, etc., to the end of the game (in each variation). The end must occur, by the rules of the games after a finite number of moves (remembering the 50 move drawing rule). Each of these variations ends in win, loss or draw. By working backward from the end one can determine whether there is a forced win, the position is a draw or is lost. It is easy to show, however, even with the high computing speed available in electronic calculators this computation is impractical. In typical chess positions there will be of the order of 30 legal moves. The number holds fairly constant until the game is nearly finished as shown ... by De Groot, who averaged the number of legal moves in a large number of master games. Thus a move for White and then one for Black gives about 103 possibilities. A typical game lasts about 40 moves to resignation of one party. This is conservative for our calculation since the machine would calculate out to checkmate, not resignation. However, even at this figure there will be 10120 variations to be calculated from the initial position. A machine operating at the rate of one variation per microsecond would require over 1090 years to calculate the first move!

It is thus theoretically possible to "solve" chess, determining with certainty whether a perfectly played game should end in a win for White, a draw, or even a win for Black. However, according to Shannon the time frame required puts this possibility beyond the limits of any feasible 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 certain 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 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".