Node:Introduction to bearoff databases, Next:Bearoff databases with GNU Backgammon, Up:Bearoff databases
There are two kind of bearoff databases: two-sided (exact) bearoff databases or one-sided (approximative) 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.
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!
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).