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

[Douglas Zare]

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