Checkers Tutor 1.03

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

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

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!

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.

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

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

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

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!

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

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

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

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

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

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

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

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!

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 :-)