Others have computed lots of empirical results for this thing (as indeed have I) but it would be nice to have some theorems! So here's an analysis of three families of simple cases for which we can (1) determine the optimal sequence of die-choices, (2) explicitly compute the resulting win probabilities (in two of the cases) and their limit (in all three), and (3) show that the limit is rational. Unfortunately this family doesn't include the specific one the original question was about :-).
Obviously we can consider this question with any set of dice. (For that matter, we can consider it with any set of weighted-average operations of finite support, but the case with dice seems hard enough already.)
I make the following claims.
Zeroth: the sequence of win-probabilities tends to a limit; if the sequence of die choices is eventually periodic, then the limit of the sequence of win probabilities is rational.
First: in the case $\{k\}$ -- that is, just one $k$-sided die and nothing more -- there are no choices to make and the limit is $2/(k+1)$. I'm not sure whether there's a nice formula for the individual win probabilities.
Second: in the case $\{2,k\}$ -- that is, one $k$-sided die and one 2-sided die, with $k>2$ -- the sequence of optimal choices repeats with period $k$: when the number of points remaining is a multiple of $k$ one should use the $k$-sided die, and otherwise the 2-sided one. Below I give formulae for the actual win probabilities; their limit turns out to be
$$\frac6{9-\frac2k+\frac3{(-2)^k-1}}.$$
Third: in the case $\{k,k+1,\dots,2k-1\}$, the sequence of optimal choices consists of $k-1$ instances of $k$ followed by $k,k+1,\dots,2k-1$, after which you can just pick $k$ every time; the sequence of win probabilities is constant from index $k$ onward. The constant is $\frac{(k+1)^{k-1}}{k^k}$.
As remarked by Rob Pratt, the neatest way to formulate this question is as a recurrence relation for the probabilities: writing $V(n)$ for the probability of success when starting with $n$ points, we have $V(n)=0$ for negative n, $V(n)=1$ for $n=0$, and otherwise $V(n)$ is the largest of the averages of the previous $d$ values, where $d$ ranges over the available dice. (The parameter $k$, the number of faces on the larger die, is left implicit.)
As a warm-up, let's deal with the easiest case (this is the first of the theorems promised above): just one die. In this case there are no choices, and we are just dealing with a linear recurrence relation: $V(n)=\frac1k\sum_{0<j\leq k}V(n-j)$, with $V(n)=0$ for negative $n$ and $V(0)=1$. Consider $U(n)=\sum_{1\leq j<\leq k}jV(n+j)$. We have $U(-k)=k$ because the only nonzero term is $k\cdot1$. We also have
$$\begin{eqnarray}
U(n)-U(n-1)&=&\sum_{1\leq j<\leq k}jV(n+j)-\sum_{1\leq j<\leq k}jV(n+j-1) \\
&=&\sum_{1\leq j<\leq k}jV(n+j)-\sum_{0\leq j<\leq k-1}(j+1)V(n+j) \\
&=&kV(n+k)-\sum_{0\leq j<k}V(n+j) \\
&=&0,
\end{eqnarray}$$
so $U$ is a constant sequence. In particular its limit is $k$; but this limit is also $1+\cdots+k$ times the limit of sequence $V$, which therefore equals $\frac{k}{1+\cdots+k}=\frac2{k+1}$.
This is also a good place to prove the zeroth theorem above, because its proof reuses the (only) idea in the proof just given.
The first part of the zeroth theorem says that the sequence of win probabilities tends to a limit. This is kinda obvious, because we are performing a sequence of averaging operations, but proving it seems trickier than I expected. (But maybe I'm missing something simple.) Let $d$ be the number of faces on the largest die that we use infinitely often; once we have stopped using any larger ones that we use only finitely often, to get from one vector of $d$ consecutive win-probabilities to the next we append a new component equal to the average of some of those $d$ win-probabilities (infinitely often, the average of all of them) and discard the first component. This means that the smallest of $d$ consecutive win-probabilities is nondecreasing, and the largest is nonincreasing; so both tend to limits; can these limits be different? Suppose that their limits are $L,U$ respectively, with $L<U$. Suppose we're far enough along the sequence that no value is outside the interval $[L-\epsilon,U+\epsilon$. (We'll choose a suitable value of $\epsilon$ shortly.) At some point we must see a value no bigger than $L+\epsilon$. The value after that is no bigger than $\frac{(d-1)(U+\epsilon)+L+\epsilon}{d}=\frac{(d-1)U+L}d+\epsilon$; by induction subsequent values are also no bigger than this. If we choose $\epsilon<\frac{U-L}{2d}$ then this means that after seeing a value close to $L$ we never again see a value bigger than $U-\frac{U-L}{2d}$, which means that $U$ is not after all the limit of the largest win probability in a consecutive sequence of $d$ values. So the assumption $L<U$ leads to a contradiction, and in fact those limits are the same, which means that the sequence as a whole tends to a limit.
The other half of the zeroth theorem: When the sequence of die-choices is periodic, the limiting win probability is always rational. Why? Well, letting $d$ be the number of faces on the largest die, once periodicity is attained (say, with period $p$) there is some $d$-by-$d$ matrix $M$ such that when $v$ is a (column) vector of $d$ consecutive win probabilities, $Mv$ is the vector of win probabilities for starting numbers $p$ higher; so we are interested in the limit of $M^nv$ where $v$ is the specific column vector once periodicity is reached. The components of $M$ and $v$ are obviously all rational. Now, we have $Mu=u$ where $u$ is a vector all of whose components are equal, because $M$ is built out of averaging operations. So $(M-1)$ is singular, where $1$ denotes the identity matrix; so there's at least one vector in its left nullspace: a (row) vector $w$ such that $wM=w$. We then have $wv=wM^nv\rightarrow wl$, where $l$ is the (column) vector all of whose elements are the limiting win-probability. In particular, if the components of $w$ are rational and their sum is nonzero then this implies that the limiting probability is rational.
There are familiar algorithms for finding the nullspace of a matrix, using only arithmetic operations; in particular, if the matrix's components are all rational then the nullspace has a basis of vectors all of whose components are rational. So we're done provided we can find a suitable $w$ whose components don't add up to 0.
If we can't, this means that everything in the left nullspace of $M-1$ is orthogonal to the column vector $c$ all of whose components are 1. The orthogonal complement of the left nullspace is precisely the image (i.e., the span of the columns), so this would mean that $c$ is in the image; that is, for some vector $u$ we have $Mu-u=c$. But $M$ is a product of matrices $M_i$ which have the following property: for any vector $u$, we have $\mathop{\textrm{min}} u\leq\mathop{\textrm{min}} Mu\leq\mathop{\textrm{max}}Mu\leq\mathop{\textrm{max}}u$. So the same is true of $M$ itself, and in particular $\mathop{\textrm{max}}Mu\leq\mathop{\textrm{max}}u$, which is incompatible with $Mu-u=c$ since the maximum component of $u+c$ is bigger than that of $u$.
Hence there is a left-nullspace vector $w$ whose sum isn't 0, so from $wv=wl$ and the fact that all components of $l$ are equal it follows that their common value is rational.
OK, back to the second theorem promised above, the {2,k} case. This will be harder work.
(The following all feels very clumsy, and I suspect it is difficult to follow without pencil and paper or a symbolic-algebra system. I bet there are ways to streamline it a lot.)
We have a proposal for what the sequence of die-choices ought to be: the $k$-sided when $k|n$, otherwise the 2-sided. (So, e.g., when $k=5$ this goes 222252222522225 and so on.) Write $W(n)$ for the resulting sequence of winning probabilities. We will be done if we can show that for each $n$, applying the "wrong" die to the sequence $W$ at step $n$ makes things worse, or at least no better. That is, when $k|n$ we would like it to be true that $\frac{W(n-2)+W(n-1)}2\leq\frac{W(n-k)+\cdots+W(n-1)}k$; otherwise we would like the inequality to be reversed. This immediately yields a proof by induction that in fact the sequences $V$ and $W$ are the same.
The thing that makes this a promising line of attack is that now we are operating entirely with the known sequence $W$ and "just" need to prove some inequalities for it. (In other cases that empirically seem to have a periodic sequence of optimal choices, the same approach should be applicable, though possibly more painful.)
The first step is to figure out what the values $W(n)$ actually are. Each is determined by the previous $k$ values (in general, this holds where $k$ is the largest number of faces on any of the dice). So let's look at what happens to the last $k$ values in the sequence when we compute the next one. If we represent those last $k$ values by a column vector $X$, what happens is that we shift them up one (discarding the first = oldest) and replace the last one with the average of some of its predecessors; that is, we premultiply $X$ by a matrix that has $k-1$ rows with 1s just above the main diagonal, and a final row that's $(\frac1k \frac1k \dots \frac1k)$ if we're using the $k$-sided die or $(0 \dots 0 \frac12 \frac12)$ if we're using the 2-sided one. Call these matrices $M_k$ and $M_2$.
So, we begin with the vector $(0 \dots 0 1)^\top$ which gives the $k$ values ending with the 0th. And then we premultiply, successively, by $M_2$ $k-1$ times, then $M_k$ once, then $M_2$ $k-1$ times, etc. So advancing a full $k$ places in the sequence means premultiplying by $M_kM_2^{k-1}$.
It's not difficult to compute the powers of $M_2$. For $r<k$, in fact, $M_2^r$ has $k-r$ upper rows with 1s $r$ places above the main diagonal, followed by $r$ lower rows $(0\,\dots\,0\,a_i\,b_i)$ for $1\leq i\leq r$, where $a_n=\frac13-(-1)^n\frac1{3\cdot2^n}$ and $b_n=1-a_n$. (Easy proof by induction.) For instance, here's $M_2^4$ where $k=7$ (so $r=4,k-r=3$: 3 rows of diagonal on top, 4 rows of 2 columns below):
$$\begin{pmatrix}
0&0&0&0&1&0&0 \\
0&0&0&0&0&1&0 \\
0&0&0&0&0&0&1 \\
0&0&0&0&0&\frac12&\frac12 \\
0&0&0&0&0&\frac14&\frac34 \\
0&0&0&0&0&\frac38&\frac58 \\
0&0&0&0&0&\frac5{16}&\frac{11}{16} \\
\end{pmatrix}$$
In particular, $M_2^{k-1}$ has a 1 at the top right corner, two columns below that, and everything else is 0s. And now we can compute $M:=M_kM_2^{k-1}$: all but the two rightmost columns are 0, and there we have $k-1$ rows with $a(1\dots k-1),b(1\dots k-1)$ followed by one row with $\frac{a_1+\cdots+a_{k-1}}k,\frac{1+b_1+\cdots+b_{k-1}}k$. Calling those $c_k,d_k$ we have $c_k=\frac13+\frac2{9k}\left((-2)^{-k}-1\right)$ and $d_k=\frac23-\frac2{9k}\left((-2)^{-k}-1\right)$.
We can now say fairly explicitly (we will be able to be even more explicit later) what the sequence $W$ is. Write $X(0)$ for the column vector with $k-1$ 0s followed by a 1, and $X(m+1)=M_kM_2^{k-1}X(m)$; then concatenating the elements of all the $X(m)$ gives precisely the sequence $W$ starting from element $-(k-1)$.
At this point, we have enough to prove the inequality we're interested in in the case $k|n$. Doing a 2-average instead of a $k$-average at step $n$ means that the last (= leftmost) factor of $M$ we multiply by is replaced with $M_2^k$, which looks just like $M$ except that its last row has $a_k,b_k$ instead of $c_k,d_k$. So if the last two elements of $X(m-1)$ were $p,q$ then we need to verify that $a_kp+b_kq\leq c_kp+d_kq$. We may readily check that $c_k-a_k=-(d_k-b_k)<0$, so our condition will hold provided $p\leq q$. Obviously this is true the very first time, where $p=0,q=1$. After that, we have $\binom{p}{q}=\binom{a_{k-1}\ b_{k-1}}{c_k\ d_k}\binom{p'}{q'}$ where $p',q'$ are the previous values of $p,q$ -- and once again we have $c_k-a_{k-1}=-(d_k-b_{k-1})<0$, so $p\leq q$ follows from $p'\leq q'$, and is therefore always true by induction.
We also need to prove that the opposite inequality holds when $k\nmid n$. The machinery developed above doesn't make this so straightforward, because the $k$-average involves elements from two successive $X(m)$ vectors. But, as we'll see, it's not so bad.
We can make our calculations of the $W(n)$ more explicit. Those $M_kM_2^{k-1}$ matrices all have 0s except in their two rightmost columns, which means that each $X(m+1)$ can be computed from just the last two elements of its predecessor $X(m)$ (which is obvious when we think about what things we're averaging to get the elements of $X(m+1)$). So let's write $Y(m)$ for the last two elements of $X(m)$; we have $Y(m+1)=NY(m)$ where $N$ is the bottom-right 2x2 submatrix of $M_kM_2^{k-1}$, which is to say $\left(\begin{smallmatrix}a_{k-1}&b_{k-1}\\c_k&d_k\end{smallmatrix}\right)$. We have a fairly simple explicit formula for each entry in that 2x2 matrix, and the further nice fact that the rows add up to 1, and this suffices to give us a (rather ugly) explicit formula for the powers of the matrix. I confess that I used a computer-algebra system to find it; once found it's easy to verify by induction. The $m$th power is
$$N^m=\frac1{\beta-\alpha}\left[\begin{pmatrix}
\beta&-\alpha \\ \beta&-\alpha
\end{pmatrix}+\begin{pmatrix}
-\alpha&\alpha \\ -\beta&\beta
\end{pmatrix}t^m\right]$$
where
$$\begin{eqnarray}
\alpha&=&6sk \\
\beta&=&-3sk+2s-3k \\
s&=&(-2)^k-1 \\
t&=&2(-2)^{-k}\frac{s+3k}{9k}.
\end{eqnarray}
$$
(Of course the computer algebra system didn't give it to me in that nice convenient form!) It's easy to see that $|t|<1$, so the limit as $m\rightarrow\infty$ is
$$\frac1{\beta-\alpha}\begin{pmatrix}
\beta&-\alpha \\ \beta&-\alpha
\end{pmatrix}$$
and so the limiting value of the sequence $W$ (which as someone already pointed clearly has a limit) is just $\frac\alpha{\alpha-\beta}$, matching all the empirical values for the limit in the {2,k} case already calculated in comments above. The formula given near the start is equivalent to this.
And we can now be a bit more explicit about the values of $W$. We have $\binom{W(mk-1)}{W(mk)}=N^m\binom01$ ($N^m$ being the matrix we just computed), and then for $0\leq r<k$ we have $W(mk+r)=a_rW(mk-1)+b_rW(mk)$. (Note that $a_0=0,b_0=1$ so the case $r=0$ works.)
And, to simplify things just a little further, $N^m\binom01$ is
$$\frac1{\beta-\alpha}\begin{pmatrix}
-\alpha+t^m\alpha \\
-\alpha+t^m\beta
\end{pmatrix}$$
and so
$$\begin{eqnarray}
W(mk+r)&=&[a_r(-\alpha+t^m\alpha)+b_r(-\alpha+t^m\beta)]/(\beta-\alpha) \\
&=&[-\alpha+(a_r\alpha+(1-a_r)\beta)t^m]/(\beta-\alpha) \\
&=&[-\alpha+(a_r(\alpha-\beta)+\beta)t^m]/(\beta-\alpha) \\
&=&[-\alpha+\beta t^m]/(\beta-\alpha)-a_rt^m
\end{eqnarray}$$
where, again,
$$\begin{eqnarray}
\alpha&=&6sk \\
\beta&=&-3sk+2s-3k \\
s&=&(-2)^k-1 \\
t&=&2(-2)^{-k}\frac{s+3k}{9k}.
\end{eqnarray}
$$
Now we have a reasonably simple formula for $W(mk+r)$, it's time to prove that other inequality. Suppose $0<r<k$ and let's compare the average of the $k$ terms preceding $W(mk+r)$ with $W(mk+r)$ itself. The difference, which we would like to be $\geq0$, is
$$\begin{eqnarray}
&&\frac{-\alpha+\beta t^m}{\beta-\alpha}-a_rt^m
-\frac1k\sum_{0\leq r'<k}\left(\frac{-\alpha+\beta t^{m-[r'\geq r]}}{\beta-\alpha}-a_{r'}t^{m-[r'\geq r]}\right)\\
&=&\frac{\beta t^m}{\beta-\alpha}-a_rt^m
-\frac1k\sum_{0\leq r'<k}\left(\frac{\beta t^{m-[r'\geq r]}}{\beta-\alpha}-a_{r'}t^{m-[r'\geq r]}\right) \\
&=&\frac{t^m}k\left[\frac{\beta k}{\beta-\alpha}-k a_r
-\sum_{0\leq r'<k}\left(\frac{\beta t^{-[r'\geq r]}}{\beta-\alpha}-a_{r'}t^{-[r'\geq r]}\right)\right] \\
&=&\frac{t^m}k\left[\frac{\beta k}{\beta-\alpha}-k a_r
-\left(k\frac{\beta}{\beta-\alpha}+(k-r)\frac{\beta (t^{-1}-1)}{\beta-\alpha}\right)+\left(\sum_{0\leq r'<k}a_{r'}+\sum_{r\leq r'<k}{a_r'}(t^{-1}-1)\right)\right] \\
&=&\frac{t^m}k\left[-k a_r
-(k-r)\frac{\beta (t^{-1}-1)}{\beta-\alpha}+\sum_{0\leq r'<k}a_{r'}+\sum_{r\leq r'<k}a_{r'}(t^{-1}-1)\right]
\end{eqnarray}$$
where $[r'\geq r]$ is Iverson notation denoting 1 if the proposition inside is true and 0 if it's false. Now we may easily check $t^{-1}-1=(\alpha-\beta)/2(s+3k)$, so this equals
$$\begin{eqnarray}
&&\frac{t^m}k\left[-k a_r
+(k-r)\frac{\beta}{2(s+3k)}+\sum_{0\leq r'<k}a_{r'}-\frac{\beta-\alpha}{2(s+3k)}\sum_{r\leq r'<k}a_{r'}\right].
\end{eqnarray}$$
Since we always have $t\geq0$, this is enough that we can now prove the result for any fixed choice of $k$ just by checking it in $k-1$ cases -- the expression inside the brackets is independent of $m$. But let's try to do it in generality.
Those sums are easily evaluated: the first is $\frac{k}3-\frac29(1-(-2)^{-k})$ and the second is $\frac{k-r}3-\frac29((-2)^{-r}-(-2)^{-k})$. We may readily verify that the first of these equals $-((-2)^{-k}\beta)/9$, and then (using this and the fact that $(-2)^{-r}=1-3a_r$) that the second equals $-\frac{r}3-\frac{(-2)^{-k}\beta}9+\frac23a_r$. So we want to prove that this is non-negative:
$$\begin{eqnarray}
&&-k a_r
+(k-r)\frac{\beta}{2(s+3k)}+\frac{(-2)^{-k}\beta}{9}+\frac{\beta-\alpha}{2(s+3k)}\left(\frac{2k-r}3-\frac{(-2)^{-k}\beta}9-\frac23a_r\right).
\end{eqnarray}$$
With a bit of computer algebra (or a bit of patience) we find that this equals
$$\begin{eqnarray}
&&\frac19\frac{-2s+3k}{s+3k}\left(1-(-2)^{-r}-3(1-(-2)^{-r})k+3r\right).
\end{eqnarray}$$
The first factor is negative ($s$ always dominates). The second factor is also negative because $k>r$ and the terms with $(-2)^{-r}$ are small. Hence this is non-negative, so averaging the last $k$ terms rather than the last 2 is never better in cases where $W$ assumes we are averaging the last 2, hence by induction $V=W$ (since we already proved the corresponding inequality for the case where $W$ assumes we are averaging the last $k$). We're done!
I've kept 3/4 of my promise above, and dealt with the cases $\{k\}$ and $\{2,k\}$. What about the third theorem listed above, dealing with $\{k,k+1,\dots,2k-1\}$?
For the first $k$ steps we cannot possibly do better than using the $k$-sided die each time, because averaging further back just brings in zeros. So our sequence begins (after the initial infinity of zeros) $1, \frac1k, \frac{k+1}{k^2}, \frac{(k+1)^2}{k^3}, \dots, \frac{(k+1)^{k-1}}{k^k}$.
After this, note that obviously averaging $k$ numbers together with their average (i.e., what we get by choosing the $k+1$-sided die) gives that same average again; and that since those $k$ numbers are decreasing we do strictly worse by averaging fewer; and that since they are preceded by zeros we do strictly worse by averaging more. Hence we should average $k+1$ next, and the last number will repeat.
And after this a similar situation repeats itself and recommends that we average $k+2$, and then $k+3$, and so on until we reach $2k-1$. (Formal proof would be by induction. The details are easy.)
At this point we have $k$ consecutive instances of the exact same value, preceded by $k-1$ strictly smaller things. So we can either average $k$, giving the same average a $(k+1)$th time, or else get a worse result; we must do the former.
Again, a similar situation repeats itself with successively larger numbers of identical values, until eventually we have had the same value $2k-1$ times in a row. At this point we can choose any die we like and always get the same result.
So, our sequence of winning probabilities consists of $\frac{(k+1)^{j-1}}{k^j}$ for $j=1,2,\dots,k$, followed by infinitely many copies of that last figure.
(It is in fact easy to see that adding more dice with $\geq 2k$ faces to the set makes no difference either to the optimal choices or to the sequence of win probabilities.)
What are the prospects for extending any of this to other cases more like the one MJD asked about? Not good (at least if we want general theorems rather than answers in specific cases; the latter might be possible) until we have at least one new idea. The first and third theorems used special-case tricks that certainly won't generalize. The key things that make the analysis in the second theorem possible are:
- We could guess in advance that the sequence will repeat, and what the repeating pattern will be.
- This lets us compute what the "right" winning probabilities are, and then confirm our guess at the pattern by checking that choosing different dice never helps.
- For that repeating pattern, we could get a not-too-horrible explicit expression for the winning probabilities that result, because the repeating pattern is nice and simple.
- This means that the computation of the "right" winning probabilities yields something we can actually work with and prove things about.
- In particular, it ends up coming down to computing powers of a 2x2 stochastic matrix.
- This means that we don't have to do anything much more complicated than summing geometric progressions. We aren't e.g. computing eigenvalues and eigenvectors of large matrices.
So what happens in the {4,6,8} case that MJD originally asked about? Empirically it looks as if there is a repeating pattern: it has period 116 (with 73 choices of the d4, 19 of the d6, and 24 of the d8). The good news is that the periodicity seems to be immediate -- the first 116 choices repeat for ever. So in principle we do in this case have our ansatz for what the right answers ought to be, and we could compute the resulting win-probabilities in terms of powers of some 8x8 matrix and a ton of other linear algebra. But getting those into a form explicit enough to prove things about might be extremely painful, or even impossible without some further insights.
