Solving chess

Last updated

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.

Contents

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). [1]

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.

Partial results

abcdefgh
8
Chessboard480.svg
Chess rdt45.svg
Chess ndt45.svg
Chess qlt45.svg
Chess kdt45.svg
Chess klt45.svg
Chess nlt45.svg
Chess bdt45.svg
Chess qdt45.svg
8
77
66
55
44
33
22
11
abcdefgh
A mate-in-546 position found in the Lomonosov 7-piece tablebase. White to move. (In this example an 8th piece is added with a trivial first-move capture.)

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). [2]

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, ignoring the 50-move rule. [3] 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.

Predictions on when/if chess will be solved

Information theorist Claude Shannon argued in 1951 that it is not feasible for any computer to actually solve chess, 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. [4] It is thus theoretically possible to solve chess, but the time frame required (according to Shannon, 1090 years) puts this possibility beyond the limits of any feasible 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. [4] [5]

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." [6]

Recent scientific advances have not significantly changed these assessments. The game of checkers was (weakly) solved in 2007, [7] 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". [8]

Chess variants

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. [9] 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. [10]

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. [11]

See also

Related Research Articles

Chess Strategy board game

Chess is a two-player strategy board game played on a checkered board with 64 squares arranged in an 8×8 grid. Played by millions of people worldwide, chess is believed to be derived from the Indian game chaturanga sometime before the 7th century. Chaturanga is also the likely ancestor of the East Asian strategy games xiangqi, janggi, and shogi. Chess reached Europe via Persia and Arabia by the 9th century, due to the Umayyad conquest of Hispania. The pieces assumed their current properties in Spain in the late 15th century, and the modern rules were standardized in the 19th century.

Draughts board game

Draughts or checkers 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. Draughts developed from alquerque. The name derives from the verb to draw or to move.

A solved game is a game whose outcome 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 information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.

Computer chess computer hardware and software capable of playing chess

Computer chess includes both hardware and software capable of playing chess. Computer chess provides opportunities for players to practice even in the absence of human opponents, and also provides opportunities for analysis, entertainment and training.

In chess and chess-like games, the endgame is the stage of the game when few pieces are left on the board.

Losing chess chess variant: goal is to lose pieces

Losing chess is one of the most popular chess variants. The objective of each player is to lose all of their pieces or be stalemated, that is, a misère version. In some variations, a player may also win by checkmating or by being checkmated.

Combinatorial game theory branch of game theory about two-player sequential games with perfect information

Combinatorial game theory (CGT) is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

Connect Four connection board game for two players

Connect Four is a two-player connection board game, in which the players choose a color and then take turns dropping colored discs into a seven-column, six-row vertically suspended grid. The pieces fall straight down, occupying the lowest available space within the column. The objective of the game is to be the first to form a horizontal, vertical, or diagonal line of four of one's own discs. Connect Four is a solved game. The first player can always win by playing the right moves.

Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.

Chess engine program that analyses chess positions and makes decisions on the best chess moves

In computer chess, a chess engine is a computer program that analyzes chess or chess variant positions, and generates a move or list of moves that it regards as strongest. A chess engine is usually a back end with a command-line interface with no graphics or windowing. Engines are usually used with a front end, a windowed graphical user interface such as Chessbase or WinBoard that the user can interact with via a keyboard, mouse or touchscreen. This allows the user to play against multiple engines without learning a new user interface for each, and allows different engines to play against each other. Over the last years, there are chess engines available for mobile phones and tablets, which makes their usage easier. The list includes chess engines like Stockfish, Komodo, Texel, Bagatur and many others.

Endgame tablebase a database of precalculated analysis of chess endgame positions

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 analysing a game that has already been played.

Shannon number lower bound on the game-tree complexity for chess

The Shannon number, named after the American mathematician Claude Shannon, is a conservative lower bound (not an estimate) of the game-tree complexity of chess of 10120, based on an average of about 103 possibilities for a pair of moves consisting of a move for White followed by one for Black, and a typical game lasting about 40 such pairs of moves.

In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used to justify the intractability of certain problems. Examples of such problems include certain mathematical functions, the analysis of some puzzles and games, and some pathological examples which can be modelled as the Ackermann function.

A pawnless chess endgame is a chess endgame in which only a few pieces remain and none of them is a pawn. The basic checkmates are types of pawnless endgames. Endgames without pawns do not occur very often in practice except for the basic checkmates of king and queen versus king, king and rook versus king, and queen versus rook. Other cases that occur occasionally are (1) a rook and minor piece versus a rook and (2) a rook versus a minor piece, especially if the minor piece is a bishop.

Go and mathematics Mathematical studies about the game of go

The game of Go is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for mathematical research. Shen Kuo, a Chinese scholar in 11th century, estimated that the number of possible board positions is around 10172 in The Dream Pool Essays. In more recent years, research of the game by John H. Conway led to the invention of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).

First-player and second-player win

In game theory, a two-player deterministic perfect information turn-based game is a first-player-win if with perfect play the first player to move can always force a win. Similarly, a game is second-player-win if with perfect play the second player to move can always force a win. With perfect play, if neither side can force a win, the game is a draw.

Outline of chess Overview of and topical guide to chess

The following outline is provided as an overview of and topical guide to chess:

Infinite chess Variation of chess

Infinite chess is any variation of the game of chess played on an unbounded chessboard. Versions of infinite chess have been introduced independently by multiple players, chess theorists, and mathematicians, both as a playable game and as a model for theoretical study. It has been found that even though the board is unbounded, there are ways in which a player can win the game in a finite number of moves.

References

  1. Allis, V. (1994). "PhD thesis: Searching for Solutions in Games and Artificial Intelligence" (PDF). Department of Computer Science. University of Limburg . Retrieved 2012-07-14.
  2. "Lomonosov Tablebases" . Retrieved 2013-04-24.
  3. "Who wins from this puzzle?" A mate-in-546 chess position, with discussion (Post 1: Position, Post 7: Playable).
  4. 1 2 Shannon, C. (March 1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine . 7. 41 (314). Archived (PDF) from the original on 2010-03-15. Retrieved 2008-06-27.
    "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 micro-second would require over 1090 years to calculate the first move!"
  5. http://www.chessgames.com Magnus Carlsen vs Viswanathlan Anand, King's Indian Attack: Double Fianchetto (A07), 1/2-1/2, 16 moves.
  6. Bremermann, H.J. (1965). "Quantum Noise and Information". Proc. 5th Berkeley Symp. Math. Statistics and Probability. Archived from the original on 2001-05-27.
  7. Schaeffer, Jonathan; Burch, Neil; Björnsson, Yngvi; et al. (14 September 2007). "Checkers Is Solved". Science . 317 (5844): 1518–1522. doi:10.1126/science.1144079. PMID   17641166.(subscription required)
  8. Sreedhar, Suhas. "Checkers, Solved!". Spectrum.ieee.org. Archived from the original on 2009-03-25. Retrieved 2009-03-21.
  9. Mhalla, Mehdi; Prost, Frederic (2013-07-26). "Gardner's Minichess Variant is solved". arXiv: 1307.7118 [cs.GT].
  10. Watkins, Mark. "Losing Chess: 1. e3 wins for White" (PDF).
  11. Aviezri Fraenkel; D. Lichtenstein (1981), "Computing a perfect strategy for n×n chess requires time exponential in n", J. Combin. Theory Ser. A, 31 (2): 199–214, doi:10.1016/0097-3165(81)90016-9