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

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
  • Get to the point
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: Senior Digital Marketing Consultant

    £28000 - £45000 per annum: Recruitment Genius: A Senior Digital Marketing Cons...

    Recruitment Genius: Assistant Stores Keeper

    £16640 - £18500 per annum: Recruitment Genius: An Assistant Stores Keeper is r...

    Recruitment Genius: Claims Administrator

    £16000 - £18500 per annum: Recruitment Genius: This is an excellent opportunit...

    Recruitment Genius: Software Developer - C# / ASP.NET / SQL

    £17000 - £30000 per annum: Recruitment Genius: Developer required to join a bu...

    Day In a Page

    'It was first time I had ever tasted chocolate. I kept a piece, and when Amsterdam was liberated, I gave it to the first Allied soldier I saw'

    Bread from heaven

    Dutch survivors thank RAF for World War II drop that saved millions
    Britain will be 'run for the wealthy and powerful' if Tories retain power - Labour

    How 'the Axe' helped Labour

    UK will be 'run for the wealthy and powerful' if Tories retain power
    Rare and exclusive video shows the horrific price paid by activists for challenging the rule of jihadist extremists in Syria

    The price to be paid for challenging the rule of extremists

    A revolution now 'consuming its own children'
    Welcome to the world of Megagames

    Welcome to the world of Megagames

    300 players take part in Watch the Skies! board game in London
    'Nymphomaniac' actress reveals what it was really like to star in one of the most explicit films ever

    Charlotte Gainsbourg on 'Nymphomaniac'

    Starring in one of the most explicit films ever
    Robert Fisk in Abu Dhabi: The Emirates' out-of-sight migrant workers helping to build the dream projects of its rulers

    Robert Fisk in Abu Dhabi

    The Emirates' out-of-sight migrant workers helping to build the dream projects of its rulers
    Vince Cable interview: Charging fees for employment tribunals was 'a very bad move'

    Vince Cable exclusive interview

    Charging fees for employment tribunals was 'a very bad move'
    Iwan Rheon interview: Game of Thrones star returns to his Welsh roots to record debut album

    Iwan Rheon is returning to his Welsh roots

    Rheon is best known for his role as the Bastard of Bolton. It's gruelling playing a sadistic torturer, he tells Craig McLean, but it hasn't stopped him recording an album of Welsh psychedelia
    Russell Brand's interview with Ed Miliband has got everyone talking about The Trews

    Everyone is talking about The Trews

    Russell Brand's 'true news' videos attract millions of viewers. But today's 'Milibrand' interview introduced his resolutely amateurish style to a whole new crowd
    Morne Hardenberg interview: Cameraman for BBC's upcoming show Shark on filming the ocean's most dangerous predator

    It's time for my close-up

    Meet the man who films great whites for a living
    Increasing numbers of homeless people in America keep their mobile phones on the streets

    Homeless people keep mobile phones

    A homeless person with a smartphone is a common sight in the US. And that's creating a network where the 'hobo' community can share information - and fight stigma - like never before
    'Queer saint' Peter Watson left his mark on British culture by bankrolling artworld giants

    'Queer saint' who bankrolled artworld giants

    British culture owes a huge debt to Peter Watson, says Michael Prodger
    Pushkin Prizes: Unusual exchange programme aims to bring countries together through culture

    Pushkin Prizes brings countries together

    Ten Scottish schoolchildren and their Russian peers attended a creative writing workshop in the Highlands this week
    14 best kids' hoodies

    14 best kids' hoodies

    Don't get caught out by that wind on the beach. Zip them up in a lightweight top to see them through summer to autumn
    Robert Fisk in Abu Dhabi: The acceptable face of the Emirates

    The acceptable face of the Emirates

    Has Abu Dhabi found a way to blend petrodollars with principles, asks Robert Fisk