CHESS

With the enormous strides made in computational power it should come as no surprise that the ‘younger cousin’ of chess, checkers (or draughts) had been solved by computer programs.

It took thirteen years of brute-force computer analysis to examine all 500 billion billion possible board positions before researchers at the University of Alberta in Canada formally announced that they had finally solved the centuries-old game of checkers. Specifically: they had a file which contained full information on every legal position that can arise during the game, and which move, if any, will lead to a win or a draw in that position.

The task of solving checkers was undertaken and completed by Prof. Jonathan Schaeffer, who had been at it for close to twenty years.

“Checkers has a search space of 5x1020, a daunting number,” Schaeffer says. “Almost continuously since 1989 (with a gap in the 1997 to 2001 period), dozens of computers have been working around the clock to solve the game. You’ve got 500 billion billion pieces of hay in your haystack, and you’ve got to find the needles.“

On being asked if chess could be solved by the same means: “I have been asked many times when chess will be solved and I refuse to say anything other than it cannot be done for a very long time unless there is a fundamentally new breakthrough. The computing models that we have today – even if they are a billion times faster -- won’t make a dent in chess. We need something much better. The answer might be quantum computing, but this technology is still in its infancy and remains unproven.”

In the 1992 a checkers program called Chinook was defeated by Marion Tinsley, world champion from 1955–1962 and from 1975–1991. In 1994, Tinsley had to resign in the middle of an even match for health reasons; he died shortly thereafter. The number of legal positions in chess is estimated between 1043 and 1050 legal positions

The supercomputer named Lomonsov has developed seven-man tablebases (thus all the positions that include two kings and five pieces) and its size is about 100 terabytes.

The tablebases of all endgames with up to six pieces are available for free download and take up more than one terabyte (1000 gigabytes!) of storage space. Bourzutschky and Konoval discovered a K+Q+N v K+R+B+N position where mate can be forced after an astonishing of 517 moves!

White, in severe time-pressure, now played 1 Bb3. WAS THIS AN ERROR?