[hddqsb]

Interesting post, but the premise is misleading. The title says "Best ... strategy" and the first sentence reads "This post will derive an optimal ... strategy", but there is nothing to suggest that this strategy is optimal.

One strategy which is obviously optimal is to use minimax (recursively, not like Knuth's Mastermind strategy which was mentioned by @christiangenco), however this strategy is not computationally feasible.

---

Aside: There is something broken with this site's history manipulation. When I open the blog post it creates two entries in the history list, and clicking the browser's back button takes me to a page with the same URL as the blog post that displays "Error Page Not Found".

[less_less]

I agree with your criticism. It's also not clear what "optimal" means, since there are multiple desirable metrics: fewest average guesses, fewest worst-case guesses, etc.

Full brute force is allllmost computationally feasible, at least for some metrics. Like you could probably exhaust the search space in a month on a small cluster, at least if you're minimizing either (worst case, average case) or (pr(lose), pr(take 6 guesses), pr(take 5 guesses) ...). It's also significantly easier to brute-force in hard mode.

[taejo]

> One strategy which is obviously optimal is to use minimax (recursively, not like Knuth's Mastermind strategy which was mentioned by @christiangenco), however this strategy is not computationally feasible.

With some restrictions it's possible to do a full minimax. In that case, you still don't know if it's optimal, but you've at least got an upper bound. And it turns out, it's possible to guarantee victory while finishing in an expected 3.554 guesses. Alternatively, you can finish in an expected 3.212 guesses if you don't mind a small chance of taking more than six guesses.

[hddqsb]

To add to my previous comment...

I realise that this blog post is about a strategy for humans to use rather than for an ideal solver, so a degree of inexactness is to be expected. Still, I dislike the way the words "best" and "optimal" are thrown around. The guesses presented in the blog post are "best" in the sense that they maximise some heuristic (namely covering the most frequent letters), but the blog post doesn't explain why that heuristic is good.

Regarding an ideal solver, to prove that a strategy is optimal (in terms of the worst-case number of guesses) one would need to show two things:

- That the worst-case number of guesses of the strategy is N, and

- That there is no strategy whose worst-case number of guesses is less than N.

The first is quite easy to do (for an automated strategy): simply run the strategy against each possible secret "wordle" and keep track of the maximum number of guesses. The second is much harder.

(Since the worst-case number of guesses is likely to be small, this is not a fine-grained way to compare strategies. One could also look at the distribution of the number of guesses to get more information; for example a strategy that takes 6 guesses half the time and 5 guesses the other half is clearly better than a strategy that always takes 6 guesses. Still, it would be really nice if people who published automated strategies also published their worst-case number of guesses.)

Knuth's strategy is optimal (in terms of the worst-case number of guesses) for Mastermind, but it might not be optimal for Wordle. Knuth showed that his strategy takes at most 5 guesses for Mastermind, and presumably there is no strategy that takes at most 4 guesses. But his strategy is not optimal in terms of the distribution of the number of guesses; there are strategies with a lower average number of guesses (and the same worst-case number of guesses; see https://mathworld.wolfram.com/Mastermind.html). Reducing the set of possibilities as much as possible is a very sensible strategy, but it might not be optimal because the number of guesses required to solve a set depends on the nature of its elements, not just on the size of the set. In the case of Mastermind, this inefficiency does not affect the worst-case number of guesses; but in the case of Wordle it might.