A brief history of computer checkers
I wrote my first checkers program in 1996. The inspiration for it was that I had read about the
Tinsley-Chinook matches, so in a way, my program wouldn't exist if there hadn't been programs
before. This page attempts to give an overview of who did what and when, in computer checkers - without
being either complete or accurate! I hope to expand this article with time, for the moment it's really very
brief!
Before Checkers
When the first computers were developed during the second world war, the first would-be game programmer
was Alan Turing. Turing is famous for many reasons in the field of computer science. Both during and after the war,
Turing experimented with machine routines for playing chess. In the absence of a computer to run his heuristic chess program,
Turing simulated the operation of the program by hand, using paper and pencil. Needless to say, the program was very bad.
Nevertheless, this was the first time that somebody had succeeded in using a set of well-defined rules to play a game like chess.
Much more about Alan Turing.
Samuel's Checkers Program
A little later, in 1952, Arthur L. Samuel wrote a checkers program. The principal focus of his work was however not
a game-playing program, but rather a learning program. A few years later, Samuel had incorporated both rote learning and a form of genetic
evaluation feature learning in his program. By playing two copies of his program against each other, he eliminated the weaker program,
and produced a new second copy. The repetition of this process produced a stronger program. Samuel's work on checkers
if famous, and it seems that he managed to create the impression (I'm not sure if that was intentional!) that his program was
a master-level player. In a famous game, Samuel's program beat one Robert Nealey, a blind checkers master from Connecticut. You
can replay the game. It turned out however, that Nealey was not half as good as was claimed,
and Samuel's program lost 8 games in a row in 1966 against Walter Hellman and Derek Oldbury.
Of course, at Samuel's time, computers were much slower than they are today, and his program was a milestone in computer checkers
history- not only that, it was also a milestone in artificial intelligence. His program was probably the first which could improve itself
without human intervention. More about Arthur Samuel.
The Duke program
In the 70's some people at Duke university wrote a checkers program - Eric Jensen, Tom Truscott and Alan Bierman. Their program
beat Samuel's program in a 2-game match, and went on to lose against grandmaster Elbert Lowder in a 5-game match with 2 losses,
2 draws and a win. However, Lowder played carelessly and should have won the game he lost. Still, the authors of the program were
inspired to challenge the world champion, Marion Tinsley. However, the match never happened, and the program was retired.
Chinook
In 1989 Jonathan Schaeffer started out with what would become the world's most famous computer checkers program, to this date.
He had been working on computer chess, but decided to switch to computer checkers. He got a team of people to work with him on
Chinook: Norman Treolar was the team's checkers expert, and responsible for the evaluation function and the opening book, Robert
Lake was in charge of the endgame databases, later on, Martin Bryant supplied a very big and very good opening book for Chinook.
A lot of graduate students were also involved. Of course, computers were faster now, so even the older programs would have been
more powerful at that time. However, Chinook introduced something new to the field of computer checkers: endgame databases. The
method of retrograde analysis had long been known - pioneering work on the subject was done by Ströhlein; Ken Thompson used
it for chess endgame databases. The Chinook team produced databases which gave the computer perfect knowledge for all positions
with 8 pieces or less on the board of the form win/loss/draw. Up to that time, chess endgame databases were being computed as
distance-to-win databases, i.e. for every position, there was an associated distance to mate. Like this, you do not need to search
once you are in the database. The win/loss/draw scheme is interesting, because it has to store less information and therefore you
can compress these databases much more. This is important if you want to access the database during the search. The 8-piece
database turned out to be about 6GB in compressed form. As far as I know, the Chinook endgame database was the largest
endgame database ever computed at that time.
Like the Duke programmers, Schaeffer and his team wanted to play against the human world champion, Marion Tinsley. They
got their match in 1992, but lost with 2 wins versus 4 losses. At that time, they didn't have the 8-piece database yet. In 1994, a
rematch was started, this time Chinook had the full 8-piece database. Due to bad health, Tinsley forfeited the match after
6 drawn games, he died shortly afterwards. Chinook went on to beat Don Lafferty, who was considered the second best player
in the world after Tinsley in 1995 in a very close match (1 win and 31 draws), and finished clear first far ahead of the field in the 1996 national
tournament in the US. At that point, the Chinook team decided there was nothing left to prove, and the program was retired. The 6-piece
endgame database was made public, and was the standard for PC programs for many more years.
Chinook website
The PC programs
The 1990s saw the advent of personal computers. They invaded offices and homes, and we are so used to them now that we
can hardly remember life before PCs. The Chinook program had been running on very powerful computers for it's time, but
thanks to Moore's law, today's (2003) PCs are faster than the machines Chinook was running on. I don't know too much about
the first PC programs. There was Checkers by Gil Dodgen, and Colossus by Martin Bryant. Bryant traded his opening book
against Chinook's endgame database, and in the early 90's, Colossus was probably the best PC program, but it was never
developed further. Gil Dodgen went
on to create World Championship Checkers with Ed Trice, and some new players arrived on the scene, all from England:
Adrian Millet with Sage, Murray Cash with Nexus and later with Nemesis and Roberto Waldteufel with Wyllie. Roberto was
the first to publish a program with a 7-piece database, which he computed on his own - the Chinook team was not releasing
their 7- or 8-piece database. Murray Cash and the Trice/Dodgen team both computed the 8-piece database by the end of 2001,
and after I also finished computing the 8-piece database in early 2002, Schaeffer finally released the 8-piece Chinook database to the
public. Nemesis is the current computer world champion.
CheckerBoard
Hmm, a paragraph for my own program in computer checkers history? Isn't that a bit too much?! Perhaps, but I leave it to others
to judge...
When I wrote CheckerBoard (1999 or early 2000, I don't remember), I was inspired by Tim Mann's Winboard for chess. Like Winboard,
CheckerBoard is purely an interface to checkers engines, it has no playing intelligence itself. Along with this it defines a protocol for
checkers engines, which describes how engines and interface interact. Like this, you can now write a checkers program without
worrying about interface programming. This has lowered the hurdle for beginning checkers programmers, and they can concentrate
on their program rather than on windows programming. All of this would not be worth mentioning if it was only theory. But here's what
happened: When Ed Gilbert happened to come across my CheckerBoard page in early 2000, he resurrected his age-old checker program.
I added an engine match feature to CheckerBoard, which allowed us to play automated matches of our programs over many games.
This possibility both made us improve our engines, because we wanted to beat each other, and it also helped improve our engines,
since we could easily test what effect a change in our programs would have in a match. Therefore, CheckerBoard has produced two of
the world's best checkers programs: Cake (by me) and KingsRow by Ed Gilbert.
They are the two top free
programs, about as good as the best commercial programs, and better than the weaker commercial programs.
The availability of strong free programs has made the commercial programmers
work harder on their programs, and this has improved the standard of play of PC programs in general. The level of today's top PC programs
is higher than that of Chinook when it retired, of course in part because today's PCs are faster than Chinook's hardware at the time.
Solving checkers
In 1990, Martin Bryant wrote:
Some fear has been expressed that in five or ten years computers will be able to beat the World Champion "every time" or even "solve" the game completely.
Well I've been in this field for a long time and in my opinion computers will NOT be able to beat the World Champion in any of our lifetimes and will
NEVER be able to "solve" the game completely.
Well, he was obviously wrong about the first part. How about the second part? It turns out that he was also quite wrong about that; apparently, he
underestimated the power of the endgame databases. One of the striking features of checkers is that if you can capture you must - this means that
as the game progresses, you more or less inevitably find yourself playing with less and less pieces (in contrast to chess for example, where this
scenario also can play out, but doesn't have to). The 8-piece database allowed Ed Gilbert and me to create enormous opening books
with a technique called "drop-out expansion", invented by Thomas Lincke at ETH Zürich who was doing a Ph.D. thesis in the group of professor
Jürg Nievergelt. As luck would have it, I knew another guy working in the group from the chess club and so I got to know Thomas and used his
technique. The opening books that Ed and I constructed are based on millions of computer-analysed positions, and are extremely accurate. Together with
these books, our engines Cake and KingsRow will hardly ever lose a game of checkers any more, and "for practical purposes" the game of checkers was
solved with this approach. However, a real solution was still missing. Ed Gilbert managed to compute the 10-piece database in early 2007 - alone, on a
couple of high-end PCs. Since then, he has used this database to analyse a lot of openings that remained unclear even with the 8-piece programs. A bit later,
in July 2007, the Chinook team announced that they had computed a formal proof that checkers was a draw. Of course the result was no surprise, but this is
the most complex game to ever have been solved.
Back to main checkers page - written on May 3rd 2003, last updated June 26, 2009