Chinook
One Jump Ahead One Jump Ahead - the story about Chinook, is available from Springer-Verlag. Read some reviews of the book.

Chinook is the World Man-Machine Champion, the first computer program to win a human world championship. This feat is recognized by the Guinness Book of World Records.

Breaking News!

We have achieved a milestone in our quest to solve the game of checkers. The White Doctor opening (10-14 22-18 12-16) has been solved: it is a draw. This means that our program when playing Black (the weak side) will never lose. When playing White, our program will never lose and may win (if the opponent makes a mistake). The solution to the White Doctor opening will be made available on the web in the coming weeks.

The result of the White Doctor opening has been known since December, but we had to convince ourselves it was correct. We have implemented two solvers using different algorithms and used them to verify that each other is correct. This process was useful since it allowed us to find some small hard-to-find bugs (that did not affect the final result). Also, we had to solve the graph-history interaction problem (GHI). Most game-playing programs ignore this obscure phenomenon. The reality is that in games with repeated positions such as chess and checkers, the classic search algorithms (including alpha-beta and proof number search when used with a transposition table) are not guaranteed to return a correct proof. Even though the GHI problem is relatively rare, any proof that does not consider this problem cannot be called a proof. We have successfully solved this problem and our solution is GHI free.

We began the effort to solve checkers in 1989 with the construction of the 4-piece checkers endgame database (7.3 million positions). Today we have the complete 9-piece databases and the 5-piece versus 5-piece subset of the 10-piece database (13 trillion positions). These computations took a "backwards" approach, starting at the end of the game and moving towards the start of the game. We also used a forward search, which began computing at the start of the game, searching until an endgame database position is encountered.

When will checkers be solved? We have one opening that has been solved and the proof is being verified, and a third opening has just been started. There are just under 200 3-move checkers openings and, ideally, we would like to solve all of them. However, to solve checkers for the initial starting position (i.e. with no moves made), only 50ish openings need to be computed (alpha-beta cutoffs eliminate most of the openings). Solving subsequent openings will not take as long as the first one did. The computations will speed up for several reasons:

  1. Some of the validation techniques used to verify that our algorithms are working are no longer needed.

  2. More endgame databases. The six-piece versus 4-piece database will soon be in production use (another 14 trillion positions). Also, the computation of the six-piece versus 5-piece database is starting soon using a new algorithm that calculates only the useful part of the database.

  3. Data reuse. Openings transpose into each other. Each additional opening increases the chances for reusing the results of one opening on another. The only obstacle remaining to completely solving checkers is compute cycles. With the current resources we are using, finishing checkers will take a few years. With enough resources, the game could be solved in a few months. Contact jonathan@cs.ualberta.ca if you have a cluster of computers with at least 3 GB of RAM and 300 GB of local disk per machine sitting idle!

Over the years, many people have contributed to the project. I want to thank all of them for their outstanding contributions:

Solver: Yngvi Bjornsson, Neil Burch, Andreas Junghanns, Akihiro Kishimoto

Graph-history interaction solution: Akihiro Kishimoto, Martin Mueller

Endgame databases: Yngvi Bjornsson, Neil Burch, Joe Culberson, Brent Gorda, Brent Knight, Robert Lake, Paul Lu, Steve Sutphen, Ken Thompson

Verification of the 7- and 8-piece databases: Gil Dodgen and Ed Trice

Computing resources: Department of Computing Science (University of Alberta), Lawrence Livermore Laboratories, MACI, WestGrid

Funding Agencies: NSERC, iCORE, University of Alberta

Jonathan Schaeffer

August 2, 2004


Chinook
Please take a moment to sign or view the Chinook guestbook.

* About Chinook
* Authors
* Publications
* Endgame Databases
8-piece databases available for download!

May 24: 10-piece databases completed!

* Matches and Tournaments
* WWW Wall of Honor
* 1994 Chinook-Tinsley checkers match. (by Jim Propp)
* One Jump Ahead - the story about Chinook.
Checkers
* American Checker Federation
* British Draughts Federation
* The International Checker Hall of Fame
* Grandmasters and Masters
* Matches and Tournaments
* Commercial Checker-Playing Programs
* Checkers software (free!)
* Collections of games
* For sale
* Computer Draughts and Checkers Page
* Jim Loy's Checkers Pages
* VOG Checkers Club
* GameColony.com Free Checkers and Chess - Chat & Play
* TripleJump Checkers
* Checkers Programs


Chinook and Checker
News Briefs
Chinook WWW Awards

*
Search the Chinook WWW pages:
 

Visitor number: visitor counter
[University of Alberta]
University of Alberta
[Department of Computing Science]
Computing Science
[Chinook]
Chinook

Copyright © Department of Computing Science.
All rights reserved.