Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Edit: This question is a lot shorter than it is. Don't get intimidated. If you know backgammon, just skip to question 2.

In Backgammon, each game is played for one point (or one dollar) between two players. There is a die, called the doubling cube, which has the numbers $2, 4, 8, ...$, in the middle of the board (it is not 'owned' by anyone). The players take turns rolling two regular dice (not the doubling cube) and moving. But before each roll, a player can 'offer the cube' (or 'offer to double', 'double', etc.) which is basically saying "Hey, why don't we play this game for 2 points". The other player can drop, or refuse the cube, and lose one point, or may accept, or take, the cube, in which case the game continues for twice as many points as before.

A player's equity in the game is the probability that he'll win a cubeless game, where cubeless means neither player can offer the cube (or a one point game). (For backgammon players who know the rules, I'm ignoring gammons and backgammons, so the equity equals the probability of winning. Edit: As @Henning Makholm's first answer indicates, I also do not want to include the equity of owning the doubling cube.

I have two questions, but I know the answer to the first one and I think I'm calculating it right.

1) What equity does the player receiving the cube require in order to accept it? Answer, I'm told, is $.25$?

The receiving player will accept the double when the expected value of taking it is greater than the expected value of dropping (which automatically loses him $1$ point). $p$ is the probability (equals equity) of the receiving player winning (are you guys following all this?).

$E(take) \ge E(drop) \\ 2p-2(1-p) \ge -1 \\p > .25$

I'm nearly certain that's correct, so

2) What equity is required for a player to offer the cube (offer to double the game's stakes)?

How is that calculated? We don't know whether the cube's recipient will accept or not.

I start the same as question 1: The giver will double when his expected value of doubling is greater than his EV of not doubing (duh!). If $EV(rolling)$ is $p-(1-p)$, and $EV(doubling)$ is $2p-2(1-p)$, then

$E(doubling) > E(rolling) \\ 2p-2(1-p) > p-(1-p) \\ p > .5$

Which can't possibly be correct. While I'm not BG expert, I did used to play for (small amounts) of money in NYC. There is no way in heck that I would double with 51% chances.

OK, that's all I got. How do we figure this out? Thanks.

share|improve this question

3 Answers 3

up vote 6 down vote accepted

Here's an analysis that tries to take into account redoublings and cube ownership. It is based on completely ignoring the actual gameplay of backgammon and substituting the (quite counterfactual) assumption that the underlying game is a simple Brownian motion: The game starts by placing a counter a point 0.5 on a scale from 0 to 1. The counter then performs a one-dimensional continuous-time random walk. When it reaches either 1 or 0, the game ends and player A or B, respectively, is declared the winner. While the game is ongoing, the two players have the options of doubling and redoubling at arbitrary times, but otherwise according to the backgammon doubling rules.

In this game, the only choice a player has to make is when to offer the cube. His strategy can be summarized by two numbers $k$ and $\lambda$. When a player owns the doubling cube, he will offer a redouble as soon as the position is $k$ or more; he will offer the first doubling when the position reaches $\lambda$ for the first time. The situation before the first doubling is appreciably different from when the cube has an owner, so $\lambda$ can differ from $k$, but since a random walk is symmetric under time shifts, there is no reason to consider strategies where $k$ changes as the game ages.

Let's find the optimal $k$ first. Consider two functions $f$ and $g$ such that $f(p)$ is the expected value of the game (for the player who wins at $p=1$, and assuming optimal play) at position $p$, given that the player owns the cube, and $g(p)$ is the expected value when the player doesn't own the cube. These expected values are always between $0$ and $1$; we imagine that we have already paid $\frac 12$ into the pot that the winner will take home.

Because of symmetry we must have (if both players play optimally, which in particular means that their $k$s are the same): $$g(p)=1-f(1-p)$$ Look at the value of the game at position $k$ when we're just about to offer a redouble; let's call this value $v$. Then $$v=f(k) = \min(1, 2 g(k) - \frac12)$$ The $\min$ is because the opponent will only accept the doubling if doing so will be more advantageous to him than refusing. Subtracting $\frac 12$ accounts for our share of doubling the pot (or in other words, for the risk that we may eventually lose 2 units rather than 1).

Now, it is clear that we should redouble at least as soon as the point where a rational opponent would refuse it -- from that point, waiting any longer is not going to yield us anything. So we can do away with the $\min(1,\ldots)$ and just remember that $k$ must be chosen such that $v\le 1$. We then have $$\tag{1} v = 2g(k)-\frac12 = 2(1 - f(1-k))-\frac 12 = \frac32 - 2f(1-k)$$

When $p$ is between $0$ and $k$, the value of the game depends on the probability that the position will reach $k$ before it reaches $0$. By a wonderful property of Brownian motion, this probability is simply $p/k$, so we have $$\tag{2} f(p) = \frac pk f(k) = \frac vk p$$ Clearly, for optimal play we must choose $k$ such that the proportionality constant $\frac vk$ is as large as possible. To find the relation between $v$ and $k$, specialize (2) to $p=1-k$: $$ f(1-k) = \frac{1-k}{k} v$$ and telescope that into (1): $$ v = \frac 32 - 2\frac{1-k}{k} v \quad\Longrightarrow\quad v = \frac{3k}{4-2k}$$ Thus $\frac vk$, which we're trying to maximize, is $\frac{3}{4-2k}$. This increases monotonically with $k$, so we want to have $k$ as large as possible. But, as argued previously, we cannot have $v>1$, so we find the optimal $k$ by solving $1=v=\frac{3k}{4-2k}$ for $k$. This yields $$k=0.8$$ for optimal play once the doubling cube is owned.

We're now ready to find $\lambda$. At the beginning of the game the situation is symmetric, so if both players follow the same (optimal) strategy, each player will make the first doubling offer with probability $\frac 12$. The objective is then to maximize the value of the game after that first doubling happens: $$ g(\lambda) = 1-f(1-\lambda) = 1 - \frac{1-\lambda}k = 1.25\lambda - 0.25$$ which is maximized by choosing $\lambda$ as large as possible. But as before, choosing a $\lambda$ so large that the opponent refuses our doubling is just a waste. So in fact $\lambda$ should be chosen just at the threshold where the opponent would start refusing the doubling. But that happens to be the same criterion as was used to find $k$, so in fact $\lambda=k$ is optimal.

Conclusion: For optimal play with doublings and redoublings, assuming that backgammon can be modeled as a Brownian motion:

  • Offer to double or redouble as soon as your position is 80% or more.
  • Accept a doubling or redoubling offer if your position is better than 20%.

Exercise: prove that with this strategy, no matter which strategy your opponent follows, your net expected outcome of a game is never negative.

share|improve this answer
    
This is a very nice answer; I enjoyed reading it :-). I was surprised by the $80\%$ result; I didn't expect it to be that high; so I wrote a simulation to test it. The result was that indeed the $80\%$ strategy wins against other strategies. Against the strategy of doubling whenever one is in the lead, it wins more than $1.5$ as many points as the opponent. Here's the code. –  joriki Mar 15 '12 at 15:57
    
@joriki: Always nice to have empirical support. :-) For completeness you should probably test also against strategies where one's threshold for accepting an offer is not necessarily the complement of one's threshold for making one. I didn't mention that possibility in my answer (because the optimal acceptance threshold drops out of the analysis by itself -- if it didn't, I would have had to solve $f(x)\ge.25$ as a separate step), but if you happen to know that your opponent always follows a particular suboptimal strategy, you can do "better than optimal" by varying yours in this way. –  Henning Makholm Mar 15 '12 at 17:02
    
Yes, you can gain an advantage against a suboptimal strategy that way, but the equilibrium strategy must have both thresholds the same, so to find the equilibrium it should suffice to test all strategies with equal thresholds against each other, no? –  joriki Mar 15 '12 at 17:06
    
@joriki: At least to me it wasn't clear that they would have to be the same in an equilibrium before I did the calculuations. A priori, it is conceivable that there could be a situation where it would be irrational for $A$ not to offer and irrational for $B$ not to accept. Even now, I only believe it can't be so because that's what my equations tell me. –  Henning Makholm Mar 15 '12 at 17:22
    
OMG! How can you guys do this so fast? It will be months before I can even digest it (but good work!). –  Jeff Mar 15 '12 at 18:56

Let's assume that you and your opponent are master analysts, so both of you always know the equity exactly. It's a full-information game anyway.

I think the reason why you wouldn't double with a 51% advantage is that after you double, you lose the right do double again, until your opponent has redoubled.

If you double with a 51% advantage, the game is still (ignoring the doubling cube) almost even. If you have bad luck with the dice and later find yourself at 21%, your opponent can offer you a redouble, which you would refuse, losing the game. On the other hand if it goes exactly the other way and you find yourself at 79%, you don't have that option anymore; you'll need to play until you actually win before you've won.

So for a game with about even equity, owning the doubling cube is a rather significant advantage, which you're not including in the calculations in the question. How significant this advantage is cannot be quantified purely in terms of equity -- one must also take into account how wild swings in equity will be likely during the remainder of the game, and in which direction.

For example, consider an idealized situation (with no direct equivalent in actual backgammon), where player A will automatically win in 25 turns unless player B rolls a 1-1 before that happens, in which case B wins instantly. In this position each player has a probability of about 50% of winning, but having the ability to double wouldn't affect them equally. It would be pointless for B ever to offer a double, but A will get a net benefit by offering a double when there's about 9 turns left (at which point B should refuse).

This also shows that accepting a double can have greater expected value than refusing even with less than 25% equity, and given optimal play.

share|improve this answer
    
"Let's assume that you ... are master analysts" LOL. Thanks. Interesting reply. I understand that there is an equity bump in owning the cube. But ignoring that, I'm still looking to learn how to calculate the equity necessary to double. –  Jeff Mar 10 '12 at 15:56
    
If you ignore the effect or owning the right to double, then the answer is what you have already calculated in the question. –  Henning Makholm Mar 10 '12 at 17:22
    
That doesn't sound familiar (because I've seen the answer before - a long, long time ago). Let me mull it over and see what else comes up. –  Jeff Mar 10 '12 at 20:58
    
Hm, I'll have to correct my previous comment. Your $.5$ result is the threshold at which you should offer, if there is no further doubling, and your only choices is between offering now or never offering. If we compare different strategies for when to double (and there is still no redoubling), then the optimal choice is to offer as close to 0.75 as you can manage -- with arguments similar to my other answer. –  Henning Makholm Mar 15 '12 at 16:52
    
"Now or never" doubling is what one backgammon writer (the only one I've ever read) would call "missing your market". "Missing your market" is a situation in which you didn't double, and now your position is too good to have the double accepted. At least you get 1 point, but you didn't get the maximum you might have gotten. –  Jeff Mar 15 '12 at 18:58

You can actually do a fair bit better than the 20%/80% approximation.

Rick Janowski wrote a paper about it here:

http://www.bkgm.com/articles/Janowski/cubeformulae.pdf

Two big innovations in that paper:

  • You want to account for the possibility of gammons and backgammons. You do that by assuming that the proportion of wins that are gammon wins (and the proportion that are backgammon wins) stays constant as the probability of win changes. Ditto for gammon/backgammon losses.
  • He noted that the 20%/80% thing above is a "live cube" limit. It assumes that the probability of win diffuses continuously, when really it jumps from turn to turn. Because of that you can wait right until before the cash point to offer the double, capturing all the theoretical value. Actually, because you might jump across the cash point, you want to double earlier than right before the cash point. So the "live cube" limit is an upper limit to the proper cubeful equity. The "dead cube" limit, where you assign no value to owning the cube, is a lower limit. Janowski proposed a linear interpolation in equity between those two limits; the linear interpolation parameter is a proxy for all the complicated stuff about jumps in probability, size of doubling window, etc.

With this you can get relatively simple expressions for take and cash points, as well as initial double and redouble points. It's all in that paper, which is a real classic.

I also did a bit of work on this, modeling the changes in probability as jumps instead of a continuous diffusion. Still a bit rough but if you're interested you can check it out here:

http://compgammon.blogspot.com/2012/03/new-cube-decision-model-posted-on.html?showComment=1333785363926

share|improve this answer
    
From my limited experience playing Backgammon against a computer, it would seem that before doubling one should consider the probability that the game might shift back in the opponent's favor enough for them to double. There are some situations where one might have a very high probability of winning, but have a non-trivial risk of having the equity shift severely. –  supercat Feb 24 at 0:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.