Perft(20)

[sje]

In 1945. authors Irving Chernev and Kenneth Harkness wrote An Invitation to Chess, a best selling introductory text. I recall reading it way back in the late 1960s when I was but a young lad and mostly innocent with respect to chess and computers.

In the book, there is a claim for what we would call perft(20). The number given is 169,518,829,100,544,000,000,000,000,000 (ca. 1.7*10^29) which has a suspiciously long string of zeroes. I realized at the time that it must be just an estimate. But how good of an estimate was it?

The mean branching factor for the above is about 28.9 and that seems a bit high to me. We know that perft(13) will be close to 2*10^18 (MBF ca. 25.6). To get to 1.7*10^29, a factor of 8.5*10^10 over seven ply is needed; that's an MBF of ca. 36.42 for each of those remaining ply.

I'll make a guess that the MBF for the unexplored region will be about 32, so my estimate for perft(20) is 7*10^28, less than half the figure given 66 years ago.

[Sven]

My guess is close to yours but about 10% higher: 7.7 * 10^28. I base it upon an extended interpolation which I started and posted in the context of the current perft(13) thread:

Code: Select all

depth                                   perft      BF  deltaBF
    1                                      20
    2                                     400  20.000
    3                                   8,902  22.255
    4                                 197,281  22.161    2.161
    5                               4,865,609  24.663    2.408
    6                             119,060,324  24.470    2.308
    7                           3,195,901,860  26.843    2.179
    8                          84,998,978,956  26.596    2.126
    9                       2,439,530,234,167  28.701    1.858
   10                      69,352,859,712,417  28.429    1.833
   11                   2,097,651,003,696,806  30.246    1.545
   12                  62,854,969,236,701,747  29.964    1.536
   13               1,979,078,380,667,300,000  31.486    1.240
   14              61,737,614,603,214,200,000  31.195    1.231
   15           2,001,643,963,368,810,000,000  32.422    0.935
   16          64,294,429,943,331,100,000,000  32.121    0.926
   17       2,125,069,329,957,430,000,000,000  33.052    0.630
   18      69,577,938,016,677,700,000,000,000  32.741    0.621
   19   2,322,338,741,299,310,000,000,000,000  33.378    0.325
   20  76,769,945,273,531,600,000,000,000,000  33.057    0.316

The interpolation is based on the branching factor increasing in steps of two plies, where the decrease of deltaBF (:= BF(d) - BF(d-2)) seems to converge to about 0.305 (so I took this as an assumption for depth 13 to 20).

The values for depth 1 to 12 are the real ones.

Sven

[Uri Blass]

I think that it is possible to use statistics to calculate a good estimate for perft 20.

first we should have an upper bound for perft 1 for every ply
that we call u(i) for i<=20.

We have u(1)=20 because we always have 20 legal moves in the starting positions
we have u(2)=20 because black has only 20 legal moves in the starting position.

Later we have u(3)>20 because white can have more than 20 legal moves in the third ply and it should be easy to calculate u(3)....u(12) by chess programs and get some estimate for u(13)...u(20) when games with more than u(13)...u(20) moves at ply 13-20 plies practically never happen

After doing all this process we can translate every random sequence of numbers
1<=g(i)<=u(i) to legal game or to not legal game.

Most of these sequences are not going to be legal games because at some point we are going to have g(i)>perft(1) but even if only something near 2/(1000,000) of these sequences are going to be legal games then we can get a good estimate for perft(20) after trying to play 10^9 random games of 20 plies based on the sequence and have success only in 1978 random games and in this case the estimate is going to be
u(1)*u(2)*....u(20)/1978.

With the hardware of today it is easy to play 10^9 random games of 20 plies in an hour(we need only 2*10^10 nodes and I believe with 4 cpu's assuming no evaluation and search it should be easy to get 10^7 nodes per second.

[Sven]

I think that it is possible to use statistics to calculate a good estimate for perft 20.

first we should have an upper bound for perft 1 for every ply
that we call u(i) for i<=20.

We have u(1)=20 because we always have 20 legal moves in the starting positions
we have u(2)=20 because black has only 20 legal moves in the starting position.

Later we have u(3)>20 because white can have more than 20 legal moves in the third ply and it should be easy to calculate u(3)....u(12) by chess programs and get some estimate for u(13)...u(20) when games with more than u(13)...u(20) moves at ply 13-20 plies practically never happen

Nice idea!

I have implemented a new command "uperft" in my engine. So far I get:

Code: Select all

Your move: uperft 7
u[ 1] =  20
u[ 2] =  20
u[ 3] =  31
u[ 4] =  32
u[ 5] =  46
u[ 6] =  48
u[ 7] =  52
time = 0:11:31.24

It takes a while with my pseudo-legal move generator which does not allow to skip making/unmaking moves at the last ply. NPS is around 4.5Mnodes/sec on my machine (using 1 CPU). I could complete "uperft 9" today but would need three days for 10 and three months for 11, which is impossible since I need the PC for other tasks ... So I would need to start estimating already at depth 10, or get the numbers by someone else with better computing power.

After doing all this process we can translate every random sequence of numbers 1<=g(i)<=u(i) to legal game or to not legal game.

Most of these sequences are not going to be legal games because at some point we are going to have g(i)>perft(1) but even if only something near 2/(1000,000) of these sequences are going to be legal games then we can get a good estimate for perft(20) after trying to play 10^9 random games of 20 plies based on the sequence and have success only in 1978 random games and in this case the estimate is going to be
u(1)*u(2)*....u(20)/1978.

With the hardware of today it is easy to play 10^9 random games of 20 plies in an hour(we need only 2*10^10 nodes and I believe with 4 cpu's assuming no evaluation and search it should be easy to get 10^7 nodes per second.

I am going to prepare my engine for this experiment, starting with plies lower than 20 for testing, which will hopefully also need less random games. I'll come back when I have any results.

Sven

[Sven]

Hi Uri,

I do not yet understand your formula for final estimation. With

Code: Select all

u(1)*u(2)*....u(20)/nLegalGames

(where "nLegalGames" is the number of legal games that could be found after playing 10^9 random games, in your example 1978) I get a number that seems to be independent from the number of random games played. But if I play more games then I'll also get a higher "nLegalGames" which changes (reduces) the estimated perft value a lot.

In the meantime I have implemented the code for playing random games in the way described. Based on the "upper bound" values up to depth 7 I now get this:

Code: Select all

Your move: randgame 7 1000
estimated perft(7) after 1000 random games (72 legal) = 632763733
time = 0:00:00.04
Your move: randgame 7 10000
estimated perft(7) after 10000 random games (705 legal) = 64622679
time = 0:00:00.22
Your move: randgame 7 100000
estimated perft(7) after 100000 random games (6998 legal) = 6510287
time = 0:00:01.20
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70193 legal) = 649053
time = 0:00:11.03
Your move: randgame 7 10000000
estimated perft(7) after 10000000 random games (701394 legal) = 64954
time = 0:01:50.20

I can image that 100000 or more games are simply too much in this case and create noise. My intention was only to show how the estimated perft values go down with increasing number of random games.

What am I missing?

Sven

[Sven]

I have implemented a new command "uperft" in my engine. So far I get:

Code: Select all

Your move: uperft 7
...
time = 0:11:31.24

[...] I could complete "uperft 9" today but would need three days for 10 and three months for 11

I somehow mixed the numbers, off by a "negligible" factor of 60

Correction:
Depth 8 would take 5 hours with my program.
Depth 9 would take 6 days.
Depth 10 would take 6 months.
Depth 11 would take 15 years.
Depth 12 would take 450 years.

So I think I need to estimate everything starting with depth 9 to get this preparation step done.

Sven

[Uri Blass]

Hi Uri,

I do not yet understand your formula for final estimation. With

Code: Select all

u(1)*u(2)*....u(20)/nLegalGames

(where "nLegalGames" is the number of legal games that could be found after playing 10^9 random games, in your example 1978) I get a number that seems to be independent from the number of random games played. But if I play more games then I'll also get a higher "nLegalGames" which changes (reduces) the estimated perft value a lot.

In the meantime I have implemented the code for playing random games in the way described. Based on the "upper bound" values up to depth 7 I now get this:

Code: Select all

Your move: randgame 7 1000
estimated perft(7) after 1000 random games (72 legal) = 632763733
time = 0:00:00.04
Your move: randgame 7 10000
estimated perft(7) after 10000 random games (705 legal) = 64622679
time = 0:00:00.22
Your move: randgame 7 100000
estimated perft(7) after 100000 random games (6998 legal) = 6510287
time = 0:00:01.20
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70193 legal) = 649053
time = 0:00:11.03
Your move: randgame 7 10000000
estimated perft(7) after 10000000 random games (701394 legal) = 64954
time = 0:01:50.20

I can image that 100000 or more games are simply too much in this case and create noise. My intention was only to show how the estimated perft values go down with increasing number of random games.

What am I missing?

Sven

There is a misunderstanding about my formula and I see that in the example I did a mistake by dividing by the wrong number.

You start with u(1)*u(2)*....u(20) but you multiply by the percentage of the number of legal game and do not divide by the number of legal games(multiplying by the percentage of the number of legal games is practically multiplying by the number of legal games and dividing by the number of total games(including illegal games).

for perft 7 you have
u[ 1] = 20
u[ 2] = 20
u[ 3] = 31
u[ 4] = 32
u[ 5] = 46
u[ 6] = 48
u[ 7] = 52

20*20*31*32*46*48*52=45558988800 is an upper bound for perft 7 when every legal game can be translated to a sequence but not the opposite.

If you get
701394 legal games out of 10.000.000 then you need to multiply it by
701394/10,000,000 to get perft 7 so you get an estimate of
3195480139 games that is very close to perft 7.

perft(7)=3,195,901,860

[Uri Blass]

I have implemented a new command "uperft" in my engine. So far I get:

Code: Select all

Your move: uperft 7
...
time = 0:11:31.24

[...] I could complete "uperft 9" today but would need three days for 10 and three months for 11

I somehow mixed the numbers, off by a "negligible" factor of 60

Correction:
Depth 8 would take 5 hours with my program.
Depth 9 would take 6 days.
Depth 10 would take 6 months.
Depth 11 would take 15 years.
Depth 12 would take 450 years.

So I think I need to estimate everything starting with depth 9 to get this preparation step done.

Sven

Yes and for estimating it you can play many random games and see the maximal value of perft(1) at every ply.

You can also try not to play not totally random games but play games with a bigger probability for moves that increase mobility of white or a bigger probability for moves that increase mobility of black to get a better estimate for u(i) for big i.

practically I guess that only about 1/1000,000 of the games with 20 plies are going to be legal.

I thought also about something different but I suspect that it does not work.

You can try get an estimate based on a single game based on multiplication of perft(1) and do average of these numbers on many games but I am not sure if you get correct expected number by it and I will think about it.

[Uri Blass]

I think that estimating perft based on a single game and calculating average of estimates on many games does not work.

If I try to think of a simple example of a game with different number of moves at different plies that are not independent then I cannot find example that it is not a good estimate.

if I have a game when the possible sequences are
1,1,1
1,2,1
1,2,2
2,1,1
2,1,2
2,1,3
2,2,1
2,3,1
2,3,2
2,3,3
2,3,4

It means perft(3)=11

my estimates based on the 11 legal games(only the first 2 numbers are relevant for the estimate because perft(1) at the last ply is independent on the last ply)
1,1,1(2*2*1=4)
1,2,1(2*2*2=8)
1,2,2(2*2*2=8)
2,1,1(2*3*3=18)
2,1,2(2*3*3=18)
2,1,3(2*3*3=18)
2,2,1(2*3*1=6)
2,3,1-4(2*3*4=24)
average
(4*1+8*2+18*3+6*1+24*4)/11=(20+54+6+96)/11=176/11

Edit:A more simple example is the case when there is only one legal game of n plies but the players can make many moves at the first plies and different moves than the single game simply finish the game earlier than n plies.
In this case it is clear that the estimate based on the single possible game is going to be clearly higher than 1.

[Sven]

I do not yet understand your formula for final estimation. With

Code: Select all

u(1)*u(2)*....u(20)/nLegalGames

...

There is a misunderstanding about my formula and I see that in the example I did a mistake by dividing by the wrong number.

You start with u(1)*u(2)*....u(20) but you multiply by the percentage of the number of legal game and do not divide by the number of legal games(multiplying by the percentage of the number of legal games is practically multiplying by the number of legal games and dividing by the number of total games(including illegal games).
[...]
perft(7)=3,195,901,860

Now this makes perfectly sense. After changing the formula I get reasonable results which are on average only 0.2% above the real value:

Code: Select all

Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70272 legal) = 3201521260
time = 0:00:10.97
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70392 legal) = 3206988339
time = 0:00:10.94
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70293 legal) = 3202477999
time = 0:00:10.96
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70224 legal) = 3199334429
time = 0:00:10.97
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70572 legal) = 3215188957
time = 0:00:10.99
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70537 legal) = 3213594392
time = 0:00:10.97
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70221 legal) = 3199197752
time = 0:00:10.98
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (69986 legal) = 3188491390
time = 0:00:10.97
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70244 legal) = 3200245609
time = 0:00:10.96
Your move: randgame 7 1000000
estimated perft(7) after 1000000 random games (70131 legal) = 3195097443
time = 0:00:10.99

Sven