On Thu, 19 Jul 2007, Thane Plambeck wrote:
The article confuses me. How can checkers be "solved" if only the best-play outcome is only known for pieces involving at most ten pieces?
Here's what the paper in Science says (in part): The researchers began by constructing a database of all 39,000 billion arrangements with 10 or fewer pieces on the board. In the process, they determined whether each one led to a win for black, a win for red, or a draw. They then considered the very beginning of the game, opened with a move by black, and then used a specialized search algorithm to trace out subsequent moves and show that, as the two players try to maximize their advantage, they inevitably steer the game to one of the 10-checker configurations that leads to a draw. Schaeffer credits improvements in computers for making the result possible. In fact, he suspended work from 1997 to 2001 to wait for a particular technology--the 64-bit processor--to mature. But Murray Campbell, a computer scientist at IBM's Thomas J. Watson Research Center in Hawthorne, New York, says that the researchers' ingenuity was key, too. "Without a lot of the clever ideas behind what they did, I think it would have been a number of years before technology alone could have solved checkers," says Campbell, who co-wrote the Deep Blue program that defeated chess champion Garry Kasparov in 1997. Most experts expected that checkers would eventually be proved a draw, says Jaap van den Herik, a computer scientist at Maastricht University in the Netherlands, if only because grandmaster players routinely play each other to a draw. But, he says, "if you have not proved the result, then every expectation is worth nothing." Schaeffer says he feels vindicated by the proof. In 1994, a program he developed called Chinook played the then-reigning world champion, Marion Tinsley, to a series of draws before Tinsley withdrew because of health problems and conceded. Tinsley, who is considered the best player ever and who lost only three tournament games from 1951 to 1991, died of cancer 8 months later. Some players scorned Schaeffer, he says, and even charged that the stress of the special title match had killed Tinsley. Chinook defended its crown in two subsequent matches against the next-highest-ranked player. "To this day, I still get people saying that you would never have beaten Tinsley," Schaeffer says. "The program today would never lose to Tinsley or anyone else, period." And because humans eventually make mistakes, the program should inevitably prevail in a series of games against any person, even Tinsley, for whom Schaeffer says he has "great respect." Van den Herik worries that Schaeffer's solution will accelerate the decades-long decline of tournament checkers. Meanwhile, Schaeffer is turning his computers to poker. In principle, that game can't be solved--but it can make you a lot of money.