davet@oakhill.UUCP (Dave Trissel) (08/02/85)
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.
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!davettrt@rti-sel.UUCP (Tom Truscott) (08/07/85)
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
ray@rochester.UUCP (Ray Frank) (08/07/85)
> 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.
trt@rti-sel.UUCP (Tom Truscott) (08/09/85)
> 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
bwm@ccice1.UUCP (Bradford W. Miller) (08/09/85)
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
trt@rti-sel.UUCP (Tom Truscott) (08/12/85)
> 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
lance@riccb.UUCP (Lance R. Ogasawara ) (08/12/85)
> 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.