[Bug-gnubg] Re: Playing with Nis' algorithm for rollout dice

[Nis Jorgensen]

On 30 Oct 2002 at 17:51, Jim Segrave wrote:

> On Tue 29 Oct 2002 (21:06 +0100), Nis Jorgensen wrote:
> > 
> > Here is my suggestion for how to do it. I am afraid it includes a 
> > dynamically sized array (to hold the rolls used for move number n). 
> > This means that I cannot really do the programming - but here it is 
> > in something that might look like C, but isn't. Note that the 
> > randomization algorithm is missing ... this should be done based on 
> > the rng, and I have no idea how. If anyone has ideas for how to 
> > extend the "exaxt" rotation of rolls beyond 2 turns, I am very 
> > interested. I think I will try asking in a math newsgroup one of 
> > these days.
> > 
> > Explanations of algorithm will follow - I need people to tell me what 
> > is not understandable.
> 
> I looked at the algorithm and turned it into working C code. It was
> amusing for someone who hates arrays and likes poionters - I'd seldom
> needed a declaration that was quite so line-noise like as:
> 
>   static int (**aRolls)[36][2];
> 
> Those interested are welcome to this version.

I guess that would be me ...
 
> But I still wasn't happy with it - it didn't deal with inital
> positions and, after the first two rolls, it didn't ensure that all 3
> roll sequences would be done in 38880/46656 games. 

Yes - those were known limits of the algorithm I submitted

> And, while a
> dynamically resized array is amusing to code, until CPUs get a lot
> faster, I can't see anyone caring if they get the first 5 rolls
> exhaustively done. 

I don't really understand what you are saying here. The aim of the 
dynarray is not to get exhaustive 5-ply rollouts.

> So I recoded it using a staticly allocated array
> and coping with at most the first 4 rolls, after which the dice are
> the results of calls to random. 

I looked at your code, and saw three problems (except for the missing 
stratification of later moves :-)

1) The randomization algorithm is wrong. Try changing it to 

  for (i = 1; i < 36; ++i) {
      swap = random () % (i + 1)
      for (j = 0; j < 2; ++j) {
        save = aRolls[iTurn][swap][j];
        aRolls[iTurn][swap][j] = aRolls[iTurn][i][j];
        aRolls[iTurn][i][j] = save;
      }
  }

2) The limits array is also wrong, or I don't understand what you are 
doing. We have 

static int limits[2][4] = { 
  { 36, 36 * 36, 36 * 36 * 36, 36 * 36 * 36 * 36 },
  { 30, 36 * 36, 36 * 36 * 36, 36 * 36 * 36 * 36 }
};

I believe those should be 

static int limits[2][4] = { 
  { 36, 36, 36 * 36, 36 * 36 * 36 },
  { 30, 36, 36 * 36, 36 * 36 * 36 }
};

or in a (to me) more readable form

static int limits[2][4] = { 
  { 36, 36 , 36 ^ 2, 36 ^ 3},
  { 30, 36, 36 ^ 2, 36 ^ 3}
};

3) Even with the above mentioned changes, there is a problem with the 
rolls not being sufficiently rotated for turns 2 and 3 . For 
instance, for the first 1296 games, the same 36 combinations of  roll 
0,2 and 3 are repeated over and over (since iGame/limit is 0). Of 
course this evens out as weapproach 36^4 trials - but that wasn't the 
idea, was it?
-- 
Nis Jorgensen
Friends Development & Support
Greenpeace 
+31 (20) 52 36 202