[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[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.
--
Jim Segrave address@hidden
nis.c
Description: Text document