In this game numbers are added to a list, the sum of all the numbers in the list at the end of the game is your score.
The game consists of 10 rounds, in each you roll 2 (6-sided) dice and choose one.
If the result is higher than the last number in the list, the result is added to the end of the list. Otherwise result is discarded. Any number can be added after a 6.
Example:
1. Roll 1 and 4 – Choose 1
List [1] – Current Score 1
2. Roll 3 and 4 – Choose 3
List [1, 3] – Current Score 4
3. Roll 1 and 3 – No valid choice
List [1, 3] – Current Score 4
4. Roll 2 and 6 – Choose 6
List [1, 3, 6] – Current Score 10
5. Roll 1 and 4 – Choose 4
List [1, 3, 6, 4] – Current Score 14
etc
What is the optimal strategy for this game?
Is it to always keep the higher number?
I have tried to look at different methods like Value Iteration but can't seem to get it to fit this problem. My main problem is working out what the probabilities should be. The probability a given number appears on either dice is 11/36 but then the probabilities don't sum to 1 and I think this is throwing it off.
10th Round – obviously pick highest number
9th Round
Choose 6 if possible
If Choose 5 – expected score is 5 + 11/36 * 6 = 6 5/6
If Choose 4 – expected score is 4 + 11/36 * 6 + 9/36 * 5 (because if you can pick 6 you do)
…
I can see how this helps, thanks.
Further thoughts:
Can we expand this to an n-sided dice with m rounds.
Does it change if we add more dice?
What if we changed the restrictions to something different?
Best Answer
As you say, the chance that any number is on at least one die is $\frac {11}{36}$. At each point you have a favorite number, the one that you will keep in preference to any other. You will keep that one with probablity $\frac {11}{36}$. You will keep your second favorite with probability $\frac 9{36}$ because it loses two cases to the faovrite and so on down the scale.
Clearly you should always keep a $6$ if available. It give the most points and least restriction on what happens after.
As Empty2 suggested, think about the $9$th round. If you keep a $5$ your expected score in the last two rounds is $5+\frac {11}{36}\cdot6=\frac {246}{36}$ because you have to roll a $6$ in the tenth round to score. If you keep a $4$ your expected score is $4+\frac 9{36}\cdot 5 +\frac {11}6=\frac {255}{36}$. This is slightly better. Keeping a $3$ gets you $3+\frac 7{36}\cdot 4 +\frac 9{36}\cdot 5 +\frac {11}6=\frac {247}{36}$ Keeping a $2$ gets you $2+\frac 5{36}\cdot3+\frac 7{36}\cdot 4 +\frac 9{36}\cdot 5 +\frac {11}6=\frac {226}{36}$. Keeping a $1$ gets you $1+\frac 3{36}\cdot 2+\frac 5{36}\cdot3+\frac 7{36}\cdot 4 +\frac 9{36}\cdot 5 +\frac {11}6=\frac {196}{36}$
This shows you should keep the numbers on round $9$ in preference order $6,4,3,5,2,1$ We can make a spreadsheet showing the expected score from this round and later if you keep each number. For each round your favorite number to keep is a $6$, then is the one that gives the next highest score going forward. Through round $6$ the rule is simple-keep a $6$ and otherwise keep the smallest number you can. In rounds $7,8,9$ the order is confused by the short game and in round $10$ you should keep the largest number you can.
If there are more sides on the dice the perturbation at the end may get longer, but I suspect the early idea of take the smallest number available will still hold. If you roll more dice the chance of getting at least one $6$ gets higher and it may well be better to keep higher numbers. With lots of dice you will almost always get a $6$ so if you don't you should clearly keep the highest number available, which will very likely be a $5$.
Rounds are across the top, number kept down the left column. Entries are the expected score from this round forward if you keep the number to the left