Optimal strategy for Fallout terminal hacking

Written by Benjamin Eriksson

22 September 2016

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:� 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.� 

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 = ""
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

� 

Example

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.

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.� 

� 

� 

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

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

Write your comment!

Comments