Editing Computer chess (section)

== Endgame tablebases ==
{{Main|Endgame tablebase}}

Endgame play had long been one of the great weaknesses of chess programs because of the depth of search needed. Some otherwise master-level programs were unable to win in positions where even intermediate human players could force a win.

To solve this problem, computers have been used to analyze some [[chess endgame]] positions completely, starting with [[king (chess)|king]] and [[pawn (chess)|pawn]] against king. Such endgame tablebases are generated in advance using a form of [[retrograde analysis]], starting with positions where the final result is known (e.g., where one side has been mated) and seeing which other positions are one move away from them, then which are one move from those, etc. [[Ken Thompson (computer programmer)|Ken Thompson]] was a pioneer in this area.

The results of the computer analysis sometimes surprised people. In 1977 Thompson's Belle chess machine used the endgame tablebase for a king and [[rook (chess)|rook]] against king and [[queen (chess)|queen]] and was able to draw that theoretically lost ending against several masters (see [[Philidor position#Queen versus rook]]).  This was despite not following the usual strategy to delay defeat by keeping the defending king and rook close together for as long as possible. Asked to explain the reasons behind some of the program's moves, Thompson was unable to do so beyond saying the program's database simply returned the best moves.

Most grandmasters declined to play against the computer in the queen versus rook endgame, but [[Walter Browne]] accepted the challenge.  A queen versus rook position was set up in which the queen can win in thirty moves, with perfect play.  Browne was allowed 2½ hours to play fifty moves, otherwise a draw would be claimed under the [[fifty-move rule]].  After forty-five moves, Browne agreed to a draw, being unable to force checkmate or win the rook within the next five moves. In the final position, Browne was still seventeen moves away from checkmate, but not quite that far away from winning the rook.  Browne studied the endgame, and played the computer again a week later in a different position in which the queen can win in thirty moves.  This time, he captured the rook on the fiftieth move, giving him a winning position.<ref>{{harvp|Levy|Newborn|1991|pp=144–148}}</ref><ref>{{harvp|Nunn|2002|p=49}}</ref>

Other positions, long believed to be won, turned out to take more moves against perfect play to actually win than were allowed by chess's fifty-move rule. As a consequence, for some years the official FIDE rules of chess were changed to extend the number of moves allowed in these endings. After a while, the rule reverted to fifty moves in all positions{{snd}} more such positions were discovered, complicating the rule still further, and it made no difference in human play, as they could not play the positions perfectly.

Over the years, other [[endgame database]] formats have been released including the Edward Tablebase, the De Koning Database and the [[Eugene Nalimov|Nalimov]] Tablebase which is used by many chess programs such as [[Rybka]], [[Shredder (chess)|Shredder]] and [[Fritz (chess)|Fritz]]. Tablebases for all positions with six pieces are available.<ref>{{cite web|author=Kirill Kryukov |url=http://kirill-kryukov.com/chess/tablebases-online/ |title=Endgame Tablebases Online |publisher=Kirill-kryukov.com |access-date=2010-04-03}}</ref> Some seven-piece endgames have been analyzed by Marc Bourzutschky and Yakov Konoval.<ref>{{cite web|url=http://www.xs4all.nl/~timkr/chess2/diary_16.htm |title=Open chess diary 301–320 |publisher=Xs4all.nl |access-date=2010-04-03}}</ref> Programmers using the Lomonosov supercomputers in Moscow have completed a chess tablebase for all endgames with seven pieces or fewer (trivial endgame positions are excluded, such as six white pieces versus a lone black [[king (chess)|king]]).<ref>[http://tb7.chessok.com/shared-positions http://tb7.chessok.com] Lomonosov website allowing registered user to access 7-piece tablebase, and a forum with positions found.</ref><ref>[https://www.chess.com/forum/view/endgames/who-wins-from-this-puzzle "Who wins from this? (chess puzzle)"] An example chess position found from the Lomonosov chess tablebase.</ref> In all of these endgame databases it is assumed that castling is no longer possible.

Many tablebases do not consider the fifty-move rule, under which a game where fifty moves pass without a capture or pawn move can be claimed to be a draw by either player. This results in the tablebase returning results such as "Forced mate in sixty-six moves" in some positions which would actually be drawn because of the fifty-move rule. One reason for this is that if the rules of chess were to be changed once more, giving more time to win such positions, it will not be necessary to regenerate all the tablebases. It is also very easy for the program using the tablebases to notice and take account of this 'feature' and in any case if using an endgame tablebase will choose the move that leads to the quickest win (even if it would fall foul of the fifty-move rule with perfect play). If playing an opponent not using a tablebase, such a choice will give good chances of winning within fifty moves.

The Nalimov tablebases, which use state-of-the-art [[Data compression|compression]] techniques, require 7.05 [[Gigabyte|GB]] of hard disk space for all five-piece endings. To cover all the six-piece endings requires approximately 1.2 [[Terabyte|TB]]. It is estimated that a seven-piece tablebase requires between 50 and 200 [[Terabyte|TB]] of storage space.<ref>The Rybka Lounge / Computer Chess / Tablebase sizes, http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380 {{Webarchive|url=https://web.archive.org/web/20170627041247/http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=9380 |date=2017-06-27 }}, 19th June 2012</ref>

Endgame databases featured prominently in 1999, when Kasparov played an [[Kasparov versus the World|exhibition match on the Internet against the rest of the world]]. A seven piece [[Queen (chess)|Queen]] and [[pawn (chess)|pawn]] endgame was reached with the World Team fighting to salvage a draw. [[Eugene Nalimov]] helped by generating the six piece ending tablebase where both sides had two Queens which was used heavily to aid analysis by both sides.

The most popular endgame tablebase is syzygy which is used by most top computer programs like [[Stockfish (chess)|Stockfish]], [[Leela Chess Zero]], and [[Komodo (chess)|Komodo]]. It is also significantly smaller in size than other formats, with 7-piece tablebases taking only 18.4 TB.<ref>{{cite web |url=https://lichess.org/blog/W3WeMyQAACQAdfAL/7-piece-syzygy-tablebases-are-complete |title=7-piece Syzygy tablebases are complete |website=lichess.org |date=19 August 2018 |access-date=2023-10-02}}</ref>

For a current state-of-the art chess engine like Stockfish, a table base only provides a very minor increase in playing strength (approximately 3 Elo points for syzygy 6men as of Stockfish 15).<ref>{{Cite web |title=Useful data |url=https://github.com/official-stockfish/Stockfish/wiki/Useful-data |access-date=2023-10-12 |website=GitHub }}</ref>