Academic Papers

---

Introduction

In tournament backgammon, the objective is to win a specified number of points V before one's opponent wins V. (V is typically anywhere from 11 to 25.) Each game is initially worth 1 point. During the course of a 1-point game, either player may double the stakes before rolling his dice. If A doubles to 2, then B may either concede 1 point to A and start a new game or agree to play the existing game for 2 points. If B elects to play on then only he may redouble. Suppose that B decides to play and eventually redoubles to 4. Then A may either give B  2 points or play on for 4. If A decides to continue then only he may redouble, etc. There is no limit to the number of doubles. However, once the value of any game exceeds V doubling becomes irrelevant.

Gammons

It is possible for a player to win a gammon, or double-game, meaning that he wins  2K  points if the value of the game is  K.  We will not consider the possibility of a triple-game or "backgammon" because these are rare.

The Crawford Rule

In tournament play the Crawford Rule is almost always used. This rule says that when either player reaches a score of  V − 1  the other player may not double for one game. He may double after that game (assuming he wins it). Thus, suppose A needs 3 and B needs 4. A wins a 2 game, se he needs 1 and B needs 4. During the next game B may not double. If he wins, he will need 3 unless he gammons A and may double during any remaining game. Note that it is to B's advantage to double immediately whenever possible when A needs only 1 point.

Continuous Time Markov Approximation

Let  p(t)  denote the probability that player A will win a given game, assuming that neither player may double. If  p(t)  is a continous function of time, we call the game continuous. In backgammon,  p(t)  is not continuous since it is defined only on nonnegative integers and may jump considerably from one move to the next. We begin by assuming that  p(t)  is continuous and then make modifications to account for its actual discontinuity. The following lemma is from [1].

Example 1.  Suppose that  x = 0.75.  Then the probability that A wins  (p = 1  before  p = 0)  is  0.75 / 1 = 0.75. 

Example 2.  Suppose that  x = 0.6.  Then the probability that  x = 0.8  before  x = 0  is  0.6 / (0.6 + 0.2) = ¾. 

Lemma 1 may be extended to any linear function of  p(t),  such as A's expectation. In other words, the probability that A's expectation rises by  b  before it falls by  a  is also  a / (a + b). 

It is shown in [1] that in a continuous game A should double or redouble when  p = 0.8.  When A doubles, it does not matter whether B accepts or declines, his expectation in both cases is  −K,  where  K  is the value of the game before the double. To see this, observe that if B accepts, he will own the doubling cube at  2K.  He will win by reaching  p = 0.2  before  p = 1.  Using Lemma 1, his probability of winning is  0.2 / (0.6 + 0.2) = ¼.  Therefore, his expectation is  ¼(2K) − ¾(2K) = −K.  This is exactly what he would lose if he did not accept the double.

Note that A's chances of winning when  p(t) = 0.8  are 0.8 assuming that neither player may double. If B owns the cube then A's chances are 0.75.

In a tournament game, the optimal doubling strategy for each player depends on the score of the match and the current value of the game. Let A_i(x₁, x₂) denote player i's chances of winning the match at the start of a new game when player 1 needs x₁, player 2 needs x₂, and x₁ ≥ 2, x₂ ≥ 2. When x₁ or x₂ = 1, it is possible that the player who is behind may not be able to double for one game because of the Crawford Rule. Let B_i(x₁, x₂) denote player i's chances when the underdog cannot double in the present game (but can in future ones). Let B_i(x₁, x₂) denote player i's chances when the underdog can double. Let y denote player 1's chances of winning a game and let gy denote his chances of winning a gammon. Then we have

B1(1, 1) = y,
B1(2, 1) = gy + (y − gy)y,
B1(1, 1) = y,	(1)
B1(2, 1) = y  (because player 1 will double immediately),
B1(3, 1) = gy + (y − gy)y  (because player 1 will double immediately),
B1(4, 1) = gy + (y − gy)y  (because player 1 will double immediately),

and, in general,

B1(x1, 1) = gyB1(x1 − 4, 1) + (1 − g)yB1(x1 − 2, 1),  and
B1(x1, 1) = gyB1(x1 − 2, 1) + (1 − g)yB1(x1 − 1, 1).	(2)

B₁(1, x₁) and B₁(1, x₁) are obtained from (1) and (2) by replacing y by 1 − y.

When the state of the match is (x₁, x₂, K) (K represents the value of the current game), there will be some point in the current game at which player 1's (2's) advantage will be such that he can double and it will not matter whether his opponent takes or not. This point is called the minimum take point for player 2 (1). Let D₁(x₁, x₂, K) denote player 1's chances of winning at the minimum take point for player 2, assuming that neither player may double. (In nontournament play, assuming the game is continuous, D_i(–, –, K) = 0.80 ∀K, and for i = 1, 2.)  Let D₁(x₁, x₂, K) denote player 1's chances of winning at the minimum take point for player 2, given that his opponent may double. (In nontournament play  D_i(–, –, K) = 0.75 ∀K, i, whether the game is continuous or not.)

If a player's chances of winning after doubling are D(x₁, x₂, K) let G₁ · D(x₁, x₂, K) denote his chances of winning a gammon. G₁ is a scalar which represents the fraction of wins that are gammons and will vary depending on the position. (In a straight race G₁ = 0.) Let G₂ · (1 − D(x₁, x₂, K)) denote the probability that the player accepting the double wins a gammon. In general, G₁ > G₂, since the player who accepts the double will often redouble instead of playing for the gammon.

When x₁ > 2K and x₂ > 2K, D₁(x₁, x₂, K) is determined by the condition that player 1's probability of winning the match is the same whether player 2 takes or drops. Stating this mathematically, and letting D₁ represent D₁(x₁, x₂, K), we have

G1D1 · A1(x1 − 4K, x2)
+ (1 − G1)D1 · A1(x1 − 2K, x2)
+ G2(1 − D1) · A1(x1, x2 − 4K)
+ (1 − G2)(1 − D1) · A1(x1, x2 − 2K)	=  A1(x1 − K, x2).	(3)

Solving (3) for D₁ we obtain

D1(	G1A1(x1 − 4K, x2)
	+ (1 − G1)A1(x1 − 2K, x2)
	− G2A1(x1, x2 − 4K)
	− (1 − G2)A1(x1, x2 − 2K)	)  =	A1(x1 − K, x2)
			− G2A1(x1, x2 − 4K)
			− (1 − G2)A1(x1, x2 − 2K),	(4)

or  D₁(x₁, x₂, K)  =

A1(x1 − K, x2) − G2A1(x1, x2 − 4K) − (1 − G2)A1(x1, x2 − 2K) G1A1(x1 − 4K, x2) + (1 − G1)A1(x1 − 2K, x2) − G2A1(x1, x2 − 4K) − (1 − G2)A1(x1, x2 − 2K)

(5)

A similar expression may be determined for D₂ and is  D₂(x₁, x₂, K)  =

A2(x1, x2 − K) − G2A2(x1 − 4K, x2) − (1 − G2)A2(x1 − 2K, x2) G1A2(x1, x2 − 4K) + (1 − G1)A2(x1, x2 − 2K) − G2A2(x1 − 4K, x2) − (1 − G2)A2(x1 − 2K, x2)

(6)

When x₁ ≤ 2K and x₂ > 2K, player 2 will redouble immediately after player 1 doubles and rolls since player 1 needs at most 2K points. Therefore, when x₁ ≤ 2K and x₂ > 2K, (5) should be adjusted by substituting 2K for all occurrences of K, except in the term A₁(x₁ − K, x₂), which remains unchanged. The same adjustment should be made to (6) except for the term A₂(x₁, x₂ − K).

For x₁ or x₂ ≤ 2K, we have  D₁(x₁, x₂, K) = D₁(x₁, x₂, K),   since no additional doubles will be made after the first one, except possibly an automatic redouble made by the player who is behind. (The equation  D₁ = D₁  is still correct for this case.)

Suppose now that  x₁ > 2K,  x₂ > 2K.  Recall that  p(t)  denotes player 1's chances of winning at time  t  assuming there is no cube. If player 1 doubles at  p(t) = D₁(x₁, x₂, K),  he will have to reach  p(t) = 1  to win before his opponent reaches  p(t) = 1 − (D₂(x₁, x₂, 2K) + Δ).  (The Δ is a correction factor to take into account the fact that the game is not continuous, and is a function of the board position.)

Therefore, using Lemma 1, and recalling that  D₁(x₁, x₂, K)  represents player 1's chances of winning after doubling at p(t) = D₁(x₁, x₂, K),  we have

D1(x1, x2, K)  =  D1(x1, x2, K) − (1 − (D2(x1, x2, 2K) + Δ)) D2(x1, x2, 2K) + Δ ,  or

D1(x1, x2, K)  =  (D2(x1, x2, 2K) + Δ)(D1(x1, x2, K) − 1) + 1.

(7)

A similar expression may be obtained for D₂(x₁, x₂, K).

If both players are equally skillful, the probability that player 1 reaches a doubling position first when the match state is  (x₁, x₂)  is, by Lemma 1,

D2(x1, x2, 1) + Δ − 0.5 (D1(x1, x2, 1) + Δ − 0.5) + (D2(x1, x2, 1) + Δ − 0.5) ,

(8)

where  Δ  is again a correction factor to account for discontinuities.

The probability that player 2 reaches a doubling position first is

D1(x1, x2, 1) + Δ − 0.5 (D1(x1, x2, 1) + Δ − 0.5) + (D2(x1, x2, 1) + Δ − 0.5) .

(9)

When either player doubles, we will assume that his opponent drops. This assumption is accurate since the doubling points were determined by the condition that the probability of winning is the same whether one drops or takes.

Therefore, using (8) and (9), we have  A₁(x₁, x₂) = 

(D2(x1, x2, 1) + Δ − 0.5) A1(x1 − 1, x2) + (D1(x1, x2, 1) + Δ − 0.5) A1(x1, x2 − 1) D1(x1, x2, 1) + Δ + D2(x1, x2, 1) + Δ − 1 .

(10)

A similar expression may be written for  A₂(x₁, x₂) .

(1)–(10) and their counterparts for player 2 were combined recursively to determine  A₁(x₁, x₂), D₁(x₁, x₂, K), D₁(x₁, x₂, K), D₂(x₁, x₂, K),  and  D₂(x₁, x₂, K)  for  K =  1, 2, 4, 8, 16, and for  0 ≤ x₁ ≤ 25 ,  0 ≤ x₂ ≤ 25 .

In order to do this, values for  g, G₁, G₂, Δ  and  Δ  had to be determined. The following table was computed by taking  g = 0.25, G₁ = 0.25, G₂ = 0.15, Δ = 0.08, Δ = 0.06 . These values were selected based on our playing experience plus some work on running games [4].¹

Table 1 may be read as follows. The  x,  respectively  y,  coordinate of Table 1 gives the number of points player 1, respectively player 2, needs to win. For each pair  (x, y),  three numbers are given. The top number gives player 1's chances of winning the match  (A₁(x, y)).  The lower left number gives a modification of  D₁(x, y, 1)  which takes gammon equity into account. Recall that when player 1 has a probability  D₁(x, y, 1)  of winning, his expectation is considered to be  2G₁D₁ + (1 − G₁)D₁ − (1 − G₂)(1 − D₁) − 2G₂(1 − D₁),  which when  G₁ = 0.25  and  G₂ = 0.15  equals  2.40D₁ − 1.15.  The number appearing in the lower left which we call  D′₁(x, y, 1)  gives the probability player 1 would need in a straight race to have an expectation equal to  2.40D₁ − 1.15.  Since player 1's expectation in a straight race  = 2D′₁(x, y, 1) − 1,  we have  = D′₁(x, y, 1) = 1.2 D₁(x, y, 1) − 0.075.  The number in the lower right is  D′₂(x, y, 1).    D′₁  and  D′₂  are similar modifications of  D₁  and  D₂  which take gammon equity into account.

Because of space limitations, we were not able to give all the results obtained by the program. For example, for the pair  (4, 3)  we have

D1(4, 3, 1) = 0.670,	D1(4, 3, 2) = 0.602,	D1(4, 3, 4) = 1.0,
D2(4, 3, 1) = 0.756,	D2(4, 3, 2) = 0.820,	D2(4, 3, 4) = 1.0,
D1(4, 3, 1) = 0.633,	D1(4, 3, 2) = 0.602,	D1(4, 3, 4) = 1.0,
D2(4, 3, 1) = 0.642,	D2(4, 3, 2) = 0.820,	D2(4, 3, 4) = 1.0,
D′1(4, 3, 2) = 0.647,	D′2(4, 3, 2) = 0.909,	D′1(4, 3, 1) = 0.685,
D′2(4, 3, 2) = 0.695,	D′1(4, 3, 2) = 0.647,	D′2(4, 3, 2) = 0.909.

It is useful to observe that  D₁(4, 3, 2) = A₁(2, 3),  and  D₂(4, 3, 2) = A₂(1, 4).  Also,  D′₁(4, 3, 1) = 0.73,  which is considerably less than  D′₂(4, 3, 1) = 0.83,  even though  D₁(4, 3, 1) ≈ D₂(4, 3, 1).  This is because  D′₁(4, 3, 2) = 0.647,  while  D′₂(4, 3, 2) = 0.909.  In other words, player 1 can couble earlier when the cube is at 1 because player 2 must wait a long time to double back when the cube is at 2.

Analysis When the Players Differ in Skill

The analysis for this situation is more complicated and we strive for a good approximate solution. Suppose that player 1 is the better player. Intuitively, the better player should travel from  p = 0.5  to  p = 1  with less effort, i.e., with effort proportional to  0.5 / (1 + B),  rather than  0.5,  where  B > 0.  If we assume that the better player improves his position with less effort, while the inferior player requires the same effort as before, then a reasonable expression for the probability of the good player moving from  x  to  x + b  before reaching  x − a  would be

a a + b / (1 + B) .

(11)

Suppose instead that we assume that the better player moves more easily (with effort proportional to  1 / (1 + α) ) whereas the inferior player moves with greater effort (proportional to  1 / (1 − α) ). A natural expression for the probability of player 1 reaching  x + b  before  x − a  would then be

a / (1 − α) b / (1 + α) + a / (1 − α) .

(12)

This expression equals

a a + b(1 − α) / (1 + α) ,

in other words it equals (11) when  (1 + α) / (1 − α) = 1 + B.  Thus, without loss of generality we will only consider formulas similar to (11).

To take the skill factor into account, (10) now becomes  A₁(x₁, x₂) = 

(D2(x1, x2, 1) + Δ2 − 0.5) A1(x1 − 1, x2) + (D1(x1, x2, 1) + Δ1 − 0.5) A1(x1, x2 − 1) (D2(x1, x2, 1) + Δ2 − 0.5) + (D1(x1, x2, 1) + Δ1 − 0.5) / (1 + B) ,

(13)

where  Δ₂ > Δ₁,  since the inferior player presumably makes less accurate doubles.

Effect of Skill on Minimum Take Points

A skillful player should be able, in general, to double earlier because his chances in most positions are greater than they would be against an equal player. Similarly, in a continuous game the weaker player should in general wait longer before doubling.

Determination of New Formulas for  D₁(x₁, x₂, K)  and  D₂(x₁, x₂, K) 

We will assume that player 1 is the better player, and that his advantage is measured by  1 + B.  The  x₁, x₂  in  D₁(x₁, x₂, K)  and  D₂(x₁, x₂, K)  will be suppressed. In other words, we will let  D₁(K)  denote the minimum take point for player 2 when player 1 doubles from  K  to  2K. 

The formulas for  D₁(K)  and  D₂(K)  are the same as before and are given by (5) and (6). To obtain the new formula for  D₁(K),  we note that when  p = D₁(K),  player 1 must travel a distance  1 − D₁(K)  to win before his opponent travels a distance  D₁(K) − (1 − D₂(2K) − Δ₂).  Thus we have

D1(K)	=  D1(K) − (1 − D2(2K) − Δ2) D1(K) − (1 − D2(2K) − Δ2) + (1 − D1(K)) / (1 + B)
	=  (D1(K) + D2(2K) + Δ2 − 1)(1 + B) (D1(K) + D2(2K) + Δ2 − 1)(1 + B) + 1 − D1(K)
	=  1 − 1 − D1(K) (D1(K) + D2(2K) + Δ2 − 1)(1 + B) + 1 − D1(K) ,	(14)

so

(D1(K) − 1) ((D1(K) + D2(2K) + Δ2 − 1) (1 + B) + 1 − D1(K))  =  D1(K) − 1 ,

or

1 + (D1(K) − 1) ((D2(2K) + Δ2 − 1) (1 + B) + 1)

=  D1(K) ((1 − D1(K)) (1 + B) + D1(K) − 1 + 1) ,

hence

1 + (D1(K) − 1) (D2(2K) + Δ2 + B(D2(2K) + Δ2 − 1))  =  D1(K) (1 + B(1 − D1(K))) ,

so

D1(K)  =  1 + (D1(K) − 1) (D2(2K) + Δ2 + B(D2(2K) + Δ2 − 1)) 1 + B(1 − D1(K)) .

(15)

Performing a similar analysis and noting that

1 − D2(K)  =  1 − D2(K) 1 − D2(K) + (D2(K) − (1 − D1(2K) − Δ1)) / (1 + B) ,

we obtain

D2(K)  =  1 + (D1(2K) + Δ1) (D2(K) − 1) BD2(K) + 1 .

(16)

To incorporate the above formulas into a computer program, we assumed that the more skillful player would be a 6 to 4 favorite in a game with no cube, and that his expectation would approximately double in a money game with a cube (his expectation would be approximately 0.4 of a point per game). These assumptions allowed us to compute  B  in the following manner.

In a money game,  D₁(K) = D₂(K) = 0.75.  Substituting ¾ for  D₁(K)  and  D₂(K)  in (15) and (16), and taking  Δ₁ = 0.05, Δ₂ = 0.07, Δ₁ = 0.07, Δ₂ = 0.09,  we were then able to combine formulas (13), (15) and (16) to determine that value of  B  which made player 1's expectation in a money game equal to 0.4. Upon running the program with different parameter values, it became clear that the guesses of  Δ₁, Δ₂ Δ₁, Δ₂  were relatively unimportant compared to the assumption that player 1's expectation would be 0.4. In other words, the numbers in Table 2 are not affected significantly by small changes in  Δ₁, Δ₂ Δ₁, Δ₂,  but are affected significantly by a change in player 1's expectation.

Table 2 may be read in the same fashion as Table 1. For example, the three numbers in the box corresponding to (4, 3) indicate that when player 1 needs 4 and player 2 needs 3, player 1's chances are 57%, that player 2's minimum take point in a straight race is 76%, and that player 1's minimum take point is 82%. This does not contradict the fact that the underdog should generally double with weaker positions. The assumption is that player 2 plays poorly, so that when player 1 takes with a position that would give him an 18% chance against a good player (with no cube), his actual chances are 39.7%,² whereas when player 2 takes with a position that would give him a 24% chance against an equal player (with no cube), his actual chances are 20.3%.^3, 4

References

1. Keeler, E. and Spencer, J., "Optimal Doubling in Backgammon," Operations Research, Vol. 23, No. 6 (Nov.–Dec. 1975), pp. 1063–1071.
2. Zadeh, N., "Computation of Optimal Poker Strategies," Operations Research, (July–August, 1977).
3. ———, Winning Poker Systems, Prentice-Hall, Englewood Cliffs, N.J., 1974.
4. ——— and Kobliska, G., "On Optimal Doubling in Backgammon," Management Science, Vol. 23, No. 8 (April, 1977).

Scan of this article, from Management Science, Vol. 23, No. 9.

More articles by Norman Zadeh

More academic papers on backgammon

Backgammon Galore : Articles