Solving (German) Hangman with Letter Frequencies

This project is heavily inspired by this video by Ballpark Figures. All code used for this project is available on Github

Hangman Rules

Hangman is a two player game, where one player is the Game master, deciding on a secret word (in my case a noun in German). The other player tries to guess this word by asking for individual letters. If the secret word contains that letter, the Game master reveals all positions, where that letter is at. If it doesn’t, the player loses a life. Figuratively, one body part is added to a stick figure hanging from the gallows. The guessing player knows the number of letters in the secret word. In the following, I will assume the guessing player has perfect knowledge of the wordset and the choosing player randomly selects a word from it.

I settled on hangman with 6 lives (Head, Body and 4 limbs) and set umlauts (Ä, Ö, Ü) and the ‘sharp S’ (ß) as separate characters.

Taumata­whakatangihanga­koauau­o­tamatea­turi­pukaka­piki­maunga­horo­nuku­pokai­whenua­ki­tana­tahu

Taumata­whakatangihanga­koauau­o­tamatea­turi­pukaka­piki­maunga­horo­nuku­pokai­whenua­ki­tana­tahu is the longest word in my Wordlist. It has $85$ letters and apparently is the name of a hill in New Zealand. Note that in German, you can infinitely chain nouns together. German-Nouns only selects words that were mentioned in German Wikipedia. Since the guessing player knows the number of letters at the start of the game, we can treat every word length as its own separate problem.

Each different guess can have a maximum of $2^{n}$ different outcomes, where $n$ is the number of unknown positions in the word.

The Frequency tactic

The first real tactic that comes to mind is picking the most frequent letters in order. It is flawed, because it completely disregards existing information the guessing player has: Letter count of the word, Existing successful guesses and his knowledge about the German language.

This naive tactic yields a winrate of about $9.0\%$ with an average number of $10.73$ misses per word. We are already significantly better than just choosing letters in alphabetical order, where we get a winrate of $0.2\%$ with $13.89$ avg misses per word. Note that the miss counts come from letting every game run to the end of the alphabet instead of stopping at the sixth wrong guess. That is why they are so far above the 6 lives an actual game gives you.

The greedy Strategy

At every game step, we can perform a letter frequency analysis on the remaining word options and select the most frequent letter and thus make the optimal greedy choice. I will call this strategy Letter Counting from here on. This of course assumes perfect knowledge of the choosing player’s wordset. After running for about 10 minutes on 500 samples per wordlength, this achieved a $97.2\%$ winrate with $1.21$ average misses. We mainly fail on short, unconventional words. Some examples for len 3-8:

Len 3: 'gäa' in 8 guesses (6 wrong: eoinbd, 6 to finish)
Len 3: 'sou' in 8 guesses (6 wrong: aebndg, 7 to finish)
Len 3: 'rtl' in 6 guesses (6 wrong: aeouid, 7 to finish)
Len 3: 'ivf' in 7 guesses (6 wrong: aeouhl, 8 to finish)
Len 3: 'ria' in 8 guesses (6 wrong: eocdfm, 7 to finish)
Len 4: 'tipp' in 8 guesses (6 wrong: aeonkl, 7 to finish)
Len 4: 'crow' in 8 guesses (6 wrong: aelgbf, 6 to finish)
Len 4: 'smog' in 8 guesses (6 wrong: aelrnh, 6 to finish)
Len 4: 'chef' in 7 guesses (6 wrong: aiorln, 6 to finish)
Len 4: 'zaya' in 7 guesses (6 wrong: mrgnpv, 7 to finish)
Len 5: 'füdle' in 9 guesses (6 wrong: aiuoth, 6 to finish)
Len 5: 'wippe' in 8 guesses (6 wrong: anlktr, 8 to finish)
Len 5: 'ziege' in 9 guesses (6 wrong: smflrw, 6 to finish)
Len 5: 'haxen' in 10 guesses (6 wrong: rlmgbf, 7 to finish)
Len 5: 'debüt' in 8 guesses (6 wrong: aiourh, 6 to finish)
Len 6: 'tauber' in 9 guesses (6 wrong: lnskgp, 6 to finish)
Len 6: 'medium' in 7 guesses (6 wrong: nrlstg, 6 to finish)
Len 6: 'fasson' in 9 guesses (6 wrong: eirkmb, 6 to finish)
Len 6: 'schulz' in 11 guesses (6 wrong: eaiotd, 7 to finish)
Len 6: 'zörbig' in 7 guesses (6 wrong: eansou, 6 to finish)
Len 7: 'dämlack' in 7 guesses (6 wrong: eonhru, 7 to finish)
Len 7: 'curling' in 10 guesses (6 wrong: eathbm, 6 to finish)
Len 7: 'bexbach' in 7 guesses (6 wrong: nrslti, 6 to finish)
Len 7: 'fußfall' in 8 guesses (6 wrong: eonhrb, 6 to finish)
Len 7: 'gezücht' in 11 guesses (6 wrong: nrslim, 6 to finish)
Len 8: 'luftkuss' in 7 guesses (6 wrong: eaoicn, 6 to finish)

Note that the first guess can be different depending on lengths, because each len has a unique letter distribution

These words are pretty unsurprising. Due to the lower letter count, we have much less information that narrows down the candidate count. There also is a lower probability the letter appears in the guessed word, just because it is shorter. Thus, we can generally expect worse performance on shorter words.

Letter distributions

It’s actually pretty interesting, how the letter distribution of the words Letter Counting loses on differs from the wordset as a whole:

We see, that unpopular letters such as j, ß or x are much more popular in difficult words, confirming my theory. By looking at the outliers, we can conclude, that the choosing player should generally choose words with a, u, k and specifically p and z more, and n,r and s less often.

Conclusion

We can see, that for long words, the game is pretty much trivial. To ensure a fair (and fun) game assuming perfect play, I suggest a system of dynamic lives according to this table:

Every colour in those hangmen is one life. As the count drops, parts get merged into a single stroke: both legs at once, then both arms, until for 9+ letters we just draw a head. Hangmen drawn in Excalidraw btw

What now?

A list of possible research questions for the future:

• You could further investigate the frequency differences to English (or other languages) and do a frequency analysis on specific wordlengths.
• You could also develop a system for humans to implement the greedy strategy as best as they can.
• The dataset doesn't consider arbitrary composite nouns
• What would happen if the guessing player didn't know the letter count?

Seriously try playing it this way! It actually is really fun. Thanks for reading this post, it took a lot of effort. :)