Printer Friendly
The Free Library
23,396,934 articles and books


Check on checkers: in perfect game, there's no winner.

Computers can now play a flawless game of checkers. A calculation that began almost 2 decades ago shows that if both players make perfect moves, the game will be a draw every time. The achievement makes checkers the most complicated game to have been solved completely.

Computers have been able to beat people at checkers since 1994, when a program called Chinook won the checkers world championship. The program, written by computer scientist Jonathan Schaeffer of the University of Alberta in Edmonton, used rules of thumb to guess the best available move, a method that imitates how people play. Now, Schaeffer has removed the guesswork with a program that examined every possible position that can occur on a checkerboard to find the best move every time.

The brute-force calculation underlying o the new program was conceptually simple but logistically demanding, because checkers has approximately 500 billion billion (5 x [10.sup.20]) possible positions. Each player starts with 12 pieces on an 8-by-8 checkerboard, and he or she moves a piece by sliding it forward and diagonally one square. A piece captures an enemy by jumping diagonally across it into an open square. The last player with pieces on the board wins.

Beginning in 1989, Schaeffer used as many as 200 computers simultaneously to grind out the problem. He started with the endgame, putting just two pieces on the board and calculating every possible outcome for each position they might assume. Then he did the same for three pieces, then four, and so on up to 10. At that point, 39 trillion positions were possible.

Each step in this process took 10 times as much work as the previous step, so continuing in this way was impractical. Instead, Schaeffer turned to the beginning of a game, calculating all the positions that could result from one move, then two moves, then three moves, and so on. The program continued the game until there were only 10 pieces left, at which point it checked its database of endgames to find the outcome. Ultimately, the analysis included somewhere between 100 trillion and a quadrillion checkers positions. Schaeffer and his colleagues report their results in an upcoming Science.

"We're pushing the frontiers of what computers can solve," Schaeffer says. "If we had waited 10 or 20 years, the machines would be faster," making the problem easy. As it was, he and his team had to invent clever ways of storing and searching the data.

For example, they stored the outcomes for the 39 trillion possible positions for endgames in a mere 237 gigabytes of computer-storage space, an average of 154 positions per byte. The mathematicians are now applying these techniques to bioinformatics, looking for ways to manage the massive quantity of data generated by the sequencing of genomes.

"It's just a prodigious amount of work," says Ken Thompson of Mountain View, Calif.-based Google, who in 1983 developed the first master-level chess computer program. Thompson says that solving checkers brings computers a step closer to being able to solve more-complicated games, such as chess or go. However, he estimates that those tasks will take another 100 years to complete. Chess has about 1020 times as many positions as checkers does, Schaeffer says.
COPYRIGHT 2007 Science Service, Inc.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2007, Gale Group. All rights reserved.

 Reader Opinion

Title:

Comment:



 

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:This Week
Author:Rehmeyer, J.
Publication:Science News
Date:Jul 21, 2007
Words:538
Previous Article:Persistent prions: soilbound agents are more potent.
Next Article:Den mothers: bears shift dens as ice deteriorates.



Related Articles
A.V. FAIR TO FEATURE BIG-NAME MUSIC PERFORMERS.
PERFECT GAME MARKS 7 YEARS GIVEAWAYS, FUN SET FOR WEEKEND.
Poetic lotto: playing the game. (poetic license).
When you play, you win. (web head report).
COSTS ARE OFTEN HIDDEN UNDER OTHER CATEGORIES.
Growth through volunteering: a mother and her children received surprising rewards from meeting nursing home residents. (Feature Article).
Tips for making writing easier; part 9: improving your spelling.
Misspellings on eBay.
HOME AGAIN FAMILY FINDS DOG MISSING FOR 10 DAYS.
No hope of winning?

Terms of use | Copyright © 2014 Farlex, Inc. | Feedback | For webmasters