Papers on Backgammon
 Mathematics and Backgammon Bob Koca September 2010

### Introduction

This paper is based on a talk I gave as part of the Community College of Baltimore County (CCBC) mathematics colloquium. It covers examples of mathematics using backgammon that I have used in my classes. I gave the examples, how they relate to the class, and in some cases what more advanced mathematics or backgammon strategies could follow. In this paper I will sometimes give pointers to sources of more information.

In the talk I first played through a couple games quickly pointing out some basic rules and basic strategy as they arose, though my purpose was to just give an idea of what the game entails. In the classes it was enough to just play through an endgame with no contact pointing out the race aspect. Before giving the examples first some basic rules of backgammon and background on some of the CCBC math classes are given.

### Basic Backgammon Rules

For those new to the game a basic summary is that backgammon is a racing game.

From the following starting position:

``` +13-14-15-16-17-18------19-20-21-22-23-24-+
| X           O    |   | O              X |
| X           O    |   | O              X |
| X           O    |   | O                |
| X                |   | O                |
| X                |   | O                |
|                  |BAR|                  |
| O                |   | X                |
| O                |   | X                |
| O           X    |   | X                |
| O           X    |   | X              O |
| O           X    |   | X              O |
+12-11-10--9--8--7-------6--5--4--3--2--1-+
```

X moves counterclockwise and O moves clockwise according to the result of two dice. Once a player gets all 15 checkers in the home board (the lower right quadrant for X, and the upper right quadrant for O) the checkers can then be removed from the board. The first player to remove all of his checkers wins. The players moving in opposite directions gives the possibility of setting blocking formations to hinder the opponent's motion.

The checkers move according to the rolling of two dice. When moving you can land on a blank spot, where you have at least one checker, or where your opponent has a single checker. For example from the opening position suppose X has a 6-5 to play. A possible move is to play a checker from 24 to 18 with the 6 and then from 18 to 13 with the 5. Another is to play 24 to 18 with the 6 and 13 to 8 with the 5. Playing 24 to 19 with the 5 though is not allowed. When a player lands where an opponent has a single checker that checker is hit and must begin its progress home anew. It is placed on the bar in the middle of the board to indicate this and it must reenter before that player can move any other checkers.

Suppose that X has been hit (the checker on the bar indicates it is off the board and must reenter) and X is on turn in the following position.

``` +13-14-15-16-17-18------19-20-21-22-23-24-+
| X     X  O       |   | O     O          |
| X     X  O       |   | O     O          |
| X                |   | O                |
| X                |   |                  |
| X                | X |                  |
|                  |BAR|                  |
|                  |   |                  |
|                  |   |                  |
|                  |   | X                |
| O        O  X  O |   | X  X  O          |
| O        O  X  O |   | X  X  O          |
+12-11-10--9--8--7-------6--5--4--3--2--1-+
```

Suppose that X rolls a 4-6. The checker on the bar cannot enter with the 6 since the 19 point is owned by O. Similarly the checker on the bar cannot enter with the 4 since the 21 point is also owned by O. Since X cannot move until the checker on the bar enters he must forfeit any move.

Suppose that X rolls a 3-6. The checker must enter with the 3 going to the 22 and then the only legal 6 is to move from 8 to 2. Since it leaves a blot (single checker vulnerable to getting hit) and gives up a valuable blocking point, X would actually prefer to forfeit the 6 but the dice must be played if possible.

Suppose from this position that it is O's turn instead and that O rolls a 1-2. It is allowed to move the same checker twice but it must actually be able to move in two separate steps. Thus playing 19 to 22 (via 6 to 5 to 3) would be legal but playing 4 to 7 would not be.

For more on backgammon rules I suggest: http://www.bkgm.com/rules.html.

### Some CCBC Math Classes

Math 111, "Ideas In Mathematics," is a survey class which is often the last math class that non-science majors would take and covers set theory, probability, statistics, finance, and other optional topics.

Math 131, "Concepts of Mathematics I: Numeration Systems and Operations," and Math 132, "Concepts of Mathematics II: Geometry and Measurement" are classes for Elementary Education majors. Math 131 includes ways to think about numbers, why the basic calculation algorithms work, and alternative methods including mental math and estimation techniques. Math 132 includes symmetry.

Math 163, "Statistics," is a introductory noncalculus based statistics course.

Math 243, "Discrete Mathematics," is a class mainly for math and computer science majors and includes as topics counting problems, and recursive algorithms.

### Examples

#### Pip Counting

A pip count tallies the total that must be traveled to remove all checkers from play. For example in the following position the pip count for X can be calculated as 3 + 3 + 3 + 4 + 4 + 5 + ... ,

``` +13-14-15-16-17-18------19-20-21-22-23-24-+
|       O     O  O |   | O  O  O  O       |
|                O |   | O  O  O  O       |
|                O |   |    O     O       |
|                  |   |                  |
|                  |   |                  |
|                  |BAR|                  |
|                  |   |                  |
|                  |   |    X             |
|                X |   |    X     X       |
|                X |   | X  X  X  X       |
|    X           X |   | X  X  X  X       |
+12-11-10--9--8--7-------6--5--4--3--2--1-+
```

A faster way is to use the repeated addition model of multiplication and calculate

(3 × 3) + (2 × 4) + (4 × 5) + (2 × 6) + (3 × 7) + (1 × 11) = 81.

A clever method is to mentally shift the position to one in which X instead has 14 checkers on the 5 point and one on the 11 point. This does not change the pip count since the extra pips gained from shifting two checkers from the 4 to the 5 point is balanced by pips lost by shifting one from the 6 point to the 5 point. Similarly the shifts from the 7 and 3 points balance out. Instead of mentally doing the shifts one can see the visual symmetry of those 14 checkers around the 5 point. Thus, for those 14 checkers the average pip count per checker is 14. Having done this we can now calculate as

14 × 5 + 11 = 81.

The pip count for O can be done similarly but one can more quickly find it by using the 81 value determined for X and then adjust for how much O is ahead or behind. If we move O's checker on the 15 point back to the 14 point (increasing O's pip count by 1) and move the checker on the 17 point to the 20 point (decreasing O's pip count by 3) then the positions for X and O are identical. Thus O's pip count is 81 − 1 + 3 = 83.

In Math 131, I relate this to the idea that a calculation can be changed in a way that does not change the result. This idea can help explain both why some common techniques work and also why some mental math tricks work. For example when using the standard borrowing approach one thinks of 42 − 19 as (30 + 12) − (10 + 9). When adding 29 + 54 mentally one could instead think 30 + 53. In Math 132 I give this as an example of symmetry.

In Math 131 I also give pip counting as an example of positive and negative numbers.

After taking a pip count suppose I am up 8 pips. For the next rolls I can keep a running count. For example if my opponent then rolls 10 pips I add 8 + (−10) = −2 and I am now down 2 pips.

For advanced pip counting techniques I suggest: http://www.backgammon-biba.co.uk/PipCount.htm#totals

#### Probability

In Math 111, probability is covered including the theoretical probability formula for equally likely outcomes

P(E) = (# outcomes favorable to E) / (# outcomes),
the "OR" rules
P(A or B or C or ...) = P(A) + P(B) + P(C) + ...
for disjoint events and
P(A or B) = P(A) + P(B) − P(A and B)
for nondisjoint events, the "AND" rule
P(A and B) = P(A) · P(B given A)
and the complement rule
P(A) = 1 − P(not A).

I do a couple simple examples of theoretical probability based on the 36 equally likely dice rolls. For example, what is the chance of entering from the bar in the following position?

``` +13-14-15-16-17-18------19-20-21-22-23-24-+
|             O    |   | O     O     O  O |
|             O    |   | O     O     O  O |
|             O    |   |       O          |
|                  |   |                  |
|                  | X |                  |
|                  |BAR|                  |
|                  |   |                  |
|                  |   |                  |
| O                |   |             X  X |
| O                |   | X  X  X  X  X  X |
| O                |   | X  X  X  X  X  X |
+12-11-10--9--8--7-------6--5--4--3--2--1-+
```

I explain that all they need to know about backgammon is that this is the same as P(get at least one 3 or 5) when two dice are rolled. In the diagram the bold values are the favorable outcomes showing that P(at least one 3 or 5) = 20/36 = 5/9. A possibly quicker way to come to this conclusion is to see that the rolls that do no enter form a 4 by 4 grid and thus total 16. 36 − 16 = 20. Yet another way is to see that two columns and two rows are used giving 24. However 3-3, 3-5, 5-3, 5-5 are double counted so we obtain 24 − 4 = 20. Visualizing this table and seeing such patterns and structures can help for other situations as well.

 1-1 1-2 1-3 1-4 1-5 1-6 2-1 2-2 2-3 2-4 2-5 2-6 3-1 3-2 3-3 3-4 3-5 3-6 4-1 4-2 4-3 4-4 4-5 4-6 5-1 5-2 5-3 5-4 5-5 5-6 6-1 6-2 6-3 6-4 6-5 6-6

My final project in Math 111 involves a presentation on an area of math of the student's choosing. One of the options is to analyze strategy and probability from a game, and some choose backgammon. One question I ask to explain is the probability that X on roll wins in the following position.

``` +13-14-15-16-17-18------19-20-21-22-23-24-+
|                  |   |                O |
|                  |   |                O |
|                  |   |                O |
|                  |   |                O |
|                  |   |                  |
|                  |BAR|                  |
|                  |   |                  |
|                  |   |                X |
|                  |   |                X |
|                  |   |                X |
|                  |   |                X |
+12-11-10--9--8--7-------6--5--4--3--2--1-+
```

What needs to be known here about backgammon is that doubles (same value for each die) allows one to move the number 4 times and that any value here allows one to remove the checkers from the 1 point. For example if X rolls 5-3 X can remove two checkers. If X rolls 4-4, all 4 checkers can be removed winning the game immediately.

This can be seen as an OR problem. White can win immediately by rolling doubles (with probability 1/6). White can also win on his second turn by not rolling doubles and then opponent also not rolling doubles. White would then have only two checkers left and the win is guaranteed.

P(X wins)
 = P(X wins on first turn or on second turn) = P(X wins on first turn) + P(X wins on second turn) = P(X rolls doubles immediately) + P(X does not roll doubles and O does not roll doubles) = P(X rolls doubles immediately) + P(X does not roll doubles) × P(O does not roll doubles) = 1/6 + 5/6 × 5/6 = 31/36

Alternatively one could look at the probability that the opponent wins and subtract from 1.

 P(X wins)  = 1 − P(O wins) = 1 − P(X does not get a double and then O does get a double) = 1 − (5/6) × (1/6) = 1 − 5/36 = 31/36.

Another example from Math 111 is the expected total when two dice are rolled with doubles counting double (in backgammon when a double is rolled the player gets to play it 4 times). A distribution can be made:

 Total 3 4 5 6 7 8 9 10 11 12 15 20 24 Prob (×1/36) 2 3 4 4 6 5 4 2 2 1 1 1 1

For example to advance forward 6 pips the rolls could be 1-5, 2-4, 4-2, or 5-1. Note that 3-3 is a double and advances 12 instead of 6.

The expected value can then be calculated as

(2/36)(3) + (3/36)(4) + ...  =  81/6.
There is a clever way to calculate this which I don't cover in class. By symmetry, the expected value of 1 die is 3.5. Ignoring that doubles count twice gives a total of 7. 1/6 of the time doubles are rolled giving an extra 7 on average. 7 + 7/6  =  81/6.

Recursive Algorithms and a Counting Problem

Strategically it can be useful to know the distribution for number of turns a position takes to bearoff (remove all checkers from the board). For example, the following position (with only X shown) if played out will finish in one roll 19/36 of the time. (Good numbers are 6-2, 6-3, 6-4, 6-5, 5-2, 5-3, 5-4, 6-6, 5-5, 4-4, 3-3 and 2-2. Note that if the roll is not a double it really counts twice as 6-2 and 2-6 for example are both possible rolls.)

``` +13-14-15-16-17-18------19-20-21-22-23-24-+
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |BAR|                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |    X        X    |
+12-11-10--9--8--7-------6--5--4--3--2--1-+
```

The only way that it would require 3 turns is if 2-1 is rolled twice consecutively which has probability of 2/36 × 2/36 = 1/324. Four or more turns are never required.

This leaves 1 − (19/36 + 1/324) = 152/324 probability of being off in exactly 2 rolls. This gives an expected value of approximately 1.48 turns.

For positions further from completion the calculation is more complicated. Even the checker plays involved may be needed. A recursive algorithm as discussed in Math 243 can deal with this type of problem. If smaller instances of the problem are already known then others can be done. For example suppose a 2-1 is rolled in the following position:

``` +13-14-15-16-17-18------19-20-21-22-23-24-+
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |BAR|                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |       X          |
|                  |   | X  X  X  X       |
|                  |   | X  X  X  X     X |
+12-11-10--9--8--7-------6--5--4--3--2--1-+
```

If the smaller versions of the problem are known one can then look at the resulting positions for each legal play and choose the play that does best. Here that would be moving 4 to 2 and removing the checker on the 1 point with the 1.

By doing that for every roll the expected number of turns to bear off can be calculated as:

 E  = (1/36) × sum over the 36 rolls of expected number of remaining turns after best play has been made

If the smallest positions are started with and longer positions are ordered and built up in a good order, all such positions can be done.

Suppose that one wants to store in a computer the expected number of turns for every possible position in which all 15 of a player's checkers are either in the home board or already borne off. Is that feasible? We need to know how many such positions there are.

Counting techniques are also a topic in Math 243. One basic one is the combinations formula saying that if you are going to choose r items out of n items without repeats and that order does not matter then there are n!/(nr)!r! ways to do so. For example choosing a committee of 3 people from a group of 7 people fits this situation. It does not make sense to choose someone twice and since it is a committee (as opposed to say choosing a President, Vice president, and Treasurer) the order of the names does not matter. There are 7!/(3!4!) = 35 ways to choose the committee.

Suppose that you want to guess on a 5 question T-F exam giving exactly two T answers. This also fits a combinations problem. Of the 5 questions you choose which 2 to answer T to. The order that you choose those 2 questions does not matter. Putting a T for question 4, and the a T for question 3 results in the same answer sheet as if you put T for question 3 first and then T for question 4 next. You may want to check that you can give the 10 ways to do this.

(T T F F F is one such way). This level of problem is also done in Math 111 but in Math 243 we see how it can be applied in some clever ways.

A common problem goes something like: "Suppose you want to buy 15 pies. There are 7 flavors available. How many ways are there to do this?" Here the order does not matter. If you say for example that the first 4 pies are cherry and the rest blueberry you get an identical order of pies as if you had said that the first 11 are blueberry and the rest cherry.

The problem of how many bearoff positions with 15 checkers all either borne off or in the home board is mathematically the same as the one above. Replace pies with checkers and replace flavors with the 7 possible locations (the 1 though 6 points plus off the board). There is a trick to turn it into a simple combinations situation as seen previously.

Imagine placing 20 slashes and consider them as barriers. Note that 21 locations are formed with the far left and far right considered as locations along with locations bound on both sides by a slash.

| | | | | | | | | | | | | | | | | | | |

Next choose 6 of those locations to put a •. For example

| | | • | • | • | | | • | | | | | | • | | | | | • |

This can be associated with a bearoff position as follows.

Look at how many locations are empty before the first •, then look at empty locations between each group of two •s (possibly 0) and then at the number of locations after the last •. Here we obtain the list of numbers (3, 0, 0, 2, 5, 4, 1) and we can associate this with the number of checkers on the points from 6 to 1 with the last value being the number already borne off. It gives the position

``` +13-14-15-16-17-18------19-20-21-22-23-24-+
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |   |                  |
|                  |BAR|                  |
|                  |   |             X    |
|                  |   |             X  X |
|                  |   | X           X  X |
|                  |   | X        X  X  X |
|                  |   | X        X  X  X |   X (one checker off)
+12-11-10--9--8--7-------6--5--4--3--2--1-+
```

There is a one-to-one correspondence between such positions and the ways that we could have chosen to place the •s. But that is just a combinations problem. Of the 21 locations we chose which 6 to use. We obtain C(21, 6) = 54264.

There have been several papers written on ways of estimating the number of turns to bear off. Walter Trice's paper at http://www.bkgm.com/articles/EffectivePipCount/ suggests some very effective simple rules for certain position types. For more difficult positions Jean Luc Seret used neural net technology to derive an approximating function with several inputs: http://www.bkgm.com/articles/GOL/Dec00/pipples.htm.

#### Rollouts and Confidence Intervals

In the last few years many feel that the best backgammon playing computer programs have surpassed the world's best players. A neural net approach in which a computer learns by experience how to value certain aspects of a position has been key to the strong play of bots. For more on this topic I direct you to the paper Temporal Difference Learning and TD-Gammon by Gerald Tesauro which appeared in Communications of the ACM, March 1995 / Vol. 38, No. 3 and is available at:  http://www.bkgm.com/articles/tesauro/tdl.html.

Often there may be a decision that a player is not sure of and the player "asks the bot".

One way is to essentially just ask the bot its opinion. If time is available though a better answer can be obtained by doing a rollout. The computer plays the game out several thousand times and reports which play empirically does the best. Along with these results a confidence interval may be given. For example a rollout was done on which 4-1 play is preferable in the following position, 24/23, 13/9 or 13/9, 6/5. Results look like:

``` GNU Backgammon  Position ID: 4HPKATDgc/ABMA
Match ID   : MAEmAAAAAAAA
+12-11-10--9--8--7-------6--5--4--3--2--1-+     O: red
| X           O    |   | O              X |     0 points
| X           O    |   | O              X |     Rolled 41
| X           O    |   | O                |
|                  |   | O                |
|                  |   | O                |
|                  |BAR|                  |     1 point match(Cube: 1)
| O                |   | X                |
| O                |   | X                |
| O           X    |   | X                |
| O           X    |   | X              O |
| O  X  X     X    |   | X              O |     0 points
+13-14-15-16-17-18------19-20-21-22-23-24-+     X: black

1. Rollout          13/9 6/5                     Eq.:  -0.067
0.466 0.174 0.035 - 0.534 0.264 0.059 CL  -0.067 CF  -0.067
[0.004 0.005 0.004 - 0.004 0.007 0.005 CL   0.007 CF   0.007]
Full cubeful rollout with var.redn.
1293 games, Mersenne Twister dice gen. with seed 895636461
and quasi-random dice
Play: 0-ply cubeful prune [expert]
Cube: 0-ply cubeful prune [expert]
2. Rollout          24/23 13/9                   Eq.:  -0.073 ( -0.005)
0.464 0.177 0.032 - 0.536 0.239 0.037 CL  -0.073 CF  -0.073
[0.003 0.005 0.003 - 0.003 0.006 0.004 CL   0.006 CF   0.006]
Full cubeful rollout with var.redn.
1296 games, Mersenne Twister dice gen. with seed 895636461
and quasi-random dice
Play: 0-ply cubeful prune [expert]
Cube: 0-ply cubeful prune [expert]
```

The line in parentheses indicates the standard error. For example for the 13/9, 6/5 play the rollout predicts that the play will win 46.6% of the games but with a standard error of 0.4%. The 24/23, 13/9 play wins 46.4% of the games with a standard error of 0.3%. The win percentages are close enough and the standard errors are large enough that there is not high confidence in the result.

In Math 163 Statistics I use this as an example of how the confidence intervals indicate there is a decent chance that the play which is on top might not actually be the best play and that it gives a measure of uncertainty due to a sample of a finite size being used.

There is a lot more going on which goes beyond the level of Math 163. There are several clever ways to reduce variance and make the number of trials effectively a larger value.

Frederick Dahl developed a way that involves using estimates of luck to adjust the results in an unbiased way. A good summary of the technique and why it works is given by David Montgomery at:  http://www.bkgm.com/articles/GOL/Feb00/var.htm.

### Concluding Remarks

There are many more situations on backgammon where interesting math can be used.

Here I restricted myself to ones that I have used in the Freshman and Sophomore level mathematics classes which I teach. Even with no interest in backgammon, the students can see how these are real life (at least to me) applications of the material.