CheckerBoard

Checkers for the Amazon Kindle

2011-03-25T22:10:00.004+01:00

A couple of weeks ago, I received emails from two American programmers called Matt and Mike who planned to write a checkers program for the Amazon Kindle. I contributed my Java checkers engine (which also powers Checkers Tutor), and those two did all the rest in record time - and now Checkers is available from Amazon. For more information, check out the A gamz website or look at a video on YouTube!. I haven't ever seen the game live, but judging from what I can see, Matt and Mike have done a great job with it!

Checkers Tutor 2.1

2011-02-14T14:56:00.001+01:00

I just posted Checkers Tutor 2.1 for Android on the Android market. It has a lot of improvements over the previous version:

Nicer graphics (see previous post)and new nicer launcher icon
A new pushover level where you should be able to win even when moving at random
A smoother transition of playing strength when moving up from beginner levels to depth-controlled levels to timed levels. This is done by disabling parts of the evaluation on the lower depth-controlled levels
The entire last game is restored now on startup, not only the last position
Two small bugs fixed
Behind the scenes, a lot of the code was cleaned up

To me, it looks as if it should be the best/nicest checkers app for the Android platform, but obviously I'm rather biased! Now all I need is some customers and some good ratings :-)

Playing with graphics for Android checkers

2011-02-13T22:01:00.003+01:00

Over the weekend, my wife went on a short hike with our kid and his godmother, giving me a bit of time to play around with the checkers tutor graphics. Here's my current preview, and I think I will leave it at that - I like the looks of it!

I increased the size of the pieces a bit, and used Inkscape to produce pieces with gradients and highlights. Obviously I'm not a graphic artist, but I think they are much nicer than the plain circles I used to have.

Android checkers reloaded

2011-02-10T23:23:00.003+01:00

During my x-mas holidays, disappointed with the measly 5000 downloads I got over one year of my free Android Checkers Tutor App, I came up with a great plan: make it a paid app instead of free - like that, all the people who know nothing at all about checkers won't download it and won't complain about the must-capture-rule, and won't give it bad ratings. Great plan, but with 6 sales in 40 days, it didn't really work out... Not one to give up easily, I have decided to revamp it a bit. I've started making the code cleaner behind the scenes, and also tried to improve the looks of the app. Not too sure about whether it's an improvement - what do you think?

Moving to Visual C Express 2010

2010-08-11T21:50:00.003+02:00

After using the great free Java IDE's Eclipse and Netbeans for a while, and also because I bought a nice new Core i5 laptop recently, I thought it might be worthwhile installing something more modern than my slightly antiquated Visual Studio 2005 on it. I love those new features like code completion and refactoring, the fact that you can just hover your mouse over variables in the code during debugging and it shows you what they are and all the other nice bells and whistles in the Java IDEs. Having also gotten used to not having to pay for a nice programming environment, I decided to install Visual C 2010 Express. Upgrading my old projects (such as CheckerBoard, Cake, book and endgame database generators, Connect 4 and my chess engine Muse) turned out to be quite a bit of a hassle - the upgrade wizard failed to convert about half of my projects, and I had to restart them from scratch, and had some more trouble because some libraries that used to be added automatically are not added any more, causing linker errors. I had another smallish disappointment when I noticed that there is practically no refactoring support in the express edition, and a bit a larger disappointment when I noticed that there is no 64-bit support either. While I do appreciate that M$ is giving away a free more or less modern IDE, I still would wish for more. So here's my question to the C programmers out there: is there anything else that you would recommend for the Windows platform - something that would also allow me to import my Visual Studio projects with as little trouble as possible?

Suicide checkers is a draw - probably

2010-04-15T21:09:00.003+02:00

During this winter, I let my suicide checkers book generator run for quite some time, expanding the size of my suicide checkers opening database from about 60'000 to over 180'000 positions. With the generator running on a machine that was twice as fast as for the 60'000 first nodes, the overall quality of the book must have improved massively. It now predicts draws for all 7 opening moves, from which I draw the conclusion in the title of this post.
With the beginning of spring I turned the generator off again - my green conscience would at least like to scavenge some waste heat for my house from book building... Furthermore, I am slightly ashamed to have a PC with a quad-core processor running on a single core only - it could be building the book at nearly 4 times the speed it is doing now, using only a little more energy if I programmed it to use all cores. With PCs nowaday having 4 or even 8 cores, I really should learn how to program a multithreaded search...

common Java codebase

2010-04-14T21:53:00.003+02:00

I worked a bit on my Java checkers engine so that I can now use the same code for both my Android checkers tutor and my Java PC program - I'm glad I managed to combine the two! The only difference (and one I will probably forget to change from time to time...) is the size of the hashtable, which is obviously much smaller on the phone.
I also improved playing strength a bit, and will probably release new versions of both my Java checkers programs soon.

jCheckers web start

2010-03-29T22:26:00.002+02:00

I had some trouble to get jCheckers running on my own office PC... so I thought I better try something easier and played around with Java web start and produced the following test page - now that is much cooler!

jCheckers!

2010-03-28T18:38:00.003+02:00

After a rainy Sunday afternoon in front of my PC, jCheckers is now available! For some reason, I had to rewrite the entire GUI because NetBeans wasn't creating a proper distribution output for my jCheckers project. At least I also learned how to write callback functions in Java (with Interfaces), and implemented one for communication between the JCheckerBoardPanel and the main window. I should also implement one for the communication between the checkers engine and the JCheckerBoardPanel - but since my Java checkers engine is shared between Android and the full Java program, I was a bit reluctant to touch it. In fact, the engine isn't properly shared between the two because of some differences between Android and standard Java. My programmer friends tell me I should use dependency injection, but that will have to wait!
In the meantime, you can enjoy jCheckers on Linux and Mac, where CheckerBoard isn't available. jCheckers has a powerful Java checkers engine, multiple levels of play, PDN support, and unlimited takeback through the game.
Since I don't own either Mac or Linux computers, I'd be glad to get feedback on whether it runs on these systems as it should.

Java Checkers on the finish line

2010-03-20T22:03:00.002+01:00

It's been a while since I worked on my java checkers program (the general one, not the one for Android). It's something like a simple version of CheckerBoard, but it should run on all platforms if java lives up to its "write once run anywhere" promise. I just programmed the PDN save and load features which were the last features missing for an initial release. It will still need some finishing touches, but since I have about 16 hours of train-rides coming up in the next 48 hours and my laptop with me I hope to be able to apply these very soon and finally publish jCheckers!

Checkers Tutor reaches 1000 downloads

2010-01-17T20:05:00.004+01:00

Today, following another download-increasing update to version 1.06, Checkers Tutor has reached over 1000 total downloads. For reasons unclear to me (and from reading on the internet, everybody else too), Google does not offer a PC interface to the Android market, and therefore there are 3rd party websites that do offer such an interface. I use AndroLib, where I can see how many ratings and comments I got, and how the ratings develop over time. Apparently, Checkers Tutor has a rating of 3.33 out of 5, after 9 ratings. Unfortunately, not a single comment on what could be improved...
Androlib also has some download statistics. According to these, of currently 23'477 apps, 61.6% have been downloaded less than 1000 times. So CT is in the top 38.4% of all apps; and only 19.9% of all apps (or 4672) are in the category above with more than 5000 downloads. So CT isn't doing too bad, then again the other checkers programs out there are doing better or much better - and when I run out of upgrade ideas, my downloads will slow down to a trickle once again. I have two upgrade ideas left, but then it will be time to leave CT to its own devices on Android market.

Checkers Tutor 1.04, 1.05 etc.

2010-01-10T18:50:00.005+01:00

The Android market has a developer console which tells developers how often their application has been downloaded, how many active installations of it there are, and how the application is rated by the users. These stats are interesting, but not really up to Google standards - for example, you have no clue about how your downloads are distributed over time, and I have been logging in to my dev console every night to see how my Checkers Tutor is doing (it would be so much nicer if daily/weekly/monthly stats were available...). I have noticed that whenever I publish an update of Checkers Tutor, the number of downloads increases massively. I can also see that the number of active installs increases too, so I guess that my app is more visible on the Android market for perhaps a day after an update (but this is pure speculation). Anyway, seeing that my download stats are disappointing, I will be making some incremental updates to Checkers Tutor in the hope of attracting more users (1.04 released, 1.05 going up tonight, and 1.06 already planned), and perhaps gaining visibility in the Android Market (which is probably a combination of downloads and rating, but again this is guesswork). One problem which all checkers apps seem to have in common is that many people don't know that you must capture if you can in checkers. Aart Bik's Checkers for Android is by far the most downloaded checkers app, and it seems that about half of it's comments are "stupid - computer cheats" or "don't install - can't make moves I want to". And the ratings are correspondingly low. Unfortunately, Aart put in an option to make captures optional in his program, which is a bit of a shame because these people should learn how to play checkers for real...

Checkers Tutor 1.03

2009-12-31T14:01:00.009+01:00

I just published version 1.03 of Checkers Tutor on the Android Market. It has improved move input, displays the current level in the title bar, displays the last move with a blue arrow instead of not-so-nice highlighted squares, and fixes a bug in the arrow rendering for capture moves when the board is flipped. Behind the scenes, I cleaned up a bit again, but my board class is still a God Object which isn't nice. The screenshot below shows how it looks (still quite similar to version 1.0!).

Checkers Tutor has some features that are better than what I have in CheckerBoard

The move input is smarter: clicking on a piece that only has one legal move immediately executes that move (like in CheckerBoard), but also clicking on a square that can only be reached by one piece executes that move (unlike in CheckerBoard). This is nice because on those tiny mobile phone screens it's probably not easy to input moves, and every click you can save helps.
All legal moves can be displayed with yellow arrows to teach the rules.
The last move played can be shown with a blue arrow.
The beginner level attempts to reach a bad (but not immediately losing) position at all times. This should avoid frustration for beginners, who are usually not happy with my PC programs because they lose too often.

Some other things are not so nice yet:

The checkers engine is not as strong as I would like it to be. A large part of this is the low speed of the hardware, but I must admit that I haven't worked too hard on improving my Java checkers engine. It will most probably be more than good enough for 99% of the users. Nevertheless, a small opening book and perhaps endgame databases up to 4 pieces would greatly enhance its play, as would some more work on the evaluation function.
The game is not saved when you quit and return (or when you switch the display from portrait to landscape mode or vice versa), only the current position. You cannot undo any moves made in the last session.
There is not much advice to help a novice what to do with the game after installation. I would like to add something like Tips on Startup to improve this.
Move input is limited to touch, but perhaps on phones with small screens this is not practical, and adding keyboard support would be nice.
And probably many other things that I forget...

However, my christmas holidays are coming to an end, so the next update will have to wait a bit.

Checkers Tutor 1.02

2009-12-27T18:44:00.006+01:00

In the 5 days since the publication of Checkers Tutor for Android, I fiddled around with it a bit. I added a feature to display all legal moves in the current position (it claims to be a tutor after all...), and I fixed some minor bugs: v1.02 now also displays properly in the landscape mode and the board numbers scale better (also on hi-res devices). Behind the scenes, I cleaned up the user interface code a bit to make it more readable, maintainable and less bug-prone. As usual with this cleaning business, it never actually ends. My board class has more than 700 lines of code, and after reading Robert C. Martin's nice book titled Clean Code, I must assume that that is too much, and besides I find a couple of the code smells he lists in my code...
These things aside, I'm afraid that my Checkers Tutor has missed the boat anyway - it got 228 downloads in its first 5 days, which means nearly none compared to Aart Bik's Checkers for Android, which apparently got over 250'000 downloads in one year (see Aart's blog for more information). This is the usual punishment for coming late to the party - I could have published Checkers Tutor in August, but somehow felt I should still add zillions of features to make it better than Aart's app - in the end I never added these features, and the early bird has caught the worm - the attention of the Android Market, where often-downloaded programs are more visible, and thus go in a positive feedback loop.

Blog labels

2009-12-26T13:18:00.003+01:00

I added labels to nearly all posts on this blog, so that it is now much easier to find specific information. I have no idea whether anyone might be looking for anything here, but if so, it will be much easier to find things now! I am a bit surprised that suicide checkers takes the top spot in the labels list to the right...

Checkers Tutor for Android published!

2009-12-23T01:20:00.002+01:00

I finally got round to publishing my Android checkers program - it *should* be available on the Android market under the name "Checkers Tutor" - but since I don't have an Android phone I have no way of knowing whether it really is there!

CheckerBoard 1.7 & co.

2009-12-21T20:43:00.003+01:00

I just published a new version of CheckerBoard on my website. CB 1.7 has some minor bugs fixed, and doesn't write to the program files - CheckerBoard directory any more, which was a problem with the UAC (user account control) of Windows Vista and Windows Seven. Most of the changes in CB 1.7 were contributed by Ed Gilbert; thanks a lot Ed!
The CB source code is also available, but still rather difficult to comprehend.

I also updated the engines to comply with Vista/Win7, Cake and the Kingscourt engine didn't work with the new OS versions unless run with administrator rights. The CB install package now also includes Suicidal Cake with a 4-piece endgame database for suicide checkers and an opening book. I worked on suicide checkers about 3 years ago, and thought it would be a shame to leave what might be the world's best suicide checkers program rot on the shelf...

CB and Windows 7

2009-12-16T21:46:00.003+01:00

I'm writing this post on my brand-new Windows 7. Unlike Vista to which I took an instant dislike, this product seems to be much more user-friendly (UAC...) and the harddisk isn't working for about an hour after startup. Of course, the very first thing I did with Win7 was to test whether CheckerBoard was working on it, and it is - however, it has to be run as Administrator, otherwise it crashes. I think it was the same with Windows Vista (but I can't remember), and I hope I will have some time during the christmas holidays to sort out these issues.

Checkers for Android Phones

2009-08-11T22:05:00.004+02:00

It's been a while since I worked on my Java program. Actually, the underlying purpose of writing a Java checkers program was to (1) learn Java and (2) write a checkers program for the Android operating system running on the Google phones. There are two checkers programs for the iPhone based on my simple checkers engine, and since developing for the iPhone seems to be a PITA or at least some kind of licensing hell, I was never interested. The much more open philosophy of Android attracted me however, and my checkers program is already running on my emulator. It manages to search about 5000 positions per second, i.e. it's nearly 1000x slower than my corresponding PC program, and therefore also quite a bit weaker. But since it incorporates a lot of the stuff that I learned during the many years of programming Cake, it plays a decent game nevertheless. I worked hard on it during the last two weeks on my mountain holidays (whenever I wasn't climbing the mountains), and it's already a working program. However, I may have overdone things a bit trying to put a lot of features into the program, so it won't be ready today or tomorrow, but hopefully before the summer is out.

Multi-core KingsRow tested

2009-07-15T22:45:00.008+02:00

I have been testing KingsRow 1.16d against Cake 1.8x12 on my quadcore machine. Here are some results of engine matches at 5 seconds per move:


Cake 1.8x12 - KingsRow 1.16d (1 core)  +19 -14 =255
Cake 1.8x12 - KingsRow 1.16d (2 cores) +19 -18 =251
Cake 1.8x12 - KingsRow 1.16d (4 cores) +18 -19 =251

I had been expecting Cake to be slaughtered by the multi-core version of KingsRow, but apparently it's not that bad. To check whether or not it might be a bug in the multithreaded search of KingsRow, I played a match with Cake and KingsRow running on 1 core, but KingsRow got 10 seconds per move - so essentially this should reproduce the second match above. I found


Cake 1.8x12 - KingsRow 1.16d (10s)  +17 -21 =250

There is always some variability in engine matches, otherwise one might conclude that the 2-core version of KingsRow was not performing as well as KingsRow with twice the search time. As it is, I don't quite know what to make of it.

KingsRow goes multicore!

2009-07-14T15:19:00.004+02:00

The amazing Ed Gilbert has done it again: he rewrote his KingsRow engine so that it can use multiple CPUs. While he was at it, he also fixed a few bugs in CheckerBoard. You can download a new version of CheckerBoard, and the multi-CPU-KingsRow on Ed's webpage. Enjoy!

Java Checkers progress

2009-05-19T18:38:00.003+02:00

I've continued working on my Java checkers program, and it has an interface similar to CheckerBoard now, and plays a decent game (albeit without opening or endgame databases). I also worked on a beginner level that will be less frustrating than CheckerBoard is now!
However, work on the interface is slow, as I feared. I want to add PDN support, and while writing a PDN parser was simple, I find it quite hard to use the Swing Table to display the games when loading them. Oh well, at some point I will either give up on the PDN feature and publish anyway or find out how to use it....

Java checkers' first draw against Cake

2009-03-18T22:48:00.003+01:00

My Java checkers engine now has its own - very primitive - GUI based on Swing, and I can let it play games against my other engines. Here is its first game against Cake:

[Event "test game"]
[Date "2009-03-18"]
[Black "Cake 1.8"]
[White "Java engine"]
[Result "1/2-1/2"]
1. 11-15 22-18 2. 15x22 25x18 3. 8-11 29-25 4. 4-8 25-22 5. 12-16 24-19 6. 16-20 19-15 7. 10x19 23x16 8. 6-10 16-12 9. 9-14 18x9 10. 5x14 26-23 11. 2-6 22-18 12. 14-17 21x14 13. 10x17 31-26 14. 6-10 23-19 15. 1-6 19-15 16. 10x19 26-22 17. 17x26 30x16 18. 6-10 28-24 19. 10-15 18-14 20. 15-18 14-10 21. 7x14 16x7 22. 3x10 12x3 23. 18-22 3-7 24. 22-26 7-2 25. 10-15 2-7 26. 15-18 7-10 27. 14-17 10-14 28. 18-22 14x21 29. 26-31 21-17 30. 22-25 17-22 31. 25-30 32-28 32. 30-26 22-25 33. 26-30 25-22 34. 30-26 22-18 35. 26-30 1/2-1/2

This one draw doesn't mean too much of course - in its next game, it got into trouble against simple checkers, but just managed to escape with a draw. There is still a lot of knowledge missing in the evaluation function... And the GUI will need a lot more attention too!

Java perft, again

2009-03-10T19:05:00.004+01:00

After some more optimizations my Java perft now runs much faster than before, it is now nearly half as fast as the C code. I would have expected much less from Java and am pleasantly surprised. I'm quite happy already with the Java engine, so now for the hard part - creating an interface....

perft 1 time 1 positions 7 kN/s 7
perft 2 time 1 positions 49 kN/s 49
perft 3 time 1 positions 302 kN/s 302
perft 4 time 1 positions 1469 kN/s 1469
perft 5 time 1 positions 7361 kN/s 7361
perft 6 time 15 positions 36768 kN/s 2451
perft 7 time 1 positions 179740 kN/s 179740
perft 8 time 63 positions 845931 kN/s 13427
perft 9 time 250 positions 3963680 kN/s 15854
perft 10 time 1156 positions 18391564 kN/s 15909
perft 11 time 5437 positions 85242128 kN/s 15678
perft 12 time 24954 positions 388623673 kN/s 15573

Java checkers' first sensible game

2009-03-08T21:56:00.004+01:00

After improving the evaluation function a bit and after adding some standard search improvements, my Java checkers engine now appears to be playing a good game. It searches 3 million positions per second on my 2GHz Core Duo laptop, and typically gets around 17 ply search depth within a few seconds (that is faster than simple checkers, and a few ply deeper than simple checkers). It can't use endgame databases (yet?!) and has no opening book, but apart from that it is "Cake light" - a simplified version of Cake, using parts of the evaluation and parts of the search strategies that Cake does - but all on a much less complex level. The code is a joy to read compared to the Cake source code :-) (and much shorter). I will still have to improve the "Javaness" of the code - coming from a procedural language, I am writing C-style code in Java...

Here is the first sensible game of the engine playing against itself - red got a winning position but then blew it. But at least this already looks like checkers to me.

[Event "test game"]
[Date "2009-03-08"]
[Black "Java Engine"]
[White "Java Engine"]
[Result "1/2-1/2"]
1. 11-15 22-18 2. 15x22 25x18 3. 8-11 29-25 4. 4-8 25-22 5. 11-16 23-19 6. 16x23 26x19 7. 9-14 18x9 8. 5x14 27-23 9. 8-11 22-18 10. 14-17 21x14 11. 10x17 24-20 12. 17-22 32-27 13. 1-5 30-26 14. 6-10 26x17 15. 10-15 19x10 16. 7x21 23-19 17. 2-7 27-24 18. 21-25 19-16 19. 12x19 24x8 20. 3x12 18-14 21. 25-30 28-24 22. 30-25 31-26 23. 25-21 26-22 24. 21-25 22-18 25. 25-22 18-15 26. 22-26 15-10 27. 5-9 10x3 28. 9x18 24-19 29. 18-22 3-7

Java checkers' first game

2009-03-06T23:06:00.005+01:00

My as yet unnamed Java checkers engine just played its first game against itself! Apparently, there is still some room for improvement...

[Event "Test"]
[Date "3rd March 2009"]
[Black "Java Engine"]
[White "Java Engine"]
[Result "1/2-1/2"]
1. 11-15 22-18 2. 15x22 25x18 3. 8-11 29-25 4. 12-16 25-22 5. 16-20 24-19 6. 9-13 19-16 7. 5-9 28-24 8. 10-15 16-12 9. 6-10 23-19 10. 11-16 18x11 11. 16x23 27x18 12. 20x27 32x23 13. 7x16 22-17 14. 13x22 26x17 15. 9-13 30-26 16. 13x22 26x17 17. 16-20 31-27 18. 4-8 23-19 19. 8-11 17-13 20. 11-16 27-23 21. 20-24 18-14 22. 10x17 21x14 23. 24-27 19-15 24. 27-31 15-11 25. 31-26 23-18 26. 16-20 11-8 27. 26-22 18-15 28. 22-17 15-10 29. 20-24 8-4 30. 2-6 10-7 31. 17x10 7-2 32. 24-28 2x9 33. 1-5 4-8 34. 5x14 13-9 35. 28-32 9-5 36. 10-15 5-1 37. 14-18 8-4 38. 18-23 1-6 39. 23-27 6-2 40. 27-31 2-6 41. 15-11 6-2 42. 31-26 2-6 43. 32-28 6-2 44. 26-23 2-6 45. 23-26 6-2 46. 26-23 2-6 47. 23-26 6-2 48. 26-23 2-6 49. 23-26 6-2 50. 26-23 2-6

and a draw by repetition because it doesn't yet understand the concept of progress...

Java perft

2009-03-03T23:12:00.006+01:00

I just finished debugging a Java checkers move generator - thanks to perft I found some bugs, and just watched the first game of my Java checkers engine played against itself (not a nice sight). Not surprisingly (at least to me), the Java code runs much slower than the C code - I found a factor 3.2 difference. Is that just me, or is it Java??

C (Cake's code without move ordering)
depth 1 positions 7 time 0.000000 1.$ kN/s
depth 2 positions 49 time 0.000000 1.$ kN/s
depth 3 positions 302 time 0.000000 1.$ kN/s
depth 4 positions 1469 time 0.015000 97.9 kN/s
depth 5 positions 7361 time 0.000000 1.$ kN/s
depth 6 positions 36768 time 0.000000 1.$ kN/s
depth 7 positions 179740 time 0.000000 1.$ kN/s
depth 8 positions 845931 time 0.063000 13427.5 kN/s
depth 9 positions 3963680 time 0.156000 25408.2 kN/s
depth 10 positions 18391564 time 0.547000 33622.6 kN/s
depth 11 positions 85242128 time 2.656000 32094.2 kN/s
depth 12 positions 388623673 time 12.266000 31683.0 kN/s

Java
perft 1:7 1ms 7000positions/sec
perft 2:49 1ms 49000positions/sec
perft 3:302 1ms 302000positions/sec
perft 4:1469 17ms 86000positions/sec
perft 5:7361 1ms 7361000positions/sec
perft 6:36768 16ms 2298000positions/sec
perft 7:179740 17ms 10572000positions/sec
perft 8:845931 79ms 10707000positions/sec
perft 9:3963680 392ms 10111000positions/sec
perft 10:18391564 1813ms 10144000positions/sec
perft 11:85242128 8486ms 10045000positions/sec
perft 12:388623673 39141ms 9928000positions/sec

A postscript a couple of days later: I managed to improve my Java code a bit, it is now only 2.3 times slower than the C code. I suppose that is about the best one can hope for with Java - or??

perft for checkers

2009-02-15T21:31:00.004+01:00

A couple of days ago I got a mail from Aart Bik, a programmer working at Google. He is currently developing a checkers application (among others) for the Google android platform (aka gPhone). He asked me about perft numbers for checkers. Perft is an invention of the chess programming community, a test to verify the correctness of the move generator, by printing how many legal moves exist in a search tree to depth N from the current position. Although I have this function in my chess engine, I never thought of adding it to Cake until now. However, Aart is right, and a perft function is always good to have for debugging purposes, so I added it to Cake. In the next CheckerBoard/Cake release, Cake will have this functionality. For starters, here are the numbers Cake reports from the initial position:


depth 1 positions 7
depth 2 positions 49
depth 3 positions 302
depth 4 positions 1469
depth 5 positions 7361
depth 6 positions 36768
depth 7 positions 179740
depth 8 positions 845931
depth 9 positions 3963680
depth 10 positions 18391564
depth 11 positions 85242128
depth 12 positions 388623673

Aart is happy too, since his numbers match. If you are interested in his applications for the gPhone, then check out his blog.

Dweeb!

2009-01-26T22:31:00.004+01:00

I just heard that Jonathan Schaeffer published a revised version of his book on Chinook, One Jump Ahead. I own it, and it was one of the things that motivated me to work on checkers. In the new version, some new material was added on the solution of checkers by the Chinook team, which probably also makes good reading. I also get mentioned in the book - although I'm rather on the receiving end:

"Darse Billings and many other people were upset at the junk that was being posted on the web. Darse sent out the following message:

Who the hell is this dweeb? I read the report of the Las Vegas tournament and was appalled with his obnoxious and slanderous comments against Jonathan. Someone should teach him some manners.
Personally, I see no reason for Jonathan to accept a challenge from NEMESIS - CHINOOK doesn't have to prove anything to anywone. The program did enough talking eight years ago - long before the pipsqueaks started squeaking. But if he does grant them a match, I hope it will only be after sufficient preparation to blow them out of the water. Punks."

Darse (and Schaeffer with his Junk) is referring to my report on the Las Vegas world championship (As a side note, Darse was not on the Chinook team, and not a checkers programmer - exactly what his qualifications would be to judge the claims in my report remains a mystery to me).

Well, at least I learned some new English curse-words :-)

4 in a row source code

2008-08-07T00:30:00.004+02:00

I just published the source code of my 4 in a row program on my four in a row page. While this doesn't appear to fit in a computer checkers blog, I think it does belong for two reasons: first, it is an example of how to write a high-performance game program. Second, this is the second part of my plan to publish some of my source code (CheckerBoard came in first). More to follow...

CheckerBoard source code release

2008-07-22T22:45:00.004+02:00

My interest in computer checkers is waning - partly because the game is solved, partly because other interests are taking more of my time these days. I still sometimes get mail asking for new features in CheckerBoard, but I haven't done much lately. Since I don't think this will change anytime soon, I have made the source code of CheckerBoard (in version 1.651) public. This code can be used in any way you might see fit; I'm not going to bother with some kind of public license.
I am very much aware that the code is neither particularly good nor clean; CheckerBoard was - like perhaps most software - not really designed well, i.e. it started out as a simple program and then I kept on adding more and more things to it, and so the whole program structure isn't nice. Some of the source code is really old, written at a time when my programming skills were even less developed than they are now. And of course, I'm not a trained programmer who learned how to properly develop software. All of this will make the CheckerBoard source code rather hard to understand, but if you have a lot of patience and a decent working knowledge of standard C, then you can probably get to grips with it.

CheckerBoard 1.651

2008-07-18T12:37:00.003+02:00

I just published CheckerBoard 1.651 on my webpage. This release fixes four things:

1) a serious synchronization bug between the multiple threads of CheckerBoard, which could show up in autoplay and engine match mode; on my two newer machines that I usually use for development, this bug didn't show, but on my oldest machine it was very obvious. Even if the bug didn't show clearly on the newer machines, it is possible that it affects engine match outcomes - an upgrade is therefore strongly recommended if you run engine matches.

2) a small bug with graphics updating when changing the piece set (the board would update, the pieces only on the next window resizing).

3) export to HTML now also works from setup positions for Italian checkers (it always worked for English checkers)

4) I forgot to include the file 11man_FEN.txt which is used for 11-man engine matches. It contains 2400 of the 2500 possible 11-man starting positions. 100 of the positions are omitted, because they are likely wins for one side. The newest release includes this file, so that 11-man engine matches with 4800 games can be run (if you have the patience...) for better statistics than with standard engine matches.

If I get no negative feedback on this release, I will also publish the source code of CheckerBoard, since I find it increasingly difficult to find the time to work on CB - making the source public is a better alternative to stopping the development altogether.

But now, enjoy your bug-free 11-man matches!

CB 1.65 bug

2008-07-13T20:06:00.004+02:00

It has been nearly 3 months since I released CheckerBoard 1.65, and I hate to admit that I got bug reports nearly instantly after its release. I finally took the time to look into them (partly because my girlfriend is in Spitzbergen). I cleaned up a lot of my source code in CB 1.65 with the goal of making it public with this release, and unfortunately, I managed to add a rather serious synchronization bug to it. I believe to have found it, some final testing is still required, but probably there will soon be an update available.

Engine match mania

2008-02-22T19:53:00.008+01:00

Over the last week, I tested several versions of my latest checkers engine (which carries the rather bland name Cake 1.8) - and I did this on all of my three computers. I own a AMD64 desktop, a CoreDuo laptop and a CoreQuad Desktop. These machines are all about equally fast; the CoreQuad is a bit faster than the other two, it also runs a 64-bit windows. Here are the results of my engine matches against KingsRow 1.16c:


Engine           CoreQuad CoreDuo  AMD64    total
-------------------------------------------------
Cake 1.8 v1      +28-12   +27-18   +27-20   82-50
Cake 1.8 v2      +19-17   +25-17   +32-15   76-49
Cake 1.8 v3      +23-15   +24-19   +27-17   74-51
Cake 1.8 v4      +21-15   +23-17   +26-17   70-49
Cake Manchester  +23-11   +24-13   +24-21   71-45

The results are a mess! I ordered the different versions of Cake 1.8 according to their overall result, and while you can see that v1 is best overall, it is worse than v2 on the AMD64 and worse than Cake Manchester on the CoreDuo. Which means that if I had only been testing on the CoreDuo, I would have been disgusted with the performance of my new program, because it's worse than the old one, and if I had been testing on the AMD64, I would have chosen v2 rather than v1. Which of course means that running engine matches on a single computer (as I did for the past 7 years or so) is clearly insufficient, and it also casts some doubt on the current methodology of using 3 computers - how do I know that using 3 computers is enough? Wouldn't 10 be better? All in all, this is quite a disgusting discovery, and I'm at a bit of a loss of how to proceed when optimizing my engine :-(

Bug squashing

2008-02-07T23:09:00.001+01:00

Yesterday and today I found bugs in Cake's evaluation. I was looking at some games that Cake had lost, and made a change in the evaluation which should have improved the situation. However, although the evaluation was different, the output of the engine remained the same - the exact same number of nodes searched with the same value for the position. That made me *very* suspicious, and I looked at the code a bit more closely, and discovered that during my code cleanup of last summer I had broken a really important piece of knowledge. Being suspicious, I continued looking for bugs and found one minor bug and one cosmetic bug. The match result improved drastically after stomping the first bug, from +19-16 @5s/move to +26-11. I don't have much hope that the minor bug will make a big difference but soon I will see!

Multi-Core speed

2008-02-04T22:23:00.002+01:00

Nowadays, CPUs aren't getting much faster in terms of clock speed, but the manufacturers are putting multiple cores in one CPU. While this gives a lot more bang for the buck, it is a challenge for programmers to make use of the newly available resources. Some problems are easy to parallelize, while others are much more difficult. Unfortunately, tree searching such as in two-player-strategy-games belongs to the second class: it's not straightforward at all to implement a parallel game tree search. Of course there are solutions for this, the best-known is called YBWC for young brother wait concept. This is quite easy to explain with words, but really programming it is something different :-(
I haven't managed to find any sensible description of the algorithm with some real code, except for the source code of Crafty, a strong free chess engine. While this is documented quite well on the source code level, there are very many source code files and many of them have the required changes for the parallel search, and it's all very confusing to me. I wonder if there is any sensible YBWC tutorial anywhere on the net?

Anyway, my own plans were different to start with: All I wanted to do was to make my book generator work in parallel - it is quite easy to have multiple threads running on a multi-core-CPU when each thread is just doing a standard search on its own position. The big difficulty only arises when all threads are supposed to help search the same position, because they have to start communicating with each other.

The only problem in having multiple threads running simultaneously is the following: the endgame database access code has to be protected from being accessed by multiple threads, since confusion could occur when two threads try to load data from disk at the same time. In such situations programmers use a "lock" to prevent other threads from accessing critical code when one thread starts using it. This thread has to free up the critical code again once it is done, so that the other threads can also use it. Obviously, this whole process might slow down the program a lot, because one thread can be blocking the others - and the only way of knowing whether this is a problem is to try! I made Cake thread-safe last summer, and finally tested the speed on my new quadcore yesterday. Here is the result:

1 thread: 2050 kN/s
2 threads: 2000 kN/s
4 threads: 1815 kN/s

Running 2 threads simultaneously thus results in a speed loss of about 2.5%, while running 4 threads gives a loss of 11%. Of course, that is not a big price to pay, since in total you are getting 4x89% = 356% out of your CPU compared to having a single thread running. I also have to admit that I just put the whole database lookup call in a critical section; perhaps it is possible to make that more efficient by only putting the parts of the database lookup that affect the database cache in a critical section. Nevertheless, I'm afraid I have no excuses any more and should be working on a multi-threaded book generator now...

Heavyweight match

2008-01-17T23:17:00.001+01:00

I just finished running an engine match between the 64-bit versions of Cake and KingsRow. Cake managed a narrow win, but what makes even happier is that the entire engine match ran without problems, i.e. CB64 and Cake64 and KingsRow64 are all stable enough to run for 12 hours without any errors. I will probably publish the 64-bit versions in a couple of weeks.

As an aside, I got so annoyed with Windows Vista UAC (user account control) popping up TWO message boxes to confirm when I just want to rename a file that I ended up disabling UAC. I really wonder what the MS guys were thinking when they invented this feature. One message box for renaming a file would already be a huge PITA, but two... I guess the only people who don't disable UAC are those who don't know how to do it!

Some more Vista madness: I also noticed that by default my system was set to defragment its harddisk daily, run a full virus check daily, and run the pretty much useless Windows Defender. My system (a QuadCore with 4GB RAM) used to access the harddisk permanently for about 15-30 minutes after the system start. With all this stuff disabled, it is much better. In my quest for energy efficiency, I bought an 80+ power supply (80plus.org), which is not only energy efficient but also very silent (it only generates little heat and thus needs less ventilation than a standard power supply). However, with a loudish harddisk I didn't have any benefit of that. Now I do :-)

64-bit speedups

2008-01-14T21:32:00.001+01:00

I tried to find out how much performance increase a 64-bit compile will give compared to the 32-bit compile. I tested three different programs: my Connect 4, Cake and KingsRow. I also have a speedup reported by Ed Gilbert for his international checkers program, KingsRow-10. Here are the numbers:

KingsRow: 5.8%
Cake: 6.4%
Connect 4: 11.6%
KingsRow-10: 42.9%

This list shows that all programs are able to benefit from the 64-bit compile, although the gain is rather moderate for all programs except KingsRow-10. Why can some programs benefit more than others? Probably this has to do with how much they make use of 64-bit operations. For example, my Connect 4 program uses a 64-bit representation of the board. KingsRow and Cake use 32-bit representations and don't really have any use for the larger word size on the 64-bit machine. KingsRow-10 on the other hand also uses 64-bit numbers for its board representation and benefits much more than any other program on the list.

With all these numbers I have to add that there are some points to be considered: The KingsRow 32/64-bit versions don't seem to search the exact same tree - in kN/s searched, KR-64 was 5.8% faster, but its search time was only 2.6% lower. Additionally, KR wasn't using the endgame database during this test, since it doesn't recognize it for some reason on my system. Cake 32/64 searches exactly the same number of nodes on the one-minute search I used for this test. Cake32 makes use of some assembler instructions which Cake64 does not, so probably the speed difference would be a bit larger if I found out how to program these functions in 64-bit assembler. The same is true for Connect 4 (For the experts: I don't have a LSB function in assembler for the 64-bit versions).

Cake 64

2008-01-13T23:30:00.001+01:00

I recently bought a new motherboard/CPU for the computer that was generating the opening book database for Cake. My new machine is the most powerful I ever had, with a Core Quad and 4 GB of RAM. For curiosity's sake, I also installed Windows Vista on that machine. I'm not at all convinced by Microsoft's new OS, but at least it gives me the opportunity to finally run my 64-bit compiles myself. Thanks to this, I found the bug in the 64-bit version of Cake, and of course it was a 32/64-bit issue. I was computing the size of a memory block full of pointers for the endgame database with

char *pointer;
int memsize = blocknum * sizeof(int);
pointer = malloc(memsize);

since I had assumed that sizeof(int) would change to 8 byte on the 64-bit machine. But it stayed at 4 bytes, while pointers do need 8 bytes, and of course the whole thing crashed. I replaced the sizeof(int) with sizeof(pointer) and now it works. It appears that this was the only portability issue; I now have a working 64-bit version of Cake on my machine. By a strange coincidence I clocked it to be 6.4% faster than the 32-bit version.

Housekeeping

2007-08-22T18:20:00.001+02:00

I recently inherited the house of my grandfather, and now have a lot more housekeeping to do than earlier. Somehow, this might have helped me in my decision to do some housekeeping with Cake. Those of you who have programmed probably know the feeling: even if you started out with a more or less clean concept (I certainly didn't with Cake), things eventually get out of hand. You add an idea here, put in a quick fix there, and before you know it, your code is unreadable and unmaintainable. That's about the state that Cake was in before my summer holidays in the Austrian mountains. There, besides reading the Harry Potter finale and climbing some mountains, I cleaned up Cake's source code during two whole weeks. That much time is necessary, since you really have to stand back, and get an overview over your whole program to decide exactly how you want to do your cleaning up. You can't just do it on a single day, or fix it by programming one evening per month - until you get back to programming, you will have forgotten everything again (at least that's what would happen to me, but then I turned 36 recently!).
The result of two weeks of hard programming is that there are no global variables left in Cake, that Cake can be switched to thread-safe mode (at a small speed penalty), and that much of Cake's code is now much clearer and cleaner than before. It doesn't play any better at all though - but now that I have (nearly) finished the housekeeping part, I might be more inclined to work on it again!

64-bit versions of CheckerBoard and Cake

2007-02-18T12:38:00.001+01:00

Linux users could already benefit from the new powerful 64-bit processors for quite some time, while M$'s win64 never really got out of its beta phase. With the release of Windows Vista, this has changed, and 64-bit computing is now also available to the masses. I run neither Linux nor Vista, but I do have a compiler capable of producing 64-bit executables. I wonder whether they will run under 64-bit Vista? If you happen to own a 64-bit Vista, you can try it by downloading CB_64.zip (264KB), and installing it in your CheckerBoard directory. To do this, you need to extract checkerboard64.exe to the CheckerBoard directory, and CakeM64.dll to your engines directory. Run checkerboard64.exe and choose CakeM64.dll as your engine. Let me know what happens!

Wow! CheckerBoard runs under Vista

2007-02-09T21:33:00.001+01:00

I haven't been doing any checkers-related stuff lately. I'm all the more pleased to hear that CheckerBoard and Cake run under M$ newest OS - that means I don't have to do any checkers-related stuff in the near future :-)
And no, of course I didn't try this myself: I'm going to avoid Vista for as long as possible!

Computer power consumption

2006-12-19T23:23:00.000+01:00

In a previous post, I promised to measure the power consumption of my PCs. I finally did this, and got the following results:


Computer off, power supply off: ......... 0 Watt
Computer off: ........................... 7 Watt
Windows idle after startup: ............ 64 Watt
Book generator running: ............... 112 Watt
Monitor (Flatscreen) alone: ............ 36 Watt

This result was slightly surprising for me. I would have expected my PC to use more power than 112 Watt when running Cake - after all, it is using the CPU fully and also using the harddisk quite a bit. What are all these 350 Watt power supplies for, I wonder? The result also changes my checkers programming economics post: My book generator now "only" uses 2.7kWh per day, or 0.35$ a day. Since I have been computing opening books for about 4 years now, that puts the worth of the opening book at 500$.
On the other hand, 112 Watt is still a lot, given that we should be moving towards the 2000-Watt-Society - I am using over 5% of my power consumption for something rather useless like checkers book building....

I also measured the power consumption of my other PCs. Unsurprisingly, my other desktop PC is quite similar to the book generator PC, while my old laptop with a 1.4GHz Centrino processor uses only 23.5 Watt idle and 39 Watt when running Cake. Turning off the LCD screen saves another 6 Watt. Here's an interesting thing: on my desktop PC (with a AMD 64 3400+), running Cake costs about 50 Watt more compared to the idle state of the PC for nearly 2000 kN/s. On my laptop, running Cake at about 70% of that speed costs only 15 Watt, or about 3 times less. That means that my laptop is producing about twice as many nodes/second with the same amount of energy. Unfortunately, I measured these numbers before I got my new Core Duo machine, so I have no figures for that.

Core Duo!

2006-12-18T20:33:00.001+01:00

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

2006-12-01T21:33:00.000+01:00

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

2006-11-06T23:46:00.001+01:00

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

2006-11-01T08:13:00.001+01:00

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

2006-09-17T21:37:00.000+02:00

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

2006-09-05T20:55:00.001+02:00

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

2006-08-30T22:33:00.001+02:00

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

2006-06-03T10:40:00.001+02:00

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

2006-04-26T23:56:00.001+02:00

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!

2006-04-26T00:45:00.001+02:00

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

2006-04-22T07:01:00.001+02:00

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!

2006-04-18T22:45:00.001+02:00

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

2006-04-14T16:17:00.000+02:00

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

2006-04-03T23:55:00.001+02:00

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!

Switzerland 6, Canada 0!

2006-03-10T00:36:00.001+01:00

The suicide checkers match ended in an even clearer result than the hockey match between Switzerland and Canada at the olympic games: Suicidal Cake beat Roshi47 4-0. Its authors then challenged me to two games human-human, and I managed to raise the Swiss score to 6-0. All in all, a surprisingly lopsided affair. I wrote a short article on the match. I have a couple of afterthoughts on the match, which I will add to that article in a couple of days. All that is left to add right now is the following email which I received today:

To: Martin Fierz
From: Jonathan Schaeffer
Subject: Suicide Checkers
Date: Wed, 8 Mar 2006 16:48:02 -0700
X-Mailer: Apple Mail (2.746.2)

Congratulations! Experience trumps youth :) I think both
Mike and Frano are stunned at the result.

Now, that is something to be proud of :-)

The fastest suicide checkers loss?

2006-02-20T22:32:00.001+01:00

I've been playing around a bit with my book generator for suicide checkers because of the upcoming match against the Canadians. I was looking at early losses in suicide checkers, and this is the earliest I found so far:

1. 10-15 22-17 2. 6-10 23-19??

Red to move and win! Can you solve it? Can you find a faster way to lose a game of suicide checkers?

Tweaking the book generator, part 2

2006-02-15T22:24:00.001+01:00

At the end of last year I received the following email:

Hi, I recently played Cake Manchester 1.09d and set the time to 10 Seconds and used Best Moves, and Cake couldn't even draw. I analyzed the game and saw that Cake played terribly through out the game. I think that you should produce or if you already have then release a newer version because it's too easy for me.
Attached is the game that I won. Please view it.

Thanks

Yacoob

Attached was the following game:

[Event "I Lose"]
[Date "2005-12-29"]
[Black "Chikita Mia"]
[White "Yacoob"]
[Result "1-0"]
1. 11-15 24-19 2. 15x24 28x19 3. 8-11 22-18 4. 11-16 25-22 5. 16-20 32-28 6. 10-14 22-17 7. 9-13 17x10 8. 6x22 26x17 9. 13x22 30-26 10. 4-8 26x17 11. 8-11 29-25 12. 11-16 25-22 13. 5-9 19-15 14. 16-19 23x16 15. 12x19 17-13 16. 9-14 22-17 17. 14-18 17-14 18. 19-23 27-24 19. 20x27 31x24 20. 23-27 24-19 21. 27-31 14-9 22. 1-6 28-24 23. 31-27 24-20 24. 27-24 9-5 25. 18-23 19-16 26. 7-11 15x8 27. 3x19 5-1 28. 6-9 13x6 29. 2x9 21-17 30. 9-13 17-14 31. 23-27 20-16 32. 27-32 16-11 33. 19-23 11-8 34. 23-27 1-6 35. 27-31 6-10 36. 31-26 10-15 37. 26-22 14-10 38. 32-28 15-11 39. 13-17 8-3 40. 24-19 10-6 41. 22-18 3-8 42. 17-22 11-7 43. 18-15 6-1 44. 22-26 7-11 45. 15-18 1-6 46. 26-31 6-10 47. 31-27 8-4 48. 27-24 10-6 49. 24-20 6-10 50. 19-16 10-7 51. 16-12 7-3 52. 28-24 11-7 53. 24-19 4-8 54. 20-24 7-10 55. 18-15 10-7 56. 24-27 8-4 57. 27-23 4-8 58. 23-18 7-2 59. 19-16 2-6 60. 18-14 8-4 61. 16-11 6-1 62. 15-10 1-5 63. 10-6 5-1 64. 14-10 1-5 65. 6-1 5-9 66. 1-5 9-13 67. 10-15 13-17 68. 15-18 17-13 69. 18-22 4-8 70. 11x4 3-7 71. 4-8 7-10 72. 22-18 13-17 73. 18-14 10-15 74. 14x21 15-18 75. 8-11 18-23 76. 12-16 23-27 77. 16-19 27-32 78. 11-15 32-28 79. 5-9 28-32 80. 19-24 32-28 81. 9-14 28x17 82. 21x14 1-0

You can make up your own mind as to what I thought when I read that email and looked at the game - in particular check out the game headers :-)
But leaving these petty details aside, I checked on this game quickly - after all, it's not often that Cake loses a game so I decided to investigate. Most of the time, it's because Cake's published opening book has some errors left, and they are fixed in my 2-million-move-book. It turns out that in this game too, Cake is lost when it leaves the book with 9...30-26. I looked at my large book, and - the same error is in that book too! According to Basic Checkers, white should play 22-17 instead of 32-28 on his 5th move. I changed my book generator so that this line will be expanded sooner.
So what was the problem that this line wasn't expanded? Basically, it has a lot to do with the design of the book generator, which I wrote in december 2001. At that time, I only had a 6-piece endgame database, and I didn't foresee what would happen once I had the 8-piece database and 2 million book positions: Most of the positions that my book generator is looking at now are positions which are a more or less clear draw - Cake can see ahead far enough to hit the 8-piece database and return an evaluation of 0. When this started happening (years ago already!), I decided I didn't want the book generator to spend lots of time computing obviously drawn positions. There are many solutions to this problem, and unfortunately, I chose a rather bad solution (it was a quick fix - often a bad idea!): I decided to reduce the priority of positions (i.e. decrease the chance that the book generator would look at them again) which have a heuristic evaluation of 0. With heuristic evaluation I mean that Cake can already see the 0 evaluation in that position - it doesn't have to expand further to be able to back-propagate a 0 evaluation. That is what happens to all first moves: all seven first moves also have a 0 evaluation which has been propagated from the book tree - but they all have non-zero heuristic evaluations. In the example above, Cake produces a heuristic 0 towards the end of the book line, and that was enough for that line not to be expanded further. Now it's your turn to think: what could I do to make my book generator smarter?

Tweaking the book generator

2006-02-05T18:31:00.001+01:00

I was in the alps on my winter holiday for the past two weeks, and used the times in between skiing (when my knee hurt...) to tweak my book generator a bit. I knew of two lines in the book generator that were not what they should be. The first one goes like this:

1. 11-16 22-18 2. 10-14 25-22 3. 8-11 24-20

My openings database thinks that 8-11 is a big mistake because of 24-20 - because red must play 4. 16-19, sacrificing a man to draw. Now, if this 4. 16-19 line was expanded just a couple of moves further, it would play into the white doctor opening (1. 10-14 22-18 2. 12-16 24-20, and now 3. 16-19 is required to draw), which is in the book as a draw. However, this line is not expanded further because of the way the book generation works: if a move is thought to be clearly inferior, then it is not expanded any deeper, or only much later than the best move. In this example, 3. 7-10 is recognized as a draw, and therefore 3. 8-11 never got expanded much further. In a way, this is no serious error in the book, because it is meant only to find sound lines, and if you know one way to draw you don't need another. On the other hand, I would like my book to be a reference which checkers players can trust (once I publish it...), and if it doesn't know about this line, then people could easily be disappointed. The simplest fix to this problem is to tell the book generator to expand this specific line more deeply. This is also a very stupid approach, because the fact that the generator didn't expand this line is telling me that there may be other similar lines that it didn't expand and which would be worthy of expansion too. With over 2 million positions in the book, there is no way for me to check everything, so I have to make sure that whatever fix I make, it will affect the way that this line and others like it are expanded after the fix. In this case, I decided to penalize mistakes on the first 10 moves less than on later moves, causing an earlier expansion of the line above. I wanted the transition to be somewhat smooth so I used a weight of 0.05*depth + 0.5 with which I multiply the penalty for errors on the first 10 moves; for later moves the weight is 1.0. This change has had the desired effect: The line in question is now going to be expanded soon.

There is another line which I had to find a fix for, where even my 2-million-moves book still had a losing move in the book. It's a longer story so I'll keep that for my next post!

Suicide checkers challenge!

2006-02-04T08:53:00.001+01:00

I just received a mail from the Chinook creator, Jonathan Schaeffer. It says:

I have a couple of students who built a suicide checkers program
as a course project. They have tinkered around with it since then
and are curious to know just how good it is. Obviously it kills
all humans. I understand you have a strong suicide checkers program.
Would you be willing to have your program play a match with them?

I'm looking forward to giving SC another spin. On the downside, in the process of saving, synchronizing and backing up things, I seem to have lost the source code of both the latest SC and the latest endgame database builder for SC - I'm feeling pretty stupid! I still have the latest version of the programs and I hope I won't manage to lose those too...

Kingscourt solved!

2006-01-17T14:23:00.001+01:00

Today, my opening book generator for the game of Kingscourt terminated because it solved the game: white wins in approximately 62 half-moves ( Kingscourt is the checkers variant where crowning a man wins the game). The method with which I solved the game only gives a result and a complete opening book with which the win can be played out; there is no guarantee that this is the shortest possible win. If you want to try to outwit the perfect opponent, you can download the book: kingscourt_book.zip (~2MB). You will have to extract the book in your CheckerBoard directory (not the engines directory), and kingscourt.dll should recognize it. Once you get out of the opening book, you will have to let the dll compute the win, but this should take no longer than a few seconds.

The opening book for the proof contains about 200'000 nodes, and was constructed in about 4-5 months on an AMD Athlon 64 system, using kingscourt.dll to search each of these 200'000 nodes. Initially I thought the game would be easier to solve, and I didn't put too much effort into optimizing the algorithms - I'm sure there is a lot of room for improvement left.

The whole idea of automated opening book computation on which this proof is based is due to Thomas Lincke.

CheckerBoard 1.64!

2005-12-05T21:00:00.001+01:00

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

2005-12-04T23:47:00.001+01:00

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!?

2005-12-03T00:45:00.001+01:00

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

2005-11-26T10:06:00.001+01:00

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

2005-11-22T20:50:00.001+01:00

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

2005-11-21T23:31:00.001+01:00

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

2005-10-31T20:13:00.001+01:00

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!

2005-10-24T10:02:00.001+02:00

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

2005-10-23T23:35:00.001+02:00

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?

2005-10-20T13:12:00.001+02:00

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

2005-10-16T21:56:00.001+02:00

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

2005-09-20T13:40:00.001+02:00

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!

2005-09-15T11:40:00.001+02:00

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

2005-09-13T22:32:00.000+02:00

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

2005-09-12T21:48:00.001+02:00

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

2005-08-27T11:42:00.000+02:00

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!

2005-08-27T11:40:00.001+02:00

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

2005-08-10T00:18:00.001+02:00

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!

2005-08-09T20:07:00.001+02:00

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

2005-08-08T20:04:00.001+02:00

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!

2005-07-22T15:48:00.001+02:00

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

2005-07-16T22:36:00.002+02:00

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

2005-07-02T16:11:00.002+02: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

2005-06-25T16:12:00.001+02:00

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

2005-05-29T15:42:00.001+02:00

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

2005-05-22T16:33:00.001+02:00

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

2005-05-21T11:52:00.001+02:00

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

2005-05-18T13:30:00.001+02:00

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

2005-05-15T00:32:00.001+02:00

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!

2005-05-10T10:45:00.001+02:00

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

2005-05-08T11:16:00.001+02:00

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

2005-05-08T09:42:00.001+02:00

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

2005-05-04T09:37:00.001+02:00

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

2005-05-01T21:45:00.001+02:00

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

2005-04-29T08:46:00.001+02:00

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

2005-04-22T23:23:00.001+02:00

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

2005-04-22T00:19:00.001+02:00

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!