Solving chess

Last updated

Solving chess consists of finding an optimal strategy for the game of chess; 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). It is also related to more generally solving chess-like games (i.e. combinatorial games of perfect information) such as Capablanca chess and infinite chess. 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]

Contents

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 (if ever). Progress to date is extremely limited; there are tablebases of perfect endgame play with a small number of pieces (up to seven), and some chess 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

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 are computerized databases that contain precalculated exhaustive analyses of 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 endgames, including all non-trivial endgames with no more than seven pieces or pawns (including the two kings). [2]

One consequence of developing the seven-piece endgame tablebase is that many interesting theoretical chess endings have been found. The longest seven-piece example is a mate-in-549 position discovered in the Lomonosov tablebase by Guy Haworth, ignoring the 50-move rule. [3] [4] 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, which initially (in 2014) required 140 TB of storage space and the use of a supercomputer but was later reduced down to 18.4 TB through the Syzygy tablebase. As of January 2023, the longest known forced mating sequence for the eight-piece tablebase (also ignoring the 50-move rule) was 584 moves. This was discovered in mid-2022 by Marc Bourzutschky. [5] The eight-piece tablebase is currently incomplete, though, so it is not guaranteed that this is the absolute limit for the eight-piece tablebase.

Chess variants

A variant first described by Claude 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 that the first player has at least a draw thus: if the first player has a winning move in the initial position, let him play it, else pass. The second player now faces the same situation owing to the mirror symmetry of the initial position: 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. [6]

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. [7] Although losing chess is played on an 8×8 board, its forced capture rule greatly limits its complexity, and a computational analysis managed to weakly solve this variant as a win for White. [8]

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

The complexity of chess

Information theorist Claude Shannon in 1950 outlined a theoretical procedure for playing a perfect game (i.e. solving chess):

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

Shannon then went on to estimate that solving chess according to that procedure would require comparing some 10120 possible game variations, or having a "dictionary" denoting an optimal move for each of the approximately 1043 possible board positions (currently known to be about 5x1044). [6] [10] 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. [6] [11]

Predictions on when or if chess will be solved

In 1950, Shannon calculated, based on a game tree complexity of 10120 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 1090 years to make its first move. Even allowing for technological advances, solving chess within a practical time frame would therefore seem beyond any conceivable 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, 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." [12]

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

See also

Related Research Articles

<span class="mw-page-title-main">Chess</span> Strategy board game

Chess is a board game for two players. It is sometimes called international chess or Western chess to distinguish it from related games such as xiangqi and shogi.

<span class="mw-page-title-main">Checkers</span> Strategy board game

Checkers, also known as draughts, is a group of strategy board games for two players which involve forward movements of uniform game pieces and mandatory captures by jumping over opponent pieces. Checkers is developed from alquerque. The term "checkers" derives from the checkered board which the game is played on, whereas "draughts" 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.

<span class="mw-page-title-main">Computer chess</span> 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. Computer chess applications that play at the level of a chess grandmaster or higher are available on hardware from supercomputers to smart phones. Standalone chess-playing machines are also available. Stockfish, Leela Chess Zero, GNU Chess, Fruit, and other free open source applications are available for various platforms.

The endgame is the final stage of a chess game which occurs after the middlegame. It begins when few pieces are left on the board.

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.

<span class="mw-page-title-main">Evaluation function</span> Function in a computer game-playing program that evaluates a game position

An evaluation function, also known as a heuristic evaluation function or static evaluation function, is a function used by game-playing computer programs to estimate the value or goodness of a position in a game tree. Most of the time, the value is either a real number or a quantized integer, often in nths of the value of a playing piece such as a stone in go or a pawn in chess, where n may be tenths, hundredths or other convenient fraction, but sometimes, the value is an array of three values in the unit interval, representing the win, draw, and loss percentages of the position.

The fifty-move rule in chess states that a player can claim a draw if no capture has been made and no pawn has been moved in the last fifty moves. The purpose of this rule is to prevent a player with no chance of winning from obstinately continuing to play indefinitely or seeking to win by tiring the opponent.

<span class="mw-page-title-main">Combinatorial game theory</span> Branch of game theory about two-player sequential games with perfect information

Combinatorial game theory 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 that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory 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.

Combinatorial game theory measures game complexity in several ways:

  1. State-space complexity,
  2. Game tree size,
  3. Decision complexity,
  4. Game-tree complexity,
  5. Computational complexity.

The two knights endgame is a chess endgame with a king and two knights versus a king. In contrast to a king and two bishops, or a bishop and a knight, a king and two knights cannot force checkmate against a lone king. Although there are checkmate positions, a king and two knights cannot force them against proper, relatively easy defense.

<span class="mw-page-title-main">Endgame tablebase</span> Database of precalculated chess analysis

In chess, the endgame tablebase, or simply tablebase, is a computerised database containing precalculated evaluations of endgame positions. Tablebases are used to analyse finished games, as well as by chess engines to evaluate positions during play. Tablebases are typically exhaustive, covering every legal arrangement of a specific selection of pieces on the board, with both White and Black to move. For each position, the tablebase records the ultimate result of the game and the number of moves required to achieve that result, both assuming perfect play. Because every legal move in a covered position results in another covered position, the tablebase acts as an oracle that always provides the optimal move.

In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to the way its combinatorics depends on input, constraints and bounds. 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.

<span class="mw-page-title-main">Minichess</span> Family of chess variants played on a smaller board

Minichess is a family of chess variants played with regular chess pieces and standard rules, but on a smaller board. The motivation for these variants is to make the game simpler and shorter than standard chess. The first chess-like game implemented on a computer was the 6×6 chess variant Los Alamos chess. The low memory capacity of early computers meant that a reduced board size and a smaller number of pieces were required for the game to be implementable on a computer.

A pawnless chess endgame is a chess endgame in which only a few pieces remain, and no pawns. 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.

<span class="mw-page-title-main">Go and mathematics</span> Calculations of the game complexity 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, an 11th century Chinese scholar, estimated in his Dream Pool Essays that the number of possible board positions is around 10172. In more recent years, research of the game by John H. Conway led to the development of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals being a specific example of its use in Go).

<span class="mw-page-title-main">Anti-computer tactics</span> Human methods against game-playing computers

Anti-computer tactics are methods used by humans to try to beat computer opponents at various games, most typically board games such as chess and Arimaa. They are most associated with competitions against computer AIs that are playing to their utmost to win, rather than AIs merely programmed to be an interesting challenge that can be given intentional weaknesses and quirks by the programmer. Such tactics are most associated with the era when AIs searched a game tree with an evaluation function looking for promising moves, often with Alpha–beta pruning or other minimax algorithms used to narrow the search. Against such algorithms, a common tactic is to play conservatively aiming for a long-term advantage. The theory is that this advantage will manifest slowly enough that the computer is unable to notice in its search, and the computer won't play around the threat correctly. This may result in, for example, a subtle advantage that eventually turns into a winning chess endgame with a passed pawn.

<span class="mw-page-title-main">First-player and second-player win</span>

In combinatorial 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.

The queen and pawn versus queen endgame is a chess endgame in which both sides have a queen and one side has a pawn, which one tries to promote. It is very complicated and difficult to play. Cross-checks are often used as a device to win the game by forcing the exchange of queens. It is almost always a draw if the defending king is in front of the pawn.

<span class="mw-page-title-main">Outline of chess</span> Strategy board game

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

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. ↑ "ChessOK: Lomonosov Tablebases" . Retrieved 2023-12-30.
  3. ↑ "What is the longest known 7-piece checkmate?". Chess Stack Exchange. Retrieved 2023-06-14.
  4. ↑ "Probe". tb7.chessok.com. Retrieved 2023-06-14.
  5. ↑ Silver, Albert (2022-05-11). "8-piece endgame tablebases - first findings and interview!". chessbase.com. Chess News. Retrieved 2023-01-26.
  6. 1 2 3 Shannon, C. (March 1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine . 7. 41 (314). Archived (PDF) from the original on 2010-07-06. Retrieved 2008-06-27.
  7. ↑ Mhalla, Mehdi; Prost, Frederic (2013-07-26). "Gardner's Minichess Variant is solved". arXiv: 1307.7118 [cs.GT].
  8. ↑ Watkins, Mark. "Losing Chess: 1. e3 wins for White" (PDF).
  9. ↑ 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
  10. ↑ John Tromp (2021). "Chess Position Ranking". GitHub .
  11. ↑ http://www.chessgames.com Magnus Carlsen vs Viswanathlan Anand, King's Indian Attack: Double Fianchetto (A07), 1/2-1/2, 16 moves.
  12. ↑ Bremermann, H.J. (1965). "Quantum Noise and Information". Proc. 5th Berkeley Symp. Math. Statistics and Probability. Archived from the original on 2001-05-27.
  13. ↑ Schaeffer, Jonathan; Burch, Neil; Björnsson, Yngvi; et al. (14 September 2007). "Checkers Is Solved". Science . 317 (5844): 1518–1522. Bibcode:2007Sci...317.1518S. doi: 10.1126/science.1144079 . PMID   17641166. S2CID   10274228.(subscription required)
  14. ↑ Sreedhar, Suhas. "Checkers, Solved!". IEEE. Archived from the original on 2009-03-25. Retrieved 2009-03-21.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.