And now, after putting dozens of computers to work night and day for 18 years--jump, jump, jump--he says he has solved the game--king me!. "The starting position, assuming no side makes a mistake, is a draw," he says. Schaeffer's proof, described today in Science (and freely available here for others to verify), would make checkers the most complex game yet solved by machines, beating out the checker-stacking game Connect Four in difficulty by a factor of a million. "It's a milestone," says Murray Campbell, a computer scientist at IBM's T. J. Watson Research Center in Hawthorne, N.Y., and co-inventor of the chess program Deep Blue. "He's stretched the state of the art." Although technological limits prohibit analyzing each of the 500 billion billion possible arrangements that may appear on an eight-by-eight checkerboard, Schaeffer and his team identified moves that guaranteed the game would end in a draw no matter how tough the competition.
Samuel's successes included a victory by his program over a master-level player. In fact, the opponent was not a master, and Samuel himself had no illusions about his program's strength. This single event, a milestone in AI, was magnified out of proportion by the media and helped to create the impression that checkers was a solved game. Nevertheless, his work stands as a major achievement in machine learning and AI. Since 1950, the checkers world has been dominated by Tinsley.
In 1992, the seemingly unbeatable World Checker Champion Marion Tinsley defended his title against the computer program CHINOOK. After an intense, tightly contested match, Tinsley fought back from behind to win the match by scoring four wins to CHINOOK's two, with 33 draws. This match was the first time in history that a human world champion defended his title against a computer. This article reports on the progress of the checkers (8 3 8 draughts) program CHINOOK since 1992. Two years of research and development on the program culminated in a rematch with Tinsley in August 1994. In this match, after six games (all draws), Tinsley withdrew from the match and relinquished the world championship title to CHINOOK,citing health concerns. CHINOOK has since defended its title in two subsequent matches. It is the first time in history that a computer has won a human-world championship.
In August 1992, the world checkers champion, Marion Tinsley, defended his title against the computer program CHINOOK. Because of its success in human tournaments, CHINOOK had earned the right to play for the world championship. Tinsley won the best-of-40-game match with a score of 4 wins, 2 losses, and 33 draws. This event was the first time in history that a program played for a human world championship and might be a prelude to what is to come in chess. This article tells the story of the first Man versus Machine World Championship match.
"The program can achieve at least a draw against any opponent, playing either the black or white pieces," the researchers say in this week's online edition of the journal Science. "Clearly ... the world is not going to be revolutionized" by this, said Jonathan Schaeffer, chairman of the department of computing science at the University of Alberta. The important thing is the approach, he said. In the past, game-playing programs have used rules of thumb -- which are right most of the time, he said -- to make decisions. "What we've done is show that you can take non-trivial problems, very large problems, and you can do the same kind of reasoning with perfection.