Solving chess

Short description: Finding an optimal algorithm for playing chess

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 either a victory or 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]

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.

## Contents

* 1 Partial results
* 1.1 Endgame tablebases
* 1.2 Chess variants
* 2 Complexity of chess
* 3 Predictions on when or if chess will be solved
* 4 See also
* 5 Notes
* 6 References
* 7 External links

## Partial results

### Endgame tablebases

Script error: No such module "Chessboard".

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.Script error: No such module "Chessboard".Script error: No such module "Chessboard".

### 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]

## 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 (Shannon number) possible game variations, or having a "dictionary" denoting an optimal move for each of the approximately 4.8x1044[lower-alpha 1] possible board positions.[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

* Shannon number (a calculation of the lower bound of the game-tree complexity of chess)
* First-move advantage in chess

## Notes

1. ↑ This estimate was published in 2021. Shannon's 1950 estimate of this quantity was 1043.

## References

1. ↑ Allis, V. (1994). "PhD thesis: Searching for Solutions in Games and Artificial Intelligence". Department of Computer Science. University of Limburg. http://www.dphu.org/uploads/attachements/books/books_3721_0.pdf.
2. ↑ "ChessOK: Lomonosov Tablebases". https://tb7.chessok.com/.
3. ↑ "What is the longest known 7-piece checkmate?" (in en). https://chess.stackexchange.com/questions/37240/what-is-the-longest-known-7-piece-checkmate.
4. ↑ "Probe". https://tb7.chessok.com/probe/3/61.
5. ↑ Silver, Albert (2022-05-11). "8-piece endgame tablebases - first findings and interview!" (in en). Chess News. https://en.chessbase.com/post/8-piece-endgame-tablebases-first-findings-and-interview.
6. ↑ 6.0 6.1 6.2 Shannon, C. (March 1950). "Programming a Computer for Playing Chess". Philosophical Magazine. 7 41 (314). http://archive.computerhistory.org/projects/chess/related_materials/text/2-0 and 2-1.Programming_a_computer_for_playing_chess.shannon/2-0 and 2-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf. Retrieved 2008-06-27.
7. ↑ Mhalla, Mehdi; Prost, Frederic (July 26, 2013). "Gardner's Minichess Variant is solved". arXiv:1307.7118 [cs.GT].
8. ↑ Watkins, Mark. "Losing Chess: 1. e3 wins for White". https://magma.maths.usyd.edu.au/~watkins/LOSING_CHESS/LCsolved.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". https://github.com/tromp/ChessPositionRanking.
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. http://www.aeiveos.com/~bradbury/Authors/Computing/Bremermann-HJ/QNaI.html.
13. ↑ 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. Bibcode: 2007Sci...317.1518S.
14. ↑ Sreedhar, Suhas. "Checkers, Solved!". IEEE. http://www.spectrum.ieee.org/print/5379.

## External links

* "Infinite Chess, PBS Infinite Series" Infinite Chess, PBS Infinite Series.

* v
* t
* e

Chess

Outline|

* Chess theory
* Chess titles
* Grandmaster
* list of Grandmasters
* Computer chess
* glossary
* matches
* engines
* software
* Correspondence chess
* FIDE
* Glossary
* History
* timeline
* notable games
* Rating system
* world rankings
* norms
* Variants
* List
* World records

Equipment|

* Chess set
* chessboard
* pieces
* King
* Queen
* Rook
* Bishop
* Knight
* Pawn
* Chess box
* Chess clock
* Chess table
* score sheets

Rules|

* Castling
* Check
* Checkmate
* Draw
* by agreement
* Fifty-move rule
* Perpetual check
* Stalemate
* Threefold repetition
* En passant
* Pawn promotion
* Time control
* Fast chess
* Touch-move rule

Terms|

* Blunder
* Chess notation
* algebraic
* descriptive
* PGN
* annotation symbols
* symbols in Unicode
* Fianchetto
* Gambit
* Key square
* King walk
* Pawns
* backward
* connected
* doubled
* isolated
* Maróczy Bind
* passed
* Open file
* Half-open file
* Outpost
* School
* romantic
* hypermodern
* Swindle
* Tempo
* Transposition
* Trap

Tactics|

* Battery
* Alekhine's gun
* Block
* Checkmate patterns
* Combination
* Decoy
* Deflection
* Desperado
* Discovered attack
* Double check
* Fork
* Interference
* Overloading
* Pin
* Sacrifice
* Skewer
* Undermining
* Windmill
* X-ray
* Zwischenzug

Strategy|

* Artificial castling
* Compensation
* Exchange
* the exchange
* Initiative
* first-move advantage
* Middlegame
* Pawn storm
* Pawn structure
* Piece values
* Prophylaxis

Openings|

| Flank opening|

* English Opening
* Zukertort Opening
* Réti Opening
* King's Indian Attack
* Larsen's Opening
* Bird's Opening
* Grob's Attack
* Dunst Opening
* Benko Opening

|

King's Pawn Game|

* Alekhine's Defence
* Caro–Kann Defence
* French Defence
* Modern Defence
* Nimzowitsch Defence
* Open Game
* Italian Game
* Semi-Italian Opening
* Giuoco Piano
* King's Gambit
* Petrov's Defence
* Philidor Defence
* Ruy Lopez
* Scotch Game
* Owen's Defence
* Pirc Defence
* Scandinavian Defense
* Tennison Gambit
* Sicilian Defence
* Alapin
* Dragon/Accelerated Dragon
* Najdorf
* Scheveningen

Queen's Pawn Game|

* Dutch Defence
* Indian Defence
* Benoni Defence
* Modern Benoni
* Bogo-Indian Defence
* Grünfeld Defence
* King's Indian Defence
* Nimzo-Indian Defence
* Queen's Indian Defence
* Trompowsky Attack
* London System
* Queen's Gambit
* Accepted
* Declined
* Slav Defence
* Catalan Opening

Other|

* List of openings
* theory table
* List of chess gambits
* Irregular
* Fool's mate
* Scholar's mate

Endgames|

* Bishop and knight checkmate
* King and pawn vs king
* Opposite-coloured bishops
* Pawnless endgame
* Queen and pawn vs queen
* Queen vs pawn
* Rook and bishop vs rook
* Rook and pawn vs rook
* Lucena position
* Philidor position
* Strategy
* fortress
* opposition
* Tarrasch rule
* triangulation
* Zugzwang
* Study
* Tablebase
* Two knights endgame
* Wrong bishop
* Wrong rook pawn

Tournaments|

* List of strong chess tournaments
* Chess Olympiad
* Women
* World Chess Championship
* List
* Candidates Tournament
* Chess World Cup
* FIDE Grand Prix
* Other world championships
* Women
* Team
* Rapid
* Blitz
* Junior
* Youth
* Senior
* Amateur
* Chess composition
* Solving
* Computer chess
* Computer speed chess
* Chess engine

Related|

* Cheating in chess
* Chess aesthetics
* Chess in the arts
* in early literature
* Chess books
* opening books
* endgame literature
* Chess boxing
* Chess club
* Chess composer
* Chess in Europe
* Göttingen manuscript
* Chess libraries
* Chess museums
* Chess newspaper columns
* Chess periodicals
* Chess problem
* glossary
* joke chess
* Chess prodigy
* Gökyay Association Chess Museum
* Deep Blue
* Dubrovnik chess set
* Mutilated chessboard problem
* PRO Chess League
* Simultaneous exhibition
* Solving chess
* Staunton chess set
* Top player comparison

* v
* t
* e

Topics in game theory

Definitions|

* Cooperative game
* Determinacy
* Escalation of commitment
* Extensive-form game
* First-player and second-player win
* Game complexity
* Graphical game
* Hierarchy of beliefs
* Information set
* Normal-form game
* Preference
* Sequential game
* Simultaneous game
* Simultaneous action selection
* Solved game
* Succinct game

Equilibrium
concepts|

* Nash equilibrium
* Subgame perfection
* Mertens-stable equilibrium
* Bayesian Nash equilibrium
* Perfect Bayesian equilibrium
* Trembling hand
* Proper equilibrium
* Epsilon-equilibrium
* Correlated equilibrium
* Sequential equilibrium
* Quasi-perfect equilibrium
* Evolutionarily stable strategy
* Risk dominance
* Core
* Shapley value
* Pareto efficiency
* Gibbs equilibrium
* Quantal response equilibrium
* Self-confirming equilibrium
* Strong Nash equilibrium
* Markov perfect equilibrium

Strategies|

* Dominant strategies
* Pure strategy
* Mixed strategy
* Strategy-stealing argument
* Tit for tat
* Grim trigger
* Collusion
* Backward induction
* Forward induction
* Markov strategy

Classes
of games|

* Symmetric game
* Perfect information
* Repeated game
* Signaling game
* Screening game
* Cheap talk
* Zero-sum game
* Mechanism design
* Bargaining problem
* Stochastic game
* n-player game
* Large Poisson game
* Nontransitive game
* Global game
* Strictly determined game
* Potential game

Games|

* Go
* Chess
* Infinite chess
* Checkers
* Tic-tac-toe
* Prisoner's dilemma
* Optional prisoner's dilemma
* Traveler's dilemma
* Coordination game
* Chicken
* Centipede game
* Volunteer's dilemma
* Dollar auction
* Battle of the sexes
* Stag hunt
* Matching pennies
* Ultimatum game
* Rock paper scissors
* Pirate game
* Dictator game
* Public goods game
* Blotto game
* War of attrition
* El Farol Bar problem
* Fair division
* Fair cake-cutting
* Cournot game
* Deadlock
* Diner's dilemma
* Guess 2/3 of the average
* Kuhn poker
* Nash bargaining game
* Prisoners and hats puzzle
* Trust game
* Princess and Monster game
* Rendezvous problem

Theorems|

* Arrow's impossibility theorem
* Aumann's agreement theorem
* Folk theorem
* Minimax theorem
* Nash's theorem
* Purification theorem
* Revelation principle
* Zermelo's theorem

Key
figures|

* Albert W. Tucker
* Amos Tversky
* Ariel Rubinstein
* Claude Shannon
* Daniel Kahneman
* David K. Levine
* David M. Kreps
* Donald B. Gillies
* Drew Fudenberg
* Eric Maskin
* Harold W. Kuhn
* Herbert Simon
* Hervé Moulin
* Jean Tirole
* Jean-François Mertens
* Jennifer Tour Chayes
* John Harsanyi
* John Maynard Smith
* Antoine Augustin Cournot
* John Nash
* John von Neumann
* Kenneth Arrow
* Kenneth Binmore
* Leonid Hurwicz
* Lloyd Shapley
* Melvin Dresher
* Merrill M. Flood
* Olga Bondareva
* Oskar Morgenstern
* Paul Milgrom
* Peyton Young
* Reinhard Selten
* Robert Axelrod
* Robert Aumann
* Robert B. Wilson
* Roger Myerson
* Samuel Bowles
* Suzanne Scotchmer
* Thomas Schelling
* William Vickrey

See also|

* All-pay auction
* Alpha–beta pruning
* Bertrand paradox
* Bounded rationality
* Combinatorial game theory
* Confrontation analysis
* Coopetition
* First-move advantage in chess
* Game mechanics
* Glossary of game theory
* List of game theorists
* List of games in game theory
* No-win situation
* Solving chess
* Topological game
* Tragedy of the commons
* Tyranny of small decisions

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Solving chess. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Solving_chess&oldid=4297139"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template