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) = 1665861398 in 17090 ms. 97475.8 KN/s

Comments

Unknown said…
hey aart,
could u please add some in regard to on what system these perfts where tested (CPU, RAM, etc.).
Otherwise the timings wont realy help as a reference.
thnx
December 13, 2012 at 3:46 AM
Aart Bik said…
Of course. I had just started development of my 10x10 checkers program, so I was more focused on correctness of the numbers than speed. Nevertheless, this was tested on an Intel Xeon X5650 2.67GHz, no hash table. I now also have new numbers with bulk-counting, and a hard-collision free hash table, similar to what I used for the deep perft numbers project for 8x8 checkers.
December 13, 2012 at 9:15 AM
Unknown said…
Int. Checkers is indeed nice .. I am thinking on maybe writing an engine too .. So might need some reference values :)) .. Thnx 4 the answer
December 13, 2012 at 10:45 AM
Unknown said…
I Love all your apps and as a fellow Dutchman I'm looking forward to your version of a draughts/dammen app.
March 20, 2013 at 5:14 PM
Marc said…
Are these perft numbers generated with only longest capture sequence?

I also started a similar project, but it seems my program generates less leaf nodes. Or more, if a also count shorter capture possibilities. But i don't remove duplicate moves.
May 4, 2013 at 2:48 PM
Aart Bik said…
Unlike my perft numbers for 8x8 checkers (see this checkers website), for international checkers my perft method counts all legal captures, thereby removing duplicates. Can you say at what point our numbers differ, with a simple divide() session we could narrow it down to the difference....
May 4, 2013 at 3:05 PM
Anonymous said…
At depth 4 I only have about 3960 leaf nodes. But did you remove captures which would not be allowed under the 'meerslag' rule? If i dont remove these our numbers match up to depth 4, but then @ depth 5 my leaf count becomes bigger.
May 4, 2013 at 3:22 PM
Aart Bik said…
Well, note that there are two kinds of capture removals for international checkers. Captures that are not legal due to the "meerslag" rule are of course *always* eliminated. Additionally, move generators have the choice to eliminate captures that eventually have exactly the same result but are taken in "different directions". I eliminate those too, and most other engines do the same, because for international checkers, the number of legal moves otherwise goes quickly out of control.
May 4, 2013 at 4:36 PM
Marc said…
Thanks for clarifying that. It seems that the duplicate move reduction kicks in from depth 5? My perft 4 was off by exactly the same number of moves as the moves deleted by the part that checks for the longest capture. So that initially got me thinking the bug was in that part of my code that tried to enforce the meerslag rule.
May 6, 2013 at 2:22 PM
Post a Comment

Popular posts from this blog

Checkers Move Generation

-
I was able to make a small improvement in the checkers move generator (written in Java for the Android SDK). The following table shows run times of several perft depths before and after optimization when run on the emulator (which should mimic actual run times on the phone quite well). DEPTH #LEAF NODES ORIGINAL OPTIMIZED TIME TIME ==================================== 7 179740 2.9s 1.9s 8 845931 14.2s 9.7s 9 3963680 66.3s 45.6s 10 18391564 294.6s 208.7s P.S. Runtimes for a C++ checkers move generator on a 2.2 GHz Core 2 Duo are given at my checkers page .
Read more

Connecting Chess for Android to a Remote Server

-
Image
I have received several questions on how to connect Chess for Android running on an Android device (e.g. a phone) as client to a remote chess server (e.g. a powerful desktop), so I decided to write a small document with detailed instructions. What you will need: The server software from Bernhard Wallner's chess utilities , suited for your server's operating system (if, say, your desktop runs Windows, you will need to download the Windows version). You do not need to download the client software in this case. The network enabled version of Chess for Android . On the server, start the engine server software, and construct a new row for every engine you want to run remotely. Assign a name, port number, and select the full path to each engine binary (an executable that runs on the server). You can also supply command line options for starting the engine. Check the active checkboxes and click start when done. This yields something similar to the screenshots below. Here, I have s...
Read more

Connecting with the DGT Board

-
Image
After all the fun I had connecting Chess for Android with the Millennium  over Bluetooth, I was curious if I could provide similar support for the DGT electronic chess boards. Some of these have Bluetooth capabilities, most use USB connections, and some older models, like the one I have, still use the RS-232 connector. To my pleasant surprise, by combining the original serial cable of DGT with a USB-to-serial cable and a female-USB-to-USB-C cable, I was able to get an actually working connection between my DGT board and my tablet or phone. Next was implementing support in Chess for Android. Luckily, DGT kindly shared the protocol documentation with me, and after a fun weekend of hacking, Chess for Android now proudly supports DGT electronic chess boards as well.
Read more