Perft on large boards

[Rein Halbersma]

In an old thread about rectangular boards, I gave the perft(9) result for 12x10 boards. Together with the 10x12 board with the right coloring, this is the largest board for which a bit-layout using 1 ghost column at each side fits within a 64-bit integer. The 10x12 board has the following bit-layout:

Code: Select all

   0   1   2   3   4   5
 6   7   8   9  10  11
  13  14  15  16  17  18
19  20  21  22  23  24
  26  27  28  29  30  31
32  33  34  35  36  37
  39  40  41  42  43  44
45  46  47  48  49  50
  52  53  54  55  56  57
58  59  60  61  62  63

Below the results of a perft(10) for the initial position on the 10x12 board

Code: Select all

   b   b   b   b   b   b
 b   b   b   b   b   b
   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   w   w   w   w   w
 w   w   w   w   w   w

"W:B1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24:W37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60"

Searching to nominal depth=10

info depth  1 leafs           11 nodes            1 time      0 nps     inf
info depth  2 leafs          121 nodes           12 time      0 nps     inf
info depth  3 leafs         1222 nodes          133 time      0 nps     inf
info depth  4 leafs        10053 nodes         1355 time      0 nps     inf
info depth  5 leafs        79049 nodes        11408 time      0 nps     inf
info depth  6 leafs       584100 nodes        90457 time      7 nps 12922429
info depth  7 leafs      4369366 nodes       674557 time     59 nps 11433169
info depth  8 leafs     31839056 nodes      5043923 time    468 nps 10777613
info depth  9 leafs    236364607 nodes     36882979 time   3327 nps 11085957
info depth 10 leafs   1742748504 nodes    273247586 time  24717 nps 11055047

The straightforward bit-layout for the 12x10 board has 1 ghost column at each side along the longer column dimension and requires 65 bits. Fortunately, a rotation of the internal bit representation by 90 degrees will align the ghost squares along the shorter row dimension. As I showed 3 years ago, this makes it possible to also fit a 12x10 board inside a 64-bits integer:

Code: Select all

58  45  32  19   6
  52  39  26  13   0
59  46  33  20   7
  53  40  27  14   1
60  47  34  21   8
  54  41  28  15   2
61  48  35  22   9
  55  42  29  16   3
62  49  36  23  10
  56  43  30  17   4
63  50  37  24  11
  57  44  31  18   5

Below the results of a perft(11) for the initial position on the 12x10 board

Code: Select all

 b   b   b   b   b
   b   b   b   b   b
 b   b   b   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   w   w
 w   w   w   w   w
   w   w   w   w   w

"W:B10,20,5,15,25,9,19,4,14,24,8,18,3,13,23,7,17,2,12,22,6,16,1,11,21:W40,50,60,45,55,39,49,59,44,54,38,48,58,43,53,37,47,57,42,52,36,46,56,41,51"

Searching to nominal depth=11

info depth  1 leafs            9 nodes            1 time      0 nps     inf
info depth  2 leafs           81 nodes           10 time      0 nps     inf
info depth  3 leafs          658 nodes           91 time      0 nps     inf
info depth  4 leafs         4265 nodes          749 time      0 nps     inf
info depth  5 leafs        27117 nodes         5014 time      0 nps     inf
info depth  6 leafs       167140 nodes        32131 time      2 nps 16065500
info depth  7 leafs      1049442 nodes       199271 time     17 nps 11721824
info depth  8 leafs      6483961 nodes      1248713 time    113 nps 11050558
info depth  9 leafs     41291394 nodes      7732674 time    748 nps 10337799
info depth 10 leafs    263895730 nodes     49024068 time   4633 nps 10581495
info depth 11 leafs   1731541289 nodes    312919798 time  28484 nps 10985810

And yes, the results up to and including depth=9, match the results that I gave 3 years ago.

[Rein Halbersma]

Of course, rectangular boards are only a curiosity, although a few experimental tournaments on 11x10 and 12x10 boards have been organized in the last few years (mainly because these boards have a 3 kings vs 1 king endgame that is not a draw). However, in Canada, 12x12 boards are an officially recognized variant, and the Canadian former 10x10 World Champion Marcel Deslauriers (in 1956) was also a national champion on this larger board. This was reason enough for me wanting to add such boards to my draugths and checkers template library.

So I needed to go beyond 64-bit integers. This in itself is not a very difficult programming exercise. In C++ it is pretty straightforward to define a generalized BitBoard class that overloads all the bitwise operators and behaves just like a 64-bit integer. In fact, the C++ Standard Library provides a class template std::bitset<N> that is almost perfectly suited for the job. Moreover, gcc adds as an extension two member functions _Find_first() and _Find_next() that enable iteration over all the 1-bits of such bitsets. However, it is not possible to use compile-time initialization of such extended class types, and many of my template metaprogramming tricks were simply not suited for such generalized BitBoards.

Enter C++14. I know it is only 2013, but early next year, a minor update to the C++11 Standard is very likely to be voted in as the next version. In fact, the soon-to-be-released 3.4 version of the Clang compiler is already feature complete! One particular feature stands out: relaxed compile-time constant expressions, recognizable by the C++11 keyword constexpr. This feature allows using almost all of C++ syntax (except virtual functions and some other minor features) at compile-time, provided the compiler has knowledge of all the inputs (so no I/O). It allows the creation of user-defined literal types that can be intialized and modified at compile-time. This feature is extremely powerful and allowed me to eliminate all template metaprogramming from my library and replace it by much shorter and much more readable regular C++ syntax.

The result is that I can now define arbitrarily large boards while keeping the bitboard syntax and bitwise operators, and also initialized these bitboards at compile-time (and the efficiency that comes along with that!). There are still a few minor limitations related to the preprocessor macros that are currently in place, but they will soon be eliminated so that the compiler can compute the minimal number of 64-bits integers required to fit the bit-layout of the user-provided board dimensions.

The underlying bitset class is a fusion between the earlier mentiond std::bitset<N> template and another C++ Standard Library class template called std::set<int> (an ordered collection of unique integers). I have defined the combined interface of both these classes and also provide iterators over the various 1-bits (using a rewrite of the earlier mentioned Find_first() and Find_next() functionality). This allows very easy serialization of bitboards to Standard Containers (e.g. the serialization of the bitboard pattern of legal man moves is obtained by applying std::transform with a back_inserter into a std::vector<Move>). This functionality is so general that it can easily be adapted for other large board games (chess, Xiangqi, Shogi, Go).

I have tentative plans to provide this functionality as a standalone GitHub repository. You can currently play with it in my current draughts and checkers template library repository. Note that the requirements are pretty steep: the latest SVN version of Clang (soon to be released as Clang 3.4) and some minor patching of one header in the the gcc 4.8 libstdc++ library. Support for gcc 4.9 is tentatively planned (coming next Spring).

[Rein Halbersma]

The bit-layout of the 10x12 board in the opposite coloring (for reasons that will become clear in the next post) with 2 ghost columns (2 columns is the default in my library in order to support orthogonal captures from the Frisian game of draughts) at each side, requires 74 bits:

Code: Select all

 0   1   2   3   4   5
   8   9  10  11  12  13
15  16  17  18  19  20
  23  24  25  26  27  28
30  31  32  33  34  35
  38  39  40  41  42  43
45  46  47  48  49  50
  53  54  55  56  57  58
60  61  62  63  64  65
  68  69  70  71  72  73

As a correctness-test, the perft(10) of the initial position on the above board should be identical to the one given earlier (opposite coloring, 1 ghost column at each side), and indeed it is:

Code: Select all

 b   b   b   b   b   b
   b   b   b   b   b   b
 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   w   w   w   w   w
   w   w   w   w   w   w

"W:B1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24:W37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60"

Searching to nominal depth=10

info depth  1 leafs           11 nodes            1 time      0 nps     inf
info depth  2 leafs          121 nodes           12 time      0 nps     inf
info depth  3 leafs         1222 nodes          133 time      0 nps     inf
info depth  4 leafs        10053 nodes         1355 time      0 nps     inf
info depth  5 leafs        79049 nodes        11408 time      1 nps 11408000
info depth  6 leafs       584100 nodes        90457 time     11 nps 8223364
info depth  7 leafs      4369366 nodes       674557 time     96 nps 7026635
info depth  8 leafs     31839056 nodes      5043923 time    709 nps 7114137
info depth  9 leafs    236364607 nodes     36882979 time   5323 nps 6928983
info depth 10 leafs   1742748504 nodes    273247586 time  39035 nps 7000066

Note that for the above computation, a bitset representation with two 64-bit integers was used, and this explains the almost 60% performance penalty. The corresponding bit-layout of the 12x10 board without an internal rotation and 2 instead of 1 ghost column at each side, requires 77 bits and looks like this:

Code: Select all

 0   1   2   3   4
   7   8   9  10  11
13  14  15  16  17
  20  21  22  23  24
26  27  28  29  30
  33  34  35  36  37
39  40  41  42  43
  46  47  48  49  50
52  53  54  55  56
  59  60  61  62  63
65  66  67  68  69
  72  73  74  75  76

As another correctness-test, the perft(11) of the initial position on this board should be the same as the one given earlier, and again it is (skipping the earlier iterations):

Code: Select all

info depth  9 leafs     41291394 nodes      7732674 time   1128 nps 6855207
info depth 10 leafs    263895730 nodes     49024068 time   7143 nps 6863232
info depth 11 leafs   1731541289 nodes    312919798 time  45325 nps 6903912

The performance penalty of using a twice as large bitboard representation is again almost 60%.

[Rein Halbersma]

On to the main result: the bit-layout of a 12x12 board with 2 ghost columns at each side requires 88-bits

Code: Select all

   0   1   2   3   4   5
 7   8   9  10  11  12
  15  16  17  18  19  20
22  23  24  25  26  27
  30  31  32  33  34  35
37  38  39  40  41  42
  45  46  47  48  49  50
52  53  54  55  56  57
  60  61  62  63  64  65
67  68  69  70  71  72
  75  76  77  78  79  80
82  83  84  85  86  87

The perft(10) for the initial position on the above board is as follows:

Code: Select all

   b   b   b   b   b   b
 b   b   b   b   b   b
   b   b   b   b   b   b
 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   w   w   w   w   w
   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,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30:W43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72"

Searching to nominal depth=10

info depth  1 leafs           11 nodes            1 time      0 nps     inf
info depth  2 leafs          121 nodes           12 time      0 nps     inf
info depth  3 leafs         1222 nodes          133 time      0 nps     inf
info depth  4 leafs        10053 nodes         1355 time      0 nps     inf
info depth  5 leafs        79049 nodes        11408 time      1 nps 11408000
info depth  6 leafs       584100 nodes        90457 time     12 nps 7538083
info depth  7 leafs      4369366 nodes       674557 time     95 nps 7100600
info depth  8 leafs     31839056 nodes      5043923 time    709 nps 7114137
info depth  9 leafs    237209258 nodes     36882979 time   5319 nps 6934194
info depth 10 leafs   1761652936 nodes    274092237 time  39125 nps 7005552

Note that the board coloring of the middle 4 rows of the 12x12 board are the same as the 10x12 board in the previous post. This was done on purpose so that doing a divide() on the 10x12 board (for which I had a correct 64-bit implementation) was easy comparable to the divide() on the 12x12 board (for which no smaller board representation exists). Happily, the perft(10) on the 10x12 board is the same in either bit-layout, so this adds confidence to claim that the above 12x12 perft(10) is also correct. Furthermore, the perft counts start the differ only beyond depth=9 since then the shallower depth of the smaller board will yield different moves (which is the same phenomenon as happened between the 10x10 and the 12x10 boards). Finally, the ubiquitous perft(11)=1665861398 on an artificially inflated 10x10 board with 8 ghost columns at each side (thereby straddling 90 bits!) is also correctly reproduced.

In any case, an independent confirmation is very much welcome!

[Rein Halbersma]

Code: Select all

   0   1   2   3   4   5   6   7   8
10  11  12  13  14  15  16  17  18  19
  21  22  23  24  25  26  27  28  29
31  32  33  34  35  36  37  38  39  40
  42  43  44  45  46  47  48  49  50
52  53  54  55  56  57  58  59  60  61
  63  64  65  66  67  68  69  70  71
73  74  75  76  77  78  79  80  81  82
  84  85  86  87  88  89  90  91  92
94  95  96  97  98  99 100 101 102 103

My program can now display arbitrarily large boards. Above a 10x19 board. This board is a member of the H x (2 x H - 1) class that allow a winning 3 kings vs 1 king endgame (as show in the classic book "3 tegen 1 is gemeen" by De Bruijn and Thoen). The board is special because (as all rectangular boards with even width and height) it has 2 single corner diagonals, but in this particular case, these diagonals intersect at the opposing edge (square <4> in this case). This allows a double catchment position. Place 3 white kings on 25, 84 and 92. A lone opposing king can then only be in one of the two upper triangles above the two single corner diagonals (because of threats like 25-X (X on 95 through 35) or 25-Y (Y on 36 through 91). If black is above the diagonal 94/4, then white plays 25-3 and black loses immediately (staying in that corner is followed by 3-Z, (Z in 13 through 42) and 92-4 with a single corner lockup.

The above board can be fit within 104 bits using 1 or 2 ghost edge columns. My program can now select the optimal ghost layout (rotated by 0, 90, 180 or 270 degrees) given the height, width, parity and number of ghost columns required. I use a piece of template metaprogramming (TMP) from the Boost.MPL library

Code: Select all

template
<
        class Dimensions,   // contains height, width and parity
        int EdgeColumns,
        class Orientations = boost::mpl::vector_c<int, 0, 90, 180, 270>
>
struct SizeMinimizingOrientation
:
        boost::mpl::deref< typename
                dctl::mpl::min_element< typename
                        boost::mpl::transform_view<
                                Orientations, detail::size<detail::make<Dimensions, boost::mpl::int_<EdgeColumns>, boost::mpl::_1>>
                        >::type
                >::type::base
        >::type
{};

During compile-time, the above piece of code will try each of the 4 angles 0, 90, 180 and 270 degrees, build a Grid class of the appropriate layout (using the detail::make template) and then compute its size (using detail::size). All these transformations are taken care of using boost::mpl::transform_view, and mpl::min_element will then find the smallest such angle. This angle is then selected (by mpl::deref, still at compiletime!) by the program to be create the actual board being used at runtime. I have tested this exhautively against handwritten bit layouts and in each case the compiler agrees

The actual rotations of a grid is done at compile-time, but this time with C++14 constexpr functions. Here's a piece of sample code that is called by the above TMP code

Code: Select all

inline
constexpr auto rotate(DimensionsObject const& dim, Angle const& theta)
{
        switch (theta) {
        case   0: return dim;
        case  90: return DimensionsObject{ dim.width() , dim.height(), static_cast<bool>((dim.height() % 2) ^ !dim.parity()) };
        case 180: return DimensionsObject{ dim.height(), dim.width() , static_cast<bool>((dim.height() % 2) ^ (dim.width() % 2) ^ (!!dim.parity())) };
        case 270: return DimensionsObject{ dim.width() , dim.height(), static_cast<bool>((dim.width()  % 2) ^ !dim.parity()) };
        default: return throw std::invalid_argument("Dimensions rotation angles shall be a multiple of 90 degrees."), dim;
        }
}

A DimensionsObject is a simple class containing height, width, and parity. Rotations on such an object follow the laws of geometry: width and height are interchanged, and the parity changes depending on whether height and/or width or even or odd. [Mathematicians can be assured: the corresponding unit tests with these classes verify the axioms of the rotation group so that I am pretty confident that these rotations are correctly defined].

Because this is a constexpr function supplied with compile time constant parameters, the return value can also be computed at compile-time and be used in the above mentioned meta-programming. This allows compile-time computations to be written using regular C++ syntax. Note e.g. the switch() statement inside rotate(). This code has 4 lines for each possible angle of rotation. The equivalent TMP code (which was in my library until recently) required 4 different partial specializations of a Rotate class template. Note also the throw() statement if an invalid angle is encountered. Exceptions are not allowed in constexpr functions, so throwing one on an invalid_argument will abort the compilation. This allows a nice way of having soft errors at runtime (if a user provided angle (e.g. from IO) turns out to be invalid) and hard errors at compile-time (if the compiler can prove an angle is invalid).

IMO, the only place to use TMP in modern C++ is to write algorithms on type sequences. The reason is that Boost.MPL provides a large class of very convenient compile-time equivalents to the Standard Library (such as the above min_element and transform_view). Unfortunately, the equivalent versions of those algorithms (std::min_element and std::transform) are not constexpr (yet). So the current state of compile-time computations in C++ is a hybrid between regular syntax and somewhat arcane TMP.

[Rein Halbersma]

Since I don't think I ever published perft on 14x14 boards, for Jan-Jaap's and others' convenience, here the perft(9) results while dropping duplicate captures:

Code: Select all

   b   b   b   b   b   b   b
 b   b   b   b   b   b   b  
   b   b   b   b   b   b   b
 b   b   b   b   b   b   b  
   b   b   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   w  
   w   w   w   w   w   w   w
 w   w   w   w   w   w   w  
   w   w   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,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42:W57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98"

Searching to nominal depth=9

info depth  1 leafs           13 time      0 inf knps
info depth  2 leafs          169 time      0 inf knps
info depth  3 leafs         2042 time      0 inf knps
info depth  4 leafs        20513 time      0 inf knps
info depth  5 leafs       195333 time      2 97666.5 knps
info depth  6 leafs      1710812 time     26 65800.5 knps
info depth  7 leafs     15007858 time    240 62532.7 knps
info depth  8 leafs    127249292 time   2178 58424.8 knps
info depth  9 leafs   1093968733 time  27646 39570.6 knps

Any confirmation welcome!

[jj]

Any confirmation welcome!

Confirmation summary:
- rules: international draughts
- unique captures (duplicates removed)
- W x H = 12 x 10 depth 10: confirmed (opposite coloring: not tested)
- W x H = 10 x 12 depth 11: confirmed (opposite coloring: not tested)
- W x H = 12 x 12 depth 10: confirmed
- W x H = 14 x 14 depth 9: confirmed

See also Perft for arbitrary board sizes viewtopic.php?f=53&t=2666.

Details:

Code: Select all

W x H = 12 x 10
 x x x x x x
x x x x x x 
 x x x x x x
x x x x x x 
 . . . . . .
. . . . . . 
 o o o o o o
o o o o o o 
 o o o o o o
o o o o o o 
white to move
perft(1) 11 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 121 leafs 12 nodes in 1 msec 12 kN/s
perft(3) 1222 leafs 133 nodes in 11 msec 12 kN/s
perft(4) 10053 leafs 1355 nodes in 1 msec 1355 kN/s
perft(5) 79049 leafs 11408 nodes in 41 msec 278 kN/s
perft(6) 584100 leafs 90457 nodes in 276 msec 327 kN/s
perft(7) 4369366 leafs 674557 nodes in 823 msec 819 kN/s
perft(8) 31839056 leafs 5043923 nodes in 6014 msec 838 kN/s
perft(9) 236364607 leafs 36882979 nodes in 42853 msec 860 kN/s
perft(10) 1742748504 leafs 273247586 nodes in 324147 msec 842 kN/s
confirmed

W x H = 10 x 12
 x x x x x
x x x x x 
 x x x x x
x x x x x 
 x x x x x
. . . . . 
 . . . . .
o o o o o 
 o o o o o
o o o o o 
 o o o o o
o o o o o 
white to move
perft(1) 9 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 81 leafs 10 nodes in 1 msec 10 kN/s
perft(3) 658 leafs 91 nodes in 1 msec 91 kN/s
perft(4) 4265 leafs 749 nodes in 11 msec 68 kN/s
perft(5) 27117 leafs 5014 nodes in 21 msec 238 kN/s
perft(6) 167140 leafs 32131 nodes in 101 msec 318 kN/s
perft(7) 1049442 leafs 199271 nodes in 311 msec 640 kN/s
perft(8) 6483961 leafs 1248713 nodes in 1461 msec 854 kN/s
perft(9) 41291394 leafs 7732674 nodes in 10491 msec 737 kN/s
perft(10) 263895730 leafs 49024068 nodes in 73546 msec 666 kN/s
perft(11) 1731541289 leafs 312919798 nodes in 438087 msec 714 kN/s
confirmed

12x10 and 10x12 opposite coloring: not tested

W x H = 12 x 12
 x x x x x x
x x x x x x 
 x x x x x x
x x x x x x 
 x x x x x x
. . . . . . 
 . . . . . .
o o o o o o 
 o o o o o o
o o o o o o 
 o o o o o o
o o o o o o 
white to move
perft(1) 11 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 121 leafs 12 nodes in 1 msec 12 kN/s
perft(3) 1222 leafs 133 nodes in 11 msec 12 kN/s
perft(4) 10053 leafs 1355 nodes in 1 msec 1355 kN/s
perft(5) 79049 leafs 11408 nodes in 51 msec 223 kN/s
perft(6) 584100 leafs 90457 nodes in 151 msec 599 kN/s
perft(7) 4369366 leafs 674557 nodes in 844 msec 799 kN/s
perft(8) 31839056 leafs 5043923 nodes in 6263 msec 805 kN/s
perft(9) 237209258 leafs 36882979 nodes in 43984 msec 838 kN/s
perft(10) 1761652936 leafs 274092237 nodes in 326214 msec 840 kN/s
confirmed

W x H = 14 x 14
 x x x x x x x
x x x x x x x 
 x x x x x x x
x x x x x x x 
 x x x x x x x
x x x x x x x 
 . . . . . . .
. . . . . . . 
 o o o o o o o
o o o o o o o 
 o o o o o o o
o o o o o o o 
 o o o o o o o
o o o o o o o 
white to move
perft(1) 13 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 169 leafs 14 nodes in 1 msec 14 kN/s
perft(3) 2042 leafs 183 nodes in 1 msec 183 kN/s
perft(4) 20513 leafs 2225 nodes in 21 msec 105 kN/s
perft(5) 195333 leafs 22738 nodes in 71 msec 320 kN/s
perft(6) 1710812 leafs 218071 nodes in 403 msec 541 kN/s
perft(7) 15007858 leafs 1928883 nodes in 3179 msec 606 kN/s
perft(8) 127249292 leafs 16936741 nodes in 30651 msec 552 kN/s
perft(9) 1093968733 leafs 144186033 nodes in 255055 msec 565 kN/s
confirmed

Jan-Jaap