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:
Some of the validation techniques used to verify that our algorithms
are working are no longer needed.
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
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 email@example.com 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
August 2, 2004