Editing Computer chess (section)

== Solving chess ==
{{Main|Solving chess}}
The prospects of completely [[solved game|solving]] chess are generally considered to be rather remote. It is widely conjectured that no computationally inexpensive method to solve chess exists even in the weak sense of determining with certainty the value of the initial position, and hence the idea of solving chess in the stronger sense of obtaining a practically usable description of a strategy for perfect play for either side seems unrealistic today. However, it has not been proven that no computationally cheap way of determining the best move in a chess position exists, nor even that a traditional [[alpha–beta search]]er running on present-day computing hardware could not solve the initial position in an acceptable amount of time. The difficulty in proving the latter lies in the fact that, while the number of board positions that could happen in the course of a chess game is huge (on the order of at least 10<sup>43</sup><ref name="Shannon1950">The size of the state space and game tree for chess were first estimated in {{Citation | author = [[Claude Shannon]] | title = Programming a Computer for Playing Chess | journal = Philosophical Magazine | volume = 41 | issue = 314 | year = 1950 | url = http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | access-date = 30 December 2008 | url-status = dead | archive-url = https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf | archive-date = 6 July 2010 }} Shannon gave estimates of 10<sup>43</sup> and 10<sup>120</sup> respectively, smaller than the estimates in the [[Game complexity]] table, which are from [[Victor Allis]]'s thesis. See [[Shannon number]] for details.</ref> to 10<sup>47</sup>), it is hard to rule out with mathematical certainty the possibility that the initial position allows either side to force a mate or a [[threefold repetition]] after relatively few moves, in which case the search tree might encompass only a very small subset of the set of possible positions. It has been mathematically proven that ''generalized chess'' (chess played with an arbitrarily large number of pieces on an arbitrarily large chessboard) is [[EXPTIME-complete]],<ref>{{Citation |author1=Aviezri Fraenkel |author2=D. Lichtenstein | title = Computing a perfect strategy for n×n chess requires time exponential in n | journal = J. Combin. Theory Ser. A | volume = 31 | year = 1981 | pages = 199–214 | doi = 10.1016/0097-3165(81)90016-9 | issue = 2| doi-access =  }}</ref>  meaning that determining the winning side in an arbitrary position of generalized chess provably takes exponential time in the worst case; however, this theoretical result gives no lower bound on the amount of work required to solve ordinary 8x8 chess.

[[Martin Gardner]]'s [[Minichess]], played on a 5×5 board with approximately 10<sup>18</sup> possible board positions, has been solved; its game-theoretic value is 1/2 (i.e. a draw can be forced by either side), and the forcing strategy to achieve that result has been described.

Progress has also been made from the other side: as of 2012, all 7 and fewer pieces (2 kings and up to 5 other pieces) endgames have been solved.