Core Duo!

It's been a long time since I last bought a new computer (21 months, to be exact, a record for me in the last 10 years!) - but I just did it again: I got myself a new laptop with an Intel Core Duo CPU - unfortunately not one of the even better Core 2 Duos. However, even this machine is absolutely great! Cake runs about as fast on my Core Duo at 2GHz as on my Athlon 64 at 2GHz. But the cool thing is that I can run two instances of Cake at the same speed, if I want to. Not that this really helps me in any way... it just shows why these dual core machines are so cool. The days of single core CPUs are numbered (as far as PCs go, anyway), and the first quad-cores for consumers are already on the market. Which gives me a bit of a headache, because it means that I should try to rewrite Cake so that it can use these new CPUs with multiple cores! All good chess programs have this capability, but the only checkers program that I know of that could use multiple processors was Chinook. However, the speedup from multiple processors there was quite lousy compared to what is reported for chess programs. For chess, it's something like 1.9x faster for dual cores and 3.5x faster for quad-cores, for Chinook it was approximately 3x faster on 16 CPUs [1]. It's not quite clear to me whether checkers is inherently tougher to parallelize than chess or whether the implementation in Chinook was poor. Any opinions?

Usage Statistics for November

Since November 2006, the full 8-piece checkers endgame database is available for download on my website. I checked the usage statistics for my server, and found the following:

Month 2006              traffic
August                   7.8 GB
September               67.3 GB
October                 93.4 GB
November                 142 GB

This means that the 8-piece database is responsible for about a 20-fold increase in data traffic from my website! It also means that the database was downloaded about 60 times. In the same month, CheckerBoard was downloaded 2'500 times, and the opening book 200 times. 60 downloads in one month is not that much, but it still makes me think about something like checkers@home...
For comparison, my 4 in a row program was downloaded 500 times, while Sudoku Champion didn't make it to the top 30 files which I can view.

Cake Manchester 1.09d - KingsRow 1.16: +20-17=251

The match between my "old" Cake Manchester 1.09d and KingsRow 1.16 finished with a narrow win for Cake - 20 wins vs 17 losses and 251 draws (naturally this is with books off - else it would be draws all around - or very nearly so). I also repeated the match with learning disabled in Cake, with the result that not much changed: +22-19=247. So to stay in line with my last post, that would mean that I could leave Cake alone somewhat longer - but the result is too close for comfort, and so I decided to start tuning Cake a bit. When I try to improve Cake, there are many different ways to do it. One of the things I sometimes try is to tune the evaluation function, i.e. to change weights of different terms in the evaluation (as opposed to adding new terms to the evaluation). When an engine has been a sitting duck for years, as Cake Manchester has, then it is quite well possible that the opponent (KingsRow in this case) is just well-tuned to beat Cake. Changing the playing style a bit might make quite a difference in such a case. So to start, I am trying to just tune Cake a bit to avoid Ed's last two years worth of tuning of KingsRow - of course, I don't just mindlessly change the evaluation weights; instead, I checked the games that Cake lost in this match. Then I also have some ideas left on how I might improve the evaluation function with new terms, and a new idea for the search which I already tested but which didn't work well in the first implementation. Nevertheless, it also didn't work too bad, and perhaps with some refinement it will work. If all runs smoothly, I will have a new version of Cake ready for Christmas!

KingsRow 1.16

Checkers programming is going slow for me these days, and I don't seem to be the only one: It took Ed Gilbert over half a year to release a new version of KingsRow (1.16) which is now available for download on his webpage. We both seem to have used our time for other projects (For me, writing a suicide checkers engine, for Ed, more sensibly, writing a 10x10 international checkers engine).

I am running a match with KingsRow 1.16 against Cake Manchester 1.09d right now, and it's looking good for KingsRow: after 200 of 288 games, KingsRow is in the lead with 12-11 wins. If KingsRow wins the match, it would be the first time ever since 2004 that I see Cake losing a match - which brings me back to the introduction of this post: One of the reasons that I didn't do very much since my initial Cake Manchester release in 2004 is that it consistently beat KingsRow since then, and that I wasn't motivated to work on Cake because it was (IMO of course) still the world's most powerful checkers engine. It looks like I might have to shake the dust off Cake's source code soon!

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.