Perft(13) betting pool

[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,

[Daniel Shawul]

Two notes:
I think my 2e18 was a lucky one. With different seeds it got much worse, so I guess the minium acceptable depth where sample are taken is 2.

I tested the roullete wheel selection (since I already had that code for MC) and it seems to be a better predictor than uniform prng as expected.

[petero2]

I think my 2e18 was a lucky one. With different seeds it got much worse, so I guess the minium acceptable depth where sample are taken is 2.

I think your 2e18 was lucky too, but I still think you can use random walk from the first ply. After 5e7 random walks starting from the root node, I got:

1980932313533478912 (estimated value)
0000476479549379638 (estimated standard deviation)

It seems a bit worse than my earlier depth 3 full-width search, but certainly not unusably bad. I suppose in general, a larger full-width depth is preferable, because it will lead to a more uniform sampling of the tree.

I tested the roullete wheel selection (since I already had that code for MC) and it seems to be a better predictor than uniform prng as expected.

What tree did you use for this test? Was it perft with LMR?

[Daniel Shawul]

Yes the 0 ply result doesn't look bad at all.

Yes I used LMR like you did for decreasing every 8th move moves.
I did the same to the move scoring using something like count - i + 1 . My get_random_move takes care of roulette move selection using move scores. Illegal moves if picked would have their scores zeroed out and another pick of a legal move is tried.
I did tests of perft 10 with LMR (about 1.3million nodes) and compared it with the two PRNG versions. The quasi mc gave closer result for a single run (didn't do many of them).

I will see if I can produce with bigger depths.

[Daniel Shawul]

I am having very very bad results with LMR decrement of one every move and depth=20 as you did ?! i don't know why. It differs in order of magnitudes now. Maybe taking many samples will help here but I am using R=3.
I get only good results with LMR reduction of every fourth move or more.

More tommorrow.

[petero2]

Is this with uniform sampling? As I wrote before, my test was 30% wrong even after 3.7e6 samples. The estimated standard deviation was also wrong, so the difference between estimation and truth was more than 3 estimated standard deviations.

I think uniform sampling is hopeless for trees with this much imbalance. The probability of randomly walking into the larger sub-trees is just too small.

[Daniel Shawul]

I still had the depth where MC starts at 0 for perft 20 which was the problem. Even taking that to ply 3 did not give satisfactory result so I needed to go to depth 10 full width (i.e with the heavy LMR) to get comparable value for perft 20. It seems also the weights used for the roullette selection have an effect on the performance so that needs to be tuned too.

What happens here is that , if the MC is started at the root, and say the last move is searched then , the amount of nodes searched will be too low. Since the last move will be searched to depth=1 in perft 20. I think that is why I couldn't get good results until I went to depth=10 for the non-MC part.