
BGonline.org Forums
Got Variance?
Posted By: Timothy Chow
Date: Sunday, 23 May 2010, at 11:30 p.m.
In Response To: Got Variance? (Daniel Murphy)
O.K., let's see if I can explain the potential issues here concisely.
What is the equity of a position? It is the value of the game, averaged over all possible ways of playing out the game (i.e., all possible subsequent sequences of dice rolls). We can't compute this directly because we don't have infinite computing power. So we sample from the space of possible games by doing a rollout. Ignoring variance reduction for simplicity, what we get is a long list of outcomes: some +1, some 1, some +2, some 2, some +3, some 3, some +4, some 4, etc. We can plot a histogram of these results, with the height of each bar being proportional to how often we observed that result. The weighted average of the samples gives us an equity estimate.
Now, where does the confidence interval come from? This comes from the assumption that, in the long run, if we take enough samples, the shape of the histogram will approach a bell curve (a Gaussian or normal distribution). The bell curve has certain properties, such as the fact that 95% of the area lies within 2 standard deviations of the mean. We can estimate the standard deviation by taking the standard deviation of our samples. This is what the bots report as the 95% confidence interval: plus or minus 2 sample standard deviations from the sample mean (maybe they do some slight correction to compensate for the fact that the sample standard deviation is a biased estimate of the true standard deviation even in the Gaussian case, but this is a technical point that is not really relevant to the present discussion).
So what if anything is wrong with this procedure? The main issue is that the histogram may not, in fact, approach a bell curve in the limit. Perhaps it's slightly lopsided. Perhaps rare, large values (i.e., very large cubes) occur with probability different from what the Gaussian assumption would predict. How can we test this?
The way to do it is to take extremely large samples and try to piece together the histogram directly, without making any assumptions about bell curves. For this we need something like the GNU "View statistics" feature, which tells us how many trials ended with a single/double/triple win or loss with the cube on various values. This way we can see directly what the histogram looks like and find out if indeed 95% of the area lies within 2 standard deviations of the mean.
In a money game, there's still some small chance that one could encounter difficulties because maybe the cube gets exponentially large an exponentially small percentage of the time, and no finite amount of sampling will ever detect this. We can circumvent this problem by restricting ourselves to match play, where there's an upper limit on the size of the cube. Then, provided we take a large enough sample, we will get an excellent approximation of the true (infinite) histogram.
What will we find if we carry out such an experiment? I don't know. However, it seems plausible to conjecture that different positions will give rise to differentlooking histograms. Some positions may lead to more lopsided graphs than others.
It's not so much that the bot is doing something wrong as that the Gaussian assumption is reasonable for some positions but no so reasonable for others. Without doing thorough analyses of the type described above, we can't really hope to figure out which positions have funnylooking histograms and which ones don't. But conversely, if we do, we may get some insight into what sorts of positions are likely to report misleading confidence intervals.

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