This section describes what kind of bearoff databases you can use with gnubg as well as how you may obtain these.

Introduction to bearoff databases
=================================

There are two kind of bearoff databases: two-sided (exact) bearoff databases or one-sided (approximative) bearoff databases.

Two-sided bearoff databases
---------------------------

Two-sided bearoff databases contain exact probabilities or equities for winning.

For example, for less than 6 chequers inside the home quadrant, each side has 924 different positions, for a total of 924 * 924 = 853,776 positions possible. The bearoff database will contain the exact winning probability for each of these 853,776 positions. Typically, the database also includes cubeful equities for money game. Cubeful equities for match play is generally not included as it is dependent on match score and cube level.

Consider the following position:

      GNU Backgammon  Position ID: CgAAEAEAAAAAAA
                      Match ID   : cIkMAAAAAAAA
      +13-14-15-16-17-18------19-20-21-22-23-24-+     O: gnubg
      |                  |   |          O  O    | OOO 0 points
      |                  |   |                  | OOO
      |                  |   |                  | OOO
      |                  |   |                  | OO
      |                  |   |                  | OO
     v|                  |BAR|                  |     (Cube: 1)
      |                  |   |                  | XX
      |                  |   |                  | XX
      |                  |   |                  | XXX
      |                  |   |                  | XXX On Roll
      |                  |   |    X        X    | XXX 0 points
      +12-11-10--9--8--7-------6--5--4--3--2--1-+     X: jth

Using a two-sided bearoff database will yield that player X has 67.1% cubeless chance of winning. The database also gives cubeful money equities of +0.3441, +0.3210, and +0.1605 for X owning cube, centred cube, and O owning cube, respectively. So it's an initial double since +0.3210 >= 2 * +0.1605. However it's not a redouble since +0.3441 >= 2 * 0.1605.

The major problem with two-sided databases is that the size increases incredible fast with the number of points and chequers:

Chequers
Points
Number of positions
6           6          853,776
7           6          2,944,656
8           6          9,018,009
...
15          6          2,944,581,696
...
15          24         18,528,584,051,601,162,496

gnubg stores the equity for each position with a precision of approximately 0.00003 which requires 2 bytes of storage. Hence, storing one cubeless and three cubeful equities requires a total of 8 bytes per position. This gives the following storage requirements for n chequers inside the home quadrant:

Chequers
Points
Number of positions
Size/MB
6           6          853,776          6
7           6          2,944,656        22
8           6          9,018,009        68
9           6          25,050,025       191
10          6          64,128,064       489
11          6          153,165,376      1,168
12          6          344,622,096      2,629
13          6          736,145,424      5,616
14          6          1,502,337,600    11,461
15          6          2,944,581,696    22,465

For the typical user the limit is probably 10 or 11 chequers unless she owns vast amounts of disk space. Also, the time to generate these databases increases proportionally with the size. The 15 chequer database takes at least 3,500 times the time it takes to generate the 6 point database. For example, on the author's 1GHz Pentium III it takes approximately 6 minutes to generate the 6 points database, hence it would take at least 21,000 minutes or approximately 15 days to generate the 15 point database on the same computer.

One-sided bearoff databases
---------------------------

Instead of looking at both player's positions simultaneously large savings can be obtained by looking at each side independently. For each position we tabulate the probability P(n) what the player will bear all chequers off in n rolls; P(n) is the one sided bearoff distribution. Assume player 0 and player 1 has one sided bearoff distributions P0(n) and P1(n), respectively. The chance of player 0 bearing all chequers off before player 1 is:

p = sum(i=0 to infinity) P0(i) [ sum(j=i to infinity) P1(j) ]

For example, consider the following position:

      GNU Backgammon  Position ID: 2x0AAOi2AQAAAA
                      Match ID   : cAkAAAAAAAAA
      +13-14-15-16-17-18------19-20-21-22-23-24-+     O: gnubg
      |                  |   |       O  O  O  O | O   0 points
      |                  |   |       O  O  O  O | O
      |                  |   |       O  O       | O
      |                  |   |                  | O
      |                  |   |                  | O
     v|                  |BAR|                  |     (Cube: 1)
      |                  |   |                  | X
      |                  |   |                  | X
      |                  |   |             X    | X
      |                  |   |    X  X  X  X    | X   On roll
      |                  |   |    X  X  X  X  X | X   0 points
      +12-11-10--9--8--7-------6--5--4--3--2--1-+     X: jth

The one sided bearoff distributions are

Rolls   jth   gnubg
3    1.917%    2.811%
4   18.749%   28.403%
5   44.271%   50.307%
6   32.998%   18.114%
7    2.029%    0.363%
8    0.037%    0.002%

Applying the formula above gives:

1.917% * 100% + 18.749% * 97.189% + 44.271% * 68.786% ... + 0.037% * 0.02% = 56.7%

The cubeless gwc's calculated from one sided bearoff distributions are usually quite good, although no thorough investigations have been performed so far. Although the databases are one sided they can also give correct moves in ``desperation'' scenarios.

By storing the probability to bearoff at least one chequer, it's also possible to calculate gammon probabilities, as the chance of being gammoned is the probability that my opponent bears all chequers off before I bear at least one chequer off. Analogously, it's possible to calculate the chance of gammoning the opponent.

The storage requirements are much smaller than for the equivalent two sided databases.

Chequers
Points
Number of positions
15          6          54,264
15          7          170,544
15          8          490,314
15          9          1,307,504
15          10         3,268,870
15          11         7,726,160
15          12         17,383,860
15          13         37,442,160
15          14         77,558,760
15          15         155,117,250
15          16         300,540,195
15          17         565,722,720
15          18         1,037,158,320

For example, 15 chequers on 6 points is only 54,264 positions for the one sided bearoff database compared to 294,458,696 positions for the equivalent two sided bearoff database. However, for each position we need to store an array of probabilities. For example, for 15 chequers on the 18 point we have to store 15 non-zero probabilities compared to only one in the two sided bearoff database. The table below gives approximate database sizes for gnubg's one sided databases (both bearoff and gammon distributions):

Chequers
Points
Size in MB
15          6          1.4
15          7          5
15          8          15
15          9          42
15          10         112
15          11         284
15          12         682
15          13         1,543
15          14         approx 4,300
15          15         approx 10,700
15          16         approx 26,700
15          17         approx 66,700
15          18         approx 166,000

So, the practical limit is probably around the 11 to 13 point, depending on the disk space available.

gnubg can generate one sided bearoff database where the exact bearoff distribution is approximated by a normal distribution: instead of storing up to 15 or 20 non-zero probabilities only two parameters characterising the normal distribution has to be stored: the mean and the variance. The approximative distributions yields reasonably accurate gwc's and gammon probabilities compared to the exact one sided bearoff database. The size of the these approximative databases are roughly a quarter of the exact one, hence the limit is around the 13 to 15 point depending on the disk space available. The option to use approximative bearoff databases is work in progress!

As with the two sided bearoff databases it can be a rather time consuming task to generate one sided databases. The 10 point database takes approximately 2 hours to generate on the author's 1 GHz Pentium III. The 12 point database may more than one day!

Hypergammon databases
---------------------

gnubg can also play Hypergammon; a variant of backgammon with only 3 chequers, but with counting gammons and backgammons. The starting position is

      GNU Backgammon  Position ID: AACgAgAAKgAAAA
                      Match ID   : cAkAAAAAAAAA
      +13-14-15-16-17-18------19-20-21-22-23-24-+     O: gnubg
      |                  |   |          X  X  X |     0 points
      |                  |   |                  |
      |                  |   |                  |
      |                  |   |                  |
      |                  |   |                  |
     v|                  |BAR|                  |     (Cube: 1)
      |                  |   |                  |
      |                  |   |                  |
      |                  |   |                  |
      |                  |   |                  |     On roll
      |                  |   |          O  O  O |     0 points
      +12-11-10--9--8--7-------6--5--4--3--2--1-+     X: jth
     Pip counts: O 69, X 69

gnubg can also play the two-chequer and one-chequer variations as well. Although it looks very simple to play, Hypergammon is in fact quite difficult to play correctly.

There are 3,276 possible ways to distribute 3 (or less) chequers over 25 points (the 24 points plus the bar). This gives a total of 10,732,176 possible two sided positions. However, many these are illegal:

Position type
Number of positions
Game over           6,551
Race (no contact)   587,926
Contact             7,365,427
Illegal positions   2,772,272
Total               10,732,176

So there is close to 8 million legal positions for Hypergammon. Since this is a relative small number it's possible to tabulate the game winning chance, cubeless equity, or cubeful equities for all positions.

Due to the contact positions it is not possible to generate such a database in one run; instead the process is iterative: (a) ``guess'' equities for the 8 million positions, (b) use these equities to calculate 1-ply equities for all positions, and (c) if the equities change significantly then go back to step (c).

Bearoff databases with GNU Backgammon
=====================================

gnubg works with both one sided and two sided bearoff databases. Currently, it works with up to four databases; two of each kind. Two of the databases are read into memory for fast access, but of course these are limited to very small databases.

The one sided database kept in memory is either built-in or stored on disk as gnubg_os0.bd depending on the compile time option USE_BUILTIN_BEAROFF, which is most easily controlled by passing the option --enable-bearoff=TYPE where type is either no, static, or external. gnubg can also work without this database, but will generate a heuristic version every time the program starts. This can take up to several minutes, depending on the speed of your computer.

We recommend using an external file as the executable will be smallest possible, and several running instances of gnubg will share the memory if your system has mmap (memory mapping of files).

The standard size is 15 chequers on 6 points, but you may generate a larger one, but remember that the gnubg will read the file into memory. The default size should be adequate for all purposes.

The two sided database kept in memory (gnubg_ts0.bd) is optional and you may generate or download your own (see next section for details). gnubg will use the exact cubeful equities in the databases for cubeful money game evaluations and for truncation in money game rollouts (see (insert ref to rollout chapter)).

gnubg cannot directly use the equities for match play as the equities, in general, depend on the match score, cube value, and cube ownership. However, it's possible to calculate the cube efficiency parameter X from Rick Janowski's formulae from the cubeful money equities that are available. This is very important as the cube efficiency parameter often is very different from the range 0.6 and 0.68 that gnubg uses for long bearoffs and contact play, respectively. The calculated value of X is used in match play generalisation of Janowski's to yield cubeful match winning chances. gnubg uses a similar heuristic for Hypergammon (see below).

The two databases (gnubg_os.bd and gnubg_ts.bd) are kept on disk and accessed when needed. See next section for details on how to generate or download your own.

A few words of caution: the race neural net in gnubg is believed to be quite good, so it may not be worthwhile to generate large one sided database. Joseph Heled has published a comparison of chequer play decisions between the 0.13 race net and a one sided bearoff database for 15 chequers on 12 points. A total of 34,165 positions were examined, and the error rates were quite small:

Ply
Error rate/positions
Number of errors
Percentage of positions with errors
0     0.00025     3231     9.5
1     0.00032     3418     10.0
2     0.00002     1255     3.7

In order to play or analyse Hypergammon matches or session you need the databases hyper1.bd, hyper2.bd, and hyper3.bd for 1-chequer, 2-chequer, and 3-chequer (normal) Hypergammon. These databases contain the cubeless game winning chance, gammon, and backgammon probabilities (based on cubeless money play without Jacoby rule), and cubeful equities for money game: centered cube (with Jacoby rule), centered cube (without Jacoby rule), owned cube, and unavailable cube. For match play gnubg uses a similar heuristic to the usage of the two-sided bearoff database in match play for normal backgammon: the cube efficiency parameter X from Janowski's formulae are estimated from the cubeful money equities.

Each position requires 28 bytes of storage. For easy indexing of the file gnubg also use storage for the illegal positions. The table below shows the size of the Hypergammon databases.

Number of chequers
Number of positions
Size of file/bytes
1     676           19,968
2     123,201       3,449,668
3     10,732,176    300,500,968

Obtaining bearoff databases
===========================

Generate your own
-----------------

gnubg is supplied with a program makebearoff that is used to generate bearoff databases. Due to various limitations it is only possible to generate bearoff databases with a size less than 2GB, i.e., the 13pt one-sided database and the 11 chequer two-sided database are the largest databases that can be generated with makebearoff.

To generate one sided database issue

     makebearoff -o 10 -f gnubg_os.bd

to generate the one sided 10 point database. The program makebearoff uses a cache to store previously generated positions. You may set the cache size with the -s size option, e.g.,

     makebearoff -o 10 -s 123456789 -f gnubg_os.bd

to use 123,456,789 bytes of memory for cache size. In general, if the cache size is less than the size of the database to be generated, then extra time is needed to generate the bearoff database because some positions may have to be calculated several times.

makebearoff can also reuse previously generated databases, so if you already had generated the 9 point database you can reuse it:

     mv gnubg_os.bd gnubg_os9.bd
     makebearoff -o 10 -O gnubg_os9.bd -f gnubg_os.bd

Note that makebearoff requires temporary disk space to generate both one sided and two sided databases. In general, twice the disk space of the database to be generated is needed.

To generate a two sided database issue

     makebearoff -t 6x8 -f gnubg_ts.bd

This example will generate the 8 chequers on 6 points database. Again, it's possible to adjust the amount of memory with the -s option. It's recommended to set the cache size to the maximum amount of memory available (although there is no need to set it beyond the size of the bearoff database to be generated).

Other options for makebearoff are available, see makebearoff --help for the complete set.

At compile time the built-in one sided bearoff database is generated with the command

     makebearoff -o 6 | makebearoff1 -o br1.c

which generated a 6 point one sided bearoff database. The database is piped into makebearoff1 that generates the C code for the database. The resulting br1.c is more than 8MB, so it's not distributed with the source for gnubg.

The accompanying program makehyper is used to generate databases for Hypergammon. For example, to generate the 3-chequer database issue the command

     makehyper -c 3 -f hyper3.bd

Since the generation is very time consuming makehyper will generate a checkpoint file (in the example above: hyper1.bd.tmp) that can be used to restart the calculation if needed by using the -r option. You can also change the default convergence threshold of 0.00001 if you're happy with less accurate equities. To generate the 3 chequer database you need approximately 400 MB of free memory. On a 2.4 GHz box with 512 MB of RAM the calculation ran for 58 iterations of 3000 seconds each, i.e., a total of 48 hours!

See makehyper --help for the complete set of available options.

Download
--------

You may download the two sided database with 6 chequers on 6 points from ftp://alpha.gnu.org/gnu/gnubg/gnubg_ts0.bd.gz and the one sided database with 15 chequers 6 points from ftp://alpha.gnu.org/gnu/gnubg/gnubg_os0.bd.gz.

Later, other databases may be available for download or it may be possible to purchase these on CDROM or DVD for a nominal fee.

Verification of databases
-------------------------

To verify that your generated or downloaded bearoff database is correct, the table below lists the MD5 checksums for a number of possible databases.

One-sided bearoff databases (compressed)
........................................

The table below contains the MD5 checksums for the compressed one sided bearoff databases, i.e., databases generated with default options.

Chequers
Points
MD5 checksum
15          1          c789f049ec98ce4e307b471257999f39
15          2          b6e61c1625ae4b3b164e93ab064192b9
15          3          346dae6139ccb4b227c534373e5c52e4
15          4          653255f5f9f22fd50277f7ff25b2a343
15          5          2064f9a56b23117d053a573c96a92fa2
15          6          3dc7b833c4670849cee00479a9e21b49
15          7          67235c8e0ee152df5daf36cbeae5b3c2
15          8          a4acbb5c7e9e1f08e561afe0af934e5c
15          9          9c4ddab4e51c3e668c9c97b8f8768dbc
15          10         81b3898f06bbd08ee8295a839251a10a
15          11         78ecb4be86dab6af8755ea4063d50fb6
15          12         770fcff48894a96ebb2249343ef94866
15          13         cc74b69a62f6e648936f533838a527a8
15          14         not available
15          15         not available
15          16         not available
15          17         not available
15          18         not available

Two-sided bearoff databases (with cubeless and cubeful equities)
----------------------------------------------------------------

The table below contains the MD5 checksums for the default two sided bearoff databases.

Chequers
Points
MD5 checksum
1           6          7ed6f8e7fce16ea2b80e07a4a516653c
2           6          e9d760bf213841c285245ed757a52f4d
3           6          9d67da3db32ad4720cc38eecf9a67967
4           6          9156f37032d1d4b0352a41186e632dfc
5           6          0db19ab08feae1feb33ddbd709479f62
6           6          44b6040b49b46cb9dd2ce8caa947044d
7           6          9eb8b042d4d2ddf8d40e74a892745ad5
8           6          fcdbbc80b7ef84ddc81b839d0f26bed1
9           6          a11b2d410d51401143d05e73f9ffac15
10          6          12dc70c86f356d06bc96ee38dee40c62
11          6          not available
12          6          not available
13          6          not available
14          6          not available
15          6          not available

Two-sided databases for Hypergammon
...................................

As the generation of the Hypergammon databases are an iterative process it's not possible to give MD5 checksum for these, as it depend heavily on your convergence threshold, the number of restarts, and rounding errors.

Below is a random position from the database. The equities and percentages in your own database should be very similiar (if not identical):

      GNU Backgammon  Position ID: ADAAAQAkIAAAAA
                      Match ID   : cAkAAAAAAAAA
      +13-14-15-16-17-18------19-20-21-22-23-24-+     O: gnubg
      |       X     X    |   |                X |     0 points
      |                  |   |                  |
      |                  |   |                  |
      |                  |   |                  |
      |                  |   |                  |
     v|                  |BAR|                  |     (Cube: 1)
      |                  |   |                  |
      |                  |   |                  |
      |                  |   |                  |
      | O                |   |                  |     On roll
      | O                |   |             O    |     0 points
      +12-11-10--9--8--7-------6--5--4--3--2--1-+     X: jth

                  Player       Opponent
     Position         3018          2831

     Owned cube                    : -0.0230
     Centered cube                 : -0.2310
     Centered cube (Jacoby rule)   : -0.2186
     Opponent owns cube            : -0.3548

             Win     W(g)    W(bg)   L(g)    L(bg)   Equity  (cubeful)
     static: 0.456   0.244   0.014   0.318   0.019   (-0.168  (-0.219))

     No double           : -0.219
     Double, pass        : +1.000   (+1.219)
     Double, take        : -0.710   (-0.491)

     Correct cube action: No double, beaver