Re: [Bug-gnubg] Bug in makebearoff when building db w/o gammons

[Øystein Johansen]

Christian Anthon wrote:
> On Sun, Mar 1, 2009 at 11:23 AM, Øystein Johansen <address@hidden> wrote:
>> For discussion:
>> For bearoff databases with gammon distributions, the db stores gammon
>> distributions for _all_ positions in the db. Even those positions where
>> a gammon is already saved. It uses only 2 bytes for such positions, but
>> I'm estimating that there is about > 20000 positions where there is no
>> gammon involved. Making a scheme to check for possible gammon and only
>> storing those distributions sounds trivial, but is it worth the effort?
>> If I commit such change, it will break compatibility with existing
>> bearoff databases, but the memory footprint will be 40-50Kb less. Is it
>> worth it?
>>
> 
> The gammons in the default race database is completely irrelevant, and
> even in the larger databases they are almost pointless, considering
> that the normal gammon-save races have a couple or more men starting
> on the opponents half of the board. Much more relevant would be to
> design a database with stragglers vs. an opponent in bearoff. But it
> might require some consideration to have the index right and avoid
> "holes" in the database and contact positions at the same time.

Yes! That was my initial idea for separating the two. I've already
separated the gnubg_os0.bd into two databases, one which gives the
bearoff distributions and one for giving the gammon distributions.

For the overall strength of gnubg, I don't think it will contribute much
to have a gammon distribution bearoff database on it's own, since the
race neural network is so strong and accurate. However, it makes some of
the code more general:

We have three distribution-databases: bearoff, gammon-save, and
race-backgammon. (Forget about two-sided databases since this type of
database is not a distribution database)
All these databases has one operation in common (common behaviour):
get_distribution()
What I was planning was to implement this a gtyped class, with the method:

void get_distribution( DistDB *db, gint *board, gushort *dist );

And then maybe a static method:
float calculate_prob( gushort *p0, gushort *p1 );

I have not coded all the details of this, but I believe it clearifies
the code a bit.

Back to the specific splitting of a compressed gnubg_os0.bd:
The original db contains 54264 positions.
First it's a header of 40 byte. Perfectly ok to me.
Then there is a index. The index entry for each position of 8 bytes.
The data following the index is 1031636 bytes containing bearoff and
gammon data for _all_ position. That is, a gammon distribution for
positions where the gammon is already saved is also included and will
take 2 bytes each.

The traditional compressed gammon bearoff database takes:
Header:                   40 byte
 Index: 54264 x 8 =   434112 byte
  Data:              1031636 byte  (905114 + 126522)
---------------------------------
                     1465788 byte

Considering if we split this into bearoff and gammon (15 checkers and 6
points), we need two indexes but each index entry needs only 6 byte.

For bearoff only:
Header:                   40 byte
 Index: 54264 x 6 =   325584 byte
  Data:               905114 byte
---------------------------------
                     1230738 byte

For the gammon part I only need to store the positions where there are
still 15 checkers left. 38760 position can be left out!

Gammon database:
Header:                   40 byte
 Index: 15504 x 6    = 93024 byte
  Data:                49002 byte (126522 - 38760*2)
---------------------------------
                      142066 byte

If I add these two sizes, I get 1372804 byte, only 92984 bytes less than
the original. Nothing to make a song and dance about, but considering
that this will have a higher potential for bigger databases, I consider
this ok.

(I will _not_ commit this code into the main cvs repository until I get
all the details working, and things go a bit slower these days, so don't
expect anything soon....)

-Øystein

signature.asc
Description: OpenPGP digital signature