[link|http://machinist.salon.com/blog/2007/07/19/checkers/index.html?source=newsletter| Salon]
2007.07.19 \ufffd 14:00 EST
Chinook, the unbeatable checkers-playing computer

Scientists at the University of Alberta report that they've built an unbeatable checkers-playing computer. Their machine, Chinook, has solved checkers: It proves that if two players play perfectly, making no mistakes, the game of checkers will result in a draw.

The proof required analyzing 500 billion billion checkers positions -- 5 x 1020 -- a computational process that began in 1989 and has been running on hundreds of processors almost continuously since. Chinook now knows everything about checkers, the perfect response to any move, and the best that any human can do is drive Chinook to a draw. You can never win.

Checkers grandmasters have long suspected that [link|http://en.wikipedia.org/wiki/Perfect_play#Perfect_play| perfect play] would result in a draw, but until now, there has been no definitive proof. The first checkers-playing computer was created in 1963 by the artificial intelligence pioneer Arthur Samuel; the computer managed to win a single game against a human.

In 1989, Jonathan Schaeffer, who now heads the computer science department at Alberta, created Chinook with the aim of marshaling parallel processing and lots of storage to take on the world's best players. In 1990, Chinook became good enough to enter the checkers World Championships, and in 1992, it faced off against the world champion -- and the best checkers player who ever lived -- [link|http://en.wikipedia.org/wiki/Marion_Tinsley| Marion Tinsley]. Tinsley narrowly defeated Chinook. Then, in 1994, the pair had a rematch, but Tinsley took ill and withdrew in the middle of the game. He died of pancreatic cancer a short while later.

"The unfinished Tinsley match left the question unanswered as to who was the better player," Schaeffer and his colleagues write in this week's issue of the journal Science, where their paper is published. But now the answer is clear: "As great as Tinsley was, he occasionally made losing oversights -- he was human after all," they say. Chinook will not make mistakes, and thus becomes the greatest checkers player of all time.

[More ...]