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
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.
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
Unknown said…
I Love all your apps and as a fellow Dutchman I'm looking forward to your version of a draughts/dammen app.
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.
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....
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.
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.
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.

Popular posts from this blog

Connecting Chess for Android to a Remote Server

Checkers Move Generation

Connecting with the DGT Board