GNU Backgammon
Backgammon board image
Table of Contents


Introduction to rollouts

The million dollar question is simple enough: out of all the games that could result from playing this position, how many do we win (and how many of our wins and losses are gammons, and how many are backgammons)? The model is exactly the same as if we had an urn with a googol balls in it (it’s a big urn), and many of the balls have win written on them, and some say gammon loss, and if we look hard enough there are a few that read backgammon win, and so on. 1) Instead of having the patience to count the googol balls, we just give the urn a really good shake and then pull 100 balls out without looking, and say for instance “Well, I got 53 wins, 31 losses, 9 gammon wins, 6 gammon losses, and a backgammon win – looks like my equity’s roughly +0.26.” and go home. If we were a bit more thorough, we could go a bit further and figure out that by cheating and measuring the sample proportions instead of the population proportions, we introduced a standard error of 0.06 into our result. (Of course, the trick is to select a sample size that’s big enough that you reduce the standard error to a tolerable level, but small enough that the answer arrives before you get bored.)

It will come as no surprise that a rollout with a limited number of trials follows exactly the same procedure. It’s sufficient to say that the proportion of wins/gammons etc. that come up when GNU Backgammon plays against itself (say) 1296 times, aren’t likely to vary all that much from the proportion we would get if we measured the proportion of results in every game we could possibly get of GNU Backgammon playing against itself. (Of course, there may still be some doubt whether the results of GNU Backgammon vs. GNU Backgammon are representative of the results of a perfect player vs. a perfect player, or of you vs. Joe Average, but that’s another story.)

Rollouts in GNU Backgammon

In GNU Backgammon the Rollout function implements the procedure described above, with the following improvements:

Quasi-Random Dice

Quasi-Random Dice are used to reduce the element of luck in rollouts. Instead of selecting purely random dice, GNU Backgammon will ensure a uniform distribution of the first roll of the rollout. If 36 trials are requested, one game will start with 11, two games with 21, two games with 31, etc. In general, if n * 36 games is requested, n games will start with 11, 2*n games with 21 etc. This is called rotation of the first roll. Similarly, if n*1296 trials is requested, the second roll will be rotated, such that n games will start with 11-11, n games with 11-21, n games with 21-21, etc. The third roll be also be rotated if the number of trials is proportional to 46656.

Suppose a user stops a 1296 trial rollout after 36 games. The 36 games would have had the following rolls for the first two rolls of each game: 11-11, 21-11, 12-11, 31-11, 13-11, …, 66-11 Obviously such a rollout will give skewed results since the second roll was 11 for all games! To avoid this problem GNU Backgammon will randomise the sequence of rolls such that it is guaranteed that for any sample of 36 games you have exactly one game with first roll 11, exactly one game with second roll 11, etc. This is called stratification.

GNU Backgammon will actually also rotate and stratify rollouts where the number of trials are not multiples of 36, 1296, etc. The distribution of rolls is obviously not uniform any longer in this case, but it will still provide some reduction of the luck, i.e., no 37 trial rollout will have 3 games with a initial 66.

Before the first game of a rollout, GNU Backgammon creates a pseudo random array which it will use for all the games in the rollout. In effect it has already decided the roll sequence it will use for up to 128 rolls in every game of the rollout. In other words, for a normal rollout where games don’t go over 64 moves, every single game of every possible rollout length has already had its dice sequence determined. During the rollout of game n, sequence n will be used, for game n+1 sequence n+1, etc. If it’s a rollout as initial position, then whenever the current sequence starts with a double, the sequence is skipped and the dice routine moves on to the next sequence. Say an rollout as initial position is about to start using sequence 275, but that sequence begins with a double. The dice routine moves to sequence 276. On the following game, it will use sequence 277 (it remembers how many it has already skipped).

So, if you select rollout as initial position and 36 games, then you will get a prefect set of rolls for games 1..30 and the first 6 rolls of the next perfect set (the same rolls you would have gotton for games 31..36 if you’d asked for 1080 games or 10800 games or 92 games or whatever.

The dice sequence doesn’t know how many trials it will be asked for, it simply generates sequences such that for a normal rollout (rollout as initial position) every 36 (30) games you get all possible 1st rolls, every 1296 (1080) games get every possible first 2 rolls, every 46656 (38880) games you get full sets of 3 rolls, etc.

How to set up a rollout

FIXME Explain all the options in the rollout setting dialog.

1) Balls and urns are to probability theorists what teapots and chequerboards are to computer graphics researchers, or “squeamish ossifrage” is to cryptographers – they seem to come with the territory.
rollouts.txt · Last modified: 2013/02/08 08:19
Valid XHTML 1.0! Valid CSS! Get Firefox!