"Optimal coverage" in the article title refers to unique letters. It's not the case that playing these is optimal, due to frequencies and position-density of letters (obviously).
I wrote a script that finds the word that gives the smallest average number of possibilities left (across all possible actual solutions) and came up with "raise". "cloth" is often a good second word, but it depends of course.
42 q 70 j 89 x 97 z 261 v 418 w 445 f 480 k 549 g 557 b 636 y 646 h 647 m 757 p 793 c 828 u 990 d 1027 n 1266 t 1268 i 1305 l 1468 o 1488 r 1848 a 2443 e 2552 s
I often struggle to find a matching second word when I start with soare or raise. I wonder if somebody did try to optimize for a first word that makes it easy to come up with a second quess statistically.
> right letter wrong place is far less useful than right letter right place
It's not that easy. If you're guessing the most common position for a letter, you may not be gaining the maximum amount of information.
The heuristics approach you're using won't beat brute force evaluation of all possible guesses for all possible solutions (which is only a few million combinations).
Well, part of the goal is also to finish in less than 6 guesses, so surely an optimal starting pattern is best. And since you can't do better than each letter being unique, you might as well ensure those unique letters are both common and ideally positioned. From that point on, the remaining words I guess you could brute force, or combine statistical with statistical to cover best letters first.
I'm sure brute forcing will probably guarantee a win almost always, but will it be, for example a 3 or 4 word win which is pretty easy to do for a human.
Also, how many words are not on the list? I tried “Punic” today (granted that might be considered obscure as well) and it wasn’t accepted. I just checked “Dutch” and it is okay while “Irish” is not.
Apparently there are two word lists: one for the word to be guessed and one to validate user guesses. I imagine vozhd and waqf would appear in the latter lit but not in the former.
The NYT article suggests that one person validated the list—however that one person is an avid word game player, and is in fact the developer’s partner, for whom the game was created—so said validator likely had a deep vocabulary of highly arcane words!
What I'm looking for is some optimal solution, in the average number of guesses needed, for the two dictionaries of Wordle. I think we already know that covering all letters is not optimal at all with this regard, given the large letters frequency imbalance in the dictionaries.
Yeah ideally you want to narrow down your search space as much as possible with each guess. Starting with determining your vowels seems like a natural thing to do, but it gets slightly more complex from there if you're looking at letter frequencies and positions.
I wrote a solution that loses 13 times out of the 2315 possible games, but gets the answer correct on average in 3.64 guesses, on hard mode! Maybe I should do a write up...
I have a decision tree that averages 3.67 guesses [0], so a bit worse than yours, but the maximum guess length is 5. My heuristic is to search for trees by looking at how the guesses split the remaining answers by their match patterns. For each guess, create a map from match pattern to the count of answers with that pattern. Order guesses by the sum of the squares of answer counts (to penalise patterns with lots of answers). Evaluate sub-trees for the top 2^(6 - depth) guesses.
Ooh, interesting! I ended up making a framework to test different strategies. The minimax strategy is the most similar to yours, but it orders guesses by the maximum number of answer counts, and doesn't check any of the sub-trees. It still has a maximum guess length of 5, but has a slightly worse average at 3.81 guesses.
Edit: How often do you need to evaluate sub-trees as a tie-breaker? I re-implemented your strategy of selecting the guess that minimizes the sum of the squares of the counts, but didn't include the evaluation of sub-trees. That was enough to reproduce your 3.67 average, (`{2: 23, 3: 802, 4:1416, 5:74}`), without the sub-tree recursion.
How would your approach work against random 20 character strings?
I feel like calculating the possibility space for such a small game doesn't really reveal a lot (because we can just observe that it is a small game in that sense).
I've got a solution that filters the answer space down each guess, picking words with most common letter frequency and common letter position as a tie breaker.
Avg is 3.7 guesses, worst case is 6 over the entire wordle dictionary. I don't think it would have any issues scaling to 20 letter words. https://github.com/mschrandt/Wordle
I was a little inspired by this thread [0] about the practicality of implementing brute force algs in pure python for solving wordle. Using only built-ins and with a bit of optimisation [1] it runs in 4 minutes single threaded in cpython.
[1] Instead of considering every possible combination, it discards non-optimal subsets. E.g. when considering o-words, only u- and a-word combos that already cover 10 letters are looked at. This significantly dampens the combinatorial explosion
This is a lesson I think should really be brought up more often. Everyone constantly talks about which language is fast or slow, but 9 times out of 10 the question should be which _programs_ are fast or slow. Improvements like this often completely trump everything else. The move from bash to rust is generally a linear improvement, but discovering a better algorithm has way more potential.
My experience has been that the range of problems big enough for scale to matter, but small enough for language to matter isn't that big. If I won't wait a year for python to compute something, I probably won't wait three weeks for rust either.
Obviously if we're talking about paying for compute cycles then it matters, but surprisingly that's not usually where discussion is focused.
You know, as much as I admire the drive of people to write tools and hack together scripts to brute force and essentially break the game - I also hate that the world is like this sometimes. Cant we just have a fun game that people can while away a few minutes a day being human and imperfect for once? Do we have to find the optimal solution to everything... all the time?
Agreed, but in this case I don't see it as optimal. In the last example he's found 4 of the 5 letters after 2 guesses. Using 3 more guesses at that point seems like a bad idea. At some point finding words that shuffle known letters around to unscramble them might be better. There are also words like ROBOT that have duplicate letters - that was the wordle of the day recently.
For a nice do-it-by-hand puzzle try this:
Fill a 4x4 grid with whole numbers less than 30, such that all rows have the same product (of all 4 numbers) and all columns have the same sum (of all 4 numbers). This can be done by hand with some paper - I kept notes in notepad to do it.
The game itself has limited novelty, with the majority of people getting the solution in 3 or 4 guesses through normal fitting. It's entirely natural that people try to find new ways to challenge themselves with it.
You're asking whether we can have a challenge where no one on earth is interested in studying it and I think the answer is "no."
If you don't want spoilers, don't look them up? It's like complaining that the existence of archeology as a field takes the romanticism out of dinosaur stories.
I don't think I'm asking that? I guess I'm asking, where is the fun in reducing a game that takes some brain power to a game of solving one 5-letter anagram. Your analogy is a fair one though. I don't begrudge people using their talents to analyse and dig deep in to a game (like chess or go), I think it's just a bit sad that every single one of these simple games is effectively broken just days or hours after taking hold with 20 lines of code (see also 2048).
> every single one of these simple games is effectively broken
Can you elaborate on how the game is broken? How does someone else writing a solver affect your own enjoyment of the game? Wordle isn’t competitive, right, so is the problem just knowing that a robot can do it demotivates you from trying?
This might be an interesting question about human behavior and our motivations that we should think about as we move into the AI age, because no, there will never be another popular game that escapes AI players. Not only are we going to make AI for every playable game, we are building AI for every human activity.
FWIW, I’ve written Sudoku and Boggle solvers, and still love to play those games manually. In fact writing the solvers I think increased my own enjoyment of them, it gives a certain perspective on the difficulty of the game, and of how much humans do to simplify our effort compared to a computer.
I guess it's broken because it's been reduced from a game of progressive deduction to solving 1 5 letter anagram - not the original intent of the game.
I completely agree that it's a fascinating wider question I think I'm alluding to here - living in a world where AI/computer brute force can achieve everything is a going to be a strange place to live in in 50-100 years time. Do we want to make humans redundant in this way - sure this is just a silly game, but, as COVID has shown us the last couple of years, supply chains, logistics etc are all minutely tuned and determined by computers with little human involvement - is that a world we all want to live in, I'm not so sure.
But I mean why does someone else reducing the game to an algorithm hurt your personal experience with the game? If you don’t use AI to play the game, and if the game isn’t competitive, why does it make you sad when someone else does?
BTW I’m not trying to debate or contradict you, your opinion is valid and I’m hoping to dig into that wider question a little by getting more specific about your personal experience and emotions, to uncover in more detail what it is about AI that is bumming you out. I’m curious to hear about what the automation is taking away from you from your perspective. Does the Wordle anagram solver here feel worse to you or similar to older examples like the Big Blue chess AI? And how do computers in general fit in, as well as mechanical automation like cars & tractors, etc?
Are there certain kinds of AI automation you see value in, any things that leave humans with less manual labor and more free time? I’m kind of excited for driving AI, for example, if we can make it safe and reliable enough. It will definitely upset certain economies, but maybe fewer accidents and traffic jams and more free time during travel are redeeming values?
I agree. The one thing I wish there was a program that just gave me the list of remaining possible words. Some start words have an S or T in them which doesn't really help since 80% of the word list has an S or T. I use more obscure words. Sometimes it works and sometimes it doesn't. I got today's on the 2nd guess by thinking "what is a weird word" with only knowing one letter and I got it. These days are way more fun than always getting it on turn 4.
I don't see the harm in someone spending a few hours nerding out on a strategy for a solitaire game. It's an interesting read for some, and shouldn't diminish your enjoyment.
The group of people playing a game, and group of people analyzing the same game for optimal solutions are both doing the it for fun. In what way does either group spoil the fun for the other?
There's a lot to optimize here - a bit of looking at the profiler and an 8-line patch makes generating 24-character solutions already 5+ times faster (on my MacBook, using a single process).
Considering there is no LICENSE in the original notebook or repo, I'm not sure I can publish my changes.
55 comments
[ 43.5 ms ] story [ 191 ms ] thread"Optimal coverage" in the article title refers to unique letters. It's not the case that playing these is optimal, due to frequencies and position-density of letters (obviously).
grep -P '^[a-z]{5}$' /usr/share/dict/words | sed 's/\(.\)/\1\n/g' | grep -Pv '^\s$' | sort | uniq -c | sort -n | xargs
42 q 70 j 89 x 97 z 261 v 418 w 445 f 480 k 549 g 557 b 636 y 646 h 647 m 757 p 793 c 828 u 990 d 1027 n 1266 t 1268 i 1305 l 1468 o 1488 r 1848 a 2443 e 2552 s
and:
$ grep -P '^[a-z]{5}$' /usr/share/dict/words | sed 's/\(.\)/\1\n/g' | grep -Pv '^\s$' | sort | uniq -c | sort -n | tail -n 10 | awk '{print $NF}' | xargs | rev
s e a r o l i t n d
for a bit more readability, is that "arose" is a better starting word for 5 letter english words.
That said, the difference between the i and the o is not large, so both probably work well.
1st: 303 t 305 p 343 b 370 c 629 s
2nd: 404 u 511 e 530 i 699 o 758 a
3rd: 325 n 370 r 405 o 444 i 515 a
4th: 253 a 299 l 313 n 358 t 1013 e
5th: 291 t 394 d 472 y 495 e 1506 s
So.. I guess unsurprisingly ending a word in "es" is the way to go and an "a" is 2nd is pretty good closely followed by "o"
With those values "cares" or "bares" seems like a better bet? It gets you that popular r in 3rd, and the ending es...
It's not that easy. If you're guessing the most common position for a letter, you may not be gaining the maximum amount of information.
The heuristics approach you're using won't beat brute force evaluation of all possible guesses for all possible solutions (which is only a few million combinations).
I'm sure brute forcing will probably guarantee a win almost always, but will it be, for example a 3 or 4 word win which is pretty easy to do for a human.
s e a o r i l t n d
e a r o t l i s n c
https://en.wikipedia.org/wiki/Vozhd
https://en.wikipedia.org/wiki/Waqf
How many such (arguably) obscure words are there in the Wordle word list?
https://www.merriam-webster.com/dictionary/dutch
Absolutely
I have a decision tree that averages 3.67 guesses [0], so a bit worse than yours, but the maximum guess length is 5. My heuristic is to search for trees by looking at how the guesses split the remaining answers by their match patterns. For each guess, create a map from match pattern to the count of answers with that pattern. Order guesses by the sum of the squares of answer counts (to penalise patterns with lots of answers). Evaluate sub-trees for the top 2^(6 - depth) guesses.
[0] https://github.com/perigean/wordle/blob/main/tree.txt
Edit: How often do you need to evaluate sub-trees as a tie-breaker? I re-implemented your strategy of selecting the guess that minimizes the sum of the squares of the counts, but didn't include the evaluation of sub-trees. That was enough to reproduce your 3.67 average, (`{2: 23, 3: 802, 4:1416, 5:74}`), without the sub-tree recursion.
I feel like calculating the possibility space for such a small game doesn't really reveal a lot (because we can just observe that it is a small game in that sense).
Avg is 3.7 guesses, worst case is 6 over the entire wordle dictionary. I don't think it would have any issues scaling to 20 letter words. https://github.com/mschrandt/Wordle
I did :D
Vozhd, for example, is not in Merriam-Webster.
[0] https://twitter.com/eevee/status/1484716294179934209
[1] Instead of considering every possible combination, it discards non-optimal subsets. E.g. when considering o-words, only u- and a-word combos that already cover 10 letters are looked at. This significantly dampens the combinatorial explosion
My experience has been that the range of problems big enough for scale to matter, but small enough for language to matter isn't that big. If I won't wait a year for python to compute something, I probably won't wait three weeks for rust either.
Obviously if we're talking about paying for compute cycles then it matters, but surprisingly that's not usually where discussion is focused.
Not to belittle your effort, but one of the appeals of Wordle is 1) everyone has the same word, 2)Once per day. It becomes a ritual between friends.
For a nice do-it-by-hand puzzle try this:
Fill a 4x4 grid with whole numbers less than 30, such that all rows have the same product (of all 4 numbers) and all columns have the same sum (of all 4 numbers). This can be done by hand with some paper - I kept notes in notepad to do it.
Part of the fun (and in game-nerdery terms, the “optimality”) is getting there before 6 guesses, which would require some adaptive strategy.
If you don't want spoilers, don't look them up? It's like complaining that the existence of archeology as a field takes the romanticism out of dinosaur stories.
Can you elaborate on how the game is broken? How does someone else writing a solver affect your own enjoyment of the game? Wordle isn’t competitive, right, so is the problem just knowing that a robot can do it demotivates you from trying?
This might be an interesting question about human behavior and our motivations that we should think about as we move into the AI age, because no, there will never be another popular game that escapes AI players. Not only are we going to make AI for every playable game, we are building AI for every human activity.
FWIW, I’ve written Sudoku and Boggle solvers, and still love to play those games manually. In fact writing the solvers I think increased my own enjoyment of them, it gives a certain perspective on the difficulty of the game, and of how much humans do to simplify our effort compared to a computer.
I completely agree that it's a fascinating wider question I think I'm alluding to here - living in a world where AI/computer brute force can achieve everything is a going to be a strange place to live in in 50-100 years time. Do we want to make humans redundant in this way - sure this is just a silly game, but, as COVID has shown us the last couple of years, supply chains, logistics etc are all minutely tuned and determined by computers with little human involvement - is that a world we all want to live in, I'm not so sure.
BTW I’m not trying to debate or contradict you, your opinion is valid and I’m hoping to dig into that wider question a little by getting more specific about your personal experience and emotions, to uncover in more detail what it is about AI that is bumming you out. I’m curious to hear about what the automation is taking away from you from your perspective. Does the Wordle anagram solver here feel worse to you or similar to older examples like the Big Blue chess AI? And how do computers in general fit in, as well as mechanical automation like cars & tractors, etc?
Are there certain kinds of AI automation you see value in, any things that leave humans with less manual labor and more free time? I’m kind of excited for driving AI, for example, if we can make it safe and reliable enough. It will definitely upset certain economies, but maybe fewer accidents and traffic jams and more free time during travel are redeeming values?
Considering there is no LICENSE in the original notebook or repo, I'm not sure I can publish my changes.