Featured Research

from universities, journals, and other organizations

Scientists Solve Checkers

Date:
July 20, 2007
Source:
University of Alberta
Summary:
Game over. Computer scientists 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,scientists have built a checkers-playing computer program that cannot be beaten.

Jonathan Schaeffer has been working on the checkers puzzle for 18 years.
Credit: Image courtesy of University of Alberta

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.

"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.

More information is available at http://www.cs.ualberta.ca/~chinook

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


Story Source:

The above story is based on materials provided by University of Alberta. Note: Materials may be edited for content and length.


Cite This Page:

University of Alberta. "Scientists Solve Checkers." ScienceDaily. ScienceDaily, 20 July 2007. <www.sciencedaily.com/releases/2007/07/070719143517.htm>.
University of Alberta. (2007, July 20). Scientists Solve Checkers. ScienceDaily. Retrieved April 16, 2014 from www.sciencedaily.com/releases/2007/07/070719143517.htm
University of Alberta. "Scientists Solve Checkers." ScienceDaily. www.sciencedaily.com/releases/2007/07/070719143517.htm (accessed April 16, 2014).

Share This



More Computers & Math News

Wednesday, April 16, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Twitter, Apple Social Data Purchases Likely to Spur More Mergers and Acquisitions

Twitter, Apple Social Data Purchases Likely to Spur More Mergers and Acquisitions

TheStreet (Apr. 16, 2014) The social media data space is likely to see more mergers and acquisitions following Twitter Inc.'s acquisition of tweet analyzer Gnip Inc. on Tuesday and Apples Inc.'s purchase of Topsy Labs Inc. back in December. One firm in particular, the U.K.'s DataSift Inc., could be on the list of potential buyers. Among other social media startups that could be ripe for picking is Banjo, whose mobile app provides aggregated content by topic and location. Banjo could also be a good fit for Twitter. Video provided by TheStreet
Powered by NewsLook.com
Google Patents Contact Lens Cameras; Internet Is Wary

Google Patents Contact Lens Cameras; Internet Is Wary

Newsy (Apr. 15, 2014) Google has filed for a patent to develop contact lenses capable of taking photos. The company describes possible benefits to blind people. Video provided by Newsy
Powered by NewsLook.com
NYPD Ends Muslim Surveillance Program

NYPD Ends Muslim Surveillance Program

AP (Apr. 15, 2014) The New York City Police Department has ended a program that once kept tabs on the city's muslim population. (April 15) Video provided by AP
Powered by NewsLook.com
Images Of Rumored Amazon Smartphone Leaked

Images Of Rumored Amazon Smartphone Leaked

Newsy (Apr. 15, 2014) BGR has leaked images of what could be Amazon's smartphone. The outlet's been right about Amazon leaks before. Sources expect an announcement in June. Video provided by Newsy
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:
from the past week

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins