Machinist
Inside tech: Gizmos, people and big ideas

2007.07.19 • 14:00 EDT

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 10²⁰ -- 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 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 -- 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.

The research makes checkers "the most challenging popular game to be solved to date, roughly one million times more complex that Connect Four," which was solved in 1989 (if two players play Connect Four perfectly, the first player will always either win or draw).

Their work also highlights the utility of raw computing power in intense artificial intelligence applications. In the early days of A.I. research, Schaeffer and his colleagues note, scientists often tried to make computers mimic human thought. But this approach led to difficulties, and they found that "human-like strategies are not necessarily the best computational strategies."

A better method for solving complex tasks like checkers, A.I. theorists discovered, was "brute force" -- rather than trying to master human strategies, computers would rely on "limited knowledge" of the specifics of the game, and instead use superior processing power to search and analyze all possible moves. That's the approach taken by chess-playing computers -- such as IBM's Deep Blue, which beat champion Gary Kasparov in 1997 -- and it's also what Chinook does with checkers.

That their machine managed to solve the game, the researchers say, "provides compelling evidence of the power of limited-knowledge approaches to artificial intelligence." This method will become even more powerful as computers themselves get faster and cheaper, they note. But solving games as complex as chess is still far off.

"Checkers has roughly the square root of the number of positions in chess (somewhere in the 10⁴⁰-10⁵⁰ range)," they write. "Given the effort required to solve checkers, chess will remain unsolved for a long time, barring the invention of new technology." But disk-flipping game othello -- solving that is possible, they say. The effort "will require considerably more resources than were needed to solve checkers," but soon we'll have an unbeatable othello-playing machine, too.

You can play against Chinook here.