Checkers programming economics

I received a rare donation for CheckerBoard the other day, so today I thought I could try to calculate the economic aspects of CheckerBoard. Here's what I came up with: At the end of november 2005 (10 months ago) I redesigned my checkers webpages and added Google ads to them. I also added that infamous donate button. On the negative side, I have a computer running 24/7 working on CHOB. In Zürich, electricity costs 0.16 Swiss Francs per kWh (that's about 0.13$/kWh). I'll try to measure the power consumption of my PCs soon, for now I'll assume that such a PC needs about 200W, which makes about 5kWh/day or 65 cents per day. So that gives me a daily budget of

Income from Google Ads:....+0.45$
Income from donations:.....+0.25$
Electricity bill:..........-0.65$

which leaves me with an income of 5 cents a day - not exactly much. Nevertheless, I shouldn't complain: Ed Gilbert has no Google ads, and no donations, and he's running 5 (!) machines simultaneously...

As a PS, it is no wonder that Murray Cash gave up on Nemesis!

Book update

I released a new version of Cake's Huge Opening Book (CHOB) recently. The new version is now based on about 2.35 million positions that were analyzed by Cake, the previous version (released in mid-April) was based on about 2.2 million positions. The new book would be approximately one ply deeper in the shallower main lines than the old book; however, I also threw out all positions which are in the leaf of my book tree - i.e. those positions where no successors have been searched. The reason I threw out those positions is that they are based on a 90-second book-generating search on a fast computer (AMD Athlon 64 3400+ with 2GB ram), which is good, but perhaps not good enough. The book-generating search produces evaluations for all moves in a given position, and takes longer than the regular search to reach a specified search depth. Therefore, it is approximately equivalent to a 30-second regular search on a fast machine. That means that if you set Cake to search for more than 30 seconds on a fast machine (and if you have the 8-piece database), then you might get a better move than what is in the book. This alone is enough to throw out the leaf positions, but there is more: Ed Gilbert actually found a losing book move in my first release of CHOB, and it was just such a leaf node. Now, this move is no longer in the book, and if you give Cake enough time, it won't make this losing move. Looking at the data from the opening book generator, it seems that it will have to run for another 2-3 months until it will expand that position with the losing move further.
Having found (or been told about, rather) one error in CHOB 1.0, I have to assume that there were more errors. After all, Even in a 288-game-match only about 288x10 = ~3000 book moves are actually played by Cake. Now that I know that one of these was a loser, I could extrapolate and say that 1 of 3000 moves is bad, and that therefore there are approximately 1000 losing moves in the book. I don't think it's this bad at all though, but there is no way to really know.

The 8-piece suicide checkers database

It's been a long time since my last post - but that doesn't mean I wasn't doing anything! It just took a long time to do it. But as of today, my suicide checkers 8-piece database is ready. It took about 1 month to compute on an Athlon64 3000+ with 1.5GB memory, and another 2 days to compress it. I decided to compute it after Ed Gilbert told me I was wasting my time computing a suicide checkers opening book with "only" the 7-piece database. I realized he was probably right, and so I stopped that opening book computation and went for endgame database computation. Adapting the database-building code from 7-piece to 8-piece should have been straightforward, but of course there were some little traps into which I promptly fell: In regular checkers, I didn't compute the lopsided databases (like 5-3, 6-2 and 7-1 pieces), and I didn't have any problems with my code. In suicide checkers these databases are important too, and my code to compute the binomial coefficient of n and k (I hope that's what it's called in English; it's = n!/(k!*(n-k)!) ) promptly overflowed past the size that a 32-bit integer can hold, and my database builder crashed when computing the 7-1-piece database. Next, Suicidal Cake crashed when I tried to use it with the 8-piece database - I noticed that I had a hard limit of 25 database files which I could open in my 8-piece database code. But with the new lopsided databases, I needed more, and that caused the crash. After fixing all these bugs, it now seems to be working.

The database takes 113GB uncompressed on my disk, and it is compressed to 18.4GB - that's just over a 6-fold compression. The regular checkers 8-piece database compresses over 4 times better, which shows that the suicide databases are more irregular. I'm surprised that I can even use the database with any efficiency at all, since it is so large, but Ed Gilbert already predicted that this would be the case. He has experience with even larger databases, having computed the 9- and 10-piece databases for regular checkers.

Enough for now, I am going to test my new toy!

Suicide checkers rematch

On May 29th, Suicidal Cake (now in version 1.13c, with a larger endgame database and less materialistic evaluation than last time round, also with a new 30'000 move book) played a rematch against Suicide Kallisto. We again played 4 games, and again, Kallisto proved to be stronger. At least this time the result was not too lopsided, with +1=1-2 from Cake's point of view. The first two games were horrible to watch: they were a direct repetition of two themes which cost Cake two games in the last match. In the first game, Kallisto sacrificed 2 men just to get a red piece of Cake on the dreaded 21 square, then sacrificed a 3rd man and won convincingly. In the second game, Kallisto sacrificed a man to get an endgame where Cake's pieces were trapped on the edge.
I knew about both themes, the man on 21 and the mobility issue, and had improved Cake accordingly, but apparently I'm still not evaluating these things highly enough. In the 3rd game, Cake showed it wasn't a pushover, by sacrificing a man itself (to place a white man on square 5, which is probably not as bad as square 12/21, but also bad). Cake then went on to win. The last game ended in a fast draw.

[Event "Kurnik"]
[Date "2006-05-29"]
[Black "Suicidal Cake 1.13c"]
[White "Kallisto Suicide Checkers 1.13"]
[Result "0-1"]
1. 10-15 23-18 2. 9-13 21-17 3. 7-10 18-14 4. 3-7 14-9 5. 5x21 24-19 6. 15x24 28x19 7. 6-9 19-16 8. 11x20 27-23 9. 9-14 22-17 10. 13x22 26x17 11. 10-15 17x3 12. 15-18 23x14 13. 2-7 3x10 14. 1-6 10x1 15. 8-11 1-6 16. 20-24 0-1

[Event "kurnik"]
[Date "2006-05-29"]
[Black "Kallisto Suicide Checkers 1.13"]
[White "Suicidal Cake 1.13c"]
[Result "1-0"]
1. 9-13 24-20 2. 12-16 21-17 3. 5-9 28-24 4. 8-12 25-21 5. 1-5 32-28 6. 4-8 29-25 7. 11-15 20x4 8. 9-14 22-18 9. 15x29 26-22 10. 14-18 23x14 11. 7-11 14x7 12. 3x10 30-26 13. 12-16 26-23 14. 5-9 24-20 15. 9-14 28-24 16. 29-25 24-19 17. 25x18 19x12 18. 13x22 21-17 19. 14x21 23x7 20. 21-25 27-24 21. 25-30 31-27 22. 30-26 7-3 23. 11-15 3-8 24. 6-9 20-16 25. 2-6 8-3 26. 6-10 16-11 27. 22-25 11-7 28. 25-30 24-20 29. 26-22 27-24 30. 30-26 7-2 31. 26-23 20-16 32. 23-26 16-11 33. 26-31 3-8 34. 31-26 24-20 35. 26-23 8-3 36. 9-14 3-8 37. 15-19 8-3 38. 14-17 3-8 39. 22-18 20-16 40. 18-22 11-7 41. 22-25 8-3 42. 25-21 4-8 43. 17-22 8-4 44. 21-17 3-8 1-0

[Event "kurnik"]
[Date "2006-05-29"]
[Black "Suicidal Cake 1.13c"]
[White "Kallisto Suicide Checkers 1.13"]
[Result "1-0"]
1. 9-13 22-18 2. 12-16 26-22 3. 16-20 31-26 4. 10-15 18-14 5. 5-9 14x5 6. 8-12 23-19 7. 6-10 22-18 8. 15x31 19-16 9. 12x19 24x8 10. 3x12 28-24 11. 13-17 21x14 12. 10x17 25-21 13. 2-6 21x14 14. 6-9 29-25 15. 9x18 25-21 16. 7-11 21-17 17. 4-8 32-28 18. 18-22 17-14 19. 12-16 14-10 20. 22-26 30x23 21. 31-26 10-7 22. 26x19 24x15 23. 11x18 28-24 24. 8-11 7-3 25. 11-15 3-7 26. 18-22 7-10 27. 16-19 10-7 28. 19x28 27-23 29. 22-26 7-11 30. 15-19 1-0

[Event "Kurnik"]
[Date "2006-05-29"]
[Black "Kallisto Suicide Checkers 1.13"]
[White "Suicidal Cake 1.13c"]
[Result "1/2-1/2"]
1. 9-13 24-20 2. 12-16 22-17 3. 13x22 26x17 4. 8-12 28-24 5. 4-8 25-22 6. 16-19 23x16 7. 12x28 17-13 8. 5-9 21-17 9. 1-5 31-26 10. 8-12 29-25 11. 11-16 20x11 12. 7x16 27-24 13. 2-7 26-23 14. 16-19 23x16 15. 12x19 24x15 16. 10x19 22-18 17. 3-8 25-22 18. 8-11 30-25 19. 19-23 18-14 20. 9x18 22x8 21. 5-9 8-4 22. 23-27 32x23 23. 28-32 25-22 24. 7-11 22-18 25. 32-28 23-19 26. 11-16 19x12 27. 28-24 4-8 1/2-1/2

Match report

I posted a match report on the suicide checkers match between Suicidal Cake and SuicideKallisto to my checkers website. You can jump to the report directly: the match report. You can replay the first 3 games online, the fourth would have been identical to the second, and only lasted 3 moves so I left that one out...

4-0 again!

Tonight, Suicidal Cake played a match on Kurnik against SuicideKallisto by Igor Korshunov. Once again, the match was extremely lopsided, and the result 4-0 - but this time, Suicidal Cake was the one to lose!
SuicideKallisto demonstrated a far superior understanding of the game and completely destroyed my program; the final humiliation came in game 4 when Cake tranposed moves in the opening to reach the same position as in game 2, which it had lost previously. I resigned on move 3, because we would just have repeated game 2. Igor generously offered me to play a different move somewhere, but I didn't want to - if my program is too stupid to realize that it is playing into the same loss again, then that is entirely my fault, and it's not really my program that was that stupid, but rather me...

Congratulations to Igor for a fantastic suicide checkers program and for the clear win in this match! I will post the games later on my website.

Another suicide checkers challenge

I just received the following email:

From: Igor Korshunov
To: Martin Fierz
Date: 4/21/2006

Hi Martin!I am made first version of suicide checkers.I want to match your program.When we can meet in battle?

Best wishes,Igor

I'll try to hold this as an online match on Kurnik again - once I know the time and date, I will publish it here.

Igor is the author of WildCat, a strong chess engine. He has also written a checkers program playing the Russian checkers variant, but I couldn't find an internet reference for that. WildCat is much better than Muse, my chess engine. You can verify this on Leo Dijksman's rating list, where WildCat is rated 2570, while Muse is only rated 2382. In my defence, I never took up chess programming very seriously. In any case, Igor's background in computer programming makes it unlikely that the match will be quite as lopsided as the one against Roshi47.

The Book!

I'm still not satisfied with the huge opening book - but I guess I never will be... so I posted it on my checkers site. I'll probably write some more about it later; for the moment: Enjoy!

A hidden function

Sitting here in a comfortable sofa, with the Matterhorn visible through the window, I remember that many years ago I once read in a computer magazine that you could press a wild combination of keys in Excel, and you would get a flight simulator. I tried, and indeed, there was a simple flight simulator where you would fly past something like a mountain where the names of the developers of Excel (a lot of people!) were displayed. Weird stuff! CheckerBoard also has a hidden feature: the engine match. When I want to test a change in Cake, I run a match of 288 games against KingsRow to verify that I have really improved something. Of course, this is all automated, and you can run such a match too: Ctrl+Shift+M starts a match - you can figure out the rest for yourself - I have to go back to staring at Switzerland's most beautiful mountain...

Odds and Ends

I'm busy waiting for my book generator to finish its book computation - but I'm not busy with checkers! Instead, I added a touch to my Connect Four program: it has nicer graphics and now offers different levels of evaluation intelligence - you can make it really dumb so that you can beat it easily. I also just finished a Sudoku program, using C#. C# makes it much easier to create applications rapidly. At least I'm programming something at all; I didn't find much time for that during the last year. Ed Gilbert has used my laziness to catch up with Cake: In my latest match, KingsRow 1.15u still lost to Cake Manchester 1.09d with -21+17=250, but this narrow result may just as well be accidental - Ed has some more results at different levels, and sometimes Cake wins, sometimes KingsRow. When I published Cake Manchester somewhere during Summer 2004, the match results against KingsRow were extremely lopsided - those were the days!