7 ms·

Optimal coverage for Wordle with Monte Carlo methods – Part III

50 points by Maro 5y ago

Maro 5y ago
['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).
- mortehu 5y ago
  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.
  - capitainenemo 5y ago
    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.
    - oezi 5y ago
      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.
      - mortehu 5y ago
        In a way it's supposed to be hard, because there will often be only a handful of options left.
    - mortehu 5y ago
      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.
      - capitainenemo 5y ago
        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.
        capitainenemo 5y ago
        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...
        mortehu 5y ago
        > 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).
        capitainenemo 5y ago
        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.
    - readthenotes1 5y ago
      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
      - readthenotes1 5y ago
        And with the actual word list from the game, e a r o t l i s n c
- photon-torpedo 5y ago
  TIL: https://en.wikipedia.org/wiki/Vozhd https://en.wikipedia.org/wiki/Vozhd https://en.wikipedia.org/wiki/Waqf https://en.wikipedia.org/wiki/Waqf How many such (arguably) obscure words are there in the Wordle word list?
  - brewmarche 5y ago
    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.
    - mdeck_ 5y ago
      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
    - bmm6o 5y ago
      Isn't Punic a proper noun? Those are excluded from most word games.
  - quibono 5y ago
    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.
    - thehours 5y ago
      The words are unique in each list, so the validation is on the combined set.
  - CrazyCatDog 5y ago
    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!
- readthenotes1 5y ago
  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.
Reventlov 5y ago
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.
- TillE 5y ago
  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.
tomlockwood 5y ago
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...
- unmole 5y ago
  > Maybe I should do a write up Absolutely
- hinoki 5y ago
  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 https://github.com/perigean/wordle/blob/main/tree.txt
  - MereInterest 5y ago
    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.
  - maxerickson 5y ago
    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).
pbhjpbhj 5y ago
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.
- mikequinlan 5y ago
  The word lists are in the Javascript for the page.
  - pbhjpbhj 5y ago
    Thank you.
adamjb 5y ago
Here are the rest of the 25 letter sets, found using brute force with the same 1 vowel per word with no repeated letters trick. [['brung', 'waqfs', 'vozhd', 'cylix', 'kempt'], ['brung', 'waqfs', 'vozhd', 'xylic', 'kempt'], ['jumby', 'waqfs', 'vozhd', 'clipt', 'kreng'], ['jumby', 'waqfs', 'vozhd', 'pling', 'treck'], ['jumby', 'waqfs', 'vozhd', 'prick', 'glent'], ['jumpy', 'waqfs', 'vozhd', 'bling', 'treck'], ['jumpy', 'waqfs', 'vozhd', 'brick', 'glent']] 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 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
- hiptobecubic 5y ago
  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.
fouadf 5y ago
I start with autos and miner Most common consonants and all vowels covered A try or two from there will get you covered
mynegation 5y ago
If author is here - “vozhd” does not mean “to lead”. It is a noun form of the verb, so it means “leader” or “chief”.
bbasketball 5y ago
Wordle fans should checkout https://wordhoot.com/ https://wordhoot.com/
- SubiculumCode 5y ago
  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.
rusty__ 5y ago
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?
- phkahler 5y ago
  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.
  - mturmon 5y ago
    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.
- ape4 5y ago
  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, ...
- SomeBoolshit 5y ago
  Finding the best way to beat a fun game is a fun game, as well.
- defaultname 5y ago
  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.
deleted 5y ago
[deleted]
akx 5y ago
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.

50 points by Maro 5y ago

Maro 5y ago

['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).

mortehu 5y ago
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.
- capitainenemo 5y ago
  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.
  - oezi 5y ago
    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.
    - mortehu 5y ago
      In a way it's supposed to be hard, because there will often be only a handful of options left.
  - mortehu 5y ago
    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.
    - capitainenemo 5y ago
      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.
      - capitainenemo 5y ago
        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...
      - mortehu 5y ago
        > 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).
        capitainenemo 5y ago
        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.
  - readthenotes1 5y ago
    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
    - readthenotes1 5y ago
      And with the actual word list from the game, e a r o t l i s n c
photon-torpedo 5y ago
TIL: https://en.wikipedia.org/wiki/Vozhd https://en.wikipedia.org/wiki/Vozhd https://en.wikipedia.org/wiki/Waqf https://en.wikipedia.org/wiki/Waqf How many such (arguably) obscure words are there in the Wordle word list?
- brewmarche 5y ago
  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.
  - mdeck_ 5y ago
    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
  - bmm6o 5y ago
    Isn't Punic a proper noun? Those are excluded from most word games.
- quibono 5y ago
  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.
  - thehours 5y ago
    The words are unique in each list, so the validation is on the combined set.
- CrazyCatDog 5y ago
  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!
readthenotes1 5y ago
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.

Reventlov 5y ago

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.

TillE 5y ago
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.

tomlockwood 5y ago

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...

unmole 5y ago
> Maybe I should do a write up Absolutely
hinoki 5y ago
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 https://github.com/perigean/wordle/blob/main/tree.txt
- MereInterest 5y ago
  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.
- maxerickson 5y ago
  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).

pbhjpbhj 5y ago

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.

mikequinlan 5y ago
The word lists are in the Javascript for the page.
- pbhjpbhj 5y ago
  Thank you.

adamjb 5y ago

Here are the rest of the 25 letter sets, found using brute force with the same 1 vowel per word with no repeated letters trick. [['brung', 'waqfs', 'vozhd', 'cylix', 'kempt'], ['brung', 'waqfs', 'vozhd', 'xylic', 'kempt'], ['jumby', 'waqfs', 'vozhd', 'clipt', 'kreng'], ['jumby', 'waqfs', 'vozhd', 'pling', 'treck'], ['jumby', 'waqfs', 'vozhd', 'prick', 'glent'], ['jumpy', 'waqfs', 'vozhd', 'bling', 'treck'], ['jumpy', 'waqfs', 'vozhd', 'brick', 'glent']] 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 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

hiptobecubic 5y ago
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.

fouadf 5y ago

I start with autos and miner Most common consonants and all vowels covered A try or two from there will get you covered

mynegation 5y ago

If author is here - “vozhd” does not mean “to lead”. It is a noun form of the verb, so it means “leader” or “chief”.

bbasketball 5y ago

Wordle fans should checkout https://wordhoot.com/ https://wordhoot.com/

SubiculumCode 5y ago
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.

rusty__ 5y ago

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?

phkahler 5y ago
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.
- mturmon 5y ago
  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.
ape4 5y ago
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, ...
SomeBoolshit 5y ago
Finding the best way to beat a fun game is a fun game, as well.
defaultname 5y ago
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.

deleted 5y ago

[deleted]

akx 5y ago

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.