[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Bug-gnubg] Bug in makebearoff when building db w/o gammons
From: |
Øystein Johansen |
Subject: |
Re: [Bug-gnubg] Bug in makebearoff when building db w/o gammons |
Date: |
Fri, 06 Mar 2009 18:34:06 +0100 |
User-agent: |
Thunderbird 2.0.0.19 (Windows/20081209) |
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