Optimal coverage for Wordle with Monte Carlo methods – Part III(bytepawn.com)
bytepawn.com
Optimal coverage for Wordle with Monte Carlo methods – Part III
https://bytepawn.com/optimal-coverage-for-wordle-with-monte-carlo-methods-part-iii.html
55 comments
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.
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.
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...
Are you using only the answer words as guesses?
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
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
Hey I did a little write up: https://news.ycombinator.com/item?id=30050231
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.
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 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
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
> Maybe I should do a write up
Absolutely
Absolutely
['brick', 'glent', 'jumpy', 'vozhd', 'waqfs']
"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).
"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).
TIL:
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://en.wikipedia.org/wiki/Vozhd
https://en.wikipedia.org/wiki/Waqf
How many such (arguably) obscure words are there in the Wordle word list?
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.
Possibly attributable to the definition of “(going) dutch” as “splitting the bill”?
https://www.merriam-webster.com/dictionary/dutch
https://www.merriam-webster.com/dictionary/dutch
Isn't Punic a proper noun? Those are excluded from most word games.
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!
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.
raise and arise aren't too bad (and atone with traditional "etoain shrdlu") but my suspicion based on:
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.
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.
Doing a similar analysis on the enable2k word list comes up with a slightly different order:
s e a o r i l t n d
s e a o r i l t n d
And with the actual word list from the game,
e a r o t l i s n c
e a r o t l i s n c
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.
In a way it's supposed to be hard, because there will often be only a handful of options left.
I took into account the position constraints you learn from the game after entering the word too. This is why "raise" beats "arise" for example.
oh. that's an excellent point. I hadn't thought about that.
right letter wrong place is far less useful than right letter right place.
> 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).
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.
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.
hm. again I don't know what dictionary he's using, but using /usr/share/dict/words and some more shell I get:
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...
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...
I took the letter words from the enable2k word list, and calculated the letter frequency. It is not the same as it is for all English words.
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?
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.
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.
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.
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?
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?
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.
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.
Yes, the word optimal should be understood very narrowly here.
Part of the fun (and in game-nerdery terms, the “optimality”) is getting there before 6 guesses, which would require some adaptive strategy.
Part of the fun (and in game-nerdery terms, the “optimality”) is getting there before 6 guesses, which would require some adaptive strategy.
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.
Finding the best way to beat a fun game is a fun game, as well.
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.
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?
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.
You (and your friends) don't have to use a script. Every other game has been solved by programs: tick-tac-toe, sudoku, chess, go, ...
Wordle fans should checkout https://wordhoot.com/
Nice job with the game.
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.
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.
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.
Considering there is no LICENSE in the original notebook or repo, I'm not sure I can publish my changes.
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.
[deleted]
What dictionary are Wordle using? The Bytepawn author mentions the dictionary is known, in part 1, but not where this info comes from?
Vozhd, for example, is not in Merriam-Webster.
Vozhd, for example, is not in Merriam-Webster.
I start with autos and miner
Most common consonants and all vowels covered
A try or two from there will get you covered
If author is here - “vozhd” does not mean “to lead”. It is a noun form of the verb, so it means “leader” or “chief”.
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.
[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