I'm working on a dynamic programming problem. I want to find the optimal strategy and simulate it.

The game's description:

The player rolls two dice.

  • If the numbers shown by the two dice are different then the player will add the sum given ($2+3$ for example) to the cumulative rewards he has.

  • If the numbers shown by the two dice are equal then the player will loose all his reward.

I started modeling the problem. The state of the system is as follow: I chose one random number (300 for example) that may be the maximum reward for $N$ rounds game. The state is $V_k(S,D)$ where $S$ is the cumulative sum and $D$ is the sum of the two numbers shown on the two dice.

If we suppose that the numbers of rounds is finite, what will be the optimal strategy in a simple form?

In the case of infinite game what's the mean of the reward?

Reference : http://people.brandeis.edu/~igusa/Math56aS08/Math56a_S08_notes041.pdf

Thank you in advance guys :)

  • $\begingroup$ Oh, wait, maybe I mosread: In case of equal dice, will the player loose the sum from his reward or will he loose all his reward? $\endgroup$ – Hagen von Eitzen Feb 11 '13 at 16:02
  • $\begingroup$ he will all his reward $\endgroup$ – Ayoub Ennassiri Feb 11 '13 at 17:08
  • 2
    $\begingroup$ Your description of the game is very lacking. As described there are no choices a player can make: an entire game consists of one person rolling two dice a single time. I can imagine a variety of different games that it sounds like you were trying to describe. Also, you don't state what you are trying to find a strategy for. (common options are "maximal expected score", "best odds of beating some target score", and "best odds of beating an opponent", although the game as described is a single-player game....) $\endgroup$ – user14972 Feb 11 '13 at 17:13
  • $\begingroup$ Hi Hurkyl, This is a dynamic programming problem. I'm looking for an optimal strategy to maximize the expected score. It is not a game theory problem. It is a single-player game. In another way, when should the player stop. $\endgroup$ – Ayoub Ennassiri Feb 11 '13 at 17:24

When to stop depends on how many rounds you're allowed to play. If you're allowed to play for arbitrary many rounds, you could decide not to stop until you have a million points. Then with probability $1$ sooner or later (most likely much later) you will leave the table with a million points.

So the game is only interesting when there's a time limit after which you must stop playing and leave with whatever you've got at that time if you haven't cashed out before that.

A strategy is a function $f(N,S)$ that gives our decision to either cash out or keep playing as the output of two inputs: $N$ is the number of rounds left, and $S$ is how many points you have when you make the decision. The fact that you're supposed to use dynamic programming is a hint that you're not supposed to find an explicit formula for $f(N,S)$, but rather to compute a table of values for $f(N,S)$.

It is easy enough to analyze what the optimal choice for $N=1$ is. If you quit now your expected winnings are $S$; if you play the last round your expected winnings are $\frac16 0 + \frac56(S+7)$, (since a roll that doesn't bankrupt you wins you 7 points on average). So you should play the last round iff $\frac {5S}6 + \frac{35}6 \ge S$ which is if $S\le 35$.

In order for you to proceed to $N=2$ you need to compute an auxiliary table of the expected value of the game before you make the $f(1,S)$ for various $S$. For large enough $S$ you should always cash out, in which case the expected value is $S$ itself -- so you only need to tabulate the expected values for $S$ less than the cash-out threshold.

Now you can compute $f(2,S)$ as follows: The expected value of walking out is $S$. To find the expected value of playing, consider the various outcomes of the dice roll: you could go bankrupt or win 3, 4, 5, ..., 10, 11 points, each with a particular probablity. Each of these cases take you to a state $(1,S')$ that you have already computed the expected value of; the appropriately weighted average of those expectations is the value of going on. Compare this with $S$ to figure out if you should leave or go on.

Now do the same thing for $f(3,-)$, $f(4,-)$ and so forth, until you reach the actual length of your game.

(Note that the actual strategic decisions can be made in constant time on the fly if only you have tabulated the values of the game at each possible state).

  • $\begingroup$ Should $\frac S6 + \frac{35}6$ be $\frac {5S}6 + \frac{35}6$? $\endgroup$ – user940 Feb 11 '13 at 19:52
  • $\begingroup$ @ByronSchmuland: Hm, yes it should. And that changes the threshold to $S\le 35$. Thanks. $\endgroup$ – hmakholm left over Monica Feb 11 '13 at 19:57
  • $\begingroup$ In fact, the optimal strategy for this game is to play until you run out of rolls or $S\geq 35$, whichever comes first. $\endgroup$ – user940 Feb 11 '13 at 19:58
  • $\begingroup$ @ByronSchmuland: Really? So if I have 36 points and a quadrillion turns left, I should stop? That sounds counterintuitive; if I roll and lose, I'll have plenty of time to attempt to reach 36 once more afterwards -- so continuing is almost a no-loss proposition for me there. $\endgroup$ – hmakholm left over Monica Feb 11 '13 at 20:01
  • $\begingroup$ Sorry I assume that at the first loss, you go to zero and the game ends. I'm not sure if the OP meant this or not. $\endgroup$ – user940 Feb 11 '13 at 20:02

I will assume that when you lose all your money the game is over and you are not allowed to play anymore. Under this assumption, you should not keep rolling even with unlimited rolls available, because if you play too long, you'll eventually hit zero and lose everything.

Starting with $S$ dollars, the expected amount after rolling the dice one more time is $$0\,{6\over 36}+(S+3){2\over 36}+(S+4){2\over 36}+(S+5){3\over 36}+\cdots+(S+11){2\over 36}= {5\over 6}S+{35\over 6}.$$ The first term, with value zero, corresponds to rolling doubles and losing all your money. Otherwise, your money increases by anything from 3 to 11 dollars.

The optimal strategy is to play until either you run out of rolls, or the current amount $S$ is greater than or equal to ${5\over 6}S+{35\over 6}$, i.e. $S\geq 35.$ In the latter case, the risk in losing your fortune outweighs the potential gains, so it is better to stop.

For $S\geq 1$, the value function for the game with $N\geq 0$ rolls is $$v^N(S)=\cases{35-(5/6)^N(35-S)&for $S\leq 35$\cr S&for $S\geq 35$.}$$ This is the expected payoff when you start with $S$ dollars and follow the optimal strategy.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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