Solving checkers a great idea

December 17th, 2007

Jonathan Schaeffer 'solved' checkers this year and his achievement has been named one of 2007's top ideas by the New York Times.

The Times, which lists 70 of the ideas that "helped make 2007 what it was," zeroed in on Schaeffer's solving of the game of checkers.

"They called and interviewed me, and they said the list was the year's most interesting, innovative and quirky ideas," said Schaeffer, chair of the U of A Department of Computing Science and Canada Research Chair in Artificial Intelligence. "But I didn't know if mine was interesting, innovative or quirky."

Schaeffer's idea was chosen for the Times article by reporter Clive Thompson, who wrote, "After running a computer program almost nonstop for 18 years, (Schaeffer) had calculated the result of every possible endgame that could be played, all 39 trillion of them. He also revealed a sober fact about the game: checkers is a draw. As with tic-tac-toe, if both players never make a mistake, every match will end in a deadlock."

The implications obviously go beyond a game.

'It's personal in the sense that artificial intelligence really gets to the heart of what we are as human beings," he said. "It's a very intimate topic. And what artificial intelligence is doing is demystifying us."

Schaeffer points to the 'best of' lists that cropped up around the turn of the millennium that named Gutenberg's printing press, Einstein's theory of relativity and the Wright brothers' first flight as the most amazing advances in human history. Schaeffer says such lists often miss one of the biggest discoveries.

"We think of ourselves as unique, but one of the greatest, most profound revelations of all time is the realization that human intelligence could be achieved using a silicon ship, DNA computing, quantum computing," he said.

"Intelligence is not uniquely human - or even organic. A piece of silicon - these are rocks out of the ground - you put electricity in it and you recreate many of the activities that you and I think of as intelligence. It's very profound, it's very deep. Some people would even say it's religious."

Artificial intelligence is an unavoidable part of modern life, said Schaeffer. One hundred years ago, the Wright brothers were just figuring out the details of human flight, now computers not only design and build the airplanes, but they're flying them, he pointed out.

But, in the end, it's not really about checkers, said Schaeffer.

"Clearly we're not going to solve checkers and it's going to revolutionize technology," he said. "One of the biggest things - and this is what other people tell me - is that it opened their eyes to the fact that what they thought was big, was not so big."

The sheer volume of calculations required to solve the board game is about 10 to the 20th power, roughly equivalent to emptying the Pacific Ocean with a teaspoon.

"Big problems were like 10 to the 13th, 10 to the 14th. This is bigger by, like, a factor of a million. Where checkers has the impact, is it opens out eyes that really big problems are not so big."

Source: University of Alberta