Computer Endgame Analysis
Writing a strong chess playing program has long been the Holy Grail to many computer scientists. In 1968 Scottish chess champion David Levy made a £500 bet, with leading researcher in artificial intelligence John McCarthy, that a computer would not be able to beat him within 10 years. Although David won this, along with a subsequent bet, by the end of the 1980's computers began to score victories against International Masters in tournaments.
Despite the tactical strength of today's super strong chess engines, one area where computers are still weak is in the endgame. Many endgames require slow and long-winded manoeuvring to gain any kind of an advantage. Today's computers are just not powerful enough to calculate the awesome number of continuations within the time allowed under match conditions. To counter this, chess engines make use of tablebases which store the analysis of millions of positions.
Ken Thompson, creator of Unix and the World champion computer chess program called Belle, has done much computer analysis of the endgame. This research, along with that of others, has led to several new discoveries. It turns out that many theoretical evaluations had been wrong, and winning lines of play were found in positions previously thought to be drawn. In the famous example below, two bishops dominate a knight, and eventually capture it on move 66.
|Mate in 69 - Ken Thompson 1983|
The position above represents the longest possible forced winning line where black puts up the toughest resistance by prolonging the final checkmate. Endgame specialist A. J. Roycroft described the procedure as 'not to be found in any book and characterized by excruciating slowness and mystery'. The following two examples are even more remarkable. The unbelievable sequence of apparently random looking moves leave grandmasters in complete bewilderment. The method is considered to be beyond human comprehension.
|Mate in 255 - Stiller 1991||Mate in 262 - Thompson & Karrer 2000|
By 2006, the analysis of all endgame positions with up to six pieces (including the two kings) was completed. A full analysis of seven piece endgames is expected to be completed by 2015. Unless some radical new method for storing inconceivable amounts af data is discovered, this research will soon hit a brick wall. The idea of a tablebase including all 32 pieces is completely off the Richter Scale.
The moves to the above three endgames can be downloaded in pgn format.