Hangman

My new video on Hangman is out. You can watch it here. This post provides more detail on some things that I wasn’t able to fit into the video.

This video went very differently than I expected. Battleship and Yahtzee both deal with numbers of states that are at the edge of what a single computer can handle in a reasonable amount of time. Hangman is fundamentally a very similar game to Battleship in that one player chooses a state from a large state space, and then the other player has to narrow down that state via a series of guesses. The difference is that the state space in hangman is 6 orders of magnitude smaller than Battleship (almost 7 if you only count the words of a single length). This was supposed to be an easier video where I could focus a bit more on figuring out the production process, and take a step back from what seemed like a very long, 33-minute video on Yahtzee.

Hangman brings its own set of challenges, though. Being a “simpler” game just means that it’s possible to solve it more fully. While my Battleship video focused primarily on using a greedy guessing strategy, the smaller state space in hangman meant that it was essentially possible to solve the game under certain conditions. If you fix a distribution over all possible words that the chooser could use, then we can actually find an optimal strategy for most word lengths, and I probably could have gotten an optimal strategy for every word length if I had thrown just a bit more compute at the problem. Just as with Battleship, the goal was to find something close-ish to a Nash equilibrium, but hangman seemed approachable enough that we might actually be able to get pretty close.

The variation over different word lengths and the nature of the guesses also bring challenges that I didn’t really anticipate. Letters of the alphabet behave very differently than squares on a Battleship board, and patterns in how letters appear do change pretty substantially across different word lengths, mostly due to conjugations, prefixes, and suffixes. When I made my Yahtzee video, I was worried that I was sort of going overboard by talking about each of the 13 boxes on the scorecard. When that turned out not to bother people, I joked to myself that the only thing twice as good as talking in depth about 13 of something was talking in depth about the 26 letters of the alphabet. I ultimately realized, though, that I couldn’t really do justice to this game without some understanding of its basic building blocks.

The Words

There’s a sense in which a hangman strategy is only as good as its word list. In Battleship, the state space is massive, but at least the players agree on what it is. I’m sure I could have spent a lot more time refining the word list to get something much closer to a person’s vocabulary, and I’m sure there will be many changes to this list as I cover other word games (including in my next video. Stay tuned). It seems sort of funny that “phylogeny” ends up right above the cutoff for inclusion, while “cookout” is right below it, but there’s a surprisingly inconsistent relationship between a word’s frequency and our understanding of it (plus, it’s really hard to come up with a reliable word list).

I’m sure there are better ways to approximate a person’s vocabulary than “try to eyeball a cutoff and then have Claude apply a bunch of filters to the resulting list.” My hope was that the words that shouldn’t have been kept had similar letter patterns to the words that shouldn’t have been removed, resulting in similar hangman strategy to the “correct word list,” although I don’t know how true this is in practice.

I also put a lot of thought into how to think about word frequencies, but ultimately didn’t come up with much. Using a uniform frequency is almost certainly not a reasonable thing to do, but the natural alternative of just using words’ frequencies in English text also didn’t seem quite right, and it made the game a lot easier for the guesser. I suspect that the “right” weighting to simulate how people actually play hangman is somewhere in between: people try to pick weird words, but it’s just much easier to think of words that you know well, and you probably don’t want to pick a word that your opponent doesn’t know at all.

Guessing Strategy

After being stuck on the greedy strategy in the Battleship video, it was nice to be able to tackle a game where the full optimal strategy could be computed (even if it relies on assumptions about the distribution of words). Like Battleship, the objective of hangman is usually about maximizing information, but in both games, there is a strong incentive to prioritize “correctness” over just information. In Battleship, you’re rewarded for correct guesses: you need to get all 17 hits to win the game, so you’d usually rather guess a square with an 80% chance of being a hit over one with a 50% chance of being a hit, even though the latter would provide more information on average.

Hangman sort of has the reverse of that constraint. You’re penalized for misses, with the game ending after a fixed number of misses, so you again want to prioritize hits over information. On top of that, there are usually many ways for a letter to be in a word, but only one way for it not to be, so choosing the letter most likely to be in the word is usually the information-maximizing move anyway.

It’s not that surprising, then, that the greedy strategy is very close to optimal here. Jan Misali conjectured in his video that it was optimal, and one of the big takeaways from mine is that he was wrong in theory, but mostly correct in practice. There really isn’t that much more to be done beyond the greedy strategy.

Generating the Optimal Strategy

The video gives the backbone of the approach to the optimal strategy. You try to find the starting letter to optimize your chances of winning (or expected number of misses, depending on which part of the video we’re in), which requires you to expand the decision tree for each starting letter.

One thing worth noting, which I may not have made clear in the video, is that I occasionally went back and forth between “minimizing expected turns” and “maximizing the probability of winning the game.” For the usual game with 6 misses, the optimal strategy was found for every word length. Most of the video focused on minimizing expected turns, with the main exceptions being the 3-letter tree in the intro, and the graphs at the very end where we looked at the probabilities of winning with every number of misses.

Switching from minimizing turns to maximizing win probability doesn’t have a huge impact on strategy, but there are some noticeable changes. I becomes the top starting letter at length 7 and 8 (any length above 8 can always be solved in fewer than 6 misses). I’m assuming this is because of the same ING thing that dominates the choosing strategy at those lengths. ING words are the hardest words to distinguish between at those lengths, so the consequences of wasting an E on an ING word are greater than the consequences of wasting an I on a word that has an E in it. You’ll raise your expected misses by guessing the I, but you’ll help your chances in exactly the cases that are likely to cause you to lose (optimal win rates are 98% and 99.9% at those word lengths anyway).

The approach to the strategy itself was outlined very roughly in the video. For each starting letter, look at the possible scenarios you could reach after guessing that letter (either a miss, or some combination of blanks filled in). Then for each of those scenarios, look at the possible followup guesses, and their possible scenarios, and so on. We ultimately want to find the choice of letter that minimizes expected misses (or maximizes win probability), which we can get by recursively solving further and further down the game tree and then iterating back up.

This can quickly turn into a massive problem give the size of some of these trees. The depth of the tree peaks at length 3, and can reach 14 misses and a total of 17 guesses (the video had an example of a length 4 word that hit 14 misses with the greedy strategy, but I’m pretty sure that the optimal strategy does better on length 4 than length 3), while the number of words peaks at length 7. There are a few major optimizations to make:

1. The decision you make at any given step depends only on the possible words remaining at that step. If you solve for a given collection of words once, then you can just store the result and come back to it later, which helps a lot for many of the smaller cases that you encounter lower in the decision tree. An unfortunate side effect is that it improves speed at the cost of blowing up your RAM, which is hard to come by right now.

2. In many cases, you can guarantee that an option is going to be worse than the best strategy found so far at a given node without actually having to finish the computation. The fact that the greedy strategy is so close to optimal helps a lot with this. We can just start by checking the greedy guess at each node, and we often end up being able to eliminate most of the alternatives pretty quickly.

3. There’s no reason to guess a letter that can’t appear in the word given the blanks filled in so far, which narrows the search space a lot.

Near-Optimal Strategy

The main thing that made the optimal search work for the video, though, was that it was possible to find a sequence of estimates for the expected turns that converged to the true optimal value. The idea is this:

1. For some number alpha, we cap the number of misses at alpha. If we get any number of misses greater than alpha, we just count it as alpha.

2. We find the optimal strategy for minimizing the expected number of misses with this alpha cap. This provides a lower bound for the actual expected number of misses, since the actual optimal strategy could be improved or at least kept the same by imposing the alpha cap.

3. We can also use this to get an upper bound on the optimal number of expected misses by just using this capped optimal strategy until we get alpha misses, and then applying a greedy strategy after that point. The expected number of moves for any actual strategy is necessarily an upper bound for the optimum.

4. If we ever encounter an alpha where the optimal strategy with the alpha cap never exceeds alpha misses, then we know we have found the true optimal strategy.

This thankfully meant that even though I wasn’t able to find and prove optimal strategies for word lengths 3-6, I was able to get values with tight enough bounds to do everything else that was needed for the rest of the video.

The Tier List

When I computed the (near) optimal strategies, I was left with a decision tree for each length. This outlines a full set of strategies, but 1) the results are often not that intuitive, and 2) it’s fairly difficult to reduce these trees down to something that can reasonably be talked through in a video. In the Battleship video, I tried to focus on certain things like the initial sequence if you kept missing (and I did that for length 3 in the hangman video), but it seemed like it would get pretty repetitive if I tried to do something like that for every word length.

I had sort of joked to myself about jumping from talking about the 13 Yahtzee boxes to the 26 letters of the alphabet, but it ultimately seemed like the most intuitive way to break down the strategy. I could sprinkle in bits and pieces about what happens at each word length, while focusing on some core principles that were common across word lengths.

I spent some time early on trying to come up with ways to think about how letters were treated across all word lengths. I essentially settled on a way of comparing 2 letters. For every word, you can look at the sequence of guesses made by the optimal strategy until we get the word. Given two letters (which I guess we’ll call alpha and beta to avoid confusion?), look at how many words have alpha guessed before beta (if alpha is guessed and beta is not, this counts as alpha being guessed before beta). If alpha is usually guessed before beta, then alpha is in some sense a “higher priority” letter than beta.

You can then apply this sort of logic to sets of letters. Given a collection of letters, you can look at the number of times a letter from outside the collection is guessed before a letter inside the collection (more formally, the sum over all words of the number of (alpha, beta) pairs where alpha is in the set, beta is not in the set, and beta is guessed before alpha in that word’s guess sequence). Ideally, if we start with a set of “high tier” letters, then the number of these misordered pairs between the set and its complement should be low.

So the approach to the tier list was this: Start with an empty set. Then go through all letters not in the set (in this case, all of them), and try to add each one individually to the set. After each addition, look at the number of misordered pairs between the set and its complement. Whichever letter minimizes this number of misordered pairs gets added to the set. We repeat this process 26 times, and we keep track of the order in which the letters get added to the set. This order is essentially a ranking of how useful the letters are in hangman. In general, a higher ranked letter is usually guessed before any of the letters ranked below it. E gets added to the set first, then I, then A, and so on.

One thing I noticed is that sometimes, a letter is basically tied with the next best choice - there can be 2 or more letters that basically produce the same number of misordered pairs when they’re added to the set. In some cases, however, there is a clear winner, where one letter is the best choice by far. This is how I assigned the tiers. If one letter was a much better addition than the next, then I put a tier cutoff after that letter.

This provides a nice procedure for quickly generating a tier list given a strategy. If we changed the word frequencies, switched to British English, or used an improved choosing strategy, it was enough to just regenerate all of the decision trees for the new strategy, and then plug in those trees to generate a new tier list (although I don’t think the tier list does a good job of capturing the strategy against the improved choosing strategy). I’ll probably use a similar procedure for analyzing other word games going forward.

On Word Frequencies

While “choosing a word from the list at random” is nice from an analysis perspective, it doesn’t seem like a realistic way to make word choices. There sort of seem to be two competing effects here:

1. Players aren’t going to choose words that they don’t know or can’t think of, which biases the choice toward more common words.

2. Players probably will try harder to use more obscure words, partially to make it harder to guess, and partially just to make the game more interesting

I doubt that these effects cancel out completely. In particular, because there are relatively few common words and many rare ones, if there’s any reason to occasionally choose more common words, then each one will probably end up being more likely. In practice, this probably means that the “real” distribution of words chosen will be somewhere in between “every word equally likely” and “words chosen proportional to frequency.”

I stuck with the equal weighting partially because it made the results feel a bit more mathematically sound to me, and partially because applying almost any other weighting (unless it’s chosen very carefully. See below) will probably just make things easier for the guesser. Especially a weighting as biased as word frequency (each individual letter in the word “the” accounts for more than 1% of English text on its own) is likely to create exploitable patterns for the chooser.

I’m planning to cover other word games in the future, so I’d like to come up with more realistic versions of both the word list and the frequencies. Other considerations include things like:

1. Certain types of “more interesting” words are more likely to be chosen. Coming up with a reliable metric for how interesting a word is seems difficult, though.

2. I would expect plurals, conjugations, and suffixes to be a bit less common than the corresponding root words.

3. Depending on how much the chooser has thought about hangman, I would expect that more difficult words with rare letters or repeats would be more common.

I’m not sure how realistic any of these considerations actually are, but I’m sure that they would affect the frequencies at least some amount. Thankfully, while the guessing strategy sort of has to rely on some assumptions about the chooser, the chooser can assign whatever frequencies they want, and can do so in such a way so that the guesser’s strategy barely matters.

Word Choice Strategy

For the chooser, I again took a similar approach to my Battleship video: start with a uniform random distribution over all possible words, and then modify that distribution a bit at a time to make things harder for the guesser. While the guessing strategy from the first half of the video was based on an assumption about the specific distribution of words used by the chooser, the choosing strategy is constrained only by the wordlist itself.

The Improved Greedy Strategy

In trying to come up with a guessing strategy for the optimized chooser to compete against, I had to balance effectiveness with computational feasibility. Recomputing the optimal strategy every time wasn’t feasible (I wasn’t even able to compute it a single time for some word lengths), so I started to a similar approach to the Battleship video: just having the guesser use a greedy strategy.

The main problem with this is that it quickly became clear that the optimized choosing strategy was exploiting weird quirks about the greedy strategy, rather than developing a good, general strategy. Specifically, it was able to find cases where the most likely letter to appear in a word was actually a very suboptimal guess, so the chooser ended up with a strategy that could be exploited if the guesser switched from greedy to something better.

Instead, I chose something that was essentially a step toward optimal: Try every possible choice of first letter, and then use the greedy strategy for the rest of the game. Then choose the starting letter that minimizes the expected misses. This ensures that, at least for one turn, the guesser is actually making the right decision and not just the greedy one.

This choice of guessing strategy was part of the reason that we get that chart around the 35 minute mark in the video. The chooser is essentially optimizing for not allowing any starting letter to be particularly good. This leads to the common property of Nash equilibria where the opponent is indifferent to the top choices of strategies, because if one were better for them, then you could probably adjust your own strategy to make your opponent’s best option worse, and their second best option better.

In some sense, the surprising thing here is that “only” 16 letters ended up in a virtual tie as the best starter (other word lengths had slightly fewer starting letters that were close to the best). No amount of optimization could make the bottom tier letters as desirable as the top ones, because increasing their frequencies too much would end up restricting the entire word list to become more predictable.

The Optimization

My choice for the approach to the optimization was also supposed to be a balance between accuracy and feasibility. I decided to focus on patterns of a single letter: all possible outcomes that you could get when you guessed a single letter of a given length. Each word would be given a relative frequency that is a product of multipliers corresponding to these letter patterns. For example, BALLPARK would be a product of multipliers corresponding to B_______, _A___A__, __LL____, ____P___, ______R_, and _______K.

We iterate through every letter pattern, tweaking its multiplier to change the frequencies of all words containing that pattern. We then adjust the improved greedy strategy to account for the new frequencies. If we find a way to increase the expected misses for the guessing strategy, then we keep our changes to the frequencies. We then repeatedly iterate through every letter pattern, stopping once we have no way to increase the expected misses.

The thought behind this letter pattern system started with the fact that I wanted to weight individual letters. I figured that we would want to increase the frequencies of less common letters, and decrease the frequencies of common ones. I could have just applied multipliers for each letter in the word, rather than using this more complex blank pattern system, but the pattern system seemed to capture a few main things:

1. Repeated letters make words harder to guess. If we applied a multiplier for each distinct letter, then it would create a weird situation where a word with repeated rare letters would be given a lower frequency than a word with many different rare letters, even though the word with repeated rare letters would be harder to guess.

2. The patterns reflect the actual outcomes when a letter is guessed, so it might turn out that two patterns for the same letter give very different amounts of information to the guesser.

On the other end of the spectrum, I could have just tweaked the frequency of each word individually. At first, I avoided this just because of the increased computational power that it would take, but I ended up having enough time to try this approach. It turned out that it just didn’t work. It wasn’t able to find good strategies like the ING strategy for 7-letter words. Increasing the frequency of ____I__ results in increasing the frequency of every ING word, which makes guessing harder. But increasing the frequency of a single ING word doesn’t really do much.

I expect that there is probably a slightly better approach that makes use of more complicated relationships between letters (for example, I expect that increasing the frequencies of words with Q but no U would probably increase the average guesses), but I expect that the choosing strategies found by the optimizer are probably close to optimal in most cases.

The Guesser’s Response and “Fair” Hangman

The guesser’s response to the improved word choice strategy was somehow both more simple and more complicated than I was expecting. It was more complicated in that it seemed to be pretty hard to come up with anything that was worth explaining in a video. There were very few clear patterns to how letters should be guessed under this new system, and the patterns that did exist seemed to be very specific to certain word lengths. The tier list approach that worked earlier in the video didn’t really apply here.

But there was a sense in which the new guessing strategy was also surprisingly simple. In a lot of games, the Nash equilibrium strategy involves doing something that makes your opponent indifferent to any of the possible choices that they could make. And there was clearly some of this. The top 15 letters that the guesser could use as a first guess at length 7 were all in a virtual tie for the fewest expected misses. But it is also pretty interesting that there were only 15 letters involved in this tie, and that they were basically just the 15 most useful letters in the first place. The fact that there is nothing we can do within the constraints of our dictionary to make the lower tier letters as useful actually says a lot about the language.

You could imagine an (incorrect) model of the English language where, say, for everywhere we see an S, there is some chance that there’s some other, less common word out there that uses a Z in its place. If this were the case, then it should be possible to tweak the frequencies of S and Z words to make them equally useful in hangman.

But the fact that things don’t work that way lead to a conclusion that is both completely obvious and somehow a bit profound (or at least seems profound as I write this post at 2 AM the night before releasing the video): different letters have different structural purposes within the English language. Z just can’t do the things that S, or N, or even P can do. The only way to make Z common enough to be worth guessing in hangman is to completely restructure all word frequencies so much that “Z words” move to the forefront, and “Z words” are so rare and so different from the rest of the language that it makes it easier to guess the rest of the word once you know it’s more likely to have a Z in it.

The “Fair” Number of Misses

After getting the adjusted word choice strategy and the corresponding near-optimal guessing strategy, we can figure out how long the game “should” take under near-perfect play. Here, I set the guesser’s strategy to maximize the chances of winning for each possible number of misses, rather than minimizing the expected misses. We only actually care about the number of misses where this probability is close to 50%, and while I wasn’t able to compute the optimal strategy for every number of misses, I was able to get the optimal strategy computed for the numbers of misses that mattered here.

Funnily enough, we get that the ideal number of misses covers every number from 1 to 8 except for 6. Granted, this only applies if both players are using an optimal strategy (I’m assuming that the guesser using an actual randomized optimal strategy won’t significantly change the chances of winning). For actual human play, I don’t have a great sense of which side would have the advantage.

My guess would be that the chooser would have an easier time playing closer to optimal. Most of their strategy can be covered by “play fewer common letters” at shorter word lengths, and “end your words with -s/-y at length 5, -ed/-er/-es/-ing at length 6, -ing at length 7/8,” while the chooser would have to have a pretty solid knowledge of words of various lengths, far beyond what you could get from just memorizing my tier list.

For humans playing at a typical, non-optimized level, I suspect that the advantage would still go to the chooser. It’s far easier to come up with a single word with weird letters than it is to narrow down which of those weird words might have been used.

Conclusion

Hangman was supposed to be a short video to slow things down, focus on other parts of the process, and prepare for my next video on Wordle. It didn’t occur to me how many interesting things would come up when doing this, but it makes me even more excited for the Wordle video, where the primary focus on length-5 words will hopefully make it easier to narrow in on some specific topics.