Home | CV | Publications | PhD | PostDoc | SIMD |
Android | Glass | Astronomy | Retro | Games | Lego |
As an enthusiastic young chess player, Aart Bik was thrilled to get the Fidelity Electronics Sensory Chess Challenger 8 as a birthday present from his parents in 1981. After a while, Aart found that if the Chess Challenger responded to e2-e4 with e7-e5 from its random opening book, it could always be beaten at Level 1 through the game shown below.
Since those early days, Aart has been fascinated by programming a computer to play chess, which eventually resulted in the development of the game playing engines shown on this page. Excellent online resources related to this topic can be found, for example, at Adam's Computer Chess Pages, Certabo Forum, Checker Maven, Chess Computer Museum, Chess Computers, Chess Programming Wiki, Chesstroid, Chess2U, ChessWar, Chinook project, Computer Chess Testing, Countrychess, CSVN, Ed Schröder's website, Forum ComputerSchach, Hiarcs Chess Forums, ICGA, Komodo Chess Engine, Leela Chess Zero, MZ Chess Forum, Open Chess Forum, PicoChess, VanHeusden, TalkChess Forum, SchachComputer, SchachComputer Forum, SchachComputer Online Museum, WBEC Ridderkerk, World Draughts Forum, Winboard Forum.
[Date "sometimes in 1981"] [White "a much younger Aart Bik"] [Black "Chess Challenger 8 (Level 1)"] [Result "1-0"] 1. e4 e5 2. Nf3 Nc6 3. Bb5 a6 4. Bxc6 dxc6 5. Nxe5 Qd4 6. Qh5 Qxe4+ 7. Kd1 Qxg2 8. Qxf7+ Kd8 9. Qxf8# 1-0
Aart occasionally works on his UCI chess engine, called BikJump. All source code of BikJump (except the probing and decompression code for the endgame tablebases, which are used with kind permission of Eugene Nalimov and Andrew Kadatch) has been built from the ground up by Aart as a fun after-hours project to gain experience with chess programming and experiment with new ideas. Aart is a chess hobbyist who enjoys writing his own, original code. He obviously used ideas found in chess-related books, papers, and web postings, but sees no fun in copying-and-pasting code and claiming it as his own.
The first generation of BikJump (v1.x), released in January 2007, was based on a mailbox representation, and increased in strength from about 1750 to 2000 RUEL. The second and current generation (v2.x), released in November 2008, is based on a bitboard representation. Aart now has started work on "Deep" BikJump, featuring multi-threading to perform the search in parallel (SMP support).
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):
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 shown further down this page. 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)).
Pseudo-code for a reversi perft method is given below. Note that at the point marked with (*), neither player can move and the game is over. The implementation shown here includes such a higher leaf node in the perf count as well (in fact, a naive implementation that ignores game over situations would obtain the same count, as the players simply keep passing until a full-depth leaf node is reached). Alternatively, the code could return 0 to exclude higher leaf nodes in which the game is over, which would be closer the chess perft method, where higher leaf nodes are discarded (i.e. effectively only counting the number of move paths that reach the given depth).
int64 perft(int depth, boolean passed) { if (depth == 0) { return 1; // at leaf node } int64 nodes = 0; generateMoves(); if (num_moves == 0) { if (passed) { // both sides passed (game over) return 1; // (*) see comment above } do_pass(); nodes += perft(depth-1, true); undo_pass(); } else { for (int i = 0; i < num_moves; i++) { do_move(i); nodes += perft(depth-1, false); undo_move(i); } } return nodes; }
Below, some perft numbers for 8x8 reversi from the start position are given. 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. The table also shows the split of leaf nodes that reach full-depth or occur higher in the game tree. Thanks to Jonathan Kreuzer (author of the excellent Pointy Stone application) for verifying my perft numbers.
DEPTH #LEAF NODES #FULL-DEPTH #HIGHER ========================================== 1 4 2 12 3 56 4 244 5 1396 6 8200 7 55092 8 390216 9 3005288 10 24571284 11 212258800 = 212258572 + 228 12 1939886636 = 1939886052 + 584 13 18429641748 = 18429634780 + 6968 14 184042084512 = 184042061172 + 23340
A Sudoku puzzle consists of placing the numbers 1 through 9 into the cells of a 9x9 grid divided into nine 3x3 regions, where some cells already contain numbers (called the "givens" or "clues"), such that eventually every row, every column and every region contains each of the numbers 1 through 9 exactly once. Aart wrote a simple Sudoku solver in C that will find all solutions for any given initial placement of numbers on the grid or report that no solution is possible (even though a pure Sudoku puzzle should always have exactly one solution). In the standard mode, the solver simply reports solutions, while in the verbose mode, the solver also explains which steps are taken. Sample output is shown below.
To reduce state space search, the solver always proceeds with a cell that has a minimum set of candidates. After some hand-optimization, the solver can search the state space up to over 20 million nodes-per-second on a 3.4GHz Pentium 4 processor. Due to the simplicity of state space pruning, the solver typically considers many more nodes than more 'intelligent' solvers with lower nodes-per-second rating, which can easily nullify all gains obtained by the fast search. Fast search still seems to have some potential in filtering out multi-solution puzzles, where it is not as clear yet which kind of solver performs better. In the verbose mode, the solver explains each step with a must-be, when there is a unique candidate, or a try, when only non-singleton sets of candidates appear (under the simple pruning rules used by this solver) and, hence, backtracking is required. A dead-end indicates the end of a trial for which no further solutions are possible. The notation x,y = z is used as a shorthand for placing the number z on the cell at row x and column y (with 1,1 top-left and 9,9 bottom-right).
PROBLEM: +---+---+---+ |...|4..|5..| |...|27.|.8.| |..6|..8|..4| +---+---+---+ |3..|6..|4..| |.4.|.5.|.7.| |..2|..9|..6| +---+---+---+ |2..|9..|7..| |.8.|.3.|.5.| |154|762|..8| +---+---+---+ must-be 7,3 = 3 must-be 7,2 = 6 must-be 7,9 = 1 must-be 7,8 = 4 must-be 7,5 = 8 must-be 7,6 = 5 must-be 8,4 = 1 must-be 8,6 = 4 try 1,5 = 1 from {19}:#2 must-be 3,5 = 9 must-be 4,5 = 2 must-be 6,5 = 4 try 8,9 = 2 from {29}:#2 try 9,8 = 3 from {39}:#2 must-be 9,7 = 9 must-be 6,8 = 1 must-be 8,7 = 6 must-be 3,8 = 2 must-be 4,8 = 9 must-be 1,8 = 6 must-be 1,6 = 3 must-be 5,9 = 3 must-be 6,7 = 8 must-be 5,6 = 1 must-be 5,4 = 8 must-be 5,3 = 9 must-be 5,1 = 6 must-be 4,9 = 5 must-be 6,2 = 7 must-be 4,6 = 7 must-be 8,3 = 7 must-be 1,3 = 8 must-be 4,2 = 1 must-be 6,4 = 3 dead-end 4,3 = ? try 9,8 = 9 from {39}:#2 must-be 4,8 = 1 must-be 4,6 = 7 must-be 4,2 = 9 must-be 8,7 = 6 must-be 6,8 = 3 must-be 6,4 = 8 must-be 3,8 = 2 must-be 1,8 = 6 must-be 5,9 = 9 must-be 2,9 = 3 must-be 3,7 = 1 must-be 5,4 = 3 must-be 1,9 = 7 must-be 2,2 = 1 must-be 4,9 = 5 must-be 4,3 = 8 must-be 5,3 = 1 must-be 9,7 = 3 must-be 1,3 = 9 must-be 1,1 = 8 dead-end 6,7 = ? try 8,9 = 9 from {29}:#2 must-be 8,3 = 7 must-be 9,8 = 3 dead-end 8,1 = ? try 1,5 = 9 from {19}:#2 must-be 3,5 = 1 must-be 6,5 = 4 must-be 4,5 = 2 try 4,8 = 1 from {19}:#2 must-be 6,8 = 3 must-be 6,7 = 8 must-be 9,8 = 9 must-be 4,6 = 7 must-be 4,2 = 9 must-be 8,9 = 2 must-be 8,7 = 6 dead-end 6,4 = ? try 4,8 = 9 from {19}:#2 must-be 4,9 = 5 must-be 9,8 = 3 must-be 9,7 = 9 must-be 6,8 = 1 must-be 6,2 = 7 must-be 4,2 = 1 must-be 8,9 = 2 must-be 8,7 = 6 must-be 3,8 = 2 must-be 1,8 = 6 must-be 1,6 = 3 must-be 1,2 = 2 must-be 3,7 = 3 must-be 2,9 = 9 must-be 1,9 = 7 must-be 2,2 = 3 must-be 4,6 = 7 must-be 4,3 = 8 must-be 5,3 = 9 must-be 8,3 = 7 must-be 1,3 = 1 must-be 1,1 = 8 must-be 8,1 = 9 must-be 3,4 = 5 must-be 3,2 = 9 must-be 3,1 = 7 must-be 5,6 = 1 must-be 2,7 = 1 must-be 2,6 = 6 must-be 2,3 = 5 must-be 5,9 = 3 must-be 5,4 = 8 must-be 6,4 = 3 must-be 6,1 = 5 must-be 5,7 = 2 must-be 6,7 = 8 must-be 2,1 = 4 must-be 5,1 = 6 SOLUTION: +---+---+---+ |821|493|567| |435|276|189| |796|518|324| +---+---+---+ |318|627|495| |649|851|273| |572|349|816| +---+---+---+ |263|985|741| |987|134|652| |154|762|938| +---+---+---+ #PUZZLES=1 #SOLUTIONS=1