Checkers match
Murray Campbell
who has been world checkers champion for many years, and
"Chinook", a checkers program out of the University of Alberta written
by a group headed by Jonathan Schaeffer. The match is taking
place in London, England. I heard that on Wednesday August 19,
Chinook managed to beat Tinsley to level the match at one win each
with 6 draws. This is notable because Tinsley has lost only a
handful of games in his 40 year career, and has had no losses
in the past ten years. The match is supposed to continue
until August 29, with a total of 40 games to be played.
Richard V. Nash
I thought checkers was solved. Is it not?
--
+---------------------------------------------------------------+
| Richard V. Nash | Visual Understanding Systems, Inc. |
| na...@visus.com | Tel. (412)-488-3600 Fax. (412)-488-3611 |
+---------------------------------------------------------------+
Jeff Hanson
>
>I thought checkers was solved. Is it not?
>
Yes, if you have a heck of a memory & you work hard . . . but
then there's draw checkers & 11 man checkers & 11 man draw checkers . . .
Draw checkers is where the first move by each player is determined
by lot, with a couple of lemons excepted.
In 11 man checkers one piece is removed from the front row
(I think the one closest to the side of the board).
Tom Truscott
Checkers is most definitely not solved.
Chinook is easily the best computer checkers program that has ever existed,
yet it can lose whether going first or second.
Most people can name a world-class chess player,
yet few people can name *any* tournament checkers player,
let alone the world checkers champion (who has been champion for *decades*).
Jonathan Schaeffer even had difficulty locating
the American Checkers Federation.
Lack of information about the game has allowed for many misconceptions
about computer checkers to continue.
======================
Here are some true statements:
1. Checkers it not solved. It is not yet known whether the going first
wins, going second wins, or no one wins.
2. There has never (before Chinook) been a World, U.S.,
or even U.S. state checkers champion (in title or in effect).
3. Arthur Samuel (IBM, then Stanford) wrote a checkers program that about
thirty years ago defeated the Connecticut (US) *Blind* Checkers Champion.
This program, which pioneered many techniques including "learning",
was a great inspiration to AI researchers.
The belief that rapid progress would continue
no doubt resulted in some of the misconceptions.
4. Chinook has won a game against the World Checkers Champion,
the first such victory ever in the game of checkers.
========================
Since the match is currently even, I would suspect that Marion
Tinsley will start to pull ahead as he learns the program's
strategic weaknesses. Or perhaps Tinsley, who is getting old,
will become fatigued. Who knows?!
Perhaps the most interesting thing about Chinook
is that soon it may be able to solve the game of checkers.
Chinook has been computing a huge "solved endgame" book,
and is also building up a list of "solved" positions
that can be reached by a deep search from the initial position.
When this happens the misconceptions will become the truth!
What is the status of this effort?
Tom Truscott
Darse Billings
>I thought checkers was solved. Is it not?
Certainly not. Furthermore, it is often underestimated by snobbish chess
players (I was one) who feel it is "trivial" compared to the royal game.
You may be under the common misconception surrounding Arthur Samuel's
famous work, but his program only played expert strength checkers.
Although not as tactically complex, checkers is strategically comparable
to chess. And having a smaller branching factor (set of reasonable
candidate moves in a given position) is compensated by deeper analysis
(or search, in the case of computers). Perhaps checkers deserves
greater attention than it has historically received.
Of course, 19x19 Go is *much* more complex, both strategically and
tactically than either chess or checkers.
The largest game (by size of search domain) solved was previously
Connect Four, which was solved almost simultaneously by James D Allen
and Victor Allis in 1988, using very different methods. It is a win for
the first player (and d1 is the only winning move). For an excellent
account, see "Heuristic Programming in Artificial Intelligence -- The
First Computer Olympiad" by DNL Levy and DF Beal (editors).
In the third Computer Olympiad, in 1990, Qubic (4x4x4 Tic-Tac-Toe)
became the largest solved game, (although old analysis from around 1980
was mostly responsible for this). It is also a win for the first player
(any corner on level one or four, or any center square on level two or
three are equivalent moves and win, whereas the one distinct alternative
does not). Details may be found in "Heuristic Programming in Artificial
Intelligence 3", which has been recently released.
Checkers is considerably larger than Qubic, having a search space of
about 10^20 positions, with perhaps 10^18 of these being reachable in
practice. The ultimate goal of the Chinook project is to solve the
game, but this may not be achievable for some time. Of course, the
immediate goal for Chinook is to win the "de facto" world championship.
Jonathan Schaeffer believes it may be possible to solve the game of
checkers, particularly if all of the eight-piece endings can be computed
(and stored!). But it seems to be near the threshold of computational
limitations, so this remains to be seen.
Chess has a search space of about 10^44 positions, and 19x19 Go is just
a tad bigger at 10^170 positions (!!). Hence it is unlikely that these
games will be solved any time soon.
--
- Darse Billings, 2100 CM, 7 kyu.
Go is better than Chess. Poker is more lucrative. Sex is more fun.
Roberto Blaskovic
From what I heard Tinsley has only lost 8 games in his 40 years also I
heard that the number of game is only 30 and not 40 has there being a
change?
Bert van Oortmarssen
If Chinook will solve the game of checkers (within a few years), it might be
interesting to have a look at the 10x10 variant of this game (a.k.a.
polish checkers, as played in Russia, Holland, France, ...).
10x10 checkers has a higher complexity and will (probably) never be sold.
In Holland there are some twenty programs and every half year a torunament is
held. Winner of the last (5+) tournaments was TRUUS, which really is a strong
program (will probably be amongst the top-10 of players in Holland).
I am writing a longer article about 10x10 checkers & computers (not finished
yet), so contact me if you are interested.
Bert van Oortmarssen
AND-software bv. Rotterdam
be...@and.nl
J E H Shaw
>
>Since the match is currently even, I would suspect that Marion
>Tinsley will start to pull ahead as he learns the program's
>strategic weaknesses. Or perhaps Tinsley, who is getting old,
>will become fatigued. Who knows?!
>
"...
Observers point out that Dr. Tinsley played 14 hours on Tuesday
and was forced to play on a planned rest day yesterday whereas
computers never have an off-day."
Still a fantastic success for Chinook!
-- Ewart Shaw
--
J.E.H.Shaw, Department of Statistics, | JANET: st...@uk.ac.warwick.cu
University of Warwick, | BITNET: strgh%uk.ac.warwick.cu@UKACRL
Coventry CV4 7AL, U.K. | PHONE: +44 203 523069
yacc - the piece of code that understandeth all parsing
bar...@otago.ac.nz
> In article <1992Aug20.1...@watson.ibm.com> m...@watson.ibm.com (Murray
> Campbell) writes:
>> There is currently a match going on between Marion Tinsley (sp?),
>> who has been world checkers champion for many years, and
>> "Chinook", a checkers program out of the University of Alberta written
>> by a group headed by Jonathan Schaeffer. The match is taking
>
>
managed to lose a game. I have read a description of the program which shows
that it does fall short of a complete solution. Essentially it starts with
an opening book, continues by reading a full width search until it hits the
end-game database. the endgame database consisted of all positions with 6
or fewer pieces and it couldn't guarantee to hit it each time so had to have
an evaluation. as the endgame database grows the solution will become more
complete. Anybody have an E-mail address for Schaeffer to confirm progress.
Barry Phease
dwe...@uoft02.utoledo.edu
> Campbell) writes:
>> There is currently a match going on between Marion Tinsley (sp?),
>> who has been world checkers champion for many years, and
>> "Chinook", a checkers program out of the University of Alberta written
>> by a group headed by Jonathan Schaeffer. The match is taking
>> place in London, England. I heard that on Wednesday August 19,
>> Chinook managed to beat Tinsley to level the match at one win each
>> with 6 draws. This is notable because Tinsley has lost only a
>> handful of games in his 40 year career, and has had no losses
>> in the past ten years. The match is supposed to continue
>> until August 29, with a total of 40 games to be played.
>
> I thought checkers was solved. Is it not?
>
> --
NO! that was just a myth. it was BELIEVED to have been solved by a lot
of people in artificial intelligence...this turned out to be only a
rumor that was unfounded (like the guy who played in "leave it to
beaver" was killed in viet nam and the kid from the "life" commercial
named mikey choked to death on pop rocks )
then the guys who wrote Chinook wanted to study the heuristics
of the "solved" checkers program and found out that it didn't exist...so
they went to work...
rest is history in the making.
don wedding