Suboptimal Hangman Strategy

How do you play Hangman? I mean, assuming you do play Hangman. The answer is “probably suboptimally,” and a recent lifehacker (ugh) blog post describes A Better Strategy for Hangman, a strategy which uses suitable letter statistics and conditional probabilities.

The basic idea is to constrain the space of possible words by using an accurate tabulation of letter frequencies (based on any number of occurrences in single words, not texts) to pick the most probable letter at any given step. When you don’t have any letters, this is just the most probable letter given the length of the word in question. Once you’ve chosen a letter, if it’s not in the word, this further reduces the space of possible words, which is to say that it affects which letter will be most probable in the next step. There’s a table near the end of the linked post giving the “optimal calling order” for words of length 1-20.

While this is almost certainly better than what I imagine is the typical Hangman strategy, it is, at best, incomplete. And I’m skeptical that it’s anything like optimal.

It’s incomplete because it only gives “optimal” choices when you learn that a previous choice is not in the target word. But having a letter get rejected isn’t the only way to constrain the space of possibilities. Indeed, the whole point of optimizing your letter choices is to constrain the space of possibilities all the way down to the one correct possibility. Of course, it would take a good bit more than a blog post to work out the optimal calling order for every possible accepted letter, so I can hardly blame the writer of the post for not doing so.

But there are other, more interesting reasons that the given strategy is suboptimal, even if it had included the whole gamut of conditional probabilities based on sequences of correct and incorrect guesses. First, the letter with the highest conditional probability, by definition, reduces the space of possible words less than any less probable letter. It’s just restating the formula for calculating the probabilities, but a letter is most probable in a given situation precisely when it occurs in the largest number of words.

So, sure, choosing the most probable letter increases your chances of getting a letter right, and constraining the word space by choosing correct letters is certainly better than doing so by choosing incorrect letters – you don’t get hangman bits drawn and it’s likely much easier to navigate the reduced word space that you know has to have certain letters in certain locations than it is the reduced word space that you know doesn’t have certain letters at all.

Which brings me to the other reason that basing your choices on even carefully calculated orthographic numbers is likely to be suboptimal. When we think of words, we don’t think of them only in terms of letters (or, if we’re illiterate, we don’t use letters at all, but then, if we’re illiterate, we’re very unlikely to be playing Hangman, so…). Okay, sorry, the point is that we think of words in terms of phonemes, too, and the mapping between (sequences of) letters and phonemes in English isn’t always straightforward.

And it’s not just that we think of words in terms of phonemes, but that when we search our mental lexicon, different parts of words seem to matter more than others and different types of phonemes are more helpful than others in constraining the reduced search space. For example, it’s much easier to bring to mind the set of words that begin with ‘p’ than the set of words with ‘p’ as the third letter.

And vowels seem to constrain lexical access more weakly than do consonants. Here’s a (pdf) of a psycholinguistics paper in which speakers of Spanish and Dutch were asked to change non-words into real words by changing only a single sound. Speakers were faster and more accurate when changing a vowel rather than a consonant, and, when given the choice, changed vowels more often than they did consonants.

Why is this relevant to Hangman? If you choose a vowel – as is allegedly optimal in almost every situation – it will be easier to think of more (mostly incorrect) words than it will be if you choose a consonant. When you choose vowels, there is less functional reduction in the search space than when you choose consonants.

I’m not going to do the work to figure out the true optimal strategy (or even a better strategy than the lifehacker one, at least not in any more detail than I’ve already given), but my guess is that picking consonants with middle-to-high probabilities, and maybe taking word position into account when crunching your numbers, will give you a leg up on even the purely likelihood based approach.

(HT: Andrew Gelman)


This entry was posted in language, SCIENCE!. Bookmark the permalink.

Comments are closed.