GO IN DEPTH

# Checkers Solved

After eighteen years of work, scientists have designed an unbeatable checkers computer.

### Transcript

An invincible checkers computer. I'm Bob Hirshon and this is Science Update.

It took eighteen years and hundreds of computers, but a team of scientists has finally solved the game of checkers. Led by computer scientist Jonathan Schaeffer of the University of Alberta in Canada, they've made a checkers-playing computer program that can't possibly lose.

Schaeffer:

So for example, if the computer makes the first move of the game, you have seven different moves. And for each one of those seven moves, the computer has a response ready.

In theory, checkers has 500 billion billion possible board positions. But in order to crunch the numbers in less than a lifetime, Schaeffer's team developed an algorithm that disregards irrelevant positions and choices.

He says the algorithm could help other artificial intelligence programs find the best possible strategy for a complex task. I'm Bob Hirshon, for AAAS, the science society.

### Making Sense of the Research

Checkers is a relatively simple game: All the pieces are identical, have the same power, and move in the same way (except for "kings," which have the added ability to go backwards). The board is perfectly symmetrical. All the board squares are identical as well, and have the same function in the game.

Yet, as you heard, a checkers game can still play out in an extraordinary number of ways. It has "500 billion billion" possible board positions: numerically, that's 500,000,000,000,000,000,000. To put that in perspective, that's more than 100 times as many board positions as there are grains of sand on all the beaches on earth, as estimated by University of Hawaii mathematicians.

It's important to distinguish between a computer that has "solved" a game, and a computer that's just really good at playing it. There are many excellent chess computers, including IBM's Deep Blue. In 1997, Deep Blue famously defeated world human chess champion Garry Kasparov—but that was in a best-of-six game series, in which Deep Blue won two matches, Kasparov won one, and three matches ended in a draw. Kasparov had also previously beaten Deep Blue in several other individual games.

In contrast, Chinook, the checkers computer, cannot possibly lose to a human. As soon as its human opponent makes a bad move, the computer knows exactly how to win the game. If Chinook's human opponent doesn't make any mistakes—in other words, if the game is played perfectly by both sides—it will end in a tie. To this day, there is no such thing as an unbeatable chess computer; the game is far too complicated for even the fastest supercomputer to solve.

Getting to this point required not one, but dozens of computers, working around the clock for eighteen years, running through all sorts of hypothetical moves and counter-moves. Even so, Schaeffer says that he wouldn't have lived to see the solution if he hadn't figured out a shortcut. As you heard, his team programmed the computers to stop every time it found a winning move from a hypothetical board position.

Here's an example: Suppose that starting from a certain board position, the computer's opponent makes a dumb move. And suppose that the computer has ten possible responses—let's call them options 1 through 10—based on the board spaces that are open at the time. And suppose, further, that it figures out that it can eventually win the game if it chooses option 1. If so, the computer won't even bother analyzing the other nine choices; it just decides that if it ever finds itself in this board position, it will choose option 1. As a result, Chinook will never have to consider any board position that results only from choosing options 2 through 10, since that board position will never occur as long as Chinook is playing.

Using this technique, Schaeffer's team reduced the actual number of board positions that Chinook had to analyze from 5 x 1020 to 5 x 1014: in other words, they made the problem a million times simpler. And it still took them eighteen years to solve the game! Imagine how much more difficult it would be to solve chess, which has six different kinds of pieces, each of which moves in a different way.

Why do scientists bother doing this sort of thing? Well, solving a game like checkers, with very clearly defined rules, helps them design artificial intelligence systems that can tackle difficult problems. Schaeffer says that the time-saving trick it built into Chinook might be applied to solving real-world problems as well. For example, he cites the construction of something large, like a space shuttle, which may require the efforts of hundreds of scientists and skilled laborers, and the purchase of a wide variety of very specific materials along a very specific timeline. An artificial intelligence program might be able to come up with a master plan for the job that makes the best possible use of time and money.

Now try and answer these questions:

1. What does it mean to "solve" a game?
2. What was the key to the checkers-solving algorithm? How did it make the solution simpler?
3. Can you guess what other games might have already been solved?
4. In what other real-world tasks might it be useful to use a computer that can identify the best possible strategy?

You may want to check out the August 17, 2007, Science Update Podcast to hear further information about this Science Update and the other programs for that week. This podcast's topics include: dinosaurs and their rivals, a computer that solves checkers, the placebo effect and the brain, keeping fruits and vegetables fresh, and the evolution of walking and talking.

For Educators

Learn more about Chinook, and play against it yourself, at Schaeffer's site, Chinook: World Man-Machine Checkers Champion.

In the NY Times Learning Network's lesson plan, It's Alive! Learning About How Artificial Intelligence Affects Our World, students will learn about the developing field of artificial intelligence and create a blueprint for their own devices based on artificial intelligence technology.

The National Geographic news article, "Robot Scientist" Said to Equal Humans at Some Tasks, profiles a robot that can formulate hypotheses, design experiments, and interpret results on par with the best of its human counterparts.

#### Related Resources

Talking Lights
6-12 | Audio
Risk Remedies
6-12 | Audio
Precise Negotiations
6-12 | Audio