5 ms·

Going for greens is a good heuristic, but the general solution is to seek guesses that shrink the size of the set of compatible words the most. https://langproc

Going for greens is a good heuristic, but the general solution is to seek guesses that shrink the size of the set of compatible words the most. https://langproc.substack.com/p/information-theoretic-analysis-of https://langproc.substack.com/p/information-theoretic-analys...

zeroonetwothree 5y ago
Using essentially this method I get that the best initial guess is RAISE (there are some others that are very close). It seems the author of this post didn’t use the actual word list from the game so got a different word.
- tomlockwood 5y ago
  I used the actual wordlist, yoinked out of the javascript with my totally elite dev-tools-in-chrome-hacking! But yeah, given the frequency of letters, in position, in the target list, the answer is SLATE.
- canjobear 5y ago
  Yeah when I ran my script using the real wordlist I got RAISE too. (Just updated the article.)
- loeg 5y ago
  For me, ARISE and RAISE were equally good.
OJFord 5y ago
Or, especially in first guess or so, shrink the set of letters used by the remaining compatible words, which is subtly different right?
npinsker 5y ago
> From an information-theoretic perspective, the optimal initial guess is the one which is maximally informative about the target, given the resulting pattern. 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.
- canjobear 5y ago
  Yeah, the analysis doesn't really work for hard mode as noted in a footnote.
  - npinsker 5y ago
    I don't think it works for easy mode either. The overwhelming majority of 6-word sets can be distinguished in two guesses in easy mode (their EV is either 11/6 or 2), while this set has an EV that's around 3.
    - canjobear 5y ago
      I think you're right. Although a first guess might reduce the set size a lot, it might lock you into a situation where all the possible second guesses are useless.
    - pxx 5y ago
      for this specific set in easy mode doesn't (bawds, chefs) result in unique responses for all of them? so that's 2.5 guesses total? Where are you getting the EV for 6-word sets?
      - npinsker 5y ago
        You're right: the EV is 2.5 (my guess was pessimistic). For (almost all) 6-word sets, there's a single word you can use to delineate all six words, which gives an EV of 1.83 if that word is in the set and 2 if it isn't.
kccqzy 5y ago
That's exactly my approach. 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.)
- carry_bit 5y ago
  I also implemented essentially this algorithm. For guesses I always consider the full list of possible words, not just the list of possible answers. Doing so requires a check so words that have been excluded are only used if they're better than words that haven't been.
- returningfory2 5y ago
  FWIW, your O(N^3) algorithm can be equivalently implemented in O(N^2) by using the following observation: a word is not eliminated by a guess if and only if the result of testing the word against the solution is the same as the result of testing the guess against the solution. Using this, you can implement the algorithm like so: for a given solution, partition all of the guesses based on the result of testing them against that solution. This partitioning takes O(N). Then, the set of words that will be left over from a guess is equal to all the words in the same partition as the guess. This makes it easy to calculate "how many words can be eliminated from a particular guessed word". I'm making this comment because I started with the same O(N^3) approach and then realized this. :)

zeroonetwothree 5y ago

Using essentially this method I get that the best initial guess is RAISE (there are some others that are very close). It seems the author of this post didn’t use the actual word list from the game so got a different word.

tomlockwood 5y ago
I used the actual wordlist, yoinked out of the javascript with my totally elite dev-tools-in-chrome-hacking! But yeah, given the frequency of letters, in position, in the target list, the answer is SLATE.
canjobear 5y ago
Yeah when I ran my script using the real wordlist I got RAISE too. (Just updated the article.)
loeg 5y ago
For me, ARISE and RAISE were equally good.

OJFord 5y ago

Or, especially in first guess or so, shrink the set of letters used by the remaining compatible words, which is subtly different right?

npinsker 5y ago

> From an information-theoretic perspective, the optimal initial guess is the one which is maximally informative about the target, given the resulting pattern. 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.

canjobear 5y ago
Yeah, the analysis doesn't really work for hard mode as noted in a footnote.
- npinsker 5y ago
  I don't think it works for easy mode either. The overwhelming majority of 6-word sets can be distinguished in two guesses in easy mode (their EV is either 11/6 or 2), while this set has an EV that's around 3.
  - canjobear 5y ago
    I think you're right. Although a first guess might reduce the set size a lot, it might lock you into a situation where all the possible second guesses are useless.
  - pxx 5y ago
    for this specific set in easy mode doesn't (bawds, chefs) result in unique responses for all of them? so that's 2.5 guesses total? Where are you getting the EV for 6-word sets?
    - npinsker 5y ago
      You're right: the EV is 2.5 (my guess was pessimistic). For (almost all) 6-word sets, there's a single word you can use to delineate all six words, which gives an EV of 1.83 if that word is in the set and 2 if it isn't.

kccqzy 5y ago

That's exactly my approach. 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.)

carry_bit 5y ago
I also implemented essentially this algorithm. For guesses I always consider the full list of possible words, not just the list of possible answers. Doing so requires a check so words that have been excluded are only used if they're better than words that haven't been.
returningfory2 5y ago
FWIW, your O(N^3) algorithm can be equivalently implemented in O(N^2) by using the following observation: a word is not eliminated by a guess if and only if the result of testing the word against the solution is the same as the result of testing the guess against the solution. Using this, you can implement the algorithm like so: for a given solution, partition all of the guesses based on the result of testing them against that solution. This partitioning takes O(N). Then, the set of words that will be left over from a guess is equal to all the words in the same partition as the guess. This makes it easy to calculate "how many words can be eliminated from a particular guessed word". I'm making this comment because I started with the same O(N^3) approach and then realized this. :)