A taste of things to come?
Jonathan Schaeffer
as it may be a forerunner of what will eventually happen in chess.
The checkers program, Chinook, authored by Jonathan Schaeffer, Joseph
Culberson, Norman Treloar, Brent Knight, Paul Lu and Duane Szafron
(University of Alberta, Edmonton, Canada) has stunned the checkers world
by winning the right to play for the (human) World Checkers Championship.
In August, Chinook competed in 2 human tournaments against the best
best checkers players in the world. In the Mississippi State Open,
in Tupelo Miss., Chinook's first tournament with humans, the program
scored 7 wins, 0 losses, and 7 draws to win first prize. Along the way
it defeated Richard Hallet (+1,-0,=1) and Elbert Lowder (+2,-0,=0)
and drew with Ron King (+0,-0,=2); all three are ranked in the top 10
in the world.
This tournament was a warmup for the U.S. National Open. Almost all the
best players in the world were competing, including World Champion Marion
Tinsley. Only one player in the world top-10, Derek Oldbury from England,
was absent.
Chinook, won 4 matches, lost none and drew 4. Each match was 4 games long.
Along the way it defeated the #2 player in the world, Don Lafferty (+1,-0,=3),
and Ron King (+2,-0,=2) and drew an exciting 4-game match with Tinsley
(+0,-0,=4). Final standings were:
W L D Pts
1. Marion Tinsley 5 0 3 13/16
2. Chinook 4 0 4 12/16
3. Richard Hallet 4 1 3 11/16
4. Asa Long 3 0 5 11/16
A 6 way tie for 5-10th included Lafferty and another computer program,
Checkers Experimental, authored by Gil Dodgen, with 5 wins, and 3 losses
(losing to Tinsley, Long, and Lafferty). There were 34 players in the
tournament, all of master or grandmaster strength.
The highlite of the event was the Tinsley-Chinook showdown. Tinsley has been
the best in the world for 40 years and has only lost 5 games in that period.
In June, he defended his World Title by defeating his challenger, Paul Davis,
10-0 with 20 draws. The 4 game match ended in 4 draws. In games 1 and 4,
Tinsley pressed hard for a win, only to be rebuffed by strong defense. After
game 1, Lafferty commented that the defense was so complicated and intricate
that "no human would have survived the attack."
By coming second to Tinsley, Chinook has won the right to challenge him
to a 40-game World Championship match. It is not clear whether this will
happen; the American Checker Federation must make a ruling on whether a
computer will be allowed to play for a World Championship. Tinsley has
offered to play us a 20 game "friendly match" without the World title at
stake.
This is the first time in history that a computer program has earned the
right to play for a world title. Previous matches between World Champions
and computers have been exhibitions: in 1980, the backgammon program BKG9
played the World Champion a 7 point match; in 1989 the chess machine Deep
Thought played a 2 game match against the World Champion.
Although Chinook's results were extraordinary and, to be honest, unexpected,
the program is not yet in Tinsley's class. Chinook is now in the top 10
in the world and with a bit more work, we can reach number 2. Tinsley has
lost 5 games since 1950 - a record unmatched in any sport.
Over the 2 tournaments, Chinook lost 2 games. Both games were the same
problem - opening book. Rather than typing in thousands of opening positions,
we are having the computer generate its own opening book. Unfortunately,
in the tournaments, we walked into opening traps that were beyond the depth
of search of the program (one required 26-ply and the other 33-ply to see!).
It is important to note that knowing the book in checkers is much more
important than in chess. In chess, if you do not know the best moves you will
get an inferior position. In checkers, there are many positions in the first
10 moves that have been proven to be forced losses - and the analysis runs
very deep. Not knowing the book can result in a lost position as early as
move 4! Chinook was never in trouble in any game where it survived to move
10 with a reasonable position. Once we have a better opening book and several
other improvements that are under way, the program will be significantly
stronger.
For the tournament, the program had access to databases with all the 6-piece
positions. These databases enumerate all positions with 6 or fewer men on
the board and contain perfect information as to which positions are wins,
losses or draws. The databases, combined with deep searches (averaging 20 ply
plus extension) allowed the program to declare 8 games as over IN UNDER 10
MOVES! We are currently starting on the 7-piece endgames but will need
some help for this (machine time and memory). If we were to solve the 8-piece
endgames, I feel the program will be unbeatable. There are 100 billion 4:4
positions, well beyond anything we can hope to handle in the foreseeable
future.
Michael L. Kaufman
if I was in a spelling bee, I would not want to have to compete against a
computer. Or, if there was a math competition the idea of a computer competing
would not come up. So why are computers in chess tournaments? I have never had
to play against a computer in a turny but I would certainly complain if it ever
came up. Don't get me wrong, I play computer chess at home, and I would like
to see the programs get as good as possible. Any comments?
Michael
Melvin H. Nicholson -- YBH
In an interactive fiction game based loosley on the world of William
Gibson's Nueromancer, the Chess World consists of a BBS-type local where
each player uploads a program to compete against the other. While I
wouldn't suggest that we are teetering on that extreme, the prospect
*is* rather bleak, and I doubt I'd be very happy to have an unerring
silicon opponent wipe me out using computational power and speed which
I can only dream of.
I like the idea of good chess computers, and of the computer olympics,
where they can compete at all those games, but HUMAN championships
should be for HUMANS! If we let computers into the master's circle, as
in CHECKERS, they will eventually kill the game, as no human will be
able to compete with them.
Mel
:wq
Will Bralick
I sympathize with the (inplied) sentiment. Note that you are allowed to
inform the TD that you either (1) _prefer_ to not play against a machine
or (2) _refuse_ to play against a machine. If you do not inform the TD
of (1) or (2) then he will assume that you are willing to play a machine.
Personally, I would refuse to play a computer -- to me chess is a human
activity and I derive enjoyment from it in that context; remove the
human opponent and my interest level drops to zero.
| ...
| Don't get me wrong, I play computer chess at home, and I would like
| to see the programs get as good as possible. Any comments?
Well, the advantage humans have is that if computers take over the
game we can just learn a new game and play that. A chess program is
an idiot savant -- CHESSumpty-ump-dot-umpty-ump would play a lousy
game of Diplomacy. The fear is that if computers play well enough
people will lose interest in chess. Perhaps when programs get good
enough and players generally _refuse_ to play them then sponsors will
start making all tournaments "NC."
Regards,
--
Will | ... when princes think more of
bra...@cs.psu.edu | luxury than of arms, they lose
bra...@sol4.cs.psu.edu | their state.
with disclaimer; use disclaimer; | - Niccolo Machiavelli
Staveren van Hans
"I like to crush the other guys ego"
It is hard to do that to a computer. If I can't make my opponent suffer
what is the fun in playing?
paolo ciancarini
In article <Fj22z#-1...@cs.psu.edu> bra...@osgiliath.endor.cs.psu.edu (Will Bralick) writes:
>In article <11...@accuvax.nwu.edu> kau...@delta.eecs.nwu.edu (Michael L. Kaufman) writes:
>| I have a question. Why are computers allowed to play in tournaments?
>
>Personally, I would refuse to play a computer -- to me chess is a human
>activity and I derive enjoyment from it in that context; remove the
>human opponent and my interest level drops to zero.
I am surprised that people that normally use computers to work
cannot see why someone could be glad to play with them.
Commercial computer play in human tournaments why this way they gain
Elo evaluations that are used for publicity. Their participation
is useful because normally software houses sponsor in some way
the tournament.
Academic computers play in human tournaments because this is
the best way to test them. Moreover, competitive computer
chess is maybe the most interesting research theme for
non computer wizards.
By the way, almost all experts say that clever chess machines
are immediately anthromophized: compare the novel
"Hence", by B.Leithelberg, in which a young grandmaster
plays against a chess machine. So there is a"human"
side in playing against a computer.
Chess is the simulation of a war: the computer is your enemy. If
you study him, you know his weaknesses and his strong points.
That is all.
>
>| ...
>| Don't get me wrong, I play computer chess at home, and I would like
>| to see the programs get as good as possible. Any comments?
>
>Well, the advantage humans have is that if computers take over the
>game we can just learn a new game and play that.
When a chess computer will beat the World Champion, no problem.
My favourite scenarios are two:
1) chess research stops for awhile, and
humans change slightly the rules of the game,
(as they did many times during the chess history:
think about the old queen movements, or about
old castling rules) just to annichilate all the algorithms
and databases developed until now.
<Hint for discussion:
which changes would be most effective, maintaining chess as a
perfect information game?>
2) chess machines integrate perfectly human grandmasters;
in tournaments you are allowed to use any machine you want.
The combination human+machine is a new kind of player
that should be more explored.
> A chess program is
>an idiot savant -- CHESSumpty-ump-dot-umpty-ump would play a lousy
>game of Diplomacy. The fear is that if computers play well enough
>people will lose interest in chess.
Chessplayers that are women do not lose interest in chess
also if any statistics say that men are better players.
They play, enjoy the game, and try to improve female statistics!
I agree with you that some playing programs are "idiot savant",
especially if they use too much "perfect information".
Maybe use of perfect information should be avoided in tournaments.
But many useful "intelligent" techinques were developed
using chess. D.Michie said (citing on memory):
"chess research is the most important research in the field of
knowledge engineering, a field that will become very important.
Chess is for us what Drosophyla was for genetists:
a simple and very useful testbed to develop new techiques".
> Perhaps when programs get good
>enough and players generally _refuse_ to play them then sponsors will
>start making all tournaments "NC."
Botvinnik said in 1960:
"When computers will become grandmasters, special tournaments
will be organized for them". Until that time,
I suggest that we allow them to participate.
Paolo Ciancarini
Yale University
kevydahm
tournaments. They aren't awarded titles and the organizers frequently, if
not always, give players the option of saying before the tournament that they
do not wish to play the computer. (In two different tournaments that I have
played in, the person entering the computer program offered a cash prize to
the lowest rated player to beat his program. Kind of a nice touch.) I'm
not overly worried about computers ruining the game of chess. I know that
a computer proved that the game of checkers is a forced win, I believe for
the first player, but I have yet to meet anyone who could claim to be a perfect
checkers player- so how has the game been ruined?
As for changing the game of chess to make old algorithms and databases
obsolete, I don't think this will be necessary, but all the same there's one
variation which I invented (probably not uniquely invented, far be it from me
to have that much imagination) that might make fun tournament play. The game
starts with only the pawns in place, and the players alternate placing one
of their pieces somewhere in the back rank. I think this also eliminates
white's advantage, since white still has the edge of first move, but black
has the advantage of seeing white's placement and being able to react to that.
I've experminented with this variation on occasion and found it interesting.
Kevin
Louis Blair
The author is Brad Leithauser.
Will Bralick
|
| In article <Fj22z#-1...@cs.psu.edu> bra...@osgiliath.endor.cs.psu.edu (Will Bralick) writes:
| >Personally, I would refuse to play a computer -- to me chess is a human
| >activity and I derive enjoyment from it in that context; remove the
| >human opponent and my interest level drops to zero.
|
| I am surprised that people that normally use computers to work
| cannot see why someone could be glad to play with them.
That isn't what I said. I merely said that _I_ am not interested
in playing a machine in a tournament.
| Chess is the simulation of a war: the computer is your enemy. If
| you study him, you know his weaknesses and his strong points.
| That is all.
I wouldn't spend an entire weekend trying to "beat" a video game
either (even one that is a simulation of a war), but I might be
interested in a chess tournament, wargame, etc. I am not saying
that it is _wrong_ to play a computer, I am merely saying that I
find it singularly _uninteresting_ and so I do not choose to do it.
| ...
| I agree with you that some playing programs are "idiot savant",
| especially if they use too much "perfect information".
No, they are "idiot savants" because they can only do one thing --
play chess (at which they can have moderate success) and are
abysmally stupid at everything else.
| Botvinnik said in 1960:
| "When computers will become grandmasters, special tournaments
| will be organized for them". Until that time,
| I suggest that we allow them to participate.
They _are_ allowed to participate. However, as a human, I have the
right to refuse to play one -- I will choose to exercise that right.
Regards,
--
Will | If no set of moral ideas were truer or
bra...@psuvax1.cs.psu.edu | better than any other, there would be no
bra...@gondor.cs.psu.edu | sense in preferring civilised morality to
with disclaimer; use disclaimer; | savage morality... -- C.S. Lewis
Will Bralick
| I don't see what the big deal is about letting computers play in "human"
| tournaments. They aren't awarded titles and the organizers frequently, if
| not always, give players the option of saying before the tournament that they
| do not wish to play the computer.
As I mentioned earlier, the organizers don't _give_ this option to the
players -- it is the (human) player's _right_ as specified in the rules
of chess.
Jonathan Schaeffer
> > ... . I know that
> > the first player, but I have yet to meet anyone who could claim
> > to be a perfect checkers player- so how has the game been ruined?
>
>
There are 5*10**20 checkers positions, of which a small percentage,
we estimate 10**18, are legally reachable. To "prove" the game, you
may need as few as the square-root of the positions. We believe the
game is solvable with current technology and are working to do just that.
> I am sure that there are 10-20 humans who can defeat the best
> current computer checkers program.
I do not think the checkers' community will agree with you. Chinook's
performance in Tupelo has given it a rating of 2755 (based on 46 games),
second only to the World Champion's 2815. Third place is 2680. However,
I believe Chinook is currently over-rated. 6 months from now, once all
the known deficiencies in the program are fixed, then I belive this will
probably be an accurate assessment.
> There are very few humans who play tournament checkers,
> so *chess programs* defeat a larger fraction of tournament players!
This is true. Checkers may be a dying game. In the last 20 years, there
has not been an infusion of young blood into the game.
> Computers play checkers relatively badly because no one has put
> in an effort comparable to that of the best chess programs.
Sorry Tom. You probably view things in the light of 10 years ago when
the Duke program was doing well. The software and hardware technology
has made big advances in that time. Checkers programs do not play
"badly" anymore.
> To "solve" the game of checkers is a much bigger challenge.
> I think it might be possible within the next 20 years,
> but only if someone is willing to try!
5 years or less, if someone can help us out with the equipment we need.
> Checkers just doesn't get any respect. Or interest.
> When was the last world checkers championship? Who won?
In June. Marion Tinsley defeated Paul Davis 10-0 with 20 draws.
> No wonder no one bothers with computer checkers!
> Tom Truscott
Not true. For some reason, there has been has been a surge of interest
in computer checkers. Last year's computer Olympiad in London attracted
6 entries for the checkers event. Gil Dodgen of California and Martin
Bryant of England have quality programs (that have done well in human
tournaments) that are now commercially available.
Thomas Truscott
> the first player, but I have yet to meet anyone who could claim
> to be a perfect checkers player- so how has the game been ruined?
Checkers is not a solved game. No computer program plays it perfectly.
I am sure that there are 10-20 humans who can defeat the best
current computer checkers program.
There are very few humans who play tournament checkers,
so *chess programs* defeat a larger fraction of tournament players!
Computers play checkers relatively badly because no one has put
in an effort comparable to that of the best chess programs.
To "solve" the game of checkers is a much bigger challenge.
I think it might be possible within the next 20 years,
but only if someone is willing to try!
Checkers just doesn't get any respect. Or interest.
When was the last world checkers championship? Who won?
Steve Armentrout
> I know that a a computer proved that the game of checkers is a forced win,...
I find that surprising.
As stated in Nilsson's "Principals of Artificial
Intelligence",
It has been estimated that the complete game tree for
checkers has approximately 10**40 nodes and the chess
tree has approximately 10**120 nodes.
It would take about 10**21 centuries to generate the
complete checker tree, even assuming that a successor
[position] could be generated in 1/3 of a nanosecond.
What are your references?
Steve
Bruce Wright
>
> >Well, the advantage humans have is that if computers take over the
> >game we can just learn a new game and play that.
>
> When a chess computer will beat the World Champion, no problem.
> My favourite scenarios are two:
>
> 1) chess research stops for awhile, and humans change slightly the rules
> of the game, (as they did many times during the chess history:
> think about the old queen movements, or about old castling rules) just
> to annichilate all the algorithms and databases developed until now.
> <Hint for discussion:
> which changes would be most effective, maintaining chess as a
> perfect information game?>
Simple changes such as Capablanca's Chess, where a couple new pieces
combining things like a Knight's move with a Rook's move are added
to the game, would not be likely to slow down computer programs very
much; there would need to be a few changes to the programs, and
perhaps a couple years of experience tuning the programs for the
modified game, but it wouldn't have very much of an effect after that.
Ditto for going back to the old castling rules (in fact that would
probably have even less effect).
One of the changes that would make the most difference has already
been made: in Japan. In Japanese chess (shogi), captured men are
not killed; they are mercenaries which are now _your_ men and work
for you, and can be entered on the board on a vacant square instead
of moving a piece on the board! Of course, there are a few changes
to the set that are needed for this to work: the typical sets don't
have colors, but symbols for the type of the piece. Some sets use
symbols like the chess symbols in Western chess diagrams, but most
sets use the Japanese ideograms (which are not so difficult to
recognize as a non-Japanese speaker might suppose - after all, even
the Western chess diagrams are just arbitrary collections of symbols).
You can tell which are your men and which are your opponent's men by
which pieces have the symbols right side up or upside-down.
There are a few other differences between Japanese shogi and Western
chess, notably that _most_ pieces can promote (and that the type of
piece resulting from the promotion is strictly determined by the
original type of the piece, and is not optional as in Western chess),
but from the point of view of the computer programmer the "drop" is
by far the worst problem.
The problem for computer programs is that this makes the game much
more difficult to attack by brute force. It is not uncommon to have
a half dozen men "in hand" and ready to drop anywhere; this increases
the branching factor considerably. The fact that you don't ever reach
situations like a chess endgame (where attrition might reduce the armies
to the point that the weaker simply has no further ability to resist,
or that neither side has sufficient material to do anything useful)
means that there isn't as much of a penalty for things like Pawn
sacrifices or even Exchange or piece sacrifices, in order to obtain
structural or dynamic advantages. So the simple reliance on counting
up material, which even in Western chess can cause computer programs
problems, becomes fatal in shogi.
This also means that there are VERY few draws in shogi - there's not
the prospect of draws by reduction of material that occur in chess.
So it probably means that when and if a really good computer program
is ever developed for shogi, it would be a real monster. But although
there are a couple of shogi-playing programs around, I don't know of
any that are of anywhere near the quality of checker and chess
programs, and I don't know of very many people working on them.
Because shogi can have a _lot_ of tactics, there's a bit of emphasis
on how to build positions that are resistant to attack by the drop.
Computers could probably do pretty well even now against a weak
opponent (at the level where a lot of tactics are completely over-
looked), and in mating attacks where every move is forced; but if it
is playing against a strong player it would be likely to sooner or
later get itself in an awkward position, and in shogi as in chess,
tactics tend to flow from a good position, not a bad one. It doesn't
do much good to see in gruesome detail how you are going to get
mated once it's inevitable!
In short, this modificiation would present game programmers with
a whole different set of problems. I suspect that they are solvable,
but probably not by simple adaptations of the methods used to approach
Western chess.
Bruce C. Wright
Brian Yamauchi
(Will Bralick) writes:
>
> >Well, the advantage humans have is that if computers take over the
> >game we can just learn a new game and play that.
>
> When a chess computer will beat the World Champion, no problem.
> My favourite scenarios are two:
>
> 1) chess research stops for awhile, and
> humans change slightly the rules of the game,
> (as they did many times during the chess history:
> think about the old queen movements, or about
> old castling rules) just to annichilate all the algorithms
> and databases developed until now.
> <Hint for discussion:
> which changes would be most effective, maintaining chess as a
> perfect information game?>
I can think of two simple changes each of which alone would make brute
force approaches to the game completely untenable.
(1) Wargame style movement -- Allow players to move as many pieces (from
none to all) as they wish on each turn. This drastically increases the
branching factor to the point at which exhaustive search becomes
prohibitively expensive.
(2) Wargame style combat -- Use some sort of Combat Results Table to
determine whether any given attack succeeds (e.g. a queen attacking a
pawn might have a 5/6 chance of success while a pawn attacking a queen
might only have a 1/6 chance). This makes approaches such as minimax
search useless -- you really don't want to plan for the worst case,
since the worse case will become vanishingly unlikely.
Of course, I'm not sure either (1) or (2) counts as a *slight* change to
the rules. :-) Human players would need to modify their strategies as well.
One of the other benefits of making these changes would be to make chess
more interesting as an AI research problem (as opposed to a systems
research problem).
_______________________________________________________________________________
Brian Yamauchi University of Rochester
yama...@cs.rochester.edu Computer Science Department
_______________________________________________________________________________
Herbert Enderton
be), but the topic of what games are tractable by standard computer
chess methods interests me. Raising the branching factor by giving
pieces more mobility as was suggested will probably only help the
computer. High branching factor makes the game hard for humans as
well. The only reason humans are competitive in chess at all, at this
point, is that we can reason about the game in ways that chess programs
can't (or don't). For example, we can look at the pawn structure and
decide whether White would be able to create a passed pawn if the
pieces were traded off. Chess programs have a hard time (compared to
humans) dealing with positions with a lot of structure, e.g. closed
positions, pawn endings, positions where a piece is trapped for a long time,
or positions with subtle "permanent" weaknesses. In tactical middle games,
with pieces zooming all over the board, it's hard to reliably reason
about local aspects of the game. If I wanted to make chess harder for
computers (easier for humans), I'd put a limit on the distance each
piece can move (so queens can only move like kings, say). That way the
tactical situation in one corner of the board would be less sensitive
to movement on the rest of the board.
-- Bert Enderton (aspiring go programmer)