Perft(13) betting pool

[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).

[Daniel Shawul]

I am surprized by the efficiency of this method, and now I have no doubt the first 3 significant digits will be 1.98. I think the fact that perft is full width and most of the moves will almost always have equal number of replies means, taking one sample may be enough. We can only be so wrong if we have some checking moves in there and one of them is selected.

Your version of the method is like a random walk on the tree in a depth first manner, more like UCT builds its tree. Anyway it seems even one sample approximates the true value to atleast 3 significant digit which is impressive.
I am interested to see how the method performs on a really selective tree such as adding aggressive LMR on top of perft.

[petero2]

Yes, the idea really is simple but I made it look complicated with all the fancy notation I made up trying to be stringent. Maybe a simplified stringent proof could be made utilizing the fact that E(X+Y)=E(X)+E(Y) even if X and Y are not statistically independent.

[petero2]

I am surprized by the efficiency of this method, and now I have no doubt the first 3 significant digits will be 1.98. I think the fact that perft is full width and most of the moves will almost always have equal number of replies means, taking one sample may be enough. We can only be so wrong if we have some checking moves in there and one of them is selected.

I also think the reason the method is efficient is because the branching factor doesn't vary too much between different parts of the tree.

The method should give an unbiased estimate regardless of the shape of the search tree, but that doesn't mean the method has to be useful in practice. As an extreme example, imagine a tree that is equal to the perft(13) tree, except that one node at ply 12 has 1e100 children. In order to get an accurate estimate, you would have to sample this node several times, which means that the total number of samples needs to be several times larger than perft(12).

Your version of the method is like a random walk on the tree in a depth first manner, more like UCT builds its tree. Anyway it seems even one sample approximates the true value to atleast 3 significant digit which is impressive.

Actually, "one sample" is perft(3)=8902 random walks because of the 3 ply full width search. One such sample has standard deviation 2.5e16, so the standard deviation for a single random walk should be 2.5e16*sqrt(8902), which is about same size as perft(13).

The reason my final estimate for the standard deviation is so small is because I let the program run in the background for several hours. I collected 180000 samples which corresponds to 1.6e9 random walks.

I am interested to see how the method performs on a really selective tree such as adding aggressive LMR on top of perft.

It performs significantly worse. I modified my perft function so that it does LMR with the reduction equal to the move number. This means the first move is searched to full depth, the second move is reduced by one, the third move is reduced by two, etc.

I then computed perftLMR(20) exactly (which turned out to be 10720569 with the move ordering given by my move generator), then tried to estimate it using my random walk method. After collecting 3.7e6 samples, the estimate is still almost 30% too low.

[Daniel Shawul]

I also think the reason the method is efficient is because the branching factor doesn't vary too much between different parts of the tree.

Agreed.

The method should give an unbiased estimate regardless of the shape of the search tree, but that doesn't mean the method has to be useful in practice. As an extreme example, imagine a tree that is equal to the perft(13) tree, except that one node at ply 12 has 1e100 children. In order to get an accurate estimate, you would have to sample this node several times, which means that the total number of samples needs to be several times larger than perft(12).

That is exactly the problem with the montecarlo methods. When I tried a monte-carlo searcher for chess the major problem was captures. If there is one capture out of 20 moves , the capture has to be sampled a number of times for it to be considered. Otherwise it will be swamped by noise causing serious tactical blindness. Perft as it is now seems perfectly suited to monte-carlo approximation because of uniformity of tree, and we are using uniform PRNG.

Btw the method is very practical. I am infact implementing almost the same thing as you do for perft, to search a Hex tree on the gpu. The monte carlo part below ply 3 is done by thread processors in parallel so it is fast. A shallow depth tree of 3 or more on top can be used to take care of some tactical blindness which is typical of monte-carlo methods. I haven't decided if to make this part of the tree static or dynamic yet, but for perft it is obviously static. Dynamic is preferable for search to do more simulations as the search uncovers some knowledge.

Actually, "one sample" is perft(3)=8902 random walks because of the 3 ply full width search. One such sample has standard deviation 2.5e16, so the standard deviation for a single random walk should be 2.5e16*sqrt(8902), which is about same size as perft(13).

The reason my final estimate for the standard deviation is so small is because I let the program run in the background for several hours. I collected 180000 samples which corresponds to 1.6e9 random walks.

Right. But even a one sample estimate (starting from depth 0) gave me 2e18 ! That is very close value I can not come up with EBF methods. Bear in mind the first and second ply are exactly predicted because we have 20 replies for all of the moves. Yes the nodes count below each of the moves will be different , but that is due to difference in tree sampling. You can even get good estimate for game tree complexity for the game of chess (as well as others) using this method.
Btw you should change the long to double to compute large perft values but I guess for perft(13) long is better.

For games like Hex, it should give the exact perft estimate, and for games like Go something very close I think.
Edit: I guess Hex's game tree complexity is easy to calculate 122! I think. Since BF decreases by 1 on every move.

It performs significantly worse. I modified my perft function so that it does LMR with the reduction equal to the move number. This means the first move is searched to full depth, the second move is reduced by one, the third move is reduced by two, etc.

I then computed perftLMR(20) exactly (which turned out to be 10720569 with the move ordering given by my move generator), then tried to estimate it using my random walk method. After collecting 3.7e6 samples, the estimate is still almost 30% too low.

Thanks! That confirms our suspicion. I would think a quasi-monte carlo method with more weight to the leading moves should give better estimate. We can use roulette-wheel selection strategy where the first move takes the largest slot..

regards,