Endgame Tablebase - Background

Background

See also: Computer chess

Physical limitations of computer hardware aside, in principle it is possible to solve any game under the condition that the complete state is known and there is no random chance. Strong solutions, i.e. algorithms that can produce perfect play from any position, are known for some simple games such as Tic Tac Toe (draw with perfect play) and Connect Four (first player wins). Weak solutions exist for somewhat more complex games, such as checkers (with perfect play on both sides the game is known to be a draw, but it is not known for every position created by less-than-perfect play what the perfect next move would be). Other games, such as chess (from the starting position) and Go, have not been solved because their game complexity is too vast for computers to evaluate all possible positions. To reduce the game complexity, researchers have modified these complex games by reducing the size of the board, or the number of pieces, or both.

Computer chess is one of the oldest domains of artificial intelligence, having begun in the early 1930s. Claude Shannon proposed formal criteria for evaluating chess moves in 1949. In 1951, Alan Turing designed a primitive chess playing program, which assigned values for material and mobility; the program "played" chess based on Turing's manual calculations. However, even as competent chess programs began to develop, they exhibited a glaring weakness in playing the endgame. Programmers added specific heuristics for the endgame – for example, the king should move to the center of the board. However, a more comprehensive solution was needed.

In 1965, Richard Bellman proposed the creation of a database to solve chess and checkers endgames using retrograde analysis. Instead of analyzing forward from the position currently on the board, the database would analyze backward from positions where one player was checkmated or stalemated. Thus, a chess computer would no longer need to analyze endgame positions during the game because they were solved beforehand. It would no longer make mistakes because the tablebase always played the best possible move.

In 1970, Thomas Ströhlein published a doctoral thesis with analysis of the following classes of endgame: KQK, KRK, KPK, KQKR, KRKB, and KRKN. In 1977 the KQKR database was used in a match versus Grandmaster Walter Browne.

Ken Thompson and others helped extend tablebases to cover all four- and five-piece endgames, including in particular KBBKN, KQPKQ, and KRPKR. Lewis Stiller published a thesis with research on some six-piece tablebase endgames in 1995.

More recent contributors have included the following people:

  • Eugene Nalimov, after whom the popular Nalimov tablebases are named;
  • Eiko Bleicher, who has adapted the tablebase concept to a program called "Freezer" (see below);
  • Guy Haworth, an academic at the University of Reading, who has published extensively in the ICGA Journal and elsewhere;
  • Marc Bourzutschky and Yakov Konoval, who have collaborated to analyze endgames with seven pieces on the board;
  • Peter Karrer, who constructed a specialized seven-piece tablebase (KQPPKQP) for the endgame of the Kasparov versus The World online match;
  • Vladimir Makhnychev and Victor Zakharov from Moscow State University, who completed 4+3 DTM-tablebases (525 endings including KPPPKPP) in July 2012. The tablebases are named Lomonosov tablebases. The next set of 5+2 DTM-tablebases (350 endings including KPPPPKP) was completed during August 2012. The high speed of generating the tablebases was because of using a supercomputer named Lomonosov (top500). The size of seven-man tablebases is about 100 TB.

The tablebases of all endgames with up to six pieces are available for free download, and may also be queried using web interfaces (see the external links below). Nalimov tablebase requires more than one terabyte of storage space.

Read more about this topic:  Endgame Tablebase

Famous quotes containing the word background:

    I had many problems in my conduct of the office being contrasted with President Kennedy’s conduct in the office, with my manner of dealing with things and his manner, with my accent and his accent, with my background and his background. He was a great public hero, and anything I did that someone didn’t approve of, they would always feel that President Kennedy wouldn’t have done that.
    Lyndon Baines Johnson (1908–1973)

    Pilate with his question “What is truth?” is gladly trotted out these days as an advocate of Christ, so as to arouse the suspicion that everything known and knowable is an illusion and to erect the cross upon that gruesome background of the impossibility of knowledge.
    Friedrich Nietzsche (1844–1900)

    ... every experience in life enriches one’s background and should teach valuable lessons.
    Mary Barnett Gilson (1877–?)