I'm working on dynamic programming problems this week. The following is a dice game. I'm trying to find the optimal strategy using dynamic programming.

The game's description :

The player rolls two dice.

  • If the sum of the numbers shown by the two dice are equal to the precedent sum (precedent round) then the player will loose all his reward.

  • Otherwise the player will add the sum given ($2+3$ for example) to the cumulative rewards he has.

I started modeling the problem. The state of the system is as follow: I chose one random number (400 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?

Thank you in advance guys :)

  • $\begingroup$ If you get the running total over 12, are you safe? $\endgroup$ – Ross Millikan Feb 13 '13 at 21:59
  • $\begingroup$ I'd suggest to use "sum" for the sum of the two dice and "total" for the running total of the reward throughout. I suspect that the answer to @Ross' question above is that "the precedent sum (precedent round)" refers to the sum of the two dice in the preceding round, not the running total of the preceding round? When you say that the player will lose their reward, does that end the game and the value is $0$, or can the player start accumulating rewards again? I presume the former, since the latter would lead to the game value being infinite. $\endgroup$ – joriki Feb 13 '13 at 22:44
  • $\begingroup$ The player should be able to decide when to stop but he can continue if he sees that he can get a better reward. Precedent round refers to the sum of the two dice in the preceding round. $\endgroup$ – Ayoub Ennassiri Feb 13 '13 at 23:45
  • $\begingroup$ @Samatix: Do I understand correctly that you're saying that the player can start accumulating rewards again when they lose the reward? (That's what I'd asked about.) Are you aware that in that case the game is infinite and the player can obtain an arbitrarily high reward? My answer assumes that the game ends when the sum is repeated and the reward is lost. $\endgroup$ – joriki Feb 13 '13 at 23:49
  • 2
    $\begingroup$ I have deleted an inappropriate comment. $\endgroup$ – Zev Chonoles Feb 15 '13 at 0:40

Here's a Sage session that calculates the expected value and the optimal strategy:

sage: @CachedFunction
sage: def f(s,d):
...       if (s > 500):
...           return s    
...       exp = 0
...       for i in range (2,13):
...           if i != d:
...               p = (6 - abs (7 - i)) / 36
...               exp = exp + p * f (s + i,i)
...       return max (s,exp)    
sage: f (0,0)
sage: _.n ()
sage: for i in range (2,13):
...       for s in range (0,500):
...           if f(s,i) == s:
...               print "If you rolled",i,", stop if you have at least",s
...               break
If you rolled 2 , stop if you have at least 250
If you rolled 3 , stop if you have at least 127
If you rolled 4 , stop if you have at least 86
If you rolled 5 , stop if you have at least 66
If you rolled 6 , stop if you have at least 54
If you rolled 7 , stop if you have at least 46
If you rolled 8 , stop if you have at least 53
If you rolled 9 , stop if you have at least 63
If you rolled 10 , stop if you have at least 81
If you rolled 11 , stop if you have at least 119
If you rolled 12 , stop if you have at least 241

Thus the game's value is about $25.4$, and the reward at which to stop depends strongly on the probability of repeating the last roll, and is also slightly higher for the lower of two equiprobable sums (e.g. $2$ and $12$), as might be expected.

  • $\begingroup$ This really a pertinent answer. Could you please give me more details. What does the function f refers to ? is it the payoff ? $\endgroup$ – Ayoub Ennassiri Feb 13 '13 at 23:50
  • $\begingroup$ @Samatix: Yes, $f$ calculates the payoff for the arguments s and d, which correpsond to your variables $S$ and $D$. It does so by comparing the expected value if you roll again to the sum you could keep if you stop. The results are automatically cached due to the decorator @CachedFunction. $\endgroup$ – joriki Feb 13 '13 at 23:52
  • $\begingroup$ I still have one question if I don't bother you. How did you get the 25.4 (the game value). $\endgroup$ – Ayoub Ennassiri Feb 14 '13 at 0:05
  • $\begingroup$ @Samatix: I called f (0,0), which yields a huge fraction, and then called n () on that to get its decimal representation. (I guess the answer to your first question should have been that f calculates the expected payoff, so f (0,0) is the expected payoff at the beginning of the game, i.e. the game value.) $\endgroup$ – joriki Feb 14 '13 at 0:20

The Game Strategy: stop rolling and keep the current reward if and only if the next rolling will not increase the reward statistically.

The Game Value: expectation of reward of this game based on the above game strategy.

I implemented a C++ implementation as follows, http://cpluspluslearning-petert.blogspot.co.uk/2014/09/dynamic-programming-game-value-of.html.

Game value calculated on this example is: 22.224974509843324.


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.