Very simple dice game

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

Solution 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.