Hacker News Reader

Comment by Dwolb | Hacker News Reader

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.

Reply on news.ycombinator.com