Re: [Bug-gnubg] Re: Race database and bearoff DB

[Jim Segrave]

On Fri 04 Oct 2002 (06:29 -0400), Douglas Zare wrote:
> Quoting Jim Segrave <address@hidden>:
> 
> > On Tue 01 Oct 2002 (16:19 +0000), Joern Thyssen wrote:
> > > On Tue, Oct 01, 2002 at 05:20:15PM +0200, Jim Segrave wrote
> > 
> > I just tried a little crude perl script to see how many values are
> > unneeded in the database.
> > 
> > My plan was:
> > 
> > the probability of clearing in n rolls is 0, if the number of chequers
> > is more than 4*n. In these situations, you could omit the beginning of
> > the values for a position, since they are known to be 0.
> > 
> > the probability of having cleared after n rolls in a position is 1 if
> > (n * 3 >= pip count) and (n * 2) >= number of chequers since you'd
> > still clear everything even with repeated 21 rolls. 
> 
> No, 3111 can fail to be off in 2 rolls, even though there are 4 checkers and 
> the pip count is 6. I don't know what the exact criterion should be, but 
> maybe 
> it would be closer to imagine that the points are numbered 2,3,5,6,8,9,11,12 
> and that the roll is 3-2. You would always play at least 4 pseudopips (except 
> on the last roll) and at most 5, and this is a bit tighter than always 
> playing 
> at least 2 pips but at most 3. 3111 would correspond to 5222, hence 11 
> pseudopips.

Oops - it was a bit too loose as an estimate. 

> > There is probably some much more realistic threshold after which the
> > probability of clearing all checkers from the 1 through 6 points is
> > effectivly 1, particularly given that the database can't give a
> > probability less than 10**-5 in a short.
> 
> There is potential wastage even if the rolls are smaller than average, 
> particularly on the last roll. I think there is also the issue that the 
> threshold is 2^-17, or lower if you multiply by a factor to use the higher 
> bits. 
> 
> If one ignores these, I think a direct calculation is easier than being very 
> careful about the error estimates of strange distributions.
>
> Pips Rolls
> 
> 15 5
> 30 8
> 45 11
> 60 13
> 75 16
> 90 18
> 105 21
> 120 23
> 135 25
> 150 28
> 165 30
> 180 32
> 195 34
 
> For 105 and 150 pips, the chance of taking exactly 21 and 28 rolls, 
> respectively, is less than 2^-16, but the chance of taking at least that many 
> rolls is just over 2^-16.

I was just looking for a conservative upper bound on useful entries
where the probability is being represented in 16 bits. I was mostly
looking at the 32 values for a 6 point db and thinking this has to be
overkill. Your table above suggests that we could drop a large chunk
of the values in the db for 6 points. It was a very off-the-cuff
estimate by someone who's nor paricularly skilled in this area of
maths, and I appreciate seeing an accurate derivation rather than some
fast hand-waving on my part.
 
> Here is the Mathematica code I used for solving the one checker roll 
> distribution:
> 
> Clear[onecheck]
> 
> onecheck[npips_, rolls_] := 
>   onecheck[npips, rolls] = 
>     If[npips <= 0, If[rolls == 0, 1, 0], 
>       N[1/36(2 onecheck[npips - 3, rolls - 1] + 
>               3onecheck[npips - 4, rolls - 1] + 
>               4 onecheck[npips - 5, rolls - 1] + 
>               4 onecheck[npips - 6, rolls - 1] + 
>               6 onecheck[npips - 7, rolls - 1] + 
>               5 onecheck[npips - 8, rolls - 1] + 
>               4 onecheck[npips - 9, rolls - 1] + 
>               2 onecheck[npips - 10, rolls - 1] + 
>               2 onecheck[npips - 11, rolls - 1] + 
>               1 onecheck[npips - 12, rolls - 1] + 
>               1 onecheck[npips - 16, rolls - 1] + 
>               1 onecheck[npips - 20, rolls - 1] + 
>               1 onecheck[npips - 24, rolls - 1])]]
> 
> The N means that Mathematica only keeps about 17 decimal places of accuracy, 
> perhaps 48 bits, which should suffice for this calculation. 
> 
> > A side note for the mathematically inclined (totally irrelevant to
> > gnubg):
> 
> 
> Spoiler below.

Thanks - I was looking for a model for visualising this and I couldn't
come up with one.

-- 
Jim Segrave           address@hidden