Checkers has been solved. This headline has appeared in many news articles in the past few days, as Dr. Johnathan Schaeffer announced on July 19, 2007, that his team at University of Alberta has completed their quest to develop a rigid proof that checkers is, with perfect play on both sides, a drawn game.

This proof is a monumental achievement in computer science and took years of work to develop. The proof is non-trivial, both in complexity and quality; Dr. Schaeffer's team not only proved that checkers is a draw, they've shown how to do it. Given that you have a very powerful computer, an enormous database, and some sophisticated computer code, you can draw all your games from now on.

What's our reaction to this? As computer literates ourselves, we're most impressed with Dr. Schaeffer's work. As checker players and fans, we can only say, "Let's play checkers." In fact, this week your editor himself was quoted in Nature Magazine, when asked about the impact of this new proof on the checker playing public, as saying, "People will keep right on playing checkers."

And, of course, they will.

We note that, while checkers is now known definitively to be a draw, this coming week's U.S. National Tournament hasn't been canceled, and we in fact predict with great confidence that the tournament will produce some really fine games of checkers. Too, we have no plans to discontinue publishing The Checker Maven as we still think there are plenty of checker topics worthy of column space.

While the computer has had a profound influence on our game, mostly (but not entirely) for the good, checkers is in the end a game for people. Real, live people from all walks of life play checkers, and they won't stop now. From country picnic tables all the way to Las Vegas tournament halls, checkers will go on.

A draw? Yes, in theory, the game is a proven draw. In practice, it's still a great deal of fun and a tremendous intellectual challenge, and that's not going to change.

Editor's note: The photo at the top of this article is a file photo and is not of Dr. Schaeffer and his laboratory.

Here's an astronomy question for our checker fans:

Q. What's denser than the galactic core and has to do with checkers?
A. Ed Gilbert's 10-piece endgame database.

Completed in just under a year (admittedly somewhat faster than the Milky Way galaxy took to reach its present form), and containing the proverbial billions and billions of endgame positions, Ed Gilbert's 10-piece endgame database is dense, rich, and full of checker content. It's the very first product of its type to become available for home use by serious checker enthusiasts, and it is destined to change and enhance top-level checker play as leading players begin to use it for analysis and study.

The concepts involved seem complex on a nearly cosmological scale, so to bring things down to earth, The Checker Maven interviewed database creator Ed Gilbert by email. Here's what Ed has to say about the database and other topics of interest.

CM: Tell us a little bit about the 10 piece database.

Ed: It's a database which gives the exact win, draw, or loss value of every checkers position having from 2 to 10 pieces with up to 5 pieces on a side. Checker programs have used endgame databases for quite a while. What makes this one somewhat newsworthy is its size and the tremendous increase in playing strength that it gives to Kingsrow. Up until about 2001 the largest endgame database that was available to the public was for 6 pieces. At that time several commercial programs introduced 8 piece databases, and free programs like Cake and Kingsrow soon followed with 8 piece databases computed by Martin Fierz and Jonathan Schaeffer.

The number of checker positions that are possible increases rapidly with the number of pieces on the board, as does the size of these databases and the time it takes to compute them. A 6-piece database can be computed in a couple of hours, and easily fits on a 64mb flash drive. An 8-piece database takes a couple of weeks and occupies about 4GB. It is only within the last few years that anyone has been able to build a 10-piece database. Jonathan Schaeffer was able to complete the first 10-piece database in 2003 using the resources that were available to him as a department head at the University of Alberta. He estimates that it took him 15 computer years to build it. The Kingsrow 10-piece database is the first to be available to the general public.

CM: How long did it take you to develop the database? How did you go about it? What would you estimate you've invested in time and expense?

Ed: I started building it in August, 2004, and finished 11-1/2 months later. Before starting, I spent several months working on the program that would build it and optimizing its performance to run as quickly as possible. I wanted to build the database in one year, and I did not want to buy 15 computers to do it! I also had to work out some technical difficulties in building some of the very largest subdivisions. Schaeffer had available to him a powerful 64-processor Silicon Graphics workstation with 32gb of RAM. I had to work out schemes to build everything on my home PCs with only 2gb. I ended up building and using 4 computers to do most of the database computations. By building them myself I was able to save some money, and also get exactly what I needed, which was computers with lots of RAM and the largest hard drives available, but without any other extras normally purchased with a new PC. I didn't need keyboards, mice, speakers, or displays, since these machines were only used to compute databases 24 hours a day. There is a more detailed account of my building the database at my web site here:

http://pages.prodigy.net/eyg/Checkers/10-pieceBuild.htm.

It describes some of the computer science involved, as well as my experiences maintaining the equipment and keeping the whole thing running for a year.

CM: How do you think the database will influence checker play and analysis?

Ed: I think it will help identify some errors in published play, and it will allow many difficult endings that have up to now been left as 'probable loss' or 'probable draw' to be conclusively resolved. Many tournament players like to review their games and see if they missed a win, if their opponent missed a win, or if they lost, identify the exact losing move. The 10pc db is a tremendous help with this type of analysis. There is also a small group of analysts that like to try to find draws in absurdly difficult opening lines. I admit to doing some of this myself, although strictly using the computer, since my own crossboard analytical skills are not very strong. I've been maintaining a specialized 10-piece opening book in which I've accumulated new play in ballots like the Black Hole, Twilight Zone, Gemini, Wilderness, Double Cross, Octopus, etc. This opening book is available on the web here:

http://pages.prodigy.net/eyg/Checkers/BH_draws.htm.

CM: Although we know that overall you're won't even come close to making a profit, nonetheless in absolute dollar terms the database is, at $160, a non-trivial investment. What do you think is the market?

Ed: I think the number of people that will purchase this is quite small, due to the declining population of serious checkers players. I will be surprised if the money made from selling 10 piece databases will cover the cost of even one of the computers that I used to build it. This is not a money making business! Selling the database allows me to get it to the people that really want it and can make good use of it. As far as the price goes, I think it's an incredible bargain. If you are serious about playing checkers, there is nothing else that comes close to giving you the information it provides. You cannot obtain one of these anywhere else in the world. If you wanted to build one yourself, assuming you had the skills to do it, you'd have to buy a bunch of computers and run them for a very long time. Then you'd have to figure out how to integrate it into a checkers program, which means you'd have to write your own checkers program...

CM: We understand that the database needs some hefty computing power for effective use. Can you tell us something about that?

Ed: A few years ago this was true, but by today's standards the requirements are no longer "hefty." Basically you need a sufficient amount of RAM to cache portions of the database during a search, and you need enough free hard drive space to store it. That means you need about 2gb of RAM and about 250gb of free disk space. There is a way you can use the database with less; you can read the details at the Kingsrow web site. If you're using an older machine that needs more of these things, it's likely you can add them quite inexpensively. A coworker at the office just bought 2gb of RAM for $75, and 320gb hard drives are selling for around that same amount.

CM: Whenever large leaps are taken in computer checkers, such as represented by your database, there is inevitable discussion of "solving" checkers once and for all. Indeed, a university team is working on that very thing. Do you think checkers will be "solved" and how do you think that might affect human play?

Ed: Apparently Schaeffer is getting close to proving the win/loss/draw value of all of the 3-move ballots. This will be a nice milestone in computer science and the culmination of perhaps 10 years of work by his team. I expect that they will simply confirm what people have already known about the ballots for a long time, and it will have very little if any effect on human play. However there always is a small possibility that they will find a draw in one of the ballots thought to lose. If this occurs then it will be big news for 3-move tournament players, and also for that other group I mentioned that likes to look for draws in absurdly difficult opening lines.

CM: You are a world-class checker programmer and database developer. Can you tell us a little about your background and interests? What do you do as a "day job" and what do you do for fun?

Ed: For about the last 27 years I've been working for what used to be called Hewlett-Packard, until they spun off their electronic instrument business as a separate company a few years ago, and now I work for that company, Agilent Technologies. I work in R&D as an engineer developing new products. I'm married, with 3 daughters, two of whom have finished college, while the youngest just turned 20 and has a couple of years left to go. I do a lot of bicycling on my road bike (on an Italian steel frame that I built into a complete bike about 15 years ago), and I've also been a runner and regular lap swimmer for over 35 years. When I was younger I used to race in running road races and triathlons, and now I keep up these activities simply for the enjoyment and the exercise.

CM: Can you tell our readers how they might decide if they want the database, and how they might obtain it if so?

Ed: If you're serious about the game of checkers, and you want to have the most powerful tool for analyzing positions that is available anywhere, then you want the 10-piece database. All the information that you need to obtain it, including PC requirements and installation instructions, are at the Kingsrow web site:

http://pages.prodigy.net/eyg/Checkers/KingsRow.htm.

The Checker Maven thanks database developer Ed Gilbert for granting us this interview, and repeats Ed's statement that if you're a serious checker player, the 10-piece database is a true "must have" product. We're getting our own copy as soon as we possibly can.

Ed Gilbert has set his KingsRow engine and 10 piece endgame database on the path of more deep discoveries as he continues to mine interesting problems. Here's a sample of some of the things Ed has unearthed:

• As long suspected, the alternate jump in the Single Corner (11-15 22-18 15-22 26-17) is a draw. Ed cautions us that his findings don't constitute absolute proof, but his new computer opening book shows a draw against virtually all lines of attack.
• Elbert Lowder's 13-17 defense in the Will-o-the-Wisp is a very narrow draw.
• The new book contains some interesting Switcher lines like play after 11-15 21-17 9-13 25-21 8-11 23-18 4-8.
• Ed has searched for alternate lines in the Double Cross. The book confirms that after 9-14 23-18 14-23, then 26-19 is indeed a loss. Also, after 9-14 23-18 14x23 27x18 12-16, then only 18-14 draws, and all others are almost certain losses.
• How about drawing lines in the dreaded Edinburgh? The book shows that after 9-13 22-18 6-9 18-14 xx, there are three moves to draw: 12-16, 11-15, and 1-6.
• The book makes an end of this "ash can" line: 10-15 22-17 15-19 24x15 11x18 23x14 9x18 26-23 6-9 23x14 9x18 30-26 5-9 17-14 1-5 21-17 9-13 25-21 3x22 26x17.
• And similarly, the book finishes off this GAYP line: 11-15 24-19 15x24 27x20 9-14 23-19 8-11 26-23 11-15 22-18 15x24 18x9.
• Ed looked into the 27x20 jump in the Waterloo opening: 11-15 23-18 8-11 18-14 9-18 24-19 15-24 22-8 4-11 and now if 27-20 instead of the normal 28-19, the draw is tough, but it is there.
• Perhaps most exciting of all, Ed has found five new drawing lines in the Black Hole!

See for yourself; you can download this special opening book, for use with KingsRow and CheckerBoard, from Ed's web site here.

Thanks to both Ed Gilbert and Brian Hinkle for providing us with input for this story.

Martin Fierz recently released a new, major upgrade to his CheckerBoard interface, and it's a gem.

This new release features improvements in appearance, options, and analysis. If you haven't yet upgraded, you should do so at once: visit Martin's blog for a download link and installation instructions.

Now, this new gem does have a couple of rough edges related to installation. We didn't succeed with an in situ upgrade, and ended up doing a new installation to a new directory, necessitating copying our databases from the old directory to the new. Not a big deal, but you might save yourself some frustration and just go with a new install.

You also need to be certain that your engines (e.g., KingsRow) are compatible with this latest release, and that they are placed in the new 'engines' subdirectory. Ed Gilbert has released KingsRow 1.15q, fully compatible with CheckerBoard 1.64; there is a link on Martin's site. Be sure to upgrade!

But believe us when we say that these minor extra troubles are worth it.

The new CheckerBoard gives you a choice of languages: English, Spanish, German, and Italian are currently available (though surprisingly, not French). There is also a choice of board and piece images (developed and contributed by Ron Carney). No longer must you bear with the flat circles of previous versions; now you have a choice of an elegant 'official' set or a stunning metal and marble set (the old circle set is still there if you really can't bear to part with it). Click here for screenshots; to preserve detail these are rather large and we've put them on a separate page.

Game database (PDN) options are improved, and there is now the possibility of analyzing a complete multi-game PDN file in one single "batch" run. (Depending on your computer and the size of the file, this could occupy your machine for hours or days!)

There have been some meaningful technical improvements; at least subjectively, it seems that the large endgame databases load faster, and information provided by the program as to what it's doing is now more complete and useful. The overall "feel" of the program is snappy and quite pleasant.

There is also a sound option that we haven't been able to make work as yet, though we assume this provides audio feedback for piece moves.

In this release, Martin has done a fine job of balancing utilitarian features, performance improvements, and aesthetics, without going down the insidious path of bloatware and useless chrome. CheckerBoard is easily overall the finest interface available today, with a superb choice of world-class playing engines to support it. Upgrade now if you have an older version; or if you haven't yet discovered CheckerBoard, there's no time like the present.

In the 1930s, the 3-move restriction style of play was introduced as a follow-on to 2-move restriction and the earlier go-as-you-please (unrestricted) play, in order to hopefully "energize" tournaments and reduce the number of drawn games. Leaving out duplicates and immediate losses, there are 174 possible 3-move ballots; initially, 137 of them were considered "playable."

Over time, that number went up to 144, and recently, 12 additional ballots have been added to the deck (see Richard Pask's book, The Golden Dozen, available for download on this site). Now, openings formerly thought to be overly one-sided, such as the Skunk, the Black Hole, the Twilight Zone, and others, are being seen in high-level competition.

This still leaves 18 ballots believed to be unplayable. But Ed Gilbert, author of the world-class KingsRow computer checker engine, is doing deep automated analysis to test this assumption.

Having recently completed calculation of a 10-piece endgame database (some 250 or more gigabtyes in size, including every possible position with 10 or fewer pieces on the board), Ed thought that intensive "book" analysis was the order of the day. After all, computer analysis, (along with skilled human analysis, of course) was a major factor in bringing the latest 12 ballots into play. Could there be hidden secrets in the remaining 18 ballots still thought to be a loss?

Ed expects book analysis of these last openings to take a few months. He doesn't necessarily expect to find that one of these is indeed playable, but he'll know the answer one way or the other in due course.

Ed explains his procedure and motivation as follows, with an interesting reference to Italian checkers: "I set up a computer to work on a book for the 18 'lost' ballots with KR 10 (KingsRow with the 10-piece database). I will let it run until all are confirmed lost. The reason I started this is that I just finished the 9-piece and partial 10-piece databases for the Italian game. What I found interesting is that I played out the 9 Italian ballots that I had labeled as probable losses, and in one of them it dropped out of book and instantly showed a database draw! I probed some of the other 'winning' attacks and think I might have found a draw for another one. I will have to build books to really confirm this, but it's possible that the 8-piece book was wrong about some of these lost ballots. Wouldn't it be neat if something similar happened with English checkers? If course I have already played out the 18 lost ballots with KR10 and did not find any obvious draws, and I think it is a lot less likely." (Playing out a position is a less conclusive but faster type of analysis than building a book.)

Ed followed up later: "The book generator has only been working for about 3 days, but already most of the lost ballots have scores around 90 (meaning they are indeed losses). While it will probably take a couple of months to fully complete this job, if there are any that have drawing chances I may know much sooner than that. There are three left that still have low scores--- the Shark, the Cheetah, and the cousin to the Black Widow (12-16 23-19 16-23). While it is not very likely, I am hoping for a draw in one of these!" (In KingsRow, scores approaching 100 are just about certain losses. The lower the score, the more balanced the position. Scores of around 30 show a definite advantage but short of a sure win; scores around 10 or lower are highly likely to indicate drawn positions.)

We'll report further on Ed's results as they become available.

Some years ago, Jon Kreuzer started work on a checker playing program as an experiment in developing game-tree searching code. The experiment was refined over time, and when a graphical-user interface (GUI) was added, Jon gave his program a logical name: GUI Checkers. (You can click on the screen-shot above for a much more detailed full-sized version.)

The nascent GUI Checkers got the attention of world-class checker programmer Martin Fierz (creator of CheckerBoard and the Cake series of engines), and Jon was inspired to invest additional effort to improve GUI's playing strength and features.

The result is before us today: GUI Checkers release 1.00, and it is most impressive.

We put GUI through its paces here at The Checker Maven, first running our standard test against Simple Checkers. GUI won easily, and we wondered just how far GUI might go. We next tested against Marujito 1.08a, which itself can defeat Simple Checkers. GUI won that encounter as well. So we kept pushing. We then ran GUI against the solid Class B engine Damas 99. (Class B engines easily defeat Simple Checkers and are quite strong, but short of world class.) The result was an interesting draw (click here for animation), played without error or missed opportunity on either side.

But we had a hunch, and so we played GUI against Nexus, the strong forerunner of the world-class Nemesis program. Amazingly, GUI won the encounter! Of course, one game doesn't tell the whole story, but the win was most impressive. Here's the situation, and we invite you to find the winning line before clicking on Read More for the solution and full game animation.

GUI 1.00 is thus established as a top Class B entry. It doesn't beat KingsRow or Cake Manchester, but it certainly plays a very worthy game. GUI features a small opening book and a small endgame database, a really nice look and feel, and some serious-minded features such as FEN and PDN import and export.

Author Jon Kreuzer granted the The Checker Maven an interview, and we learned that while he has produced an extraordinary checker engine, he has a more general interest in board game programming, having started with an Othello playing program while at Cornell University, and also having a strong chess playing engine to his credit. He has a current interest in 3D programming, as evidenced at his web site, 3D Kingdoms.

In talking about GUI Checkers, Jon points out that the program is open source and is probably the strongest open source checker program to be found. He does not have ambitions to advance it to the world-class category, but nevertheless has additional ideas on how to make it stronger and add features. He's especially interested in improving the opening book.

We asked Jon if he ever thought checkers would be completely "solved." He thought that perhaps it might, and that could limit his interest in further checker programming, but held out hope for the rest of us: "I don't think it should affect games between people." Well said, Jon, and congratulations on your fine achievement with GUI Checkers!

(GUI Checkers can be obtained from the author's web site, and it's well worth your while to do so.)

[Read More]

PLEASE NOTE: The download links and CD offers in this article are obsolete and no longer valid. As of October 2021, you can get Martin Fierz's programs and databases from his website. You can get WCC Platinum from archive.org.

---

Gil Dodgen's WCC Platinum II and III checker playing computer programs are now available for the cost of duplication and shipping. Testing was a complete success and we are ready to take orders. Please read our special web page for further information, prior to contacting us.

We are also pleased to be able to distribute Martin Fierz's compact 8-piece endgame database, which runs with his Cake Manchester and also with Ed Gilbert's King's Row. This will also be available elsewhere for free download, and that is far and away the preferred option for all concerned. But, if you don't want to or can't download it, you will be able to get it from us on 4 CDs for just the cost of duplication and shipping. Watch here for timing of availability and details on ordering.

Please note: The Checker Maven maintains strict neutrality and impartiality. Our distribution of checker software and databases is intended as a service to the checker playing public, and must not be construed as making any kind of statement as to the claims or relative merits of any particular program or database. Such statements are made by us only in the context of a published review or evaluation.

There's a brand-new checker playing engine just released. It's called Marujito, named after a yellow canary that is a character on the Barcelona television comedy show Plats Bruts. It (the engine, not the canary) runs with Martin Fierz's CheckerBoard interface, and was developed by Angel Galan Galan of the University of Barcelona. He bundles it here under the name Matilde with two other engines that play European checker variants.

As those of you know who follow my checker program review page, I test nearly all new programs against Martin Fierz's Simple Checkers, an engine that I rate as "Class C" meaning it plays a good casual game, if short of expert or master level. Simple generally destroys the competition as, alas, the majority of checker programs out there aren't all that great.

Well, this new kid on the block is no comical bird, despite its name. Marujito clearly outplayed Simple Checkers in a test game! The game was a very interesting matchup, with Marujito calculating a pretty way to win a piece and then correctly winning a 3 kings vs. 2 kings endgame--- something that the more basic programs very often fail to do.

You can view the full game in animated form, with comments and evaluations, here. But before you do that, take a look at this position:

Simple has just blundered by playing 25-22, a losing move. But it looks like a pretty natural move in this position. Can you see the way to a Black victory? Try your hand at it, and check your winning ways against the actual game as linked above. You'll see that Marujito handles this very nicely.

The Checker Maven congratulates program author Angel Galan Galan on turning out a checker engine that plays a very good game and will be a lot of fun to use as a casual sparring partner.

A summary review of Marujito now appears on the review page.

The Program Review web page (see link in the right column) has been completely overhauled, with a streamlined rating system and more accurate evaluations. Dozens of checker-playing computer programs are reviewed and no-nonsense recommendations provided. Check it out soon!

On the checker program review page, you'll find our review of the very unusual checker playing program Blondie24. One of the reasons that the program is unusual is that it is one of a very few "neural net" checker programs, a type of program that "teaches itself" to play. This approach has produced world-class backgammon programs but hasn't done well with non-probabalistic games.

It doesn't come close to world-class results in Blondie24 either, despite the authors claim of expert-level play (although it doesn't do that badly either). However, though neural network programming is interesting and different, that isn't at all what makes this program unique. I won't spoil it for you here; just use as a clue the fact that the game is subtitled "Checkers With An Attitude."

Take a look at the review, check out the Digenetics web site, and see what you think. Then, for an objective look, check out this animated game between Blondie and Simple Checkers, showing surprising over-the-board play quality.