Thursday, January 15, 2015

Hangman Challenge - Answer Revealed


I've enjoyed playing Hangman with all of the readers who took me up on the challenge. Without further ado, the winners of the 2014/2015 Hangman Challenge are...

My two daughters, ages 5 and 7! Playing as a team, they guessed the mystery word, WILL, with only 7 misses. Reader Cristian won in the grownups category with 9 misses.

***

How did I choose the word WILL in the first place? What sorts of words are difficult to guess quickly in Hangman?

One principle to consider is that a guesser will often make rapid progress once the first letter has been identified. One way to delay that event is to use a four-letter word. Short words offer few targets for the guesser to hit by chance.

For longer words, repeated letters can be valuable because they keep the number of distinct targets small. However, this is a high risk / high return strategy, and a poorly chosen repeated letter reveals far too much (as in C?CC??, for example).

In general, uncommon letters are hard on the guesser. However, an opponent who knows what you're up to could guess uncommon letters with somewhat higher frequency than their dictionary frequency. (Many of the readers who responded to the Hangman Challenge seemed to be playing along these lines—choosing Y as their first vowel, for example, which they probably don't do when playing Hangman against their niece or nephew.)

Common letters should appear in positions where they reveal little. For example, S at the end of a word gives the guesser less information than in other positions, because S occurs at the end of so many words. (The guesser does learn that the resulting (n−1)-letter word has no S.)

Another strategy is to come up with a word that has the property that even after all of the common letters have been guessed, and there's just one letter left to go, there are still enough possibilities to make life difficult for the guesser. For example, ?ARE could be any of 12 different possibilities (BARE, CARE, DARE, FARE, GARE, HARE, MARE, PARE, RARE, TARE, WARE, or YARE).

I used some of these principles to come up with my Hangman challenge word. A computer program that I wrote to play Hangman racked up 17 misses along the way to guessing WILL. That score was also about average for the adults who played the game. (Not sure what algorithm my kids were running....)

For a slightly longer word, one might use something like WILLET. This word uses relatively uncommon letters, although the letters aren't so uncommon as to be exotic (meaning that they aren't too tempting for an iconoclastic guesser, and they aren't too informative once they appear). The one common vowel, E, is in a pretty uninformative place. There's a double letter, too.

Presumably it pays to use a word outside your opponent's vocabulary. For this reason one might prefer WILLET to WILLED, although it might be a close call because of the letter frequencies (T more common than D). For what it's worth, my computer program solves WILLET one step faster than it solves WILLED; then again, its vocabulary is much better than any single person's.

Of course, if you apply all of these strategies as ruthlessly as possible, then people might not want to play with you!

***

Surprisingly, a quick online search turned up no definitive articles about the game theory of Hangman. All I found was some blog posts and forum discussions, the most interesting of which were these two:

"A Better Strategy for Hangman" at www.datagenetics.com

"25 Best Hangman Words" at www.wolfram.com

Thanks again to all who played the Hangman Challenge!

P.S. Congrats as well to reader Jeff, who correctly solved the Change for a Dollar puzzle!

No comments: