Computer Program Can't Lose at Checkers

Jul 19, 2007
Checkers

Game over. Computer scientists at the University of Alberta have solved checkers, the popular board game with a history that dates back to 3,000 B.C.

After 18-and-a-half years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, Dr. Jonathan Schaeffer and colleagues have built a checkers-playing computer program that cannot be beaten. Completed in late April this year, the program, Chinook, may be played to a draw but will never be defeated.

The results of this research are published today in the academic journal Science.

"This is a tremendous achievement—a truly significant advance in artificial intelligence," said Dr. Jaap van den Herik, editor, International Computer Games Journal.

"I think we've raised the bar—and raised it quite a bit—in terms of what can be achieved in computer technology and artificial intelligence," said Schaeffer, chair of the U of A Department of Computing Science. "With Chinook, we've pushed the envelope about one million times more than anything that's been done before."

A self-described "awful" checkers player, Schaeffer created Chinook to exploit the superior processing and memory capabilities of computers and determine the best way to incorporate artificial intelligence principals in order to play checkers.

With the help of some top-level checkers players, Schaeffer programmed heuristics ("rules of thumb") into a computer software program that captured knowledge of successful and unsuccessful checkers moves. Then he and his team let the program run, while they painstakingly monitored, fixed, tweaked, and updated it as it went.

An average of 50 computers—with more than 200 running at peak times—were used everyday to compute the knowledge necessary to complete Chinook. Now that it is complete, the program no longer needs heuristics—it has become a database of information that "knows" the best move to play in every situation of a game. If Chinook's opponent also plays perfectly the game would end in a draw.

"We've taken the knowledge used in artificial intelligence applications to the extreme by replacing human-understandable heuristics with perfect knowledge," Schaffer said. "It's an exciting demonstration of the possibilities that software and hardware are now capable of achieving."

Schaeffer started the Chinook project in 1989, with the initial goal of winning the human world checkers championship. In 1990 it earned the right to play for the championship. The program went on to lose in the championship match in 1992, but won it in 1994, becoming the first computer program to win a human world championship in any game—a feat recognized by the Guinness Book of World Records.

Chinook remained undefeated until the program was "retired" in 1997. With his sights set on developing Chinook into the perfect checkers program, Schaeffer restarted the project in 2001.

"I'm thrilled with this achievement," he said. "Solving checkers has been something of an obsession of mine for nearly two decades, and it's really satisfying to see it through to its conclusion."

"I'm also really proud of the artificial intelligence program that we've built at the University of Alberta," he added. "We've built up 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."

On July 24 and 25 this year, Polaris, a poker-playing computer program built by Schaeffer and his U of A colleagues, will challenge two poker professionals in a $50,000 man versus machine poker world championship event in Vancouver, as part of the annual conference for the Association for the Advancement of Artificial Intelligence.

Links:

Video: More about Chinook

Chinook: http://www.cs.ualberta.ca/chinook

For more about the man versus machine poker match please go to games.cs.ualberta.ca/poker/man-machine/

Source: University of Alberta

Explore further: Professor proposes alternative to 'Turing Test'

add to favorites email to friend print save as pdf

Related Stories

Media shock stories about GameOver Zeus are not helpful

Jun 06, 2014

We need to watch out for headlines like the ones earlier this week warning that people had two weeks to protect themselves from a "powerful computer attack". It can end up scaring people who have little idea ...

Programming drones to fly like birds

Jan 15, 2014

(Phys.org) —Jack Langelaan's lab in the basement of Hammond Building is a model airplane builder's dream. In one room, graduate students Nathan Depenbusch and John Bird test algorithms on commercial flight ...

Robockey 2012: Slapshot bots

Dec 20, 2012

After a 4-week binge of laser-cutting, wiring, soldering, programming and debugging, it all came down to the moment when a tall man in a dark gray suit took the stage.

Recommended for you

Forging a photo is easy, but how do you spot a fake?

3 hours ago

Faking photographs is not a new phenomenon. The Cottingley Fairies seemed convincing to some in 1917, just as the images recently broadcast on Russian television, purporting to be satellite images showin ...

Algorithm, not live committee, performs author ranking

8 hours ago

Thousands of authors' works enter the public domain each year, but only a small number of them end up being widely available. So how to choose the ones taking center-stage? And how well can a machine-learning ...

Professor proposes alternative to 'Turing Test'

Nov 19, 2014

(Phys.org) —A Georgia Tech professor is offering an alternative to the celebrated "Turing Test" to determine whether a machine or computer program exhibits human-level intelligence. The Turing Test - originally ...

Image descriptions from computers show gains

Nov 18, 2014

"Man in black shirt is playing guitar." "Man in blue wetsuit is surfing on wave." "Black and white dog jumps over bar." The picture captions were not written by humans but through software capable of accurately ...

Converting data into knowledge

Nov 17, 2014

When a movie-streaming service recommends a new film you might like, sometimes that recommendation becomes a new favorite; other times, the computer's suggestion really misses the mark. Yisong Yue, assistant ...

User comments : 0

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.