Perft(13) betting pool

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Michel
Posts: 1965
Joined: Sun Sep 28, 2008 11:50 pm

Re: Summary of Monte Carlo results for perft(12) so far

Post by Michel » Tue Aug 16, 2011 11:17 am

I use proportioning by sub-tree size. If you use the Peter1 depth-first search it uses proportioning by sub-tree count of the leaf nodes. I haven't yet started to see if other formulas with variance term in it would improve it but I suspect mean proportioning is pretty good too.
Just for the record. As I was saying above. The optimal frequency is proportional to the standard deviation of the estimator used in the leaf node.

But since it might be too expensive to get a good estimation of the standard deviation
(you cannot reuse those searches for perft) using the subtree size is probably a good idea.
Last edited by Michel on Tue Aug 16, 2011 11:20 am, edited 1 time in total.

Michel
Posts: 1965
Joined: Sun Sep 28, 2008 11:50 pm

Re: Summary of Monte Carlo results for perft(12) so far

Post by Michel » Tue Aug 16, 2011 11:19 am

No that is just the result of the second sequence of random numbers which gets dumped in the end. Well to my surprise it gave good values for the 3-ply result but of course it should be ignored since it is biased.
If it carries no information why include it in every table? It only leads to extra (and unnecessary) confusion....

Daniel Shawul
Posts: 3498
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Summary of Monte Carlo results for perft(12) so far

Post by Daniel Shawul » Tue Aug 16, 2011 11:31 am

I believe I have tested proportioning by standard deviation some time ago and it performed worse than proportioning by variance. The test was for a limited 3-ply version which grows the tree at start up. Is your new proposition for my new method here which adds a 1 ply full width? I suspect mean proportioning will be good at earlier iterations since it takes some time to establish good variance / std estimates. I will do some tests with 3-ply to pick up suitable formula ..

Michel
Posts: 1965
Joined: Sun Sep 28, 2008 11:50 pm

Re: Summary of Monte Carlo results for perft(12) so far

Post by Michel » Tue Aug 16, 2011 11:49 am

I believe I have tested proportioning by standard deviation some time ago and it performed worse than proportioning by variance.
Well unless I made a mathematical mistake proportioning by sd is optimal.

Suppose you have constants x1,...,xn and unbiased estimators X1,...,Xn for those.
You want to estimate x1+...+xn.

Let's for simplicity assume that X1,...,Xn are independent (note this is a statement about
estimators, not about the subtree sizes, these are of course not independent). I think the
independence is actually not necessary for the conclusion if you do a more precise
computation.

For i=1,...,n do Ni runs of Xi and take the sum of the averages of each run. We
get an estimator for x1+...+xn with variance

Var(X1)/N1+...+Var(Xn)/Nn

We want to minimimize this subject to the condition that N1+....+Nn is constant.

Using Lagrange multipliers we find that Var(Xi) must be proportional to Ni^2, or
equivalently Ni must be proportional to StDev(Xi).

EDIT:

Note also: if you continue this computation you find that sampling X1,..,Xn
with the optimal frequency and adding gives a lower variance than repeated Peter style
MC selection with optimal weights. So if you have the choice sampling is better.

Daniel Shawul
Posts: 3498
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Summary of Monte Carlo results for perft(12) so far

Post by Daniel Shawul » Tue Aug 16, 2011 12:50 pm

Ok I will do the test with std proportioning and other formulas for ply-4 search. But bear in mind last time I did the test the second sequence was done as frequently as the first. Now that it is done much less frequently there may not be much to gain from fine-grained formulas. Infact I suspect mean proportioning may be the safer option in early iterations.

The best variance formula I had which selects the node with the highest reduction in variance was.

Code: Select all

original_var = sigma^2 / N
after_one_game = sigma^2 / (N + 1)
X = sigma^2 (1 / N - 1 / (N + 1)) = (sigma^2 / N ) / (N + 1)
X = original_var / (N + 1)
Doing something with reduction of standard deviation instead of variance,

Code: Select all

X = sigma / sqrt(N) - sigma / sqrt(N + 1)
X = original_std / (1 - sqrt(N / (N + 1))
P.S: The std version didn't do bad but not better either. It was among one of those overlapping curves I think.

Michel
Posts: 1965
Joined: Sun Sep 28, 2008 11:50 pm

Re: Summary of Monte Carlo results for perft(12) so far

Post by Michel » Tue Aug 16, 2011 2:09 pm

I am a bit confused about what precisely causes biasedness in Daniel style methods.

I think the following is ok. Perhaps other people have an opinion.

I am reusing the notations introduced in my earlier post.

(*) Compute an estimate y1 for

x1+......+xn

using certain "proportions" (Daniel's terminology).

(*) Use the data collected during this computation to generate new proportions.

(*) Compute a new estimate y2 using these new proportions, but do not reuse
_any other data_ that went into the computation of y1. E.g. updating only an estimate
for a certain xi and keeping the other estimates is not allowed.

(*) Repeat to compute y3,y4,y5,.......(the proportions for yn may use data from y1,...y(n-1)).

(*) Compute (a possibly weighted) average of y1,y2,y3,... as the final estimate.

The reasoning behind this is that each of the yi are unbiased estimates. Hence so is the average.

Daniel Shawul
Posts: 3498
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Summary of Monte Carlo results for perft(12) so far

Post by Daniel Shawul » Tue Aug 16, 2011 3:42 pm

To be honest, I thought I knew the reason why it will be biased but after seeing the decent result of the 3-ply result, I am not sure if it is really biased or just takes a long time to get there. It started from a low value while the first sequence started from a good estimate, and then slowly climbed up to 6.288e16. For all practical purposes, I think the deeper ply results are biased since usually the end up around 6.22e16.
I first noticed this when I did a checksum after finishing the perft estimates. Whenever I recomputed the perft with the same leaf node visits UCT generated I got better and closer estimates. So I decided to add a second sequence. My reasoning (a hunch actually) was that if you reuse your computation to determine proportions (weights) , the random number sequence will be corrupt and usually underestimates the real perft value. I have stopped splitting for now at least so that can't be an excuse. Anyway it is an interesting problem.

Michel
Posts: 1965
Joined: Sun Sep 28, 2008 11:50 pm

Re: Summary of Monte Carlo results for perft(12) so far

Post by Michel » Tue Aug 16, 2011 4:02 pm

if you reuse your computation to determine proportions (weights)
Well if you read my post you see that I think the problem is not actually the proportions or
weights but rather the reuse of other parts of the computation. If you keep things separate
and at the end combine the results by taking an average there should be no problem.

If you don't trust the mathematics you can also argue as follows: Your proportions
and Peter's weights are similar in concept. Now we know experimentally that Peter2 is
unbiased (otherwise he would have quickly gotten high z values). So this means if you
replace weights by proportions the resulting estimator should be unbiased as well.

Daniel Shawul
Posts: 3498
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Summary of Monte Carlo results for perft(12) so far

Post by Daniel Shawul » Tue Aug 16, 2011 4:04 pm

Here is a Daniel3 which slightly improved upon the previous method. I added a selective part after the full width so it is now:

Code: Select all

Tree growth upto K plies + Full width N plies (currently 1) + Selective M plies (currently 1) + Monte carlo
The selective part is right now considering 2 random moves( instead of 1 as in monte carlo).

I did runs for 3 ply and 4 ply upto 500 mil move gen calls:

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
I think why it didn't work for HG was that he tries more than one move at deeper plies as well. For example
if we have a 40-move wide node at ply 8, it is most likely an exception than the marginal BF is 40. I am going to
try with a tapering from full width to random 2-moves, then MC.

Michel
Posts: 1965
Joined: Sun Sep 28, 2008 11:50 pm

Re: Summary of Monte Carlo results for perft(12) so far

Post by Michel » Tue Aug 16, 2011 4:14 pm

The selective part is right now considering 2 random moves
Do you force the two moves to be different? I think this is beneficial.

Post Reply