Wordle-solving state of the art: all optimality results so far
poirrier.ca
poirrier.ca
Wordle 222 3/6
⬛⬛⬛⬛⬜
⬛⬜⬛⬜⬛
⬜⬜⬜⬜⬜
However, this isn't truly spoiler free. It still leaks information. From what I posted above alone, you can infer that the last letter is probably a relatively common one.
With the help of Twitter's APIs (or in my case, a janky screen-scraping script), you can trivially gather thousands of these emojified game logs. I do not consider this cheating, because sharing these is part of the game.
You can use these, in aggregate, to perform frequency analysis. I haven't shared my code yet because I'm still working on it, but as an example, here's the output from my script for day 216:
https://twitter.com/David3141593/status/1484669351261347842
Out of all the possible words, it ranked the correct solution at rank 5 - and that's before providing a single input to the game.
Edit: Replaced green blocks with "⬜" because HN doesn't like them.
1. Provide a different scoring mechanism. Number of guesses is a bit simplistic. I'd like to see something where blank squares are 2 points, yellow are 1 point, and green is 0. Then a total score could be computed across all guesses, with the goal being the least number of points. It would incentivize "hard mode" I think.
2. Provide a difficulty rating of the daily word based on average number of guesses
3. Given a "spoiler free" answer, make a game out of guessing what the original player guessed.
Thanks for clarifying, my first impression was inverted i.e. that the solid ones were "green".
I don't get what you mean about leaking information, but you can infer that all letters are "probably" relatively common ones, that's a property of relatively common, higher probability
If I give you the new information "I guessed L4 on my first guess", you can use this to update the histogram. The more-probable entries in the histogram are now even more probable, and the less-probable entries less probable.
For the specific numbers, have a look at Bayesian Inference
Code in C#: https://github.com/davidebbo/WordleReverseSolver
Although my current implementation is O(n), compared to his O(n^2) - but he's getting much better results.
https://medium.com/@furstenheim/learning-from-the-mistakes-o...
Yet another thing that’s easily overlooked is that you don’t share a URL with a preview, as most developers would naturally think of; it’s just plain text! So it’s absolutely trivial to cheat, much simpler than extracting the word list or the solution from the code.
But why would you cheat? What’s the point?
I made one simple web page with JS, HTML, and CSS, and now I can play it whenever I want (or show it off to my friends who introduced me to Wordle a few days ago).
Essentially Wordle is just Hangman with a neat twist.
I'd say the closer comparison is to Mastermind[0].
- Mastermind is based on abstract codes, Wordle is words. Words are fun!
- Wordle is much easier to explain. I could explain it to somebody who hadn’t heard of it and we could be playing on pen and paper inside two minutes.
Mum to mud to mad to Dad Dad to dam to dum to Mum
I do commend Josh Wardle for implementing Wordle with native web components, I personally wouldn't have the patience.
Your server-side PHP version would be slower for most users and might get expensive to run.
I'd consider Tetris to be far more impressive design-wise in that it's a easy to learn but difficult to master, despite its simplicity. It's a mind-blowing experience to watch the best Tetris players in the world. The skill gap between a beginner Wordle player and the best in the world simply cannot be that great, by nature of the game's design. I guess a large part of the reason is because the player can't alter the game state: they can only gain information. It doesn't allow for complexity to emerge.
Partly that's state, as you say, but I think it's also significant that Tetris is a realtime arcade-style game. Experts are vastly faster than newbies, and the main difficulty increase mechanism is that the blocks drop faster.
Wordle might have some similarities there. People don't commonly share their times, but I bet even among competent players who routinely solve it in 4-5 moves every day, there are some expert players who can do it much faster -- just like some people can solve the daily crossword in a few minutes, while others work on it gradually over the whole day.
You could also distinguish between people who usually take 4-5 moves and those who can do it in 3-4 (e.g. optimal play with its average of ~3.4 moves). It's just not obvious immediately because there's a lot of variance; if a great player solves it in 3 you could write it off as a fluke, and if a poor player is genuinely lucky and gets it in 2 you could mistake that for skill.
Both are very good games, but only one of them became a world wide sensation.
We can't share the wordle emoji thing here because hacker news strips something from it that removes the colors.
I'm in a group chat where we all share our Wordle results for the day. It seems everyone is at least as good as me.
In addition, if it was an ad-filled, high growth commercial venture, this approach would likely never have been chosen. (Not to mention the entire game mechanics of one word per day, instead of trying to show you a stream of ads every minute or so after each word you would have played).
I guess what I wanted to say is: thanks, open web!
The reason justification you just provided is wrong. People aren't digging through because they can, they're digging through because they like the game and it sits in a perfect state of simple, popular, fun where people want to see the curtains behind the game.
This would still be reverse engineered if it had to be decompiled first.
Your second statement kind of proves that you don't believe in your first statement, and in fact it is definitely the simplicity, popularity and fun that comes from the game that spawned intrigue.
What you really wanted to say was: "thanks, fun games!" because this has nothing to do with the game being open.
Flappy Bird and Desert Golfing are both really simple, and both were viral successes; but neither was directly analysed so rapidly and so openly, because it’s much more difficult to do that on iOS.
It's kind of made easier, but not started by open code.
If something is a huge success it's likely to be hacked, sure. But being open and hackable can contribute to its success, so if it's closed, it might be less likely to be a success in the first place. In which case nobody will bother hacking it.
Only the first guess is "unbounded"
https://jonathanolson.net/experiments/optimal-wordle-solutio...
Even with adversarial Wordle, the upper limit on guesses is 5 (ie after 3 guesses the maximum remaining word pool is 2)
The hardest words in Wordle are BOOBY / BOOZY no optimizer would include those letters in the first two guesses ...
joshbuckler wants an algorithm that has the fewest words that take at least 6 guesses, and also among all algorithms that tie for that number of words that take at least 6 guesses, has the fewest number of words that take at least 5 guesses, and also among all the algorithms that tie for that number of words that take at least 6 and at least 5 guesses, has the fewest number of words that take at least 4 guesses, and also...
The page you linked to doesn't seem to say it does that.
If you removed just 1 of those 2 words (leaving 2312 possible Wordles) all Wordles can be solved in max 4 guesses.
Ignoring the 2 scenarios where your first two "optimal" guesses are the Wordle
X% of the time you have 1 word left (guesses= 3)
Y% of the time you have 2 words left (guesses =3.5)
(100-Y-X)% of the time there is a pool of words left, requiring one more "optimal" guess
And either your optimal guess #3 is the Wordle Z% of the time (guess=3) or there is now one word remaining (guess ≈ 4)
Where Z in this case is just a function of the number of words remaining (ie Y is just a special case of Z)
So you want to maximize X and the weighted average of Z across pools.
By sheer brute force you can do so
1) for each 2 guess combo 2) discard any "suboptimal" combo where for any remaining response state word pool there is no optimal guess #3 (ie not possible to definitively guess in 4 guesses) 3) calculate avg remaining guesses 4) identify optimal word 1 (minimum of sum of step 2 per first guess) 5) within combos with word 1, identify optimal guess 2 for each response state
And the weighted average of step 3 for these combos is the global minimum for Wordle.
I believe this is the algorithm you're after? In this case, we're making a first guess that maximizes the chance we will get 3 guesses instead of 4.
Per this algorithm, optimal guess 1 is RAVED.
In other words: what's the cost of a second blind guess?
Maybe going even further: is it possible to still win the game with three blind guesses, or four? What is the smallest subset of "blind" guesses after which the possible solution set is "small" (say at most a word or a handful: less than some specified k).
First guess: ARISE Second guess (from 0 - 5 matches): COULD CLOUT CLOUT PLANT PWNED EIGHT
I'm hoping to get the 3.4 result, soon, in a Rust program I'm writing!
We’re both basically playing hard mode with letter position frequencies, but for some reason yours is slightly better, although I’m not sure why. Also, yours runs much faster than mine, probably because I’m using a regex instead of a proper positioning index.
I’ve been playing with various strategies, but position frequency of single letters has been the best one I’ve come up with. Even factoring factoring in the frequencies of bigrams is worse. Kind of depressing that my first guess was the best.
I’ve been explicitly avoiding incorporating knowledge that there is a target dictionary and legal guess dictionary. It seems like cheating, but it looks like the optimal bots use that information.
My next strategy is to explicitly calculate coverage of the words, instead of using probabilities. (FWIW, all my statistical approaches suck horribly. :/ )
Also yeah, my next attempt is going to do some other stuff, I moved to rust to speed it up, but its mostly a learning exercise.
Thanks for sharing!
"Score" is the sum of all the guesses, with 7 for losses.
Yours:
Wins 2302 Losses: 13 Surrenders: 0 Played: 2315 WinPct 99.438 %
Number of attempts to win: mean: 3.644811
Score (lower better) 8485
Winning Histogram
1 | 0.04 % | (1)
2 | 6.34 % | ### (146)
3 | 37.36 % | ################### (860)
4 | 43.31 % | ###################### (997)
5 | 11.08 % | ###### (255)
6 | 1.87 % | # (43)
Wins 2297 Losses: 18 Surrenders: 0 Played: 2315 WinPct 99.222 %
Number of attempts to win: mean: 3.626034
Score (lower better) 8455
Winning Histogram
1 | 0.04 % | (1)
2 | 5.75 % | ### (132)
3 | 40.81 % | #################### (937)
4 | 40.72 % | #################### (935)
5 | 10.37 % | ##### (239)
6 | 2.31 % | # (53)Since the game rejects words that are not in the guess list without penalty, it could easily have been brute forced if it was not easily obtainable from the implementation.
This sub-link is especially good. https://alexpeattie.com/blog/establishing-minimum-guesses-wo...
I really really need to learn how to use an SAT solver. The problems they can solve is downright magical as far as I’m concerned. Does anyone know of some good tutorials?
And for MIP solving, the Python mip package is quite convenient.
You can view these as compilers to SAT, much like "no-one writes in assembler", most people don't write raw SAT either :)
Apart from that, it is worth noting that the solver used in the article, OR-Tools, is not strictly a SAT solver. I would rather describe it as a hybrid portfolio solver, since it combines constraint programming, SAT, MIP, and local search in a single solver. It is also possible to use that solver as a back-end when solving a model written in MiniZinc.
It seems to me like with more flexibility in what words to guess, it might be able to eliminate words faster and build a more-optimal tree.
some algorithms can be described as a decision tree, but not all.
still curious if they all converged to the same seed word (or basket of seed words with similar characteristics).
still curious what the first node looks like though ... (and it it's similar across what people are finding)
My wife plays and has tried strategies like focusing on high frequency letters or maximizing vowels used in the first word, for example. It would be neat to know if one of these approaches yielded more information than others.
If you want something much less elaborate (i.e. something you can memorize), you will find plenty of heuristics (e.g. "what are the optimal two starting words based on letter distributions") in the earlier discussions. The optimality of a heuristic for your strategy necessarily depends on your strategy though, and unless you actually memorized the list of solution/trial words, such a strategy will remain impossible to formalize.
In the show, you usually get one letter for free in the six letter words so there's a better word set available with more words to remember. Despite this, the episode was quite boring to watch because the optimized guessing strategy takes all the fun out of the game by guessing the same words every day.
But I agree that using the 2315-word list is basically cheating. On the other hand, are words in that list more common English words than words in the 12972-word list? If so, then humans in a sense intuitively take advantage of the 2315-word list by guessing more common English words rather than infrequent English words. So since humans sort of use the 2315-word list intuitively, it sort of makes sense for a computer to use it as well.
Subjectively, yes - those are the 2315 words that the dev's partner recognised out of the 12972.
This leaves a fuzzy middle ground for human players: there are accepted guess words like SOARE that can be good as a first guess, but is almost certainly not going to be the answer. Conversely, FAVOR is not a good first guess; but of the two words human players know which is more likely to be the answer.
For computer implementations that want to avoid "cheating" (not use the answer list), there would still seem to be room for evaluating how likely a given guess is to be in the curated list.
That could be done by examining a corpus for frequency of each guess word, which if done right should give the same insight we have as humans.
Here is the code if anyone is interested : https://gist.github.com/unrealwill/83dc7a1d0675ac0751535a6c4...
Could eliminating previous solutions help reduce the search space meaningfully?
Of course, on the last day (in 2027?), there will only be one word left, so the game can be solved with one query.
That's not interesting, but for how long will the game stay interesting? How hard will it still be in 2023, 2024, etc.?
The word list for the initial guess can be precomputed (I handle this simply as well, top 16 words with 3+ vowels, no duplicated letters and maximized pairwise similarity). The easiest first step that goes a long way on its own is simply maintaining constraints. Having applied constraints, the next issue is selecting from narrowed word lists. To do that I compare every word to every other word by spelling, idea being highest scoring word will be most informative, but also constrained to maximize difference from previous guess (although this step is rarely needed).
As available guesses are already significantly whittled down even by second guess, it runs in << 1s and completes in 3-4 guesses.