[MLUG - DISCUSSION] Champion at Checkers That Cannot Lose

[Mike Miller <EMAIL:PROTECTED>]

This is an interesting story (below).  The amazing part is that a math 
prof named Marion Tinsley was undefeated World Champion in checkers for 42 
consecutive years.  In 1992, the computer did beat him in two games, but 
Tinsley won the match, 4-2-33 (that's 33 draws!).  They were to battle it 
out again two years later, but after 6 draws Tinsley got sick and dropped 
out. It turned out that he had cancer and it killed him 7 months later. 
So he never lost a match to the machine.  But the big news today is that 
it has been proven that the computer program will always either win or 
draw every checkers game it plays, no matter how good the opponent, be it 
human or machine.  Tinsley was pretty close to achieving this ideal but he 
still made a few rare mistakes and could lose (in 40+ years of tournament 
play he lost five games to people and two games to the computer).  --Mike

--------------------------------------------------------------------------


http://www.nytimes.com/2007/07/20/science/20checkers.html

N.Y. Times
July 20, 2007

Champion at Checkers That Cannot Lose to People

By KENNETH CHANG

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.


Copyright 2007 The New York Times Company

_______________________________________________
discussion mailing list
EMAIL:PROTECTED
http://mlug.missouri.edu/mailman/listinfo/discussion