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.

Two players compete to reach a certain number N of points (for example 100) to win the game by throwing a each roll two regular dice and noting the amount accumulated since their first roll. So, the first player reaching N points wins the game.

Each game starts with a stake of S dollars. A fair coin is tossed to designate the first player.

When a player to roll feels he has a sufficient advantage, he can choose , before he rolls the two dice, to offer to double the stake of the game to 2S dollars. The opposing player can:

-turn down the offer, but concedes the game by doing so and loses S dollars, OR

-accept the offer: then the stake of the game doubles (to 2S). When a player accepts a double, he takes control of the right to (re)double the stake and he is the only player who can make the next offer of a new double (to 4S), etc.

Assuming the player to roll reached s1 points (N-s1 to go to N) and his opponent has s2 (N-s2 to go to N), how to compute if and when:

-he must offer to double (redouble)

-his opponent must accept

share|improve this question
2  
Do you just have to exceed the target, or hit it exactly? If we express the answer just in terms of winning probability for each player, it doesn't matter, but if you want to calculate winning probabilities it does. –  Ross Millikan Apr 29 '11 at 16:44
1  
If you search for "backgammon doubling strategy", there are many pages. Probably some are right. When calculated in terms of winning probability, this is the same except for the possibilities of gammons, which are often ignored at the start of the analysis. –  Ross Millikan Apr 29 '11 at 17:39
    
For backgammon a couple of rules-of-thumb can be found at bkgm.com/glossary.html –  ThudanBlunder Jun 6 '11 at 21:55

1 Answer 1

It's easy to compute the optimal strategy for $N$ reasonably small (say, up to $N \le 10000$). You just iterate backwards from the end of the game. There are three possible doubling states:

  1. Both players have the right to double (i.e. nobody has doubled yet);
  2. You have the right to double;
  3. Your opponent has the right to double.

Note that the number currently showing on the doubling die -- to use the backgammon term -- is irrelevant to your strategy (although not irrelevant to your expected gain/loss).
So for each doubling state $s \in \{1,2,3\}$ you want to compute the expected gain $E(s,x,y)$, expressed as a multiple of the number on the doubling die, where $s$ is the doubling state, $x$ is the number of points you need to win, and $y$ is the number of points your opponent needs to win.
$x$ and $y$ can't both be zero, so we can start the ball rolling with $E(s,0,y) = 1$, $E(s,x,0) = 0$. Then you have to set up a number of simple but tedious equations expressing $E(s,x,y)$ in terms of $E(s', x', y)$ for $x' < x$ and all values of $s$ and $s'$. Then you can work backwards to calculate $E(s,x,y)$ for all $s,x,y$.
The details are, as I said, tedious, and I'm not going to spell them out unless you pay me. Just be aware that you have to store the intermediate values in a table of size $3N^2$. Don't be seduced by the obvious recursive solution -- its asymptotic complexity is exponentially worse.

share|improve this answer
    
Hit the target N wins. I searched and found math.hmc.edu/~benjamin/papers/BackgammonRacing.pdf. Given s1, s2 and N, it is not too difficult to compute the winning probability WP of the players ...if there was not the possibility of the double. So, I think these WP are not sufficient to determine when to double and when to accept because of the possibility for the player who eventually agreed to double the stake. –  Jean-Pierre Apr 30 '11 at 1:51
    
Of course it's possible. It's just tedious. –  TonyK Apr 30 '11 at 7:49

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.