🚀 go-pugleaf

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.

I feel that if the effort and expertise spent in creating any one of
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

> Scientific American a few months ago had an article about checkers strategy.
> 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.
> 
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.
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.

> 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.

The program you refer to dates through the sixties.  It had, as far as I
recall, a learning component, but used the same evaluation function for its
estimate of its opponent's estimate of a position as it did for its own
estimate of a position, and hence was not really "adaptive". (A truly adaptive
system would maintain two evaluation functions -- one reflecting its own
strategy, the other its estimate of its opponent's strategy.  It would
use predictive-corrective methods to continuosly modify its estimate of its
opponent's strategy, and then adapt its own strategy to this.)

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 ...
-- 
Saumya Debray
SUNY at Stony Brook

	uucp: {allegra, hocsd, philabs, ogcvax} !sbcs!debray
	arpa: debray%suny-sb.csnet@csnet-relay.arpa
	CSNet: debray@sbcs.csnet

> 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. ...

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

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.

In article <10913@rochester.UUCP> ray@rochester.UUCP (Ray Frank) writes:
>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

> If an algorithm exists that insures a win for the first player, checkers is
> 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

> 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.
> 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.

> 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. ...

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

> 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
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

In article <9100002@ada-uts.UUCP> ron@ada-uts.UUCP writes:
>
>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.

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
	jim@rand-unix.arpa

Steve Vegdahl:
>> 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
> in the deciding game was anything but convincing.  The score might have
> 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-sb.csnet@csnet-relay.arpa
	CSNet: debray@sbcs.csnet