CheckerBoard 1.64!

I know I should have waited a bit to give you a chance to comment on beta 2 - but with busy season coming up, I just wanted to get this off my mind. I proudly present CheckerBoard 1.64, which you can download on the CheckerBoard site. Besides, I remade the site using advanced techniques (ahem) like CSS and PHP. ahem because these things have been around for so long that they are probably outdated now that I finally found some time to look at them :-)

CheckerBoard 1.64 beta 2

I've updated the CB 1.64 beta which you can download as http://www.fierz.ch/CB_setup_164.exe (1670 KB). It doesn't have a new version number but it displays December 2 as date in the status bar on startup. I have a particular question: one user reported that the "add comment" feature wasn't working - he would add a comment and that would just disappear. Does anybody else see this problem (because I don't...)?

Getting organized!?

The other day I was looking at a PHP tutorial and followed a couple of links and finally ended up on backpackit - quite a coincidence, since over the last couple of months I've been frustrated with how disorganized I am! I'm not sure yet whether this is the real solution, so: how do you organize your ideas, projects etc?

CheckerBoard 1.64 beta

I've posted CheckerBoard 1.64 to my website; there is no link as yet but you can download it as http://www.fierz.ch/CB_setup_164.exe.1.64 introduces a change to the directory structure: there is a new dir called "engines" where all engines should go. In the "bmp" directory, there are now subdirectories where you can put all kinds of piece sets which then show up in the options menu. There are 3 sets pre-installed, my standard set and two new ones by Ron Carney. For serious checkers players, there is the option to analyze an entire PDN database. Ed Gilbert sent me some code to improve my PDN parser, which is now more forgiving of non-PDN input, such as games which you copy-paste from a webpage. CB 1.64 also introduces alternate languages, albeit only for the menu and not for the dialogs. It's a start... Angel Galan Galan did the Spanish translation. My thanks to all those who contributed to this release!

To install CB 1.64, download and execute the CB_setup file. There are several ways to get it working properly:

-> Install CB 1.64 over your old CB directory: In this case, CB 1.64 will not recognize checkers engines which are not in the "engines" directory. You must manually copy these engines (all the *.dll files and associated files) into the engines folder.

-> Install CB 1.64 side-by-side with your old CB: choose a new directory such as C:\program files\CheckerBoard164 for your new installation. The two versions should be able to coexist on your system.

-> Uninstall the previous version of CB: First, remove your old version of CB. Make sure to keep games that you have saved! Re-install the new version over it.

GUI checkers 1.05

Is it a bird? Is it a plane? No, it's GUI checkers running at an amazing 4.5 million nodes per second on my Athlon 64 3000+! I managed to coax Jon Kreuzer from his checkers retirement by requiring a tiny change in the way engines interact with CheckerBoard, and instead of just implementing this change, he went on to improve GUI further. It is now searching about 3 times as fast as Cake Manchester. You can download GUI on Jon's checkers page.
Jon also wrote a nice tutorial on bitboards in checkers programs, which gives you an idea on how to program a blazingly fast checkers program.

PS: of course, speed is not everything. There are reasons why Cake is so much slower than GUI, and it's not only that Jon is a more accomplished programmer. Cake has larger endgame databases which take time to probe, and it also has a more complex evaluation function. As you know from our human checkers experience, it is not necessary to examine millions of positions to find a good move - it is more important to examine the right positions, and to evaluate them correctly. Cake Manchester is better than GUI checkers despite searching less positions per second.

CheckerBoard 1.64

CB 1.64 is under way, and will be finished soon. I'll be posting the link to a beta in some days. CB 1.64 will have a small change in the directory structure; this may cause some problems which is why I am going to need you as beta tester! I am also going to need translations of the help file to Italian and German; the help file itself will be slightly updated, but if you feel like translating, you can start on the current help file, there are not many differences. Remember to leave a comment that you're working on the translation so that others can see that this task has been taken care of!

Open Office 2.0

Totally off-topic - or maybe not: Open Office 2.0 has been released. It's not quite as off-topic as it may seem: CheckerBoard is freeware, and so is Open Office. I'm always on the lookout for decent free software, and Open Office certainly belongs into this category (much more so than CheckerBoard). If you're tired of paying Micro$oft for annoying you with talking paper clips, try this!



While I'm at it: If you're looking for a decent program to create installations, try Inno Setup.

On my computers at home, I also use free antivirus software: Anti-Vir personal edition on my desktop computer and AVG free edition on the laptop. I haven't made up my mind as to which one is better.

When it comes to graphics, I use XnView.

I edit my website with Arachnophilia. But I'm not 100% satisfied with it - it's very no-frills, and you need to know your HTML to use it.

How about you? What free software works well for you? I'm only interested in productive software like the above, not in games like CheckerBoard :-)
If you know of a great free program (no NagWare or trial versions!), please add a comment!

CheckerBoard @ Wikipedia!

I just noticed that CheckerBoard has its very own Wikipedia entry. Wikipedia is one of the best things I've ever seen on the net, and I'm flattered to see my humble program being mentioned there :-)

ISCA world championship games

I went over the games played between George Miller and Yuri Sorkin with Suicidal Cake. George has started publishing those games on the ISCA message board. The comments by Suicidal Cake are not on yet, but will be soon. Analyzing human games is one of the few things that I can do with Suicidal Cake - the players don't want to see it published :-(

What's the fastest loss in suicide checkers?

The title says it all: I want to go looking for the fastest loss in suicide checkers with the help of my Suicidal-Cake-generated opening book. Any guesses?

ICSA world championship

Over the last days, George Miller and Yuri Sorkin fought for the suicide checkers world championship over the internet. George won a very close match with 6.5-5.5. I had Suicidal Cake look at the games, and have a small challenge for you: in the following game, Yuri missed a win very early in the opening. What should he have played here?

[Event "3rd ISCA World Championship Match"]
[Date "2005-09-30"]
[Black "George Miller"]
[White "Yuri Sorkin"]
[Result "1-0"]

1. 12-16 21-17 2. 9-13 24-20 3. 8-12 25-21 4. 16-19 {already a loser! 5-9 instead is probably a draw} 23x16 5. 12x19

White to move and win!

Why a chess player programmed checkers

I'm a chess player. I learned the rules when I was five years old, joined a club when I was about 10 or 11 years old, and have been playing ever since. So why did I write a checkers program? I once tried to write a chess program when I was 17 or 18 - I failed miserably. After learning how to program a bit more seriously, I still didn't feel ready to write a chess program, and tried my hand at Connect Four instead. That's a game with very simple rules, and I learned all the basics of strategy game programming like alpha-beta pruning and hashtables there. Later on, when I felt a bit more familiar with the concepts of strategy game programming, I again wanted to write a chess program, but still didn't feel confident enough. So I wrote a checkers program although I had never played the game myself at all. The only reason that I chose checkers was that it was somewhere between Connect Four and chess in the complexity of its rules, and the fact that I read about the Tinsley-Chinook matches in time magazine. It may seem strange that a weak player can write a strong program, but in chess the same pattern has often been seen: the programmers of many strong programs like Shredder, Chess Genius, Chess Tiger etc are all quite weak players themselves.

2 million moves!

My book generator just passed the 2 million move mark. For me this was a psychologically important moment, although as a physicist I am usually immune against that kind of innumeracy. The reason this one number means something to me is an email I received from Murray Cash (programmer of Nemesis) over 3 years ago. He had just completed a match between Nemesis and Cake++ 1.4 (the details are still available on the Nemesis benchmarks page). His conclusion then was that Cake was a decent engine, but that it would need a book of 2 million moves or so. It took me and my computer farm quite some time to come up with this book! I'm glad I had the patience to build this book...

KestoG 1.1

I just put up a new version of Kestutis Gasaitis' Russian checkers engine, KestoG 1.1. The main difference to the previous version is that the hashtable is now resizeable - besides this, there are some minor modifications to the search. You can download it from the checkers download page.

KingsRow 1.15a

Ed Gilbert has published a new version of KingsRow, 1.15a. You can download it on his website. The new version of KingsRow plays a better game, and removes the engine unlock feature that future versions of CheckerBoard will no longer support. That means that older versions of Kingsrow (1.14xy and earlier) will no longer work with the next update of CheckerBoard.

A russian checkers engine for CheckerBoard

I received a new CheckerBoard engine this morning from Lithuania. Kestutis Gasaitis has written an engine which plays Russian checkers - the kings fly and men can capture backwards in this version. I already lost three times against it! You can download the engine on the CheckerBoard website. It even comes with source code!

New pieces for CheckerBoard available for download!

There are four new piece sets available for download on the CheckerBoard site. All of them were created by Ron Carney from Florida. Thanks a lot Ron! Here's a challenge for all of you: try to create even nicer pieces :-)

New pieces for CheckerBoard

Scrambling back on topic, I remember that when I introduced bitmaps in CheckerBoard back in December 2003 I hoped that somebody would supply nicer bitmaps than those I had whipped up. I also hoped that that would happen rather sooner than later. Instead, nothing ever happened - until I received a nice set of new pieces by email a few days ago. Ron Carney is obviously more talented when it comes to computer graphics than I am, and with the next release of CheckerBoard, it will probably come with his new bitmaps. To get a preview of things to come, turn to any game on my website, such as this one from the Big Engine Match between Cake and KingsRow last year. If you have any further suggestions about these new pieces, this is the time and place to drop a line!

The shuttle has landed!

Going completely off-topic, I watched the space shuttle land today. As a child, I was fascinated by rockets and spaceships and the like, and I still can remember quite well how I first read about the Challenger disaster: it was the headliner of the Swiss tabloid "Blick" that day. Later it became clear that the Challenger disaster was a direct consequence of managers overruling scientists and engineers, something which has lead to catastrophes before (e.g. Titanic) and afterwards (e.g. Chernobyl). Today, my fascination for manned space flight has disappeared; I tend to agree with the article A Rocket to Nowhere - there's not much point in sending humans into space. My interest in engineering problems however has increased, since I'm more of an engineer today than the physicist I was by training. Gregg Easterbrook's article from 1980 (before the first shuttle flight) has a nice description of the engineering tasks involved in building the space shuttle.

All of this has nothing at all to do with checkers, and I apologize for the digression. Except, perhaps, that my early fascination with space technology also lead to a fascination with computers - and that lead to CheckerBoard, many years later!

4 in a row 3.0

The last two weeks I was in the alps, and of course I had my laptop with me. I first worked a bit on CheckerBoard, adding the option to change the menu languages. Then, I revamped my old 4 in a row program. You can download it on my 4 in a row page. Have fun!

Ed Gilbert finishes the 10-piece endgame database!

Over the past approximately 2 years, Ed Gilbert (the author of KingsRow) had this completely crazy project of building the 10-piece database on a couple of "normal" PCs. Crazy because building endgame databases is in principle something very simple and straightforward - if you have enough RAM. PCs with 32-bit operating systems are limited to about 2GB RAM, which is just fine for the 8-piece database, but very little for the 10-piece database. Ed devised lots of clever schemes to circumvent these limitations; you can read the whole story on his page on building the 10-piece database.
Congratulations, Ed!

Translation request

In the next release of CheckerBoard, I plan to add an option to change the language of the menu items. The help file should naturally also be translated. At the moment, there are only Italian and Spanish checkers engines, so these two languages are currently the only ones I'd like to add. Since my knowledge of these languages is very rudimentary at best, I'm looking for someone to translate the menu commands and the help file into Italian and Spanish. Any takers?

GUI checkers 1.00

Jon Kreuzer has released version 1.00 of his program, Gui checkers. There is a standalone version as well as a dll which works as an engine in CheckerBoard. The main improvement over 0.99 is that 1.00 now has an opening book, which enhances the playing strenght. You can download Gui checkers on Jon's checkers page.

Aerosols instead of checkers

I've been working a lot lately; we are just finishing a protoype of a new device which measures particulate matter in the air - a form of air pollution. It's rather small and portable and sends its data over bluetooth to a PDA, the whole thing looks like this:

Because I'm working more than usual, I had no time lately for checkers programming. Two projects are ongoing, and I don't need to do anything about them: the book generators for regular checkers and for suicide checkers are both churning away on their respective computers. The generator for regular checkers is filling in the gaps in the newly merged huge opening book, a process which takes a lot of time. I guess that I'll be able to release the resulting book in about two months. I restarted the suicide checkers generator a few weeks ago, since Suicidal Cake now also has access to the 7-piece endgame database. After analyzing 46'000 positions, it still thinks that the game is a draw.

In 10 days, my holiday season starts, and hopefully I will be able to get back to cleaning up CheckerBoard's source code!

The 7-piece suicide checkers database

Last week, I computed the 7-piece suicide checkers database. First, I changed my database generator so that it can now also compute databases with more than 4 pieces per side. For suicide checkers this is necessary, since positions with e.g. 6-1 pieces are not clear at all, they might be either a win or a loss (no draws, I think). The 7-piece database took 2 days to generate, and in compressed form it is 2GB large. That is much larger than the regular 7-piece database. I probably won't build the 8-piece suicide database, it will be huge in compressed form and practically unusable. I have restarted my suicide book generator again from scratch, with the larger database the book it generates should be much improved.

More old code

I built a 6-piece suicide checkers endgame database (up to 4 vs 2 pieces, no 5 vs 1) a couple of months ago, and generated a suicide checkers opening book with Suicidal Cake. One of the problems in suicide checkers is that endgames which are materially lopsided are not clear at all. Imagine a situation where one side has one piece remaining, and the other side has N, with N being a large number, e.g. 4. Sometimes the position is such that the side with one piece manages to lose his last piece, sometimes not. If he can't do that more or less immediately, he will usually lose; like in normal checkers, it is good to have more material in suicide checkers. There are many exceptions though, and for these Suicidal Cake should have a larger database, especially also lopsided databases like the 5 vs 1 which I didn't generate. I didn't generate it because my old database generator was limited to 4 pieces per side. This weekend, I cleaned up my old db generator (it hurt!), and removed this 4-piece limitation. I plan to build at least the 7-piece suicide database including all lopsided databases with the new generator.

The new book, finally

This week I released a new install package for CB - with the latest versions of CB, Cake, and the opening book. The new book has 93'000-something moves, just like the old one, but it should be quite a bit better. The last result of the matches against KingsRow with the final book was

• mailplay:
  +0 -4 = 20
  
• lost:
  +16 -18 =2
  
• normal:
  +4 -13 =271
  

In fact, this is a worse result than I got at 74'000 moves; however this is most likely just because of KingsRow's random opening choice. With the original book, the result is

• mailplay:
  +0 -7 =17
  
• lost:
  +8 -18 =10
  
• normal:
  +4 -15 =269
  

which is clearly worse, although the improvements are mainly in mailplay+lost openings. This is mostly because of the new book generator which looks at unbalanced ballots deeper than the old book generator.
I also wrote a book merge tool with which I have replaced the old database entries in the opening database with their new counterparts. Since quite a lot of play has changed in the opening stages, it will now take a long time for the book generator to expand these new lines to the same level as the old lines, so don't expect a new big book any time soon.

Innumeracy

This post seems quite unrelated to checkers programming (but it's not), but I can't help it - I just have to digress! Across the street from our house, a mobile phone company is planning to build a base station. Concerned citizens in the neighbourhood have already formed an anti-antenna interest group and are trying to prevent it. My neighbour, a 50-ish woman, asked me what I thought about it, and also told me that she had heard (at a meeting of this anti-antenna-group) that such an antenna was especially dangerous within a 46-meter radius. Because we live within this radius the woman was concerned.

I am constantly amazed at how little the general public understands about the basics of physics, or science as a whole. Our society is dominated more and more by ever-improving technology, but nobody understands it. You can claim ridiculous stuff - like that an antenna is dangerous within a certain radius, but not any more if you take one step further away from it, and people don't understand that this kind of reasoning is hogwash. If I had tried to explain to her that there was such a thing as ionizing and non-ionizing radiation, and what the difference is in terms of health hazards, I would have failed completely (If you really want to know about health issues and mobile phones, see the FAQ of John E. Moulder). This phenomenon I just observed is called innumeracy and is the much-overlooked but much more common cousin of illiteracy. I don't know if there is also such an in/il-term for not knowing any science. If there was, it would explain why people hold magnets in their hands for hours in the belief that this will cure them from some kind of disease; and also people would stop asking for proofs that something is safe. You can only prove that something (mobile phones, genetically engineered food, smoking etc) is not safe, never that it is safe.

You will ask: what has all of this got to do with checkers programming? It's quite simple: programming is sometimes called computer science, and when you write a checkers program and want to make it better, you have to make use of scientific methods. You need to devise methods to test your program, so that you can measure progress. You need to apply changes and either reject them or accept them on the basis of your test method. If you don't have the tools to test your program, and if you don't regularly test your changes, your program will not improve. I guess my neighbour will never write a good checkers program!

GUI checkers 0.99

Jon Kreuzer has released a new version - 0.99 - of his GUI checkers. You can download it on his checkers page. It is much better than simple checkers, but (still) weaker than KingsRow or Cake. It also comes with complete source code!

Nerd!

To develop a good game playing program, you probably have to be a bit of a nerd. I just tested my nerdiness and achieved the following:



How about you?

The Big Ball of Mud

After writing that I didn't want CheckerBoard to become bloatware like so many other programs, I wondered whether there was a formal definition of bloatware. Wikipedia is a fantastic online encyclopedia, free for all to use (and to improve!) - and indeed there was a chapter on bloatware in Wikipedia. Reading through the article and following some links I can now improve on my old code posting: Wikipedia has a comprehensive list of bad programming practices, and I found a lot of things I was guilty of! The top problem of CheckerBoard is that it is a big ball of mud. Related problems are lava flow, procedural code, action at a distance and accumulate and fire. Read the articles and have a good laugh imagining me wading in my big ball of mud :-)

Another book update

Back from my chess tournament, I tested the latest version of the new book - it is now at 74'000 positions. It has improved further and got the following results in the 2s-per-move match against KingsRow 1.14p (with its massive 800'000 move book):

• mailplay:
  +1 =19 -4
  
• lost:
  +14 =4 -18
  
• normal:
  +4 =274 -10
  

I'll keep the generator running for another week, when the new book will be about the same size as the old book that was published on the web - then I will publish a whole new installation package for CB; it's high time I did that anyway - the last versions of CB were all only available as zip-files. One of the reasons for computing a new small book was that I wanted to both have a stronger book for the installation package and not turn CB into bloatware (software which uses more diskspace on every new release), like most other programs out there. It looks like my ideas about the new book were quite right - it is already better than the old book!

Old Code

When I added a few features to CheckerBoard a few days ago, I once again was confronted with my programming past. CheckerBoard is such an ugly program, it makes me want to throw it all away, and start over, or rewrite everything seriously. Unfortunately, that would take a lot of time so I never do it. I cleaned up a bit of code that was particularly awful, but there is still lots I would like to fix some time. What do you do with your old code?

CheckerBoard 1.63

I posted CheckerBoard 1.63 as a zipfile on my website. Download it now and unzip the contents into your CheckerBoard folder. The zipfile contains CB 1.63 and an updated helpfile. What's new? I fixed a bug in the user book, and added new search features: in the search mask, you can now search with the current board position too, and results of previous searches can be accessed rapidly with new search functions.

Chess, not Checkers

I'm off to a chess tournament which will last for 9 days. However, the title of the post is misleading, I plan to fix two bugs and add a couple of features to CheckerBoard when I'm not playing chess! I also want to write a book merge tool to replace the old values in the opening database with the newly calculated ones. I hope I'll find the time for all the things I want to do...

In the meantime, I have new results from the new book, which was at 46'000 moves when I last tested it:

• mailplay:
  +1 = 18 -5
  
• lost:
  +14 = 4 -18
  
• normal:
  +3 = 271 -14
  
  

That's hardly better than at 20'000 moves, although there is some randomness to these matches, because KingsRow chooses among equal moves at random.

The need for a book update

I have to admit: I'm not really a good programmer. I still program in plain C, have no idea about object-oriented programming and new developments like Java have passed me by. Good practices like documenting code, using CVS and the like are not on my skills list either. Why do I mention this? My programs are usually "work in progress". Often, I know better but don't bother to fix certain things. The book generator is such an example. As a small excuse, I wrote it at a time where I didn't have the 8pc database yet and didn't ever expect to generate opening databases with millions of positions. But now that this has happened, some rather obvious flaws in the design of the book generator have appeared. The basic problem is that with the 8pc database and a huge book (meaning lines are searched very deeply), most openings turn out to have the value 0 - the book generator manages to more or less find a path directly from the 3-move starting position into the endgame database. It also turns out that in most positions, there are a number of moves that all have value 0 - all of these moves draw. However, typically one of these moves might leave you in a strong position, and the opponent has to play accurately to draw, while another of these moves could leave you struggling for the draw. Of course, I would want Cake to choose the move that leaves it in what is called a strong draw. But how do you do this? The solution I envisaged at the time I wrote the book generator works as follows: In every position, the opening database contains the values of all moves as they were computed when this position was first examined, plus the values that come from propagation of further expansion. The propagated values are the true values, but if two or more of these are the same, I want Cake to choose the move which looked better on a shallower search. That's just what it does right now. Does all of this make sense? Doesn't this sound like a sensible approach? Well, there is a flaw: When I started generating the opening database, I used a beta version of Cake Sans Souci for the first approximately 90'000 moves. Then I switched to Cake Sans Souci, and much later, already after over 1 million positions, I switched to Cake Manchester. At the same time, I upgraded the hardware from an Athlon XP 1600+ to a XP2400+ and later to an Athlon64 3000+. All of this means that the first positions examined - the most important ones! - were searched with a clearly weaker machine+engine-combination than what I have today. The first positions are the most important ones, because that's where you decide how to play - at later stages things are often forced or simply a draw. Therefore, the most important decisions in the opening are not made by Cake Manchester, but by Cake Sans Souci beta, and I'm not happy about that! I'm in the process of computing a small opening book with Cake Manchester, which I will then import into the full opening database, which should improve things. There are many other details that are not good in my book generator, but this post is already too long to write about them now!

The match that wasn't

Currently, a suicide checkers match is being played between Europe and the US on 10 boards. You can view the games online! Suicidal Cake should have played on the 11th board against an American program, but some human players didn't want the programs participating. I can understand that people don't want to play against programs (after all, I should have played against a chess computer in a Swiss tournament in 1991, and decided to forfeit the game rather than play!), but I don't quite understand the objection against two programs playing each other. In fact, I cannot understand at all that the human experts aren't interested in seeing what the programs play!

Book update

I have been computing a new book for Cake starting from scratch for the last 10 days. With 20'000 moves in the book, I had Cake Manchester 1.09 play against KingsRow 1.14p with its massive opening database on my AMD64 3200+, @2s/move, with 512MB db cache and 64MB hashtable each. The result, predictably, was quite lopsided:

• 12 mailplay openings (now part of the standard deck):
  +0 =17 -7
• 18 lost openings:
  +13 =6 -17
• 144 normal openings:
  +6 -16 =266

This certainly isn't too good, however, the book is still very small and will improve rapidly. Keep in mind that my full book is based on 1.6 million positions! I haven't tested how the old 90'000 move book that is distributed with the CB installation does in a match with KingsRow, but probably not much better than this new tiny book. Once the new book is reasonably good (probably around 100'000 to 200'000 positions), I will release it. Why am I doing this instead of releasing my full book? Good question, and I will answer it in my next post.

The Cake 7pc database is available for download!

Thanks to a generous individual who has offered me space+bandwidth on the internet, the 7pc endgame database for Cake (KingsRow can use it too) is now available for download. Get it!
The Cake endgame database is more compact than the Chinook endgame database, and will give you a bit better performance.

A postscript to exaggerations, part 3

A bit more than 2 weeks ago I wrote about the exaggerations on the WCC website. Yesterday, I read in Bob Newell's Checker Maven that Bob is now going to distribute WCC platinum versions II and III at the cost of duplication and shipping. The only good thing about this is that more people will get their hands on platinum and be able to see that the claims on the WCC website are in no way true.

Cake for Linux with opening book released

Peter Chiochetti has published Cake 1.20 with an opening book for Linux. The book is based on a huge opening database of over 1.5 million positions, and is probably nearly error-free. Get the new version of Linux-Cake on the xcheckers page!

More on suicide checkers draws

I'm just back from my easter holiday in Saas Fee, where I tried to avoid serious injuries while sliding down snowy mountains on skis. I tried thinking about how to solve the suicide checkers problem, but I couldn't find an answer. The problem is this: In general, so I am told, material is quite important in suicide checkers. The side with more material is generally well off. However, unfortunately, there are many draws like those mentioned in the last post. These fortresses are of course detected by the endgame database, but only for positions with few enough stones. Of course I could compute larger endgame databases, but the problem remains: I cannot trust the verdict of Suicidal Cake, unless it sees a database win/draw/loss, because Suicidal Cake believes (like a regular checkers program) that being up a man or two is going to win a game. If you have any ideas on how to score suicide checkers positions more accurately, then drop a line here!

Drawing tendencies in suicide checkers

I (currently) believe that suicide checkers is a draw. In regular checkers, typically endgame positions with equal material and nothing dramatic going on are just draws. Endgame positions with a (numerical) material advantage are normally a win. In suicide checkers, some things are very different. For example, 1 King vs 1 King is never a draw. Depending on who has the move, it is a win or a loss. This kind of observation would make you think that suicide checkers should be either a win or a loss as a whole too - for after all, checkers is a convergent game, i.e. it converges towards endgames because of the fact that you must capture when you can. Therefore, looking at some endgames gives you an idea of what might happen after the middlegame dust has settled. 2 kings vs 1 king is normally won for the side with 2 kings, here's a short example:

[Result "0-1"]
[Setup "1"]
[FEN "W:WK5,K1:BK32."]
1. 1-6 32-28 2. 6-10 28-32 3. 5-9 32-28 4. 9-14 28-32 5. 10-15 32-28 6. 14-18 28-32 7. 15-19 32-28 8. 19-24 28x19 9. 18-23 19x26 0-1

However, if the single king happens to be close enough to the 2 kings, it can sometimes win:

[Result "1-0"]
[Setup "1"]
[FEN "B:WK21,K1:BK18."]
1. 18-22 21-25 2. 22x29 1-6 3. 29-25 6-10 4. 25-22 10-6 5. 22-18 6-2 6. 18-15 2-7 7. 15-11 7x16 1-0

However, all these endings are wins and losses too (This statement is wrong, as George Miller points out in his comment below - there are also drawn positions). Once we get to 2-2 kings though, we start to see some draws; here's an example:

B:WK23,K22:BK11,K8. This position is a draw. And this is where things get really interesting: You can add more or less as much material for the white side to this position without changing the result. Like this: B:WK23,K22,K17:BK11,K8. Draw. Or like this B:WK26,K23,K22,K17:BK11,K8. Still draw - and you could continue! Why is this? If the white kings approach the red kings, the red kings can sacrifice themselves and win. Like this:

[Result "1-0"]
[Setup "1"]
[FEN "B:WK26,K23,K22,K17:BK11,K8"]
1. 8-12 17-14 2. 12-8 26-31 3. 8-12 31-27 4. 12-8 27-24 5. 8-12 22-17 6. 12-8 17-13 7. 8-12 13-9 8. 12-8 9-6 9. 8-12 {the white kings can't go any nearer, else this happens:} 6-2 10. 11-7 2x11 11. 12-16 11x20 1-0

The same is true vice versa. Neither side can make progress, and the game is drawn, despite a clear material imbalance. This means that unlike regular checkers, a large material advantage is sometimes not winning. Here's another example with a king and a man holding the draw:

W:W17,K11,K9,7:BK27,19. Draw.

The implications are rather clear: material is not as important in suicide checkers as in regular checkers, and the game has a drawing tendency because in endgames, often neither side can approach the other without losing instantly.

GUI checkers 0.90

One month ago, I wrote about a small checkers program called GUI checkers 0.80 by Jon Kreuzer. He just released version 0.90 which you can download on his homepage. Great news: the new version is also available as a dll for CheckerBoard. It is much stronger than simple checkers, but also still clearly weaker than Cake or KingsRow. The lack of book and endgame database is too big a handicap. GUI also comes with source code, where you can look at some more advanced techniques which are not demonstrated in simple checkers, such as hashtables and forward pruning.

Exaggerations, part 3

Today's pick in the exaggeration category wins the title strongest program to use exaggerations. The plural form is intentional, there is so much stuff on that website that is incorrect that I can't list it all; I will stick with just two claims. If you haven't guessed by now, the program is World Championship Checkers. The name is slightly ironic - WCC was the only top program that didn't show up at the 2002 computer world championship. Let's see what its authors claim on their website: The first thing you notice is the big banner on top that claims that WCC is the program that eats other checkers programs for breakfast. Of course, they have nothing to back up this wild claim. I played 10 games with WCC gold against Cake Sans Souci - an older version of Cake, also using only the 6-piece database for this match - and WCC lost 3 games and drew 7. That's not exactly what I would call eating for breakfast! Of course, with only 10 games, this is not a statistically significant result; a repetition of the match with different openings would produce a different result. However, it is likely that WCC is a bit weaker than the top programs. 4 games of that match can be replayed online at my games page. Both WCC gold and Cake are free downloads, you can repeat this kind of experiment any time you like.
Reading further on the WCC website, I read the next wild claim: Accelerated database lookup code makes WCC outperform all checkers programs on the market. The WCC databases are much smaller and are accessed three to four times faster than those of all other available checkers programs. Again, there is nothing to back this up of course. I have no idea how fast the database lookup of WCC really is, but vice versa the WCC authors have no idea how fast my database lookup (and that of other programs) is. How can they know they are 3-4 times faster? They can't, their statement is ridiculous. Their database, it is true, is 14.5% smaller than mine, and I don't want to pretend that is not good. It is good! But does it make a significant difference? The answer is no, it doesn't. This can be shown by running engine matches with different database cache sizes for one engine, and the results are not significantly different. Besides, there is something more to be said about endgame databases: A database not only uses RAM for the database itself, but also for some tables it needs. The amount it needs for its tables, the overhead, can be different for different databases. I don't know how much overhead WCC has, and I won't start claiming it has a larger overhead than my database. But any comparison between databases without including the overhead is rather pointless.

Suicide checkers: is it a draw?

Two player games such as checkers have a so-called game-theoretic value. The game-theoretic value is the outcome of the game when it is played perfectly. A game is said to be weakly solved when the game-theoretic value is known. For checkers, it is rather obvious that the game-theoretic value is a draw, but it is not proven (yet, see a previous post on the end of checkers). Most interesting games, such as checkers or chess, are very likely drawn with perfect play. Games which are a win or a loss for the first player can be considered to be flawed - somehow, it's not right that one side has a winning advantage right from the start of the game. An example for this is Connect 4: It is a win for the player who starts the game. A computer solution of that game was already given about a decade ago. How about the checkers variants? As I already mentioned, Kingscourt (the checkers variant where the first side to get a king wins) cannot be a draw and is therefore flawed. But how about suicide checkers? Is it a flawed game or not? I do not have a real proof, but I believe the game is a draw. My suicide checkers book now has 62'000 positions, and it comes to the conclusion that the game is drawn.
Among human players, suicide checkers mostly leads to decisive games, unlike regular checkers where the draw is a very common result. Therefore, Suicidal Cake's verdict may seem surprising, but there are in fact some things about suicide checkers that make it more drawish than one might think at first - I will return to this subject in another post!

The suicide checkers opening book

Suicidal Cake is computing an opening book for suicide checkers, the book currently has 50'000 positions. That may sound like little compared to the 1.6 million positions for my regular checkers book. Keep in mind though that the regular book has to cover all 174 3-movers, while the suicide book is just for GAYP - it can leave out lots of lines. Many lines in suicide checkers are considered by humans to lose more or less instantly; for example, the following is believed to be a loss for white:

[Black ""]
[White ""]
[Result "*"]
1. 11-15 24-19 2. 15x24 28x19 3. 12-16 19x12 *

(By similar logic probably the starting moves 1. 10-14 and 1. 9-14 are probably considered to be very weak or even outright losses.) The reasoning is that red will play 3-7 at the right moment; the right moment being the one where it wins on the spot with a clearance. White can do nothing about red playing 3-7 at some point, and must be extremely careful on every move in order not to lose straightaway. By this logic, red continues with 7-11, immediately setting up the possibility of playing 3-7. A lot of moves now already lose by force, such as 22-17 which allows an immediate clearance:

[Result "1-0"]
1. 11-15 24-19 2. 15x24 28x19 3. 12-16 19x12 4. 7-11 22-17 5. 10-14 17x10 6. 6x15 23-19 7. 15x24 27x20 8. 3-7 {here we go!} 12x3 9. 9-13 3x10 10. 1-6 10x1 11. 13-17 21x14 12. 5-9 14x5 13. 11-16 20x11 14. 4-8 11x4 15. 2-6 1x10 1-0

This brings me back to the question of intermediate goals in suicide checkers: One of them is the establishment of such a clearance set-up; Suicidal Cake recognizes this specific pattern of red men on 3,8 vs a white man on 12, and gives it a big bonus. However, if my opening book is right, then this is not the end of the story: The book says that after 7-11, white must continue 27-24, and will draw. However, the path to the draw is very narrow and the last word may not be spoken - the book is not 100% clear on this line.

The suicide checkers endgame database

When I computed the suicide checkers 6-piece endgame database, I was in for an unpleasent surprise: My compression program which worked fine for the regular checkers endgame database didn't do a good job at all compressing the suicide checkers database. While the regular 6-piece database is only about 40MB, the suicide 6-piece database is a full 150MB, nearly 4 times larger. Why is this? To understand why it doesn't compress well, you first need to know how the compressor works: it uses a scheme known as "run length encoding" or RLE for short. RLE replaces "runs" of the same value in the database with a pair of values: the length of the run, and the value of the run. If this sounds gibberish, an example might help. Let's say you have a way of enumerating all positions in your database from 1...N. You write down the value for every position and get something like

WWWWWWWWWWDDDDDDDDDDWWWWWWWWWWDDDDDDDDDD....

with W a win, D a draw and L a loss - none of them present in the above database. The compressor now works by storing (10,W), (10,D), (10,W), (10,D) instead. In many databases the runs reach amazing lengths, especially in lopsided databases where most positions are just a win for the stronger side. There are of course the positions where one side can capture something, and they usually have more or less random results. For this reason, positions with captures are just removed from the database; your program will have to look one ply deeper and look up the position after the capture. This results in nice compression ratios for regular checkers, the compressed database is approximately 10x smaller than the uncompressed database. Now you can probably guess why the suicide checkers database doesn't compress well: The results in those databases are much less monotonous, and therefore this compression scheme is no longer particularly efficient.
Again, an example might make things clearer: In regular checkers, all positions with 2 vs 1 king are wins for the 2 kings if you remove the positions with a capture, with only one rather pathological exception; red kings on 3 and 12 and a white king on 11, with red to move. Therefore, this database compresses exceptionally well. In suicide checkers, 2 vs 1 king is normally a win for the side with 2 kings, however, if you played through the game I posted yesterday, you can see that in the endgame red could get 2 kings vs 1, but he would lose all the same. Therefore, the 2 vs 1 king database in suicide checkers has wins as well as losses in it, and doesn't compress well. On another note, this also means that the database is more important in suicide checkers than in regular checkers: Obviously, it would be quite difficult to write a heuristic that can guess the likely outcome of the game with 2 vs 1 kings on the board, something which is very simple for regular checkers. And of course for more complicated endgames, it gets even more difficult.

Suicidal Cake

My suicide checkers program, Suicidal Cake, has reached version number 1.08. It has a 6-piece endgame database, I suppose I am the first to compute this database. It also has an opening book of about 36'000 moves right now, with approximately 2000 more added each day. Suicide checkers is extremely tactical, many lines in the book have more star moves than non-star moves. This makes the game very hard for humans. It's hard for the programs too of course, as one mistake might cost you the game! Suicidal Cake has the huge advantage of an endgame database, which is more important in suicide checkers than in regular checkers; I'll return to this later. Suicidal Cake has played some games against two of the world's best suicide players, and has won every single game. I believe it is the strongest suicide checkers playing "entity" on the planet right now. Here's a game where the endgame database played a part, you can copy and paste the game into CheckerBoard.

[Event "Email game"]
[Date "2005-02-20"]
[Black "N.N."]
[White "Suicidal Cake 1.08"]
[Result "0-1"]
1. 11-15 24-19 2. 15x24 27x20 3. 8-11 21-17 4. 11-15 17-13 5. 12-16 20x11 6. 7x16 22-18 7. 15x22 26x17 8. 16-20 25-22 9. 4-8 28-24 10. 20x27 31x24 11. 8-11 29-25 12. 3-8 23-18 13. 10-14 17x10 14. 6x15 13x6 15. 1x10 30-26 16. 15-19 24x6 17. 2x9 18-14 {Suicidal Cake returns the man it has won to reach a winning 2 vs 2 endgame database position} 18. 9x18 22x15 19. 11x18 26-23 20. 18x27 32x23 {And here it is, this position is a win for white. Would you have guessed?} 21. 5-9 23-18 22. 9-13 18-15 23. 8-12 25-21 24. 12-16 15-11 {Red resigned. Play might have continued:}
25. 16-19 11-8 26. 19-23 8-4 27. 23-27 4-8 28. 27-32 8-11 29. 32-27 11-15 30. 27-32 21-17 31. 13x22 15-19 32. 22-25 19-23 33. 32-28 23-18 34. 28-24 18-22 35. 24-19 22x29 36. 19-24 29-25 37. 24-19 25-22 38. 19-16 22-18 39. 16-20 18-23 40. 20-24 23-27 41. 24x31 0-1

Intermediate goals

When programming a strategy game, you basically combine two elements: A deep search and an evaluation function. The search will look at lots of positions (millions) that might arise from the current board position, while the evaluation has to tell the program whether this line is any good or not. Most of the time, the evaluation is not that difficult, at least not in checkers. The reason is simple, checkers is a very materialistic game. Most of the time, being a man ahead will win the game. In other games this is different, e.g. in chess the goal is to mate the enemy king, and you can sacrifice a lot of material for a violent attack on the king. In checkers, the situations where you can sacrifice a man are rather rare, allowing even pretty dumb programs to play well. Dumb in this context means that they have a rather weak evaluation function, but paired with a deep search it will do the job most of the time. Such intermediate goals, like winning a man or getting the first king which you can code into your evaluation, are necessary for the program to know what to do; only knowing the ultimate goal of the game alone will not get you anywhere unless the game is so simple that you can calculate right to the end.
Two weeks ago, I wrote a program that plays suicide checkers. In suicide checkers, the ultimate goal is to lose, i.e. not to be able to make a move any more (either by losing all men or by getting smothered). Now, if the final goal there is to lose all your men, instead of winning all your opponent's men, what would a good intermediate goal in suicide checkers be? To win material like in normal checkers, or the other way round? And are there any positional goals that one might want to achieve? Can you guess some answers to these questions?

Exaggerations, part 2

Today's pick in the exaggeration category is Wincheck 3D by Jean-Bernard Alemanni. Wincheck is shareware and costs something like 50$ to register. There are two different versions you can register, but you can also play against the free version. Wincheck has neither an opening book nor an endgame database. It plays a decent game, but is chanceless against a strong program like Cake Manchester (I played two games between the two, and Manchester easily won both). The author uses a trick to make his program look better than it is: He groups all programs he found according to playing strength, leaving the "Top" category for Chinook, and including all decent programs in the "Strong" category. That means that Wincheck, Sage, Cake, Colossus, Damas 99, KingsRow, Nemesis, Nexus, Plus700, Wyllie and WCC all end up in the same category.
Wincheck is a nice program, I particularly like the graphics. But it is far from being in the same league as Nemesis, KingsRow or Cake (no wonder, without endgame database and opening book!). Jean-Bernard wins the runner-up prize in the category "Serious program marketed with unserious means".

Cake Manchester's opening book

The book I just created for Cake++ for Linux is much better than the book that you can download for Cake Manchester. Manchester's book is still the same I once created in 6 weeks with a beta of Cake Sans Souci after the computer checkers world championship in Las Vegas in 2002. That book is based on the first 90'000 positions my book generator explored. Now, among these 90'000 moves roughly half will never occur when you set the book to play best moves only. Of the remaining say 50'000 moves, about one quarter are just forced captures. So effectively, that book has a mere 40'000 useful book moves, and they are based on an opening database with "only" 90'000 positions, which means there are also quite a number of errors in that book.
The book for Cake++ only contains lines that Cake will actively select, i.e. there are no wasted moves for lines it will never play. I also left out the forced captures in that book. Finally, all moves are based on the 1'600'000 position opening database, which means that there are only very few errors left (if there are any at all).
Cake Manchester will also get an updated book - I'm just waiting for the book generator to discover the bad move that caused Cake's only loss in the big match between Cake and KingsRow late last year.

An opening book for Linux-Cake

Peter Chiochetti recently revamped his checkers interface for Linux. The best engine for this interface is an old version of my checkers program, Cake++ 1.19. Yesterday, I added some code to it to handle an opening book and built a 115'000 move opening book from my opening database for it. Peter will first have to check my new code for compatibility issues with Linux, so it may take a while for this new version to appear on Peter's website. The book should be virtually error-free and worth the wait.

A well-deserved retirement

Back in early 2002 I wrote a program that automatically generates a checkers opening book, without any human intervention. The algorithm for this was invented by Thomas Lincke and it's called drop-out expansion. I have a computer at home which works on the opening book day and night. Yesterday, I replaced its mainboard, CPU and memory for newer components. After 20 months of nonstop computing, this AMD Athlon XP 2400+ CPU has certainly deserved retirement! During this time, it searched through nearly 100'000'000'000'000 checkers positions, generating the largest part of my now 1.6 million-move opening book.
The replacement is an AMD Athlon 64 3400+ CPU, like the old machine this one also has 1.5GB memory. The reason that I don't have Intel inside is that the AMD processors are better suited for integer computations than the Intel CPUs - for floating point it's the other way round. But since checkers programs (chess programs too) only use integer numbers, you get much more bang for the buck when you choose an AMD processor.

Exaggerations, part 1

There are a lot of computer checkers programs, but on my website I link only to very few of them. The reason is that most of the programs out there are not very good. Even worse, their authors claim things about their programs that are far from true. I'll look at a few of those.

Let's start out with strategist checkers by Arthur Crump, which is advertised as "Strategist checkers is the ultimate opponent". Mr Crump boldly continues "Whether you're brushing up on your game or practicing for a tournament, strategist checkers can help you". You can play against the lowest of 3 playing levels in the unregistered version. Even a pathetic player like me can easily beat it on that level. To get access to the other levels, you're supposed to pay 10$. The program has practically no other features except load and save game, and that of course isn't PDN! No book, and no endgame database, of course.

For the fun of it, I had Cake Manchester play without book on the instant level (1/100th of a second thinking time) against Strategist checkers. You can copy-paste the resulting slaughtering into CheckerBoard. Cake never got the opportunity to use its endgame database, because the game ended before the database was relevant!

The bottom line: This program is so incredibly bad that Mr Crump's wild claims about his program are immediately obvious. He can only hope to fool those who really know nothing about checkers or checkers programs at all. Mr Crump easily wins the title in the category "largest difference between real and advertised playing strength". And that guy earned more money with his program than I did with mine :-(

[Black "Cake Manchester 1.09"]
[White "Strategist Checkers"]
[Result "1-0"]
1. 11-15 23-19 2. 8-11 22-17 3. 4-8 17-13 4. 15-18 24-20 5. 9-14 27-24 6. 5-9 31-27 7. 18-23 27x18 8. 14x23 26-22 9. 11-15 22-17 10. 7-11 25-22 11. 9-14 30-25 12. 14-18 19-16 13. 12x19 32-27 14. 23x32 13-9 15. 6x13 20-16 16. 11x27 28-24 17. 19x28 17-14 18. 10x26 25-22 19. 18x25 29x22 20. 26-31 22-18 21. 15x22 21-17 22. 31-26 17-14 23. 27-31 14-10 24. 2-7 10-6 25. 1x10 1-0

The world's most awful checkers program...

...is undoubtedly Braveheart Checkers 3D". Do not install it on your computer! And its not the absolutely useless 3D Braveheart-themed environment in which you play checkers that makes it the most awful. And also not the engine, which is quite decent. What makes it the most awful program of them all is that it will install tons of spyware on your computer when you install it. You'll have to do a lot of cleaning up. Shame on those who publish this kind of program!

Kingscourt

As I already mentioned yesterday, Kingscourt checkers (first side to make a king wins) cannot be a draw, unlike regular checkers or losing checkers. But which is it? Make your guess now, I will answer the question in a future post!

Checkers Variants

One of the problems of checkers is that it is played in a bazillion different variants in different countries. Chess is played with the same rules in all countries, and I strongly believe that this is one of the reasons that it is much more popular than checkers. In Europe, you cannot go from one country to another without changing rules: the board size (8x8 or 10x10), the capture rules (men can or cannot capture kings, men can or cannot capture backwards), the king movement (chess-king-like, flying in two different forms), the board orientation and the side to start the game can change. The last two items are essentially irrelevant, since they are just a convention - the game itself doesn't change if you change these rules, but of course it will appear unfamiliar to a player accustomed to another playing style.
Now, even without changing the possible moves, we can generate checkers variants: I'll take a closer look at two specific changes. The first is Kingscourt: the first side to make a king wins. If one player loses all pieces or cannot move, he loses. Another variant is Losing Checkers (also called suicide checkers): The side which loses according to normal rules wins.
The first thing to note is that Kingscourt cannot end in a draw; it must be a win either for black or for white. Losing checkers on the other hand has many drawn endgame positions, some of them are quite surprising! I'll return to this topic in my next post.

The end of checkers?

The advent of huge endgame databases has made computer programs very strong. While the current top PC programs all use the 8-piece endgame database, researchers in Canada finished their computation of the 10-piece endgame database in May 2004. With the help of this database, they hope to solve checkers once and for all; solving meaning that they will be able to say what the correct result of a game of checkers should be if both sides never make a mistake. The answer is in fact already clear now, checkers is a draw. However, until now this is only a conjecture and will be proven by the Chinook team within a few years. On their website you can view the proof that the White Doctor opening is a draw.

Gui Checkers .80

I recently came across a quite unknown checkers program written by Jon Kreuzer, Gui Checkers .80. Jon has written a very good chess program, so I was naturally curious about his checkers program. It turns out he wrote it (including the interface) in only a few days, so it's not as good as the best programs out there. But the interface has nice graphics, and I bet that with a little effort, Jon could develop a top checkers engine. Perhaps you can encourage him to do so?

The CheckerBoard Blog

After seeing so many blogs on the net, I decided to start my own. I will post on different subjects here: Computer checkers in general, CheckerBoard, Cake and occasionally checkers in general. I'll begin with a link to the only serious review of computer checkers programs that I could find on the net (and I'm not saying this because my program gets a good rating!): Bob Newell has taken the time to check out a huge number of programs and rated them all. Check out his checker program review page!