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.
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: love, dive, cave and test.
If we guess love, and the correct password is dive, the 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 |
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.
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.
min = $\infty$
best = ""
for guess in passwords:
max = 0
for outcome in outcomes:
c = 0
for correct in passwords:
if test(guess,correct) == outcome:
c++
if c > max
max = c
if max < min
min = max
best = guess
return best
Lets use the candidates from the previous example: love, dive, cave 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.
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.
1. http://www.cs.uni.edu/~wallingf/teaching/cs3530/resources/knuth-mastermind.pdf
2. John (http://math.stackexchange.com/users/7163/john), Knuth's mastermind algorithm, URL (version: 2015-03-16): http://math.stackexchange.com/q/1193037