Posts

Showing posts with the label checkers

Checkers for Android: Endgames

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


Checkers for Android: Position Setup

Image
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"]

1...  *


Checkers for Android: Certabo Support

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

Chess for Android 10 Year Anniversary!

Image
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 full tour…

Checkers and Reversi for Android

Image
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).


Checkers for Android: Full Game Navigation

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

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.
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) = 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 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
----------------------------------------…

Checkers for Android

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



Perft for Checkers for Depth 24

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


Direct Downloads

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

BikMove v1.2

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 searchConfigurable transposition table and endgame database cacheImproved evaluation functionAvoid querying Fierz's database when *either* side can captureBelow 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 Checkers 1.14: W-L-D: 75- 64-14…

Improved Checkers Endgame

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


One Deeper Perft for Checkers

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

Perft for Checkers (yet again)

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

Checkers Move Coach

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

Perft for Checkers (again)

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
-----------------------------------------------------------------
3493881706141 161…

More Board Textures

Image
Now that I am enthusiastic about textures, I also added a board texture to the other games. For Reversi for Android this hopefully also addresses complaints that the board was "too green".


For Checkers for Android, I simply reused the coffee table texture, as shown below.