Perft(13) betting pool

[Ajedrecista]

Hello people:

I have tried my idea with lower plies (n = 9, 11) for seeing if the numbers that I calculate are right or wrong. They are wrong (did anybody doubt it?), but they are wrong in less than 0.3%! First I start with Perft(9) and then Perft(11). Keep in mind that all is made by hand (with the calculator of Windows) except the polynomials and lines, which are made with the priceless help of Excel, so the numbers I post may contain minor errors. Number of plies is denoted by n.

Working with my alpha-beta couple of parameters, one should start with n = 9 because two known points are needed as minimum (in this case n = 5 and n = 7) for adjusting them with a line. Remember that n = 2x + 3:

[Alpha(x)]* = 2.2133 - 0.4176x
[Beta(x)]* = 2.0865 - 0.3721x

[Alpha(n = 9)]* = 0.9605 (the true one is more less 0.891779).
[Beta(n = 9)]* = 0.9702 (the true one is more less 0.876541).

{Perft(9), [alpha(n = 9)]*} ~ 2,445,183,769,160 ~ [true Perft(9)] + 0.2317%
{Perft(9), [beta(n = 9)]*} ~ 2,447,369,337,631 ~ [true Perft(9)] + 0.3213%

Taking the arithmetic average of two values above:

[Perft(9)]* ~ 2,446,276,553,396 ± 0.0447%

The central value of this interval is more less +0.2765% than Perft(9) = 2,439,530,234,167. I think this is a good estimate (only with two known points of alpha, and another two of beta), but [Perft(11)]* gives better results.

For estimating Perft(11): there are now three known points (n = 5, 7, 9). They could be adjust with a quadratic equation. Again: n = 2x +3:

[Alpha(x)]* = 2.1447 - 0.3147x - 0.0343x²
[Beta(x)]* = 1.993 - 0.2318x - 0.0468x²

[Alpha(n = 11)]* = 0.3371 (the true one is more less 0.265031).
[Beta(n = 11)]* = 0.317 (the true one is more less 0.262037).

{Perft(11), [alpha(n = 11)]*} ~ 2,101,085,392,733,300 ~ [true Perft(11)] + 0.1637%
{Perft(11), [beta(n = 11)]*} ~ 2,100,300,175,041,718 ~ [true Perft(11)] + 0.1263%

Taking the arithmetic average of two values above:

[Perft(11)]* ~ 2,100,692,783,887,509 ± 0.0187%

The central value of this interval is more less +0.145% than Perft(11) = 2,097,651,003,696,806. Both range width and relative error (of the central value of the interval respect true perft value) have been reduced from n = 9 to n = 11.

These two examples are almost nothing to conclude something. But it is true that a polynomial of high degree is better for adjusting some points than a polynomial with lower degree (of course in the region of these points, and not out of this region). If my assumption is true (who knows?), I think these reductions respond the fact of increasing the degree of the adjusting polynomial; so for n = 13 my calculations should reduce both range width (true: more less ± 0.013% < ± 0.0187%) and relative error (unknown until Perft(13) value is calculated). IMO if my reasoning is true (something... difficult): (relative error) < 0.145% and Perft(13) may fall inside or outside (surely outside) my given interval (1.980465e+18 ± 0.013%) but by a narrow edge... and my estimate would be a fairly good one... like all estimates I have read here.

You must read my PDF (the second I published, which is the first link to Megaupload in my first post) if you want to understand how I calculate the numbers of this post (and check them if you feel bored). I will try my best (as soon as possible) if someone ask me doubts.

Regards from Spain.

Ajedrecista.

[smrf]

So well, very short:

Perft(13) &#8776; 1,934197e+18

[Sven]

@Sven, can you please modify Knockout and get us results if you don't mind ?

Hi Daniel,

in general I don't mind, of course, but I have to admit that I have not followed the mathematical part of this discussion recently, and do not understand yet the most recent proposal, which would be a requirement for implementing it in my engine.

Also I will not be able to do any attempt of implementation until Monday evening or even Tuesday, since my PC @home currently has not much more installed than an OS and a web browser ...

I'll try to get in sync again as soon as possible. Maybe someone can summarize for me what exactly should be implemented.

Sven

[Daniel Shawul]

Hi Sven
The changes are simple. Right now the perft is estimated by

Code: Select all

Perft(N) = (legal_games / Total_games) * U(1) * U(2) *.... * U(N)

So only one count of legal games is kept. The required change is to have this count for each ply separately. So we have legal_games[N] which holds counts of games which finish at each ply. Then perft will be something like

Code: Select all

Perft(N) = (legal_games[1] / Total_games) * U(1)
             + (legal_games[2] / Total_games) * U(1) * U(2) +
             + (legal_games[3] / Total_games) * U(1) * U(2) * U(3) +
               ......
             + (legal_games[N] / Total_games) * U(1) * U(2) *....*U(N)
Or
            = Sum((legal_games[k]/Toal_games) * Product(U(i)),i = 1...k),k = 1 ..N)

If you see the example I gave before,the perft value is off by 240 with 8 short games at the root. Even one short game there can overestimate the perft by 20, so this is probably why the current scheme game slightly large value than expected 1.981e18. The existing method is also biased and may never reach the true value with any number of games.

cheers

[Michel]

Perft(N) = (legal_games / Total_games) * U(1) * U(2) *.... * U(N)

I am confused now. I thought the method was

Perf(N)=average of (BF(1)*....*BF(N))

where the average is over random games and BF(i)=1 if the game has ended at ply i.

The random games are selected by generating a full tree of depth <=n for
some n<=N and then uniformly sampling at each deeper ply.

Edit:

Actually the correct formula is


Perf(N)=average of (sum BF(n+1)*....*BF(N))

where the sum is over the games in the full tree of depth <=n.

[Daniel Shawul]

Uri's method is similar (if not the same) as Peter's method with this modification. Only difference is the first one constructs a bigger game tree with the BFs at each ply set to the same value i.e upper bound U(i). Then for tip nodes you give a reward of U(1) * U(2)... U(i), and for illegal routes a reward of 0. The uniformity at each ply makes the probablity of the a move the same i.e 1 / U(i).

For my previous example

R1 = U(1) = 10
R2 = U(1) * U(2) = 10 * 3 = 30
R3 = U(1) * U(2) * U(3) = 10 * 3 * 10 = 300
and
Rillegal = 0

Now for the probabilities which finish at each ply

P1 = 1/10
P2 = 1/10 * 1/3 = 1/30
P3 = 1/10 * 1/3 * 1/10 = 1/300

So when you multiply P and R , you get 1 as does Peter's method does the only difference being the latter gets it differently. It uses legal game tree, so it probably converges faster but I don't see a difference other than that. I think all monte-carlo methods we have are all the same and work in a similar manner.

[Daniel Shawul]

That is Peter's method. Uri's method works differently. First he determines upper bounds of BF for each ply, then determines an upper bound perft estimate by U(1) * U(2) .... * U(N). Then he plays games by generating them using random number 1 < g < U(i). Now some of them are deemed to be illegal since U (the upper bound) will definately exceed some of the BF at each ply. So the illegal game count to total games ratio is an estimate by how much the upper bound should be reduced. So when you multiply by that ratio it gives a correct estimate of perft.
I am saying that there is no single upper bound when some games finish earlier than the max perft depth, in which case they will be over-rewarded. That is why I think Uri's estimate gives a slightly larger value. And the equivalence can be proven too, only difference being Peter's method plays on a legal game tree, and Uri's on an illegal game tree (where some illegal moves are introduced to make the BF the same at each ply).. I have found the simple examples we discussed very helpful.

[Michel]

Ok I understand.

Uri's method is bound to be less efficient (by how much is not clear).

As an extreme example take U(i)=10000.

[Daniel Shawul]

yes but with tighter pre-calculated upper bounds , the number of illegal games can be reduced. I think with the same number of _legal_ games , both methods should give the same result. That is only the case after the modification I suggested, with its current way of counting all legal games it is biased and can give bad results when game ends prematurely.

[Michel]

Yes probably with some care Uri's method can be made to perform similarly as Peter's method.

But why would one go through this trouble, as Peter's method is trivial to implement?

Using a conceptually and practically more complicated method would only make sense if it gave some kind of benefit. I don't see this in this case.