Re: [Bug-gnubg] Re: more on bearoff databases

[Joern Thyssen]

On Sun, Oct 27, 2002 at 01:21:04PM -0600, Neil Kaz wrote
> New comments prefaced by (KAZ)
> ----- Original Message -----
> From: "Joern Thyssen" <address@hidden>
> To: "Neil Kaz" <address@hidden>
> Cc: "GNU Backgammon Bugs" <address@hidden>
> Sent: Sunday, October 27, 2002 1:06 PM
> Subject: Re: [Bug-gnubg] Re: more on bearoff databases
> >
> > Unfortunately there are 10M positions with 13 chequers on 13 points, and
> > 15 positions with 2 chequers on five points, hence a total of 150M
> > positions.
> 
>  (KAZ) OK I was afraid of something like that so lets just stop at the 13
> point !
> 
> > > (NK) I don't see how a normal distribution can pick up on wastage
> effects
> > > or tell GNU how to properly play during the bear in.
> >
> > I keep the mean and the variance for the roll distribution, so I think
> > wastage effects are accounted for.
> 
> (KAZ) I think I misunderstood. I trust that this is from a database ? I'm
> confused here.

In the normal one-sided bearoff databases we store an array of
probabilities: the probability to bear off in 0 moves, in 1 move, in 2
moves etc etc. 

For example,

 GNU Backgammon  Position ID: qm3bAADMXdsAAA
                 Match ID   : cAkZAAAAAAAA
 +13-14-15-16-17-18------19-20-21-22-23-24-+     O: gnubg
 |       O  O  O  O |   | O  O  O  O  O    |     0 points
 |       O  O  O  O |   | O  O             |
 |                  |   |                  |
 |                  |   |                  |
 |                  |   |                  |
v|                  |BAR|                  |     (Cube: 1)
 |                  |   |                  |
 |                  |   |                  |
 |                  |   | X  X             |
 |       X  X  X    |   | X  X     X       |     On roll
 |       X  X  X  X |   | X  X     X       |     0 points
 +12-11-10--9--8--7-------6--5--4--3--2--1-+     X: jth

Evaluator:      BEAROFF-OS (10 points)

             Player       Opponent
Position      3169448       3047100

Bearing off                             Bearing at least one chequer off
Rolls   Player  Opponent        Player  Opponent
    2     0.000   0.000           1.080   0.000
    3     0.000   0.000          19.255   5.348
    4     0.000   0.000          41.138  37.057
    5     0.000   0.000          33.840  52.866
    6     0.000   0.000           4.475   4.552
    7     0.024   0.011           0.208   0.175
    8     0.244   0.189           0.003   0.002
    9     1.332   1.308           0.000   0.000
   10     4.543   4.807           0.000   0.000
   11    10.585  11.350           0.000   0.000
   12    18.109  19.187           0.000   0.000
   13    22.684  23.238           0.000   0.000
   14    20.911  20.528           0.000   0.000
   15    13.623  12.634           0.000   0.000
   16     5.919   5.135           0.000   0.000
   17     1.674   1.353           0.000   0.000
   18     0.310   0.233           0.000   0.000
   19     0.038   0.026           0.000   0.000
   20     0.003   0.002           0.000   0.000

The second column is the probabilities for player jth and the third
column for player gnubg. The fourth and fifth columns are for
calculating gammon probabilities.

The problem is that foreach position I have to store, on average, 18
probabilities. If I calculate the mean and the variance for the
distributions above I get:

Bearing off                             Saving gammon
        Player  Opponent        Player  Opponent
Mean     13.142  13.048           4.218   4.569
Var.      1.732   1.694           0.855   0.680

Saving these only requires 4 values per position i.e., I've saved a
factor of four (depends on the precision required). Using normal
distributions with the means and variances above I get a roll
distribution of:

    1     0.000   0.000           0.038   0.000
    2     0.000   0.000           1.577   0.042
    3     0.000   0.000          16.656   3.900
    4     0.000   0.000          44.973  41.011
    5     0.000   0.000          31.034  48.485
    6     0.004   0.003           5.473   6.445
    7     0.036   0.034           0.247   0.096
    8     0.250   0.247           0.003   0.000
    9     1.228   1.261           0.000   0.000
   10     4.281   4.497           0.000   0.000
   11    10.597  11.218           0.000   0.000
   12    18.628  19.564           0.000   0.000
   13    23.253  23.854           0.000   0.000
   14    20.613  20.334           0.000   0.000
   15    12.976  12.119           0.000   0.000
   16     5.801   5.050           0.000   0.000
   17     1.842   1.471           0.000   0.000
   18     0.415   0.300           0.000   0.000
   19     0.066   0.043           0.000   0.000
   20     0.008   0.004           0.000   0.000
   21     0.001   0.000           0.000   0.000

which is sufficiently close to the "exact" distribution above.

In fact, with the "exact" one-sided distribution p=56.6%, whereas the
approximative distribution gives p=56.8%. A rollout gives 56.6%.

Jørn

-- 
Joern Thyssen, PhD
Vendsysselgade 3, 3., DK-9000 Aalborg, Denmark
+45 9813 2791 (private) / +45 2818 0183 (mobile) / +45 9633 7036 (work)
Note: new mobile number!