On Jul 23, 4:10 pm, Guy Macon http://www.guymacon.com/ wrote:
They wouldn't be publishing partial results in _Science_ under the
title ``Checkers is Solved.''
As I have not seen that magazine, I have no idea
whether or not "they" (whoever they are) would likely
place such an article under such a name.
The obvious google search [ checkers science magazine ]
[http://www.google.com/search?q=Check...ence+magazine]
brings you right to it:
Er, no it doesn't! That search yields nearly 1.5 million
hits from which to choose. LOL!
|The game of checkers has roughly 500 billion billion
Uh, this should I think be 500 quadrillion, not any
"billion billion" or "million million million", etc. :D
possible
|positions (5 x 1020). The task of solving the game, determining
|the final result in a game with no mistakes made by either player,
|is daunting. Since 1989, almost continuously, dozens of computers
|have been working on solving checkers, applying state-of-the-art
|artificial intelligence techniques to the proving process. This
|paper announces that checkers is now solved: perfect play by
|both sides leads to a draw. This is the most challenging popular
|game to be solved to date,
Another item posted here put that as "problem",
rather than "game" -- a gigantic difference. --Ed.
roughly one million times more complex
|than Connect Four. Artificial intelligence technology has been
|used to generate strong heuristic-based game-playing programs,
|such as DEEP BLUE for chess. Solving a game takes this to the
|next level, by replacing the heuristics with perfection.
|In essence, that reduces checkers to the level of tic-tac-toe, for
|which the ideal game-playing strategy has been codified into an
|immutable strategy. But checkers -- or draughts, as it is known in
|Britain -- is the most complex game that has been solved to date, with
|some 500 billion billion possible board positions, compared with the
|765 possibilities in tic-tac-toe.
Note how the rough guesstimate numbers yield a
distinct impression of approximation, not "perfection".
|Even with the advances in computers over the past two decades, it is
|still impossible, in practical terms, to compute moves for all 500
|billion billion board positions. So, the researchers took the usual
|starting position and looked only at the positions that occurred
|during play.
Unclear. Does this imply they examined only
checkers positions which occurred in tournament
play between checkers masters, or all legally
possible checkers positions which can be reached
via a sequence of legal moves?
|"It's a computational proof," said Jonathan Schaeffer, a professor of
|computer science at the University of Alberta who led the effort.
|"It's certainly not a formal mathematical proof." That means it is
|impossible for anyone to check every calculation the computer has
|performed.
|
|Because of the vast calculations, the researchers had to keep
|painstaking track of the data. Miscopying a single bit -- a glitch that
|did occur every few months -- could render their result incorrect if
|not caught and corrected. When an error was caught, calculations had
|to be restarted from that point. A checkers hobbyist has independently
|verified major components of the proof with another computer program.
Note how the "hobbyist" goes unnamed, as does
his program and just about anything anybody might
want to know in order to verify if these claims are
truly airtight. Coincidence? Maybe... .
|Dr. Schaeffer began his quest in 1989, aiming to write software that
|could compete with top checkers players in the world. In April, 18
|years later, he and his colleagues finished their computations.
|
|"From my point of view, thank God it's over," Dr. Schaeffer said.
|
|For an exercise in futility, anyone can play a game against the
|perfect Chinook athttp://www.cs.ualberta.ca/~chinook/play/. (It is
|limited to 24 games at a time.)
That's okay. I generally play no more than nineteen or
twenty checkers games at a time myself. ;D
|Dr. Tinsley won, 4 to 2 with 33 draws. Chinook's two wins were only
|the sixth and seventh losses for Dr. Tinsley since 1950. In a rematch
|two years later, Dr. Tinsley withdrew after six draws, citing health
|reasons. Cancer was diagnosed, and Dr. Tinsley died seven months
|later.
|
|Chinook easily triumphed over other human challengers
(...if you look over all the draws...)
, but the
|unfinished match against Dr. Tinsley left lingering doubt whether
|Chinook could claim to be the best of all time.
|
|The new research proves that Chinook is invincible in traditional
|checkers. In most tournament play, however, a match now starts with
|three moves chosen at random. In solving the traditional game, the
|researchers have also solved 21 of the 156 three-move openings,
|leaving some hope for humans.
There it is. How on earth can it be possible to
solve 21 out of 156 checkers openings instead of
156 out of 156 UNLESS they have not really
solved checkers completely? This also would
seem to explain the strange comments posted
here earlier, which suggested the same thing by
misusing the term solved to mean partly-solved.
I think the conclusion is that these guys are
confident that no human or computer will ever
beat their machine from now on, and are moving
on, satisfied with less than perfection.
-- help bot