Up: Rollouts in GNU Backgammon


9.2.1 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 randomize 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 gotten 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.