Perft(13) betting pool

[Sven]

I am bit lost. Is it now settled which method is better?

The UCT type methods give a StdDev of about 4e12 for Perft(12) for 100e6 random walks it seems. But a random walk is 12 nodes.

Is that correct? If I understand the method correctly then I think it is a bit less than that. A random walk within the selective part is (12 - fullDepth) nodes and in the end you add (1 + sum(i=1..fullDepth) (perft(i))) per walk from the root to the overall node count. Would you agree?

So a cost of

4e12 * sqrt(12 * 100e6)=1.4e17

The data posted by HGM for 5 ply fullwith 500e6 nodes search seems to give a StdDev of 0.012% which comes down to 7.5e12. So a total cost of

7.5e12*sqrt(500e6)=1.7e17

So in this case UCT seems somewhat better. At the cost of a much more complex implementation however.

EDIT:

I am assuming that in HGM's date "nodes" means all nodes visited. Not just leaf nodes.

If we do the count with leaf nodes then UCT is much farther ahead but this is probably unfair as one should really count the number of move generation
calls and not the number of leaf nodes.

I understand it the same way, based on the pseudo code snippet HGM gave where he increments his "nodes" counter unconditionally at the beginning of each node.

As to your comparison of costs: shouldn't we only compare data having the same number of visited nodes?

Sven

[hgm]

Indeed, I count the number of nodes visited. (The number of times I run the move generator, to be exact.) Note that the 0.012% error was for the 5-ply full-width method, for which I had a reasonably accurate empirical value for the standard deviation, based on 25 samples. The standard deviation for the 6-ply full-width should be smaller, but is completely unknown, as I just did a single sample.

I guess it should not be so difficult to calculate the variances based on tree statistics, though:

Suppose I only did pruning at the 7th ply, and a complete full-width perft for each accepted move. The variance of a single draw in that case would simply be the variance of the sizes of the perft(5) subtrees starting at the 7-th ply. These can be estimated on a random sample of these 5-ply sub-trees,which can be obtained through the described process by using a very low ' transmission probability' at ply 7 (e.g. 1 in 4million, to select about 1000 of the 3.9 billion perft(7) positions, and calculate their variance).

Now in my method I also prune in later levels. But it can be calculated how much the variance would be based on 3.9G/32 samples if I had perfted all these subtrees exactly. Now compared to that 'though experiment' with a fixed set of accepted moves at ply 7, I start pruning at ply 8. This perturbs my originally drawn value with a variance given by the size of the perft(4) sub-trees of my drawn perft(5) sub-trees. There is no reason to suspect this will be significantly different from the total set of perft(4) sub-trees in the perft(12) tree. I can calculate the latter the same way as at ply 7, by 1 in 100M pruning at ply 8 (and on no other ply), etc. As the drawing of ply-8 nodes from the selected set is independent from the draw that selected the set, the variances should simply add. This can be continued up to ply 11 (the last selective ply).

[Michel]

If I understand the method correctly then I think it is a bit less than that. A random walk within the selective part is (12 - fullDepth) nodes and in the end you add (1 + sum(i=1..fullDepth) (perft(i))) per walk from the root to the overall node count. Would you agree?

Yes I agree. But in the UCT approach I think people have been using fullDepth=0.
The idea is that fullDepth>0 is more or less equivalent to a uniform MC search for
fullDepth plies and the idea was precisely to do non uniform searches close to the root.

But perhaps this reasoning was flawed. As HGM's method shows. You can do fullDepth>0 searches and still be non uniform (by pruning more heavily higher in the tree).

As to your comparison of costs: shouldn't we only compare data having the same number of visited nodes?

No. The correct measure is variance*(nodes visited). Or equivalently sd*sqrt(nodes visited).

The idea is that if you do an experiment twice and take the average of the results, you halve the variance but double the work. So the product variance*work remains
the same.

Of course in the perft case if you have a large amount of time then you can
do a full tree search and reduce the variance to zero. So variance*(nodes visited)=0.
This means that one should not be too extreme in comparing methods with different
node counts.

[Sven]

If I understand the method correctly then I think it is a bit less than that. A random walk within the selective part is (12 - fullDepth) nodes and in the end you add (1 + sum(i=1..fullDepth) (perft(i))) per walk from the root to the overall node count. Would you agree?

Yes I agree. But in the UCT approach I think people have been using fullDepth=0. The idea is that fullDepth>0 is more or less equivalent to a uniform MC search for fullDepth plies and the idea was precisely to do non uniform searches close to the root.

But perhaps this reasoning was flawed. As HGM's method shows. You can do fullDepth>0 searches and still be non uniform (by pruning more heavily higher in the tree).

I do not know UCT in enough details to argue with you. But doesn't UCT, as a special form of MC tree search, include to build up a tree of nodes close to the root (selection + expansion steps of MC) and do random walks only from the leaves of that tree (simulation + backpropagation steps)? The term "fullDepth" surely does not apply there but still the length of each single random walk is not the full length from root to leaf IMO. Or am I completely wrong here?

This is only important to validate your calculation of the total number of nodes which in turn influences the costs calculation, and therefore we should not struggle too much about it. Of course one could add an explicit counter of visited nodes like HGM has it, and voilà! we have the answer

As to your comparison of costs: shouldn't we only compare data having the same number of visited nodes?

No. The correct measure is variance*(nodes visited). Or equivalently sd*sqrt(nodes visited).

Which means that from two results with same number of nodes the one with the lower variance has the lower costs But of course you are right, my proposal is no improvement, although it is not wrong (and can simplify the comparison).

The idea is that if you do an experiment twice and take the average of the results, you halve the variance but double the work. So the product variance*work remains the same.

Correct. Provided you already did the experiment more than once before, since otherwise the variance was zero and won't be halved ...

Of course in the perft case if you have a large amount of time then you can do a full tree search and reduce the variance to zero. So variance*(nodes visited)=0. This means that one should not be too extreme in comparing methods with different node counts.

I don't think that anyone should compare results of selective and non-selective "experiments" under the aspect of costs.

Sven

[Daniel Shawul]

@Michel
That explains the confusion! I believed HG when he said he counted leaf nodes but he actually counts all nodes as is shown in his code. Anyway it seems UCT does perform better. Also bear in mind the two method's are _complementary_. There is absolutely no need to use uniform full width search.

[Sven]

@Michel
That explains the confusion! I believed HG when he said he counted leaf nodes but he actually counts all nodes as is shown in his code. Anyway it seems UCT does perform better. Also bear in mind the two method's are _complementary_. There is absolutely no need to use uniform full width search.

To be even more precise: HG counts both, the number of visited nodes ("nodes" in his code snippet) and the number of leaves ("count"), where the latter is for the final perft estimate and the former for tracking how long to run (if a constant node count is given as input) and for later costs calculation.

Sven

[hgm]

@Michel
That explains the confusion! I believed HG when he said he counted leaf nodes but he actually counts all nodes as is shown in his code. Anyway it seems UCT does perform better. Also bear in mind the two method's are _complementary_. There is absolutely no need to use uniform full width search.

You misread me: I said that qperft counts in the leaves. As any perft should, or it would not return the correct perft value. But in the same post I said that for an efficiency measurement we should count move generations,which I defined as 'nodes'.

[Daniel Shawul]

@Michel
That explains the confusion! I believed HG when he said he counted leaf nodes but he actually counts all nodes as is shown in his code. Anyway it seems UCT does perform better. Also bear in mind the two method's are _complementary_. There is absolutely no need to use uniform full width search.

You misread me: I said that qperft counts in the leaves. As any perft should, or it would not return the correct perft value. But in the same post I said that for an efficiency measurement we should count move generations,which I defined as 'nodes'.

You also said this "I just have a global counter that counts leave nodes: ". Then I assumed your nodes are leaf nodes counts. Michel also got confused..

[Michel]

Michel also got confused..

Well not really. The meaning of "nodes" is quite standard in computer chess. I just wanted to be absolutely sure. That's why I asked.

I should have read back the relevant post where it is unambiguously stated that nodes refer to move generations. I had overlooked it.

[Daniel Shawul]

Michel also got confused..

Well not really. The meaning of "nodes" is quite standard in computer chess. I just wanted to be absolutely sure. That's why I asked.

I should have read back the relevant post where it is unambiguously stated that nodes refer to move generations. I had overlooked it.

Well I already stated my confusion earlier than you did but got no reply... I tried to compare the values directly with a 500 mil number of simulation result and found out it lies somewhere in the 4-ply and 5-ply result. HG did not correct me until your post today.. Yes we all understand what is going on now obviously.