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

[Jim Segrave]

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.

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. 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. 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. A bit of experimenting with the
output, grep/sed/sort/uniq -c looks kind of promising. You get a good
distribution of rolls for any length (where good is an eyeball
estimate, not a statistician's blesing). And you automatically get
full coverage of 1st rolls every 30/36 games, 2nd every 1080/1296
games, first 3 rolls every 38880/46656, etc. Attached is a sample
including a main() which will print out one per line:

turn  game  dice

for the first four rolls of every game. To run it do:

./nis size [-/1]

size is either 1..4 to do 30/36, 1080/1296, 38880/46656,
1166400/1679616 games or a simple number of games. The optional second
parameter, if '1', does an initial position (no doubles in move 0).

I think it would be easy to put this into gnubg and it should make
terminating a 1296 game rollout less biased. All in all, an amusing
programming exercise to while away a conference call in which I wasn't
really needed.

-- 
Jim Segrave           address@hidden

nis.c
Description: Text document