Appendix

GNU Backgammon works with many different kinds of equities. The equity is defined as the expected value of the position. However, this value can be expressed in several different metrics and may be calculated with or without taking the effect of the cube into consideration. In the following section we will describe the equities used and calculated by GNU Backgammon.

This is the value of the position in money game, e.g., if your equity is +0.4 an you are playing money game with a $1 stake, you will win $0.40 on average. The money equity can be calculated with or without taking the effect of the doubling cube into consideration, or cubeful or cubeless. The cubeless equity can be calculated from the basic formulae: 2*p(w)-1+2(p(wg)-p(lg))+3(p(wbg)-p(lbg)). Evaluating the cubeful equity is much more difficult; it can either be estimated from the cubeless equitity by using transformations as outlined by Rick Janowski or by constructing a neural net that directly outputs cubeful equities. GNU Backgammon uses the former approach.

In match play we’re generally not particular interested in the outcome of the individual games as much as the outcome of the entire match, so the interesting quantity for match play is match winning chance (MWC). As for the money equity the MWC can be calculated with and without the effect of the doubling cube. The MWCs are generally calculated with the use of a match equity table, which contains the chance of winning the match before a game starts, e.g., if the score is 0-0 in a 1pt match each player has 50% chance of winning the match before the game starts assuming they’re of equal skill.

The cubeless MWC is calculated as: MWC(cubeless) = p(w) * MWC(w) + p(l) * MWC(l) + p(wg) * MWC(wg) + p(lg) * MWC(lg) + p(wbg) * MWC(wbg) * p(lbg) * MWC(lbg).

For example, if the w/g/bg distribution is 0 30 60 - 40 10 0 and the match score is 1-3 to 5 with the cube on 2 the cubeless MWC is:

MWC(cubeless)= 30% * 50% + 30% * 0% + 30% * 100% + 10% * 0% + 0% * 100% + 0% * 0% = 45%,

so the cubeless MWC is 45%.

Evaluating the cubeful MWC is more difficult, and as for the cubeful money equity it’s possible to estimate cubeful MWCs from transformation on the w/g/bg distribution or directly calculate it from neural nets. GNU Backgammon uses the former approach, but the formulae are currently not published.

It’s generally very difficult to compare MWCs. For example, it’s hardly worth mentioning a 0.5% MWC error at DMP where as it’s a huge error at 0-0 to 7. It is therefore of interesting to normalise the MWCs to some common scale. The most often used normalisation is Normalised Money Game Equity (NEMG) where the MWC for any game is transformed into the same interval as money game, i.e., -3 to +3 (due to anomalies at certain match scores the NEMG can go below -3 and above +3). The transformation is linear:

NEMG = 2 * (MWC-MWC(l))/(MWC(w)-MWC(l)) - 1

In other words, extrapolation with the following two extrapolation points: (MWC(w),+1) and (MWC(l),-1).

For example, suppose the score is 3-1 to 5 with the cube on 2: MWC(l)=0% and MWC(w)=50%:

Note that a w/g/bg distribution of 0 100 100 - 0 0 0 gives a NEMG of +3 whereas the corresponding money equity is only +2. This is because the gammon price is high for that particular score. When both players are far from winning the match, e.g., 0-0 to 17 or 1-0 to 17, NEMG is very close to the ususal money equity.

NEMG can be calculated from both cubeless and cubeful MWCs.

A word of caution: A cubeless NEMG calculated from a cubeless MWC could be named “cubeless equity”, but in most backgammon litterature this term seems to be reserved for the cubeless money equity.

This chapter is a brief description of how GNU Backgammon calculates cubeful equities. The formulae build directly on the work by Rick Janowski Take-Points in Money Games from 1993.

The basic formulae for cubeful equities as derived by Janowski is

E(cubeful) = E(dead) * (1-x) + E(live) * x,

where E(dead) is the dead cube equity (cubeless equity) calculated from the standard formulae. E(live) is the cubeful equity assuming a fully live cube. We’ll return to that in the next section. x is the cube efficiency. x=0 gives E(cubeful)=E(dead) as one extreme and x=1 gives E(cubeful)=E(live) as the other extreme. In reality x is somewhere in between, which typical values around 0.6 - 0.8.

Janowski’s article doesn’t mention cubeful equities, so we use the straightforward generalisation

MWC(cubeful) = MWC(dead) * (1-x) + MWC(live) * x.

as MWC is the entity that is used for match play evaluations.

The live cube equity is the equity assuming that the equity changes continuously, so that doubles and takes occurs exactly at the double point and take point. For gammonless play this is the well-known take point of 20%. Janowski derives the more general formula

TP = (L-0.5)/(W+L+0.5)

where W is the average cubeless value of games ultimately won, and L is the average cubeless value of games ultimately lost. For example, for the following position

GNU Backgammon evaluates

and hence W=(0.454 + 0.103 + 0.001)/0.454=1.229 and L=(0.556+0.106+0.003)/0.556) = 1.196. For gammonless positions, e.g., a race, W=1 and L=1.

The live cube equity is now based on piecewise linear interpolation between the points (0%,-L), (TP,-1), (CP,+1), and (100%,+W): if my winning chance is 0 I lose L points, at my take point I lose 1 point, at my cash point I cash 1 point, and when I have a certain win I win W points:

For match play there is no simple formula, since redoubles can only occur a limited number of times.

The live cube take point is generally calculated as

TP(live, n Cube)=TP(dead, n cube) * (1 - TP(live, 2n cube)

So to calculate the live cube take points for a 1-cube at 3-0 to 7 we need the live cube take points for the 4-cube and the 2-cube. For the position above and using Woolsey’s match equity table the live cube take point are:

The calculation of these are left as an exercise to the reader.

Ignoring backgammons, the gammon rates for White and Black are 0.106/54.6=19% and 0.103/0.454=22%, respectively. If White wins the game his MWC will be

81% * MWC(-3,-7) + 19% * MWC(-2,-7) = 78%

and if Black wins his MWC will be

78% * MWC(-4,-6) + 22% * MWC(-4,-5) = 41%.

If White cashes 1 point he has MWC(-3,-7)=76% and if Black cashes he has MWC(-4,-6)=36%. Analogous to money game the live cube MWC is calculated as piecewise linear interpolation between (0%,22%), (24.5%,24%), (72.7%,36%), and (100%,41%) (from Black’s point of view):

Figure: Fully live cubeful MWC

Having established the live cube equities and MWCs we’re now in position to calculate the 0-ply cubeful equities.

Let’s start with money game: the cubeless equity is -0.097 and the live cube equity can be determined from the figure above as -0.157. Thus, the cubeful equity is -0.138.

For the match play example at the score 3-0 the cubeless MWC is 29.1% and from the figure Black using wins=45.4% we can determine the live cube MWC to be 29.2%. Using a value of x=0.68 we arrive at a cubeful MWC of 29.17%.

The previous section concerned the calculation of 0-ply cubeful equities, so how so GNU Backgammon calculate cubeful 2-ply equities? The answer is: by simple recursion:

   Equity=0
   Loop over 21 dice rolls
      Find best move for given roll
      Equity = Equity + Evaluate n-1 ply equity for resulting position
   End Loop
   Equity = Equity/36
   

Note that evaluating the n-1 ply equity involves a cube decision, since the opponent may double, so GNU Backgammon will actually calculate the two n-1 ply equities: (a) assuming no double, and (b) assuming double, take. These two equities are combined with the equity for a pass, and the optimum of these three is added to the resulting equity. For a cubeful 2-ply evaluation GNU Backgammon will end up calculating the following cubeful 0-ply equities: centred 1-cube, opponent owns 2-cube, owned 4-cube, and opponent owns 8-cube.

Note that the 2-ply level does not use the cube efficiency, it’s not used until at the 0-ply level, but it’s possible to calculate an effective one by isolating x in the basic cube formulae:

x(eff) = (E(2-ply cubeful) - E(2-ply dead))/(E(2-ply live)-E(2-ply dead)).

The cube efficiency is obviously an important parameter, unfortunately there haven’t been much investigation carried out, so GNU Backgammon basically uses the values 0.6-0.7 originally suggested by Rick Janowski:

For race GNU Backgammon uses linear interpolation based on pip count for the player on roll. A pip count of 40 gives x=0.6 and 120 gives x=0.7. If the pip count is below 40 or above 120 values of x=0.6 and x=0.7 are used, respectively.

For the two sided bearoff positions the cubeful money equity is already available from the database, so for money game there is no need to calculate cubeful equities via Janowski’s formulae. However, the cubeful equities for money game cannot be used for match play. Instead of using a fixed value of x, say, 0.6, GNU Backgammon will calculate an effective value based on the cubeful money equity. The cubeful MWC is calculated as usual, but with the calculated x.

There is obviously room for improvements. For example, holding games should intuitively have a lower cube efficiency, since it’s very difficult to double effectively: either it’s not good enough or you’ve lost the market by a mile after rolling a high double or hitting a single shot. Similarly, backgames will often have a low cube efficiency, whereas blitzes have may have a higher cube efficiency.

GNU Backgammon’s cube decisions are simple based on calculations of cubeful equities. For a double decision GNU Backgammon calculates the cubeful equity for “no double” and the cubeful equity for “double, take”. Combined with the equity for “double, pass”, it’s possible to determine the correct cube action.

The figure below shows the relevant cubeful equities for White and Black’s cube decisions in sample position from earlier.

Figure: Cubeful equities

On 0-ply Black will double when the green curve (White owns 2-cube) is above the red curve (centered cube), and White will take as long as the green curve is below 1. Similarly, White will double when the blue curve (Black owns 2-cube) is below the red curve (centered cube), and Black takes as long as the blue curve is above -1.

Note that GNU Backgammon doesn’t calculate the take point or double point explicitly. The cube decision is simply made by comparing equities from the figure.

Janowski has developed two other models for cubeful equities. The first is a generalisation of the one used by GNU Backgammon; it introduces two cube efficiencies instead of one. Often you may see that the cube efficiencies are different for the two players, and the refined general model as it is named by Janowski, tries to take this into consideration by using different cube efficiency parameters for the two players. For example, the blitzer may have another cube efficiency that the blitzee.

The second model is not published, but redefines the cube efficiency into a value that can be understood more intuitively and calculate easily from rollouts.

This section describes a method for compactly recording a backgammon position. It demonstrates how to encode a position into 10 binary bytes, which is useful for minimising the space used when recording large numbers of positions in memory or on disk. There is also an ASCII representation in 14 characters, which is convenient for output to the screen, for copying and pasting to transfer positions between programs which support the format, and for communicating positions via Usenet news or e-mail. The 10 byte binary format is called the key, and the 14 character ASCII format is the ID.

The key is essentially a bit string (imagine you start with an empty sequence of bits, and continue adding either “0” or “1” to the end). The way to build up a sequence that corresponds to a given position is:

1. For every point around the board (starting at the ace point of the player on roll, continuing around to the 24 point and ending at the bar):
   1. append as many 1s as the player on roll has on that point (if any).
   2. append a 0.
2. For every point around the board (starting at the ace point of the opponent, continuing around to the opponent’s 24 point and ending at the bar):
   1. append as many 1s as the opponent has on that point (if any).
   2. append a 0.
   3. Pad out the string to 80 bits with 0s.

The worst-case representation will require 80 bits: you can see that there are always 50 0 bits even if there are no chequers at all. Each player has a maximum of 15 chequers in play (not yet borne off) which require a 1 bit wherever they are positioned. That’s 30 bits to take of all chequers, plus the 50 bits of overhead for a total of 80 bits (the last bit is always 0 and isn’t strictly necessary, but it makes the code slightly easier). This bit string should be stored in little-endian order when packed into bytes (ie. the first bits in the string are stored in the least significant bits of the first byte).

As an example, here’s what the starting position looks like in the key format:

so altogether it’s:

00000111110011100000111110000000000011000000011111001110000011111000000000001100

In little endian bytes it looks like:

so the 10 byte key (in hex) is E0 73 F0 01 30 E0 73 F0 01 30.

The ID format is simply the Base64 encoding of the key. (Technically, a Base64 encoding of 80 binary bits should consist of 14 characters followed by two = padding characters, but this padding is omitted in the ID format.)

To continue the above example, splitting the 10 8-bit bytes into 14 6-bit groups gives:

111000 000111 001111 110000 000000 010011 000011 100000 011100 111111 000000 000001 001100 000000

In Base64 encoding, these groups are respectively represented as:

4 H P w A T D g c / A B M A

So, the position ID of the chequers at the start of the game is simply:

4HPwATDgc/ABMA

You can set the board in gnubg either by writing the position ID into the position text input field in the GUI or by executing the command

set board 4HPwATDgc/ABMA.

• This encoding is obviously not as compact as it could be: in particular, there are lots of redundant representations of illegal positions where both players have chequers on the same point. Theoretically, it would be possible to get it down to 64 bits by using D() expressions, but I think you’d have to be a mathematical masochist to try it!
• Example code to convert between a raw board encoding (the number of chequers on each point) and these keys/IDs is available licensed under GPL.
• Thanks to Tom Keith and David desJardins for their suggestions on simplifying the encoding without increasing the worst case length.

This section describes how the match ID is calculated. The match ID can be used for easy exchange of positions for gnubg users in conjuction with the position ID. The match key is a 9 byte representation of the match score, match length, value of cube, owner of cube, Crawford game flag, player on roll, player to make a decision, doubled flag, resigned flag, and the dice rolled. The match ID is the 12 character Base64 encoding of the match key. Match key

The match key is a bit string of length 66:

1. Bit 1-4 contains the 2-logarithm of the cube value. For example, a 8-cube is encoded as 0011 binary (or 3), since 2 to the power of 3 is 8. The maximum value of the cube in with this encoding is 2 to the power of 15, i.e., a 32768-cube.
2. Bit 5-6 contains the cube owner. 00 if player 0 owns the cube, 01 if player 1 owns the cube, or 11 for a centered cube.
3. Bit 7 is the player on roll or the player who did roll (0 and 1 for player 0 and 1, respectively).
4. Bit 8 is the Crawford flag: 1 if this game is the Crawford game, 0 otherwise.
5. Bit 9-11 is the game state: 000 for no game started, 001 for playing a game, 010 if the game is over, 011 if the game was resigned, or 100 if the game was ended by dropping a cube.
6. Bit 12 indicates whose turn it is. For example, suppose player 0 is on roll then bit 7 above will be 0. Player 0 now decides to double, this will make bit 12 equal to 1, since it is now player 1’s turn to decide whether she takes or passes the cube.
7. Bit 13 indicates whether an doubled is being offered. 0 if no double is being offered and 1 if a double is being offered.
8. Bit 14-15 indicates whether an resignation was offered. 00 for no resignation, 01 for resign of a single game, 10 for resign of a gammon, or 11 for resign of a backgammon. The player offering the resignation is the inverse of bit 12, e.g., if player 0 resigns a gammon then bit 12 will be 1 (as it is now player 1 now has to decide whether to accept or reject the resignation) and bit 13-14 will be 10 for resign of a gammon.
9. Bit 16-18 and bit 19-21 is the first and second die, respectively. 0 if the dice has not yet be rolled, otherwise the binary encoding of the dice, e.g., if 5-2 was rolled bit 16-21 will be 101-010.
10. Bit 22 to 36 is the match length. The maximum value for the match length is 32767. A match length of zero indicates that the game is a money game.
11. Bit 37-51 and bit 52-66 is the score for player 0 and player 1 respectively. The maximum value of the match score is 32767.
12. Bit 67 is the Jacoby flag : 0 for Jacoby “On” and 1 for Jacoby “Off” [Added April 1st, 2011] (It’s possible for the Jacoby flag to be 0 and Crawford flag to be 1 with old MatchID’s. Sanity checks on this bit should exclude testing for Crawford being 1 and Jacoby being 0 to maintain backwards compatibility with older software)

For example, assume the score is 2-4 in a 9 point match with player 0 holding a 2-cube, and player 1 has just rolled 52. The match key for this will be (note that the bit order is reversed below for readability)

1000 00 1 0 100 1 0 00 101 010 100100000000000 010000000000000 001000000000000

In little endian the bytes looks like:

01000001 10001001 00101010 00000001 00100000 00000000 00100000 00000000 00

0×41 0×89 0×2A 0×01 0×20 0×00 0×20 0×00 0×00

Analogous to the position ID from the previous section the match ID format is simply the Base64 encoding of the key.

To continue the example above, the 9 8-bit bytes are grouped into 12 6-bits groups:

010000 011000 100100 101010 000000 010010 000000 000000 001000 000000 000000 000000

In Base64 encoding, the groups are represented as:

Q Y k q A S A A I A A A

So, the match id is simply:

QYkqASAAIAAA

If someone post a match ID you can set up the position in gnubg by writing or pasting it into the Match ID text input field on the main window, or by executing the command

set matchid QYkqASAAIAAA.