Advertising

The Seattle Times Company

NWjobs | NWautos | NWhomes | NWsource | Free Classifieds | seattletimes.com

The Seattle Times

Nation & World


Our network sites seattletimes.com | Advanced

Originally published July 20, 2007 at 12:00 AM | Page modified July 20, 2007 at 2:06 AM

E-mail article     Print view

Computerized checkers player can't be beaten

With uniform pieces and diagonal moves, checkers is simple enough for a child to learn. But to achieve absolute mastery of the game, scientists...

Chicago Tribune

CHICAGO — With uniform pieces and diagonal moves, checkers is simple enough for a child to learn. But to achieve absolute mastery of the game, scientists needed to run hundreds of computers for nearly 20 years, analyzing roughly 500 billion billion scenarios.

By completing the project, a team of Canadian researchers have officially "solved" checkers, creating an unbeatable program that will choose the best move in every possible situation.

This achievement represents a major benchmark in the field of artificial intelligence, which uses games to develop complex problem-solving strategies for computers.

In 1994, a program named Chinook beat the reigning human world checkers champion, a feat that preceded Deep Blue's famous chess defeat of grandmaster Garry Kasparov by three years. But even after proving dominant over humans, finishing the calculations required to solve the game required 13 more years of research.

"Had I known 18 years ago it was this big of a problem, I probably would've done something else," said Jonathan Schaeffer, who led the project at the University of Alberta, "but once I started, I had to finish."

"It's 1 million times bigger than the biggest computation previously solved optimally," he said.

Detailed Thursday on the Web site of the journal Science, methods developed by Schaeffer's team in the process of solving the game may be applicable to other areas, such as business and biology. The resulting program proves that checkers is a "draw" game; in other words, perfect play by both players will always result in a draw.

However, checkers experts say there is no fear that the solving effort will ruin the game for traditional players, amateur or professional.

"No human can possibly memorize the billions of combinations that Dr. Schaeffer has covered," said Richard Beckwith, player representative for the American Checkers Foundation. "You still have to play as you see it, based on your own expertise and knowledge."

The entire solution includes 500,995,484,682,338,672,639 possible board configurations, according to the study, which was funded by the Canadian and Alberta governments.

Murray Campbell, a member of the original Deep Blue team, said the scope of the solution was a testament to the complexity of the game.

"Checkers is actually quite a difficult game — much more difficult than most people give it credit for," said Campbell, a research staff member at IBM's T.J. Watson Research Center, in Yorktown Heights, N.Y.

advertising

The insights gleaned from teaching computers how to play checkers can be applied to practical, computation-intensive problems. For example, Schaeffer said, the technology could be used to determine the optimal schedule for a massive construction project like the one at Ground Zero in New York.

Schaeffer co-founded a company to use the same approach to hunt for meaningful patterns in long strings of DNA and other biological building blocks.

On Thursday, the Alberta team made the new solving program available to play against on the Internet at www.cs.ualberta.ca/~chinook. Schaeffer, however, doesn't expect it to be a runaway hit.

"In some sense it's not interesting," he said. "People play games for fun, and knowing you can never beat it isn't fun."

Meanwhile, Schaeffer's group has moved on to a more profitable game: designing a poker program capable of beating even professional players. Next week, their current program, named Polaris, will challenge two pros for a $50,000 prize in Vancouver, B.C., at the Association for the Advancement of Artificial Intelligence conference.

Schaeffer speculates that human supremacy at poker remains intact — for now.

"I think humans are still better, but it's inevitable that poker will succumb to technology," he said. "Computers will be better than humans eventually, probably in less than five years."

Additional information from Los Angeles Times

Copyright © 2007 The Seattle Times Company

UPDATE - 12:42 PM
DC sniper's Muhammad's execution set for tonight

UPDATE - 12:44 PM
DOD worker assessed Fort Hood suspect months ago

UPDATE - 12:48 PM
Obama salutes Fort Hood victims, condemns murders

UPDATE - 11:24 AM
White House: Obama eyeing host of Afghan choices

UPDATE - 12:52 PM
North, South Korea clash at sea before Obama visit

Advertising

Video

Ken Auletta talks about "Googled"
Ken Auletta talks about Google with Brier Dudley at the Seattle Central Library.

Medal of Honor
Pelosi answers questions at Swedish Medical Center
Pelosi speaks at Swedish Medical Center
"Pistol" Pete Ryan
Mourners gather at KeyArena for slain officer's memorial
Procession for slain SPD officer
Election Night: Approve R-71
Election Night: Reject R-71
Election Night: Joe Mallahan

Marketplace

nwautos

2009's most fuel-efficient sedansnew
Choosing a new sedan? Weigh the impact of your choice on your wallet and on the planet.
Post a comment

Open Houses

Find this weekend's open house listings.
Or search by location:

 
Most read
Most commented
Most e-mailed
 
 
Advertising