Perft for all recognized draughts variants

[Rein Halbersma]

I have almost completed my universal draughts engine that can play on arbitrary board sizes (for which a double ghost square representation fits within 64-bits integers) and that also is aware of the game rules of all recognized draughts variants. In this thread, I will post the perft results for the initial position for these games. I also have collected links to the official rule documents. In those cases where the language is unfamiliar, Google Translate is your best friend to read them.

Technical note: all numbers below do not remove captures that only differ in the order in which pieces are captured (clockwise or counter-clockwise e.g.).

[Rein Halbersma]

Below the perft results for Brazilian checkers (international draughts on an 8x8 board). These results were first derived on the Russian Shashki forum: http://shashki.com/PNphpBB2-viewtopic-t ... rt-78.html

Code: Select all

  b   b   b   b
b   b   b   b
  b   b   b   b
.   .   .   .
  .   .   .   .
w   w   w   w
  w   w   w   w
w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching starting position to nominal depth=13

perft( 1)            7 nodes,   0.00s,   0.01 Mnps
perft( 2)           49 nodes,   0.00s,   0.05 Mnps
perft( 3)          302 nodes,   0.00s,   0.30 Mnps
perft( 4)         1469 nodes,   0.00s,   1.47 Mnps
perft( 5)         7473 nodes,   0.00s,   7.47 Mnps
perft( 6)        37628 nodes,   0.00s,  37.63 Mnps
perft( 7)       187302 nodes,   0.02s,  11.02 Mnps
perft( 8)       907836 nodes,   0.05s,  18.91 Mnps
perft( 9)      4431847 nodes,   0.25s,  17.66 Mnps
perft(10)     21566606 nodes,   1.11s,  19.43 Mnps
perft(11)    105534946 nodes,   5.55s,  19.02 Mnps
perft(12)    512171742 nodes,  27.34s,  18.73 Mnps
perft(13)   2483592238 nodes, 130.49s,  19.03 Mnps

[Rein Halbersma]

Below the results for Pool checkers (Brazilian checkers without the majority capture rule).
The official rules are given at http://americanpoolcheckers.us/american ... &Itemid=56
Again, these results were first given on the Shashki forum: http://shashki.com/PNphpBB2-viewtopic-t ... rt-57.html

Code: Select all

  b   b   b   b
b   b   b   b
  b   b   b   b
.   .   .   .
  .   .   .   .
w   w   w   w
  w   w   w   w
w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching starting position to nominal depth=13

perft( 1)            7 nodes,   0.00s,   0.01 Mnps
perft( 2)           49 nodes,   0.00s,   0.05 Mnps
perft( 3)          302 nodes,   0.00s,   0.30 Mnps
perft( 4)         1469 nodes,   0.00s,   1.47 Mnps
perft( 5)         7482 nodes,   0.00s,   7.48 Mnps
perft( 6)        37986 nodes,   0.00s,  37.99 Mnps
perft( 7)       190146 nodes,   0.02s,  11.19 Mnps
perft( 8)       929902 nodes,   0.05s,  19.79 Mnps
perft( 9)      4570615 nodes,   0.24s,  19.37 Mnps
perft(10)     22442551 nodes,   1.19s,  18.89 Mnps
perft(11)    110877932 nodes,   5.70s,  19.44 Mnps
perft(12)    544300084 nodes,  28.02s,  19.43 Mnps
perft(13)   2670481140 nodes, 141.67s,  18.85 Mnps

[Rein Halbersma]

Below the results for Russian checkers (Pool checkers with promotion en-passant, i.e. when crossing the promotion rule during a capture, without having to end there).
The official rules can be found at http://www.shashist.ru/kodeks/kodeks2004.doc
The Shashki forum again was the first: http://shashki.com/PNphpBB2-viewtopic-t ... t-126.html

Code: Select all

  b   b   b   b
b   b   b   b
  b   b   b   b
.   .   .   .
  .   .   .   .
w   w   w   w
  w   w   w   w
w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching starting position to nominal depth=13

perft( 1)            7 nodes,   0.00s,   0.01 Mnps
perft( 2)           49 nodes,   0.00s,   0.05 Mnps
perft( 3)          302 nodes,   0.00s,   0.30 Mnps
perft( 4)         1469 nodes,   0.00s,   1.47 Mnps
perft( 5)         7482 nodes,   0.00s,   7.48 Mnps
perft( 6)        37986 nodes,   0.00s,  37.99 Mnps
perft( 7)       190146 nodes,   0.00s, 190.15 Mnps
perft( 8)       929905 nodes,   0.05s,  19.37 Mnps
perft( 9)      4570667 nodes,   0.25s,  18.21 Mnps
perft(10)     22450628 nodes,   1.13s,  19.94 Mnps
perft(11)    110961169 nodes,   5.97s,  18.59 Mnps
perft(12)    545059387 nodes,  28.16s,  19.36 Mnps
perft(13)   2675994747 nodes, 137.05s,  19.53 Mnps

[Rein Halbersma]

The perft results for English/American checkers (man can't capture backwards, short king, no majority capture) are given below.
The official rules are available on http://www.usacheckers.com/rulesofcheckers.php
The corresponding Shashki link: http://shashki.com/PNphpBB2-viewtopic-t ... t-126.html

Code: Select all

  b   b   b   b
b   b   b   b
  b   b   b   b
.   .   .   .
  .   .   .   .
w   w   w   w
  w   w   w   w
w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching starting position to nominal depth=13

perft( 1)            7 nodes,   0.00s,   0.01 Mnps
perft( 2)           49 nodes,   0.00s,   0.05 Mnps
perft( 3)          302 nodes,   0.00s,   0.30 Mnps
perft( 4)         1469 nodes,   0.00s,   1.47 Mnps
perft( 5)         7361 nodes,   0.00s,   7.36 Mnps
perft( 6)        36768 nodes,   0.00s,  36.77 Mnps
perft( 7)       179740 nodes,   0.02s,  10.57 Mnps
perft( 8)       845931 nodes,   0.05s,  17.62 Mnps
perft( 9)      3963680 nodes,   0.19s,  21.08 Mnps
perft(10)     18391564 nodes,   0.88s,  20.99 Mnps
perft(11)     85242128 nodes,   4.20s,  20.28 Mnps
perft(12)    388623673 nodes,  19.06s,  20.39 Mnps
perft(13)   1766623630 nodes,  87.17s,  20.27 Mnps

[Rein Halbersma]

Below the perft results for the Czech game (English checkers with a long king and captures with a king take precedence over captures with a man)
The official rules can be found at http://www.damweb.cz/pravidla/cdfull.html
These results have not been computed before.

Code: Select all

  b   b   b   b
b   b   b   b
  b   b   b   b
.   .   .   .
  .   .   .   .
w   w   w   w
  w   w   w   w
w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching starting position to nominal depth=13

perft( 1)            7 nodes,   0.00s,   0.01 Mnps
perft( 2)           49 nodes,   0.00s,   0.05 Mnps
perft( 3)          302 nodes,   0.00s,   0.30 Mnps
perft( 4)         1469 nodes,   0.00s,   1.47 Mnps
perft( 5)         7361 nodes,   0.00s,   7.36 Mnps
perft( 6)        36768 nodes,   0.02s,   2.30 Mnps
perft( 7)       179740 nodes,   0.00s, 179.74 Mnps
perft( 8)       845931 nodes,   0.05s,  17.62 Mnps
perft( 9)      3963671 nodes,   0.19s,  20.97 Mnps
perft(10)     18368918 nodes,   0.88s,  20.97 Mnps
perft(11)     84967210 nodes,   4.16s,  20.44 Mnps
perft(12)    386267783 nodes,  19.11s,  20.21 Mnps
perft(13)   1749766090 nodes,  87.61s,  19.97 Mnps

[Rein Halbersma]

Below the perft results for Spanish checkers (Brazilian checkers where man cannot capture backwards and in case of an equal number of captured pieces, captures with the most captured kings take precedence).
The official rules can be found at http://fpdamas.home.sapo.pt/regrasclass.htm
I am not aware of any prior computations.

Code: Select all

b   b   b   b
  b   b   b   b
b   b   b   b
  .   .   .   .
.   .   .   .
  w   w   w   w
w   w   w   w
  w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching starting position to nominal depth=13

perft( 1)            7 nodes,   0.00s,   0.01 Mnps
perft( 2)           49 nodes,   0.00s,   0.05 Mnps
perft( 3)          302 nodes,   0.00s,   0.30 Mnps
perft( 4)         1469 nodes,   0.00s,   1.47 Mnps
perft( 5)         7361 nodes,   0.00s,   7.36 Mnps
perft( 6)        36473 nodes,   0.00s,  36.47 Mnps
perft( 7)       177532 nodes,   0.02s,  10.44 Mnps
perft( 8)       828783 nodes,   0.03s,  25.90 Mnps
perft( 9)      3860866 nodes,   0.19s,  20.43 Mnps
perft(10)     17743464 nodes,   0.83s,  21.40 Mnps
perft(11)     81383200 nodes,   3.96s,  20.58 Mnps
perft(12)    365734003 nodes,  18.11s,  20.20 Mnps
perft(13)   1638016958 nodes,  82.61s,  19.83 Mnps

[Rein Halbersma]

Below the perft numbers for Italian checkers (Spanish checkers with a short king, men cannot capture kings and a complicated 4-tiered majority capture rules).
Official rules available at http://www.fid.it/regolamenti/2008/RegTec_CAPO_I.pdf
These scores were computed before by Ed Gilbert using his Kingsrow Italian engine and our results agree perfectly.

Code: Select all

b   b   b   b
  b   b   b   b
b   b   b   b
  .   .   .   .
.   .   .   .
  w   w   w   w
w   w   w   w
  w   w   w   w

W:B1,2,3,4,5,6,7,8,9,10,11,12:W21,22,23,24,25,26,27,28,29,30,31,32"

Searching starting position to nominal depth=13

perft( 1)            7 nodes,   0.00s,   0.01 Mnps
perft( 2)           49 nodes,   0.00s,   0.05 Mnps
perft( 3)          302 nodes,   0.00s,   0.30 Mnps
perft( 4)         1469 nodes,   0.00s,   1.47 Mnps
perft( 5)         7361 nodes,   0.00s,   7.36 Mnps
perft( 6)        36473 nodes,   0.00s,  36.47 Mnps
perft( 7)       177532 nodes,   0.02s,  11.10 Mnps
perft( 8)       828783 nodes,   0.03s,  25.11 Mnps
perft( 9)      3860875 nodes,   0.19s,  20.54 Mnps
perft(10)     17761384 nodes,   0.89s,  19.93 Mnps
perft(11)     81647058 nodes,   4.16s,  19.64 Mnps
perft(12)    367917147 nodes,  19.58s,  18.79 Mnps
perft(13)   1655269811 nodes,  86.13s,  19.22 Mnps

[Rein Halbersma]

Just because Italian draughts is so complicated, here are two more positions that were first computed by Ed Gilbert.
Also note that both Spanish and Italian draughts use a board that is mirrored: the bottom-right square is dark, rather than the usual bottom-left.

Code: Select all

b   .   b   .
  b   b   .   .
b   .   b   .
  .   b   b   b
w   w   .   w
  .   w   w   w
.   w   w   .
  .   w   .   .

W:B1,3,5,6,9,11,14,15,16:W17,18,20,22,23,24,26,27,30"

Searching starting position to nominal depth=16

perft( 1)            5 nodes,   0.00s,   0.01 Mnps
perft( 2)           13 nodes,   0.00s,   0.01 Mnps
perft( 3)           42 nodes,   0.00s,   0.04 Mnps
perft( 4)          107 nodes,   0.00s,   0.11 Mnps
perft( 5)          360 nodes,   0.00s,   0.36 Mnps
perft( 6)         1099 nodes,   0.00s,   1.10 Mnps
perft( 7)         3736 nodes,   0.00s,   3.74 Mnps
perft( 8)        12495 nodes,   0.00s,  12.49 Mnps
perft( 9)        43686 nodes,   0.00s,  43.69 Mnps
perft(10)       164177 nodes,   0.02s,  10.26 Mnps
perft(11)       628686 nodes,   0.05s,  13.10 Mnps
perft(12)      2643623 nodes,   0.20s,  12.96 Mnps
perft(13)     10833722 nodes,   0.75s,  14.43 Mnps
perft(14)     49327264 nodes,   3.41s,  14.48 Mnps
perft(15)    212130912 nodes,  14.03s,  15.12 Mnps
perft(16)   1021757399 nodes,  68.66s,  14.88 Mnps

b   .   b   .
  b   W   .   .
b   .   .   .
  .   .   .   .
w   .   .   w
  w   w   .   .
b   .   .   b
  .   w   .   .

B:B1,3,5,9,25,28:WK6,17,20,21,22,30"

Searching starting position to nominal depth=12

perft( 1)            6 nodes,   0.00s,   0.01 Mnps
perft( 2)           47 nodes,   0.00s,   0.05 Mnps
perft( 3)          271 nodes,   0.00s,   0.27 Mnps
perft( 4)         1916 nodes,   0.00s,   1.92 Mnps
perft( 5)        10810 nodes,   0.00s,  10.81 Mnps
perft( 6)        73137 nodes,   0.00s,  73.14 Mnps
perft( 7)       389809 nodes,   0.03s,  12.18 Mnps
perft( 8)      2469050 nodes,   0.13s,  19.60 Mnps
perft( 9)     12803372 nodes,   0.74s,  17.40 Mnps
perft(10)     77920042 nodes,   3.78s,  20.60 Mnps
perft(11)    396940628 nodes,  24.19s,  16.41 Mnps
perft(12)   2365222285 nodes, 122.13s,  19.37 Mnps

[Rein Halbersma]

The perft numbers for the initial position of Thai draughts (with 4 instead of the usual 2 empty rows) are given below.
For this game I have not been able to find an official rule document. The game is similar to Spanish checkers, but without the majority capture rule and with 3 additional rules. First, pieces are removed during a capture sequence. Second, a king has to halt immediately after the final captured piece. Third, a king can reverse its capture direction 180 degrees at any time during a sequence. For some animations see http://thaibg.com/template.php?CenterFi ... rans/th/en

Note: the immediate halt after a king capture implies that 2 kings against 1 king can win. Combined with the sparse initial position, this game might be the easiest to solve once 10 piece databases have been computed.

Code: Select all

  b   b   b   b
b   b   b   b
  .   .   .   .
.   .   .   .
  .   .   .   .
.   .   .   .
  w   w   w   w
w   w   w   w

W:B1,2,3,4,5,6,7,8:W25,26,27,28,29,30,31,32"

Searching starting position to nominal depth=11

perft( 1)            7 nodes,   0.00s,   0.01 Mnps
perft( 2)           49 nodes,   0.00s,   0.05 Mnps
perft( 3)          392 nodes,   0.00s,   0.39 Mnps
perft( 4)         3136 nodes,   0.00s,   3.14 Mnps
perft( 5)        26592 nodes,   0.00s,  26.59 Mnps
perft( 6)       218695 nodes,   0.02s,  12.86 Mnps
perft( 7)      1820189 nodes,   0.05s,  37.92 Mnps
perft( 8)     14533014 nodes,   0.36s,  40.37 Mnps
perft( 9)    114530866 nodes,   3.03s,  37.77 Mnps
perft(10)    861843865 nodes,  23.66s,  36.43 Mnps
perft(11)   6305003332 nodes, 185.75s,  33.94 Mnps

[Ed Gilbert]

Rein,

Implementing efficient and correct move generators for all those draughts variations with a common set of source files is an ambitious project. Congratulations!

-- Ed

[Rein Halbersma]

Rein,

Implementing efficient and correct move generators for all those draughts variations with a common set of source files is an ambitious project. Congratulations!

-- Ed

Thanks Ed, your perft reference numbers and feedback were indispensable! The project is not quite finished: for Frisian draughts (orthogonal captures on a 10x10 board) I still need to implement one rule (a king cannot make more than 3 consecutive moves).

For those interested in the details: I indeed maintain a single code base for the universal move generator. I heavily use modern C++ template techniques, such as tag dispatching (to efficiently select rule dependent routines such as majority capture), type traits (non-intrusive properties of user-defined classes to be passed to other routines) and template metaprogramming (to compute board dependent constants such as the ghost bits). The actual move generator code is around 1000 lines of C++ code, but I needed to develop a supporting data structure (template classes for board layout, piece lists, move notations etc.) of about the same size. The actual rule definitions take up less than 100 lines of code. Adding a new variant only requires specifying in which respect the rules deviate from international draughts.

Just to give an idea: here's a bit from my main.cpp where the perft numbers for the Woldouby position is generated. "Board<10,10>" and "InternationalRules" are classes that encapsulate the board layout and the rules of the game.

Code: Select all

Position<Board<10,10> > Woldouby("W:B12,13,14,16,18,19,21,23,24,26:W25,27,28,30,32,33,34,35,37,38");
Perft::root<InternationalRules>(Woldouby, 15);

The perft routine itself is oblivious of the actual board and rules that it is called with. All those low-level details are hidden in the move generator. Thanks to the compile-time decisions made by C++ templates, performance overhead is within 10% compared to my previous non-generic perft version for international draughts. The alpha-beta search algorithm will similarly be fully generic and callable with arbitrary board/rules parameters. Only the evaluation function will have to be tuned separately for each game.

[wellnesswrotter]

van http://www.friesdammen.nl/dam/page3.php?articleID=260

Concurrentie voor Lusoris?

De meeste Friese dammers zullen het computerprogramma Lusoris wel kennen. Dat programma heeft nu mogelijk concurrentie gekregen uit Zweden. Mats Winther meldt althans op zijn homepage dat hij een programma geschreven heeft waarmee men het Friese damspel ("a wild form of checkers", zoals hij het kenschetst) kan spelen. Zie op:

http://hem.passagen.se/melki9

Het programma zelf is gratis, maar om het te kunnen spelen heeft u wel eerst het programma Zillions of Games nodig. Als ik het goed begrijp, kost een downloadversie van dat programma ongeveer 25 dollar; het laten toesturen van het programma op CD wordt ongeveer twee keer zo duur.

Welke Friese dammer test dit programma eens, en doet daar voor anderen verslag van, bijvoorbeeld in Oer Alles?

Siebren Dyk

Maar wellicht dat Rein nu ook al een speelbare versie heeft?

[Rein Halbersma]

Below the previous results in a table. I have also computed the perft numbers for Thai checkers in the position with 12 men that is used in all the other variants on an 8x8 board (Thai checkers only has 8 men in its initial position). NOTE: these results have not been corrected for possible duplicate capture moves.

There are roughly 3 major axis to distinguish the variants: 1) king range, 2) man capture backwards and 3) majority capture precedence. For the initial position, only the last 2 dimensions make a large difference in the perft counts. Up to d=4, all numbers are the same. Beyond that, the (Brazilian, Pool, Russian) family has a far larger number than the (English, Czech, Spanish, Italian, Thai) family. Within these families, majority capture further restricts the perft counts, although not by as much as the man capture backwards rule. E.g. the (English, Czech, Thai) family has slightly larger counts than the (Spanish, Italian) family, and similarly for the (Pool, Russian) games compared to Brazilian draughts.

[Rein Halbersma]

For international draughts, capture duplicates can really explode the move list. Ed Gilbert has found this position "B:W6,K8,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24", which has 17 moves without duplicates and 530 with duplicates. On the forum this position "B:W6,9,10,11,20,21,22,23,30,K31,33,37,41,42,43,44,46:BK17,K24" was posted, with 14 moves without duplicates and 178 with duplicates. (The positions differ by a white king on square 8). This is annoying since without the capture explosion, you can do with move arrays of 128 entries, and otherwise you have to blow this up to 1024 entries to be safe, or use a STL vector which is really annoying since it allocates memory on the heap rather than the stack. (I use a class wrapper around a fixed move array of 128 entries which implements a small subset of the STL vector interface).

In my international draughts move generator, I remove such duplicate captures by default. The overhead is tiny once you notice that full circle capture (which you can take clockwise or anti-clockwise) need at least 4 captured pieces. There are even 2 other constraints, namely the first capture added is by definition unique and in games where man cannot capture backwards and cannot promote en-passant, a man capture is also always unique. E.g. I have this in my code:

Code: Select all

const bool non_ambiguous = is_UniqueManCapture<Rules>::VALUE || empty() || small<Rules>()(current_capture, captured_pieces) || is_unique();

The C/C++ logical short-circuit rules make sure that the somewhat expensive function is_unique() is only evaluated if the previous 3 filters failed to evaluate to true. In games with majority capture, testing for smallness is cheap since you already have to bookkeep the number of captured pieces. In games without majority capture, I currently just do a pop-count and test whether this is smaller than 4 (on modern machines, pop-counts are single-cycle instructions). Actually, the number 4 is also game dependent since for Frisian draughts (orthogonal capture) and Thai draughts (capture reversal in mid-air) capture sequences of 3 or more pieces can already be ambiguous. This is also taken care of by the template small<Rules>().

In any case, below are the duplicates removed perft counts for all the draughts variants on an 8x8 board. In the (Brazilian, Pool, Russian) family, large man captures can be ambiguous, and the counts start to differ at d=9. For the other variants, only king captures can be ambiguous and the results start to differ at d=12.