Aart's Blog

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

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

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

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

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

As can be seen in previous postings, the perft method is useful to verify the correctness of a move generator. The method traverses the game tree up to various, increasing depths to count all leaf nodes. The results are compared with pre-computed values to isolate bugs. Although the method originated in the chess programming community, the same debugging principle can be used for any board game with deterministic rules. So far, I have used perft to verify the move generation of Chess for Android and, thanks to Martin Fierz , also for Checkers for Android. I was unable to find pre-computed perft numbers for reversi, however. Therefore, here is what is probably the debut of perft for reversi from the initial position, hopefully useful data for aspirant reversi programmers (at depths 9 and up, "passing" moves start to occur; at depths 11 and up, higher leaf nodes in which neither player can move start to occur). DEPTH #LEAF NODES ======================== 1 ...

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 .

Martin Fierz kindly extended his engine Cake with a perft feature. Luckily the numbers reported by Cake match the numbers reported by Checkers for Android exactly. Below the numbers from the start position are shown, hopefully useful data for aspirant checkers programmers. DEPTH #LEAF NODES ======================= 1 7 2 49 3 302 4 1469 5 7361 6 36768 7 179740 8 845931 9 3963680 10 18391564 11 85242128 12 388623673

Besides switching to a home-brewed bitboard representation, other parts of BikJump underwent refactoring as well. Some modifications turned out to modify strength negatively. I already wrote about null moves below. Furthermore, because the new bitboard move generator generates legal captures much faster than all legal moves, the quiescence search originally had been modified to look at captures only. After including checks again in the first few nodes, some bad tactical errors were avoided. Similarly, late move reduction had become too optimistic, and needed some adjustment towards the scheme used by the older BikJump. The "perft" nodes-per-second performance (which everybody measures differently; I simply traverse the complete tree with the same move generator that is used in search, including some bookkeeping) is about 13000KNs on a 2.66GHz Core 2 Duo. The nodes-per-second of the actual search in the first Nunn position is now about 1070KNs (64-bit) and 790KNs (32-bit)...