# Optimal strategy in the following game:

In this game, 12 hidden D6s are rolled and summed. The player is given the total of the rolled dice. The player will then guess a number from 1 to 6. If there is a unrevealed dice with that number, it is revealed, otherwise a strike is given. The player's goal is to guess all of dice in as few strikes as possible.

My initial thought is that the optimal strategy is to have a set of allowed numbers, and to always guess the number that is closest to the current average, but this can't be true, because there are certainly some 6s and 1s.

What is the optimal way to get the lowest expected (or average) score?

• Only one die is revealed at a time, or if I say "6" are all sixes revealed? (Part of the problem here is that the singular of "dice" is "die," so the phrase: "if there is a unrevealed dice with that number, it is revealed" is mixing plural and singular. – Thomas Andrews Apr 27 '15 at 21:01
• Only 1 die is revealed even if there are multiple. – Nathan Merrill Apr 27 '15 at 21:54

In principle you can find an optimal strategy by dynamic programming: let $F(n,t,S)$ be the maximum number of strikes remaining in an optimal strategy where there are $n$ unrevealed dice with sum $t$, and it is known that all the unrevealed dice are in set $S \subseteq \{1,\ldots, 6\}$ (because guesses in the complement of $S$ have produced strikes). Let $P(n,t,S) = \{x \in S^n: \sum x = t\}$ be the set of possible $n$-tuples of unrevealed dice, and $R(n,t,S) = \{y \in S: y \in x \ \text{for some}\ x \in P(n,t,S)\}$. Of course, you don't want to guess $y$ if $y \notin R(n,t,S)$. If you do guess $y$, and $y$ is in fact one of the unrevealed dice, then you go into state $(n-1, t - y, S)$. If it is not, you register a strike and go into state $(n, t, S \backslash \{y\})$ (which can only happen if $R(n, t, S \backslash \{y\})$ is nonempty. Thus $F(n, t, S) = \min_{y \in R(n,t,S)} G(n,t,y,S)$, where $$G(n,t,y,S) = \cases{\max(F(n-1,t-y,S),1+F(n,t,S\backslash \{y\})) & if R(n,t,S\backslash \{y\}) \ne \emptyset\cr F(n-1,t-y,S) & otherwise\cr}$$ and an optimal strategy in the state $(n,t,S)$ is to choose $y \in R(n,t,S)$ that minimizes $G(n,t,y,S)$. The number of possible states is not terribly large (there are only $63$ nonempty subsets of $\{1,\ldots, 6\}$ and at most $61$ possible totals for $12$ dice), so it shouldn't be too hard to compute all these.