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

PROMOTED VIDEO
Have you tried new the Independent Digital Edition apps?
Life and Style
ebookNow available in paperback
ebooks
ebookPart of The Independent’s new eBook series The Great Composers
Latest stories from i100
Have you tried new the Independent Digital Edition apps?
Independent Dating
and  

By clicking 'Search' you
are agreeing to our
Terms of Use.

ES Rentals

    iJobs Job Widget
    iJobs General

    Recruitment Genius: Service and Installation Engineer

    £22000 - £28000 per annum: Recruitment Genius: A fantastic opportunity has ari...

    Recruitment Genius: SEO / Outreach Executive

    £20000 - £23000 per annum: Recruitment Genius: Our client is a global marketin...

    Recruitment Genius: Junior Estimator

    £17000 - £18000 per annum: Recruitment Genius: A fantastic opportunity has ari...

    Recruitment Genius: Sales Negotiator - OTE £24,000

    £22000 - £24000 per annum: Recruitment Genius: An enthusiastic individual is r...

    Day In a Page

    A timely reminder of the bloody anniversary we all forgot

    A timely reminder of the bloody anniversary we all forgot

    Who remembers that this week we enter the 150th anniversary year of the end of the American Civil War, asks Robert Fisk
    Homeless Veterans appeal: Former soldiers pay their respects to a friend who also served

    Homeless Veterans appeal

    Former soldiers pay their respects to a friend who also served
    Downfall of Dustin 'Screech' Diamond, the 'Saved By The Bell' star charged with bar stabbing

    Scarred by the bell

    The downfall of the TV star charged with bar stabbing
    Why 2014 was a year of technological let-downs

    Why 2014 was a year of technological let-downs

    Security breaches and overhyped start-ups dominated a year in which very little changed (save the size of your phone)
    Cuba's golf revolution: But will the revolutionary nation take 'bourgeois' game to its heart?

    Will revolutionary Cuba take 'bourgeois' golf to its heart?

    Fidel Castro ridiculed the game – but now investment in leisure resort projects is welcome
    The Locked Room Mysteries: As a new collection of the genre’s best is published, its editor Otto Penzler explains the rules of engagement

    The Locked Room Mysteries

    As a new collection of the genre’s best is published, its editor explains the rules of engagement
    Amy Adams on playing painter Margaret Keane in Tim Burton's Big Eyes

    How I made myself Keane

    Amy Adams hadn’t wanted to take the role of artist Margaret Keane, because she’d had enough of playing victims. But then she had a daughter, and saw the painter in a new light
    Ed Richards: Parting view of Ofcom chief. . . we hate jokes on the disabled

    Parting view of Ofcom chief... we hate jokes on the disabled

    Bad language once got TV viewers irate, inciting calls to broadcasting switchboards. But now there is a worse offender, says retiring head of the media watchdog, Ed Richards
    A look back at fashion in 2014: Wear in review

    Wear in review

    A look back at fashion in 2014
    Ian Herbert: My 10 hopes for sport in 2015. Might just one of them happen?

    Ian Herbert: My 10 hopes for sport in 2015

    Might just one of them happen?
    War with Isis: The West needs more than a White Knight

    The West needs more than a White Knight

    Despite billions spent on weapons, the US has not been able to counter Isis's gruesome tactics, says Patrick Cockburn
    Return to Helmand: Private Davey Graham recalls the day he was shot by the Taliban

    'The day I was shot by the Taliban'

    Private Davey Graham was shot five times during an ambush in 2007 - it was the first, controversial photograph to show the dangers our soldiers faced in Helmand province
    Revealed: the best and worst airlines for delays

    Revealed: the best and worst airlines for delays

    Many flyers are failing to claim compensation to which they are entitled, a new survey has found
    The stories that defined 2014: From the Scottish independence referendum to the Ice Bucket Challenge, our writers voice their opinions

    The stories that defined 2014

    From the Scottish independence referendum to the Ice Bucket Challenge, our writers voice their opinions
    Stoke-on-Trent becomes first British city to be classified as 'disaster resilient' by the United Nations

    Disaster looming? Now you know where to head...

    Which British city has become the first to be awarded special 'resilience' status by the UN?