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

[Jim Segrave]

This problem of getting an optimal psuedo-random sequence of rolls for
rollouts has been nagging at me. I now have sample code which meets
the following criteria:

If the init function is called before starting a rollout, then the
function GetRoll can be called repeatedly for games.

Every 30/36 * 36**n games, every possible first n+1  rolls will appear
for n = 0..3. Later rolls within a game will be generated by a
caller-supplied function. 

It uses about 100K bytes of memory. The first time it's initialised,
it does a fairly intensive setup (but negligible in real time),
subsequeent re-initialises are very cheap.

Enclosed is a C program which uses the algorithm (compile with 

  gcc -DTEST_ROLLS -Wall -g -o randroll randroll.c

I ran a little perl script (also attached) to check that the output is
correct- it basically ensures that every 30/36 games the first roll
distribution is correct, every 1080/1296 the first two roll
distribution is correct, etc. It's been tested out to a complete 1.7M
game run.

This would be, I think, easy to include in rollout.c

Notes:
It uses random() and expects srandom() to be called when setting up
for a rollout. rand()/srand() would work, but don't give as nice a
psuedo distribution. I don't know if random()/srandom() are standard
library functions.

It uses a caller supplied struct, so if someone thinks of a reason to
run multiple copies of this simultaneously, it will work.


-- 
Jim Segrave           address@hidden

randroll.c
Description: Text document

checkrand
Description: Text document