Perft(13) betting pool

[Sven]

My "improved" estimate is now 2.04*10^18 from calculating each move's BF. Doing that for the total nodes searched gave a much lower 1.94*10^14 so I prefer the new estimate. Additional credit for calculating each move's nodes ?:)

Code: Select all

			perft(11)		perft(12)				
	m1	m2	count						
	a2a3	a7a5	2490170591441	a7a5	72665331130084	13.39460522	14.29257911	15.190553	2293277425253770
...

Could you please explain the columns of your table?

Sven

[Daniel Shawul]

Those are perft values after two half plies. I took michael byrne's result of perft 11 and steven's perft 12. Btw the latter are not sorted, each separate file has different move orders so in excel you need to sort the data first.

Code: Select all

first move -> 
second move -> 
perft 11 -> 
2nd move used for sorting -> 
perft 12 -> 
EBF11 = sqrt(perft 11) 
EBF12 = sqrt(perft 12) 
EBF13 = EBF12 + (EBF12 - EBF11) 
EBF13^13 

My EBF13 estimate sounds like an upper bound one because I assumed it will increase by the same amount but as the previous iteration. From past plots I remember it drops down a little every time. I believe it is good to consider only the closest depths though. I may have to add the now obvious odd-even effect later, if I can get similar data for depth 10.

[Sven]

Those are perft values after two half plies. I took michael byrne's result of perft 11 and steven's perft 12. Btw the latter are not sorted, each separate file has different move orders so in excel you need to sort the data first.

Code: Select all

first move -> 
second move -> 
perft 11 -> 
2nd move used for sorting -> 
perft 12 -> 
EBF11 = sqrt(perft 11) 
EBF12 = sqrt(perft 12) 
EBF13 = EBF12 + (EBF12 - EBF11) 
EBF13^13 

My EBF13 estimate sounds like an upper bound one because I assumed it will increase by the same amount but as the previous iteration. From past plots I remember it drops down a little every time. I believe it is good to consider only the closest depths though. I may have to add the now obvious odd-even effect later, if I can get similar data for depth 10.

Thanks. But I don't get the meaning yet for EBF11 and EBF12. You wrote "sqrt(perft 11)" resp. "sqrt(perft 12)", where in fact you do not use "sqrt" but "perft(11) ^ (1/11)" resp. "perft(12) ^ (1/12)". But IMO the perft counts after two plies are in fact perft(9) (for the values taken from M. Byrne) resp. perft(10) (for those from Steven) so shouldn't it be like this?

Code: Select all

EBF9  = perft(9)  ^ (1/9)
EBF10 = perft(10) ^ (1/10)
EBF11 = EBF10 + (EBF10 - EBF9)
estimated_perft(11) = EBF11 ^ 11

and then sum up all 400 values of estimated_perft(11) to get estimated_perft(13)?

The EBF values in your table are too small to match reality, this made me suspicious ...

Sven

[Daniel Shawul]

Right on all counts. The sqrt was a typo. And i should have used 1/9 and 1/10. Thanks!

My bet has changed to 1.934 * 10^18 This is much closer to the previous value I got 1.939 * 10^18 from just the total sums. Well needless to this kind of EBF estimate can not compete with those methods who sample the search tree..

[petero2]

My bet is:

1981075670675789312 (estimated value)
0000059997681255613 (estimated standard deviation)

My method uses N plies of full-width search, then 13-N plies of pruned
search. In the pruned part of the tree I search exactly one child node
for each node. (This seemed to give a lower standard deviation per
time unit than H.G.Muller's method that has a fixed move acceptance
probability if I understood correctly.)

I set N=3, called the search method repeatedly in an infinite loop,
then let it run in the background until I had around 180000 samples.
I finally computed the average and standard deviation of all samples.

The code looks basically like this:

Code: Select all

private final void doPerfTSampled() {
    while (true)
        System.out.printf("%d\n", perfTSampled(13, 3));
}

private final long perfTSampled(int depth, int fullDepth) {
    MoveGen.MoveList moves = moveGen.pseudoLegalMoves(pos);
    MoveGen.removeIllegal(pos, moves);
    if ((depth == 1) || (moves.size == 0))
        return moves.size;
    UndoInfo ui = new UndoInfo();
    if &#40;fullDepth <= 0&#41; &#123;
        int r = rnd.nextInt&#40;moves.size&#41;;
        pos.makeMove&#40;moves.m&#91;r&#93;, ui&#41;;
        long nodes = perfTSampled&#40;depth - 1, fullDepth - 1&#41;;
        pos.unMakeMove&#40;moves.m&#91;r&#93;, ui&#41;;
        return nodes * moves.size;
    &#125; else &#123;
        long nodes = 0;
        for &#40;int mi = 0; mi < moves.size; mi++) &#123;
            pos.makeMove&#40;moves.m&#91;mi&#93;, ui&#41;;
            nodes += perfTSampled&#40;depth - 1, fullDepth - 1&#41;;
            pos.unMakeMove&#40;moves.m&#91;mi&#93;, ui&#41;;
        &#125;
        return nodes;
    &#125;
&#125;

[hgm]

Indeed, I used a fixed acceptance probability (of 1 in 32) for each move independently (using a very lousy PRNG, so the 'independently' should be taken with a grain of salt). In principle that should already produce the correct expectation value (i.e. the true perft multiplied by 1/32 for every level where I do this pruning). But the variance would be dominated by the choice to prune or not, which basically would make the distribution such that you draw 0 with 31/32 probability and the true number with 1/32 probability. That distribution has a pretty large SD. By measuring which fraction of the moves was pruned, the SD could be reduced to the SD in the true number only, because the statistical noise is now only generated by which moves you select, and no longer by whether you select the moves.

It is interesting that our values are outside each other's error bars!

[Uri Blass]

If I understand correctly you accept only one move at every ply after ply 3 and multiply by the number of legal move.

You may be right that it gives an unbiased estimate but we need some proof for it and it does not seem obvious like the case of fixed probability.

Let denote
p(i)=number of legal moves after i-1 plies from the opening positions
p(1)=20 with probability 1
p(2)=20 with probability 1
p(3) is a variable that is independent on p(1) and p(2) but
p(4) is already dependent on p(3)

The question is if we can use these sequences to have an unbiased estimate for perft(13)

E(p(1)*p(2)*p(3)*p(4)...*p(13)) or in the specific case the derived claim is that
sum of perft(3) values of (p(4)*...p(13) for all the possible first 3 plies) is a variable that get expected value of perft(13) and we can use many samples to get a good estimate for the standard deviation of it.

Note that I found that the expected value of the multiplication on a random game is a biased estimate but practically we do not generate a random game by generating random moves and it seems at least based on one example that I tried that it is unbiased estimate but we need to prove it.

[petero2]

Indeed, I used a fixed acceptance probability (of 1 in 32) for each move independently (using a very lousy PRNG, so the 'independently' should be taken with a grain of salt).

I am a bit paranoid when it comes to random number generators, so I used the java SecureRandom class, which is probably massive overkill for this application.

It is interesting that our values are outside each other's error bars!

Indeed, makes the betting more interesting though.

FWIW, this is what I got after 13000 rounds of perft(12, 3):

62854969236701747 (true value according to other sources)
62853427049026968 (estimated value)
00005948504590752 (estimated standard deviation)

[petero2]

If I understand correctly you accept only one move at every ply after ply 3 and multiply by the number of legal move.

You may be right that it gives an unbiased estimate but we need some proof for it and it does not seem obvious like the case of fixed probability.

Here is a proof based on induction over the tree depth.

Define the random variable perfTS(pos,N) = the return value of perfTSampled(N, 0) when
called with initial position pos. Also define pos(m) as the position you get when playing
move m in position pos.

Let perfTS(pos,N) have probability distribution (x(pos,N,i),p(pos,N,i)), meaning that it
can take values x(pos,N,i) with corresponding probabilities p(pos,N,i), where
1<=i<=R(pos,N) and R(pos,N) is the number of possible values of perfTS(pos,N).

According to the definition of expected value, we have:

E(perfTS(pos,N)) = sum(i, x(pos,N,i)*p(pos,N,i))

The claim is that perfTS(pos,N) is an unbiased estimate of perfT(pos,N) for all possible
positions pos and all N > 0, i.e. that E(perfTS(pos,N)) = perfT(pos,N).

First note that for N=1, we have:

E(perfTS(pos,1)) = 1 * s = perfT(pos,1),

where s is the number of legal moves in position pos, because perfTS(pos,1) returns s with
probability 1 in that case. So the claim is true for N=1.

Next, assume that the claim is true for a given N and all positions pos, that is:

E(perfTS(pos,N)) = perfT(pos,N)

Then, for N+1, and a given position pos, let the legal moves be m1,m2,...,ms, where s is
the number of legal moves.

The possible return values of perfTS(pos,N+1) are

s * x(pos(mj),N,i), for 1<=j<=s, and 1<=i<=R(pos(mj),N)

and the corresponding probabilities are

P(selecting move j) * p(pos(mj),N,i))

because the two events are independent if "selecting move j" is performed using a "good
enough" random number generator. Also P(selecting move j)=1/s if the random number
generator is "good enough".

Therefore, according to the definition of expected value, we have:

Code: Select all

E(perfTS(pos,N+1)) = sum({i,j}, s * x(pos(mj),N,i) * 1/s * p(pos(mj),N,i))
   = sum({i,j}, x(pos(mj),N,i) * p(pos(mj),N,i))       (s*1/s=1)
   = sum(j, E(perfTS(pos(mj),N)))                      (sum over i first, use definition of expected value)
   = sum(j, perfT(pos(mj),N))                          (induction hypothesis)
   = perfT(pos,N+1))                                   (definition of perfT)

Since pos was arbitrary, it follows that the claim is true also for N+1, and the proof now
follows from the principle of induction.

[Uri Blass]

thanks.

Did not follow all the notation but I understand the idea that is simple.
In other words:
Let define k=perft(1) in the root position
Let define for 1<=i<=k
p(i)=perft(n-1) after move i

Let define es(i) to be out estimate for perft(n-1) that we assume by induction that it is unbiased.

The method that we have gives a probability of 1/k for k*es(i) and the expected value is the sum of 1/k*k*es(i) that is the sum of es(i) that is the sum of perft(n-1) after 1 ply that is perft(n).