Solving Wordle in 3.64 guesses on average, 99.4% of the time
lockwood.dev
lockwood.dev
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.
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?
Perhaps unsurprisingly, you can't guarantee at most 4 words.
Another possible question is: What is the best strategy minimizing (at any point) _first_ the maximum number of tries, and second the EV (average number of tries over all possible words)? That's subtly different from either answer.
If you don't care about optimizing the EV at all, the greedy tree already has the property you're interested in.
The entity choosing the word in a game like Wordle or Hang Man is more like the dungeon master in a game of D&D than an opponent in the traditional sense? They are there to help you have fun.
I don't think a maximum-number-of-guesses optimizer leads to an equilibrium (if you mean Nash equilibrium), assuming you're playing the game where the score of the game for the setter is the number of guesses. In particular, if the solver's strategy is deterministic, the setter will always pick one of the words that needs 5 guesses. There's no reason to think the nash equilibrium can be easily found.
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:
w1*n1 + w2*n2 + w3*n3 + w4*n4 + w5*n5 + w6*n6 + w7*n7
• 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 wouldn’t think so. If I get 99.9% of rounds correct with 3 guesses (and fail to find a solution to 0.1% of the rounds), and you get 100% of rounds with 6 guesses, I’d say I’ve soundly defeated you 99.9% of the time.
Except it wouldn't be 99.9% of the time. Just the games were you guessed fewer than GP.
GP's solver would expect to guess the correct word 100% of the time in fewer than 6 guess, but not that it would always take 6 guesses.
SLATE, CRONY, HOUND, BOUND, POUND, MOUND (correct: WOUND)
SLATE, SHARE, SHAME, SHAPE, SHAKE, SHADE (correct: SHAVE)
...so sometimes even if it gets 4 of 5 letters right on the second try, it still has too many options left. Of course in cases like this it could go "one step back" and try a word with (most of) the letters that are different between these words (HBPMW or MPKDV). So try different words until the number of options is narrowed down sufficiently.
I suspect that with most languages it’s impossible to achieve 100% win rate for five or more letters. So w7 should be by far the largest weight but I don’t think it can be infinite.
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.
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.
SOARE JUMBY BOOST (at this point, it claimed to have won!)
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.
In fact, simply the act of creating an infallible solver (100% likelihood of 6 guesses or less) demonstrates the futility of competing with their soft, fleshy skills.
I do think any solver that uses the solution-set is "cheating", but I suspect it makes little difference in the total solution (like... 2-3 bits of additional information needed, just a fraction of a round).
You could either compete on number of guesses. Or you could fix the hardware (eg a Famicom), and compete on runtime?
Literally half the teachers thought it was cheating and I should be punished, whilst the other half thought (because I hadn't abused it to win prizes) that it showed a creative use of more modern skills to make up for my renowned weak mental-math.
I saw the joy in writing the solver as much more interesting than the math. Same way I can't focus on sudoku given I always try to "solve" solving it.
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.
I'm surprised to hear that optimal play only gets you 3.4212 (according to the link you posted).
It was posted here four days ago [2].
[1] http://sonorouschocolate.com/notes/index.php?title=The_best_...
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...
- 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 :-).
But yeah, given the frequency of letters, in position, in the target list, the answer is SLATE.
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. :)
That's not true. Suppose the actual word is "abcdx" but the guessed word is "xefgh". The result of testing is Yellow-Black-Black-Black-Black.
Now suppose you have other words like "xijkl" that will test against the solution in exactly the same way (Yellow-Black-Black-Black-Black), but you know won't be the correct solution because in the first round the misplaced "x" already tells you "x" should be present at a different position.
So now we have a word that can be eliminated even if it tests against the solution in the way the guessed word does.
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.
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.
apart from "h" and "i" it's the same letters (and I do have c and y in my optional 3rd).
Unfortunately, I can’t seem to dig up the tweet.
I believe you are saying that the best adversary would attempt to maximize the depth of the tree. For example a branch with "{L, B, C, R, ..}ake" requires more guesses than a balanced tree despite the fact that the two trees may have the same number of nodes.
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?
> shave: [slate: 20202, share: 22202, shame: 22202, shape: 22202, shake: 22202, shade: 22202]
I guess it needs to find the right choice of [r, m, p, k, d, v] to get "shave" (since 'v' is so rare it takes 6 guesses!). Trying "marks" and "paved" would narrow that list down in 2 guesses (and a third to actually try "shave")
Anyone code this up yet? (I haven't, I took a greedy approach too [0]). Wonder how to generalize such a plan.
I have a feeling that a perfect algorithm should be able to solve all wordles in 4 guesses. (but I might be wrong)
The problem with a lot of approaches is they seem to locally optimise for each guess rather than optimise over all the guesses (if that makes sense?)
I get the feeling guessing the most frequent letters might not be the best approach, because does it cut down the number of possible words much?
My intuition tells me if you have the right first 3 guesses you should be able to cut the dataset down to 1 possible answer every time.
However I don't know how to program it.
On NPR ( https://www.npr.org/2022/01/23/1075168693/youve-heard-of-wor... )
> QNTM: So with Wordle, in theory, you can win in one guess. I've won in two guesses a couple of times. Absurdle - you cannot beat it in less than four guesses. Four is the limit. But generally just good luck - you're going to need it.
The worst case for Wordle and evil world or Absurdle should be the same... its just that evil and absurd are always the worst case.
My excel sheet is explained in this different hn thread about same game https://news.ycombinator.com/item?id=30037065
The whole word list is available in the javascript code of the game page. I know all of that can can be accessed by javascript runtime, but the javascript wordle uses is not the one I can understand, could somebody please have a look at wordle page source & let me know how can I access the variables defined in his code in js file https://www.powerlanguage.co.uk/wordle/main.e65ce0a5.js in variable named La
My some of the basic js apps I have made for myself are hosted on gitlab at username davchana
In manual mode I try to use first word with 3 vowels & no repeat letters. Hard mode is good for not letting the tryies go waste.
Thanks
For your problem though, I just copy pasted the entire list into a new file to use. If you want to use my file, its in my repo in the article under the path ./lib/words.py!
You are a real programmer!!!
The file; I was wondering how can I access the list in my javascript bookmarklet, which I can run on his game page. I mean i can define the whole list in my own variable in my bookmarklet, but sure it is going to be over the character limit of a bookmarklet.
How, when the game page is loaded, one can access that variable in console log? I tried simply typing La, but looks like it was not declared on global scope, it is a part of some object.
I am thinking of using a .js file in my bookmarklet, to bypass the char limit; or adding a script link in dom; but those will be redundant data; the original var is there in runtime.
What I did was simply sort the word_list based on frequency analysis. The guess is always the first word in the list (with the highest score) After each guess, I update the list based on the results (gray, yellow, green)
For the final test, I just looped through each word in the list and played the game for that word. My algorithm got every single word (2315 words) in 7614 total guesses giving an average guess of 3.298
Right now, I am only using the list of final_words. I believe that I can get better results by using the list of attempt_words to reduce the number of possibilities, and then using final_words to give final guesses. So maybe the first 2 guesses will be using the attempt_words and then the guesses after that will be from final_words. Or maybe keep guessing from attempt_words until the list length is below a certain number and then start guessing from final_words. Something along these lines will give better results.
In my freq analysis, I also accounted for the freq on each index.
Most people are taking this as a fun algorithmic exercise, assuming imperfect knowledge.
Also, since there's only one word a day, I think we can assume that it's chosen manually, and it won't be some archaic anglo-saxon tool for shoeing horses or something, it will be a relatively common word.
The rebus concept is actually a precursor to actual writing, historically speaking. Both in Mesopotamia/Egypt and in the Chinese civilisation, writing developed through a rebus phase. So it's a very natural thing, that's why it's so child friendly.
Unlike say an obscure linguistic term like nisba.
See the NY Times article: http://web.archive.org/web/20220106042510/https://www.nytime...
https://twitter.com/jaffathecake/status/1483057877875101697?...
Is anybody hiring people to fix situations like this at work? i.e. this script that was written in a hurry needs to be revised to be 10^3 times more efficient, in space or time.
This specific task, the next program I'm working on, seems to be a very "algo" based, comp sci type problem. I think most companies want to say that they have these kind of problems, but the reality often is, they need a batch script on a laptop.
So like, yeah, I have done things like this before in my work, but often, solutions in Python are "good enough".
Once hired (at a fantastic salary), she was then put to work copying data from a pile of CDs into a cloud storage account! Not only that, but she was given a laptop with only 1 CD drive to work with.
She quit within a week.
If something has to be done, then avoiding it makes you "smart" like avoiding taxes makes you "smart".
Sorry, I didn't mean "by translating to a lower level language".
In fact, I especially meant by fixing the script in the existing language.
Another basic pattern is converting a program or script that loads a whole job into memory into something with fixed size buffers, because specific data made the original explode.
Not for one script - but imagine everything like that is funneled to a group that supports operations. Such exists, as a matter of fact, question I have is how to find another one.
https://pdanpdan.github.io/wordle-solver/
main code in https://github.com/pdanpdan/wordle-solver/blob/master/src/li...
It solves in 3.45 moves on average, 5 or fewer moves always, and uses 5 moves less than 2% of the time.
The core parts are very fast, using bitwise tricks for filtering, uses caching throughout to reduce computation, and is fully multithreaded.
You can create your own Wordle-like puzzles on https://word.rodeo
I've already received a ton of positive feedback from friends. What are your thoughts?
On my phone I get a share sheet with additional text which makes visiting the url a pain
macOS 11.6, Chrome 96.0.4664.55.
The event listener was using event.target which wasn't the correct node when you hit the icon. I have fixed this now!
>> A set is a collection which is unordered, unchangeable*, and unindexed. [0]
I won't spoil how it works, but click the "?" button on the page if you want to know.
And you can solve it in a tree- at least for the lower levels when the search space has been reduced
I made a similar solver, it solves all the words in 3.65 average moves.
Could probably be better. The github explains how it works.
1) pick a first guess, and partition the remaining words by the hints that they give
2) given any part of a partition, pick a word that minimizes the maximum-size part of the resulting sub-partition
3) repeat (2) until words are solved.
My tree is quite different from yours, with guess distribution 1, 103, 861, 1114, 212, 24.
I think your heuristic is pretty similar to mine, just accomplished in a different way.
As it stands, it seems like your algo will always use the same first guess, have you thought about making that configurable and seeing what happens with e.g. the number of words where it gets stuck and runs out of time?
Yeah, next program will effectively do this but in an utterly insane way. Shall we brunch to discuss soon?
That website you linked doesn't lock the viewport so on my phone it's constantly panning or randomly zooming
And the grid instead a keyboard layout actually matters more than I expected for how easy it is to type
Having to manually start a game is a tiny thing but doesn't feel as smooth
I'm looking forward to trying to implement these subtle animations, too.