Optimal strategy in the following game:

95 Views Asked by At

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?

1

There are 1 best solutions below

2
On

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.