Perft(16) estimate after averaging MC samples.

[Ajedrecista]

Hello:

The end of this great forum as we know is near. I hope and wish that some members finally achieve the transition to a new server and all topics can be saved. Thanks to everybody that make this forum that great.

I started posting in this forum many years ago with an estimate of Perft(13) and just in case something goes wrong, I want that one of my last posts in the current forum to be about the same, other perft estimate. Here I go:

There is at least one Perft(16) estimate that is very good and can be found at other site: 6.507e+22. It is dated before I registered into TalkChess. I wondered how much could be improved, so I have been running MC samples of Perft(16) of the starting position for two and a half years more less, with GNU 5.50 x64 running in the background. I had not said anything before in the spirit of a secret war or a secret mission in order to get narrower and narrower intervals before posting anything, but the end of the current TalkChess forum has prompted me to share my results as they are right now.

Here is a typical output of GNU 5.50 x64 with the command perftmc 16:

Code: Select all

perftmc 16
m=6.518181e+022 sd=2.875989e+020 ci(99%)=[6.444096e+022,6.592267e+022] n=4750894 sdn=6.268663e+023 t=12.53s
m=6.507558e+022 sd=1.971200e+020 ci(99%)=[6.456780e+022,6.558336e+022] n=7126351 sdn=5.262162e+023 t=19.12s
m=6.505622e+022 sd=1.407234e+020 ci(99%)=[6.469371e+022,6.541872e+022] n=9501734 sdn=4.337782e+023 t=25.39s
[...]

The first line is the average after two iterations, then each line averages one more iteration. The meanings of the abbreviations are:

Code: Select all

m       := arithmetic mean
sd      := standard deviation (formula dividing by the number of iterations)
ci(99%) := 99% confidence interval
n       := nodes
sdn      = sd·sqrt(n)  // sdn is a measure of efficiency, less is better.
t       := time

Since each run is single threaded, I took advantage of multi-threaded CPUs and ran few runs simultaneously each time. I have been copying the full logs of each run as backup (almost 959 MB in total right now!), then taking into account the last line of each run to average in a similar fashion of other attempt by mine with Perft(15).

My best run in terms of lowest standard deviation up to now was this one:

Code: Select all

[...]
m=6.507024e+022 sd=9.432087e+017 ci(99%)=[6.506781e+022,6.507267e+022] n=1617983415 sdn=3.779099e+023 t=280802.70s

Interrupted!

Here is a summary of my long-term project:

Code: Select all

m=

Each occurrence is one iteration except the first one, where there are two. So there must be added 1 in each run:

{Runᵢ} ——> Iterationsᵢ = Occurrencesᵢ + 1

Total number of iterations after 1 125 runs: Σ(Iterationsᵢ) = 8 752 634
                                             ⁱ
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
Runᵢ	Iterationsᵢ

‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
0001	 9375
0002	22178
0003	22169
0004	22160
0005	22139
0006	 5345
0007	 5344
[...]
1116	 7403
1117	 7404
1118	 7346
1119	 7417
1120	 7422
1121	 6726
1122	 6714
1123	 6726
1124	 6728
1125	 6735

Code: Select all

__________________________________________________
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
Perft(16) Montecarlo estimates using GNU 5.50 x64.
__________________________________________________
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
Average Montecarlo estimates like averaging normal distributions with nodes as the weight factor := ωᵢ = (nᵢ) / [Σ(nᵢ)]
                                                                                                                 ⁱ
Nodes are counted with 32-bit integers and overflows happen. To get the correct number of nodes from the incorrect output n*ᵢ:
  n*ᵢ = [ (nᵢ - 2³¹) mod 2³² ] - 2³¹ ; (nᵢ - 2³¹) mod 2³² = 2³¹ + n*ᵢ
  sdnᵢ = sdᵢ × sqrt(nᵢ) ; nᵢ = [ (sdnᵢ) / (sdᵢ) ]²
  k = round[ (nᵢ - n*ᵢ) / 2³² ]
  nᵢ = k × 2³² + n*ᵢ
  nᵢ = ( round{ [ (sdnᵢ) / (sdᵢ) ]² - n*ᵢ } / 2³² ) × 2³² + n*ᵢ
                _
Average mean := m ≡ <m> = Σ(ωᵢ × mᵢ) = [ Σ(nᵢ × mᵢ) ] / [ Σ(nᵢ) ]
                          ⁱ   __         ⁱ                ⁱ
Average standard deviation := sd ≡ <sd> = sqrt{ Σ[(ωᵢ × sdᵢ)²] } = sqrt( { Σ[(nᵢ × sdᵢ)²] } / [Σ(nᵢ)]² ) = ( sqrt{ Σ[(nᵢ × sdᵢ)²] } ) / Σ(nᵢ)
                                                ⁱ                          ⁱ                   ⁱ                   ⁱ                    ⁱ
  Two ways to compute Σ[(nᵢ × sdᵢ)²] :
                      ⁱ
    a) Σ[(nᵢ × sdᵢ)²] = Σ[(nᵢ)² × (sdᵢ)²]
       ⁱ                ⁱ
    b) sdnᵢ = sdᵢ × sqrt(nᵢ) ; (sdnᵢ)² = (sdᵢ)² × nᵢ ; Σ[(nᵢ × sdᵢ)²] = Σ[nᵢ × (sdnᵢ)²]
                                                       ⁱ                ⁱ
  Option a) is chosen.

Solving z₉₅ and z₉₉ in:
  erf[ z₉₅ / sqrt(2) ] = 0.95 (95% confidence level in a normal distribution).
  erf[ z₉₉ / sqrt(2) ] = 0.99 (99% confidence level in a normal distribution).
    z₉₅ ≈ 1.959963984540054236 (rounding up to the 18th decimal at https://oeis.org/A220510 'Decimal expansion of the standard normal deviate for a 95% confidence interval').
    z₉₉ ≈ 2.575829303548900761 (rounding up to the 18th decimal at https://oeis.org/A329283 'Decimal expansion of the quantile z_0.995 of the standard normal distribution').
      <m> ± z₉₅ × <sd> ∈ [ <m> - 1.959963984540054236 × <sd> , <m> + 1.959963984540054236 × <sd> ]
      <m> ± z₉₉ × <sd> ∈ [ <m> - 2.575829303548900761 × <sd> , <m> + 2.575829303548900761 × <sd> ]

95% confidence interval of Perft(16) after 1 125 runs:
[ 65 069 225 156 643 592 417 223 ,
  65 069 550 400 274 919 421 543 ]

99% confidence interval of Perft(16) after 1 125 runs:
[ 65 069 174 057 165 657 416 504 ,
  65 069 601 499 752 854 422 262 ]

Total CPU time after 1 125 runs: Σ(tᵢ) = 42 755 300.13 seconds (494d 20h 28' 20"13).
                                 ⁱ

That is, more than 8.75 million iterations up to now in almost 500 days of CPU time! The current estimate up to 20,791,294,583,672 nodes [almost 2.08e+13 nodes; these nodes are internal nodes by GNU, so they must not be understood as a fraction of Perft(16)] is:

Code: Select all

 <m> ~ 65069387778459255919383
<sd> ~       82971838741039268

Perft(16) should start with 65069..., so the old estimate I wrote above looks really good. My intention was to share this experiment once I could discard numbers 1 and 6 with 99% confidence in the sixth digit of Perft(16) because few more can be done with current resources (a kind of hitting a wall), but I have been short for a few weeks. This project can be extended sine die until the computation of Perft(16) or loss of interest, though I prefer to wait and see the immediate future of TalkChess to make a decision.

Regards from Spain.

Ajedrecista.

[Uri Blass]

Hello:

The end of this great forum as we know is near. I hope and wish that some members finally achieve the transition to a new server and all topics can be saved. Thanks to everybody that make this forum that great.

I started posting in this forum many years ago with an estimate of Perft(13) and just in case something goes wrong, I want that one of my last posts in the current forum to be about the same, other perft estimate. Here I go:

There is at least one Perft(16) estimate that is very good and can be found at other site: 6.507e+22. It is dated before I registered into TalkChess. I wondered how much could be improved, so I have been running MC samples of Perft(16) of the starting position for two and a half years more less, with GNU 5.50 x64 running in the background. I had not said anything before in the spirit of a secret war or a secret mission in order to get narrower and narrower intervals before posting anything, but the end of the current TalkChess forum has prompted me to share my results as they are right now.

Here is a typical output of GNU 5.50 x64 with the command perftmc 16:

Code: Select all

perftmc 16
m=6.518181e+022 sd=2.875989e+020 ci(99%)=[6.444096e+022,6.592267e+022] n=4750894 sdn=6.268663e+023 t=12.53s
m=6.507558e+022 sd=1.971200e+020 ci(99%)=[6.456780e+022,6.558336e+022] n=7126351 sdn=5.262162e+023 t=19.12s
m=6.505622e+022 sd=1.407234e+020 ci(99%)=[6.469371e+022,6.541872e+022] n=9501734 sdn=4.337782e+023 t=25.39s
[...]

The first line is the average after two iterations, then each line averages one more iteration. The meanings of the abbreviations are:

Code: Select all

m       := arithmetic mean
sd      := standard deviation (formula dividing by the number of iterations)
ci(99%) := 99% confidence interval
n       := nodes
sdn      = sd·sqrt(n)  // sdn is a measure of efficiency, less is better.
t       := time

Since each run is single threaded, I took advantage of multi-threaded CPUs and ran few runs simultaneously each time. I have been copying the full logs of each run as backup (almost 959 MB in total right now!), then taking into account the last line of each run to average in a similar fashion of other attempt by mine with Perft(15).

My best run in terms of lowest standard deviation up to now was this one:

Code: Select all

[...]
m=6.507024e+022 sd=9.432087e+017 ci(99%)=[6.506781e+022,6.507267e+022] n=1617983415 sdn=3.779099e+023 t=280802.70s

Interrupted!

Here is a summary of my long-term project:

Code: Select all

m=

Each occurrence is one iteration except the first one, where there are two. So there must be added 1 in each run:

{Runᵢ} ——> Iterationsᵢ = Occurrencesᵢ + 1

Total number of iterations after 1 125 runs: Σ(Iterationsᵢ) = 8 752 634
                                             ⁱ
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
Runᵢ	Iterationsᵢ

‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
0001	 9375
0002	22178
0003	22169
0004	22160
0005	22139
0006	 5345
0007	 5344
[...]
1116	 7403
1117	 7404
1118	 7346
1119	 7417
1120	 7422
1121	 6726
1122	 6714
1123	 6726
1124	 6728
1125	 6735

Code: Select all

__________________________________________________
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
Perft(16) Montecarlo estimates using GNU 5.50 x64.
__________________________________________________
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
Average Montecarlo estimates like averaging normal distributions with nodes as the weight factor := ωᵢ = (nᵢ) / [Σ(nᵢ)]
                                                                                                                 ⁱ
Nodes are counted with 32-bit integers and overflows happen. To get the correct number of nodes from the incorrect output n*ᵢ:
  n*ᵢ = [ (nᵢ - 2³¹) mod 2³² ] - 2³¹ ; (nᵢ - 2³¹) mod 2³² = 2³¹ + n*ᵢ
  sdnᵢ = sdᵢ × sqrt(nᵢ) ; nᵢ = [ (sdnᵢ) / (sdᵢ) ]²
  k = round[ (nᵢ - n*ᵢ) / 2³² ]
  nᵢ = k × 2³² + n*ᵢ
  nᵢ = ( round{ [ (sdnᵢ) / (sdᵢ) ]² - n*ᵢ } / 2³² ) × 2³² + n*ᵢ
                _
Average mean := m ≡ <m> = Σ(ωᵢ × mᵢ) = [ Σ(nᵢ × mᵢ) ] / [ Σ(nᵢ) ]
                          ⁱ   __         ⁱ                ⁱ
Average standard deviation := sd ≡ <sd> = sqrt{ Σ[(ωᵢ × sdᵢ)²] } = sqrt( { Σ[(nᵢ × sdᵢ)²] } / [Σ(nᵢ)]² ) = ( sqrt{ Σ[(nᵢ × sdᵢ)²] } ) / Σ(nᵢ)
                                                ⁱ                          ⁱ                   ⁱ                   ⁱ                    ⁱ
  Two ways to compute Σ[(nᵢ × sdᵢ)²] :
                      ⁱ
    a) Σ[(nᵢ × sdᵢ)²] = Σ[(nᵢ)² × (sdᵢ)²]
       ⁱ                ⁱ
    b) sdnᵢ = sdᵢ × sqrt(nᵢ) ; (sdnᵢ)² = (sdᵢ)² × nᵢ ; Σ[(nᵢ × sdᵢ)²] = Σ[nᵢ × (sdnᵢ)²]
                                                       ⁱ                ⁱ
  Option a) is chosen.

Solving z₉₅ and z₉₉ in:
  erf[ z₉₅ / sqrt(2) ] = 0.95 (95% confidence level in a normal distribution).
  erf[ z₉₉ / sqrt(2) ] = 0.99 (99% confidence level in a normal distribution).
    z₉₅ ≈ 1.959963984540054236 (rounding up to the 18th decimal at https://oeis.org/A220510 'Decimal expansion of the standard normal deviate for a 95% confidence interval').
    z₉₉ ≈ 2.575829303548900761 (rounding up to the 18th decimal at https://oeis.org/A329283 'Decimal expansion of the quantile z_0.995 of the standard normal distribution').
      <m> ± z₉₅ × <sd> ∈ [ <m> - 1.959963984540054236 × <sd> , <m> + 1.959963984540054236 × <sd> ]
      <m> ± z₉₉ × <sd> ∈ [ <m> - 2.575829303548900761 × <sd> , <m> + 2.575829303548900761 × <sd> ]

95% confidence interval of Perft(16) after 1 125 runs:
[ 65 069 225 156 643 592 417 223 ,
  65 069 550 400 274 919 421 543 ]

99% confidence interval of Perft(16) after 1 125 runs:
[ 65 069 174 057 165 657 416 504 ,
  65 069 601 499 752 854 422 262 ]

Total CPU time after 1 125 runs: Σ(tᵢ) = 42 755 300.13 seconds (494d 20h 28' 20"13).
                                 ⁱ

That is, more than 8.75 million iterations up to now in almost 500 days of CPU time! The current estimate up to 20,791,294,583,672 nodes [almost 2.08e+13 nodes; these nodes are internal nodes by GNU, so they must not be understood as a fraction of Perft(16)] is:

Code: Select all

 <m> ~ 65069387778459255919383
<sd> ~       82971838741039268

Perft(16) should start with 65069..., so the old estimate I wrote above looks really good. My intention was to share this experiment once I could discard numbers 1 and 6 with 99% confidence in the sixth digit of Perft(16) because few more can be done with current resources (a kind of hitting a wall), but I have been short for a few weeks. This project can be extended sine die until the computation of Perft(16) or loss of interest, though I prefer to wait and see the immediate future of TalkChess to make a decision.

Regards from Spain.

Ajedrecista.

I guess it is possible to calculate exact value of perft(16) by calculating the sum of perft(11) of all the positions that appear after 11 plies

I found by google search that there are exactly 726155461002 positions and now you only need to calculate perft(5) in everyone of them and multiply by the number of times the position appear and add the numbers(I do not have the list of position and the number of times they appear but I guess somebody already stored them in the big memory of his computer(otherwise I see no way people know the number).

https://oeis.org/search?q=chess+positio ... &go=Search

If we take relatively easy job of calculating perft(5) and multiplying it by the number of cases the position can appear after 11 plies then we have 726155461002 easy jobs when everyone of them can take clearly less than 0.1 seconds.
if 10^6 computers work on the problem when everyone of them solve many easy jobs in one second then you may need less than a day to find the exact number.

If it is only 10^3 computers work about the problem it is still something that should take order of time of one year.

[Ajedrecista]

Hello:

I am continuing the project. There are 1.31 GB of logs right now.

The best run in terms of lowest standard deviation was improved:

Code: Select all

[...]
m=6.507017e+022 sd=8.775981e+017 ci(99%)=[6.506791e+022,6.507244e+022] n=-288217203 sdn=3.768519e+023 t=392400.32s

Interrupted!

Here is a summary of my long-term project:

Code: Select all

Total number of iterations after 1 415 runs: Σ(Iterationsᵢ) = 12 289 001
                                             ⁱ
‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
Runᵢ	Iterationsᵢ

‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾
0001	 9375
0002	22178
0003	22169
0004	22160
0005	22139
0006	 5345
0007	 5344
[...]
1406	 7500
1407	 7535
1408	 7549
1409	 7488
1410	 7455
1411	 5756
1412	 5759
1413	 5729
1414	 5758
1415	 5732

Code: Select all

95% confidence interval of Perft(16) after 1 415 runs:
[ 65 069 198 831 749 156 588 367 ,
  65 069 473 281 804 313 262 041 ]

99% confidence interval of Perft(16) after 1 415 runs:
[ 65 069 155 712 520 409 452 646 ,
  65 069 516 401 033 060 397 762 ]

Total CPU time after 1 415 runs: Σ(tᵢ) = 59 403 433.03 seconds (687d 12h 57' 13"03).
                                 ⁱ

That is, almost 12.3 million iterations up to now in almost 100 weeks of CPU time. The current estimate is:

Code: Select all

 <m> ~ 65069336056776734925204
<sd> ~       70014055697324206

So, the milestone that has almost been reached is getting a standard deviation below 7e+16, hence the update of this thread. Getting a standard deviation of circa a millionth of the Perft(16) estimate would take around (14,229,000 ± 1,500) iterations according to my calculations, that is, (1.94 ± 0.0015) million iterations more than now... still a long way to go.

Regards from Spain.

Ajedrecista.