[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-gnubg] Re: Race database and bearoff DB
From: |
Douglas Zare |
Subject: |
Re: [Bug-gnubg] Re: Race database and bearoff DB |
Date: |
Fri, 4 Oct 2002 06:29:14 -0400 |
User-agent: |
Internet Messaging Program (IMP) 3.1 |
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
> >
> > Basically it's 32 unsigned short ints for each position. The current
> > one-sided bear-off database is for 15 chequers on the 1-6 points, a
> > total of N(21,6)=54264.
> >
> > Each of the 32 integers represent the probability that we bear off in i
> > moves (multiplied by 255).
> >
> > #Pos #Short ints #bytes
> > 15 chrs on p1-6 : N(21,6) 54264 1736448 3.4 MB
> > 15 chrs on p1-7 : N(22,7) 170544 5457408 5.4 MB
> > 15 chrs on p1-8 : N(23,8) 490314 15690048 31.3 MB
> > 15 chrs on p1-9 : N(24,9) 1307504 41840128 83.7 MB
> > 15 chrs on p1-10: N(25,10) 3268760 104600320 209.2 MB
> > 15 chrs on p1-11: N(26,11) 7726160 247237120 494.5 MB
> > 15 chrs on p1-12: N(27,12) 17383860 556283520 1112.6 MB
> >
> > We currently use 15/1-6 which easily fits into memory and can be
> > referenced as:
> >
> > aaBearoff1 ( position, i )
>
> 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.
> 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.
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.
> I was interested in the N(i, j) in the above list. In fact I foolishly
> misread it as being about the number of combinations of i things taken
> j at a time and was going to send an email pointing out how wrong this
> was, but then I realised that it had nothing to do with C(i,j) and
> that the figures are right. I'd already written a little perl script
> to work out the number of positions for various numbers of points,
> which not surprisingly, matches the above. But the series has an
> interesting property. If you list the elements of the series and the
> multiplier to get the next element you get the following pleasing
> pattern (p[i.j] is the number of distinct positions of i checkers over
> j points (including some checkers possibly being borne off):
>
> multiplier to get next term
> p[15, 1] = 1 16/1
> p[15, 2] = 16 17/2
> p[15, 3] = 136 18/3
> p[15, 4] = 816 19/4
> p[15, 5] = 3876 20/5
> p[15, 6] = 15504 21/6
> p[15, 7] = 54264 22/7
> p[15, 8] = 170544 23/8
> p[15, 9] = 490314 24/9
> p[15, 10] = 1307504 25/10
> p[15, 11] = 3268760 26/11
> p[15, 12] = 7726160 27/12
> p[15, 13] = 17383860 28/13
> p[15, 14] = 37442160
>
> I'm sure there's a reason for this, but I can't see it.
I take it that you are looking for what is called a proof of a bijective
flavor, since this recursion follows directly from the exact formula, a+b-1
choose a.
Imagine that you have dividers and checkers. Initially you have 15 checkers and
no dividers. Then you insert a divider in one of the 16 gaps between the
checkers, possibly before or after all 15. (The checkers before the divider are
borne off, and those after the divider are on the ace point.) Then you insert a
divider in one of the 17 gaps... but there are two ways to get each resulting
configuration, as you might have just inserted the first or the second divider.
So each location of one divider corresponds to 17 with 2 dividers, but this
precisely double counts, hence the term 17/2. The general case is analogous.
Douglas Zare