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
