Find the optimal strategy for this dice game

Question

You are playing a game: You have $6$ standard 6-sided dice that are all rolled at the start of the game. The sum of dice values is your score. Each turn, you can take any (or none) dice and reroll them.

The goal of the game is to get score of at least $30$ in fewest turns possible. What is the optimal strategy to minimize average number of turns required to win?

Suppose alternative game where you have $10$ turns available and want to get the highest average score. What is the optimal strategy now?

In general, having $n$ $m$-sided dice, what is the optimal strategy to get score of at least $s$ in fewest average turns, or to get the highest average score in $t$ turns?

Answer 1

For the "alternative game":

This is the simpler of the two, as each die can be considered independently. You should always reroll if your average expected result over your remaining rolls is higher than your current result. The average expected value from one roll is 3.5 - so for the last chance to roll, you reroll on a (123). That's going to mean rerolling half the time, and an average value of 5 the other half, which means that you have 3.5/2+5/2, or average value of 4.25, so for the second to last roll, you're already rerolling anything that isn't a 5 or 6... which continues until that average number creeps above a 5, at which point you're rerolling everything but 6s. So...

the math for 10 rolls on a d6 works out as...

roll 10: average value 3.5. reroll 1,2,3. roll 9: average value 4.25. reroll 1,2,3,4. roll 8: average value 4.66. reroll 1,2,3,4. roll 7: average value 89/18 (just under 5). reroll 1,2,3,4. roll 6: average value 277/54 (a tch above 5). reroll all but 6. roll 5-1: keep only 6s.

final answer:

After your initial roll, reroll all but 6s for your first 6 rolls, then reroll 1,2,3,4 for the next three, then reroll 1,2,3 for the final shot. Computational simulation shows that this strategy yields average score of 34.25.

For the base game, I do not have a solution.

This one is more complicated, because you don't know exactly how many rolls you have ahead of you, and there are edge cases where you wouldn't want to reroll specific dice that were under the average (If you had a 1 you were rerolling, your chances might be better if you were not also rerolling a 6) and there are going to be cases where there's a tradeoff between chance of getting it next turn and chances of getting it within two or three turns.

...but I do have some thoughts on how one might get there.

First, a bit of basic principle

In general, you should never lock down a die that's going to make it take longer to roll. Also, the way the puzzle looks, with good play, you should never unlock a die that you've already locked. The only time it would make sense to do that would be if you somehow rolled a die higher than the locked die that also somehow made you want to reroll the locked die, and rolling higher than the locked die should always push you towards the victory condition in a way that would make that never occur. I don't know how to prove this mathematically, but I'm almost certain it is true.

Then, a simplifying conclusion that can be derived from that principle

Given that, it should be possible to reduce any pattern to a number of dice to roll (the number of unlocked dice) plus a static number to add (the total from the locked dice). You can further simplify by just subtracting the static add from the target number and having it be a number of dice to roll, opposed by a static number. The optimal strategy, then, would be to at each turn look at the dice that you've rolled and the remaining number, and lock as many as appropriate to minimize the average remaining rolls.

...and an attempt to map out what I can see of the first steps of how to make use of that simplifying conclusion.

One die is relatively simple. Either it's flatly impossible or your target number is covered by the die some percentage of the time (it won't be all the time because if it were, you'd be done). The average number of rolls for that one die (it turns out) is going to be one divided by that fraction - so if you need to make a 3 on a d6, that'll happen half the time. On average, that'll take two rolls. If you need a 6 on the die, it'll happen 1/6th of the time and require 6 rolls on average... and so forth. this is a pretty simple use of addition of an infinite series. The second die is... not so simple. Here, you need to cover the chance that you will meet the total (very similar to the one-die problem) but also the chance that one die or the other gets to a number that would get you to a superior position while not getting you all the way to your objective, and finally the chance that you get no such advance and need to reroll entirely. The math to determine all that, however, gets kind of tricky. My suspicion is that once you have the two-die solution fully mapped out and comprehended, it should be possible to expand to an N-die solution without too much additional trouble, but that second step is a doozy. I suspect it is beyond me.

Answer 2

My strategy would be

rolling every single with has less than 5 value.

with this strategy it takes,

$3.42 + 1$ rolls (assuming it takes one turn at least to play the game)

for example,

if we get 6,4,4,3,1,5 initially, we roll $4,4,3,1$ at the same time.

The second question is

Suppose alternative game where you have 10 turns available and want to get the highest average score. What is the optimal strategy now?

if I am allowed to have 10 turns, including first turn as initial result;

I will roll every single coin if the result is less than $6$ now.

and as a result the average would be;

33.

but we can tweak this result a little by

rolling the dices only with less than 5 after 6th turn.

resulting the average as

33.86

another tweak is by

rolling the dices only with less than 4 at the last turn.

resulting the average as

33.90

Answer 3

I'll try solving the general game where objective is to maximise score in t turns.

First thing to notice is each die is independent of every other die. We simply need to solve the strategy for one die, and apply it to each die.

Let f(x,t) denote the expected value we should get if the current number is x, there are t turns left and we play optimally.

f(6,t) = 6 for all t

If there's one turn left we reroll iff x ≤ 3. 3.5 technically f(1,1) = f(2,1) = f(3,1) = 3.5 (reroll)

f(4,1) = 4, f(5,1) = 5, f(6,1) = 6 (no reroll)

If there's two turns we reroll if reroll gives higher EV.

f(1,2) = max(1, sum f(x,1) / 6 ) = max(1, 4.25) = 4.25

f(2,2) = max(2, 4.25) = 4.25

f(3,2) = max(3, 4.25) = 4.25

f(4,2) = max(4, 4.25) = 4.25

f(5,2) = max(5, 4.25) = 5

f(6,2) = max(6, 4.25) = 6

Now we get our EV for two turns = sum f(x,2) / 6 = 4.666666

f(1,3) = f(2,3) = f(3,3) = f(4,3) = 4.6666666

f(5,3) = 5, f(6,3) = 6

Now for 3 turns, EV = sum f(x,3) / 6 = 4.94444444

f(1,4) = ... f(4,4) = 4.94444444

f(5,4)=5, f(6,4) = 6

Now for 4 turns, EV = 5.12936

Which means reroll for all numbers unless its a 6

Conclusion (assuming my calculations are correct):

If you have 4 or more turns, reroll unless you have a 6

If there's two or three turns left, reroll unless you have 5 or 6

If you have a turn left, reroll unless you have 4, 5 or 6

Apply this independently to each die

The simple formula is to obtain this: f(x,t) = max(x, summation (x varies 1 to m) f(x,t-1) / m) with base case f(x,0) = x. If the first value is bigger, no reroll is better, if the second is bigger, reroll is better.

I've solved the strategy explicitly for n 6-sided die, but the formula holds for any m-sided die.

Answer 4

For the general question of minimising turns to reach a score.

Let f(x1,x2, ... x6, s) be the expected number of turns required to reach s assuming optimal play, where the current state is x1 ones, x2 twos, x3 threes and so on.

Clearly f(x vec, s) = 0 iff sum i*x_i ≥ s, which forms an infinite base case.

f(x1,x2, .. x6, s) = minimum of total 2^n terms.

These are the 2^n options available at any given point. There are a total of n die, each with an option to reroll or not.

Perhaps all die with same number will get clubbed together, and always rolled together or not rolled together - this would reduce the space to 7 options instead of 2^n. But I haven't proven this yet.

Each of these 2^n options lead to 6^r possible outcomes, where r is the number of dice that got rerolled in that option( r lies in 0 to n). We will take the mean of expected values of number of turns of all 6^r options.

So f(x vec,s) = min (over 2^n terms) [ summation (over 6^r terms) f(x' vec, s)) / 6^r]

This method doesn't ever decrease s, and only changes x vector instead.

Hence we have obtained a inductive formula for f(x vec, s)

For n m-sided dice, we have a total of m^n choices for vector x, and mn legal choices for s. This is still computationally feasible for small m,n such as those given in the problem

Answer 5

Answering my own question, since I believe I have found the solution.

I found the solution computationally using dynamic programming. Here is the resulting table with average number of turns for all scores of up to 36 and up to 6 dice: https://codepen.io/BoltKey/pen/jObaZoO

How to use: the numbers in the table say how many average turns it takes to get a score with number of dice. So you throw the dice and select how many dice to keep based on which relevant number of average remaining turns in the table is the lowest.

Example: My first throw is $6$, $5$, $4$, $2$, $2$, $1$. I will keep the $6$. Now I will either be trying to get score of $24$ with $5$ dice, $19$ with $4$ dice or $15$ with $3$ dice. From the table, I see those options will take average of $3.65$, $3.44$ and $3.9$ turns respectively. That means it is the best to keep the $6$ and $5$ and attempt to get a score of $19$ with the other $4$ dice. Repeat until you reach the desired score.

The algorithm assumes that using the optimal strategy, you never have to reroll any dice you previously decided to keep. (proof left to the reader as an exercise)

The algorithm iterates over number of dice and score, calculating average number of turns for each combination. It iterates over all the possible dice configurations, saving the best possible number of turns remaining based on previous results for each configuration, weighed by the probability of rolling that configuration. This part assumes you keep at least one die from the dice rolled.

It may be impossible or very hard to reach the goal with the remaining dice, hence result of infinity turns is possible. Naturally, if that is the case, you reroll all the dice. Specifically, you reroll all the dice if the average number of turns it takes to reach the score with all the dice, incremented by 1, is lower than any other option. This leads to another interesting problem altogether - you have a list of values, but you may replace any values with average of the resulting list plus one, creating a kind of recursive problem. In the algorithm, this is solved by iterating over number of numbers to be replaced with a new value, solving a simple linear equation in each iteration, and checking whether the resulting mean value is lower than lowest replaced value and higher than highest kept value.

The answer to the original problem is that it takes an average of $4.3869...$ turns to reach score of $30$ with $6$ dice with the table describing an unambiguous strategy to reach this average. A closed-form for the general average number of turns or general strategy without using the table seems unlikely to exist.

Upade: it turns out there is quite a simple strategy for optimal number of turns - every turn, you just roll the dice that give you highest chance of getting the required score with that roll, which with some practice can be calculated relatively easily even without paper. I don't have a proof for why this is the case, but it has been confirmed computationally with about 0.02% deviation from computed values after about 1000000 trials.

The alternative problem has already been solved by Ben Barden.