I wrote a solver a few weeks ago that solves easy mode in 3.45 guesses and hard mode in 3.55 guesses. Rather than using heuristics, it explored a large portion of the game tree (with a little pruning) and I'm hopeful that it's optimal. Interestingly, the EV-optimal hard mode strategy takes 3.52 guesses on average, but requires 7 guesses a tiny fraction of the time, so I instead exposed the best strategy that always requires 6 or fewer guesses.
As a point of curiosity, what do you mean by optimal?
To me, I can see at least two (potentially different) cost functions that a Wordle strategy can aim to minimise. Firstly, you can try to minimise the expected number of guesses, and secondly you can try to minimise the expected number of guesses conditional on never losing the game. In principle you could optimise for the first but not the second by allowing a small list of hard words to take > 6 guesses on average.
Part of my point is the lack of an absolute definition of optimal: strategies are only optimal up to the specified coat function.
IMO, never losing the game is the bare minimum for any reasonable cost function: never take > 6 guesses. Beyond that, you can have different optimization functions based on whether you're trying to minimize the worst-case depth of the decision tree (number of guesses) for each position, or the average depth, or some other reasonable function of the distribution over number of guesses.
Although you could have arbitrarily many cost functions, a fairly general class is the following: pick some nonnegative constants (w1, w2, w3, w4, w5, w6, w7), and for a certain strategy, define the cost as:
where nk (for 1≤k≤6) is the number of hidden (solution) words for which the strategy takes n guesses, and n7 is the number of words for which the strategy loses the game. Then,
• Setting w7 infinite / very high is a way of encoding the condition that you not lose the game. (You can set it finite/small if you don't mind occasionally losing the game for some reason!)
• Setting w1 = 1, w2 = 2, …, w6 = 6 will simply minimize the average number of guesses,
• Having them grow exponentially, e.g. setting wk = c^(k-1), where c is some constant larger than 12972 (the number of acceptable guess words) will make sure that the minimal-cost strategy first minimizes the maximum number of guesses, then break ties by having the fewest words take that many guesses, and so on.
They specified that in the post, they were able to constrain to a strategy that guarantees 6 or fewer and then optimize for EV to get 3.55, but could get down to 3.52 by allowing some small number of words to take more than 6.
I would be interested to know if 6 is the lowest you can constrain it. Can you guarantee a solution in 5, and if so what is the best EV with that constraint?
Funnily enough, I think neither of those notions are the correct thing to optimize. For me, you want to minimize the maximum number of guesses. This leads to an equilibrium. Otherwise, your opponent can just abuse your strategy.
If two players are competing in a single round of wordle, then surely the player who guesses the correct word in the fewer number of guesses wins, right? Then it seems natural to say that the better of two players is the one with the most wins after playing all possible rounds.
The only problem is that I think this definition leads to the possibility of non-transitivity, where A beats B, B beats C, and C beats A.
I've seen a number of solvers; but my partner has forbidden me from writing one, forcing me to do everything in wetware. 3-4 guesses seems right intuitively. I saw some speculation that the dictionary was well-known, is that true?
Seems to me that the problem as-stated allows the guesser to discover a nonword "for free", but otherwise expects the dictionary to be "all five letter words" which is much larger than the real solution space. Though, maybe in practice that doesn't change the solvability by much.
The wordlist is more than well-known, the word for each day is predetermined. The entire game runs in the browser and the selected word is based on the date. Here’s a quick script based on any date you select: https://codepen.io/kevlened/full/NWaOmPw
This program actually inadvertently created a quite philosophical discussion amongst my friends! Some of them contended that writing a program to solve wordle sucked the joy out of the process of solving it, even if I solved the puzzle myself, first.
Oh dang! I was guessing that the optimal approach would be under 3.5 for easy mode, but was expecting it to be closer to 3! Amazing work. My next go at the problem is in Rust, which I am a total newcomer to. Thanks for sharing!
Nice! I was wondering almost the same thing this morning while my wife was playing Wordle - ended up coding an assistant to help you choose the optimum words.
If you just brute force solve with greedy search (always pick the word that results in the highest average reduction in remaining possible words), you get a solution with an average of 3.47. Even only guessing words on the primary word list (which Wordle uses to pick the word of the day) you can get 3.51. That's as far as I've chased the problem.
I'm surprised to hear that optimal play only gets you 3.4212 (according to the link you posted).
The graph of every possible game for Hard mode should be pretty tractable. Sounds like you wrote almost exactly what I started but have been too lazy to finish.
> but requires 7 guesses a tiny fraction of the time, so I instead exposed the best strategy that always requires 6 or fewer guesses.
That's awesome. My question is "what is the minimum number of guesses to solve every word while guaranteeing it never loses". For hard mode I'm pretty sure this can be provably brute forced. Easy mode requires enough pruning I'm not sure it can be proved.
This [1] solves it in 3.4212 average guesses 100% of the time and claims optimality, which is 99% of the difficulty it seems. For the limited 2671-word set of possible words, I think the question is now settled (for the whole 12k-word set, I don't think anyone tried anything).
Neat, didn't know that existed! Definitely would have saved me some time :)
FWIW, I wrote a similar solution a couple of days ago as well, and come up with the same result (3.421166 guesses on average, with starting word SALET). So that would support that result.
It's a bit disappointing that there's been many writeups of heuristic-based solvers make the front page, but the writeup of an exact solver doesn't make it. [Note: I was the person who submitted the link to the exact solver writeup to HN].
> From an information-theoretic perspective, the optimal initial guess is the one which is maximally informative about the target, given the resulting pattern.
This statement (which motivates the rest of the analysis) isn't correct, because it doesn't take into account the highly irregular search space of what you're actually allowed to guess. Sets of possible words can vary a lot in terms of how easily they can be further cut down: for example, if you're on hard mode and your set of possible words is [BILLY, DILLY, FILLY, HILLY, SILLY, WILLY], then you might be in trouble.
I wrote a very simple O(N^3) algorithm to determine that: for each possible actual word and the guessed word, figure out whether or not a word is eliminated. Then calculate a score based on how many words can be eliminated from a particular guessed word, averaged over all possible actual words.
(I originally thought O(N^3) would be way too slow to be useful. But it runs fast enough with a few thousand words.)
Like a sibling comment, I also found that the best initial guess is RAISE, although when I tried a different word list, I got different words like LARES (I don't think it's in the Wordle list).
One thing that surprises me is that by the time you get to the mid-game stage (after 2 guesses or so), occasionally it can be more optimal to guess a word with repeated letters; I did not originally expect that because I thought repeated letters are wasted opportunity to test more letters, but it turns out Wordle's handling of repeated letters can give you helpful information about the number of occurrences of a letter. (For example if you picked a word with 2 a's, the first one can be green the second one can be black, essentially telling you there is exactly one letter "a" in the word.)
FWIW, your O(N^3) algorithm can be equivalently implemented in O(N^2) by using the following observation: a word is not eliminated by a guess if and only if the result of testing the word against the solution is the same as the result of testing the guess against the solution. Using this, you can implement the algorithm like so: for a given solution, partition all of the guesses based on the result of testing them against that solution. This partitioning takes O(N). Then, the set of words that will be left over from a guess is equal to all the words in the same partition as the guess. This makes it easy to calculate "how many words can be eliminated from a particular guessed word".
I'm making this comment because I started with the same O(N^3) approach and then realized this. :)
I also implemented essentially this algorithm. For guesses I always consider the full list of possible words, not just the list of possible answers. Doing so requires a check so words that have been excluded are only used if they're better than words that haven't been.
Using essentially this method I get that the best initial guess is RAISE (there are some others that are very close). It seems the author of this post didn’t use the actual word list from the game so got a different word.
I have also hacked around on solving this problem. However, I decided that using the shorter list of answers was cheating, since end users wouldn't have access to this list. From a user's perspective, any word that Wordle lets you guess could be a valid solution.
It's still a work in progress, but my code died when I tried to generate a complete game tree for the full list.
However, in theory it could be done once, to determine the best starting word, and then hardcoded to always use the same start word. So, my plan to explore a game tree approach from guess 2.
No slight to anyone pursuing this strategy, but I also felt like using the shorter list for ranking candidate words was cheating. On the other hand, my solver ends up making silly suggestions that might be appropriate for early on in the game, but not for late guesses.
I've tried to think of what might be a good way of approximating a human's own sense of which words are viable Wordle answers. One thing I attempted was using a word frequency table to help bias the algorithm away from less common words. The funny thing is that some words rank low in word frequency but are otherwise count as "common knowledge". For example, "tapir" was a Wordle solution a few weeks ago, but it ranked lower than some obvious non-answers like "grovy". It could be that the frequency table I was using was weird, but I can believe that there are well-known words that aren't used that often. Maybe I could come up with a better corpus (e.g. only use the NYT or some other newspaper) to use as the basis for a custom frequency table. Seems like a lot of work!
If you right off the bat guess "bound" and then positions 2, 3, 4, and 5 all come up green, then your goal needs to then be to use words like 'morse' to rule out (in one fell swoop) words like 'sound', 'mound' and 'round'. Then, if it's not ruled out, you can then choose words that just have m and s, or s and r.
Why not simply choose a guess which narrows the set of possible solutions the most?
This could be improved by looking one step further, but this would probably require some kind of optimization / heuristic / approximation to make it computationally feasible.
It really depends on what you are trying to optimize. Least guesses on average may not want a 50/50 split it might want say a 60/40 split where the 60% is 2 guesses and the 40% is 3. But that loses to a 48:52 split which gives 2 guess 80% of the time etc.
Narrowing the search space greedily doesn't solve the problem optimally, because the size of the search space is just a heuristic. Some search spaces of size X might be more difficult to reduce further than another search space of size Y (for Y < X). This is more apparent in hard mode where you have a very limited guess-pool. The greedy heuristic approach would work fine if all possible 5-letter combinations were valid answers.
If you want to get really fancy, a full minimax solution is probably feasible without massive resources. Pretend it’s a two player game with one player guessing and the other player thinking of a potentially different word for each guess subject to the constraint of being consistent with all previous answers.
Somebody had already tweeted about solving it and finding that 3 guesses suffice, using alpha beta search (though he didn’t use the term “alpha beta” because he might have reinvented it).
> Why optimize for greens? Better to rule out more first no matter the position.
I haven't yet experimentally tested this, but I hope to soon! It may be that a green letter in position rules out more possible targets than a grey letter.
The generally optimal thing is to choose guesses to reduce the set of possible targets as much as possible. This is the same as choosing guesses with maximal entropy over the resulting patterns (that is, the result you get back from the game should be maximally informative). Because greens are rare, by maximizing the probability of greens, you are approximately maximizing the entropy of patterns, by distributing probability mass among rare patterns. This is why going for greens is a good heuristic.
This sounds like the optimal strategy for a single guess. But shouldn't the optimal strategy for solving the game include that there are multiple guesses? While some specific word might provide the highest reduce in entropy for the first guess, it might actually negatively impact the entropy reduction of remaining possible words compared to another first guess.
E.g. if RAISE is the optimal reduction in search space for the given word list, what's the best 2nd guess for every possible word? Now taking the average 2nd guesses into account, is there a better first guess?
Readit News
If you're interested, you can play with it here: http://www.npinsker.me/puzzles/wordle/ and the source (written in neophyte's Rust) is here: https://gist.github.com/npinsker/a495784b9c6eacfe481d8e38963...
(edit: It's posted elsewhere in the thread, but this is actually not optimal and someone else achieved better results! http://sonorouschocolate.com/notes/index.php?title=The_best_...)
To me, I can see at least two (potentially different) cost functions that a Wordle strategy can aim to minimise. Firstly, you can try to minimise the expected number of guesses, and secondly you can try to minimise the expected number of guesses conditional on never losing the game. In principle you could optimise for the first but not the second by allowing a small list of hard words to take > 6 guesses on average.
Part of my point is the lack of an absolute definition of optimal: strategies are only optimal up to the specified coat function.
Although you could have arbitrarily many cost functions, a fairly general class is the following: pick some nonnegative constants (w1, w2, w3, w4, w5, w6, w7), and for a certain strategy, define the cost as:
where nk (for 1≤k≤6) is the number of hidden (solution) words for which the strategy takes n guesses, and n7 is the number of words for which the strategy loses the game. Then,• Setting w7 infinite / very high is a way of encoding the condition that you not lose the game. (You can set it finite/small if you don't mind occasionally losing the game for some reason!)
• Setting w1 = 1, w2 = 2, …, w6 = 6 will simply minimize the average number of guesses,
• Having them grow exponentially, e.g. setting wk = c^(k-1), where c is some constant larger than 12972 (the number of acceptable guess words) will make sure that the minimal-cost strategy first minimizes the maximum number of guesses, then break ties by having the fewest words take that many guesses, and so on.
I would be interested to know if 6 is the lowest you can constrain it. Can you guarantee a solution in 5, and if so what is the best EV with that constraint?
The only problem is that I think this definition leads to the possibility of non-transitivity, where A beats B, B beats C, and C beats A.
Seems to me that the problem as-stated allows the guesser to discover a nonword "for free", but otherwise expects the dictionary to be "all five letter words" which is much larger than the real solution space. Though, maybe in practice that doesn't change the solvability by much.
If anyone wants to check it out, I published it here https://curiosity.ai/wordle/ - source code is also available here https://github.com/theolivenbaum/wordle-assist.
I'm surprised to hear that optimal play only gets you 3.4212 (according to the link you posted).
The graph of every possible game for Hard mode should be pretty tractable. Sounds like you wrote almost exactly what I started but have been too lazy to finish.
> but requires 7 guesses a tiny fraction of the time, so I instead exposed the best strategy that always requires 6 or fewer guesses.
That's awesome. My question is "what is the minimum number of guesses to solve every word while guaranteeing it never loses". For hard mode I'm pretty sure this can be provably brute forced. Easy mode requires enough pruning I'm not sure it can be proved.
Deleted Comment
SOARE JUMBY BOOST (at this point, it claimed to have won!)
Deleted Comment
It was posted here four days ago [2].
[1] http://sonorouschocolate.com/notes/index.php?title=The_best_...
[2] https://news.ycombinator.com/item?id=30006724
FWIW, I wrote a similar solution a couple of days ago as well, and come up with the same result (3.421166 guesses on average, with starting word SALET). So that would support that result.
With the following strategy: https://drive.google.com/file/d/1WvxRRzbvDVnHZUczHBZAko3hKft..., code: https://drive.google.com/drive/folders/1Y8k685PS0wxvYulIxsPg...
https://news.ycombinator.com/item?id=30006724
- 99.4% in 6 guesses or less
- 3.64 guesses average
- no attempt of any formal optimality result,
while the one you posted has:
- not just 100% in 6 guesses or less (so 100% wins not 99.4%), but actually 100% in 5 guesses or less!!!
- 3.42 guesses average
- a fairly convincing optimality proof (as far as average is concerned) which was apparently the only hard part computationally.
- it also had 3 upvotes until i cross-references it here, and barely more now.
- the author seems to have plenty of twitter followers, none of which seemed to care much.
And yet if you look at the "new" page, the flow of heuristics keeps coming. Conclude what you will :-).
[1] https://www.poirrier.ca/notes/wordle/
This statement (which motivates the rest of the analysis) isn't correct, because it doesn't take into account the highly irregular search space of what you're actually allowed to guess. Sets of possible words can vary a lot in terms of how easily they can be further cut down: for example, if you're on hard mode and your set of possible words is [BILLY, DILLY, FILLY, HILLY, SILLY, WILLY], then you might be in trouble.
I wrote a very simple O(N^3) algorithm to determine that: for each possible actual word and the guessed word, figure out whether or not a word is eliminated. Then calculate a score based on how many words can be eliminated from a particular guessed word, averaged over all possible actual words.
(I originally thought O(N^3) would be way too slow to be useful. But it runs fast enough with a few thousand words.)
Like a sibling comment, I also found that the best initial guess is RAISE, although when I tried a different word list, I got different words like LARES (I don't think it's in the Wordle list).
One thing that surprises me is that by the time you get to the mid-game stage (after 2 guesses or so), occasionally it can be more optimal to guess a word with repeated letters; I did not originally expect that because I thought repeated letters are wasted opportunity to test more letters, but it turns out Wordle's handling of repeated letters can give you helpful information about the number of occurrences of a letter. (For example if you picked a word with 2 a's, the first one can be green the second one can be black, essentially telling you there is exactly one letter "a" in the word.)
I'm making this comment because I started with the same O(N^3) approach and then realized this. :)
But yeah, given the frequency of letters, in position, in the target list, the answer is SLATE.
It's still a work in progress, but my code died when I tried to generate a complete game tree for the full list.
However, in theory it could be done once, to determine the best starting word, and then hardcoded to always use the same start word. So, my plan to explore a game tree approach from guess 2.
I've tried to think of what might be a good way of approximating a human's own sense of which words are viable Wordle answers. One thing I attempted was using a word frequency table to help bias the algorithm away from less common words. The funny thing is that some words rank low in word frequency but are otherwise count as "common knowledge". For example, "tapir" was a Wordle solution a few weeks ago, but it ranked lower than some obvious non-answers like "grovy". It could be that the frequency table I was using was weird, but I can believe that there are well-known words that aren't used that often. Maybe I could come up with a better corpus (e.g. only use the NYT or some other newspaper) to use as the basis for a custom frequency table. Seems like a lot of work!
[0]: https://en.wikipedia.org/wiki/Mastermind_(board_game) [1]: https://en.wikipedia.org/wiki/Mastermind_(board_game)#Best_s...
This could be improved by looking one step further, but this would probably require some kind of optimization / heuristic / approximation to make it computationally feasible.
If you want to go fancy somehow calculate with bigramms. If you guess c you don't have to guess k blindly too, etc.
Unfortunately, I can’t seem to dig up the tweet.
[0] https://qntm.org/files/wordle/
I haven't yet experimentally tested this, but I hope to soon! It may be that a green letter in position rules out more possible targets than a grey letter.
But manually I'm no where close to 3.6 either :). Also often too lazy.
E.g. if RAISE is the optimal reduction in search space for the given word list, what's the best 2nd guess for every possible word? Now taking the average 2nd guesses into account, is there a better first guess?