#alternate Edit this page Wikipedia (en)

Solving chess

   From Wikipedia, the free encyclopedia
   Jump to navigation Jump to search
   Finding an optimal strategy for playing chess

   Solving chess means 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 also
   means more generally solving chess-like games (i.e. combinatorial games
   of perfect information), such as Capablanca chess and infinite chess.
   According to Zermelo's theorem, a determinable optimal strategy must
   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).^[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.

   Progress to date is extremely limited; there are tablebases of perfect
   endgame play with a small number of pieces, and several reduced
   chess-like 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 The complexity of chess
     * 3 Predictions on when or if chess will be solved
     * 4 See also
     * 5 References
     * 6 External links

Partial results[edit]

Endgame tablebases[edit]

     a b c d e f g h
   8
   Chessboard480.svg
   a7 black rook
   h7 black knight
   c6 white queen
   f4 black king
   d3 white king
   h2 white knight
   d1 black bishop
   h1 black queen
   8
   7                 7
   6                 6
   5                 5
   4                 4
   3                 3
   2                 2
   1 1
     a b c d e f g h
   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 contains
   precalculated exhaustive analysis 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. 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.

Chess variants[edit]

   A variant first described by 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, let him play it, else pass. The second player now faces
   the same situation owing to the mirror image symmetry of the board: 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.^[4]

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

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

The complexity of chess[edit]

   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 10^120 possible game variations,
   or having a "dictionary" denoting an optimal move for each of the
   approximately 10^43 possible board positions (currently known to be
   about 5x10^44 ^[8]).^[4] 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]^[9]

Predictions on when or if chess will be solved[edit]

   In 1950, Shannon calculated, based on a game tree complexity of 10^120
   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 10^90 years to make its first move. Solving
   chess would therefore seem beyond any possible technology at that time.

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

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

See also[edit]

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

References[edit]

    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. ^ ^a ^b ^c 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.
    5. ^ Mhalla, Mehdi; Prost, Frederic (2013-07-26). "Gardner's Minichess
       Variant is solved". arXiv:1307.7118 [cs.GT].
    6. ^ Watkins, Mark. "Losing Chess: 1. e3 wins for White" (PDF).
    7. ^ 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
    8. ^ John Tromp (2021). "Chess Position Ranking". GitHub.
    9. ^ http://www.chessgames.com Magnus Carlsen vs Viswanathlan Anand,
       King's Indian Attack: Double Fianchetto (A07), 1/2-1/2, 16 moves.
   10. ^ Bremermann, H.J. (1965). "Quantum Noise and Information". Proc.
       5th Berkeley Symp. Math. Statistics and Probability. Archived from
       the original on 2001-05-27.
   11. ^ Schaeffer, Jonathan; Burch, Neil; Bjoernsson, 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)
   12. ^ Sreedhar, Suhas. "Checkers, Solved!". Spectrum.ieee.org. Archived
       from the original on 2009-03-25. Retrieved 2009-03-21.

External links[edit]

     * "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
          + top player comparison
     * Rating system
          + world rankings
          + norms
     * Variants
          + List
     * World records

   Equipment
     * Chess set
          + chessboard
          + Dubrovnik chess set
          + Staunton chess set
     * Chess pieces
          + King
          + Queen
          + Rook
          + Bishop
          + Knight
          + Pawn
          + Fairy
     * Chess clock
     * Chess table
     * Score sheets

   Rules
     * Castling
     * Cheating in chess
     * Check
     * Checkmate
     * Draw
          + by agreement
          + Fifty-move rule
          + Perpetual check
          + Stalemate
          + Threefold repetition
     * En passant
     * Pawn promotion
     * Time control
          + Fast chess
     * Touch-move rule
     * White and Black

   Terms

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

   Tactics

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

   Strategy

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

   Openings

   Flank opening
     * Benko Opening
     * Bird's Opening
     * Dunst Opening
     * English Opening
     * Grob's Attack
     * Larsen's Opening
     * Zukertort Opening
          + King's Indian Attack
          + Reti Opening

   King's Pawn Game
     * Alekhine's Defence
     * Caro-Kann Defence
     * French Defence
     * Modern Defence
     * Nimzowitsch Defence
     * Open Game
          + Four Knights Game
          + Giuoco Piano
          + Italian Game
          + King's Gambit
          + Petrov's Defence
          + Philidor Defence
          + Ponziani Opening
          + Ruy Lopez
          + Semi-Italian Opening
          + Scotch Game
          + Two Knights Defense
          + Vienna Game
     * Owen's Defence
     * Pirc Defence
          + Austrian Attack
     * Scandinavian Defense
          + Tennison Gambit
     * Sicilian Defence
          + Alapin
          + Dragon/Accelerated Dragon
          + Maroczy Bind
          + Najdorf
          + Scheveningen

   Queen's Pawn Game
     * Colle System
     * Dutch Defence
     * English Defence
     * Indian Defence
          + Benoni Defence
          + Modern Benoni
          + Bogo-Indian Defence
          + Catalan Opening
          + Gruenfeld Defence
          + King's Indian Defence
          + Nimzo-Indian Defence
          + Queen's Indian Defence
     * London System
     * Richter-Veresov Attack
     * Queen's Gambit
          + Accepted
          + Declined
          + Slav Defence
          + Semi-Slav Defence
          + Chigorin Defense
     * Torre Attack
     * Trompowsky Attack

   Other
     * List of openings
          + theory table
     * List of chess gambits
     * Irregular
          + Bongcloud Attack
          + 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 championships
          + CCC
          + CSVN
          + North American
          + TCEC
          + WCCC
          + WCSCC

   Art and media

     * Caissa
     * Chess aesthetics
     * Chess in the arts
          + early literature
          + film
          + novels
          + paintings
          + poetry
          + short stories
     * Chess books
          + opening books
          + endgame literature
     * Chess libraries
     * Chess museums
          + Bobby Fischer Center
          + Goekyay Association Chess Museum
          + World Chess Hall of Fame
     * Chess newspaper columns
     * Chess on the Internet
          + List of chess servers
          + PRO Chess League
     * Chess periodicals

   Related

     * Chess boxing
     * Chess club
     * Chess composer
     * Chess problem
          + glossary
          + joke chess
     * Chess prodigy
     * Deep Blue
     * Famous amateurs
     * Geography of chess
          + Chess in Europe
               o Goettingen manuscript
               o Lewis chessmen
     * List of chess players
          + female
     * Women in chess
     * Simultaneous exhibition
     * Solving chess

     * icon  Chess portal
     * Category

     * v
     * t
     * e

   Topics in game theory

   Definitions

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

   Equilibrium
   concepts

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

   Strategies

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

   Classes
   of games

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

   Games

     * Go
     * Chess
     * Infinite chess
     * Checkers
     * Tic-tac-toe
     * Prisoner's dilemma
     * Gift-exchange game
     * Optional prisoner's dilemma
     * Traveler's dilemma
     * Coordination game
     * Chicken
     * Centipede game
     * Lewis signaling 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
     * Induction puzzles
     * 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
     * Antoine Augustin Cournot
     * Ariel Rubinstein
     * Claude Shannon
     * Daniel Kahneman
     * David K. Levine
     * David M. Kreps
     * Donald B. Gillies
     * Drew Fudenberg
     * Eric Maskin
     * Harold W. Kuhn
     * Herbert Simon
     * Herve Moulin
     * John Conway
     * Jean Tirole
     * Jean-Franc,ois Mertens
     * Jennifer Tour Chayes
     * John Harsanyi
     * John Maynard Smith
     * 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

   Miscellaneous

     * All-pay auction
     * Alpha-beta pruning
     * Bertrand paradox
     * Bounded rationality
     * Combinatorial game theory
     * Confrontation analysis
     * Coopetition
     * Evolutionary game theory
     * First-move advantage in chess
     * Game Description Language
     * 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

   Retrieved from
   "https://en.wikipedia.org/w/index.php?title=Solving_chess&oldid=1101311
   383"

   Categories:
     * Chess theory
     * Game theory

   Hidden categories:
     * Pages containing links to subscription-only content
     * Articles with short description
     * Short description matches Wikidata

Navigation menu

Personal tools

     * Not logged in
     * Talk
     * Contributions
     * Create account
     * Log in

Namespaces

     * Article
     * Talk

   [ ] English

Views

     * Read
     * Edit
     * View history

   [ ] More

Search

   ____________________ Search Go

Navigation

     * Main page
     * Contents
     * Current events
     * Random article
     * About Wikipedia
     * Contact us
     * Donate

Contribute

     * Help
     * Learn to edit
     * Community portal
     * Recent changes
     * Upload file

Tools

     * What links here
     * Related changes
     * Upload file
     * Special pages
     * Permanent link
     * Page information
     * Cite this page
     * Wikidata item

Print/export

     * Download as PDF
     * Printable version

Languages

     * a+l+e+r+b+y+tm
     * Espanol
     * Ukrayins'ka
     *

   Edit links

     * This page was last edited on 30 July 2022, at 10:05 (UTC).
     * Text is available under the Creative Commons Attribution-ShareAlike
       License 3.0; additional terms may apply. By using this site, you
       agree to the Terms of Use and Privacy Policy. Wikipedia(R) is a
       registered trademark of the Wikimedia Foundation, Inc., a
       non-profit organization.

     * Privacy policy
     * About Wikipedia
     * Disclaimers
     * Contact Wikipedia
     * Mobile view
     * Developers
     * Statistics
     * Cookie statement

     * Wikimedia Foundation
     * Powered by MediaWiki