Introduction

Computer roll-outs such as those available with Jellyfish and Snowie (bots), often used to determine the equity of a move or position, are not as precise as some people may assume. In fact, there are limits to what a roll-out can accomplish. In a roll-out, a computer plays a position many times starting with each of two alternative moves. The move that receives the highest equity in the roll-out is deemed the better move.

In any one game there is no equity, only a specific outcome – a win or loss of 1,2, or 3 points. If we perform a roll-out, and average the outcomes, we get a sample equity, which is an approximation of the actual equity associated with a move. But the sample equity, based on many outcomes, is not exactly the true equity, based on all possible outcomes.

There are two elements at work in the calculation of sample equity – the underlying equity of each move (signal) and chance variation (noise). As we use roll-outs of greater length, true equity – the average of all possible outcomes – begins to dominate chance variation. In thinking properly about roll-outs it is critical to distinguish between sample equity (which varies from roll-out to roll-out) and true equity (which never changes).

Sample Size and Equity

An analogous situation occurs all the time in the news. In political opinion polls the same sample size is always used, but this fixed sample size can only predict the winner in one-sided elections. For example, if a poll were to show Bush with 48% of the vote and Gore with 45%, with a margin of error of 3% (a common margin of error indicating a sample size of about 1,000 to 2,000) that means Bush will get 45% to 51% of the vote and Gore 42% to 48% of the vote. Too close to call! On the other hand, if Bush were to get 60% and Gore 35%, even with the 3% margin of error, we know Bush will win, we expect him to get at least 57% and Gore at most 38%. Bush will win by a wide margin.

To predict a winner under the first scenario, Bush favored by 48% of the sample of voters and Gore favored by 45%, we would need a much smaller margin of error, and hence a much larger sample of voters.

Roll-outs are a sampling process as well, subject to chance variation, and only accurate to a margin of error that shrinks with increased sample size, but never goes away. But where is this “margin of error” in roll-outs?

What's the Best Move?

A relationship between sample size and difference in sample equity has the following form:

n = the number of games played in the roll-out
d = the difference in equity for two moves, based on the roll-out (sample equity).

For minimal evidence one move is better than another we need: n(d)² > 15, and for overwhelming evidence we need: n(d)² > 30.

Examples

Another way of saying this: although the sample equity is different for the two moves, the difference is not so great that we can say the true equities differ, or which move really has the higher true equity.

Suppose, on the other hand, I roll out a position 2,000 times and find move #1 has sample equity 0.20 and move #2 has sample equity 0.68. Calculating, we find:

2,000(0.20 - 0.68)² = 460, which is much greater than 30. In this case, although the roll-out is based on a small number of games, the evidence in overwhelming. Move #2 is clearly better. Someone else using a different software, different random number generator, or different settings, will (almost certainly) reach the same conclusion. Results may vary slightly, but move #2 will always be clearly better.

Another way of saying this: the differences in sample equity are so great that, although we do not know the true equities exactly, we know that move #2 has a much higher true equity.

Notice that a small sample is sufficient to find the best move when the moves have vastly different equity, but a large sample is NOT enough when the moves are close in equity.

What is the True Equity of a Move?

For any roll-out result we can estimate the true equity by (see appendix):

sample equity ± 3/Ön.

For example, in the first case above we had a roll-out involving 20,000 games and the first move had sample equity 0.041 and the second move had sample equity of 0.034. The estimated true equities are

Move #1: 0.041 ± 3/141.4 = 0.020 to 0.062
Move #2: 0.034 ± 3/141.4 = 0.013 to 0.055.

The considerable overlap between the two intervals is additional evidence that the two moves are indistinguishable at this sample size. Although, move #1 appears to have higher equity, the equity for move #1 could be as low as 0.020 and the equity for move #2 could be as high as 0.055.

Absolute Limitations

In other words, all bots have a largest n, and this implies that for very small differences, n(d)² can never exceed 15. So moves with nearly identical sample equities cannot be compared using bot roll-outs.

Summary

I give a rule of thumb as follows:

n = the number of games played in the roll-out
d = the difference in sample equity for the two moves.

If n(d)² > 15 there is some evidence the move that appears better really is better.
If n(d)² > 30, there is overwhelming evidence the move that appears better really is better.

I also have a rule of thumb for estimating the true equity of a move from the sample equity (roll-out results).

n = the number of games played in the roll-out
e = the equity based on the roll-out (sample equity),

e ±3/Ön.

For statistics fanatics, the mathematical derivation of these rules can be found in the Appendix.

Appendix

The following ideas are based on independent two-sample t-tests, with very large sample sizes (so that we can use a z-table in place of a t-table). Denote the following:

--the true equity for move i. The average of all outcomes if we rolled-out the position an “infinite number of times”.

--the sample equity for move i, found in the roll-out. The average of the outcomes in the roll-out.

We are considering a statistical hypothesis test where the null and alternative hypotheses are:

H_o: e_i = e_j versus  H_a: e_i ¹ e_j.

The test statistic is, which should be approximately normal (see comments at the end).

The variance for each move can be estimated by assuming some typical outcomes.

Assume a player either wins or loses a backgammon 1% of the time, either wins or loses a gammon 13% of the time, and either wins or loses a single game 36% of the time. In this case the variance in equity outcomes is 1.94 points. Although each position and move has a different profile of outcomes, most positions have a similar variance.

The value z = 1.96 is associated with a p-value (significance level) of 5%. If there is really no difference in the true equity of the two moves we will see this large an apparent difference, due to chance variation, 5% of the time. This is widely acknowledged to be the point (if we must pick a set point) where we claim we have evidence something more than chance variation is going on.

The value z = 2.58 is associated with a p-value (significance level) of 1%. If there is really no difference in the true equity of the two moves we will see this large an apparent difference, due to chance variation, a mere 1% of the time. This is widely acknowledged to be the point (if we must pick a set point) where we claim we have strong evidence something more than chance variation is going on.

Putting this all together, we have evidence when

In other words n(d)² = 14.9 is the borderline case, for statistical significance at the 5% level. I simplify this to n(d)² = 15.

For the second case, we have

In other words n(d)² = 25.8 is the borderline case, for statistical significance at the 1% level. I simplify this to n(d)² = 30, which is actually associated with a p-value of 0.54%, and makes a nicer rule of thumb, especially since 30 is twice 15.  This I consider overwhelming (very strong?) evidence.

The confidence interval:

The most common confidence interval is 95%. Indicating that such confidence intervals, in the long run, tend to be wrong 5% of the time.  A 95% confidence interval, assuming a normal distribution (see below) for any average (for example, the sample equity), is

The rule is easier to remember if 2.73 is replaced with 3, which is actually a 97% confidence interval.

The normality assumption:  Because the outcomes of a game are actually a profile of 6 possible outcomes (-3, -2, -1 for losses and +1, +2, + 3 for wins), and because the number of outcomes in a roll-out is usually in the thousands, we can say the test statistic is normally distributed.