2022-01-26

Most mathematical questions one could have about Wordle are settled by now, and a few remain open. I summarize here what is known, as far as I can tell.

tl;dr

• If we exploit the 2315-words solution list, everything is known:
  • Wordle can be solved in 3.4212 guesses on average, with 5 guesses at worst (i.e., 100% of the time comfortably within the allowed 6 guesses).
  • The corresponding decision tree is optimal both in terms of average, and in the worst case: It was proven rigorously that it is not possible to get an average lower than 3.4212, nor is it possible to have a worst case of 4 guesses, even independently.
  • In hard mode, Wordle can be solved in 3.5085 guesses on average, (with 6 guesses at worst, i.e. 100% of the time). Or, with a different decision tree, it can be solved with a slightly worse average, but always within 5 guesses. Again, both trees are optimal for their respective objective functions.
• For the full 12972-words dictionary, the worst case is known:
  • Wordle can be solved in 6 guesses at worst (i.e. 100% of the time just within the allowed 6 guesses).
  • The above result is optimal: It was proven rigorously that it is not possible to find a decision tree whose worst case is 5 guesses or less.
  • In hard mode, Wordle can be solved in 14 guesses, but there is no optimality result here.
  • So it is unknown whether hard mode Wordle can be solved 100% of the time within 6 guesses.
  • Not much is known yet about the average, as far as I can tell.

Game setup

First, let’s clarify a few things about the game:

• Wordle comes with a dictionary of 12972 words that the player is allowed to use as guesses. They are essentially all 5-letter combinations one could reasonably argue are English words. The “secret” word that the player has to discover is also always in that dictionary.

  It is so trivially easy to cheat at Wordle that there is no point to it: The list of secret words is right there in the code of the game. The daily secret words are picked sequentially from that list, so they are all known since 2021-06-19 (“cigar”) and until 2027-10-20 (not going to spoil it for you), for a total of 2315 scheduled secret words.

  One could always look up that list for the current date and solve the game immediately at the first guess. However, this is not much fun (mathematically), so we need to define the game somehow. There are two obvious options:

  Featured Content Ads

  add advertising here

  Join Bing with ChatGPT-4

  Use the new internet where you get what you ask, Fast and precise using AI.

  https://www.bing.com

  • “Full dictionary”: we consider that the secret word could be any word from the full 12972-word list.

  • “Solution list”: we know that not every word can be a secret word, and take advantage of the knowledge of the list of 2315 scheduled secret word (but we ignore its order, which would trivially allow us to win every game in one guess).

• While many focused on finding the best “first word” to play as a guess, the first guess is just a tiny part of what we really want: A decision tree. A decision tree not only tells you which guess to play first, but accompanies you as you play, telling you which guesses to play subsequently in function of the information given you by the game as you play (i.e. all the letter colors 🟩🟨⬜ so far). I only cover here fixed/deterministic decision trees, which will always reach a given secret word in the same way, because it is straightforward to give formal evaluations of how good they are.

• The word optimal has taken quite a mauling lately in Wordle-related writings. Just to be to be absolutely clear, a solution is optimal only if no better solution can possibly exist. In particular, there is no such thing as a “more optimal” solution.

  Featured Content Ads

  add advertising here

  COGNAC Metaverse

  Explore World's first metaverse that is as real as our Real world.

  https://cognac.knowasiak.com

• Now, regarding what we optimize, there are two natural choices:

  • The worst-case number of guesses. That is, given a decision tree, what is the maximum number of guesses necessary to correctly guess any secret word? In other words, after how many guesses does the decision tree guarantee that we win the game?

  • The average number of guesses. What is the average, over all possible secret words, of the number of guesses a decision tree will take to get a win?

  As we will see, those are competing objectives, sometimes irreconcilably, sometimes not so.

• Buried in the options, Wordle features a hard mode. The game is different in hard mode, in that only words that satisfy the hints given earlier are allowed as player guesses. (For example, if a letter is colored green 🟩 after one guess, that letter must be present in the same position in all subsequent guesses.)

  There are subtleties about the rules regarding words with repeated letters, and this particularly affects hard mode. However, it seems that by now everyone agrees what the rules are.

Solution list: 2315 possible secret words

In this section, we assume that we know the list of 2315 scheduled secret words, but we ignore the list’s order (it would be trivially easy otherwise).

For this case, Cyrus Freshman set up a nice automated leader board with a standardized input format. There we can directly find that five distinct people have found decision trees that solve Wordle in 3.4212 average guesses and (simultaneously) 5 worst-case guesses: Jonathan Olson Peter Tseng, CHIsomorphism, Alex Selby, as well as rahsosprout.

While I suspect all employed similar general approaches (recursive enumeration / backtracking with tree pruning and some form of caching), I will now mainly defer to Alex Selby’s nice writeup, because it is the most thorough and because the corresponding code can answer more of our questions. Alex and Peter both implemented their algorithms in such a way that not only they get good decision trees, but they can also subsequently perform an accelerated complete enumeration and prove optimality. Alex indicates that the latter is by far the most difficult part computationally: finding good trees (that happen to be optimal) is quick, proving that they are indeed optimal is much more expensive.

The best known decision tree for this version of Wordle leads to a win in 3.4212 guesses on average. In the worst case, this same tree wins the game in 5 guesses (i.e., 100% of the time, never even using the 6th guess). Alex reports on the result of the complete enumeration, formally proving that this is optimal, both in average (no tree has an average of less than 3.4212) and in the worst case (no tree wins all games in 4 guesses at most).

For hard mode, both Alex and Peter found a decision tree with in 3.5085 guesses on average and 6 guesses at worst (i.e., 100% wins in 6 guesses). Hard mode is interesting in that, if we are willing to sacrifice a bit on the average, we can improve the worst case: Alex found a different decision tree with 3.5448 guesses on average, but a worst case of 5 guesses! Again, Alex reports optimality on both fronts.

In terms of worst case, I could confirm the optimality results both for standard Wordle and hard mode.

Full dictionary: 12972 possible secret words

In this section, we assume that the game can pick secret words from its whole 12972-word dictionary. The number of potential secret words is now about 5.6x as large as in the previous case, dramatically increasing the size of an already large enumeration space.

Still, the same type of emumeration / backtracking tricks work even in this case, and with a careful implementation I found a decision tree with 6 guesses in the worst case. Even with the full dictionary of 12972 possible secret words, it is thus still possible to win every Wordle game within the 6 allowed guesses! I did not try to optimize for the average number of guesses, but it can still be measured: 4.2308 guesses on average over the 12972 words. I was not able to perform complete enumeration for 5 guesses, so there was no optimality guarantee. However, complete enumeration did rule out the existence of trees with 4 guesses in the worst case, leaving a frustrating gap between 4 and 6.

The frustration was short-lived, fortunately, as Alex Peattie proved that it is impossible to build a decision tree with 5 guesses in the worst case, making the result sharp. The proof is much more interesting than complete enumeration: it relies on cleverly finding provably-difficult-to-disambiguate word subsets and it can be checked directly by inspection without any computational tools (although Alex did double-check it with OR-Tools’ constraint programming solver).

Thanks of Alex’s proof, we now have an optimality guarantee in terms of the worst case at 6 guesses. It is still an open question whether we can find a decision tree that is optimal in terms of its average number of guesses.

Hard mode is deceptively hard to enumerate over when using the full dictionary, at least with my naive approach. I suspect that the additional structure could enable more pruning. Still, at this stage I could only find a tree with 14 guesses (!) in the worst case (4.6168 on average), and no optimality guarantee.

It thus is still an open question, with the full dictionary, whether hard mode can be always solved within the 6 allowed guesses. And the best possible average number of guesses is unknown as well in hard mode, obviously.