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: Polish Speaking Buying Assistant

    £18000 - £20000 per annum: Recruitment Genius: Superb opportunity for a BUYING...

    Recruitment Genius: Support Worker

    £14560 - £15000 per annum: Recruitment Genius: This company offers personalise...

    Recruitment Genius: Key Account Manager

    Negotiable: Recruitment Genius: A really exciting opportunity has arisen for a...

    Recruitment Genius: Multi Trade Operative

    £22000 - £24000 per annum: Recruitment Genius: An established, family owned de...

    Day In a Page

    Syria crisis: Celebrities call on David Cameron to take more refugees as one young mother tells of torture by Assad regime

    Celebrities call on David Cameron to take more Syrian refugees

    One young mother tells of torture by Assad regime
    The enemy within: People who hear voices in their heads are being encouraged to talk back – with promising results

    The enemy within

    People who hear voices in their heads are being encouraged to talk back
    'In Auschwitz you got used to anything'

    'In Auschwitz you got used to anything'

    Survivors of the Nazi concentration camp remember its horror, 70 years on
    Autumn/winter menswear 2015: The uniforms that make up modern life come to the fore

    Autumn/winter menswear 2015

    The uniforms that make up modern life come to the fore
    'I'm gay, and plan to fight military homophobia'

    'I'm gay, and plan to fight military homophobia'

    Army general planning to come out
    Iraq invasion 2003: The bloody warnings six wise men gave to Tony Blair as he prepared to launch poorly planned campaign

    What the six wise men told Tony Blair

    Months before the invasion of Iraq in 2003, experts sought to warn the PM about his plans. Here, four of them recall that day
    25 years of The Independent on Sunday: The stories, the writers and the changes over the last quarter of a century

    25 years of The Independent on Sunday

    The stories, the writers and the changes over the last quarter of a century
    Homeless Veterans appeal: 'Really caring is a dangerous emotion in this kind of work'

    Homeless Veterans appeal

    As head of The Soldiers' Charity, Martin Rutledge has to temper compassion with realism. He tells Chris Green how his Army career prepared him
    Wu-Tang Clan and The Sexual Objects offer fans a chance to own the only copies of their latest albums

    Smash hit go under the hammer

    It's nice to pick up a new record once in a while, but the purchasers of two latest releases can go a step further - by buying the only copy
    Geeks who rocked the world: Documentary looks back at origins of the computer-games industry

    The geeks who rocked the world

    A new documentary looks back at origins of the computer-games industry
    Belle & Sebastian interview: Stuart Murdoch reveals how the band is taking a new direction

    Belle & Sebastian is taking a new direction

    Twenty years ago, Belle & Sebastian was a fey indie band from Glasgow. It still is – except today, as prime mover Stuart Murdoch admits, it has a global cult following, from Hollywood to South Korea
    America: Land of the free, home of the political dynasty

    America: Land of the free, home of the political dynasty

    These days in the US things are pretty much stuck where they are, both in politics and society at large, says Rupert Cornwell
    A graphic history of US civil rights – in comic book form

    A graphic history of US civil rights – in comic book form

    A veteran of the Fifties campaigns is inspiring a new generation of activists
    Winston Churchill: the enigma of a British hero

    Winston Churchill: the enigma of a British hero

    A C Benson called him 'a horrid little fellow', George Orwell would have shot him, but what a giant he seems now, says DJ Taylor
    Growing mussels: Precious freshwater shellfish are thriving in a unique green project

    Growing mussels

    Precious freshwater shellfish are thriving in a unique green project