Aart's Blog

Work has been a lot of fun, but very busy. As a result, I had not worked on my Android games (or other hobbies) for a very long time. This Thanksgiving break, therefore, I decided to take a few extra days off, and add some long overdue new support in my games. For Checkers for Android, I finalized the support to connect an electronic board (just as was already done in the chess app), in particular for Certabo. The Certabo boards , mainly intended for chess, ship with 34 identifying chips that can be attached to any piece set, typically a full chess set with two additional queens). However, due to the flexibility of the chips, these boards can also be used for other 8x8 games, such as American checkers (enabling a full checkers set with ten additional kings). Version 3.1 brings this support to Google Play . For Chess for Android, I added timer support for the DGT3000 chess clock . Up to recently, I only used the clock to prompt the most recently played move (with a beep to alert the pla

Now that Checkers for Android supports a position setup editor, analyzing textbook studies has become a lot simpler. This has increased the significance of the small built-in endgame tablebases of my app as well, as can be seen in the study below. Here, starting from what is known as the "first position" in checkers, Checkers for Android, playing with the black pieces, announces its inevitable loss in 30 moves!

I finished a position setup feature for Checkers for Android , similar to what was already in Chess for Android . This feature allows users to copy interesting checker problems from textbooks or other sources and play from there to improve their game. In addition, I added an option to show the square labels to make playing out variants from textbooks a bit easier for players that are less familiar with the numbering scheme. Since I recently also added a feature to export games as PDN, this implied I also had to implement FEN setup for games that do not start from the initial position. An example is shown below (note the FEN tag, and the empty first ply since it is white's move in the given position). [Event "Checkers for Android Game"] [Site "United States"] [Date "2019.01.19"] [White "Checkers for Android"] [Black "Self"] [Result "*"] [PlyCount "0"] [Setup "1"] [FEN "W:W9,K32:B13,K1&q

Although the Certabo electronic boards are mainly intended for chess, the flexibility of the identifying chips makes them suitable for 8x8 checkers as well (draughts, or American checkers, with slightly different rules from e.g. 10x10 international checkers). Therefore, I am planning to add support for Certabo boards in Checkers for Android as well. The 34 identifying chips can be used for the 24 regular pieces and 10 kings for promotion (using special purpose pieces avoids stacking the regular pieces). A 3D printed set can be used for this purpose (a continued hat-tip to my brother-in-law Gerard Harbers for making all the chess and checkers sets for me!). The general idea is illustrated with this picture. Please let me know if you like this upcoming support!

I can't believe it, but Chess for Android just passed its ten year anniversary! In November 2008, it appears for the first time on the -then-called- Android Market, together with Reversi for Android. Checkers for Android was soon to follow. The Android Market was later renamed Google Play . Working on this GUI has been a lot of fun, even though it took all spare time away from further developing my chess engine BikJump. But pioneering support for third party engines (at a time nobody was compiling for ARM), both UCI and XBoard, accessing endgame tablebases on SD card, adding PGN and setup features,simplifying engine setup through Chessbase compatible format and the Android Open Exchange format, using OCR apps to read chess positions, translating text to other languages, maintaining an online manual , and recently adding support for Certabo, DGT, and Millennium electronic chessboards has been just as rewarding. I have compiled many engines for Android back in the days, ran ful

New releases for both Checkers and Reversi for Android . Both games made some improvements in the notation display, most obvious the use of parenthesis for the alternating moves (suggested by Rein Halbersma), a better column layout, and improved "scrolling" while navigating. Also, both games now support exporting the game to the clipboard or via sharing with another program. For checkers, the PDN (portable draughts notation) is used, for reversi something similar to PGN (portable game notation). For checkers this also required "disambiguating" captures using an intermediate square (which should cover most normal games).

Folks that know me probably saw this coming, but Checkers for Android now also has a notation window and full game navigation, just like Chess for Android and, recently, Reversi for Android. All three games have the same look-and-feel again! Unlike the algebraic notation in chess or reversi, checkers uses a numbered notation, explained in detail in The Checker Maven  (note that, for simplicity of display, my checkers app always just shows the "from" and "to" square for each move or capture, even though technically intermediate squares are sometimes needed to disambiguate multiple jumps). At first glance the numbering may seem a bit confusing, but the notation becomes easier with practice.

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 perf

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. divide(28) 12-16 = 2400708339858199191 11-16 = 2431386196712611878 11-15 = 2231787529331259810 10-15 = 2186446356811761737 10-14 = 1872427919495823777  9-14 = 2285893686261887442  9-13 = 2969067990365356900  -------------------------- perft(28) =

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 recove

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

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 pieces added a slight delay in single-move response added transposition table to engine more 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.

I computed the perft number for 8x8 checkers for depth 24 with the same distributed implementation I used earlier for depths up to 23. Below you see the perft breakdown per move (called "divide") from the initial position for depths 22, 23, and 24. move         divide(22)       divide(23)        divide(24) ---------------------------------------------------------- 12-16:  243598269855110 1123463594881857  5192042148594780 11-16:  246743868125768 1131373985922218  5248615918291379 11-15:  209016678583301  984253557821317  4602138522979438 10-15:  215412869777867 1000606302770349  4643700995955222 10-14:  184865466345796  856779998157523  3988937724259353  9-14:  213736468971938 1003310451936358  4712325943133747  9-13:  288999100078322 1337748969176591  6263620622082081 ----------------------------------------------------------        1602372721738102 7437536860666213 34651381875296000

Because not all Android devices support the Android Market yet, I decided to made my Android applications available as direct downloads: Chess for Android Checkers for Android Reversi for Android After the download completes, simply click the apk to start the install (make sure to check "unknown sources" under settings=>applications).

Continuing the detour in checkers. I also released v1.2 of BikMove , a checkers engine plugin to Martin Fierz' CheckerBoard application. New features include: Added internal iterative deepening to search Configurable transposition table and endgame database cache Improved evaluation function Avoid querying Fierz's database when *either* side can capture Below are results of a 3-move openings match between BikMove v1.2 and other engines (1 second-per-move, 256MB hash, 256MB database cache, 2-8 piece endgames, best-move for engines that have their own book). BikMove v1.2 vs. Easy Checkers 1.0   : W-L-D: 284-  0-  4  99% BikMove v1.2 vs. Simple Checkers 1.14: W-L-D: 136- 21-131  70% BikMove v1.2 vs. GUI checkers 1.05+  : W-L-D:   9-108-171  33% BikMove v1.2 vs. Cake1.8 + huge book : W-L-D:   0-152-136  24% BikMove v1.2 vs. Kingsrow 1.16d      : W-L-D:   1-181-106  19% For comparison, also some results under similar conditions with v1.1. BikMove v1.1 vs. Simple Check

To improve endgame play, I have added a few "distance-to-win" endgame databases to Checkers for Android (K-K, p-K, p-p, KK-K). These databases are small enough to reside in memory and are queried during the engine search. In the screenshot below, for instance, the engine (playing black) announces that it will win in 20 moves. If you are up to the challenge, just download version 2.4 of Checkers for Android from the market.  

I optimized the distributed implementation for 8x8 checkers with a transposition table (but one that stores full board positions to avoid the risk of "hard collisions"). The speed improvement enabled me to compute perft(23) on a cluster of machines in a relatively short time. As before, the table below shows the perft breakdown per move (called "divide") from the start position, but now for depths 21 to 23. move divide(21) divide(22) divide(23) --------------------------------------------------------- 12-16: 52945190026737 243598269855110 1123463594881857 11-16: 53527954221225 246743868125768 1131373985922218 11-15: 44775005468548 209016678583301 984253557821317 10-15: 46574865098865 215412869777867 1000606302770349 10-14: 39822944739732 184865466345796 856779998157523 09-14: 45530585259776 213736468971938 1003310451936358 09-13: 61923979665936 288999100078322 1337748969176591 -------------------------------------------

Rein Halbersma recently posted 8x8 checkers perft results for depth 22 with a request for confirmation (because he uses a hash table, he wanted to make sure no "hard collisions" occur). So I verified his results for depth 22 using a distributed, brute force implementation (no hash tables). The table below shows the perft breakdown per move (called "divide") from the start position for depths 20 to 22. move divide(20) divide(21) divide(22) ------------------------------------------------------- 12-16: 11531470109861 52945190026737 243598269855110 11-16: 11736729175821 53527954221225 246743868125768 11-15: 9515983205474 44775005468548 209016678583301 10-15: 10055597639275 46574865098865 215412869777867 10-14: 8600202424158 39822944739732 184865466345796 9-14: 9698986164172 45530585259776 213736468971938 9-13: 13406062152792 61923979665936 288999100078322 ------------------------------------------------------- 7454503

I received an email from Rein Halbersma who suggested an improvement for Checkers for Android by accepting a move as soon as any ambiguity has been resolved. In many cases this enables single click input. I have implemented this request, together with extending the "move coach" to show all valid moves, as illustrated below. Hopefully this new option is useful for people that are learning checkers. Both improvements are available in v2.3 of Checkers for Android.

Today I was prototyping a distributed worker pool at work which needed some test input, and this gave me a good excuse to compute perft for checkers for depth 21 (one deeper than results I posted a while back). The perft breakdown per move (called "divide") from the start position for depths 18 up to 21 is shown below. move divide(18) divide(19) divide(20) divide(21) ----------------------------------------------------------------- 12-16: 550829166472 2517202147314 11531470109861 52945190026737 11-16: 566149929068 2564849953998 11736729175821 53527954221225 11-15: 435063007630 2041959240377 9515983205474 44775005468548 10-15: 472279451484 2180656975018 10055597639275 46574865098865 10-14: 402570639569 1859042884028 8600202424158 39822944739732 9-14: 441590753001 2068865301476 9698986164172 45530585259776 9-13: 625398758917 2881467090588 13406062152792 61923979665936 ----------------------------------------------------------------- 349388