MatheMUSEments

Articles for kids about math in everyday life, written by Ivars Peterson for Muse magazine.

November 5, 2007

King Me!

It's easy to learn to play checkers, but it takes a lot of practice to become an expert player, and no one has ever played checkers flawlessly—until now. This spring, a computer program became the first perfect checkers player ever. Tic-tac-toe, connect four, and other simple games were "solved" long ago, but checkers is the first of the complex games to fall.


Computer scientist Jonathan Schaeffer of the University of Alberta, who describes himself as an "awful" checkers player, has been studying the game for nearly 20 years. Schaeffer's initial goal was to create a computer program that played checkers so well that it could beat the human world champion. Named Chinook, the program took the title in 1994, becoming the first computer program to win a human world championship in any game.

Schaeffer's next goal was to turn Chinook into a perfect player. This meant figuring out the best move to make given any of the 500 billion possible positions in the game. It took as many as 200 computers, running for years, to work out all the possibilities, but he and his coworkers finally finished the job in 2007. With this information now at its disposal, Chinook plays perfectly—and never loses—not because it is smart but because it can check the possible outcomes for every move it makes.

If you want to learn more about Chinook or even play against the program, go to www.cs.ualberta.ca/~chinook/.

Schaeffer's team also proved that if two players both play perfectly, the game always ends in a draw. Top checkers players had long suspected this, but the researchers proved it. This doesn't mean that checkers is no longer fun. You're highly unlikely to come across anyone who plays perfectly—unless you're playing Chinook. Then, you really don't have a chance.

The Rules of Checkers

Two players take turns moving pieces on an eight-by-eight checkerboard. Each side starts off with 12 checkers. Checkers move diagonally forward one square (staying on the same color square). You can capture (and remove) an opponent's piece by "jumping" your checker over it and landing in an empty space. When a checker reaches the far end of the board, it is "crowned" and becomes a king. Kings also move diagonally, but they are allowed to go backward as well as forward. A player loses when he or she has run out of pieces or has no legal moves left.


Muse, November/December 2007, p. 36.