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

[Jim Segrave]

On Sun 27 Oct 2002 (19:52 +0000), Joern Thyssen wrote:
> On Sun, Oct 27, 2002 at 01:21:04PM -0600, Neil Kaz wrote
> 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%.
> 

What if we combine the two approaches?
 1) Build a OSR database using the mean and std
 2) Compare this to the full database that you are generating and for
     each position, generate a metric on how good the mean/std
         approach is

 3) From this, build an erros database of positions with a large error
    metric. You could choose the size of the exceptions database on an
    ad-hoc basis, and this would determine the scale of error you
    would attempt to fix.

 4) Use the errors database from 3 to build an exceptions
    database. This would hash the position ID to an entry, where an
    entry would contain the position ID and a fixed length array of
    probabilities. Use something like gperf to generate the hash
    function.

Now gnubg would do the following to get the OSR data for a position:

hash the ID, look it up in the exceptions databse. If it's found, you
have your data. If it's not present, look it up in the mean/std
database and create the data from that.

The cost of the hash file lookup should be very low - it involves one
seek and read of the exceptions file. 

This would be a hugely compute intensive task with some interesting
sub-problems - are there any good merge sort utilities for Unix? How
would gperf do at producing a hash function from say 100K large keys? 
What would we use for an error metric? Max (sum-of-squares (clearance),
sum-of-squares (save gammon))? Would we want to make it more sensitive
to single erroneous values by using something more than the square of
the error?


-- 
Jim Segrave           address@hidden