Fun question. Today I was struck by this seemingly simple problem: given a roll with 5 dice, the outcome which is $\{1,1,1,6,6\}$, and two rolls remaining, what is the optimal strategy to gain a "large straight", i.e. $\{1,2,3,4,5\}$ or $\{2,3,4,5,6\}$, after the third roll? Candidate options are to fix a $1$ (or $6$) and roll the others, to fix both a $1$ and a $6$, or re-roll with all dices. Before the last roll one can again fix dices, but also choose to roll with any dices that were fixed before.
The problem is that the $\{1,1,1,6,6\}$ gives no hints for which of the two large-straight options one should go. If one would have only one roll remaining, the optimal strategy would be to re-roll with all dice. But now, with more rolls remaining, the optimal strategy seems to depend on the "optimal strategy distribution" of the next roll.
Any insights?
You can calculate the optimal strategy by using dynamic programming to work backwards from the last throw. Since there is no distinction between which dice the numbers appear on, there are "only" $252$ configurations obtainable with the five dice. However, since it is never advantageous to keep multiple copies of a number when re-rolling, it is only the $63$ possible sets of up to $5$ numbers shown on the dice, or kept when re-rolling, that need to be considered. In the following tables, each such set $\ \{a_1, a_2,\dots,a_r\}\subseteq$$\{1,2,3,4,5,6\}\ $ is represented by the number $\ 2^{a_1-1}+$$2^{a_2-1}+$$\dots$$+2^{a_r-1}\ $, with the empty set being represented by $0$. The "target" sets, one of which it is desired to obtain, are $\ \{1,2,3,4,5\}\ $ and $\ \{2,3,4,5,6\}\ $, represented by the numbers $31$ and $62$, respectively.
Final throw
The probabilities of obtaining one of the target sets from a single throw is given in the immediately following table for every possible non-target set of numbers kept fixed, when the remaining non-fixed dice are thrown. The integer representing the set of numbers on the dice kept fixed is given in the third column, and the number of dice thrown in the second column. The sets of numbers shown on the dice kept fixed can be divided into $14$ classes, with the probability of obtaining one of the target sets being the same for every set within a particular class.
If the fifth column of a row contains an entry, then none of the throws listed in that row are optimal. In all those cases, the numbers on the dice kept fixed includes a $1$ or a $6$ or both. The entry in the fifth column indicates the row of the table where a more favourable throw can be found. The sets of dice listed as kept fixed in the indicated row are all proper subsets (obtained by removing one or both of the $1$ or $6$ from the set of dice kept fixed, and including it or them among those thrown) of those listed in the original row.
If the fifth column of a row contains no entry, then the throws listed in that row are optimal provided that the dice rethrown hadn't shown any of the numbers $2,3,4$ or $5$ that was not already among the set of numbers on the dice kept fixed.
The only cases in which it is optimal to keep a $1$ or a $6$ fixed are when the numbers on the dice kept fixed form one of the sets listed in rows $8$ or $11$. Each of those sets includes a $1$ or a $6$, but not both, and exactly $2$ or $3$ of the numbers $2,3,4,$ or $5$. If, instead of keeping the $1$ or the $6$ fixed in these cases, you include it amongst the dice thrown, the set of dice kept fixed will be one of those listed in rows $6$ or $9$ of the table. For the throws in both rows $6$ and $8$ the probability of obtaining a target set is $\frac{1}{18}\ $, so it makes no difference whether you choose a throw in row $8$, keeping the $1$ or $6$ fixed, or choose the corresponding throw in row $6$ by including the $1$ or $6$ among the dice thrown. For the throws in row $11$, however, the probability of obtaining a target set is $\ \frac{1}{6}\ $, which is greater than the probabilty of $\ \frac{1}{9}\ $ obtainable from the corresponding throw in row $9$. In this case, therefore, the $1$ or $6$ should be kept fixed.
\begin{array}{c|c|c|c} \stackrel{\text{Row}} {\stackrel{\text{number}}{\small\text{}}}&\stackrel{\text{Number of}} {\stackrel{\text{dice thrown}}{\small\text{}}}& \stackrel{\text{Indicators of sets}} {\stackrel{\text{of dice kept fixed}}{\small\text{}}}&\stackrel{\text{Probability of}} {\stackrel{\text{hitting a target}}{\small\text{}}}& \stackrel{\text{Better}} {\stackrel{\text{throws?}}{\small\text{}}}\\ \hline 1&5&0&\frac{5}{162}\\ \hline 2&4&1,32& \frac{1}{54}&\text{row } 1\\ \hline 3&4&2,4,8,16& \frac{1}{27}\\ \hline 4&3& 33&0&\text{row } 1\\ \hline 5&3&3,5,9,17,34,36,40,48&\frac{1}{36}&\text{row } 3\\ \hline 6&3&6,10,12,18,20,24& \frac{1}{18}\\ \hline 7&2&35,37,41,49& 0&\text{row } 3\\ \hline 8&2&\matrix{7,11,13,19,21,25,\\ 38,42,44,50,52,56}& \frac{1}{18}&\\ \hline 9&2&14,22,26,28&\frac{1}{9}&\\ \hline 10&1&39,43,45,51,53,57&0&\text{row } 6\\ \hline 11&1&15,23,27,29,46,54,58,60&\frac{1}{6}&\\ \hline 12&1&30&\frac{1}{3}&\\ \hline 13&1&47,55,59,61&0&\text{row } 11\\ \hline 14&0&31,62&1&\\ \hline \end{array}
Penultimate throw
The next table gives the probabilities of reaching a target set with two throws left, assuming that the final throw is chosen optimally. The interpretation of the table is otherwise the same as that of the one above.
The only difference in the optimal choices with two throws left is that the throws listed in row $8$ are no longer optimal. These all result in a probability of $\ \frac{53}{2^2\cdot3^4}\approx0.16\ $ of reaching a target set (assuming the final throw will be optimally chosen), whereas the corresponding throws in row $6$, obtained by throwing the $1$ or $6$ instead of keeping it fixed, result in a probability of $\ \frac{179}{2^2\cdot3^5}\approx0.18\ $ of reaching a target set. \begin{array}{c|c|c|c} \stackrel{\text{Row}} {\stackrel{\text{number}}{\small\text{}}}&\stackrel{\text{Number of}} {\stackrel{\text{dice thrown}}{\small\text{}}}& \stackrel{\text{Indicators of sets}} {\stackrel{\text{of dice kept fixed}}{\small\text{}}}&\stackrel{\text{Probability of}} {\stackrel{\text{reaching a target}}{\small\text{}}}& \stackrel{\text{Better}} {\stackrel{\text{throws?}}{\small\text{}}}\\ \hline 1&5&0&\frac{40861}{2^4\cdot3^9}\\ \hline 2&4&1,32& \frac{5135}{2^3\cdot3^8}&\text{row } 1\\ \hline 3&4&2,4,8,16& \frac{1133}{6^5}\\ \hline 4&3& 33&\frac{529}{2^2\cdot3^7}&\text{row } 1\\ \hline 5&3&3,5,9,17,34,36,40,48&\frac{151}{6^4}&\text{row } 3\\ \hline 6&3&6,10,12,18,20,24& \frac{179}{2^2\cdot3^5}\\ \hline 7&2&35,37,41,49& \frac{5}{2^3\cdot3^2}&\text{row } 3\\ \hline 8&2&\matrix{7,11,13,19,21,25,\\ 38,42,44,50,52,56}& \frac{53}{2^2\cdot3^4}&\text{row } 6\\ \hline 9&2&14,22,26,28&\frac{5}{2\cdot3^2}&\\ \hline 10&1&39,43,45,51,53,57&\frac{5}{2\cdot3^3}&\text{row } 6\\ \hline 11&1&15,23,27,29,46,54,58,60&\frac{11}{2^2\cdot3^2}&\\ \hline 12&1&30&\frac{5}{9}&\\ \hline 13&1&47,55,59,61&\frac{1}{6}&\text{row } 11\\ \hline 14&0&31,62&1&\\ \hline \end{array}
Optimal choices for $\ \mathbf{\{1,1,1,6,6\}}\ $
The first, second and fourth rows of the preceding table show that throwing all five dice on the second last throw results in a probability of $\ \frac{40861}{2^4\cdot3^9}\approx0.13\ $ of reaching a target set, keeping a $1$ or a $6$ and throwing four dice results in a probability of $\ \frac{5135}{2^3\cdot3^8}\approx0.098\ $ of reaching a target set, and keeping both a $1$ and a $6$ and throwing three dice results in a probability of $\ \frac{529}{2^2\cdot3^7}\approx0.060\ $. The optimal choice is therefore to throw all five dice.
With $3$ throws left, the probabilities of eventually reaching a target set (assuming optimal play on the last two throws) are approximately $0.26$ if all five dice are thrown, $0.22$ if a $1$ or $6$ is kept fixed and four dice are thrown, and $0.18$ if both a $1$ and a $6$ are kept fixed and three dice are thrown. Thus again, it is best to throw all five dice.