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

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: 105
1 point match
pip: 90
score: 0

Blue is Player 1
XGID=----CCCCC-------ccccc-----: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 ply
Confidence 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: Rockwell-Kazaross


As you can see, after only 100 games the bot thinks it has the correct equity within plus-minus 0.002, which corresponds to having estimated the right winning percentage within plus-minus 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*(1-p)/n . As we don't know the exact probability, we need to find an upper-bound for the variance. So let's say we take the approximate winning percentages to be 0.83-0.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, 1-2*Q(0.001/sigma)>0.95 , were Q(.) is apparently the Gaussian-tail-function. 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 bear-off data base while evaluating this position. I wanted it to roll it out to the bitter end. I Don't know how to switch-off the bear-off data base, if possible(?1) .

Messages In This Thread

 

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.