4 ms·

Cool! I made a solver myself, yesterday. For every move, it ranks each legal word based on how much information that word will gain. It figures this out by tryi

by andopp 5y ago

Cool! I made a solver myself, yesterday. For every move, it ranks each legal word based on how much information that word will gain. It figures this out by trying all possible solutions that are still compatible with the information acquired so far. The word that gives the biggest reduction (worst case) in size of candidate solution pool, is the chosen word. For yesterday's word, it yielded the following sequence of guesses: AESIR, DROPT, ABCEE, QUERY! Most useful for us humans is that AESIR seems to be the best starting word. Here is my java source code for this solver: https://pastebin.com/k1tTCyUR https://pastebin.com/k1tTCyUR A bit obfuscated by some necessary optimziations.

ghusbands 5y ago
"Aesir" wouldn't be an accepted word in most word games, being a proper noun (capitalised). But "raise" uses the same letters, though obviously reveals differently positional info.
- notafraudster 5y ago
  ARISE and SERAI also have the same letters and different positional info. In the dictionary I used, SERAI was the optimal 5 letter word to start with.
- andopp 5y ago
  When I tried with the /usr/share/dict/words dictionary it guessed "raise" first, so I can confirm it's a great way to start the game.
thom 5y ago
These guesses seem counterintuitive in that they waste letters by repeating previous guesses. Interesting if this is optimal though.
- ghusbands 5y ago
  Reducing the possible position of letters can drastically reduce the set of possible words; but intuition probably tends towards getting more information about the presence or lack rather than the position of letters. I don't think anyone has released an 'optimal' player, yet. I imagine getting all target words (in the wordle dictionary) in four guesses is doable and three is probably not.
  - ChrisLomont 5y ago
    My bot averages ~ 3.5 moves, does all in 5, and less than a few % uses 5. I've tried many, many approaches to get all in 4, and so far none work. It is very nearly optimal (many of the parts are provably optimal, the only thing not yet optimal is doing an entire tree search, which is likely computationally impossible due to required tree size), using quite a bit of computation, precomputation, caching, etc., for the searching. Oh, I also have a bot that solves Wordle in one move, every time. Hint: the source code for Wordle is viewable from the page, and is easy to use to predict the word for each day.... But I've said too much now :)
    - ghusbands 5y ago
      (Warning: To anyone who might follow the hint, maybe heed my warning in another comment on this HN page.) Yeah, it might be bit cheeky to have a bot that guesses one word, and then gives you the correct answer and the date on which Wordle used or will use it. Is the tree size still too big if you're only using Wordle's word list? (I'm almost interested enough to code something up, but asking you might mean I don't get fully nerd-sniped.)
      - ChrisLomont 5y ago
        >Is the tree size still too big if you're only using Wordle's word list? Yes, it's what I use. Wordle has ~2300 words as possible hidden words, ~12,000 more allowed as guesses. To get best scores you need to sample from all ~15k words. So, to build a tree: for each hidden word (2k), pick a guess word (15k), gain knowledge (729 possibilities, but only one per hidden/guess pair). This reduces your possible hidden list to 70-1kish. Repeat.. Worst tree is 5 levels deep, mine averages 3 levels deep, pruning and memoization is nearly nonexistant (I checked). You now have 30M first move outcome nodes, 2k of which are wins. After second move, you have a billion plus (I've sampled these to gain knowledge of what to expect). The next few rounds push the compute time into crazy realms of time (again, I've sampled to estimate sizes). I'd guess given a lot of computing power, it could be done, since around 3-4 levels most of the games complete. But since you cannot easily store this tree, I gave up for now. You should be able to store the tree with best move only at each node, which is good for gaming, but loses interest for statistical knowledge of the tree. Good luck :) Nerd sniping complete :)
- andopp 5y ago
  I think it's better to not repeat too much from previous guesses. I don't think my greedy algorithm is optimal, and also there are multiple ways to define "optimal". For instance, you might optimize average number of moves, or try to lower the upper bound for all possible words.
  - andopp 5y ago
    Oh I misunderstood the comment I was replying to. Sometimes it is better to repeat letters, because it's a balance between discovering letters and figuring out the order.
Dwolb 5y ago
How are you calculating “biggest reduction in size of candidate pool”? Wondering if you’re trying to split the pool 50-50 or more like 90-10.
- jhgb 5y ago
  It would seem to me that 50-50 would be the "biggest reduction" since presumably you're judging the pruning based on the worst case. In the latter case the worst case is that you're still left with 90 options. Maybe I'm looking at it too much as some kind of decision tree but it looks to me like one, or at least something very similar. You don't want any branch to be too long.
  - deleted 5y ago
    [deleted]
  - Dwolb 5y ago
    I think what we’re missing is information gained by understanding the letter location. So if S is in 90% of words, well you also reveal whether or not it’s in the nth location. Whereas an incorrect guess gives you no location information. So, you’d want to guess the word that equally splits the word pool given both the letter and letter location (or just letter in a given location).
- andopp 5y ago
  I try to cut it down to as small a set of candidates as possible. Any reason to think a different split is better?
  - Dwolb 5y ago
    I was thinking that if you guess S correctly and it is in 90% of words and not in 10% of words, you’ve only removed 10% of words from the pool. Whereas if there were a letter closer to occurring in only 50% of the pool, you at least eliminate half. Does that logic make sense here or no? I’m thinking I’m missing something related to “maximum information gain”.
jhgb 5y ago
You have a list of legal words? Where is it available?
- detaro 5y ago
  in the source code of the site.
- andopp 5y ago
  There is also /usr/share/dict/words or https://github.com/dwyl/english-words https://github.com/dwyl/english-words which can be used.
  - jhgb 5y ago
    I actually have several such lists already, but if the actual list of candidate words in this game is a subset of the ones I have, I imagine solution can be arrived at quicker by excluding guesses that couldn't possibly lead to the solution.
- bfung 5y ago
  Goto wordle, right click “view source”, click and view the “main.<hash>.js” file. Search a word from previous answers, there are 2 arrays that the game uses to check with. Copy those and that’s the dictionary. Spoiler alert: the first array is the answer array for even future wordles.
  - jhgb 5y ago
    > Spoiler alert: the first array is the answer array for even future wordles. That's presumably the reason why I wouldn't want to view the source.
    - bfung 5y ago
      This lists are pretty big where if you were to copy and paste them real fast, your eyes would glaze over them enough to not know the answers... maybe just the next day ;)
loeg 5y ago
Mine does AESIR, DROPT, EVERY, then QUERY for Wordle 205. There are 3197 equally good guesses for the 3rd word (ABCEE / EVERY) on that puzzle, or 336 if you prioritize words on the answer list (which is why I land on EVERY instead of ABCEE).

by andopp 5y ago

ghusbands 5y ago

"Aesir" wouldn't be an accepted word in most word games, being a proper noun (capitalised). But "raise" uses the same letters, though obviously reveals differently positional info.

notafraudster 5y ago
ARISE and SERAI also have the same letters and different positional info. In the dictionary I used, SERAI was the optimal 5 letter word to start with.
andopp 5y ago
When I tried with the /usr/share/dict/words dictionary it guessed "raise" first, so I can confirm it's a great way to start the game.

thom 5y ago

These guesses seem counterintuitive in that they waste letters by repeating previous guesses. Interesting if this is optimal though.

ghusbands 5y ago
Reducing the possible position of letters can drastically reduce the set of possible words; but intuition probably tends towards getting more information about the presence or lack rather than the position of letters. I don't think anyone has released an 'optimal' player, yet. I imagine getting all target words (in the wordle dictionary) in four guesses is doable and three is probably not.
- ChrisLomont 5y ago
  My bot averages ~ 3.5 moves, does all in 5, and less than a few % uses 5. I've tried many, many approaches to get all in 4, and so far none work. It is very nearly optimal (many of the parts are provably optimal, the only thing not yet optimal is doing an entire tree search, which is likely computationally impossible due to required tree size), using quite a bit of computation, precomputation, caching, etc., for the searching. Oh, I also have a bot that solves Wordle in one move, every time. Hint: the source code for Wordle is viewable from the page, and is easy to use to predict the word for each day.... But I've said too much now :)
  - ghusbands 5y ago
    (Warning: To anyone who might follow the hint, maybe heed my warning in another comment on this HN page.) Yeah, it might be bit cheeky to have a bot that guesses one word, and then gives you the correct answer and the date on which Wordle used or will use it. Is the tree size still too big if you're only using Wordle's word list? (I'm almost interested enough to code something up, but asking you might mean I don't get fully nerd-sniped.)
    - ChrisLomont 5y ago
      >Is the tree size still too big if you're only using Wordle's word list? Yes, it's what I use. Wordle has ~2300 words as possible hidden words, ~12,000 more allowed as guesses. To get best scores you need to sample from all ~15k words. So, to build a tree: for each hidden word (2k), pick a guess word (15k), gain knowledge (729 possibilities, but only one per hidden/guess pair). This reduces your possible hidden list to 70-1kish. Repeat.. Worst tree is 5 levels deep, mine averages 3 levels deep, pruning and memoization is nearly nonexistant (I checked). You now have 30M first move outcome nodes, 2k of which are wins. After second move, you have a billion plus (I've sampled these to gain knowledge of what to expect). The next few rounds push the compute time into crazy realms of time (again, I've sampled to estimate sizes). I'd guess given a lot of computing power, it could be done, since around 3-4 levels most of the games complete. But since you cannot easily store this tree, I gave up for now. You should be able to store the tree with best move only at each node, which is good for gaming, but loses interest for statistical knowledge of the tree. Good luck :) Nerd sniping complete :)
andopp 5y ago
I think it's better to not repeat too much from previous guesses. I don't think my greedy algorithm is optimal, and also there are multiple ways to define "optimal". For instance, you might optimize average number of moves, or try to lower the upper bound for all possible words.
- andopp 5y ago
  Oh I misunderstood the comment I was replying to. Sometimes it is better to repeat letters, because it's a balance between discovering letters and figuring out the order.

Dwolb 5y ago

How are you calculating “biggest reduction in size of candidate pool”? Wondering if you’re trying to split the pool 50-50 or more like 90-10.

jhgb 5y ago
It would seem to me that 50-50 would be the "biggest reduction" since presumably you're judging the pruning based on the worst case. In the latter case the worst case is that you're still left with 90 options. Maybe I'm looking at it too much as some kind of decision tree but it looks to me like one, or at least something very similar. You don't want any branch to be too long.
- deleted 5y ago
  [deleted]
- Dwolb 5y ago
  I think what we’re missing is information gained by understanding the letter location. So if S is in 90% of words, well you also reveal whether or not it’s in the nth location. Whereas an incorrect guess gives you no location information. So, you’d want to guess the word that equally splits the word pool given both the letter and letter location (or just letter in a given location).
andopp 5y ago
I try to cut it down to as small a set of candidates as possible. Any reason to think a different split is better?
- Dwolb 5y ago
  I was thinking that if you guess S correctly and it is in 90% of words and not in 10% of words, you’ve only removed 10% of words from the pool. Whereas if there were a letter closer to occurring in only 50% of the pool, you at least eliminate half. Does that logic make sense here or no? I’m thinking I’m missing something related to “maximum information gain”.

jhgb 5y ago

You have a list of legal words? Where is it available?

detaro 5y ago
in the source code of the site.
andopp 5y ago
There is also /usr/share/dict/words or https://github.com/dwyl/english-words https://github.com/dwyl/english-words which can be used.
- jhgb 5y ago
  I actually have several such lists already, but if the actual list of candidate words in this game is a subset of the ones I have, I imagine solution can be arrived at quicker by excluding guesses that couldn't possibly lead to the solution.
bfung 5y ago
Goto wordle, right click “view source”, click and view the “main.<hash>.js” file. Search a word from previous answers, there are 2 arrays that the game uses to check with. Copy those and that’s the dictionary. Spoiler alert: the first array is the answer array for even future wordles.
- jhgb 5y ago
  > Spoiler alert: the first array is the answer array for even future wordles. That's presumably the reason why I wouldn't want to view the source.
  - bfung 5y ago
    This lists are pretty big where if you were to copy and paste them real fast, your eyes would glaze over them enough to not know the answers... maybe just the next day ;)

loeg 5y ago

Mine does AESIR, DROPT, EVERY, then QUERY for Wordle 205. There are 3197 equally good guesses for the 3rd word (ABCEE / EVERY) on that puzzle, or 336 if you prioritize words on the answer list (which is why I land on EVERY instead of ABCEE).