# Introduction

If you've played the modern Fallout series you have without a doubt also tried to hack a terminal. There are many tutorials on the subject but most of them solves the problem by using tricks like reloading the game before running out of attempts. Altought this works it doesn't give any in-depth understanding of the hacking, which is the reason for this article.

On the off chance that you've haven't played the game yet, I'll make a brief explanation of the mechanics behind the "hacking". Finally we'll examine an optimal strategy for hacking the terminals.

# Basics

To hack a terminal you need to guess the correct password out of a list of possible candidates. If you guess wrong the terminal returns how many letters were in the correct position. Lets say you are given the following words: lovedivecave and test

If we guess love, and the correct password is divethe terminal will return 2. This is because love and dive have two letters in the same position. The next step is to look at all the candidates that share 2 letters with love.

 Password Letters in common Dive 2 Cave 2 Test 0
x 2 + 4 x + 4 = 0

The table above shows that dive and cave are both possible candidates.The guessing continues until you either get locked out or guess the correct password. It's important to note that our guess eliminated one possible candidate. A good guess should elimate as many candidates as possible, more about this in the next section.

If you want to try it yourself i can recommend Mitchell Thompson's simulator: Fallout 3 Terminal Hacking.

# Analysis

The first thing to realize is that the fallout hacking minigame is actually a modern version of the old mastermind board game. Luckily for us the great computer scientist Donald Knuth solved this problem[1] about 40 years ago. While Knuth's solution is very comprehensive John from Stackexchange summarizes the core idea well[2]

Let's say $S_i$ is an element of $S$, the possible values of the winning code. What you're asking of each $S_i$ at the step you're puzzling about is this: If the answer were $S_i$, would I have gotten the response I got with my current guess?

— John

The goal of our algortihm should thus be to minimize the number of possible candidates or maximize the number of eliminated candidates, depending on your point of view. There is a small caveat however, the number of eliminated candidates are determined not only by our guess but also by the correct password, which we do not know. Therefore it is necessary to consider all possible candidates together with all possible passwords and minimize the worst case scenario. That is, using a minimax algorithm.

# Code

min = $\infty$
best = ""
max = 0
for outcome in outcomes:
c = 0
if test(guess,correct) == outcome:
c++
if c > max
max = c
if max < min
min = max
best = guess
return best


# Example

Lets use the candidates from the previous example: lovedivecave and hack. The possible outcomes are the possible number of letters the passwords can have in common.

 Guess love Outcomes 0 1 2 3 4 Passwords test cave, dive love c 1 0 2 0 1 max 2

The table above shows that the worst case scenario for guessing love is that the password is either dive or cave. Now we create similar tables for the rest of the passwords.

 Guess test Outcomes 0 1 2 3 4 Passwords cave, dive, love test c 3 1 0 0 1 max 3

 Guess dive Outcomes 0 1 2 3 4 Passwords test cave, love dive c 1 0 2 0 1 max 2

 Guess cave Outcomes 0 1 2 3 4 Passwords test dive, love cave c 1 0 2 0 1 max 2

The last step is to take the minimum of all the max values: $min(2,3,2,2) = 2$. The interpretation of this result is that gussing love, dive or cave are all dominant strategies.

# Conclusion

First of all it is clear that this is not a practical solution to use when playing the game since it is computation heavy and hard to do by hand. A more practical solution might try to exploit groups of passwords with the same suffixes.

It is also worth noting that this algorithm is optimal for worst case scenarios. There might be other algorithms that uses fewer guesses on average but more in the worst case.

# Notes

2. John (http://math.stackexchange.com/users/7163/john), Knuth's mastermind algorithm, URL (version: 2015-03-16): http://math.stackexchange.com/q/1193037