Particularly susceptible to draughts

When computers meet draughts players, the results can be surprisingly exciting, as William Hartston discovered in a new book

One can hardly imagine anything sounding less promising as a holiday read than a book on draughts. Unless it's a book about computer programming. Jonathan Schaeffer's One Jump Ahead (Springer, pounds 25.50) is a book about programming a computer to play draughts, and it is the most gripping and enjoyable games-related book that I have read for a long time.

If you followed the recent encounter between Deep Blue and Kasparov, the basic plot will be familiar: human intelligence battling against machine computational ability. The principal characters will be familiar too: the single-minded obsessive, determined to reach his goal of being the best in the world, and the quiet academic, searching only for truth and understanding. Only this time, the modest academic is the world draughts champion, Marion Tinsley, and his ruthless foe is the man telling the story - and recounting it with a delightful openness and self-deprecating humour.

Before he became professor of computing science at the University of Alberta, Jonathan Schaeffer was a master-strength chessplayer, and he brought the keen competitive spirit of the player into his work in writing computer chess programs. Here is his description of his feelings during a computer chess tournament:

"What's it like to watch your creation compete, without any chance of influencing the outcome? First, I get nervous, which means I make frequent trips to the washroom. As long as the game's outcome is in doubt there is a knot in my stomach ... the observant watcher will see me occasionally chew my nails, a sure sign that I'm nervous. Sometimes my leg will start vibrating up and down uncontrollably. It amazes me how fast a leg can move through unconscious control. I can't consciously move my leg that fast."

After reaching a dead end in his work on computer chess, Schaeffer, by an inspired chance, moved on to draughts. He had never taken the game seriously himself, but it offered a challenge that could not be matched by chess: there was a possibility that draughts could be solved by computer in a way that chess could not. In chess, a programmer might hope to beat the world champion - as the IBM Deep Blue team recently managed - but the prospect of playing perfect chess is not on the menu even of their dreams. The trouble is that chess is simply too huge. With something like 1044 possible chess positions, there is no prospect of any machine ever providing a definite solution to the game by working out every possibility. Draughts has a theoretical maximum of 500,995,484,682,338,672,639 possible positions (a figure, calculated by Joe Culbertson, including a large number of positions that cannot possibly be reached in a real game). That's less than the square root of the number of possible chess positions - a puny figure by comparison.

There was another feature that attracted Schaeffer to the problem of draughts: the mistaken belief among many of his colleagues that the game had been solved by computers long ago. Indeed in 1962 a small sensation was created in the worlds of computing and board games when a program written by Arthur Samuel defeated a strong human draughts player. This result soon became enshrined in the mythology of computing. The loser, Robert Nealey, was upgraded to "former champion of Connecticut" (not, even if it had been true, a state renowned for the quality of play in its draughts championship) and no mention was made of the fact that he had fallen into a well-documented trap. That game, however, promoted the fallacy that computers could play perfect draughts, so later generations of programmers went unquestioningly on to chess, leaving the simpler problem to fade into obscurity.

As Jonathan Schaeffer discovered, however, when he chose computer draughts as his research topic, there was still a good deal of work to do. He was soon able to write a program (which he called Chinook, after the draughty warm winds from the Pacific that affect Calgary in autumn) that could beat himself easily enough, and any other colleagues who strayed near his terminal, but when he began to meet serious draughts players, he increasingly realised that they knew things his machine didn't. And when the machine lost games, it was not so easy putting things right, even when he knew which move had been the fatal mistake:

"Chinook computes for three minutes and comes up with what it considers to be the best move, but it turns out to be a loser. During that time roughly 3 million positions are considered. Are some of the positions evaluated incorrectly? If so, which ones are in error? Is the search result correct? Are we properly eliminating inferior lines? It makes looking for a needle in a haystack seem easy."

With the help of some sympathetic draughts grandmasters, Schaeffer gradually improved his program until it was ready to compete against the very best in the world. And that is when the book becomes even more interesting. For as Schaeffer reveals for the first time, the world of top draughts players is one of the great undiscovered havens of eccentricity and just pure oddness.

One of Chinook's opponents - among the top handful of players in the world - is a man so shy that he will never permit himself to be photographed. He disappeared for 18 years between 1960 and 1978 and was listed as dead in at least one encyclopaedia of draughts. Another world class player is so competitive that he is not above nudging an opponent's man off the board in the slim hope that its absence will not be noticed.

One man, however, towered above all this. When Jonathan Schaeffer first came across a collection of games played by the world champion Marion Tinsley, he assumed it was vanity that had caused the author to include only ten of his losses among thousands of competitive games. Laster he discovered that Tinsley had indeed only lost that number of games in his career. In over 40 years as the best player in the world he lost only three games.

This was the man that Schaeffer knew Chinook had to beat in order to attain his objective. yet when Chinook was set to analyse Tinsley's games, it was hard-pressed to find a single error in any of them. The man seemed to play perfectly. Tinsley was also, as Schaeffer discovered to his surprise when he first met him, utterly charming and supportive, and totally lacking any of the arrogance he had expected in a man who had dominated his chosen field for most of his life.

An account of the first match between Chinook and Tinsley takes up the middle section of the book - not a move-by-move analysis of the games (though all the games are to be found in an appendix) but an account of the fluctuating emotional state of the programmer and the calmness of the human champion. At the start of the match, Tinsley was modestly confident of victory: "because I have a better programmer than Chinook. His was Jonathan, mine was the Lord." A deeply religious man and lay preacher, Tinsley sincerely wanted "not to let my programmer down".

His opponent, however, was close to perfection. Schaeffer's programme had two distinct components. For the endgame, he relied on an ever-growing database of positions which the machine could play perfectly. Any position with six men or fewer, most of those with seven men, and a fair proportion of those with eight, were in its databank and could be played with absolute accuracy.

At the other end of the game, it analysed every possibility to as great a depth as time allowed, pursuing selected lines more deeply than others. Often, even in an apparently complex position, the machine would announce the result with certainty - its analysis of possibilities from the current position joined up with the database of endgames to produce a complete solution to the position.

Yet Tinsley proved that he could see even further. He lost two games but won four to take the match. They played again in 1994, but after six drawn games, Tinsley fell ill and conceded the match. A few months later, he died of stomach cancer.

The latest rankings of the American Checkers Federation list Chinook as the best player in the world, with a rating of 2,814, a massive 182 points ahead of the highest human. At the time of his death, Marion Tinsley's rating was 2,809.

`One Jump Ahead' is available through good bookshops or direct from the publishers (01483-418822).

Chinook is on the Internet at: http://www.cs.ualberta.ca/chinook