Hacker News Reader

Comment by andopp | Hacker News Reader

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 A bit obfuscated by some necessary optimziations.

View on HN

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

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.

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.

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

I try to cut it down to as small a set of candidates as possible. Any reason to think a different split is better?

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

Imagine you have made a few guesses already. Then you have a set of candidate solutions; words that are compatible with the responses you’ve gotten from the game so far. The question then is, what word from the list of legal words should you now pick that no matter what the solution is, will ensure that that your candidate set becomes as small as possible based on the response you would receive? So basically, you have to compute, for each pair of candidate solution and legal word, the number of other candidate solutions that would yield the same response for that legal word.

But what do you consider to be “as small as possible”? Is 50% the minimum?

Say you have a 10 000 word list. In the beginning all those are candidates. Picking for instance SMOKE might give you a response that is only compatible with 1 000 words. You won’t know that before you guess it. But you can check, for any possible solution, what is the worst case scenario for SMOKE? Perhaps some solution would leave you with 1 500 possible words. Maybe FIRE as a guess would instead leave us with less than 1 000 words no matter what the solution is. Then that’s a better guess. So we pick the word that gives the lowest worst case remaining words.

A guess that eliminates 90% of possibilities is actually going to only eliminate 10% of the possibilities 90% of the time.

Trying to come up with a word that splits the list in half is actually ideal.

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

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.

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.

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

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.

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 :)

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

>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 :)

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.

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.

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

in the source code of the site.

There is also /usr/share/dict/words or https://github.com/dwyl/english-words which can be used.

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.

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.

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

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 ;)

Reply on news.ycombinator.com