Perfection in checkers
29.10.2003 – Can you imagine a world champion, who
reigns undefeated for 45 years? From 1950-1995 Dr Marion Tinsley played
in thousands of checkers tournaments and matches, and never finished
worse than undivided first. In all that time he lost exactly seven
games. In the end he was succeeded by a machine. Jonathan O'Connor tells
us the whole story.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 5x1020 positions (5 with 20
zeros after it) in checkers, whereas chess has at least 1040
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: 1020 for checkers and 1040
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.
The author:
Jonathan O'Connor is Irish and works as a software
developer for the German company XCOM. He has three children who are
sadly not into chess ("ah, but Fritz and Chesster may change that,"
he writes). Jonathan himself has played chess for over 25 years and
has a FIDE rating of 2195. Currently he is the secretary of the
Dublin Chess Club, which was founded in 1867 and has been open ever
since.
About the photo Jonathan writes: "You take my queen, and my bird
will peck out your eyes!" |
|
Links (up dating above
article)
|