Optimal Strategy in Dice Game

In a recent interview I received the following question (an optimisation/strategy game)...which left me a bit stumped. The rules of play, you start with 0 points, then:

Roll three fair six-sided dice;

Now you have the option:

Hold: i.e. accept the values shown on your dice as the score for your turn. There is a caveat, if two or more dice show the same values, then all of them are flipped upside down - e.g. 1 becomes 6

OR

reroll the dice: You may choose to hold any combination of the dice on the current value shown (so you can choose to keep 1 dice the same and then reroll the other two). Rerolling costs you 1 point – so during the game and perhaps even at the end your score may be negative. You can roll an infinite number of times...

My thoughts:

So clearly the best possible score is 18 and is achieved by rolling three 1s on the first roll The reroll penalty prevents rolling forever to get 18. If the value of the dice is greater than the expected value of rerolling them (accounting for the penalty), then you should stick... I guess what I am asking is how do I work out the expected value of rerolling them (accounting for the penalty) and how does this fit into the optimal strategy...

• I may have misunderstood your question but say you get $1,5,6$ in the first round and decide to keep $1$ and reroll $5$ and $6$ then you get $1,3$ in the second round. What's your score then? Is it $6+6+3-1=14$? If that's the case then I don't understand how the accepted answer can ignore the rule about taking the opposite sides of those with the same value. Commented Jan 29, 2021 at 3:47
• @NeatMath you example of how the game works is the case...I was thinking about this over night...@jlammy perhaps you can expand on this please...sorry to bombard you with qs.
– bob
Commented Jan 29, 2021 at 8:19
• You need to say whether you flip an existing die if you roll a matching number. Until the rules are clear there is no answer. NeatMath laid out the question well. By the way, you can only ping one person per comment with an @ Commented Jan 29, 2021 at 14:58
• sorry for the delay @RossMillikan. To clarify: Lets say on we rolled (1,2,5) on first roll and chose to roll the 2 again (held the 1 and 5) and got a 1. Dice now look like (1,1,5), and we hold all dice now knowing that the flip occurs on the hold...so the final result would be (6,6,5). In summary: yes. You flip an existing dice if you roll a matching number.
– bob
Commented Jan 30, 2021 at 8:26

The fact that you flip dice if they show the same value doesn't actually affect any expected values. You are just as likely to roll say $$(1,1)$$ (which gets flipped to $$(6,6)$$) as you are to roll $$(6,6)$$ in the game with no flipping. So I will essentially completely ignore this rule.

Now suppose our strategy is "re-roll a die if it comes up at most $$x$$, else hold the value". Then by the law of total expectation, your expected payoff $$E$$ for that particular die is $$E=\frac{x}{6}(E-1)+\left(1-\frac{x}{6}\right)\frac{x+7}{2}\implies E=\frac{42-3x-x^2}{2(6-x)}.$$ Since $$6$$ is a small number, at this point you may as well just plug in the values of $$x$$, and you will find

$$x$$ $$E(x)$$
$$0$$ $$3.5$$
$$1$$ $$3.8$$
$$2$$ $$4$$
$$3$$ $$4$$
$$4$$ $$3.5$$
$$5$$ $$1$$

So our expected value is $$12$$ with the best strategy. We have two equally good strategies: either "hold values of three or more", or "hold values of four or more".

• Thank you @jlammy is you solution for two or three dice?...Perhaps I am not understanding...
– bob
Commented Jan 28, 2021 at 15:54
• @bob sorry, my table came out horribly (still trying to see why). It turns out that $x=2$ and $x=3$ both have the same expected value! So "hold if you roll 3 or more" and "hold if you roll 4 or more" are equally good strategies. Strategy is for three die, but I analyse the die one at a time. Commented Jan 28, 2021 at 15:56
• nice table... Will try and get my head around your ans...more than likely questions to follow. thanks
– bob
Commented Jan 28, 2021 at 16:14
• why should the dice be considered independently? Wouldn't the decision to reroll be based on the overall total?
– bob
Commented Jan 28, 2021 at 16:17
• Yes sure, but you can choose whether to re-roll each individiual die right? E.g. if you roll $(6,5,1)$, your decision to re-roll the die that came up $1$ is completely independent of the fact that your first die came up $6$ -- if you had $(2,5,1)$ instead, you should still decide to re-roll that third die. Commented Jan 28, 2021 at 16:19

A good programmer (which I'm not) can implement Hugo Manet's idea and get the optimal strategy. But I believe there is no nice pattern for one to solve mathematically based on my calculation with only one step projection (thus it's not optimal). Still one can get a feeling as to why it's not so simple (I could be wrong). Here's a summary:

• If you get $$3$$ identical numbers, stick if it's $$111,222,333$$; reroll all three if you have $$444,555,666$$;

• If you get $$3$$ distinct numbers:

1. If total points $$\ge 11$$ then stick;

2. If total points $$\le 9$$ then keep the smallest, reroll the two bigger ones;

3. If total points $$=10$$: keep the bigger two and reroll $$1$$ if it's $$\{1,3,6\}$$ or $$\{1,4,5\}$$; stick if it's $$\{2,3,5\}$$.

• You get a pair and a third one which is different. This is very complicated.
1. When the pair is $$1, 2$$ or $$3$$: if the third one is $$4/5/6$$, stick; otherwise reroll the third one. Notice that if we have $$\{2,2,3\}$$ we get a tie: either stick, or reroll $$3$$;

2. When the pair is $$4$$: if the third one is $$5/6$$, stick; otherwise keep the third one but re-roll both $$4$$'s;

3. When the pair is $$5$$: if the third one is $$1/2$$, keep it and reroll both $$5$$'s; otherwise reroll only one $$5$$ and keep the other two;

4. When the pair is $$6$$: if the third one is $$1$$, keep it and reroll both $$6$$'s; otherwise reroll only one $$6$$ and keep the other two.

Again, the above is not the optimal because it only looks at one step. The optimal strategy should be decided by going backward from step 18, for example, where you know you should stick because otherwise you'd end up with a negative score.

R code below:

It was done in a rush so there's plenty of space for improvement.

pts = function(a)
{
u = unique(a);
if(length(u)==3) {
p = sum(a);
} else if(length(u)==1) {
p = 3*(7-u);
} else
{
M = sum(a)-sum(u)
p = sum(u)-M + 2*(7-M);
}
p
}

onestep <- function(a)
{
p = rep(-1,8);

p[8]=pts(a);

for(i in 1:6)
{
# 001
p[1] = p[1] + pts(c(a[1], a[2], i))/6

# 010
p[2] = p[2] + pts(c(a[1], i, a[3]))/6

# 100
p[4] = p[4] + pts(c(i, a[2], a[3]))/6

for(j in 1:6)
{
# 011
p[3] = p[3] + pts(c(a[1], i, j))/36

# 101
p[5] = p[5] + pts(c(i, a[2], j))/36

# 110
p[6] = p[6] + pts(c(i, j, a[3]))/36

for(k in 1:6)
{
# 111
p[7] = p[7] + pts(c(i,j,k))/216;
}
}

}
indx = which(p==max(p));
c(p, p[indx], indx)
}

sink("mseoutput.txt")

for(i in 1:6)
{
for(j in i:6)
{
for(k in j:6)
{
out <- onestep(c(i,j,k));
cat(i,j,k,out);
cat('\n');
}
}
}

sink()

• very nice , were the above number born in anyway out of @jlammy work? Why 11 for example in step 1? Thanks
– bob
Commented Jan 29, 2021 at 13:12
• *sorry, were were
– bob
Commented Jan 29, 2021 at 13:35
• No it's from a little program I wrote. $11$ is what it is. Basically for each triple I compute $8$ different cases (from stick to reroll all $3$) and for each case compute the average score (and adjust for $-1$ point if not sticking) and pick the highest score. Commented Jan 29, 2021 at 13:44
• Thanks for the time spent on this!!! If your willing would be interested to see the code...cheers
– bob
Commented Jan 29, 2021 at 13:53
• Sure. I've included the code. Commented Jan 29, 2021 at 14:39

One important point is that, anytime in the game, your best action depends only on the dice on the table, and not on the number of penalties you've accumulated so far. Even if you have -20 in penalties, if your dice are bad, maybe you should reroll (and worry that the dice aren't fair after all).

Apart from that, I don't see much good properties on the problem, so to me it's a modeling problem and you have to compute it.

You start with an benefit function $$f_0(\{x,y,z\})$$ which is the value of your dice combination, and you compute successively the benefit if you also add the choice to reroll at most $$i$$ times : $$f_{i+1}({x,y,z}) = \max f_i(\{x,y,z\}), (-1 + \mathbb E [f_i(\{X,y,z\})]), \dots$$.

Since the $$f_i$$ are increasing and bounded, they converge (exponentially fast) to a $$f_\infty$$, and you can make your choice by comparing $$f_\infty(\{x,y,z\})$$ and $$(-1 + \mathbb E [f_\infty(\{X,y,z\})])$$, etc.

If you want the exact values of the expectation, you can see the transformation of $$f_i$$ to $$f_{i+1}$$ as a matrix multiplication (once you reached the point where the choice of the $$\max$$ will be stable), so you just have to find its stable point.