andopp

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.

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.

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.

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.

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

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.

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

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.