King me: Schaeffer solves checkers

Jonathan Schaeffer

Eighteen years in the making, artificial intelligence researcher solves the game of checkers

Checkers dates back more than 5,000 years, but after 18 years of trying, a University of Alberta professor has solved the game.

After sifting through 500 billion billion checkers positions – that’s 5 with 20 zeroes – Jonathan Schaeffer and his colleagues built a checkers-playing computer program, Chinook, which may be played to a draw but never defeated. The achievement is a milestone in computing history.

The feat, named one of the top ideas of 2007 by New York Times Magazine, shifts our understanding of the notion of human intelligence.

“Artificial intelligence really gets to the heart of what we are as human beings," said Schaeffer. "And what artificial intelligence is doing is demystifying us. Intelligence is not uniquely human or even organic. You can take a piece of silicon, put electricity in it, and you recreate many of the activities that you and I think of as intelligence."

Why it matters

Research in this field is important because artificial intelligence is all around us, from computer programs that schedule airline flights or send elevators to different floors in the most efficient way, to those used to help solve medical mysteries.

Schaeffer says, looking back, that he was “naive” to take on the challenge. But he’s demonstrated that problems once considered impossible can be solved.

“We've raised the bar quite a bit in terms of what can be achieved in computer technology and artificial intelligence," said Schaeffer. "It's an exciting demonstration of the possibilities that software and hardware are now capable of."

Schaeffer staged a computer-vs-human competition against some of the world’s best players, a good test since the program is faced with more unknowns and the prospect of receiving misinformation in the form of a bluff. The U of A’s team is, according to Schaeffer, “the premier games group in the world, definitely second-to-none. And we've built up a strong, international, truly world-class reputation, and I'm very proud of that."