[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-gnubg] Re: more on bearoff databases
From: |
Jim Segrave |
Subject: |
Re: [Bug-gnubg] Re: more on bearoff databases |
Date: |
Mon, 28 Oct 2002 11:42:59 +0100 |
User-agent: |
Mutt/1.4i |
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