Perfection in checkers

It's Man vs Machine – in Checkers

By Jonathan O'Conner

After reading Jeff Sonas' article on whether computers are getting stronger at chess, and the reactions of the geeks on slashdot, it reminded me of some interesting research in checkers.

For those of you who don't know already, Checkers ("draughts" in Ireland and the UK) is played on 8x8 board, pieces move diagonally forward, one square at a time, and capture by jumping over and enemy piece. If a piece reaches the back rank, it is promoted to a king, which can move backwards as well as forwards. Other versions of the game, such as "Damen" in Germany are more popular in Europe and Russia.

From a mathematical game theory point of view, checkers is a simpler game than chess. There are only 5x10²⁰ positions (5 with 20 zeros after it) in checkers, whereas chess has at least 10⁴⁰ positions. Thus, we have a better chance of completely solving checkers than chess. However, that does not mean that checkers is easier (or harder) to play than chess.

The best player for the last decade has been Chinook, a program developed by Dr. Jonathan Schaeffer. It won the title "Man-Machine World Champion" from Dr. Marion Tinsley, in 1994. Chinook would not be what it is today without Tinsley.

Dr Marion Tinsley

Marion Tinsley was an amalgam of the longevity of Lasker, the invincilibility of Petrosian and the perfection of Fisher. His career is unique in any game or sport. From 1950 to 1995 Tinsley never lost a single tournament, or even shared first place with another player. He took part in nine world championship matches, winning them all, usually by an embarrassingly large margin. In the 45-year period he played in thousands of tournaments, matches and exhibitions, playing many tens of thousands of games. Of these he lost exactly seven games. "Tinsley was as close to perfect as is humanly possible," writes Jonathan Schaeffer.

By 1990, Tinsley had grown bored playing humans and looked for new challenges. He agreed to play Chinook, then the strongest computer player. The ACF (American Checkers Federation) and the EDA (English Draughts Association) had different ideas and refused to allow the match. Tinsley put the cat amongst the pigeons, resigned his title, and signed a contract to play Chinook.

The ACF and the EDA came to their senses and created the "Man-Machine World Championship". This matched the best human against the best computer. Tinsley won the first match in 1992 with 4 wins, 2 losses and 33 draws. The rematch began in 1994 against a much stronger program running on better hardware. After six draws, Tinsley resigned the match on grounds of ill health. He died a year later from cancer.

Dr Jonathan Schaeffer

In 1994, Chinook ran on a 16 processor Silicon Graphics Challenge computer. The processors ran at 150 Mhz (very fast in 1994, very slow in 2003) with 1 GB of RAM. This is equivalent to a 2.4 GHz Pentium that are common enough today, but it was a phenomenal piece of hardware in 1994. The program also had access to eight-piece tablebases for perfect endgame play. The machine searched a minimum of 19 ply.

During their preparations the Chinook team came across one interesting result: "Experiments in Chinook show that there comes a point where increased search depth provides diminishing returns." In particular, Chinook played better checkers with a 19 ply search rather than a 21 or 23 ply search.

So, what does all this mean for chess? Can we extrapolate these results from one checkers playing programs to chess playing programs? Certainly, Chinook and Fritz use similar search algorithms. They each have a positional evaluation function. They each take advantage of table bases for evaluating endgames. The big difference is the number of positions possible in each game: 10²⁰ for checkers and 10⁴⁰ for chess. To get some idea of this, if a computer could solve checkers completely in one nanosecond (a single cycle of a 1 GHz computer), it would take this computer 3000 years to solve chess.

The second difference is the usefulness of tablebases. Chinook has access to eight-piece endings (now ten-pieces). The chess playing programs now commonly use five-piece table bases, and six-piece table bases are starting to be generated. Chinook would regularly be able to decide the outcome of the game by move five, searching 19 ply ahead and looking up the eight-piece ending in its table bases. This does not happen in chess. Even at move 40 this does not happen. However, starting with 16 pieces instead of 12, and accessing five-piece endings instead of eight is too great a difference to overcome in the near future.

Personally, I do think that computers will beat the best humans in a few years, but the reasons given by the geeks in Slashdot are far too simplistic. Jeff Sonas' articles offer the evidence that playing strength is not just a straight correlation with computer processing power.

The Checkers World

While researching this article, I found out lots about the checkers world. If you think that the chess world is messy, well, just have a look at how checkers works. Their world championship matches are paid for with donations from the ordinary members of the public. Checkers is only played in the English speaking world. The alternative 10x10 game is played in Europe and Asia. Have a look at official World Draughts Federation website for more details.

Finally, we all know about the Polgar sisters, but have you ever heard of the Breen sisters from County Louth in Ireland? They are all checkers grandmasters. The eldest, Patricia, is the current ladies world checkers champion. Karena won the 1994 British and Irish Ladies championship. The youngest, Anne-Marie, won the Irish Junior championship in 1993.

The Breen grandmaster sisters: Patricia, Karena and Anne-Marie

Coincidentally, the Ladies World Checkers Championship started on Monday 27 October. Its being held in Cookstown, a small town in Northern Ireland. Patricia defended her title previously against her sister Karena, in 1995. The only comparable situation was Venus and Serena Williams battling it out for Wimbledon Ladies Championship a few years ago.

Coincidentally the Breen sisters come from the same county as the Corr sisters, of music and beauty fame.

Andrea, Caroline and Sharon Corr

Together with older brother Jim the three Corr sisters grew up in Dundalk which is situated in Ireland's beautiful County Louth. The pubs and clubs in Dundalk are known for their live music sessions, and it was in this music environment that the Corrs developed their talents. The band's music has meaning and depth and reflects all that both Ireland and Irish music stand for.

Links

• Marion Tinsley: Human Perfection at Checkers? By Jonathan Schaeffer.

• For more information about Chinook and an opportunity to play the world champion visit the Chinook web site. The academic papers are in postscript form, so you'll need a postscript viewer. I used the shareware RoPS, which you can download here.

• James Propp wrote a wonderful article on the 1994 match between Tinsley and Chinook.

• You can follow the ladies world checkers championship at the "Festival of Draughts" web site.

• The official Corrs web site