## Fallout 4 Math, Part 2

This post is the second part in a series. If you haven't ready the first part, I'd highly encourage you to do so.

Last time, we discussed four different strategies for cracking the Fallout 4 hacking mini-game. As you may recall, our four strategies are as follows:

1. Guess randomly.
2. Guess the word which is closest to the others, according to the Hamming distance.
3. Guess the word that is farthest from the others.
4. Guess the word which will result in the highest expected number of word eliminations from the list.

We also looked at an example for which these different strategies yielded different guesses. So, if these strategies really are so different, which one should we choose?

Let's answer this question experimentally. There are a couple of different metrics we could use to determine the "best" strategy. One way would be to calculate what percentage of the time each strategy is able to identify the password in four guesses or fewer (remember, in Fallout 4, you only have four guesses before the terminal locks up). Alternatively, you could ask what the expected number of guesses is for each strategy. We've got time: let's do both!

In order to test these strategies, we also need a list of words to apply the strategy to. Let's start by using the three lists from the mini-game featured in the previous post (these word lists all come from Fallout 4). Here they are:

List 1: 'agent', 'fence', 'forth', 'start', 'shape', 'grass', 'parts', 'fists', 'sound', 'sewer', 'viral', 'piled'

List 2: 'energy', 'mutter', 'warned', 'atrium', 'second', 'carved', 'forced', 'hungry', 'depend', 'heated', 'mirror', 'stream'

List 3: 'varying', 'cistern', 'expects', 'attends', 'bottles', 'torches', 'limited', 'corners', 'fortify', 'despite', 'session', 'durable'

Here's some data on how each strategy performs with respect to each of these lists. For the random guessing strategy, we simulated 100,000 playthroughs of the game for each possible password, or 1.2 million playthroughs in all. The other strategies are completely deterministic, so you only need to play the game once for each password to know how many guesses you'd need to make.

Strategy Random Guess Closest Word Farthest Word Most Expected Eliminations
List 1 Avg. Guesses: 3.06 Avg. Guesses: 2.92 Avg. Guesses: 3.50 Avg. Guesses: 2.75
Win %: 92.79% Win %: 91.67% Win %: 75.00% Win %: 100%
List 2 Avg. Guesses: 2.83 Avg. Guesses: 2.58 Avg. Guesses: 3.25 Avg. Guesses: 2.58
Win %: 96.21% Win %: 100% Win %: 83.33% Win %: 100%
List 3 Avg. Guesses: 2.78 Avg. Guesses: 2.58 Avg. Guesses: 3.08 Avg. Guesses: 2.58
Win %: 97.93% Win %: 100% Win %: 91.67% Win %: 100%

Based on this data, it's clear that selecting the farthest word is your worst option. Guessing randomly does surprisingly well in terms of win percentage, though the average number of guesses you'll need is higher than with the closest word or most expected elimination strategies. And the only strategy to guarantee a win 100% of the time is most expected elimination. So is this the one strategy to rule them all?

Before we declare a winner, it's probably worth looking at some other sets of words. After all, the word lists in Fallout 4 are probably deliberately chosen so that there's a relatively high degree of likeness between words in the list. After all, if every word had a likeness of 0 compared to every other word, all you could do to try and guess the password is blindly guess. If all the likeness scores are 0, the likeness score effectively tells you nothing.

So let's look at some lists of randomly generated words. Online, it's not too hard to find lists of words of a certain length. So, I had my computer quickly whip up 10,000 word lists of twelve words each. I did this three times: once for five-letter words, again for six-letter words, and finally for seven-letter words.

Here are the results (note that this time I only ran 1,000 playthroughs for the random stragety, not 100,000, since I had to do 1,000 playthroughs across 30,000 different word lists):

Strategy Random Guess Closest Word Farthest Word Most Expected Eliminations
5 Letters Avg. Guesses: 3.19 Avg. Guesses: 2.88 Avg. Guesses: 3.82 Avg. Guesses: 2.83
Win %: 85.92% Win %: 96.04% Win %: 64.19% Win %: 97.50%
6 Letters Avg. Guesses: 3.06 Avg. Guesses: 2.80 Avg. Guesses: 3.60 Avg. Guesses: 2.73
Win %: 90.64% Win %: 97.42% Win %: 71.31% Win %: 98.94%
7 Letters Avg. Guesses: 2.96 Avg. Guesses: 2.73 Avg. Guesses: 3.43 Avg. Guesses: 2.65
Win %: 93.67% Win %: 98.18% Win %: 77.77% Win %: 99.57%

Here are a few observations:

1. The farthest string stragegy is the poorest performer by far, both in terms of the average number of guesses needed to get the right answer, and in terms of the win percentages.
2. Guessing the word with the highest number of expected eliminations is still the best strategy, but simply selecting the closest word in the word list is fairly comparable. Both are better than guessing randomly.
3. No matter the strategy, metrics improve as the number of letters per word increases. Why do you think this might be?

Finally, let's take things one step further: what if we played this game by selecting not just 5-letter words at random, but any list of twelve 5-character strings? In this case, zfwef would be a perfectly suitable candidate, as would aaaaa.

To test this scenario, I generated 10,000 lists of twelve five-character strings, then did the same for six- and seven-character strings. Here are the results:

Strategy Random Guess Closest Word Farthest Word Most Expected Eliminations
5 Letters Avg. Guesses: 3.79 Avg. Guesses: 3.26 Avg. Guesses: 4.65 Avg. Guesses: 3.25
Win %: 66.75% Win %: 84.60% Win %: 46.59% Win %: 85.26%
6 Letters Avg. Guesses: 3.63 Avg. Guesses: 3.16 Avg. Guesses: 4.40 Avg. Guesses: 3.15
Win %: 71.13% Win %: 87.72% Win %: 50.87% Win %: 88.52%
7 Letters Avg. Guesses: 3.50 Avg. Guesses: 3.08 Avg. Guesses: 4.19 Avg. Guesses: 3.06
Win %: 74.97% Win %: 90.36% Win %: 54.94% Win %: 91.32%

Many of our previous observations still apply. All strategies perform worse when any random string of characters will suffice, probably because you're less likely to get strings with many characters in common. The farthest string strategy is still the worst, but the random guess strategy takes a fairly significant hit as well. The two remaining strategies are both strong contenders, but going by the maximum expected number of eliminations still seems to be the best bet.

Of course, if one wanted to, there's still plenty more to dig into here. Can you think of any other strategies? What if you allow for word lists that are longer than 12? What if you look at words of lengths less than 5 or greater than 7? What if you allow for word lists that contain words of varying lengths? How do you calculate distances in this case? (Here's a hint.)

And lest you think all of this work has no application outside the realm of Fallout, the idea of measuring distance between two pieces of text extends far beyond this one example. Indeed, with slightly more sophisticated notions of distance than we've discussed here, there are applications in biology and very common examples in computer science, too. Any time you've used a spellchecker, or Google has corrected a typo for you, you can bet that under the hood there are some distance calculations being performed on strings of text.

Mastermind, the original game which shares many similarities to Fallout's terminal hacking, also has an interesting academic history. Details are beyond the scope of this conversation, but if you want to know more, Wikipedia offers a good starting point.

In conclusion: even if you dislike Fallout (or video games in general), let it never be said that rich and interesting mathematics couldn't be found therein.

(Bonus: if you'd like to play around with some of the statistics on your own, I've thrown together a little command-line tool to help you do just that.)