[Bug-gnubg] Bearoff/Bearin database question

[Albert Silver]

Just out of curiosity, how exactly are the positions coded in the
databases? The reason I ask, is that it seems obvious that the most
economical manner possible is what is sought after and would be the key
for the smallest DB sizes. In chess, there are numerous ways to code a
position but clearly not everyone uses the same method. For example,
both Chess Assistant and Chessbase, the two largest chess software
producers, have tree building capabilities that allow users to make
position-based trees from large game databases. The trees allow users to
gather the statistics (win/loss, frequency, etc.) of all moves from a
large number of games (usually from 1.5-2.5 million games) enabling a
more methodical study. In Chess Assistant, such a tree would take about
2 hours to build from a 2 million game base, and take up to 1.6 Gb. In
contrast to illustrate how deeply this can change, an identical tree
made in Chessbase would take up to 24 hours, and take up 10-12 Gb. 

Similarly, in chess there are also endgame databases that are very much
like the bearoff-bearin databases being built in BG. They are designed
to provide perfect play and information on all moves included therein.
Again, the methodology used influences enormously on the size of the
bases. In all, no less than 4 different methodologies have been used,
each and every one improving on the previous. The first two, not
terribly different from each other were the Edwards and Thompson bases.
Then a couple of years ago, a Microsoft programmer, Eugene Nalimov,
specialized in compilers, devised a way that improved on the compression
by no less than 30-40%. That way, the full 3-4-5 piece endgame databases
*only* take up a little over 7 Gb. Although he owns the rights to the
scheme, he generously allows anyone to use it in their programs and even
sell CDs containing them, should they ask his permission. The 4th and
latest improvement comes from the author of the chess engine, King,
which powers the Chessmaster series. He has apparently improved on
Nalimov's technique and claims a 10-15% improvement in space. I only
relate this for those who do not know this, and to illustrate the
importance I perceive. 

For example, do all positions+material take up the same size, or do they
only code occupied spaces and pieces? I realize this is nothing new to
the authors, but by opening a discussion on how this is done, perhaps
improvements might be found.


                                        Albert