Why can't a machine be World's Checkers Champ?
Dave Trissel
Having done a chess program at first glance it seemed to me that checkers
should be so much simpler than chess that a machine should certainly be
ranked as among the world's best, if not world champion.
Think about it. Only 32 squares instead of 64. Only 4 types of pieces
instead of 12, primitive moving rules, etc. Transposition tables should
especially make a killing in checkers with significantly greater ply search
depths allowed.
So - treading into the unkown I'm porting my chess program to checkers on my
Macintosh, which means stripping out over 80 percent of the code which is
far more complicated than that needed for checkers.
The S.A. mentioned that some chess players were into checkers and claimed that
some said it ranked with chess in subtlety. Which leads me to this posting -
does anyone have an opinion?
I'll let you know when my program is converted. It will be fun to see what
ply depth I can get on a Macintosh.
-- Dave Trissel {seismo,ihnp4,gatech,ctvax}!ut-sally!oakhill!davet
j...@ddnt.uucp
Samuels (Samuelson?) had a checker program in the mid-fifties which ran
on an IBM 704, I think. It played a quite good game, they said. It had
an adaptive evaluation function so that it was self improving. Check
the literature.
Tom Truscott
the current top five computer chess programs
were spent instead on a computer checkers program
we would have a computer as World Checkers Champion
(not officially, but it would be generally suspected).
For example, back in 1977 a checkers program written
by Eric Jensen, Bruce Wright, and myself
had a credible score (1 win, 2 draws, two losses) against Elbert Lowder
who was at that time considered #2 or so among human players.
The program had an excellent search, was tolerably efficient,
had no opening book, and the authors knew nothing of checkers but the rules.
(In checkers, many tournament games *end* within the book.)
The same authors spent an order of magnitude more effort
on the "Duchess" chess program, which never achieved an Expert rating.
I think the problem with checkers is that, whereas it is much
"easier" for a computer than chess, it is sufficiently harder
than, say, reversi (which is dominated by computers) that few
are willing to put in the effort needed to produce a world beater.
Particularly since checkers is not thought of as an intellectual game.
But it would be an interesting milestone.
Tom Truscott
Ray Frank
> Having done a chess program at first glance it seemed to me that checkers
> should be so much simpler than chess that a machine should certainly be
> ranked as among the world's best, if not world champion.
>
a checker program. And the only way even the world champ could win a game
was if the computer always moved second. If the computer was aloud to move
first then it could ALWAYS win. I'm talking main frame well done checker
programs here, not a radio shack toy.
This may clear up why a machine cannot be World's Checker Champ. It could neverbe dethroned and thus would eliminate the world championship as an event. I
think that checker programs for this reason may not be aloud to play tournament
checkers. The USCF has considered outlawing chess programs before they have
a chance to be a world champ, but so far they are permited to enter most
tournaments. Usually at the discretion of the tournament director.
Tom Truscott
> a checker program. And the only way even the world champ could win a game
I too have read such reports. They are sincere but wrong.
In particular Marion Tinsley (math prof., world checkers champion)
has expressed non-trivial contempt for computer checkers programs.
Here is a snip from a paper I wrote on computer checkers:
``I should say that at present, there are several thousand
just average Class B players who could beat either
[the Duke or Stanford] computer without difficulty.''
-- W.B. Grandjean, \fIACF bulletin\fP, August 1977
.QP
``Although computers had long since been unbeatable
at such basic games as checkers, ...''
-- Clark Whelton, \fIHorizon\fP, February 1978
.PP
In computer checkers,
as in many areas of artificial intelligence,
misconceptions abound as to the present capabilities of machines. ...
> ... I'm talking main frame well done checker
> programs here, not a radio shack toy.
The Duke checkers program was written entirely in S/360 assembly language
and run on an IBM 370/165, so I guess that qualifies.
But I am sure someone could write a TRS-80 program that could beat it.
Look at Kathe and Dan Spracklin's computer chess successes on a micro.
Tom Truscott
r...@ada-uts.uucp
The Samuels checker program (mentioned in the first response to this note)
was in fact better than all human players, including the world champion,
at the time. In checkers, there's probably no comparison (today) between
the best programs and the humans.
Bradford W. Miller
>I'm almost sure that a few years ago I read that man could no longer beat
>a checker program. And the only way even the world champ could win a game
>was if the computer always moved second. If the computer was aloud to move
>first then it could ALWAYS win. I'm talking main frame well done checker
>programs here, not a radio shack toy.
If an algorithm exists that insures a win for the first player, checkers is
then not a game.
Brad Miller
--
..[cbrma, ccivax, ccicpg, rayssd, ritcv, rlgvax, rochester]!ccice5!ccice1!bwm
Tom Truscott
> then not a game.
Hmm, that might be putting it a bit harshly. People still play tic-tac-toe.
More interestingly, if such algorithm does *not* exist
then either the second player wins, or the game is a draw. Grim all around.
There is a real (to me) possibility that checkers could be "solved"
with little more effort than that needed make a world champion.
The search tree grows at an effective rate of ~ 2^depth,
and there are probably a reasonably finite number of different positions.
Anyway, it is something to consider.
Tom Truscott
Lance R. Ogasawara
> a checker program. And the only way even the world champ could win a game
> was if the computer always moved second. If the computer was aloud to move
> first then it could ALWAYS win. I'm talking main frame well done checker
> programs here, not a radio shack toy.
> This may clear up why a machine cannot be World's Checker Champ. It could neverbe dethroned and thus would eliminate the world championship as an event. I
> think that checker programs for this reason may not be aloud to play tournament
> checkers. The USCF has considered outlawing chess programs before they have
> a chance to be a world champ, but so far they are permited to enter most
> tournaments. Usually at the discretion of the tournament director.
YOUR MESSAGE
I'm not 100% certain, but I always thought that moving second was an
*advantage* in checkers because the first player tends to run out of
moves.
Tom Truscott
> was in fact better than all human players, including the world champion,
The above statement may be widely believed, but it is simply not true.
First, in neither of Samuels' papers on checkers was such a claim made.
Second, the Duke checkers program easily beat Samuels' program
in a two game match, yet lost to a human player only ranked #2 or so.
(In 1979 at least, the gap between Marion Tinsley (#1) and everyone
else was just incredible. Tinsley has been champion for *many* years.)
> ... In checkers, there's probably no comparison (today) between
> the best programs and the humans.
Frankly, I have know idea who (if anyone!) has the best checkers program.
But I do agree with this statement :-).
Tom Truscott
Steve Vegdahl
> program in the late '70s - early '80s that beat the then world champion
> pretty convincingly. But I guess that doesn't really belong here ...
I was in the CS department at CMU when that match occurred. The victory
in the deciding game was anything but convincing. The (human) world
champion had a very strong position, but Hans (rolling for the computer)
rolled something like a double-5 and two double-6's right at the end in
order to eek out the victory. The score might have appeared convincing
due to doubling that may have occured during that game. I don't remember
the details. I do remember Hans relating the story to some of us in the
department; he gave the strong impression that his program was very lucky
to have won the match.
Steve Vegdahl
Computer Research Lab.
Tektronix, Inc.
Beaverton, Oregon
Jim Gillogly
I claim that's not the case. It was in the same league as state champions,
but Samuel (not Samuels) didn't claim or believe that it was better than
all human players. I followed the literature pretty closely at the time,
being in the chess programming biz in the early 70s.
--
Jim Gillogly
{decvax, vortex}!randvax!jim
j...@rand-unix.arpa
Saumya Debray
>> Talking of game-playing programs, Hans Berliner at CMU had a backgammon
>> program in the late '70s - early '80s that beat the then world champion
>> pretty convincingly. But I guess that doesn't really belong here ...
>
> I was in the CS department at CMU when that match occurred. The victory
> appeared convincing due to doubling ... I do remember Hans relating
> the story to some of us in the department; he gave the strong impression
> that his program was very lucky to have won the match.
Berliner had a paper on this program in "Artificial Intelligence" in '80 or
'81. I seem to remember reading that afterwards, they reversed positions
to test the program: the "opponent's moves" fed to the program were in fact
its own moves when it had played the world champion, and in almost all
cases, it made exactly the move the world champ himself had made in that
position. I was tremendously impressed by this.
Again, I'm not sure how much a discussion on machine checkers belongs in
net.chess -- I've changed the followup line to cross-post this article to
net.ai: please send followups to this article to net.ai ONLY.
--
Saumya Debray
SUNY at Stony Brook
uucp: {allegra, hocsd, philabs, ogcvax} !sbcs!debray
arpa: debray%suny-s...@csnet-relay.arpa
CSNet: deb...@sbcs.csnet