Re: [Bug-gnubg] Parallel dice streams

[Michael Petch]

I realized you may be referring to something else ( rollout as initial position). If that’s the case an excerpt from the GnuBG site documentation has an explanation on what “should” happen ( http://www.gnubg.org/documentation/doku.php?id=rollouts )  :

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 psuedo 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.


On 23/08/09 11:19 PM, "Michael Petch" <address@hidden> wrote:

> Christian may wish to chime in, but I’ll tell you what I am aware of – and I may not fully understand what you are asking. There is a match seed (options/settings/dice/seed) that can be set and it is associated with the dice as you are playing the match. Normally the dice seed is reset between new matches (To get the same dice for each match see this article: http://lists.gnu.org/archive/html/bug-gnubg/2009-08/msg00239.html ). Each game should get different dice (Unless you manually reset the seed during the match yourself). If you do a rollout, there is a separate seed associated with rollouts thus a separate random stream (This seed is set on the rollout page) that should not interfere with the random number stream for the dice being produced for the game.
>
> Now, as for rollouts, rollouts are not entirely deterministic. If you do a rollout with the same seeds the results will most likely be different if you are using a multithreaded version where the Threads are set to something higher than 1. From my experience if you use more than 1 thread, you can do a rollout with a given seed and get one result - If you rollout it out again with the same seed you might get a different result. If this is a problem, then setting thread count to 1 should solve it.
>
> Michael
>
> On 23/08/09 10:37 PM, "bob koca" <address@hidden> wrote:
>
> >  I want to compare the effects of score on a doubling decision for a checker position. So I want to rollout
> > 1296 times at two different scores. To hopefully lower variablity for the differenceI used the same seed for each rollout.  Does it mean that the dice will be the same for each game 
> > (until one ends of course)? So the 1rst, 2nd, 3rd, ... games have the same dice. Or does it all get messed up as soon
> > as one game for one rollout takes longer than its counterpart in the other? I thought it should be the former but a short testing of it 
> > (7 rollouts for each with seeds 100, 200, ... 700) does not show a  strong positive correlation like I would have expected.