Hello Aart:
abik wrote: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.