perft for 8x8 checkers

[abik]

Apologies in advance for going somewhat off-topic, but for programmers that want to take a break from chess and write a 8x8 checkers engine instead, here are some perft() numbers from the starting position, computed on a 2.2 GHz Core 2 Duo (except the last three, which were obtained using a distributed implementation on a cluster of machines):

Code: Select all

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

The divide() breakdown per-move for the last three depths are shown below:

Code: Select all

       move      divide(18)    divide(19)     divide(20)
------------------------------------------------------------
  0  : 12-16 :   550829166472  2517202147314  11531470109861
  1  : 11-16 :   566149929068  2564849953998  11736729175821
  2  : 11-15 :   435063007630  2041959240377   9515983205474
  3  : 10-15 :   472279451484  2180656975018  10055597639275
  4  : 10-14 :   402570639569  1859042884028   8600202424158
  5  :  9-14 :   441590753001  2068865301476   9698986164172
  6  :  9-13 :   625398758917  2881467090588  13406062152792
------------------------------------------------------------
                3493881706141 16114043592799  74545030871553

[abik]

Continuing my quest for deeper and deeper perft numbers for 8x8 checkers, I now computed depth 25 with the same distributed implementation I used earlier for depths up to 24. Below you see the perft breakdown per move (called "divide") from the initial position for various depths up to 25 (my depth 23 and 24 numbers were recently kindly confirmed by Murray Cash at the World Draughts Forum). The numbers were computed on on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as 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).

Code: Select all

move      divide(18)     divide(19)     divide(20)      divide(21)       divide(22)       divide(23)        divide(24)          divide(25)
------------------------------------------------------------------------------------------------------------------------------------------
12-16:  550829166472  2517202147314 11531470109861  52945190026737  243598269855110 1123463594881857  5192042148594780   24019313789608561
11-16:  566149929068  2564849953998 11736729175821  53527954221225  246743868125768 1131373985922218  5248615918291379   24153215782987793
11-15:  435063007630  2041959240377  9515983205474  44775005468548  209016678583301  984253557821317  4602138522979438   21659601983574539
10-15:  472279451484  2180656975018 10055597639275  46574865098865  215412869777867 1000606302770349  4643700995955222   21609957136212495
10-14:  402570639569  1859042884028  8600202424158  39822944739732  184865466345796  856779998157523  3988937724259353   18496978526984076
 9-14:  441590753001  2068865301476  9698986164172  45530585259776  213736468971938 1003310451936358  4712325943133747   22101040287502927
 9-13:  625398758917  2881467090588 13406062152792  61923979665936  288999100078322 1337748969176591  6263620622082081   29027372375205409
------------------------------------------------------------------------------------------------------------------------------------------
       3493881706141 16114043592799 74545030871553 345100524480819 1602372721738102 7437536860666213 34651381875296000  161067479882075800

[yolin]

Well done!

Is this http://oeis.org/A133046? Be sure to upload it there too.

[Ajedrecista]

Hello Aart:

Continuing my quest for deeper and deeper perft numbers for 8x8 checkers, I now computed depth 25 with the same distributed implementation I used earlier for depths up to 24. Below you see the perft breakdown per move (called "divide") from the initial position for various depths up to 25 (my depth 23 and 24 numbers were recently kindly confirmed by Murray Cash at the World Draughts Forum). The numbers were computed on on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as 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).

Code: Select all

move      divide(18)     divide(19)     divide(20)      divide(21)       divide(22)       divide(23)        divide(24)          divide(25)
------------------------------------------------------------------------------------------------------------------------------------------
12-16:  550829166472  2517202147314 11531470109861  52945190026737  243598269855110 1123463594881857  5192042148594780   24019313789608561
11-16:  566149929068  2564849953998 11736729175821  53527954221225  246743868125768 1131373985922218  5248615918291379   24153215782987793
11-15:  435063007630  2041959240377  9515983205474  44775005468548  209016678583301  984253557821317  4602138522979438   21659601983574539
10-15:  472279451484  2180656975018 10055597639275  46574865098865  215412869777867 1000606302770349  4643700995955222   21609957136212495
10-14:  402570639569  1859042884028  8600202424158  39822944739732  184865466345796  856779998157523  3988937724259353   18496978526984076
 9-14:  441590753001  2068865301476  9698986164172  45530585259776  213736468971938 1003310451936358  4712325943133747   22101040287502927
 9-13:  625398758917  2881467090588 13406062152792  61923979665936  288999100078322 1337748969176591  6263620622082081   29027372375205409
------------------------------------------------------------------------------------------------------------------------------------------
       3493881706141 16114043592799 74545030871553 345100524480819 1602372721738102 7437536860666213 34651381875296000  161067479882075800

Fantastic! I like very much English draughts (aka American checkers) and I did an estimation of Perft(25) of the starting position at the end of July, 2011. I used a method called inverse interpolation that is described by Reinhard Scharnagl in this post and followings. I also used my own cheap method (briefly and badly explained in this post and followings). Regarding Perft(13) of chess, my estimate (only using my own method) was around 0.0302% less than the true value.

My own method:

Code: Select all

24log[Perft(25)]   23log[Perft(24)]
________________ > ________________
25log[Perft(24)]   24log[Perft(23)]


Perft(25) >= 160,778,351,488,836,793

Doing the inverse interpolation:

Code: Select all

ln[Perft(25)] ~ 39.6236719

Perft(25) ~ 1.6156306e+17

I took this last value as the centre value of an interval, and my first value as its lower bound; then, the upper bound was the symmetric value. Finally:

Code: Select all

1.6077835e+17 < Perft&#40;25&#41; < 1.6234776e+17

Perft&#40;25&#41; ~ 1.6156306e+17 ± 0.4857%

As you see, the width of this interval is very big, but at least I was right this time! The center value is more less 0.3077% higher than the true Perft(25) value.

By the way, do you know a free, fast perft counter for checkers? I only know about NebiyuCheckers 1.42 (which also does MonteCarlo and UCT estimates).

Thank you very much for this break! I see that you also posted your achievement in the World Draughts Forum. Could you answer how much time took this calculation, please? Thanks in advance.

Regards from Spain.

Ajedrecista.

[abik]

Well done! Is this http://oeis.org/A133046? Be sure to upload it there too.

Thanks for the link. Yes, that one was filed when I presented my first numbers.

[abik]

By the way, do you know a free, fast perft counter for checkers? I only know about NebiyuCheckers 1.42 (which also does MonteCarlo and UCT estimates).

Thanks for the interesting background.

Just in case folks are interested in a comparison, here are some single-threaded performance numbers of my generator on a 2.67GHz Intel Xeon:
* plain version
* optimized with bulk counting
* further optimized with a hard-collisions free hash table

The nodes per second ratings are relative to perft count numbers, so get quite high for the larger problems.

Code: Select all

                               plain                  bulk                  bulk+hash
----------------------------------------------------------------------------------------
perft(1) =           7        0ms.                    0ms.                  0ms.
perft(2) =          49        0ms.                    0ms.                  0ms.
perft(3) =         302        0ms.                    0ms.                  0ms.
perft(4) =        1469        0ms.                    0ms.                  0ms.
perft(5) =        7361        1ms.  7,361KN/s         0ms.                  0ms.
perft(6) =       36768        2ms. 18,384KN/s         1ms. 36,768KN/s       3ms.     12,256KN/s
perft(7) =      179740        7ms. 25,677KN/s         6ms. 29,956KN/s      11ms.     16,340KN/s
perft(8) =      845931       31ms. 27,288KN/s        20ms. 42,296KN/s      20ms.     42,296KN/s
perft(9) =     3963680      135ms. 29,360KN/s        66ms. 60,055KN/s      59ms.     67,181KN/s
perft(10)=    18391564      618ms. 29,759KN/s       319ms. 57,653KN/s     146ms.    125,969KN/s
perft(11)=    85242128    2,878ms. 29,618KN/s     1,455ms. 58,585KN/s     276ms.    308,848KN/s
perft(12)=   388623673   13,179ms. 29,488KN/s     6,819ms. 56,991KN/s     482ms.    806,273KN/s
perft(13)=  1766623630   60,634ms. 29,135KN/s    31,164ms. 56,688KN/s   1,292ms.  1,367,355KN/s
perft(14)=  7978439499  273,657ms. 29,154KN/s   143,178ms. 55,723KN/s   3,937ms.  2,026,527KN/s
perft(15)= 36263167175                                                 12,124ms.  2,991,023KN/s
perft(16)=165629569428                                                 45,123ms.  3,670,624KN/s

[abik]

I made some improvements to my distributed implementation for computing perft and divide numbers for 8x8 checkers that enabled me to go even deeper, and now computed depth 26 from the initial position, shown below. As reported earlier, the numbers were computed on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. 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).

Code: Select all

move              divide(26)
----------------------------
12-16:    111362678435231752
11-16:    112590257768420515
11-15:    101352649993886926
10-15:    100552646996749293
10-14:     86312674861234785
 9-14:    103811787278058952
 9-13:    136189763354484914
----------------------------
perft(26) 752172458688067137

[Ajedrecista]

Hello Aart:

I made some improvements to my distributed implementation for computing perft and divide numbers for 8x8 checkers that enabled me to go even deeper, and now computed depth 26 from the initial position, shown below. As reported earlier, the numbers were computed on a cluster of machines, further optimized with a "hard collision"-free transposition table as well as bulk counting. 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).

Code: Select all

move              divide(26)
----------------------------
12-16:    111362678435231752
11-16:    112590257768420515
11-15:    101352649993886926
10-15:    100552646996749293
10-14:     86312674861234785
 9-14:    103811787278058952
 9-13:    136189763354484914
----------------------------
perft(26) 752172458688067137

Congratulations once again! It will be difficult to do an accurate estimate for Perft(27) of checkers, but I have collected some data for trying it. The most intuitive is the branching factor but I have calculated more data. Taking into account from Perft(0) = 1 up to Perft(26), I wrote this simple Fortran 95 programme:

Code: Select all

program a
implicit none
integer::i
real(kind=3)::perft(0:27),bf(1:26),bound(3:26),factor(3:26)
open(unit=10,file='perft.txt',status='unknown',action='read')
do i=0,26
  read(10,*) perft(i)
end do
close(10)
open(unit=11,file='bf.txt',status='unknown',action='write')
do i=1,26
  bf(i)=perft(i)/perft(i-1)
  write(11,'(A,I2.2,A,F18.16)') 'BF(',i,') ~ ',bf(i)
end do
close(11)
open(unit=100,file='bounds.txt',status='unknown',action='write')
do i=3,27
  bound(i)=1d1**(i*(i-2)*log10(perft(i-1))*log10(perft(i-1))/((i-1)*(i-1)*log10(perft(i-2))))
  write(100,'(A,I2.2,A,F22.2)') 'Bound(',i,') ~ ',bound(i)
end do
close(100)
open(unit=101,file='factors.txt',status='unknown',action='write')
do i=3,26
  factor(i)=perft(i)/bound(i)
  write(101,'(A,I2.2,A,F18.16)') 'Factor(',i,') ~ ',factor(i)
end do
close(101)
end program

Here are the output files:

Code: Select all

Branching factors:

BF(01) ~ 7.0000000000000000
BF(02) ~ 7.0000000000000000
BF(03) ~ 6.1632653061224490
BF(04) ~ 4.8642384105960265
BF(05) ~ 5.0108917631041525
BF(06) ~ 4.9949735090340986
BF(07) ~ 4.8884899912967798
BF(08) ~ 4.7064148214087015
BF(09) ~ 4.6855831031136109
BF(10) ~ 4.6400224034230816
BF(11) ~ 4.6348493254842274
BF(12) ~ 4.5590564444848209
BF(13) ~ 4.5458466705398052
BF(14) ~ 4.5162078461500031
BF(15) ~ 4.5451453482282024
BF(16) ~ 4.5674325308845559
BF(17) ~ 4.5814211412284225
BF(18) ~ 4.6043688632108037
BF(19) ~ 4.6120747489751153
BF(20) ~ 4.6260909275971849
BF(21) ~ 4.6294235906274500
BF(22) ~ 4.6432056982491295
BF(23) ~ 4.6415773058085251
BF(24) ~ 4.6589862375743739
BF(25) ~ 4.6482267420597617
BF(26) ~ 4.6699213226578318

My bounds, that can be seen in the source code and also a little explanation in my first post inside this topic:

Code: Select all

BOUNDS:

Bound(03) ~                 343.00
Bound(04) ~                1716.20
Bound(05) ~                6188.46
Bound(06) ~               34093.57
Bound(07) ~              173964.46
Bound(08) ~              840286.51
Bound(09) ~             3816548.39
Bound(10) ~            17951166.54
Bound(11) ~            82886520.39
Bound(12) ~           385657496.38
Bound(13) ~          1731960876.75
Bound(14) ~          7874081158.22
Bound(15) ~         35396314082.28
Bound(16) ~        162416905634.49
Bound(17) ~        747237302357.03
Bound(18) ~       3439956018069.85
Bound(19) ~      15944930443433.94
Bound(20) ~      73742584613344.12
Bound(21) ~     342539143620704.01
Bound(22) ~    1588011654625104.93
Bound(23) ~    7401350345015265.34
Bound(24) ~   34356351306994143.90
Bound(25) ~  160778351488836792.62
Bound(26) ~  745717984070620532.31
Bound(27) ~ 3500971593638323868.20

And finally, my factors:

Code: Select all

Factor(i) = bound(i)/perft(i):

Factor(03) ~ 0.8804664723032070
Factor(04) ~ 0.8559621826059828
Factor(05) ~ 1.1894728779827857
Factor(06) ~ 1.0784439784352327
Factor(07) ~ 1.0331995148328852
Factor(08) ~ 1.0067173344647642
Factor(09) ~ 1.0385509614962865
Factor(10) ~ 1.0245330833102422
Factor(11) ~ 1.0284196705921786
Factor(12) ~ 1.0076912199315429
Factor(13) ~ 1.0200135890598076
Factor(14) ~ 1.0132533991815023
Factor(15) ~ 1.0244899254397188
Factor(16) ~ 1.0197803534118742
Factor(17) ~ 1.0154991039612712
Factor(18) ~ 1.0156762725418250
Factor(19) ~ 1.0106060763303425
Factor(20) ~ 1.0108817213610882
Factor(21) ~ 1.0074776296601921
Factor(22) ~ 1.0090434267728264
Factor(23) ~ 1.0048891775100633
Factor(24) ~ 1.0085873661514747
Factor(25) ~ 1.0017983042527904
Factor(26) ~ 1.0086553828059957

It is difficult to say at first glance, but factor(27) should be around 1.001 or somewhat like that, so Perft(27) would be around 3.5045e+18. It is just a gross estimate but I think that the true value will be close enough. I stay tuned, just in case you run your perft counter to get Perft(27)! Thank you very much for your effort.

Regards from Spain.

Ajedrecista.

[ibid]

Very interesting. You've triggered my perft addiction. :)

Spent the last couple of days putting together an undoubtably
awful checkers move generation, etc, and got it working with
my chess perft program.

After some silliness with an incorrect perft at depth 4, all is
working fine up to depth 23.

Tomorrow I will switch some hard drives around and get this
set up for a longer run; see if I can confirm those higher results.

-paul

[abik]

Spent the last couple of days putting together an undoubtably
awful checkers move generation, etc, and got it working with
my chess perft program.

After some silliness with an incorrect perft at depth 4, all is
working fine up to depth 23.

Can't be that awful if you already verified up to 23. Thanks for that!