Perft(13) betting pool

[Daniel Shawul]

I am sorry if we got lost in the discussion but believe me but it is not deliberate. Ofcourse I read your posts , maybe the fact that I don't usually quote is causing a confusion. So lets discuss them point by point to avoid any confusion.

I think this cannot be. Unless of course you reuse the data 200 125 100 50 25.
After having generated the proportions from it you should discard this data
(but you can keep an estimate generated from it, please read my post).

You say this can not be but what happens is the following. If I compute the weights from the same sequence and do that only at the root it is still unbiased. And if do it in 2-ply , 3-ply searches it becomes "visibly" more and more biased. This is a fact I can prove by running experiments. Peter also observed something similar.
So do we agree the problem is there if summation is done elsewhere other than the root? At least that is what I observed, maybe the bias is small to see when summation is done at the root? Are you saying the bias is still there if I reuse the data even at the root?

EDIT:
On second thought I think you were being very unfair to me when you discard the points I am trying to make. Well you also had confusions with my proportions and weights right? I was _honestly_ (can't stress enough) trying to understand what is happening, but if we are mis-communicating well it is better to stop it. Anyway both methods are practically unbiased so there is no issue. Just that I don't understand (you seem to understand it) doesn't mean anything. Lets move on with other tests, no hard feelings.

[Daniel Shawul]

Stopped after 2e9 iterations

Code: Select all

3-ply: 6.284980e+016 +- 7.337394e+012  6.292152e+016 +- 3.931730e+013 500232079  cost 1.64e17
4-ply: 6.284581e+016 +- 5.480793e+012  6.272345e+016 +- 3.058148e+013 500916944  cost 1.23e17
5-ply: 6.284583e+016 +- 3.867508e+012  6.107216e+016 +- 2.145204e+013 501118477  cost 8.63e16
5-ply: 6.285042e+016 +- 2.046972e+012  6.236905e+016 +- 1.170725e+013 2000938052 cost 9.15e16

[Michel]

Lets move on with other tests, no hard feelings.

Ok. Sorry. I do not know what you do in internal nodes so I cannot comment
on that. I am sure that you are simply using data you are not allowed to use.

EDIT: An of course your latest method performs very well!

[Michel]

@Peter

It may be possible to make something like this work, but you have to be careful not to introduce bias. As a very simplified example, suppose you try to estimate the mean of a random variable that is normally distributed with mean 0 and standard deviation 1. If your algorithm takes a number of samples, but for each positive sample, it decides to get "a second opinion" and use the average of the original value and the "second opinion",

I thought a lot about this example. I noticed there are slight variations of it which _are unbiased_.

Example. Assume X1,X2,X3 are independent estimators for x. We construct a new random variable Y as follows.

If X1<=0 take Y=(1/2)(X1+X2)
If X1>0 take Y=(1/2)(X1+(1/2)(X2+X3))

Then Y is an unbiased estimator for x as well.

Notice that this is almost the same as your example. Instead of taking 0 or
1 "second opinions", we take 1 or 2.

This means one does not have to discard X1 if one uses it to further
guide the search. One just has to be careful to introduce a new estimator
(the part involving X2, X3) which is independent of X1 and unbiased for
all possible values of X1.

[petero2]

@Peter

It may be possible to make something like this work, but you have to be careful not to introduce bias. As a very simplified example, suppose you try to estimate the mean of a random variable that is normally distributed with mean 0 and standard deviation 1. If your algorithm takes a number of samples, but for each positive sample, it decides to get "a second opinion" and use the average of the original value and the "second opinion",

I thought a lot about this example. I noticed there are slight variations of it which _are unbiased_.

Example. Assume X1,X2,X3 are independent estimators for x. We construct a new random variable Y as follows.

If X1<=0 take Y=(1/2)(X1+X2)
If X1>0 take Y=(1/2)(X1+(1/2)(X2+X3))

Then Y is an unbiased estimator for x as well.

Notice that this is almost the same as your example. Instead of taking 0 or
1 "second opinions", we take 1 or 2.

This means one does not have to discard X1 if one uses it to further
guide the search. One just has to be careful to introduce a new estimator
(the part involving X2, X3) which is independent of X1 and unbiased for
all possible values of X1.

I think the intuitive explanation for why this works is that the weight of X1 in the estimate of Y is the same (1/2) regardless of the sampled value of X1. It is when you do things like "hmm, this sample seems unusually large, let's trust it less" (ie reduce its weight in the final estimate), that you risk introducing bias.

The Peter1 method can be viewed having an infinite pool of random variables to sample from, one random variable for each tree and its weights. The values sampled so far are used to decide which random variable to sample next, but they don't affect the weight of the samples in the final estimate. The weight is always 1/N where N is the total number of samples.

Your example can be viewed as a variation on this theme. Depending on the value of X1, you decide if the next sample is to be taken from X2 or from (X2+X3)/2.

[sje]

The ninth draft 11 record has been generated. The position is:
[d]rnbqkbnr/1ppppppp/8/p7/8/N7/PPPPPPPP/R1BQKBNR w KQkq - 0 2[/d]
The perft(11) for the above: 2,670,298,917,876,179

This is the biggest subtotal so far in the run.

Nine down, 391 to go.

The likely next draft 11 record will be for the position arising after 1 Nc3 a5.

[Michel]

If X1<=0 take Y=(1/2)(X1+X2)
If X1>0 take Y=(1/2)(X1+(1/2)(X2+X3))

This idea may actually work. Look what I get for 3 modified fw=4 500e6 nodes
Peter1 searches.

Code: Select all

mean=6.285189e+16 sd=5.188017e+12 &#91; 6.283852e+16 <= Perft&#40;12&#41; <= 6.286525e+16 &#40;99% conf.) &#93; nodes=502930277 sdn=1.163470e+17 time=1395.86s

mean=6.285737e+16 sd=6.027782e+12 &#91; 6.284185e+16 <= Perft&#40;12&#41; <= 6.287290e+16 &#40;99% conf.) &#93; nodes=502924764 sdn=1.351789e+17 time=1445.19s

mean=6.286008e+16 sd=5.583839e+12 &#91; 6.284569e+16 <= Perft&#40;12&#41; <= 6.287446e+16 &#40;99% conf.) &#93; nodes=502927173 sdn=1.252234e+17 time=1586.90s

We learn from this that standard deviations have large standard deviations:-)
Nonetheless it seems reasonable to assume that the modification makes
the method better at zero extra cost.


Here is what I did (credit goes to HGM for suggesting something like this, and also
to Daniel for suggesting to do more complicated things in the leaf nodes of the fw tree).

(*) At a leaf node of the full with tree do 2 uniform Peter style random walks. Call the
values x1 and x2.

(*) If x1<treshold return 0.5*(x1+x2)

if x1>=treshold then do a third random walk. Call the value x3 and return

0.5*(x1+0.5*(x2+x3))

(*) Currently treshold=2*32^(remaining depth) but of course this should be determined dynamically.

[Michel]

Well the behavior of the standard deviation appears to be highly erratic (which adds another headache for those who want to compare methods). More tests are needed. Maybe it does not work after all....

[Michel]

Well after several more runs I am convinced the method does work to some extent. However the indicated treshold value is probably too high (it may have worked because I forgot to include <math.h> resulting in the type of pow being unknown, hence the return values might have been essentially random).

Unfortunately there are many variations possible and the erratic behaviour of the standard deviation makes it very difficult to tune things quickly. I have no time to look further into it.

[Michel]

mean=6.285028e+16 sd=5.964553e+12 [ 6.283492e+16 <= Perft(12) <= 6.286565e+16 (99% conf.) ] nodes=502022637 sdn=1.336409e+17 time=1454.00s

This is a run with treshold=0.1 * 32^(remaining depth).

The unmodified peter1 method typically has 1.40e17<sdn<1.55e17.


sdn=sd*sqrt(moveGen). I call this the "normalized standard deviation".