The game of checkers seems
to have been solved.
Its a draw.
here if you don't mind seeing an ad for low cholestrol cooking before
getting to the article
you subscribe to the nytimes
here if you trust
The checkers program CHINOOK cannot lose (it can draw).
The program has been around for quite some time, being
improved over time. The researchers are Jon Schaeffer (the originator),
Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar.
They say they have a `computational proof not a math proof'.
Not sure what that means, but I do believe that Checkers is now done.
There is a very good book called One Jump Ahead
that is about the program Chinook that plays Checkers very
well (now perfectly apparently) but it was written a long
time ago, before the recent news.
My impression of Chess and Checkers playing programs is
that they are very clever engineering but not really
much for a theorist to get excited about.
However, very clever engineering should not be underrated.
I also think that these programs have taught us
that (some) humans are very good at these games in a way
that is different than machines. When Deep Blue beat
Kasporov, rather than thinking (as the popular press did)
Oh no, computers are smarter than humans!!
Wow, it took that much computing power and that much
look-ahead to beat Kasporov. Kasporov must be very good
(duh) and the way he plays is different than what
a computer would do.
Similarly, the Chinook researchers ended up being
very impressed with Marion Tinsley (the best checkers
player of all time, since deceased). Analysing his games it
seems as though he almost never made a mistake.
Chinook and Tinsley had two matches- Tinsley won the first one with
4 wins to Chinook's 2. During the second one Tinsley took ill
and had to forfeit- he died a few months later.
Will checkers decline in popularity?
I don't think so--- its already so unpopular that
it can't decline much. This story may give it
a temporary revival.
Posted By GASARCH to Computational Complexity
at 7/23/2007 12:00:00 PM