You make a good point, and I made the following change to the my program:

# Find how close each letter is to half of the total word possibilitie
+s to ensure maximum gain every guess after being sorted
foreach my $occur (keys %alphabet) {
    $alphabet{$occur} = abs($#narrowed/2 - abs($alphabet{$occur} - $#n
+arrowed + 1));
}

say $_ foreach @narrowed; # Word list
say $#narrowed + 1;
say sort { $alphabet{$a} <=> $alphabet{$b} } keys %alphabet; # Sort as
+cendingly; whichever letter is closest to 0, i.e., and therefore whic
+hever letter will eliminate the most words.
[download]

However, as I play, I notice that although it does eliminate a lot of words very quickly, when it gets to a low amount of words, it becomes useless, telling me to guess letters that are not in any of the words, and telling me to guess letters that are in all of the words last.

Surely, when it comes to this point, the user can easily guess on his own but that is not really the point. I want the program to be able to find the individual word in a small amount of guesses. Perhaps I should use your method when there are more than, say, 10 possibilities, and mine from there on out.

Example illustrating my point:

I am kind of speaking to myself here, so this node is just publishing my own mental thoughts. Feel free to comment or object them.

it becomes useless, telling me to guess letters that are not in any of the words

That would indicate a bug in the implementation, not a problem in the approach as you claim.

Those were my thoughts too. However, if the user picked an extremely common word, with common letters (which makes it a common word), then shaving off 50% each time is more helpful than eliminating the 10% that don't have the recommended, most common letter.

Of course this is all theoretical and should be tested before changes are made (which I failed to do initially).

I don't mind occasionally having to reinvent a wheel; I don't even mind using someone's reinvented wheel occasionally. But it helps a lot if it is symmetric, contains no fewer than ten sides, and has the axle centered. I do tire of trapezoidal wheels with offset axles. --Joseph Newcomer

Lawliet,
then shaving off 50% each time is more helpful than eliminating the 10% that don't have the recommended, most common letter

That's not the way it works. At least not how I understand the game. So let's say you have a really common word with common letters and you pick the most common letter amongst the possible candidates. If you pick a letter that is correct, you gain new information (the position of that letter) and you don't get penalized for a wrong guess. As long as you keep guessing correct letters you can go on forever. Additionally, you still prune your candidate list because even though lots of words have the same letter - they don't all have them in the same position. If the letter is wrong, well then you purge the majority of the words in your candidate list.

You haven't convinced me approach isn't superior to the binary search of blokhead's. It can easily be tested - just modify the code for each algorithm to output "win <total_guesses> <wrong_guesses>" or "lose" rather than the verbose output. Then write a wrapper script that tests both algorithms against 10_000 randomly selected words. You can then gather statistics on which algorithm produced the most wins and for the wins, the average number of guesses required and the average number of wrong guesses used. Oh, and they should both "lose" after the same number of wrong guesses - my code defaults to 7 but is configurable.

Cheers - L~R

Your strategy is effectively a binary search. Assuming a perfect distribution (it is always possible to find a letter that is in exactly half of the remaining words), you should be able to guess (on average) up to twice as many times as you are allowed wrong guesses before losing the game. Of course, the last guess still has a 50% chance of being wrong so I believe your strategy is guaranteed to work when the total number of initial candidates is 2^^{(2G - 1)} or less, where G represents the number of allowed wrong guesses. For instance, when G = 7 then you are guaranteed (100%) to win when the initial number of candidates is 8192 or less and 50% when it is up to 16,384. For eclectic, there are 9638 initial words in my word list so only a 50% chance of success.

My strategy is optimized not to guess wrong. After only 5 guesses (2 right and 3 wrong) it had narrowed the search space down to exactly 1 word. This is because I prune by position not just by presence of letter so even successful guesses on a popular letter can still effectively decrease the search space. Your approach would be improved with this strategy as well. I don't think the opportunities stop there.

In a private /msg with Lawliet the idea of finding the solution with the least number of guesses was proposed. I indicated that my strategy would change - but to what? A binary search is already optimal. There needs to be some balance then between improving your odds from 50/50 of guessing wrong while still effectively reducing your search space each time. This way you can survive long enough to win but not guess ad nauseum.

I am kicking around some ideas where you still look for a very popular letter (say in 70% of the remaining words) but by position would still split that 70% in half if you guessed right. The result then would be that you would guess wrong 30% of the time and remove 70% of your search space or guess right 70% of the time but reduce your search space by 65%. Does this sound viable to you?

That makes sense. I hadn't considered also taking into account the positions of the letters when you guess a correct letter. So in my example, when the word has a Q, and you guess U, you can still potentially get some useful information if many of the candidate words have U appearing in different places (i.e., you could distinguish QUEUE from QUEST). In this case, it would be "best" (if minimizing total # of guesses) to try to choose a letter whose absence / presence at all positions will partition the candidates into a large number of sets, each with size as small as possible.

Update: expanding with an example: Suppose the word to be guessed matches S T _ _ _. Then suppose we are considering E for our next guess. All of the candidate words will then fall into one of these 8 classifications:

S T _ _ _ (no E in the word)
S T _ _ E (E in last position ONLY)
S T _ E _ (etc..)
S T _ E E
S T E _ _
S T E _ E
S T E E _
S T E E E
[download]

So we have 8 buckets, and we put all of the candidate words into the appropriate bucket. Suppose the bucket with most words has n words in it. Then in the worst case, after guessing E, we will have n remaining candidates. So you can take n to be the worst-case score of guessing E. Now compute this score for every letter, and take the letter with lowest score.

Note that there might be other ways to score each possible next-letter guess. Number of non-empty buckets comes to mind as an "average case" measure (to be maximized). Again, this is all assuming we're minimizing the total number of guesses. That way, all of the possible outcomes are (i.e., the guessed letter appears or doesn't appear in the word) are treated the same. To minimize the number of wrong guesses, you have to treat the "doesn't appear in the word" outcome differently and weight things in some better way.

blokhead

That actually means that the hardest hangman games are where you have to guess short words. Given that /usr/share/dict/words has 23 three letter words ending in at (only "aat", "iat" and "uat" are missing) only luck determines whether you "win" guessing a word like "mat", "cat" or "hat".