Chess Forum / General Topics / July 2007

>David Richerby 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.

|ABSTRACT
|
|Published Online July 19, 2007
|Science DOI: 10.1126/science.1144079
|Submitted on April 20, 2007
|Accepted on July 6, 2007
|
|Checkers Is Solved
|Jonathan Schaeffer, Neil Burch, Yngvi Bjoson,
|Akihiro Kishimoto, Martin Mu1ler, Robert Lake,
|Paul Lu, Steve Sutphen
|
|1 Department of Computing Science, University of Alberta,
| Edmonton, Alberta T6G 2E8, Canada.
|
|* To whom correspondence should be addressed.
|Jonathan Schaeffer , E-mail: jonathan{at}cs.ualberta.ca
|  
|The game of checkers has roughly 500 billion billion 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, 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.

|    
|News of the Week
|Science 20 July 2007:
|Vol. 317. no. 5836, pp. 308 - 309
|DOI: 10.1126/science.317.5836.308a
|
|COMPUTER SCIENCE:
|Program Proves That Checkers, Perfectly Played, Is a No-Win
|Situation
|
|Adrian Cho
|
|If two players face off at checkers and neither makes a wrong
|move, then the game will inevitably end in a draw. That's the
|result of a proof executed by hundreds of computers over nearly
|2 decades and reported online by Science this week

| NEW YORK TIMES
|
|Champion at Checkers That Cannot Lose to People
|By KENNETH CHANG
|Published: July 20, 2007
|
|Checkers has been solved.
|
|A computer program named Chinook vanquished its human competitors at
|tournaments more than a decade ago. But now, in an article published
|Thursday on the Web site of the journal Science, the scientists at the
|University of Alberta who developed the program report that they have
|rigorously proved that Chinook, in a slightly improved version, cannot
|ever lose. Any opponent, human or computer, no matter how skilled, can
|at best achieve a draw.
|
|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.
|
|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.
|
|"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.
|
|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 at http://www.cs.ualberta.ca/~chinook/play/. (It is
|limited to 24 games at a time.)
|
|The earlier incarnation of Chinook, relying on artificial intelligence
|techniques and the combined computing power of many computers, placed
|second in the 1990 United States championship behind Marion Tinsley,
|the world champion, who had won every tournament he had played in
|since 1950.
|
|That achievement should have earned Chinook the right to challenge Dr.
|Tinsley, a professor of mathematics at Florida A&M University, for the
|world championship, but the American Checkers Federation and the
|English Draughts Association refused to sanction a match. After much
|wrangling in the checkers world, Dr. Tinsley and Chinook battled for
|the man-versus-machine checkers title in 1992.
|
|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, 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.
|
|Alexander Moiseyev, the current world champion in what is known as
|three-move checkers, has never faced Chinook. He said he used
|computers to study and analyze games but did not play against them,
|and he readily conceded that people were no longer worthy competitors
|for computers.
|
|"This time is over today," he said. "It doesn't bother me." The next
|game Dr. Schaeffer hopes to conquer is poker, which is harder to
|solve, because players do not have complete knowledge of their
|opponents' positions. Next week, his program, Polaris, will take on
|two professional poker players in Texas Hold 'Em for the $50,000
|man-versus-machine world championship.
|
|Soon, computers may not just be winning games, but taking people's
|money, too.

|INFORMATION WEEK
|Canadian Programmers Claim Their Checkers Program Is Unbeatable
|
|Software developers at the University of Alberta say they've 'solved'
|checkers by developing a program that's guaranteed to never lose.
|
|By K.C. Jones
|InformationWeek
|July 20, 2007 11:58 AM
|
|Software developers in the department of computing at the University
|of Alberta say they've perfected a checkers program so powerful that
|human competitors can never win.
|
|The developers said the best players can do against the improved and
|"unbeatable" Chinook is to end the game in a tie.
|
|"Checkers is solved," they pronounced in a statement on their Web
|site.
|
|From the starting position, black (which moves first) can only draw
|against a perfect opponent, and white (which moves second) is also
|guaranteed a draw, regardless of what black plays as the opening move,
|developers said.
|
|"This is the largest non-trivial game of skill to be solved," the
|developers said. "It is more than one million times bigger than
|Connect Four and Awari."
|
|Connect Four and Awari were the biggest and most complex games solved
|before Chinook became unbeatable at traditional checkers, called
|draughts in England. A traditional game of checkers allows for
|three-move openings and about 500 billion total board positions for
|the duration of the game. The developers' claims come from a computer
|proof, not a mathematical one.
|
|Developers began work on the Chinook program in 1989 in an attempt to
|build a program that could beat the human World Checkers Champion.
|Chinook suffered a narrow loss to the world checkers champion in 1992,
|but limited the champion to draws in 1994. Two years later, Chinook
|proved stronger than people and retired. Chinook won the World
|Man-Machine Championship, three years before the Deep Blue chess
|match, marking a milestone in the history of artificial intelligence.
|
|Those who want to challenge Chinook can test their mettle online.

>Interesting.  This "strategy" was never mentioned in
>the article I read; that article stated flatly that the
>"scientists" were moving on, having settled on a
>partial solving of checkers, and placing the blame
>for their partial failure on a lack of computer power.