Comments

You must log in or register to comment.

houstoncouchguy t1_irhh35o wrote

No. There are times in hangman that you may only win based on luck. You get 7 chances before you lose.

In order, the most popular letters in the English language are:

> E, T, A, O, I, N, S, R, H, D, L, U, C, M, F, Y, W, G, P, B, V, K, X, Q, J, Z

With the word ‘Jazz’:

You may start with E and T before you fill in the A spot, and lose 2 guesses.

The next step with 4 letter words where A is the second letter could be B, C, D, E, F, G, H, I, J, K, L, M, O, P, R, S, T, V, W, or Y.

Even if you managed to get JA_ _, the remaining words with completely non-overlapping letters include:

Jack, Jagg, Jail, Jamb, Jaws, Jaup, and Jato. Which is enough variance to ensure that the results are not deterministic.

16

Abdiel_Kavash t1_irj7klm wrote

Just a minor note, in your example, JATO is not a valid result, because you had already eliminated T.

Even so, why should choosing the "most popular" letter be the optimal strategy? Letter frequencies (Etaoin Shrdlu) are based on a corpus of English texts. Naturally the distribution of words in these texts is not uniform. The reason "E" and "T" are so high is partly because they occur in the word "The". If the game is selecting words uniformly at random from a dictionary, surely the frequency distribution of letters is going to be dramatically different.

I would imagine that an optimal strategy would involve building some decision tree over the set of all n-letter words in a dictionary, in a way that you eliminate as many different words as possible with each failed guess. Quick googling told me there are about 20,000 six-letter and 35,000 seven-letter words in English (the number of 4- and 5-letter words is much smaller). If we can get even 2 bits of information out of every guess on average, we should be able to uniquely determine the hidden word.

12

houstoncouchguy t1_irjaz07 wrote

Good analysis.

I would rebut that I pulled the information from a list of English words, and not the frequency of use in sentences. But that’s really just a side note. Removing ‘jato’ would not be necessary to remove the assured victory if you have one less guess, having already eliminated it before.

The real meat of it is showing that there are at least 8 words that could be chosen that have distinct letters which can not be differentiated using process of elimination alone, even if you have 2 of the 4 bits of information already available at your disposal.

It may or may not become more difficult with longer words. And I’m sure there are much more technical ways to break down the necessary burn-letters. But I feel that the 8-word answer is sufficient to answer the question.

2

imtoooldforreddit t1_irhm5il wrote

Solving doesn't mean a forced win for the guesser though. Just means optimal strategies are known

3

DerpSouls t1_iriu9jl wrote

Doesn't solved game mean that the game's result is known, many steps early, assuming optimal play?

While the solution is obtainable the outcome of the game is still unknown even with 'perfect' play in this case

9

[deleted] t1_irhn138 wrote

[removed]

2

imtoooldforreddit t1_irhnqf1 wrote

Not quite, solved just means ideas strategy is known. If it's not a perfect information game, then you won't really be able to predict it like you describe

3

[deleted] t1_irhud7f wrote

[deleted]

3

houstoncouchguy t1_iricw3n wrote

The concept of a “solved” game assumes that the game can be performed perfectly. So if there is ever a starting point where the final outcome left to chance, it’s not quite a solved game.

In the example above, the starting words Jazz, Jack, Jagg, Jail, Jamb, Jaws, Jaup, and Jato all lead to a discreet set of guesses that could lead to failure.

4

Lornedon t1_irscjei wrote

I did a brute-force search on all two-letter words allowed by the scrabble rules, and there's no strategy that can win with every word if 7 errors are allowed.
That's probably not really relevant as no one would allow two letter words in hangman.

But I also ran my algorithm on 15-letter words, and there, winning is possible every time with a maximum of two mistakes!

In the more common word lengths, such a search quickly becomes impracticable, because there are just way too many words.

1