1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Apr 27 '15 at 21:01
  • $\begingroup$ Only 1 die is revealed even if there are multiple. $\endgroup$ – Nathan Merrill Apr 27 '15 at 21:54
0
$\begingroup$

When you say "as few strikes as possible", do you want to minimize the maximum number of strikes possible, or the expected number? Those may result in different optimal strategies. I'll suppose it's the maximum that you want to minimize. I'll also assume only one die is revealed at a time, even if there are several with the number you guessed.

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.

$\endgroup$
  • $\begingroup$ I'm actually looking to minimize the expected number, and clarified my question. $\endgroup$ – Nathan Merrill Apr 27 '15 at 21:56
  • $\begingroup$ The dynamic-programming method can easily be modified to deal with the expected number. $\endgroup$ – Robert Israel Apr 27 '15 at 22:51

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.