Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Published Online July 19, 2007
Science DOI: 10.1126/science.1144079

Research Articles

Submitted on April 20, 2007
Accepted on July 6, 2007

Checkers Is Solved

Jonathan Schaeffer 1*, Neil Burch 1, Yngvi Björnsson 1, Akihiro Kishimoto 1, Martin Müller 1, Robert Lake 1, Paul Lu 1, Steve Sutphen 1

1 Department of Computing Science, University of Alberta, Edmonton, Alberta T6G 2E8, Canada.

* To whom correspondence should be addressed.
Jonathan Schaeffer , E-mail: jonathan{at}cs.ualberta.ca

The game of checkers has roughly 500 billion billion possible positions (5 x 1020). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: perfect play by both sides leads to a draw. This is the most challenging popular game to be solved to date, roughly one million times more complex than Connect Four. Artificial intelligence technology has been used to generate strong heuristic-based game-playing programs, such as DEEP BLUE for chess. Solving a game takes this to the next level, by replacing the heuristics with perfection.


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
Intuition and Deliberation: Two Systems for Strategizing in the Brain.
W.-J. Kuo, T. Sjostrom, Y.-P. Chen, Y.-H. Wang, and C.-Y. Huang (2009)
Science 324, 519-522
   Abstract »    Full Text »    PDF »


To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)