Perft(20)

[Sven]

Using the method proposed by Uri, so far I have these estimated upper bound values for perft(1) per ply (using another new command "uperftr" of my engine KnockOut):

Code: Select all

Your move: uperftr 16 4000000
u[ 1] =  20
u[ 2] =  20
u[ 3] =  31
u[ 4] =  32
u[ 5] =  46
u[ 6] =  48
u[ 7] =  52
u[ 8] =  53
u[ 9] =  56
u[10] =  55
u[11] =  59
u[12] =  58
u[13] =  63
u[14] =  61
u[15] =  62
u[16] =  60
time = 0:06:11.03

The values up to u[7] are exact, the others are estimated by playing 4 million random games. I will repeat this with a higher number of games some day, and will then also proceed to depth > 16.

Based on these upper bound values I get the following results for the perft(N) estimate applying Uri's method:

Code: Select all

depth                           perft                  estimatedPerft  nRandomGames    dev%
    1                              20                              20     1,000,000   0.00%
    2                             400                             400     1,000,000   0.00%
    3                           8,902                           8,907     1,000,000   0.06%
    4                         197,281                         197,341     1,000,000   0.03%
    5                       4,865,609                       4,865,758     1,000,000   0.00%
    6                     119,060,324                     118,971,166     1,000,000  -0.07%
    7                   3,195,901,860                   3,209,904,114     1,000,000   0.44%
    8                  84,998,978,956                  85,542,969,699     1,000,000   0.64%
    9               2,439,530,234,167               2,432,591,226,863     1,000,000  -0.28%
   10              69,352,859,712,417              69,428,574,036,197     2,000,000   0.11%
   11           2,097,651,003,696,800           2,087,523,969,541,570     2,000,000  -0.48%
   12          62,854,969,236,701,700          63,242,213,290,599,300     2,000,000   0.62%
   13       1,979,078,380,667,300,000       1,997,340,520,734,860,000     8,000,000   0.92%
   14      61,737,614,603,214,200,000      61,805,223,274,842,600,000    16,000,000   0.11%
   15   2,001,643,963,368,810,000,000   1,990,053,614,855,530,000,000    64,000,000  -0.58%
   16  64,294,429,943,331,100,000,000  66,008,877,020,267,700,000,000   128,000,000   2.67%

Column "perft" is the exact perft number as far as known today (up to depth=12, the last two slightly rounded by Excel ), and otherwise a perft number obtained by interpolation (for depth>12). Column "estimatedPerft" contains the estimate based on Uri's method. "dev%" shows how close "estimatedPerft" is to the exact resp. interpolated perft number. My goal up to now was to keep "abs(dev%)" below 1%. For depth=16 I will have to run a lot more random games to achieve this, maybe 512 million games. Therefore I am not sure about the number of 1000 million games assumed by Uri for depth=20 but only testing can show.

As a first summary I think I can already state that the method of Uri works very well, since all known perft numbers for depth <= 12 could be predicted with high confidence and quite low effort. For higher depths I can only say that Uri's method seems to give approximately the same results as my interpolation, which allows no conclusion yet since the real quality of my interpolation is unknown (and will be for another bunch of years).

Sven

[Uri Blass]

common sense suggest that u(15)>u(13) and usually it is possible to increase perft(1) by 2 moves(of course not always and there is an upper bound for perft(1) but I think that at least we have u(i+2)>u(i) for i<20

I also suspect u(i+1)>=u(i) for i<20
so I guess that we have.
u(10)>=56
u(11)>=59
u(12)>=59
u(13)>=63
u(14)>=63
u(15)>=64
u(16)>=64

[Uri Blass]

Using the method proposed by Uri, so far I have these estimated upper bound values for perft(1) per ply (using another new command "uperftr" of my engine KnockOut):

Code: Select all

Your move: uperftr 16 4000000
u[ 1] =  20
u[ 2] =  20
u[ 3] =  31
u[ 4] =  32
u[ 5] =  46
u[ 6] =  48
u[ 7] =  52
u[ 8] =  53
u[ 9] =  56
u[10] =  55
u[11] =  59
u[12] =  58
u[13] =  63
u[14] =  61
u[15] =  62
u[16] =  60
time = 0:06:11.03

The values up to u[7] are exact, the others are estimated by playing 4 million random games. I will repeat this with a higher number of games some day, and will then also proceed to depth > 16.

Based on these upper bound values I get the following results for the perft(N) estimate applying Uri's method:

Code: Select all

depth                           perft                  estimatedPerft  nRandomGames    dev%
    1                              20                              20     1,000,000   0.00%
    2                             400                             400     1,000,000   0.00%
    3                           8,902                           8,907     1,000,000   0.06%
    4                         197,281                         197,341     1,000,000   0.03%
    5                       4,865,609                       4,865,758     1,000,000   0.00%
    6                     119,060,324                     118,971,166     1,000,000  -0.07%
    7                   3,195,901,860                   3,209,904,114     1,000,000   0.44%
    8                  84,998,978,956                  85,542,969,699     1,000,000   0.64%
    9               2,439,530,234,167               2,432,591,226,863     1,000,000  -0.28%
   10              69,352,859,712,417              69,428,574,036,197     2,000,000   0.11%
   11           2,097,651,003,696,800           2,087,523,969,541,570     2,000,000  -0.48%
   12          62,854,969,236,701,700          63,242,213,290,599,300     2,000,000   0.62%
   13       1,979,078,380,667,300,000       1,997,340,520,734,860,000     8,000,000   0.92%
   14      61,737,614,603,214,200,000      61,805,223,274,842,600,000    16,000,000   0.11%
   15   2,001,643,963,368,810,000,000   1,990,053,614,855,530,000,000    64,000,000  -0.58%
   16  64,294,429,943,331,100,000,000  66,008,877,020,267,700,000,000   128,000,000   2.67%

Column "perft" is the exact perft number as far as known today (up to depth=12, the last two slightly rounded by Excel ), and otherwise a perft number obtained by interpolation (for depth>12). Column "estimatedPerft" contains the estimate based on Uri's method. "dev%" shows how close "estimatedPerft" is to the exact resp. interpolated perft number. My goal up to now was to keep "abs(dev%)" below 1%. For depth=16 I will have to run a lot more random games to achieve this, maybe 512 million games. Therefore I am not sure about the number of 1000 million games assumed by Uri for depth=20 but only testing can show.

As a first summary I think I can already state that the method of Uri works very well, since all known perft numbers for depth <= 12 could be predicted with high confidence and quite low effort. For higher depths I can only say that Uri's method seems to give approximately the same results as my interpolation, which allows no conclusion yet since the real quality of my interpolation is unknown (and will be for another bunch of years).

Sven

1)I agree that we probably need more than 1000 million games to achieve error of less than 1% at depth 20.

2)It is also possible that your estimate for perft(16) is more than 1% lower than the real number.

3)If you already play more random games to achieve a small error then I suggest also to play the same number of random games to get a better estimate for u(i).

With smaller values for u(i) we can expect lower estimate values for perft than the real values when the disadvantage of bigger values for u(i) is that bigger values mean that you need more games to get the same number of legal games.

[Uri Blass]

Generally speaking simple statistical calculation suggest that 27225 legal games are going to give you an estimate that is wrong by no more than 1% in at least 95% of the cases(for small n you practically even need less legal games and you always get the correct number for n=1 or n=2 and even for n=3 or n=4 I suspect that you practically need less legal games but it may be interesting to test my theory for n=9-12 when we know real perft).

You can try it for small number of n for perft(n) to see if I am right.

Note that of course you need more games to get 27225 legal games when n is bigger but 128,000,000 games for depth 16 should give you more than 20,000 legal games and I believe that it means error of no more than 1% in more than 90% of the cases but not more than 95% of the cases.

[Sven]

common sense suggest that u(15)>u(13) and usually it is possible to increase perft(1) by 2 moves(of course not always and there is an upper bound for perft(1) but I think that at least we have u(i+2)>u(i) for i<20

I also suspect u(i+1)>=u(i) for i<20
so I guess that we have.
u(10)>=56
u(11)>=59
u(12)>=59
u(13)>=63
u(14)>=63
u(15)>=64
u(16)>=64

But captures reduce the number of available legal moves, so I am not sure about that "common sense".

I will try to repeat these calculations of u(i) with a lot more random games than before, and come back with any new results then.

Sven

[sje]

Google says "About 1,180 results" when searching "169,518,829,100,544,000,000,000,000,000", so that number certainly has gained some traction. A search for "62,854,969,236,701,747" (perft(12)) garners only nine results.

[hgm]

These are my perft estimates upto perft(20):

Code: Select all

hgm@hgm-laptop:~/qperft$ ./fakeperft 20
 - - - - - - - - - - - -
 - - - - - - - - - - - -
 - - r n b q k b n r - -
 - - p p p p p p p p - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - . . . . . . . . - -
 - - P P P P P P P P - -
 - - R N B Q K B N R - -
 - - - - - - - - - - - -
 - - - - - - - - - - - -

Quick Perft by H.G. Muller
Perft mode: No hashing, bulk counting in horizon nodes

perft( 1)=    2.000000e+01 ( 0.000 sec)

perft( 2)=    4.000000e+02 ( 0.000 sec)

perft( 3)=    8.902000e+03 ( 0.000 sec)

perft( 4)=    1.972810e+05 ( 0.010 sec)

perft( 5)=    4.865609e+06 ( 0.290 sec)

perft( 6)=    1.190603e+08 ( 7.180 sec)

perft( 7)= ca.3.193999e+09 (13.210 sec)

perft( 8)= ca.8.497681e+10 (18.110 sec)

perft( 9)= ca.2.440231e+12 (22.470 sec)

perft(10)= ca.6.936332e+13 (26.230 sec)

perft(11)= ca.2.096683e+15 (29.790 sec)

perft(12)= ca.6.297233e+16 (33.130 sec)

perft(13)= ca.1.984510e+18 (36.380 sec)

perft(14)= ca.6.203526e+19 (39.540 sec)

perft(15)= ca.2.019002e+21 (42.860 sec)

perft(16)= ca.6.538556e+22 (46.020 sec)

perft(17)= ca.2.188469e+24 (49.400 sec)

perft(18)= ca.7.250884e+25 (52.850 sec)

perft(19)= ca.2.495931e+27 (56.670 sec)

perft(20)= ca.8.497042e+28 (60.590 sec)

[hgm]

Corrected for actual number of samples:

Code: Select all

perft( 1)=    2.000000e+01 ( 0.000 sec)       -nan
perft( 2)=    4.000000e+02 ( 0.000 sec)   0.000000
perft( 3)=    8.902000e+03 ( 0.000 sec)   0.000000
perft( 4)=    1.972810e+05 ( 0.010 sec)   0.000000
perft( 5)=    4.865609e+06 ( 0.310 sec)   0.000000
perft( 6)=    1.190603e+08 ( 7.480 sec)   0.000000
perft( 7)= ca.3.195750e+09 (17.060 sec)  31.013949
perft( 8)= ca.8.499435e+10 (25.010 sec)  31.018984
perft( 9)= ca.2.439906e+12 (31.880 sec)  30.988370
perft(10)= ca.6.934964e+13 (38.030 sec)  31.017279
perft(11)= ca.2.097701e+15 (43.700 sec)  30.988166
perft(12)= ca.6.287770e+16 (49.080 sec)  31.019958
perft(13)= ca.1.980212e+18 (54.260 sec)  31.030410
perft(14)= ca.6.188925e+19 (59.350 sec)  30.987909
perft(15)= ca.2.018062e+21 (64.460 sec)  30.970333
perft(16)= ca.6.507415e+22 (69.760 sec)  30.990071
perft(17)= ca.2.172185e+24 (74.900 sec)  30.983098
perft(18)= ca.7.215793e+25 (80.520 sec)  30.949616
perft(19)= ca.2.473034e+27 (86.490 sec)  30.943262
perft(20)= ca.8.378534e+28 (92.680 sec)  30.987180

[sje]

When will we see the exact value for perft(20)?

From the time perft(4) was first correctly stated (by a machine; an earlier paper and pencil calculation was slightly off), the approximate release time interval between successive perft values has been about four years. Given that perft(13) should appear in early 2012 and assuming the continued use of only consumer level computers in the effort, we should see perft(20) around the year 2040. That's nearly a century after Chernev and Harkness wrote about the ca. 1.7*10^29 estimate.

Of course, a large scale distributed effort could produce perft(20) much sooner, as could the misappropriation of any of the world's top supercomputers.

[Uri Blass]

When will we see the exact value for perft(20)?

From the time perft(4) was first correctly stated (by a machine; an earlier paper and pencil calculation was slightly off), the approximate release time interval between successive perft values has been about four years. Given that perft(13) should appear in early 2012 and assuming the continued use of only consumer level computers in the effort, we should see perft(20) around the year 2040. That's nearly a century after Chernev and Harkness wrote about the ca. 1.7*10^29 estimate.

Of course, a large scale distributed effort could produce perft(20) much sooner, as could the misappropriation of any of the world's top supercomputers.

I do not know.
The interesting question is what is the number of legal positions after n plies for different n.

That branching factor should become smaller when n is bigger and it means that it is going to take less time to calculate perft(20) assuming that the hardware continue to improve at the same speed.

I think that getting a good approximation for perft(20) number(mistake of less than 1% with high confidence) is relativelty easy today and it is easier than calculating the exact value of perft(13).