[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Bug-gnubg] Re: Playing with Nis' algorithm for rollout dice
From: |
Nis Jorgensen |
Subject: |
[Bug-gnubg] Re: Playing with Nis' algorithm for rollout dice |
Date: |
Thu, 31 Oct 2002 10:10:05 +0100 |
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