27
$\begingroup$

Wordle is a game by Josh Wardle in which you try to guess a 5-letter word in at most six attempts. After each guess, the letters which are not in the word are highlighted in grey, the letters which are in the word, but are in the wrong place are highlighted in yellow, and the letters which are in the correct spot in the word are highlighted green. If a guess contains repeated letters, but there is only one instance of that letter in the word, the second instance of the letter is marked grey.

I am wondering what perfect Wordle play looks like. One can easily gain access to a day's answer by digging around the source of the webpage, which also allows one to reduce the difficulty of the game significantly by considerations on the game's dictionary of solutions. Because the the site imposes more limited strategies in this way, I am interested in the strategy a computer would execute for the general Wordle game as defined by the rules listed above. I am considering a strategy to be optimal if it minimizes guesses needed to find the answer on average, without any knowledge of the word beforehand. I am also not necessarily looking for a strategy that is executable by a human, rather I would like a series of steps that can be taken by a theoretical perfect player to minimize guesses.

For my own play, I have found that (in a certain Scrabble dictionary) the most common letters in 5-letter words are S, E, A, O, and R. I usually guess 'AROSE' as my first guess (although AEROS and SOARE work just as well) which seems to give the best chance of finding multiple yellow and green letters. If 'AROSE' is all grey, this seems to narrow the possible answers by a considerable amount, but if any of the letters are correct it seems that it would not actually that helpful for a perfect player. Therefore, I think that an actual perfect strategy would aim to halve the solution space with every guess, but I don't know if this is correct or how I would prove its correctness. I am also unsure how I would algorithmically determine the best word for executing this strategy at each step.

There is also the consideration of Hard Mode, a toggle on the website that forces the player to use letters in future guesses which have been confirmed as yellow or green. I imagine that a strategy for Hard Mode would look considerably different from a normal strategy, so I would be interested in answers regarding this as well as the normal mode.

$\endgroup$
11
  • $\begingroup$ I'm looking for an algorithm or decision tree. The strategy is not meant to be executable by a human. $\endgroup$ Jan 4 at 19:17
  • 5
    $\begingroup$ "perfect strategy would aim to halve the solution space with every guess" That would only be perfect in a game with yes/no questions. Here each guess gives many possible results. Ideally you'd want a first word where all possible colour combinations that could result represent a similar sized search space. The number of possible colour combinations is not quite $3^5$, as for example it is impossible to have 4 correctly placed and one incorrectly placed letters, and others are certain to represent small remaining search spaces (e.g. two letters swapped). So a factor of about 200 rather than 2. $\endgroup$ Jan 5 at 13:36
  • $\begingroup$ @JaapScherphuis This makes much more sense, but seems to make it even harder to execute such a strategy. If you come up with something concrete, I'd love to read your answer $\endgroup$ Jan 5 at 15:15
  • 1
    $\begingroup$ There are max 15 different answers. You cannot have more than 5 letters rights, and these are in the right or wrong place. I believe a good strategy would be to minimize the worst case, i.e. guess the word that minimizes the maximum number of remainig words among all replies. If you follow me. $\endgroup$
    – Florian F
    Jan 5 at 15:57
  • $\begingroup$ Instead of AROSE, you could use two guesses to assess the presence of the top ten most common letters. I've seen STAIR and CLONE being suggested elsewhere. $\endgroup$ Jan 5 at 16:51

11 Answers 11

17
$\begingroup$

Diagram of the handcrafted portion of the depth 6 LARNT tree

Assumptions:

  • Optimal firstly means never losing (rather than some definition of a good average depth).
  • The 12972 words in the Wordle source code are the only valid guesses.
  • The target word is selected uniformly at random from the 12972 words (no special knowledge about the possible solutions from the source code).

Having pursued a worst-case-scenario analysis here and there over the last few weeks, I have finally managed to compute a never-lose strategy with tree depth <= 6 for all 12972 wordle words.

Like @Tim I eventually came to understand the role of the 19 _ILLS words, the worst off-by-one letter set, and it was at this point I found this post about the problem. These 19 words present a significant challenge due to the large number of different consonants that the starting letter can be. However, I have come to refer to these 19 as the "lucky words" because of these requirements:

  1. Test at least 18 of the 19 starting letters
  2. Test all vowels (PILLS vs PULLS vs POLLS, etc)
  3. At least one or the repeatable letters (L and S) probably needs to be tested in more than one position, (KILLS, TILLS, KILTS etc) (slightly complicated by whether you achieve 18 or 19 for requirement 1 and there may be some necessary vs sufficient subtlety I have left unexplored).

These requirements are so constraining that it was possible to exhaust the 5-word search space computationally! The result is 1415 sets of 5 words that can perfectly isolate the 19 _ILLS words from each other and all other wordle words. These 1415 sets actually only contain 747 distinct words.

One of those words was LARKS, e.g. (FJELD, LARKS, SCOWP, THUMB, VYING) and given that it performed well for Daniel Mathias and ranked at the top of my tie-breaker list I gave it a try. The search algorithm is min-max on the number of child words with tiebreaks decided by a p * (1-p) information theory idea to uniquely rank all (just overall) the words a bit like what Sam Wang describes in another post here.

General application of min-max with liberal use of these 747 words with harmonious consonants on the exceptional cases seems to allow us to tuck in all but one of the 6+ paths under the LARKS root word. I was not able to perfectly isolate the 15 _ESTS off-by-one words with any suitable complement to LARKS. The 00002 wordle result on LARKS seems to be impossible to perfectly solve in the remaining 5 guesses.

So I ended up with a tree with just one 7-guess word and seemingly no way to make that final improvement which was very frustrating. With this strategy you would just have to lose if it was VESTS! Still 12971 out of 12972 is not bad.

After a few other speculative attempts I ended up noticing LARNT as a highly-ranking word in one of my other experiments and wondered if it could do just that little bit better than LARKS. This time it has turned out to work with some carefully selected words with harmonious combinations of consonants.

You will note that LARNT WEMBS SPICK VOZHD FUGLY perfectly isolates the 19 _ILLS words from each other and all other wordle words.

Additionally

LARNT SHOES TOWZY KOPJE BEFOG perfectly isolates the 15 _ESTS words from each other and all other wordle words. ( I am curious whether the existence of the word KOPJE makes LARNT viable where LARKS wasn't)

Everything else follows from suitably tie-broken min-max or several hand-prescribed uses of KEMPS GYVED TINES CHAWK BADGE IDEES VIBEX YIELD SCHAV KEMBS GIVED SINED BACKS FLIMP

after the LARNT root word.

I will tidy up the code and share a link to the complete tree and intermediate word lists.

Update here is the complete solution:

https://github.com/markmightknow/wordle_worst_case_analysis/blob/main/wordle_tree_larnt_lte_6_20220201.txt

Update 2 There is another 6-tree out there for the 12972 words, found by Laurent Poirrier and starting with "SPAER", and it has better average depth statistics. You can read all about it here:

https://www.poirrier.ca/notes/wordle/

Update 3 Laurent Poirrier has also found a third 6-tree starting with LARKS after all! Between this and the SPAER tree we have now confirmed the constraints described for the _ILLS words in my answer above are too rigid (sufficient but not necessary) but it was worth assuming them as they did allow discovery of the LARNT 6-tree in a reasonable amount of computing time.

$\endgroup$
8
  • 1
    $\begingroup$ This is fantastic! I appreciate how it does not use any extra knowledge about possible solutions. Furthermore, for real Wordles your decision tree performs pretty well, guessing most of the recent ones in 4 or fewer. $\endgroup$ Feb 1 at 14:29
  • $\begingroup$ As far as I know the guess words are 10576 and the answer words are well known words from a set of 2315 words $\endgroup$
    – rep_movsd
    Feb 1 at 16:40
  • 1
    $\begingroup$ @rep_movsd jodag's answer provides such a tree. puzzling.stackexchange.com/a/114678/45094 $\endgroup$ Feb 2 at 15:56
  • 1
    $\begingroup$ Congrats on cracking this! "Test all vowels (PILLS vs PULLS vs POLLS, etc)" This was a really good heuristic choice. "The result is 1415 sets of 5 words that can perfectly isolate the 19 _ILLS words from each other and all other wordle words. These 1415 sets actually only contain 747 distinct words." These are awesome insights! $\endgroup$
    – Tim
    Feb 4 at 5:39
  • 1
    $\begingroup$ @justhalf, sure, you can explore such a tree in a file or interactively with the links on the subpage: poirrier.ca/notes/wordle/download.html Note that "depth 4" means 5 guesses in this context. $\endgroup$
    – mmk
    Feb 12 at 13:22
7
$\begingroup$

Firstly, any solution using the "possible answers" is cheating in my view. This list are the answers in order for the next 5 years, not just some list of reasonable looking words. What prior knowledge would otherwise tell you ACTED isn't a possible answer?

I have a partial answer to the question and an open question.

Local Min Max

If you pick a word there are 243 = 3*3*3*3*3 possible configurations of Black/Yellow/Green which narrows down the list of possible words. One heuristic would be to minimise the maximum number of possible words at each guess. That is, suppose the game doesn't lock in the word at each turn but maintains a list of possible words and will only pick the word when it is forced by what it has told you. This creates a game tree starting with SERAI, leaving a maximum number of 697 possible words in the worst case (for fun, GYPPY is the worst possible starting word according to this rule). The words thereafter change wildly dependent on configuration of Black/Yellow/Green. The full game tree using this rule in the worst case would take 8 guesses for 2 words, GILLS and KILLS. The good news is of the approximately 13,000 words in the dictionary this leaves only 57 words which take more than 6 guesses.

Example

All of the words SLICE, SLIME, SLIPE, SLIVE, SMILE, SPILE, SWILE have the same configuration after guessing SERAI and TILDE. The 3rd word CLAMP is used to uniquely pick between them giving scores of 4 each.

Local vs global minimums

Since we're so close to a perfect game tree in the view of never losing this raises a question. What if a sub-optimal earlier guesses lead to branches that efficiently filter into the different words later? We've optimized for local minimums but that doesn't exclude the possibility of a global minimum which almost certainly is different. Changing the starting word and then continuing with the min max strategy shows that PASEO is better that SOARE despite the fact that there are there are more possible words after PASEO (776) than SOARE (769). It's almost certainly true that among the possible game trees there's one that improves the one above. Sadly, the space of possibilities looks too big to reasonably explore.

Can you do better with a global minimum on the number of words that take more than 6 guesses?

UPDATE: yes, LARES with min max strategy has just 53 words that take 7 guesses

As a sanity check I skipped and checked the 340th first word LEAFS with min max strategy...this has just 44 words that take 7 guesses. Mind blown, I don't know anymore.

$\endgroup$
7
  • $\begingroup$ This is basically the same approach I have been working on, though I have been using the smaller list of 2315 words, considering that to be a complete list of valid guesses. The main obstacle is how to choose the best guess when two or more guesses have the same maximum. +1 for applying this strategy to the full list. $\endgroup$ Jan 9 at 14:23
  • $\begingroup$ @DanielMathias if my experience is anything to go by, any word in the top 15% at each branch could possibly be part of the global minimum. The effects down at the 5/6th guess are so esoteric $\endgroup$ Jan 9 at 14:31
  • 1
    $\begingroup$ Mind blown? How about this: Using my implementation of this min-max strategy, and choosing the first best (read: not optimal) guess, except to give priority to guesses that could be on target, I checked 40 top candidates for Optimal First Guess. Of these only three had more than 50 words taking more than 6 guesses. Best in category for 'none more than 7' were LARES and LEARS with 35 words taking 7 guesses. Best overall was TALES with a mere 21 words taking 7 guesses and only one taking 8. LEATS and TEALS were not far behind. $\endgroup$ Jan 11 at 0:30
  • 1
    $\begingroup$ I'm using the 12,972 words in the list provided by @pingswept. If you are using the same, then our differing results is due only to differences in second and subsequent guesses. $\endgroup$ Jan 11 at 10:08
  • 2
    $\begingroup$ @Konchog all the anagrams of raise do well $\endgroup$ Jan 17 at 17:40
7
$\begingroup$

The list of valid Wordle answers is available in the Wordle website's source code. There are two lists of words: 2315 valid solutions and then 10657 other five letter words that no normal person would ever guess.

If you count the occurrences of the letters in the possible solutions, you get these values:

'e': 1233, 'a': 979, 'r': 899, 'o': 754, 't': 729, 'l': 719, 'i': 671, 's': 669, 'n': 575, 'c': 477, 'u': 467, 'y': 425, 'd': 393, 'h': 389, 'p': 367, 'm': 316, 'g': 311, 'b': 281, 'f': 230, 'k': 210, 'w': 195, 'v': 153, 'z': 40, 'x': 37, 'q': 29, 'j': 27})

There is only one valid solution made of the top five letters: ORATE. (OATER appears in list of valid guesses, but is not a valid solution, because what the hell is an OATER anyway? "A movie or television show about cowboy or frontier life; a western movie," it seems.)

(AROSE would be the only valid solution if you take your frequencies from the Scrabble dictionary.)

There is no valid word made of the second group of 5 letters: LISNC, nor can we fix the problem by swapping C for U (LISNU). Our next best choice is swapping N for U (LISUC), which gives the valid word SULCI, "a depression or groove in the cerebral cortex." (SULCI is not valid solution.)

But it's not clear that deploying SULCI as your second choice is optimal. (If we take letter position into account, there may be better first choices than ORATE.)

After your first choice, the optimal move may be to set any green letters aside, and then come up with a word that places, say, 2 yellow letters in their most likely locations, and then fills in the remaining 3 letters with the highest frequency letters you haven't eliminated. Delightfully, that's actually pretty hard to do.

Wordle using ORATE and SULCI as first guesses

Above is an example of implementing that strategy. After discovering that the solution contained A and L in the first two guesses, I tried MANLY, which contained A and L in new locations, plus M, N, and Y, which were among the most common letters not yet tested.

Just to illustrate the idea, other decent choices might have been MADLY or AMPLY, though I think MANLY is slightly preferable because of the relative prevalence of N, compared to D or P.

In placing your yellow letters, you can try to follow the likelihood that a letter appears in each position, as described by the bar chart in Mahmood Hikmet’s explainer: https://youtu.be/hJJaYvxQh8w?t=125

This would suggest a few general targets for words after ORATE and SULCI:

  1. Put C and S at the beginning.
  2. A, I, O and U go in the middle.
  3. Put E, R, and T at the end.

@JaapScherphuis, in a comment below, suggests the pair LATER and SONIC, which uses the 10 most common letters.

@Mahmood Hikmet suggests that SLATE is the optimal first word, taking letter position into account (but I think he calculated just from the valid solutions, which seems suboptimal to me). But that would allow a second guess of ORCIN (some chemical found in colorless lichen, I guess?).

Also note that the solution set appears to omit plurals. I assume this is deliberate. The only solutions that end in S are:

['floss', 'crass', 'abyss', 'rebus', 'truss', 'focus', 'fetus', 'glass', 'class', 'chaos', 'dross', 'cress', 'bless', 'bliss', 'brass', 'cross', 'amass', 'bonus', 'locus', 'grass', 'ethos', 'humus', 'basis', 'guess', 'lupus', 'torus', 'minus', 'dress', 'amiss', 'mucus', 'gross', 'gloss', 'virus', 'chess', 'ficus', 'press']

There are actually a few plurals that slipped through by ending in I, like CACTI, FUNGI, and RADII, plus a few odd nouns like GEESE, TEETH, and WOMEN.

(I guess I should say that I recognize that this is not the full algorithm that you're hoping for, but it seemed ridiculous to try to stuff all of this in a comment.)

If it's useful, my frequency counting code and the word sets are available at: https://github.com/pingswept/wordle-strategy/blob/main/strategy.py

$\endgroup$
14
  • 1
    $\begingroup$ For two words using the top ten most frequent letters, you could use LATER and SONIC. $\endgroup$ Jan 5 at 18:03
  • 1
    $\begingroup$ I'm looking for an answer that doesn't depend on knowing the list of possible solutions, but this is still very interesting, thank you $\endgroup$ Jan 5 at 18:07
  • 1
    $\begingroup$ @DanielMathias What I meant by "General Wordle game" in my question is a game in which every 5 letter word is a possibility and is chosen at random. Knowing that the solution must belong to a specific subset of words reduces the difficulty of the game in a way that I find less interesting. $\endgroup$ Jan 8 at 21:13
  • 2
    $\begingroup$ @EphraimRuttenberg My previous comment still applies. Any optimal strategy must know all possible solutions, even if all valid words are possible solutions. For the Wordle game as it is, all solution words can be guessed with five or fewer attempts without guessing or even considering words that are not in the solution set. $\endgroup$ Jan 8 at 21:31
  • 2
    $\begingroup$ @ChrisH On another forum I've seen STAIN CHORE PLUMB, and STALE GROIN DUMPY proposed as good sequences. $\endgroup$ Jan 19 at 16:56
7
$\begingroup$

Optimal Strategy

We can compute the optimal strategy with these simplifications:

  • we only play on Hard Mode (note: I assumed guesses must be potential answers, but it's actually more lenient)
  • valid guesses AND solution are limited to Wordle's 2315 solution dictionary

Optimal Strategy

(see the next section, Strategy Format, to learn how to interpret the links)

If 6 guesses are allowed (standard Wordle), then the optimal strategy uses 3.55378 guesses on average.

If 5 guesses are allowed, then the optimal strategy uses 3.71404 guesses on average.

If 7+ guesses are allowed, then the optimal strategy uses 3.51836 guesses on average.

Strategy Format

Here's an excerpt from the optimal strategy for 6 guesses max:

plate _~~_#  angle #####
plate _~~_#  angle ~__~#  valve #####
plate _~~_#  angle ~__~#  valve _####  halve #####
plate _~~_#  angle ~__~#  valve _####  halve _####  salve #####
plate _~~_#  angle ~__~#  valve _##_#  false #####
plate _~~_#  angle ~__~#  valve ###_#  value #####
plate _~~_#  angle ~__##  fable #####
plate _~~_#  angle ~__##  fable _#_##  ladle #####
plate _~~_#  angle ~__##  fable _####  cable #####
plate _~~_#  angle #__##  amble #####
plate _~~_#  angle #__##  amble #__##  aisle #####
plate _~~_#  angle #_~##  agile #####
plate _~~_#  angle ~_###  eagle #####
plate _~~_#  angle ~~_~#  lance #####
plate _~~_#  angle ~_~~#  large #####
plate _~~_#  angle ##_##  ankle #####

How to interpret this:

  • # - is a correctly placed letter
  • ~ - is a correct letter in the wrong spot
  • _ - is an incorrect letter

plate is an optimal first guess. If the response is _~~_# (e is correct, l and a are in the wrong spot), there are only 16 possible answers, and now we guess angle. If the response is ~__##, only 3 answers are possible (fable, ladle, cable), and we'll guess fable. If the response is #####, then we're done. Otherwise, guess ladle for _#_## or cable for _####.

Notice that there's one line per answer. And, you can quickly see how many guesses each answer took. For example, salve takes five guesses.

How this was done

Observations

It's important to notice that after any number of guesses, we only care about which words are still possible answers. (Proof: given the set of remaining possible answers, it's not helpful to know that a guess of orate led to a certain response -- we can just note "Hey, all these possible answers would give the same response to a guess of orate").

Algorithm

We can compute the best average score possible for "hard mode" with this recursive strategy:

bestAverageScore( candidate words ):

  if there's only one candidate word:
     return 1 (just guess that word)

  for each guess in candidate words:
     (calculate the score for this guess by considering each guess result)
     for each guess result:
        evaluate bestAverageScore( candidate words consistent with guess result )

  return the minimal score

Code

https://github.com/TomasSirgedas/OptimalWordle (C++)

More Details

Smaller dictionaries

Instead of using all 2315 words for guesses+solutions, let's consider using only the first N of these words.

This table shows the average number of guesses for an optimal strategy:

N       5 guesses max  6 guesses  unlimited guesses
100     2.53           2.53       2.53
200     2.69           2.69       2.69
300     2.80333        2.80333    2.80333
400     2.885          2.885      2.885
500     2.98           2.98       2.98
600     3.04833        3.04833    3.04833
700     3.09           3.09       3.09
800     3.12875        3.12875    3.12875
900     3.15667        3.15556    3.15556
1000    3.205          3.198      3.198
1100    3.23455        3.22727    3.22727
1200    3.26           3.25       3.25
1300    3.29           3.28615    3.28
1400    3.31643        3.30214    3.30214
1500    3.34733        3.33533    3.33467
1600    3.37062        3.35625    3.35562
1700    3.39706        3.38176    3.38059
1800    3.44222        3.40111    3.4
1900    3.45526        3.42474    3.42316
2000    3.5005         3.4485     3.446
2100    3.53714        3.47905    3.47048
2200    3.55727        3.49909    3.49045
2300    3.69783        3.54826    3.51478
2315    3.71404        3.55378    3.51836

Speed

This algorithm takes exponential time to execute (w.r.t. the dictionary size, N). This was the computation time (in seconds):

N       5 guesses max  6 guesses  unlimited guesses
100     0.0003024      0.0002205  0.0002167
200     0.0009784      0.000619   0.0010066
300     0.0083426      0.0051604  0.0082898
400     0.0441092      0.0380435  0.0405584
500     0.242742       0.189152   0.170213
600     0.606853       0.423651   0.5729
700     1.24252        0.924092   1.12119
800     2.88165        1.81993    2.26742
900     5.5044         3.62742    5.08155
1000    15.1655        7.80538    12.3234
1100    30.8331        15.2142    25.141
1200    45.0553        24.2716    42.0681
1300    81.8651        47.7554    100.303
1400    116.092        77.563     167.329
1500    165.032        134.577    322.469
1600    243.042        199.082    469.798
1700    311.591        309.68     676.527
1800    392.633        472.891    1090.56
1900    473.287        755.729    1801.91
2000    555.693        1021.66    2452.1
2100    732.992        1353.97    3822.42
2200    1038.54        2441.62    5327.98
2300    1251.14        3000.22    7063.53

_ILLS words

Adding in just the 19 _ILLS words contorts the optimal strategy significantly. We guess twang, then if the respond is _____, fjord. If the response is _____ again, we guess lymph. Weird!

The average score drops by from 3.55378 to 3.79006.

Easy mode

todo

(For N around 1300, easy mode can be solved with ~.05 fewer guesses.)

$\endgroup$
5
$\begingroup$

Mathematically optimal solution

The optimal strategy is going to depend on how you define the problem and what you would consider optimal play.

If we assume that Wordle is modeled such that

  • The 12972 words in the Wordle source code are the only valid guesses.
  • The target word is selected uniformly at random from the 2315 word subset on initialization.

And further, we define optimal gameplay as the strategy that will, on average, result in the least number of guesses.

Then finding the optimal strategy is equivalent to finding the decision tree with the minimal average height. A wordle decision tree would be the tree structure that provides a guess for each possible feedback at each step of the game.

This problem has been solved via exhaustive search with alpha-beta pruning, where a lower bound is established at each branch via a heuristic approach and then the branch is explored exhaustively, pruning whenever the search exceeds the heuristic bound.

This approach leads to a provably optimal solution. The full details of this approach are described by Alex Selby on his webpage at http://sonorouschocolate.com/notes/index.php?title=The_best_strategies_for_Wordle.

Apparently it took a couple days of processing to exhaust the search space, though the heuristic method was able to find what turned out to be the optimal strategy within a few minutes.

Note that I did not develop this solution.

It turns out that the best starting word is SALET which requires on average 3.4212 guesses with optimal play. On hard mode the optimal starting word is also SALET which requires on average 3.5084 guesses.

The normal mode strategy always finds the target word within 5 guesses, and the hard mode strategy will always find the target word within 6 guesses.

Edit

Expanding on the details of how the top 100 words are determined as described on Alex Selby's webpage.

Alex describes it like this:

To evaluate the top 100 (say) first words, with proof that we have all of them, we can start by getting fast, and in practice very tight, upper bounds on the values of each word. We do this by restricting the min loop to the (e.g.,) 100 most promising words out of the 12972 available, arriving at this list. The score of the 100th best of these is 8014, so we can then re-evaluate all other candidate first words using a full run (allow all 12972 words at each stage, thereby ensuring exact answers) using a beta of 8015. This will distinguish all values under 8015, so it is guaranteed to fully evaluate all of the top 100 first words.

This answers the question: Even if we have an optimal strategy for a given starting word as described in the first half of this post, how do we prove it's the best among all 12972 potential starting words? The answer is that this is done by (i) establishing an upper bound using a suboptimal search, then (ii) using that bound to limit an optimal search.

i. Establishing an upper bound (suboptimal search)

First, a potentially suboptimal search is performed on all 12972 starting words. This is suboptimal because the algorithm only exhausts the 100 top candidates (based on the heuristic) at each additional guess. This establishes an upper bound for each of the 12972 starting words, i.e. we know that the optimal strategy for each word requires no more than the number of guesses reported by this search.

By sorting these results we find the strategy for the 100th word on the list required 8014 total guesses across all 2315 starting words (average of 3.4618 guesses per word). Note that this is not necessarily the best strategy for the 100th word, but we can be sure that an optimal strategy can be no worse than this.

ii. Optimal search

8015 is then used as an upper bound on an exhaustive search over all of the 12972 words. This means that a search is performed on each of the 12972 starting words, considering all the candidates at each additional guess (not just the 100 best), but the search is terminated when it becomes impossible for additional searching to produce a strategy that performs better than 8015 total guesses. Using this approach guarantees that no words are missed that have optimal strategies with less than 8015 total guesses, and furthermore provides an optimal strategy for all words that can do better than 8015 total guesses.

$\endgroup$
3
  • $\begingroup$ Link doesn't mention 'provably optimal'? $\endgroup$ Feb 4 at 14:36
  • $\begingroup$ @AndrewAllen I don't understand the comment. Are you saying it doesn't use the term 'provably optimal'? In this link Alex describes exactly how he gets the top 100 starting words, how he knows they are actually the best, and how the optimal number of guesses is computed for each starting word. $\endgroup$
    – jodag
    Feb 4 at 18:52
  • $\begingroup$ @AndrewAllen I just added some details expanding on the somewhat terse language used in the link. Hopefully this helps. $\endgroup$
    – jodag
    Feb 4 at 19:32
4
$\begingroup$

@Andrew Allen's was the best take I've read so far. I thought I'd add a little more color about my own exploration into this. It is a bit too long for a comment.

In addition to local Min-Max, one can start doing genetic algorithms. The nodes to improve in the tree are exactly those along a path of maximum depth. You can mixed in randomness as a selection criteria or do random for 1 depth and then switch back to local min-max. You can then keep the tree that [lexically] minimizes (height, # of maximum length paths, f) where f is some criteria that changes often (for f I've been using the sum of the height of each node of the tree, but I suspect the specifics don't matter). You can then try to keep mutating and keep around a pool of the best trees you have found.

After grinding for a while, the best I have seen is a tree of height 7 with 19 words with path length 7. It starts with TOEAS. I've also gotten to 22 long paths with REAIS, and 24 with CRYPT. (It is kinda amusing that if those 19 out of 13k words were removed this problem would be solved.)

After investigating some of these almost there trees, one keeps seeing the same words in the long paths over and over. A common property of the frequent offenders is that they belong to a set of words that differ up to 1 letter. For example:

_ILLS   19 [{BILLS B} {CILLS C} {DILLS D} {FILLS F} {GILLS G} {HILLS H} {JILLS J} {KILLS K} {LILLS L} {MILLS M} {NILLS N} {PILLS P} {RILLS R} {SILLS S} {TILLS T} {VILLS V} {WILLS W} {YILLS Y} {ZILLS Z}]

These are hard to tell apart. In a single guess one cannot tell more than 5 apart. That observation right there gives a lower bound of 5 guesses for a set of 19 words. But wait as vowels A, E, I, O, U will not help telling these apart, we should only really expect for 1 guess to be 5 letters if it uses Y. The other 4 guesses can only tell 4 words in this set apart at a time. (This is not quite right due to words like CRWTH.) This hand waving suggests a lower bound of depth 6. As 2^19 subsets is small enough to brute force, we can determine that these 19 words are solvable with a minimum depth of 6. So there you go a depth <= 5 wordle tree is impossible.

Other words that appear in long paths tend to come from similar large off by one letters sets. For my best TOEAS tree, these are: VILLS, ZILLS, GIVES, ZINES, VELLS, VANGS, YANGS, PACKS, VAILS, VAPED, JAKER, FAXES, WAVES, WANES, JAMES, WAKES, WARES, WALES, ZESTS. Note TOEAS is not a very optimal guess on _ILLS. No other within-1 set is as large as 19, but there are 42 sets of size >= 12 (minimum tree depth of 4).

Anyways whether a tree of height 6 is doable is still an open question. If it is doable it is right on the edge.

--- Update: 1/17/2021 ---

After brute forcing [e.g. finding the minimum height tree for all subsets of] the _ILLS set, we can start lower bounding answers. The key lemma is S subset W then min-height(S) <= min-height(W). After a guess, we partition the set of current feasible words into buckets. Let's call this b_ij for guess i and partition j. We can look at the intersection of b_ij and the _ILLS set. b_ij intersection _ILLS is a subset of _ILLS and will have been brute-forced earlier. So when min-height(b_ij intersection _ILLs)+1 > 6, this guess cannot be solved in a tree of height <= 6.

This approach prunes out 5170 first guesses. Some are kinda surprising. This is enough to rule out many [most?] of the suggested first guesses in this thread like:

KALES, TOEAS, CARLS, AROSE, AEROS, SOARE, STAIR, CLONE, SERAI, PASEO, TRASH, NOISE, CACTI, ORATE

They have a really solid intuition but [unless I have screwed something up] they are not the first guess in a depth 6 tree.

$\endgroup$
5
  • 1
    $\begingroup$ I'd be interested in your results on LAKES or KALES, which I have at 21 words over six guesses (including one at eight guesses) with my simple implementation of min-max. $\endgroup$ Jan 14 at 23:07
  • 1
    $\begingroup$ I have improved my horribly inefficient code, and will now be able to run the full list through my simple min-max algorithm. About 800 words in, and I've hit a few that directly improve on your best. RANTS (18); CARLS, STRAD (17); SCRAT, TARNS (16), several in the teens with one word at 8 guesses, but the best so far is LARKS (10+1). $\endgroup$ Jan 15 at 23:18
  • $\begingroup$ Very cool progress. At some point someone is going to need to publish a format for communicating such trees. FWIW my efforts are currently focused on it cannot be done due to lower bounds imposed mostly by the 42 hard to solve off-by-one sets + vagaries to the Collins dictionary. My only hypothesis that might be of value to others is that (Guess, Response) sequences commute. This observation may be helpful for brute-forcing 2-3 guesses. Maybe I'll learn something? Best of luck trying to find a tree! I mostly just want to know the answer at this point. $\endgroup$
    – Tim
    Jan 16 at 5:28
  • $\begingroup$ If folks are interested in this sort of stuff, I can maybe post the set of "cannot be the first guess after 1 look ahead" somewhere (only about 42k). Just need a suggestion for a reasonable place. (The trees for brute forcing _ILLS and similar is also possible but the json is about 1.6G.) $\endgroup$
    – Tim
    Jan 18 at 5:31
  • $\begingroup$ Even thought this is 'too long for a comment' it should work as a standalone answer. $\endgroup$ Jan 30 at 16:14
3
$\begingroup$

The following strategy is far from optimal, but it's still winning for cheat mode (i.e., always finishing in up to 6 guesses - the average number is 5.03 guesses) and designed to be explicitly described and possible to memorize for a human player with a certain skill level (including a good feel for what kinds of words are included in the answers list, and ability to find examples of those that match the clues)

--

  1. Play out these words in any order: BURST CLAMP FINED

  2. If one of the following sets of words matches all the information available so far:

    • ARMOR, MAJOR, MAYOR -> play the middle one
    • BOBBY, BOOBY, BOOZY -> play the middle one
    • ENJOY, ENVOY, OZONE -> play the middle one
    • REBAR, REHAB, ZEBRA -> play the middle one
    • SHOWN, SNOWY, SWOON -> play the middle one
    • PIPER, RIPER, VIPER -> play RIVER
    • GAUNT, HAUNT, JAUNT, TAUNT, VAUNT -> play THUJA

    The hint thus chosen will resolve the answer within the set uniquely, or in the case of the last set, leave behind at most two members of the set, while you still have two full guesses to go, playing out those remaining words.

    It's enough to remember and test the middle word of each set, except for the last two sets where it's necessary to either remember the entire set, or just one representative and then also a way to resolve it safely.

  3. If outside of those special sets after your first three guesses, play GOWKS as your fourth guess.

  4. After GOWKS, there are at most two words compatible with the hints left; with a 95% probability just one candidate answer.

    However, that's up to two words from Wordle's dictionary of 2,315 possible answers. There could be more matching hints from Wordle's dictionary of almost 13,000 allowed hints. And you have only two guesses left. So only words well known to every native speaker of English that are in their dictionary form ("quality words") should be seriously considered at this stage of the game.

    Find a quality word matching the available information. Consider letters already identified as present, the remaining letters (HJQVXYZ), and repeated letters. Be careful especially about eliminated letters.

    Play the quality word as your fifth guess.

  5. If this didn't match the answer, find also the other quality word if there was one after all - and play it as your sixth guess.

--

I'm sharing this solution as a rarity because the non-adaptive approach is otherwise almost doomed. Nearly any fixed set of the first four guesses loses the game in the sense that the remaining two guesses may not be sufficient to resolve every resulting situation. But BURST CLAMP FINED GOWKS is one of those few that do not lose the game - not even if step 2 of this strategy is left till after GOWKS is played out unconditionally.

Every fixed set of the first three guesses leaves behind at least one set of 6 indistinguishable candidate answers with only three guesses remaining; and of course too many sets of four or five candidate answers each to recognize them all. BURST CLAMP FINED is one of some 550 triples that are optimal in covering 15 unique letters of the alphabet and leaving behind just one set of six indistinguishable candidate answers. For most other such triples, there's no safe fixed fourth guess as a follow up.

There is no fixed set of the first five guesses that would always determine the answer uniquely, for the only guess left.

The presented strategy thus becomes adaptive late during the game and with a more or less the smallest number of words that require special treatment (the 22 words given). Surprisingly to me, it does not matter whether the special treatment is applied after a fixed opening of three words or four words (with this particular opening).

$\endgroup$
2
$\begingroup$

My current thinking...

  1. Each letter of each guess should do the most to reduce the space of possibilities. Letters that occur with high probability reduce the space the most whether they occur or not.

Under this logic, since any letter, even E, occurs with probability considerably less than 50%, you would always be better off using more frequent letters. According to the ancients (i.e. Samuel Morse) the descending order of letters in English were ETAOINSHRDLU. Therefore one might try TRASH and NOISE (in either order) and proceed from there.

Another way to phrase this is that each wrong letter guessed would do the most to narrow down future possibilities.

  1. It is also true that guessing a low-frequency letter gives you a massive amount of information. A letter that occurs with probability p gives you -p*log2(p) bits of information. For example, if you knew the word had an X, the possibilities would be reduced considerably.

The downside risk is that you might learn nothing. (Also, low-frequency letters are consonants with a lot of “vowel load.”)

  1. Combining these ideas, the expected bit content of each guess is approximately -p^2 * log2(p), since the probability of a hit in the first place is p. This number is still maximized for frequent letters, so point #1 would still seem to hold.

However, the second strategy would more likely succeed once you have a few letters in hand. This could be calculated but that’s overkill.

  1. In all of the above, be prepared to make use of both misses and hits.

The above strategy, implemented, gave a result today that looks like this:https://mobile.twitter.com/SamWangPhD/status/1479053713507594241

In this example, I got three single-letter hits, all In the wrong place. Then I got a complete five-letter miss. This was enough information to get the word.

Note that all of the above neglects repeated letters, e.g. CANAL. But such combinations are less frequent, so I think the logic still mostly holds.

I feel like something in my logic could be wrong, so don’t hold me to it. Or try some NOISE TRASH and see!

$\endgroup$
3
  • 3
    $\begingroup$ The letter frequency of English as a whole is different to the letter frequency of a word list due to word frequencies. In particular, "the" is such a common word that the letter H is overrepresented. As pingswept's answer shows, D, U, Y are more common than H in Wordle's word list. $\endgroup$ Jan 6 at 12:37
  • $\begingroup$ Thanks, though your point is basically a detail. Yes, one can get a frequency count from a dictionary lexicon. The subject of letter frequencies for puzzlers is an old topic: www3.nd.edu/~busiforc/handouts/cryptography/… $\endgroup$
    – Sam Wang
    Jan 6 at 13:06
  • 1
    $\begingroup$ Welcome to Puzzling! It looks like your markdown towards the end of the question isn't displaying correctly, the >>> is interpreted as a triple-quoted empty line, which (I assume) wasn't what you intended. Can you correct it at your earliest convenience? $\endgroup$ Jan 7 at 15:35
2
$\begingroup$

There are various different versions of what it means to be optimal, but here are a variety of optimal solutions. (Written up in more detail here.)

There are always 12972 words allowed for guessing but for the purposes of defining our objective, the list of words that may be selected as the hidden word can be taken to be 2315 long (original Wordle hidden word list), 2309 long (current hidden word list as of March 2022), or the full 12972 list for those who regard it as gaining an unfair advantage to only consider the reduced hidden list.

The number of guesses required, using an algorithm that minimises the worst case number of guesses is as follows:

  • 5 using 2309 or 2315 hidden words, in easy or hard mode. Example first guess: PALET.
  • 6 using 12972 hidden words in easy mode. Example first guess: LANTS. (There are a little over 2100 starting words that work within six guesses.)
  • 7 using 12972 hidden words in hard mode. Example first guess: THUMP. (There are exactly seven starting words that work within seven guesses.)

These are all proved optimal: no algorithm can solve it in fewer than the number of guesses stated above. See below for strategy files (decision trees).

We can also say quite a lot about the algorithm that minimises the average number of guesses over all possible hidden words.

Mode #hidden max #guesses Tot #guesses Average #guesses Starting word with link to strategy file
Easy 2309 5,6 7897 3.4201 SALET
Hard 2309 5 8181 3.5431 PALET
Hard 2309 6 8099 3.5076 SALET
Easy 2315 5,6 7920 3.4212 SALET
Hard 2315 5 8206 3.5447 PALET
Hard 2315 6 8122 3.5084 SALET
Easy 12972 6 52896 4.07771 LANTS
Hard 12972 7 58715 4.52629 THUMP

Note that (Average #guesses) = (Tot #guesses)/(#hidden)

In all cases, the total (or average) number of guesses stated is proved to be optimal for the given starting word and given maximum number of guesses, and in all cases apart from LANTS, the starting word is proved to be the best starting word. In the case of LANTS, it looks very likely that LANTS is best, judging from heuristically restricted searches, but this has not been proved with an exhaustive search.

(By comparison, LARNT, as mentioned in another reply, requires 53109 total guesses, an average of 4.09413.)

$\endgroup$
0
$\begingroup$

I made a video showing my process here: https://www.youtube.com/watch?v=hJJaYvxQh8w

You can also play around with the tool I made here: https://sadmoody.github.io/unwordle

It's made with the assumption of "Hard Mode" and is a pretty simple algorithm. I saw you commenting that you don't want knowledge of the potential answers (i.e. you're looking for a "general wordle") - which has a couple of problems:

  • The Wordle "solution" list is artificially selected and doesn't reflect how 5 letter words behave in general. Many plurals that end in "s" are omitted. So if you made a strategy which targeted English words, it would be suboptimal for Wordle.
  • If there are even odds of any combination of 5 letters appearing, then it stops really being a word game and turns into just "Mastermind" with more colours. One of the restrictions on Wordle is that it needs to conform to English words - you can't even make guesses if they aren't "valid" words.

Either way, the strategy here doesn't change. You would still be making a "first guess" based on the frequency of the letters in your potential solutions and where they appear. Your algorithm's logic won't change with a different word-set, but its suggestions will.

@pingswept in their reply, mentioned that picking a "possible solution" vs a "valid guess" that better satisfies the probabilities is suboptimal, but I found the opposite to be the case. You only have 6 guesses, so you need to trade-off "guessing" vs "finding better information". I found that the algorithm which guessed the words with the "best" frequency from the possible remaining solutions to be the best since every entry is also a guess - you are utilising all 6 guesses.

Once you let go of hard mode, however, all bets are off. I think it would be possible to create a 5 "guess" lookup to whittle down answers to only one. But if you're trying to optimise for "best average" performance, then you're going to have to be guessing actual potential solutions as often as possible.

$\endgroup$
2
  • 3
    $\begingroup$ Could you please summarize within your answer how the tool works? We prefer for all answers to be as self-contained as possible - links rot, or might be blocked by firewalls, etc. thus while they can be useful supplements, the core of answers should be contained within the actual answer text to the most degree possible. $\endgroup$
    – bobble
    Jan 10 at 4:21
  • $\begingroup$ This doesn't answer the question, just gives a link out to a video. It would be much better if it was self contained $\endgroup$ Jan 30 at 15:56
0
$\begingroup$

Choosing the most common letters appears to be a strong strategy, but letter position also matters.

Using a brute force search (all legal starting words × all possible solution words) and scoring by the number of solution words remaining on average, the ten best starting words all contain the most common nine characters (EAROTLISN). However, there are several words that score better than ORATE despite it containing the most common five letters.

Starting Word Average Solutions Remaining
ROATE 60.4
RAISE 61.0
RAILE 61.3
SOARE 62.3
ARISE 63.7
IRATE 63.8
ORATE 63.9
ARIEL 65.3
AROSE 66.0
RAINE 67.1

Conversely, the worst starting words (without repeated letters) all use at least one of the nine least common letters (JQXZVWKFB), but JUMPY and JUDGY perform worse than several words that contain two of these:

Starting Word Average Solutions Remaining
JUMBY 642.7
JUMPY 599.4
JUDGY 590.6
JUNKY 531.3
VOZHD 529.7
JUMBO 527.6
JUMPS 521.0
MUJIK 512.6
BUXOM 500.2
BUNJY 498.4
$\endgroup$
2
  • 1
    $\begingroup$ Choosing the most common letters is a strong strategy, but choosing only the most common letters is not optimal if you want to identify every word within six guesses. Words like CRATE, PLATE, SCALE and CLASP have proven to be better in that regard. $\endgroup$ Jan 17 at 22:54
  • $\begingroup$ You certainly need to choose other letters in subsequent guesses, and here it matters if you're in "hard mode" or not (or your philosophy on choosing words you know are wrong). Starting with ROATE will give you the smallest set of possible solutions on average. If you want to blindly choose two starting starting words, CARSE DOILT is the best I've found through brute force so far, yielding 4.3 remaining solution words on average. $\endgroup$
    – Rod L
    Jan 18 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.