Hacker News Reader

Comment by andopp | Hacker News Reader

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

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.

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.

Reply on news.ycombinator.com