Aart Bik's Computer Checkers Page

Through computer chess, Aart Bik became interested in computer checkers. More information related to checkers can be found in The Checker Maven and at the World Draughts Forum. For more resources and a proof that checkers has been solved see the Chinook project.

Checkers for Android

[Icon] Checkers for Android is a checkers application for the Android platform that consists of a 8x8 checkers engine (a Java version that evolved into the C++ engine BikMove described below) together with a GUI.

Checkers Engine BikMove

Aart also implemented an 8x8 checkers engine called BikMove that can be plugged into Martin Fierz' excellent CheckerBoard application. To install BikMove v1.3, download the following zip file, unzip it in the checkboard engines directory, and then import the engine through the Engine=>Select menu. All C++ source code of BikMove has been written by Aart (except the endgame databases probing code, which is used with kind permission of Martin Fierz).
        
3-move engine matches:
BikMove v1.3 vs. Easy Checkers 1.0   : W-L-D: 287-  0-  1  99.8%
BikMove v1.3 vs. SimpleCheckers 1.14 : W-L-D: 153-  7-128  75.3%
BikMove v1.3 vs. GUI checkers 1.05+  : W-L-D:   5- 98-185  33.9%
BikMove v1.3 vs. Cake1.8 + huge book : W-L-D:   1-132-155  27.2%
A 10x10 checkers engine called BikDam is in the making.

Perft for Checkers

Aart published a paper "Computing Deep Perft and Divide Numbers for Checkers" in the International Computer Games Association Journal, December, 2012 (see http://www.icga.org/).

The perft method originated in the chess programming community as a way to verify the move generator of an engine. The method traverses the game tree up to various, increasing depths to count all leaf nodes at each given depth. These results are compared with pre-computed values to isolate bugs and timings can be used to analyze the performance of the move generator. The perft method can be applied to other game engines as well, such as perft for reversi or, as done on here, perft for checkers. Below, checkers perft numbers from the start position are given using the move generator of BikMove on a 2.2 GHz Core 2 Duo, optimized for speed with bulk counting. Please note that the move generator does not eliminate duplicate captures (viz. the situation where a king can capture the same pieces in different directions; a situation that starts to occur at depth 12 and up).

perft(0)  =                    1  in        0 ms.
perft(1)  =                    7  in        0 ms.
perft(2)  =                   49  in        0 ms.
perft(3)  =                  302  in        0 ms.
perft(4)  =                 1469  in        0 ms.
perft(5)  =                 7361  in        0 ms.
perft(6)  =                36768  in        1 ms.  36,768.0 KN/s
perft(7)  =               179740  in        5 ms.  35,948.0 KN/s
perft(8)  =               845931  in       23 ms.  36,779.6 KN/s
perft(9)  =              3963680  in       86 ms.  46,089.3 KN/s
perft(10) =             18391564  in      398 ms.  46,210.0 KN/s
perft(11) =             85242128  in     1821 ms.  46,810.6 KN/s
perft(12) =            388623673  in     8395 ms.  46,292.3 KN/s
perft(13) =           1766623630  in    37182 ms.  47,512.9 KN/s
perft(14) =           7978439499  in   174947 ms.  45,604.9 KN/s
perft(15) =          36263167175  in   808155 ms.  44,871.5 KN/s
perft(16) =         165629569428  in  3767118 ms.  43,967.2 KN/s
perft(17) =         758818810990  in 17317695 ms.  43,817.5 KN/s
perft(18) =        3493881706141  |
perft(19) =       16114043592799  |
perft(20) =       74545030871553  |
perft(21) =      345100524480819  |
perft(22) =     1602372721738102   \ distributed run
perft(23) =     7437536860666213   / (see below)
perft(24) =    34651381875296000  |
perft(25) =   161067479882075800  |
perft(26) =   752172458688067137  |
perft(27) =  3499844183628002605  |
perft(28) = 16377718018836900735  |
Aart implemented a distributed version to compute perft(18) through perft(28) on a cluster of machines (further optimized with a "hard collision"-free transposition table as well as bulk counting). The perft breakdown per move for these depths, an important debugging feature often referred to as "divide", is shown below.
move      divide(18)     divide(19)     divide(20)      divide(21)       divide(22)       divide(23)        divide(24)          divide(25)         divide(26)            divide(27)           divide(28)
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12-16:  550829166472  2517202147314 11531470109861  52945190026737  243598269855110 1123463594881857  5192042148594780   24019313789608561  111362678435231752   516399283859880203   2400708339858199191
11-16:  566149929068  2564849953998 11736729175821  53527954221225  246743868125768 1131373985922218  5248615918291379   24153215782987793  112590257768420515   519502096014967805   2431386196712611878
11-15:  435063007630  2041959240377  9515983205474  44775005468548  209016678583301  984253557821317  4602138522979438   21659601983574539  101352649993886926   476666239516455180   2231787529331259810
10-15:  472279451484  2180656975018 10055597639275  46574865098865  215412869777867 1000606302770349  4643700995955222   21609957136212495  100552646996749293   468705060101275533   2186446356811761737
10-14:  402570639569  1859042884028  8600202424158  39822944739732  184865466345796  856779998157523  3988937724259353   18496978526984076   86312674861234785   400425747281243848   1872427919495823777
 9-14:  441590753001  2068865301476  9698986164172  45530585259776  213736468971938 1003310451936358  4712325943133747   22101040287502927  103811787278058952   486493422418651579   2285893686261887442
 9-13:  625398758917  2881467090588 13406062152792  61923979665936  288999100078322 1337748969176591  6263620622082081   29027372375205409  136189763354484914   631652334435528457   2969067990365356900
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
       3493881706141 16114043592799 74545030871553 345100524480819 1602372721738102 7437536860666213 34651381875296000  161067479882075800  752172458688067137  3499844183628002605  16377718018836900735
To the best of Aart's knowledge, this is the first project that has computed deep perft numbers for checkers. Thanks to Martin Fierz, Ed Gilbert, Jonathan Schaeffer, and Ed Trice for verifying various early perft numbers when this project started. A special thanks to Rein Halbersma (first to report perft(22)), Murray Cash (verified perft(23) and perft(24)), and Paul Byrne (verified perft(24) through perft(28)).
Please note that this page is privately maintained by Aart Bik. Google+ LinkedIn