
BGonline.org Forums
Variance Reduction
Posted By: rambiz
Date: Saturday, 19 July 2014, at 12:33 p.m.
In Response To: Variance Reduction (Timothy Chow)
A lot of thanks to you and Bob Koca.
I am not much worried about the independence assumption. I also do agree that Variance Reduction increases the convergence speed. What worries me is how faster is it actually? It appears to me that the confidence intervals XG reports converge too fast and are also kind of arbitrary, since nobody (?!) knows how to exactly factor in the effect of variance reduction. As an example, please have a look at this position:
White is Player 2
score: 0
pip: 1051 point match pip: 90
score: 0
Blue is Player 1XGID=CCCCCccccc:0:0:1:00:0:0:0:1:10 Blue on roll, cube action?
Analyzed in Rollout No Double Player Winning Chances: 83.73% (G: 0.06% B: 0.00%) Opponent Winning Chances: 16.27% (G: 0.00% B: 0.00%) Double/Take Player Winning Chances: 83.73% (G: 0.06% B: 0.00%) Opponent Winning Chances: 16.27% (G: 0.00% B: 0.00%) Cubeless Equities No Double: +0.675 Double: +0.675 Cubeful Equities No Double: +0.675 (0.000) Double/Take: +0.675 Double/Drop: +1.000 (+0.325) Best Cube action: Double / Take Rollout details 100 Games rolled with Variance Reduction.
Dice Seed: 61912136
Moves and cube decisions: 3 plyConfidence No Double: ± 0.002 (+0.673...+0.676) Confidence Double: ± 0.002 (+0.673...+0.676) Double Decision confidence: 50.7% Take Decision confidence: 100.0% Duration: 53.9 seconds eXtreme Gammon Version: 1.21, MET: RockwellKazaross
As you can see, after only 100 games the bot thinks it has the correct equity within plusminus 0.002, which corresponds to having estimated the right winning percentage within plusminus 0.001.
Now let's work out how many games do we need to assess the winning chances with a 0.1% accuracy without Variance Reduction.
Assuming we knew the exact probability (which we are looking for), the variance after n trials, would be p*(1p)/n . As we don't know the exact probability, we need to find an upperbound for the variance. So let's say we take the approximate winning percentages to be 0.830.17 . So the variance after n trials would be sigma^2=0.83*0.17/n . OK, now if we want the average to be within 0.001 of the true winning chance after n trials with a say 95% confidence, 12*Q(0.001/sigma)>0.95 , were Q(.) is apparently the Gaussiantailfunction. It follows n>~3.84*0.83*0.17*10^6~541824 .
Well, 541824 is much bigger than 100, isn't it?
CAVEAT! It might well be that XG uses it's bearoff data base while evaluating this position. I wanted it to roll it out to the bitter end. I Don't know how to switchoff the bearoff data base, if possible(?1) .

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