[ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums

Variance Reduction

Posted By: rambiz
Date: Tuesday, 22 July 2014, at 6:27 p.m.

In Response To: Variance Reduction (Bob Koca)

True, I don't know the value of p but we can easily find an upper-bound for variance in most cases. For example if we know that a gammonless position is a pass, we can use 0.25*0.75 as the maximum value of the variance. While analysing this position, I knowingly chose a p-estimate close to the real value to show that even if we go with the practically smallest possible variance estimate, still the difference between the number of games needed with and without VR is huge.

On the other hand, in the VR case, even knowing the approximate value of p, won't make the sample variance redundant, since using the p*(1-p) formula basically would throw away all gained by the VR.

Is it right to say, that VR gain approximately equals the ratio p^*(1-p^)/sample variance, where p^ is the sample average?!
Applying Bob Koca's and Tom Keith's ideas, I did the following expriement:

The score (after 0 games) is: White 0, Blue 0 (match to 1 point, post-Crawford play)

Move number 6: Blue to play 43

White160

Blue167
Position ID: 4PPgASTgc/ABMA Match ID: cAkuAAAAAAAA

# Ply Move MWC
1 R 13/9 6/3* 56.28%
 0.563 0.158 0 - 0.437 0.192 0.004 56.28% 0 0 0 - 0 0 0 0.00%
Full cubeless rollout with var.redn.
1 games, rollout as initial position, Mersenne Twister dice generator with seed 719683634
Play: 2-ply cubeless prune
keep the first 0 0-ply moves and up to 8 more moves within equity 0.16
Skip pruning for 1-ply moves.
Cube: 2-ply cubeful prune
2 2 24/20 6/3* 47.71% ( -8.57%)
0.477 0.115 0.004 - 0.523 0.144 0.006
3 2 24/21 24/20 46.94% ( -9.33%)
0.469 0.105 0.004 - 0.531 0.143 0.004
4 2 24/20 13/10 46.49% ( -9.79%)
0.465 0.112 0.003 - 0.535 0.149 0.005
5 2 13/6 45.71% (-10.57%)
0.457 0.116 0.003 - 0.543 0.152 0.005

I ran 20 1-trial-rollouts starting with seed 719683634 and added 1 to the seed for the next rollout and got the following estimates for 13-9 6-3*:
0.5628 0.5163 0.2934 0.5560 0.4590 0.4337 0.6589 0.5052 0.4576 0.5006 0.5009 0.5150 0.4666 0.4543 0.4358 0.4956 0.4554 0.4366 0.4799 0.6122

Now the average is: p^=0.4898 ---> p^*(1-P^)=0.2499 and the sample variance is: 0.0057
Finally 0.2499/0.0057~43.8 . Does it mean that VR speeds up the rollout by a factor of almost 44 for this type of position? Is it this simple?!

Post Response

Your Name:
Your E-Mail Address:
Subject:
Message:

If necessary, enter your password below:

Password:

 [ View Thread ] [ Post Response ] [ Return to Index ] [ Read Prev Msg ] [ Read Next Msg ]

BGonline.org Forums is maintained by Stick with WebBBS 5.12.