BikDam: international checkers

Inspired by Rein Halbersma's kind encouragement, I have started some work on an international checkers engine. After all, "dammen" is the variant I grew up with in The Netherlands. Since I have implemented BikJump for chess, BikMove for American checkers, I decided to name this upcoming engine BikDam.

I already had some fun hacking a, hopefully, efficient move generator. The rules for captures were very interesting to implement. Here are the perft number from the start position of 10x10 international checkers (a.k.a. dammen). In contrast with my American checkers move generator, here duplicate captures are removed.

perft(1) = 9 in 0 ms.
perft(2) = 81 in 0 ms.
perft(3) = 658 in 0 ms.
perft(4) = 4265 in 0 ms.
perft(5) = 27117 in 1 ms. 27117.0 KN/s
perft(6) = 167140 in 3 ms. 55713.3 KN/s
perft(7) = 1049442 in 22 ms. 47701.9 KN/s
perft(8) = 6483961 in 78 ms. 83127.7 KN/s
perft(9) = 41022423 in 434 ms. 94521.7 KN/s
perft(10) = 258895763 in 2599 ms. 99613.6 KN/s
perft(11) = 166586139…

Perft for Checkers for Depth 28

My quest for deeper perft numbers for 8x8 checkers using has reached depth 28. Below you see the perft(28) breakdown per move, called "divide". As stated before, the numbers were computed on a cluster of machines, optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures.
At this point, the limits of 64-bit unsigned integers have been reached. Although there are obvious ways around these restrictions, this seems a very good time to give this (by now probably insane) project a rest. I have updated this OEIS entry up to depth 26, and may add the higher depths also when I am a bit more comfortable with these most recent results.
12-16 = 2400708339858199191
11-16 = 2431386196712611878
11-15 = 2231787529331259810
10-15 = 2186446356811761737
10-14 = 1872427919495823777
 9-14 = 2285893686261887442
 9-13 = 2969067990365356900
 -------------------------- perft(28) = 16377718018836900735

Perft for Checkers for Depth 27

With the new improvements in place, it would almost be a waste not to go deeper with my perft for checkers computation. Therefore, I computed perft(27) from the initial position of 8x8 checkers. Below you see the perft breakdown per move, called "divide". As stated before, these numbers were computed on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures.
move                 divide(27)
 12-16    =  516399283859880203
 11-16    =  519502096014967805
 11-15    =  476666239516455180
 10-15    =  468705060101275533
 10-14    =  400425747281243848
  9-14    =  486493422418651579
   9-13    =  631652334435528457 -------------------------------
perft(27) = 3499844183628002605
The implementation is "fault tolerant" against machine failures. Nevertheless, since I saw a few of these recoveries in this particular run, I may …

Perft for Checkers for Depth 26

I made some improvements to my distributed implementation for computing perft and divide numbers for 8x8 checkers, and now computed depth 26 from the initial position, shown below. As reported earlier, the numbers were computed on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. The move generator does not eliminate duplicate captures (viz. the situation where a king can capture the same pieces in different directions; a situation that starts to occur at depth 12 and up).
move              divide(26) ----------------------------
12-16:    111362678435231752
11-16:    112590257768420515
11-15:    101352649993886926
10-15:    100552646996749293
10-14:     86312674861234785
 9-14:    103811787278058952
 9-13:    136189763354484914 ----------------------------
perft(26) 752172458688067137

Perft for Checkers for Depth 25

Continuing my quest for deeper and deeper perft numbers for 8x8 checkers, I now computed depth 25 with the same distributed implementation I used earlier for depths up to 24. Below you see the perft breakdown per move (called "divide") from the initial position for depths 23, 24 and 25 (my depth 23 and 24 numbers were recently kindly confirmed by Murray Cash at the World Draughts Forum).
move          divide(23)        divide(24)          divide(25)
12-16:  1123463594881857  5192042148594780   24019313789608561
11-16:  1131373985922218  5248615918291379   24153215782987793
11-15:   984253557821317  4602138522979438   21659601983574539
10-15:  1000606302770349  4643700995955222   21609957136212495
10-14:   856779998157523  3988937724259353   18496978526984076
 9-14:  1003310451936358  4712325943133747   22101040287502927
 9-13:  1337748969176591  6263620622082081   29027372375205409

Further Localication

I just released version 4.0.5 of Chess for Android, available through Google Play or as direct download. This release mainly extends localization to more languages, but it also provides a new feature: copying the engine analysis to the clipboard. The following languages are now supported: Afrikaans (af)Chinese (zh)Czech (cs) Dutch (nl)English (en)French (fr)German (de)Hebrew (iw)Hindi (hi)        [coming soon]Icelandic (is)   [coming soon]Italian (it)Polish (pl)Portuguese (pt-br)Russian (ru)Spanish (es)Swedish (sv)Turkish (tr) Many thanks to my translation team: Vinícius Angiolucci, Lucas Braesch, A.N. Bürümcekci, Panna Chowdhury, Anton Hansson, Arnar Mar Hrafnkelsson, Michal Kaczmarek, Dara Koper, Morgan Lombard, Krizia Lopez, Dennis Prochko, Martin Sedlák, Philip Stutz, Haran Talmon, Ted Wong, and last but certainly not least C.R. Zamana!

Localization of Chess for Android

Version 4.0 of Chess for Android, available at either Google Play or as direct download, focuses on localization and internationalization. All user facing text (except the chess notation and engine messages) has been translated into the following languages. English (the default)Dutch (translated myself)German (many thanks to Philip Stutz)Hebrew (many thanks to Haran Talmon)Polish (many thanks to Michal Kaczmarek)Spanish (many thanks to Krizia Lopez)Swedish (many thanks to Anton Hansson) If you spot any mistakes, if you would like to see support for other languages or, even better, if you would like to help with further localization, please drop me a private note.

Scrolling utility for the micro-KIM

I had been working on some general utilities for the micro-KIM, and used some spare time during the long weekend to finish a scrolling putchar utility that can output letters and digits to the 7-segment display in a scrolling fashion (some letters needed more improvisation than others, but my daughter Karina helped me designing all the letters and converting them to hex). Here is a demo.

DeepBrutePos for Android

Folkert van Heusen is developing a chess engine, called DeepBrutePos, and he also wrote a version for Android. The engine is written in Java, and he used the Android SDK to develop a version that acts as a chess server, so that it can be imported as network socket in Chess for Android (a rather unusual, but nifty use of that feature).
I conducted a quick test with one of the first versions. Below the results of a one-second-per move tournament from both sides of all Nunn opening lines on a Nexus One. I was hoping for better results for Folkert, but hopefully he will release a strong version soon. Good luck!
                       1        2          3         4         5        6                   
1 BikJump v2.1P        *     17.5- 2.5 20.0- 0.0 20.0- 0.0 20.0-0.0 20.0-0.0 97.5/100
2 fairymax48q       2.5-17.5     *     10.0-10.0 12.5-7.5  18.5-1.5 20.0-0.0 63.5/100
3 umax48w           0.0-20.0 10.0-10.0     *     12.0- 8.0 20.0-0.0 20.0-0.0 62.0/100
4 Chess for Android 0.0-20.0  7.5…

Chess for Android v3.3

I just released version 3.3 of Chess for Android, available at Google Play or as direct download. The new features include: Ability to modify filenames of regular and tournament games.Information on network status during socket setup. In the older versions, regular games and tournament games were alway appended to, respectively, the files games.pgn and tour.pgn on SD card. The new feature allows users to change these defaults through a "Change pathnames" menu. The pathnames can even include subdirectories, provides these directories exist.

The second feature displays information on the network status during socket setup (mobile connection, Wifi, etc.). In the version without network permissions (the default on Google Play), a proper warning message is shown instead.

Monitoring Stations in the Bay Area

Below a more detailed view of all monitoring stations in the Bay Area that are part of the radiation network, where my station shows in slightly darker yellow. The station near LLNL usually shows a similar CPM rating, while the one in the South Bay usually shows a bit higher CPM. As long as my station is up, you can also view this real-time map.

Radiation Network

I purchased GeigerGraph for Networks from Mineralab, and joined the radiation network, which is a network of volunteers all over the world with radiation monitoring stations that report local CPM (counts per minute) ratings. In the graph below, you can see my station in the East Bay in slightly darker yellow.

I can highly recommend this software. The maps show active monitoring stations all over the world, and one can obtain more detailed information for each station. The software also generates graphs or spreadsheets of measured data, and allows specifying alert actions, such as sending an email, when CPM ratings exceed a certain maximum. The software can also post a real-time map on a server.

Geiger Counter Continued

I investigated the large variation observed in the graph of June 6. While babysitting the monitoring software, I noticed that occasionally the software would report bursts of over 200 CPM, even though the Geiger counter itself never measured such a spike. Two "faulty minutes" in one hour could easily explain the 400 clicks variation. Therefore, I first tried different serial/USB converters (settings were always as specified by the GC manufacturer), since low quality converters are notorious for messing up signals. But I noticed faulty burst even for expensive converters. Then I tried my only computer that still has a serial port. Now, no more faulty bursts occurred during several test runs.

After that, I redid the 24 hours experiment. The results are shown below. A much more stable graph, reporting around 700 CPH, or .1 μSv/hour, which translates into about .9 mSv/year.

I am glad I am now able to perform more reliable measurements. If anyone has suggestions on debugging the…

Geiger Counter

I got a Digital Geiger Counter for my birthday (yes, I know, geeky). As a starter use, I measured the background radiation in our house in the East Bay over the past 24 hours. The results appear in the graph below, plotting the "counts per hour" and correspondingμSv/hour over the past 24 hours. The worst-case measured .2 μSv/hour translates to about 1.8 mSv/year, which luckily seems a bit below the worldwide average background dose.

Solar Eclipse 2012

We made a road trip to Mount Shasta and back to view the solar eclipse 2012, Armed with a home-made pinhole camera made by two shoe boxes, we watched the eclipse in a safe way.

The Checker Maven

Bob Newell's The Checker Maven is a very interesting online publication on Checkers and Draughts. This week's issue features checkers applications for Android.

Bob looked at many checkers programs but concluded that the only two application that merit consideration are Checkers Tutor, by world class checker programmer Martin Fierz (author of CheckerBoard and the Cake computer engine), and .... Checkers for Android by yours truly! I am honored to receive this special mention by The Checker Maven.

You can find the summary article at the main page. A more elaborate overview, including interviews with Martin and myself and be found in the full article.

Many thanks to Bob for posting this article.

Checkers for Android

Revisiting checkers programming, I just released version 2.5 of Checkers for Android, both at the Google Play and as direct download. New features include:
simple animation of captured piecesadded a slight delay in single-move responseadded transposition table to enginemore time controls The new animation and delay will hopefully make it more clear what move was just played. The transposition table should improve the engine strength a bit.

UPDATE: version 2.5.1 improves the animation as shrinking pieces (some users thought the older fading pieces were "drag delay"!), adds more endgame knowledge, and shows kings more clearly.

Take Your Child to Work Day at Google

A fun "Take Your Child to Work Day" at Google.

Polyglot for Android

There was an interesting discussion on the TalkChess forum whether a chess GUI running on the Dalvik Virtual Machine could merely support a single protocol, and use an adapter, like Polyglot, to support other protocols. Even though Chess for Android already supports both UCI and XBoard/WinBoard, I was intrigued by the question, and decided to give it a try. First, I compiled the polyglot sources for ARM-based Android devices (I had to make a few source changes to make that work). Then I edited a polyglot.ini file pointing to my own UCI engine bikjump1.8 compiled for ARM:

And gave it a try directly from the command line:

$ ./polyglot_for_android
PolyGlot 1.4.67b by Fabien Letouzey.
st 1
1 -1 0 1 h4
1 +0 0 3 h3
1 +2 0 6 g3
1 +12 0 20 Nh3
1 +17 0 22 Nf3
2 +0 0 46 Nf3 Nf6
3 +17 0 148 Nf3 Nf6 Nc3
4 +0 1 772 Nf3 Nf6 Nc3 Nc6
5 +2 2 1691 Nf3 Nf6 Nc3 Nc6 g3
6 +0 5 3120 Nf3 Nf6 Nc3 Nc6 g…

Temporary Chess Server

As a follow-up on the previous posting and for users that want to experiment with a remote chess server without setting one up themselves, I have, very temporarily, set up a remote chess server with various engines at ports 2000 through 2005 on Simply type this hostname and one of the ports in Chess for Android and let me know if you were able to connect!