bug-gnubg
[Top][All Lists]

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

 From: Jim Segrave Subject: [Bug-gnubg] Playing with Nis' algorithm for rollout dice Date: Wed, 30 Oct 2002 17:51:06 +0100 User-agent: Mutt/1.4i

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

--