Perft for arbitrary board sizes

[Rein Halbersma]

Lately, I've managed to generalize my move generator to handle arbitrary board sizes that fit into a 64-bit integer. I've used about 400 lines of C++ templates to generate the various bitmasks (back row, initial position, etc.). The resulting code correctly reproduces my old 10x10 move generator on all perft() tests that were verified on this forum. And, there is no performance penalty because all the abstraction is done compile-time!

As a new test, here's the result for international draughts on an 8x8 board. This game actually exists and is commonly played in Brazil. Here is the result for the starting position:

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"

Starting position: searching to nominal depth=11

perft( 1)            7 nodes,   0.00s,   0.01 Mnps (b= 7.0, max=  7)
perft( 2)           49 nodes,   0.00s,   0.05 Mnps (b= 7.0, max=  7)
perft( 3)          302 nodes,   0.00s,   0.30 Mnps (b= 6.2, max=  8)
perft( 4)         1469 nodes,   0.00s,   1.47 Mnps (b= 4.9, max=  8)
perft( 5)         7473 nodes,   0.00s,   7.47 Mnps (b= 5.1, max= 10)
perft( 6)        37628 nodes,   0.00s,  37.63 Mnps (b= 5.0, max= 10)
perft( 7)       187302 nodes,   0.02s,  11.71 Mnps (b= 5.0, max= 12)
perft( 8)       907830 nodes,   0.05s,  18.91 Mnps (b= 4.8, max= 12)
perft( 9)      4431766 nodes,   0.22s,  20.14 Mnps (b= 4.9, max= 14)
perft(10)     21560022 nodes,   1.14s,  18.88 Mnps (b= 4.9, max= 15)
perft(11)    105491257 nodes,   5.25s,  20.09 Mnps (b= 4.9, max= 16)

[Rein Halbersma]

Here are perft numbers for international draughts on a "micro board" (4 by 4)

Code: Select all

  b   b
.   .
  .   .
w   w


W:B1,2:W7,8"

Starting position: searching to nominal depth=11

perft( 1)            3 nodes,   0.00s,   0.00 Mnps (b= 3.0, max=  3)
perft( 2)            9 nodes,   0.00s,   0.01 Mnps (b= 3.0, max=  3)
perft( 3)           12 nodes,   0.00s,   0.01 Mnps (b= 1.3, max=  2)
perft( 4)           16 nodes,   0.00s,   0.02 Mnps (b= 1.3, max=  2)
perft( 5)           27 nodes,   0.00s,   0.03 Mnps (b= 1.7, max=  5)
perft( 6)           30 nodes,   0.00s,   0.03 Mnps (b= 1.1, max=  3)
perft( 7)           51 nodes,   0.00s,   0.05 Mnps (b= 1.7, max=  5)
perft( 8)           69 nodes,   0.00s,   0.07 Mnps (b= 1.4, max=  3)
perft( 9)          140 nodes,   0.00s,   0.14 Mnps (b= 2.0, max=  5)
perft(10)          301 nodes,   0.02s,   0.02 Mnps (b= 2.1, max=  5)
perft(11)          677 nodes,   0.00s,   0.68 Mnps (b= 2.2, max=  5)

Here is the same for international draughts on a "mini board" (6 by 6)

Code: Select all

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


W:B1,2,3,4,5,6:W13,14,15,16,17,18"

Starting position: searching to nominal depth=11

perft( 1)            5 nodes,   0.00s,   0.01 Mnps (b= 5.0, max=  5)
perft( 2)           25 nodes,   0.00s,   0.03 Mnps (b= 5.0, max=  5)
perft( 3)          106 nodes,   0.00s,   0.11 Mnps (b= 4.2, max=  6)
perft( 4)          369 nodes,   0.00s,   0.37 Mnps (b= 3.5, max=  6)
perft( 5)         1301 nodes,   0.00s,   1.30 Mnps (b= 3.5, max=  8)
perft( 6)         4214 nodes,   0.00s,   4.21 Mnps (b= 3.2, max=  8)
perft( 7)        12912 nodes,   0.00s,  12.91 Mnps (b= 3.1, max=  8)
perft( 8)        39526 nodes,   0.00s,  39.53 Mnps (b= 3.1, max= 10)
perft( 9)       113614 nodes,   0.02s,   7.10 Mnps (b= 2.9, max= 10)
perft(10)       329982 nodes,   0.05s,   6.87 Mnps (b= 2.9, max= 13)
perft(11)       933564 nodes,   0.10s,   9.83 Mnps (b= 2.8, max= 13)

[Rein Halbersma]

The only known reference for comparison of my 8x8 results is a thread on the Russian shashki forum (with the help of Google translate) http://translate.google.com/translate?p ... ry_state0=

However, since the Russian programmers generally do not use bitboards, they do not eliminate duplicate captures in their perft scores (it is a bit more expensive with mailbox board representations). When I turn off the duplicate check, I get the numbers they generated. For the record, here are the counts for the initial position in 8x8 Brazilian draughts for depth>=8 (the lower depths are identical)

Code: Select all

perft( 8)       907836 nodes,   0.05s,  18.91 Mnps (b= 4.8, max= 12)
perft( 9)      4431847 nodes,   0.24s,  18.78 Mnps (b= 4.9, max= 14)
perft(10)     21566606 nodes,   1.11s,  19.43 Mnps (b= 4.9, max= 15)
perft(11)    105534946 nodes,   5.46s,  19.35 Mnps (b= 4.9, max= 16)
perft(12)    512171742 nodes,  27.07s,  18.92 Mnps (b= 4.9, max= 17)
perft(13)   2483592238 nodes, 135.29s,  18.36 Mnps (b= 4.8, max= 18)

They also generated perft results for international 10x10 draughts. Again, their results differ for depths>=8. I also confirm them if I turn off duplicate checking

Code: Select all

perft( 8)      6483971 nodes,   0.31s,  20.65 Mnps (b= 6.2, max= 14)
perft( 9)     41022614 nodes,   1.69s,  24.30 Mnps (b= 6.3, max= 16)
perft(10)    258935682 nodes,  10.49s,  24.69 Mnps (b= 6.3, max= 16)
perft(11)   1666207133 nodes,  66.40s,  25.09 Mnps (b= 6.4, max= 18)
perft(12)  10752899471 nodes, 423.57s,  25.39 Mnps (b= 6.5, max= 18)

The interesting thing is is that the thread on the Shashki forum was started in May 2006 (computing perft results for 8x8 Russian checkers), and the results for 8x8 Brazilian and 10x10 international draughts were already produced in March 2007! Our thread started in July 2008. So many thanks to them for the independent confirmations!

[BertTuyt]

Rein,

maybe interesting to determine the game theoretical outcome (based on the 10x10 draughts rules) for the 4x4 and 6x6 board.
don't think this will reveal any clue for 10x10, but it is just fun

Bert

[Rein Halbersma]

Rein,

maybe interesting to determine the game theoretical outcome (based on the 10x10 draughts rules) for the 4x4 and 6x6 board.
don't think this will reveal any clue for 10x10, but it is just fun

Bert

4x4 is a draw, as you can easily see by playing it out by hand
6x6 is a bit more fun. if you generate endgame databases, you can strongly solve it (i.e. know the value for every position exactly). i suspect a draw here as well

[Rein Halbersma]

Here is the same for international draughts on a "mini board" (6 by 6)

Code: Select all

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


W:B1,2,3,4,5,6:W13,14,15,16,17,18"

Starting position: searching to nominal depth=11

perft( 1)            5 nodes,   0.00s,   0.01 Mnps (b= 5.0, max=  5)
perft( 2)           25 nodes,   0.00s,   0.03 Mnps (b= 5.0, max=  5)
perft( 3)          106 nodes,   0.00s,   0.11 Mnps (b= 4.2, max=  6)
perft( 4)          369 nodes,   0.00s,   0.37 Mnps (b= 3.5, max=  6)
perft( 5)         1301 nodes,   0.00s,   1.30 Mnps (b= 3.5, max=  8)
perft( 6)         4214 nodes,   0.00s,   4.21 Mnps (b= 3.2, max=  8)
perft( 7)        12912 nodes,   0.00s,  12.91 Mnps (b= 3.1, max=  8)
perft( 8)        39526 nodes,   0.00s,  39.53 Mnps (b= 3.1, max= 10)
perft( 9)       113614 nodes,   0.02s,   7.10 Mnps (b= 2.9, max= 10)
perft(10)       329982 nodes,   0.05s,   6.87 Mnps (b= 2.9, max= 13)
perft(11)       933564 nodes,   0.10s,   9.83 Mnps (b= 2.8, max= 13)

More depth, and still dropping duplicate captures (as above)

Code: Select all

   b   b   b
 b   b   b  
   .   .   .
 .   .   .  
   w   w   w
 w   w   w  
"W:B1,2,3,4,5,6:W13,14,15,16,17,18"

Searching to nominal depth=17

info depth  1 leafs            5 time      0 inf knps
info depth  2 leafs           25 time      0 inf knps
info depth  3 leafs          106 time      0 inf knps
info depth  4 leafs          369 time      0 inf knps
info depth  5 leafs         1301 time      0 inf knps
info depth  6 leafs         4214 time      0 inf knps
info depth  7 leafs        12912 time      0 inf knps
info depth  8 leafs        39526 time      0 inf knps
info depth  9 leafs       113614 time      1 113614 knps
info depth 10 leafs       329982 time      5 65996.4 knps
info depth 11 leafs       933564 time     15 62237.6 knps
info depth 12 leafs      2678979 time     46 58238.7 knps
info depth 13 leafs      7509079 time    133 56459.2 knps
info depth 14 leafs     21546796 time    396 54411.1 knps
info depth 15 leafs     59298144 time   1122 52850.4 knps
info depth 16 leafs    172303864 time   3262 52821.5 knps
info depth 17 leafs    480328231 time   9304 51626 knps

Same for checkers on 6x6, but now keeping duplicate captures (I only drop duplicates for long-ranged kings)

Code: Select all

   b   b   b
 b   b   b  
   .   .   .
 .   .   .  
   w   w   w
 w   w   w  
"W:B1,2,3,4,5,6:W13,14,15,16,17,18"

Searching to nominal depth=17

info depth  1 leafs            5 time      0 inf knps
info depth  2 leafs           25 time      0 inf knps
info depth  3 leafs          106 time      0 inf knps
info depth  4 leafs          369 time      0 inf knps
info depth  5 leafs         1271 time      0 inf knps
info depth  6 leafs         4104 time      0 inf knps
info depth  7 leafs        12495 time      0 inf knps
info depth  8 leafs        37474 time      0 inf knps
info depth  9 leafs       104013 time      1 104013 knps
info depth 10 leafs       290032 time      4 72508 knps
info depth 11 leafs       808158 time     12 67346.5 knps
info depth 12 leafs      2209549 time     37 59717.5 knps
info depth 13 leafs      6039632 time     97 62264.2 knps
info depth 14 leafs     16775007 time    262 64026.7 knps
info depth 15 leafs     45722008 time    714 64036.4 knps
info depth 16 leafs    129088590 time   2012 64159.3 knps
info depth 17 leafs    354735390 time   5520 64263.7 knps

Again, any confirmation is welcome!

[jj]

Again, any confirmation is welcome!

Confirmation summary:
- rules: international draughts or checkers
- unique captures (duplicates removed) or non-unique (duplicates allowed)
- W x H = 8 x 8 draughts unique depth 11: confirmed
- W x H = 4 x 4 draughts unique depth 11: confirmed
- W x H = 6 x 6 draughts unique depth 11: confirmed
- W x H = 8 x 8 draughts duplic depth 10 and up: differences! <--- I have more leafs!
- W x H = 10 x 10 draughts duplic depth 12: confirmed [edit: depth 12 added]
- W x H = 6 x 6 draughts unique depth 17: confirmed
- W x H = 6 x 6 checkers duplic depth 17: confirmed
Plus:
- W x H = 8 x 10 draughts unique depth 11: to be confirmed
- W x H = 10 x 8 draughts unique depth 11: to be confirmed

So all is confirmed except 8 x 8 draughts duplic depth 10-12 where there are differences, which is remarkable.
By the way, I also have:
- W x H = 8 x 8 checkers duplic depth 13: confirmed Aart Bik (see also below).

See also: Perft on large boards viewtopic.php?f=53&t=4563.

Details:

Code: Select all

checkers = false
unique = true
W x H = 8 x 8
 x x x x
x x x x 
 x x x x
. . . . 
 . . . .
o o o o 
 o o o o
o o o o 
white to move
perft(1) 7 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 49 leafs 8 nodes in 1 msec 8 kN/s
perft(3) 302 leafs 57 nodes in 1 msec 57 kN/s
perft(4) 1469 leafs 359 nodes in 1 msec 359 kN/s
perft(5) 7473 leafs 1828 nodes in 11 msec 166 kN/s
perft(6) 37628 leafs 9301 nodes in 21 msec 442 kN/s
perft(7) 187302 leafs 46929 nodes in 89 msec 527 kN/s
perft(8) 907830 leafs 234231 nodes in 241 msec 971 kN/s
perft(9) 4431766 leafs 1142061 nodes in 1131 msec 1009 kN/s
perft(10) 21560022 leafs 5573827 nodes in 4298 msec 1296 kN/s
perft(11) 105491257 leafs 27133849 nodes in 20299 msec 1336 kN/s
confirmed

checkers = false
unique = true
W x H = 4 x 4
 x x
. . 
 . .
o o 
white to move
perft(1) 3 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 9 leafs 4 nodes in 1 msec 4 kN/s
perft(3) 12 leafs 13 nodes in 1 msec 13 kN/s
perft(4) 16 leafs 25 nodes in 1 msec 25 kN/s
perft(5) 27 leafs 41 nodes in 1 msec 41 kN/s
perft(6) 30 leafs 68 nodes in 1 msec 68 kN/s
perft(7) 51 leafs 98 nodes in 11 msec 8 kN/s
perft(8) 69 leafs 149 nodes in 1 msec 149 kN/s
perft(9) 140 leafs 218 nodes in 1 msec 218 kN/s
perft(10) 301 leafs 358 nodes in 1 msec 358 kN/s
perft(11) 677 leafs 659 nodes in 1 msec 659 kN/s
confirmed

checkers = false
unique = true
W x H = 6 x 6
 x x x
x x x 
 . . .
. . . 
 o o o
o o o 
white to move
perft(1) 5 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 25 leafs 6 nodes in 1 msec 6 kN/s
perft(3) 106 leafs 31 nodes in 1 msec 31 kN/s
perft(4) 369 leafs 137 nodes in 1 msec 137 kN/s
perft(5) 1301 leafs 506 nodes in 1 msec 506 kN/s
perft(6) 4214 leafs 1807 nodes in 1 msec 1807 kN/s
perft(7) 12912 leafs 6021 nodes in 11 msec 547 kN/s
perft(8) 39526 leafs 18933 nodes in 36 msec 525 kN/s
perft(9) 113614 leafs 58459 nodes in 128 msec 456 kN/s
perft(10) 329982 leafs 172073 nodes in 261 msec 659 kN/s
perft(11) 933564 leafs 502055 nodes in 446 msec 1125 kN/s
confirmed

checkers = false
unique = false
W x H = 8 x 8
perft(8) 907836 leafs 234231 nodes in 281 msec 833 kN/s
perft(9) 4431847 leafs 1142067 nodes in 1163 msec 982 kN/s
perft(10) 21566622 leafs 5573914 nodes in 4209 msec 1324 kN/s
      --> 21566606 Rein, Russians
perft(11) 105535090 leafs 27140536 nodes in 20138 msec 1347 kN/s
      --> 105534946 RR
perft(12) 512173213 leafs 132675626 nodes in 99394 msec 1334 kN/s
      --> 512171742 RR
perft(13) not calculated
--> differences!

checkers = false
unique = false
W x H = 10 x 10
perft(8) 6483971 leafs 1248713 nodes in 1501 msec 831 kN/s
perft(9) 41022614 leafs 7732684 nodes in 9014 msec 857 kN/s
perft(10) 258935682 leafs 48755298 nodes in 57661 msec 845 kN/s
perft(11) 1666207133 leafs 307690980 nodes in 336551 msec 914 kN/s
perft(12) 10752899471 leafs 1973898113 nodes in 2280572 msec 865 kN/s [edit: added depth 12]
confirmed

checkers = false
unique = true
W x H = 6 x 6
 x x x
x x x 
 . . .
. . . 
 o o o
o o o 
white to move
perft(1) 5 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 25 leafs 6 nodes in 1 msec 6 kN/s
perft(3) 106 leafs 31 nodes in 1 msec 31 kN/s
perft(4) 369 leafs 137 nodes in 1 msec 137 kN/s
perft(5) 1301 leafs 506 nodes in 1 msec 506 kN/s
perft(6) 4214 leafs 1807 nodes in 11 msec 164 kN/s
perft(7) 12912 leafs 6021 nodes in 11 msec 547 kN/s
perft(8) 39526 leafs 18933 nodes in 51 msec 371 kN/s
perft(9) 113614 leafs 58459 nodes in 101 msec 578 kN/s
perft(10) 329982 leafs 172073 nodes in 276 msec 623 kN/s
perft(11) 933564 leafs 502055 nodes in 291 msec 1725 kN/s
perft(12) 2678979 leafs 1435619 nodes in 761 msec 1886 kN/s
perft(13) 7509079 leafs 4114598 nodes in 2016 msec 2040 kN/s
perft(14) 21546796 leafs 11623677 nodes in 5966 msec 1948 kN/s
perft(15) 59298144 leafs 33170473 nodes in 15688 msec 2114 kN/s
perft(16) 172303864 leafs 92468617 nodes in 44416 msec 2081 kN/s
perft(17) 480328231 leafs 264772481 nodes in 119472 msec 2216 kN/s
confirmed

checkers = true
unique = false
W x H = 6 x 6
 x x x
x x x 
 . . .
. . . 
 o o o
o o o 
white to move
perft(1) 5 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 25 leafs 6 nodes in 1 msec 6 kN/s
perft(3) 106 leafs 31 nodes in 1 msec 31 kN/s
perft(4) 369 leafs 137 nodes in 1 msec 137 kN/s
perft(5) 1271 leafs 506 nodes in 1 msec 506 kN/s
perft(6) 4104 leafs 1777 nodes in 11 msec 161 kN/s
perft(7) 12495 leafs 5881 nodes in 11 msec 534 kN/s
perft(8) 37474 leafs 18376 nodes in 31 msec 592 kN/s
perft(9) 104013 leafs 55850 nodes in 91 msec 613 kN/s
perft(10) 290032 leafs 159863 nodes in 144 msec 1110 kN/s
perft(11) 808158 leafs 449895 nodes in 231 msec 1947 kN/s
perft(12) 2209549 leafs 1258053 nodes in 513 msec 2452 kN/s
perft(13) 6039632 leafs 3467602 nodes in 1379 msec 2514 kN/s
perft(14) 16775007 leafs 9507234 nodes in 3836 msec 2478 kN/s
perft(15) 45722008 leafs 26282241 nodes in 10181 msec 2581 kN/s
perft(16) 129088590 leafs 72004249 nodes in 28508 msec 2525 kN/s
perft(17) 354735390 leafs 201092839 nodes in 76281 msec 2636 kN/s
confirmed

checkers = false
unique = true
W x H = 8 x 10
 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 
white to move
perft(1) 7 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 49 leafs 8 nodes in 1 msec 8 kN/s
perft(3) 302 leafs 57 nodes in 1 msec 57 kN/s
perft(4) 1469 leafs 359 nodes in 11 msec 32 kN/s
perft(5) 7473 leafs 1828 nodes in 1 msec 1828 kN/s
perft(6) 37628 leafs 9301 nodes in 21 msec 442 kN/s
perft(7) 193605 leafs 46929 nodes in 111 msec 422 kN/s
perft(8) 995303 leafs 240534 nodes in 296 msec 812 kN/s
perft(9) 5222464 leafs 1235837 nodes in 1056 msec 1170 kN/s
perft(10) 27405228 leafs 6458301 nodes in 5589 msec 1155 kN/s
perft(11) 146853805 leafs 33863529 nodes in 27578 msec 1227 kN/s
to be confirmed...

checkers = false
unique = true
W x H = 10 x 8
 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 
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 11 msec 455 kN/s
perft(6) 167140 leafs 32131 nodes in 101 msec 318 kN/s
perft(7) 1029319 leafs 199271 nodes in 271 msec 735 kN/s
perft(8) 6127190 leafs 1228590 nodes in 1196 msec 1027 kN/s
perft(9) 36751086 leafs 7355780 nodes in 7244 msec 1015 kN/s
perft(10) 218398167 leafs 44106866 nodes in 42858 msec 1029 kN/s
perft(11) 1306818894 leafs 262505033 nodes in 253757 msec 1034 kN/s
to be confirmed...

(checkers = true
unique = false
W x H = 8 x 8
 x x x x
x x x x 
 x x x x
. . . . 
 . . . .
o o o o 
 o o o o
o o o o 
white to move
perft(1) 7 leafs 1 nodes in 1 msec 1 kN/s
perft(2) 49 leafs 8 nodes in 1 msec 8 kN/s
perft(3) 302 leafs 57 nodes in 1 msec 57 kN/s
perft(4) 1469 leafs 359 nodes in 11 msec 32 kN/s
perft(5) 7361 leafs 1828 nodes in 6 msec 304 kN/s
perft(6) 36768 leafs 9189 nodes in 21 msec 437 kN/s
perft(7) 179740 leafs 45957 nodes in 81 msec 567 kN/s
perft(8) 845931 leafs 225697 nodes in 241 msec 936 kN/s
perft(9) 3963680 leafs 1071628 nodes in 906 msec 1182 kN/s
perft(10) 18391564 leafs 5035308 nodes in 3181 msec 1582 kN/s
perft(11) 85242128 leafs 23426872 nodes in 14448 msec 1621 kN/s
perft(12) 388623673 leafs 108669000 nodes in 68106 msec 1595 kN/s
perft(13) 1766623630 leafs 497292673 nodes in 348038 msec 1428 kN/s
confirmed Aart Bik [url]http://www.aartbik.com/strategy.php[/url])

Jan-Jaap

[Rein Halbersma]

Again, any confirmation is welcome!

Confirmation summary:
- rules: international draughts or checkers
- unique captures (duplicates removed) or non-unique (duplicates allowed)
- W x H = 8 x 8 draughts unique depth 11: confirmed
- W x H = 4 x 4 draughts unique depth 11: confirmed
- W x H = 6 x 6 draughts unique depth 11: confirmed
- W x H = 8 x 8 draughts duplic depth 10 and up: differences! <--- I have more leafs!
- W x H = 10 x 10 draughts duplic depth 11: confirmed (depth 12 not calculated)
- W x H = 6 x 6 draughts unique depth 17: confirmed
- W x H = 6 x 6 checkers duplic depth 17: confirmed
Plus:
- W x H = 8 x 10 draughts unique depth 11: to be confirmed
- W x H = 10 x 8 draughts unique depth 11: to be confirmed

So all is confirmed except 8 x 8 draughts duplic depth 10-12 where there are differences, which is remarkable.
By the way, I also have:
- W x H = 8 x 8 checkers duplic depth 13: confirmed Aart Bik (see also below).

See also: Perft on large boards viewtopic.php?f=53&t=4563.

Thanks for all this confirmation. Regarding the 8x8 international without duplicates, can you also test for 10x10 international, duplicates kept, depth<= 12? The only thing that comes to mind is that with array-based programs, duplicate checking is tricky if you don't sort the array holding the captures (it's automatic with bitboards). Do you sort the squares where you captured on before duplicate checking? It could also be that the bug is from Russia with love, and that I got lulled into a false sense of security when I confirmed their results

BTW, I confirmed checkers perft(21) for Aart and was the first to do perft(22). The rest is history because Aart went to perft(28)

[jj]

Thanks for all this confirmation. Regarding the 8x8 international without duplicates, can you also test for 10x10 international, duplicates kept, depth<= 12? The only thing that comes to mind is that with array-based programs, duplicate checking is tricky if you don't sort the array holding the captures (it's automatic with bitboards). Do you sort the squares where you captured on before duplicate checking? It could also be that the bug is from Russia with love, and that I got lulled into a false sense of security when I confirmed their results

Yes I already started:
- W x H = 10 x 10 draughts duplic depth 12:

Code: Select all

perft(12) 10752899471 leafs 1973898113 nodes in 2280572 msec 865 kN/s

So confirmed. Also edited into my previous post.

I don't sort the arrays. I take one array, loop all elements and test if they occur in the other array. I wonder why you have less moves without duplicate check (and we have the same with duplicate check). In case you want to try a divide, here are my numbers:

- W x H = 8 x 8 draughts duplic depth 10:
1. divide 21-17 3531009 nodes
2. divide 22-17 4071667 nodes
3. divide 22-18 2652690 nodes
4. divide 23-18 3019189 nodes
5. divide 23-19 2398120 nodes
6. divide 24-19 2365674 nodes
7. divide 24-20 3528273 nodes
perft(10) 21566622 leafs 5573913 nodes in 4171 msec 1336 kN/s

[Rein Halbersma]

Thanks for all this confirmation. Regarding the 8x8 international without duplicates, can you also test for 10x10 international, duplicates kept, depth<= 12? The only thing that comes to mind is that with array-based programs, duplicate checking is tricky if you don't sort the array holding the captures (it's automatic with bitboards). Do you sort the squares where you captured on before duplicate checking? It could also be that the bug is from Russia with love, and that I got lulled into a false sense of security when I confirmed their results

Yes I already started:
- W x H = 10 x 10 draughts duplic depth 12:

Code: Select all

perft(12) 10752899471 leafs 1973898113 nodes in 2280572 msec 865 kN/s

So confirmed. Also edited into my previous post.

I don't sort the arrays. I take one array, loop all elements and test if they occur in the other array. I wonder why you have less moves without duplicate check (and we have the same with duplicate check). In case you want to try a divide, here are my numbers:

- W x H = 8 x 8 draughts duplic depth 10:
1. divide 21-17 3531009 nodes
2. divide 22-17 4071667 nodes
3. divide 22-18 2652690 nodes
4. divide 23-18 3019189 nodes
5. divide 23-19 2398120 nodes
6. divide 24-19 2365674 nodes
7. divide 24-20 3528273 nodes
perft(10) 21566622 leafs 5573913 nodes in 4171 msec 1336 kN/s

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 to nominal depth=10

Found 7 moves, searching each to nominal depth=9

 1.21-17 info depth  9 leafs      3531007 time     71 nps     inf
 2.22-17 info depth  9 leafs      4071665 time     82 nps     inf
 3.22-18 info depth  9 leafs      2652686 time     52 nps     inf
 4.23-18 info depth  9 leafs      3019187 time     56 nps     inf
 5.23-19 info depth  9 leafs      2398118 time     46 nps     inf
 6.24-19 info depth  9 leafs      2365670 time     45 nps     inf
 7.24-20 info depth  9 leafs      3528273 time     70 nps     inf
Total leafs: 21566606

Let's pick the first move

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  
"B:B1,2,3,4,5,6,7,8,9,10,11,12:W17,22,23,24,25,26,27,28,29,30,31,32"

Searching to nominal depth=9

Found 7 moves, searching each to nominal depth=8

 1.09-13 info depth  8 leafs       561001 time     12 nps     inf
 2.09-14 info depth  8 leafs       332513 time      7 nps     inf
 3.10-14 info depth  8 leafs        87934 time      1 nps     inf
 4.10-15 info depth  8 leafs       615895 time     11 nps     inf
 5.11-15 info depth  8 leafs       554233 time     11 nps     inf
 6.11-16 info depth  8 leafs       724719 time     15 nps     inf
 7.12-16 info depth  8 leafs       654712 time     13 nps     inf
Total leafs: 3531007

[jj]

Code: Select all

1. divide 9-13 561002 nodes
2. divide 9-14 332513 nodes
3. divide 10-14 87934 nodes
4. divide 10-15 615895 nodes
5. divide 11-15 554234 nodes
6. divide 11-16 724719 nodes
7. divide 12-16 654712 nodes
perft(9) 3531009 leafs 925537 nodes in 793 msec 1167 kN/s

Again, the first move.

Code: Select all

 x x x x
x x x x 
 . x x x
x . . . 
 o . . .
. o o o 
 o o o o
o o o o 
white to move

1. divide 17-14 41453 nodes
2. divide 22-18 32625 nodes
3. divide 23-18 129036 nodes
4. divide 23-19 53952 nodes
5. divide 24-19 50595 nodes
6. divide 24-20 114687 nodes
7. divide 25-21 138654 nodes
perft(8) 561002 leafs 148239 nodes in 401 msec 369 kN/s

[Rein Halbersma]

Code: Select all

1. divide 9-13 561002 nodes
2. divide 9-14 332513 nodes
3. divide 10-14 87934 nodes
4. divide 10-15 615895 nodes
5. divide 11-15 554234 nodes
6. divide 11-16 724719 nodes
7. divide 12-16 654712 nodes
perft(9) 3531009 leafs 925537 nodes in 793 msec 1167 kN/s

Again, the first move.

Code: Select all

 x x x x
x x x x 
 . x x x
x . . . 
 o . . .
. o o o 
 o o o o
o o o o 
white to move

1. divide 17-14 41453 nodes
2. divide 22-18 32625 nodes
3. divide 23-18 129036 nodes
4. divide 23-19 53952 nodes
5. divide 24-19 50595 nodes
6. divide 24-20 114687 nodes
7. divide 25-21 138654 nodes
perft(8) 561002 leafs 148239 nodes in 401 msec 369 kN/s

The difference was in move 7

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,10,11,12,13:W17,22,23,24,25,26,27,28,29,30,31,32"

Searching to nominal depth=8

Found 7 moves, searching each to nominal depth=7

 1.17-14 info depth  7 leafs        41453 time      0 nps     inf
 2.22-18 info depth  7 leafs        32625 time      0 nps     inf
 3.23-18 info depth  7 leafs       129036 time      2 nps     inf
 4.23-19 info depth  7 leafs        53952 time      1 nps     inf
 5.24-19 info depth  7 leafs        50595 time      1 nps     inf
 6.24-20 info depth  7 leafs       114687 time      2 nps     inf
 7.25-21 info depth  7 leafs       138653 time      3 nps     inf
Total leafs: 561001

   b   b   b   b
 b   b   b   b  
   .   b   b   b
 b   .   .   .  
   w   .   .   .
 w   w   w   w  
   .   w   w   w
 w   w   w   w  
"B:B1,2,3,4,5,6,7,8,10,11,12,13:W17,21,22,23,24,26,27,28,29,30,31,32"

Searching to nominal depth=7

Found 7 moves, searching each to nominal depth=6

 1.05-09 info depth  6 leafs        20260 time      0 nps     inf
 2.06-09 info depth  6 leafs        26261 time      0 nps     inf
 3.10-14 info depth  6 leafs         3717 time      0 nps     inf
 4.10-15 info depth  6 leafs        26029 time      0 nps     inf
 5.11-15 info depth  6 leafs        19044 time      0 nps     inf
 6.11-16 info depth  6 leafs        21337 time      0 nps     inf
 7.12-16 info depth  6 leafs        22005 time      0 nps     inf
Total leafs: 138653

[jj]

Code: Select all

1. divide 5-9 20260 nodes
2. divide 6-9 26261 nodes
3. divide 10-14 3717 nodes
4. divide 10-15 26029 nodes
5. divide 11-15 19045 nodes
6. divide 11-16 21337 nodes
7. divide 12-16 22005 nodes
perft(7) 138654 leafs 37598 nodes in 131 msec 287 kN/s

Move 5.

 x x x x
x x x x 
 . x . x
x . x . 
 o . . .
o o o o 
 . o o o
o o o o 
white to move

1. divide 17-14 247 nodes
2. divide 22-18 977 nodes
3. divide 23-18 3678 nodes
4. divide 23-19 3274 nodes
5. divide 24-19 510 nodes
6. divide 24-20 5573 nodes
7. divide 29-25 2434 nodes
8. divide 30-25 2352 nodes
perft(6) 19045 leafs 5039 nodes in 21 msec 239 kN/s

[Rein Halbersma]

Code: Select all

1. divide 5-9 20260 nodes
2. divide 6-9 26261 nodes
3. divide 10-14 3717 nodes
4. divide 10-15 26029 nodes
5. divide 11-15 19045 nodes
6. divide 11-16 21337 nodes
7. divide 12-16 22005 nodes
perft(7) 138654 leafs 37598 nodes in 131 msec 287 kN/s

Move 5.

 x x x x
x x x x 
 . x . x
x . x . 
 o . . .
o o o o 
 . o o o
o o o o 
white to move

1. divide 17-14 247 nodes
2. divide 22-18 977 nodes
3. divide 23-18 3678 nodes
4. divide 23-19 3274 nodes
5. divide 24-19 510 nodes
6. divide 24-20 5573 nodes
7. divide 29-25 2434 nodes
8. divide 30-25 2352 nodes
perft(6) 19045 leafs 5039 nodes in 21 msec 239 kN/s

Move 7

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,10,12,13,15:W17,21,22,23,24,26,27,28,29,30,31,32"

Searching to nominal depth=6

Found 8 moves, searching each to nominal depth=5

 1.17-14 info depth  5 leafs          247 time      0 nps     inf
 2.22-18 info depth  5 leafs          977 time      0 nps     inf
 3.23-18 info depth  5 leafs         3678 time      0 nps     inf
 4.23-19 info depth  5 leafs         3274 time      0 nps     inf
 5.24-19 info depth  5 leafs          510 time      0 nps     inf
 6.24-20 info depth  5 leafs         5573 time      0 nps     inf
 7.29-25 info depth  5 leafs         2433 time      0 nps     inf
 8.30-25 info depth  5 leafs         2352 time      0 nps     inf
Total leafs: 19044

   b   b   b   b
 b   b   b   b  
   .   b   .   b
 b   .   b   .  
   w   .   .   .
 w   w   w   w  
   w   w   w   w
 .   w   w   w  
"B:B1,2,3,4,5,6,7,8,10,12,13,15:W17,21,22,23,24,25,26,27,28,30,31,32"

Searching to nominal depth=5

Found 8 moves, searching each to nominal depth=4

 1.05-09 info depth  4 leafs          349 time      0 nps     inf
 2.06-09 info depth  4 leafs          412 time      0 nps     inf
 3.07-11 info depth  4 leafs          523 time      0 nps     inf
 4.08-11 info depth  4 leafs          505 time      0 nps     inf
 5.10-14 info depth  4 leafs          261 time      0 nps     inf
 6.12-16 info depth  4 leafs          263 time      0 nps     inf
 7.15-18 info depth  4 leafs          118 time      0 nps     inf
 8.15-19 info depth  4 leafs            2 time      0 nps     inf
Total leafs: 2433

[jj]

Code: Select all

1. divide 5-9 349 nodes
2. divide 6-9 412 nodes
3. divide 7-11 523 nodes
4. divide 8-11 505 nodes
5. divide 10-14 261 nodes
6. divide 12-16 263 nodes
7. divide 15-18 119 nodes
8. divide 15-19 2 nodes
perft(5) 2434 leafs 764 nodes in 4 msec 191 kN/s

Move 7.

 x x x x
x x x x 
 . x . x
x . . . 
 o x . .
o o o o 
 o o o o
. o o o 
white to move

1. divide 22x15 12 nodes
2. divide 23x14 107 nodes
perft(4) 119 leafs 43 nodes in 2 msec 21 kN/s