Perft(20)

[Evert]

So here's a question.
There is a notion that mobility in evaluation works because having good mobility means you have many move options, and chances are that one of those will be good (simplified, but I'm sure we've all heard of the idea). Therefore you select at depth 1 the (a) move that leads to the highest mobility after N moves.
Is there any correlation at all between how "good" an opening move is thought to be and the size of the tree below that move?

[smrf]

See the inverse interpolation around perft(13) ...

http://www.talkchess.com/forum/viewtopi ... 47&t=39678

[Ajedrecista]

Hello everybody:

Some people have estimated Perft values for the game of chess up to 20 plies. Here are the links (maybe the list is incomplete):

Labelle (2011?) http://wismuth.com/chess/statistics-games.html
Muller (10th July): http://talkchess.com/forum/viewtopic.ph ... 38&t=39630
Scharnagl (26th July): http://www.talkchess.com/forum/viewtopi ... ht=#416849
Muñoz (4th August): http://talkchess.com/forum/viewtopic.ph ... ht=#418051
Schüle (9th August): http://talkchess.com/forum/viewtopic.ph ... 57&t=39678

The methods that were used for estimating these Perft values are very different from each other. The nice thing is that all these estimates are very similar between them. For example, the most different estimates of Perft(20) are Scharnagl's (the highest) and mine (the lowest), and the difference is slightly over 1% (which is quite small IMO).

It would be interesting that other people (Blass, Hair, Marcel, Österlund, Shawul, Van den Bergh or anyone else) will try their methods to see how they work when estimating Perft values when n > 13 (and post results, please). I took a look on Schüle's estimates and I realise they were very acceptable with very few games (1e+6 games), so there is no need of huge samples of 1e+8 or 1e+9 games (fast estimates seemingly work well).

Good luck and thanks in advance.

Regards from Spain.

Ajedrecista.

[Sven]

It would be interesting that other people (Blass, Hair, Marcel, Österlund, Shawul, Van den Bergh or anyone else) will try their methods to see how they work when estimating Perft values when n > 13 (and post results, please). I took a look on Schüle's estimates and I realise they were very acceptable with very few games (1e+6 games), so there is no need of huge samples of 1e+8 or 1e+9 games (fast estimates seemingly work well).

As to "my" estimates, I did not do much for them, the credit is due to Peter whose method I implemented in my engine.

Furthermore, how do you know that these values are very acceptable, although I did not publish a standard deviation so far?

Well, to satisfy that last condition, here is a current run with the "Peter1" method, depth=20, fw=4 and about 1e8 nodes:

Code: Select all

32 cycles, 101223521 nodes: 8.348876e+028, stddev = 8.933488e+025, time = 0:08:00.15 (480 sec), nps = 210816

The methods recently discussed in the Perft(13) thread will most probably not come to fundamentally different expected values so everything is about precision. To a certain extent, fast estimates may work well but as soon as we want to approach more digits with higher confidence we need much longer runs (or even better methods).

Sven

[Ajedrecista]

Hi Sven:

Thanks for answer so fast. I wrote 'your' estimates because you posted them and you run them (taking your time...) but I give full credit to Peter and his method (which seems very accurate to my eyes).

I also wrote that the estimates seem accurate because the mean values are so close between them; if you know how my laughable method work, you will see that I do not work with standard deviations: I do one estimate using my alpha parameter and I do another estimate using my beta parameter. Then, I take the arithmetic average of both estimates and I have an interval (sometimes alpha gives the maximum and beta the minimum, the rest of times is just the opposite). So my 'method' is... (find a word for it).

I see that you have run another method (Peter1) with more less 1e+8 nodes (great! I like big ammount of nodes for reducing the luck factor... and only in 8 minutes!) and the new estimate comes a little closer to mine (8.3348e+28), from ~ 8.3691e+28 (some hours ago) to ~ 8.3489e+28 (some minutes ago). I hope these estimates are enough close (< 1% error) to true Perft(20) value.

The estimates you posted some hours ago were a little strange and I explain it: the 'odd - even effect' increases and decreases BFs alternatively, but with your values, BFs increase three times in a row if I am not wrong (I think the problem was in Perft(15)/Perft(14) because Perft(14) was a little high (in comparison with other estimates), but IMO this is bad luck due to the short number of games).

I said that there is no need to run long tests (i.e. too much nodes) because I do not want people will waste time with this when Perft(13) is almost here. But of course that longer tests are better. People had advanced so much with their methods since Perft(13) thread was started. This is brilliant! Some people think astonishing methods and other people (for example, myself) think... another ways, maybe too imaginative and no rigurous. But my estimates are close to the rest of estimates and this is enough for me (they are orientative).

Please keep the good work! I appreciate it so much.

Regards from Spain.

Ajedrecista.

[Don]

Steven,

A way to estimate the branching factor is to play random legal moves up to depth N and average them together. You can sample millions of position is a short period of time and probably get a very accurate estimate assuming the RNG is not biased of course.

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]

Steven,

A way to estimate the branching factor is to play random legal moves up to depth N and average them together. You can sample millions of position is a short period of time and probably get a very accurate estimate assuming the RNG is not biased of course.

Hi Don,

see also the thread "Perft(13) betting pool"

Sven