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.