optimal strategy for a 20 sided die with 100 rounds game

optimal strategy for a 20 sided die with 100 rounds game

In a game there is a 20-sided die. At the start of the game it is on the table and the 1 face is facing upright. In each of the 100 rounds you have 2 options: you can either roll the dice or you can take a number of dollars equal to the current face.

When you take the money, you also take the die off the table, so you have to spend one round to roll it again before you can take money again.

How would you play this game to maximize the expected profit? And what would this profit be?

So for example, say the number 1 is facing upwards, if I take this 1, I take the die off the table as well, so I have to spend one round to roll again.

What would the optimal strategy be?

I guess the baseline strategy would be take, reroll, take, reroll etc, with no regard of what number/cash being taken. So the average cash being taken here is 10.5 which is just the average of the numbers between 1 to 20. And I can take money 50 times. So the expected profit using this basic strategy would be 50×10.5=525.

Obviously there is a better strategy to this. It just doesn't feel right to take say 1 as it is the lowest number, so it is much better deal to reroll. So I think now I should adjust the range of numbers that I should accept? For example I can choose to take any numbers between say 11 to 20 and so on. And reroll when I get a number between 1 to 10. I guess now I can keep testing values until I figure out my which range gives the maximum return. But surely you can do this with equations?

How can I mathematically/algebraically solve for maximum return?

Answer

Like in the similar problem 20-sided dice 100 rounds game, the threshold for rerolling depends on the round. But whereas that other game has a trivial limit in that you should always roll if some sufficiently large number of rounds is left, here we can determine a non-trivial limiting strategy for large numbers of rounds before solving the concrete 100-round game numerically.

With the end of the game sufficiently far off on the horizon, you’ll always take the money above the same threshold t, so we can determine the expected payoff per round as a function of t.

The game has two states, in which the die is on or off the table. In the off state, the game transitions to the on state with probability 1. In the on state, it remains in the on state with probability t/20 (where you immediately reroll) and transitions to the off state with the remaining probability 1−t/20 (where you take the money and then reroll a round later). The equilibrium occupancy p of the on state thus satisfies p=p⋅t/20+1−p, with the solution

p=20/(40−t).

Your expected payoff in the off state is 0, and your expected payoff in the on state is

1/20∑k=t+1^20 k=1/40(21+t)(20−t),

so overall your expected payoff per round is

(21+t)(20−t)/2(40−t).

You can check that this is 0 for t=20, since you always reroll and never take money, and 1/2⋅21/2 for t=0, since you never reroll and always get the average payoff of 21/2 every second round.

This function has its maximum at 40−2√305≈5.07 and takes the values 50/9<39/7>189/34 at t=4,5,6, respectively, so in the limit of an infinite game you should take the money above 5 and then the expected payoff per round is 39/7≈5.57.

I wrote this Java code to solve the finite game with 100 rounds. The expected total payoff is

42530816287894271349465773575664858068335475018523440090448543/76624777043294442917917351357515459180936956109180108800000≈555.05,

quite close to 100 times the expected payoff of the infinite game per round. The optimal threshold is 5 (the limiting threshold) all the way up to and including round 92, and the remaining optimal thresholds above which you should take the money are:

(Obviously you should always take the money in the last round.)

There’s an interesting oscillation there, which illustrates that at the end of the game the parity of the number of rounds left becomes crucial, since with n rounds left you have at most ⌈n/2⌉ payoffs left, so wasting a round by rerolling is a lot more costly with an odd number of rounds left. For instance, in the penultimate round, you know you have one payoff left no matter what you do, so the threshold is high because you only take the money if you expect to get less on a single reroll. But in the round before that, you know that after this round you’ll only have one payoff left no matter what you do, so the opportunity cost of taking the money isn’t a full payoff but only an extra reroll for the last payoff, which is worth less than 3, so you should take the money if it’s at least 3. The oscillations decay with increasing distance from the end and subside 8 rounds before the end.