Nov 152015
 

Since its release last week, I’ve been playing quite a bit of Fallout 4. There’s an interesting mini-game (which was in previous iterations as well) for “hacking” computer terminals, where you must guess the passcode on a list of possibilities with a limited number of guesses. Each failed guess provides the number of correct letters (in both value and position) in that particular word, but not which letters were correct, allowing you to deduce the correct passcode similarly to the game “Mastermind.” A natural question is, “what is the best strategy for identifying the correct passcode?” We’ll ignore the possibility of dud removal and guess resets (which exist to simplify it a bit in game) for the analysis.

Reformulating this as a probability question offers a framework to design the best strategy. First, some definitions: N denotes the number of words, z denotes the correct word, and x_i denotes a word on the list (in some consistent order). A simple approach suggests that we want to use the maximum likelihood (ML) estimate of z to choose the next word based on all the words guessed so far and their results:

\hat{z} = \underset{x_i}{\mathrm{argmax}}~~\mathrm{Pr}(z=x_i)

However, for the first word, the probability prior is uniform—each word is equally likely. This might seem like the end of the line, so just pick the first word randomly (or always pick the first one on the list, for instance). However, future guesses depend on what this first guess tells us, so we’d be better off with an estimate which maximizes the mutual information between the guess and the unknown password. Using the concept of entropy (which I’ve discussed briefly before), we can formalize the notion of “mutual information” into a mathematical definition: I(z, x) = H(z) - H(z|x). In this sense, “information” is what you gain by making an observation, and it is measured by how it affects the possible states for a latent variable to take. For more compact notation, let’s define F_i=f(x_i) as the “result” random variable for a particular word, telling us how many letters matched, taking values \{0,1,...,M\}, where M is the length of words in the current puzzle. Then, we can change our selection criteria to pick the maximum mutual information:

\hat{z} = \underset{x_i}{\mathrm{argmin}}~~H(z|F_i)

But, we haven’t talked about what “conditional entropy” might mean, so it’s not yet clear how to calculate H(z | F_i), apart from it being the entropy after observing F_i‘s value. Conditional entropy is distinct from conditional probability in a subtle way: conditional probability is based on a specific observation, such as F_i=1, but conditional entropy is based on all possible observations and reflects how many possible system configurations there are after making an observation, regardless of what its value is. It’s a sum of the resulting entropy after each possible observation, weighted by the probability of that observation happening:

H(Z | X) = \sum_{x\in X} p(x)H(Z | X = x)

As an example, let’s consider a puzzle with M=5 and N=10. We know that \forall x_i,\mathrm{Pr}(F_i=5)=p_{F_i}(5)=0.1. If we define the similarity function L(x_i, x_j) to be the number of letters that match in place and value for two words, and we define the group of sets S^{k}_{i}=\{x_j:L(x_i,x_j)=k\} as the candidate sets, then we can find the probability distribution for F_i by counting,

p_{F_i}(k)=\frac{\vert{S^k_i}\vert}{N}

As a sanity check, we know that \vert{S^5_i}\vert=1 because there are no duplicates, and therefore this equation matches our intuition for the probability of each word being an exact match. With the definition of p_{F_i}(k) in hand, all that remains is finding H(z | F_i=k), but luckily our definition for S^k_i has already solved this problem! If F_i=k, then we know that the true solution is uniformly distributed in S^k_i, so

H(z | F_i=k) = \log_2\vert{S^k_i}\vert.

Finding the best guess is as simple as enumerating S^k_i and then finding the x_i which produces the minimum conditional entropy. For subsequent guesses, we simply augment the definition for the candidate sets by further stipulating that set members x_j must also be in the observed set for all previous iterations. This is equivalent to taking the set intersection, but the notation gets even messier than we have so far, so I won’t list all the details here.

All that said, this is more of an interesting theoretical observation than a practical one. Counting all of the sets by hand generally takes longer than a simpler strategy, so it is not well suited for human use (I believe it is O(n^2) operations for each guess), although a computer can do it effectively. Personally, I just go through and find all the emoticons to remove duds and then find a word that has one or two overlaps with others for my first guess, and the field narrows down very quickly.

Beyond its appearance in a Fallout 4 mini-game, the concept of “maximum mutual information” estimation has broad scientific applications. The most notable in my mind is in machine learning, where MMI is used for training classifiers, in particular, Hidden Markov Models (HMMs) such as those used in speech recognition. Given reasonable probability distributions, MMI estimates are able to handle situations where ML estimates appear ambiguous, and as such they are able to be used for “discriminative training.” Typically, an HMM training algorithm would receive labeled examples of each case and learn their statistics only. However, a discriminative trainer can also consider the labeled examples of other cases in order to improve classification when categories are very similar but semantically distinct.

Jul 042012
 

I normally don’t write about videogames, but I thought it would be fun to take some time to write about the armor and resistance system in Diablo III, as well as to throw some math at it to see how best to improve one’s character.

In Diablo III, the key to surviving Inferno is getting appropriate gear. However, aside from the obvious improvements of increasing the stats on an item, it can be difficult to intuitively judge the tradeoffs between dissimilar stats. Is it worth it to give up 40 vitality points in order to gain 20 points of resistance to all? How about trading 100 points of strength for 100 points of intelligence? In trying to answer these questions, we will temporarily ignore the question of damage, because, if you can’t survive an attack from an Inferno-level elite, unless you do over a million DPS, you won’t have a chance to kill it anyway. There are two basic concepts to understanding survivability when absorbing damage (we will ignore dodge because it further complicates things): damage reduction and effective hit points, which are really two ways of looking at the same stats.

Damage Reduction

The combat system is pretty straightforward: when a monster attacks, a random number is generated between its min and max attack values, that number is reduced by armor, resistance, and extra modifiers, and then the resulting value is subtracted from your health. The consensus (which can be experimentally verified) is that the resistance and armor reductions can be found with the following formulas:

r_{resist}=\frac{R_{all}}{5m+R_{all}}, r_{armor}=\frac{A}{50m+A}

Where R represents resistance total, A represents armor total, m represents the monster level (60 for all of inferno, as far as I can tell), and r is the reduction, which is expressed on the UI as a percentage. Therefore 1-r is used to calculate how much damage is done by an attack. The two resistances multiply, so the total damage done by a single attack is given as (1-r_{resist})(1-r_{armor}) multiplied by the initial attack damage. Note that if you find a shrine of protection or use a skill such as the wizard’s blur ability, it is counted in a third category that we will ignore from here out. This category is multiplied in exactly the same way, so total damage becomes (1-r_{resist})(1-r_{armor})(1-r_{other}) in that case.

The reduction is the remainder after the damage amount is subtracted from the total damage. If we normalize by the monster’s damage, we find that the damage reduction for any attack becomes:

DR=1-(1-r_{resist})(1-r_{armor})

To increase one’s survivability, it is necessary to increase the value of damage reduction, but because stats are limited on items, there is always a tradeoff. Because there is a direct, unchanging relationship between strength an armor (1 strength adds 1 armor) and between intelligence and resistance to all (10 intelligence adds 1 to all resistance), we will first look at the tradeoff between armor and resistance alone. A quick look at the two equations tells us that if we multiply r_{resist} by 10/10, we will get the same expression that is used to find the reduction by armor, which suggests that 1 resistance to all is equal to 10 armor because they increase their respective reductions at the same rate. This is only accurate in certain cases, because the total damage reduction depends on the product of all resistance and armor, rather than a linear combination of the two.

Instead, it is much more useful to examine the partial derivatives of damage reduction with respect to all resistance and armor, respectively :

\frac{\partial {DR}}{\partial A}=(1-r_{resist})(\frac{\partial }{\partial A}\frac{A}{50m+A})

=(1-r_{resist})(\frac{1}{50m+A}-\frac{A}{(50m+A)^2})=(1-r_{resist})(\frac{50m}{(50m+A)^2})

The partial derivative of damage reduction due to all resistance can be found analogously to be:

\frac{\partial {DR}}{\partial R_{all}}=(1-r_{armor})(\frac{5m}{(5m+R_{all})^2})

The relationship between all resistance and armor is, therefore, dependent on what the two values are, and we can see that increasing the smaller value will have a larger impact on total damage reduction than further increasing the larger value will, which means that 1 all resistance is not always worth the same as 10 armor, when it comes to changing damage reduction—sometimes all resistance is more valuable, and sometimes less, with the 1:10 ratio being equal when r_{resist} and r_{armor} are equal. This is kind of hard to visualize, so it’s much more useful to simply create a contour plot of damage reduction as a function of both armor and all resistance, which serves as a guide for the relationship between the two stats.

A contour plot demonstrating the relationship between armor and all resistance as it contributes to damage resistance

Moving to a darker red area represents an increase in total damage reduction, and so we see that along the diagonal, both contribute equally, but when one variable is significantly larger than the other, further increases are not as effective as bumping the lower stat would be.

Effective HP

With a good understanding of how damage resistance is calculated, it is time to extend the concept to allow us to include other tradeoffs when determining which gear to use. The next component of survivability is how many hit points your character has. However, all characters with 30,000 HP are not created equal—the character with better damage reduction will do better in combat, so our goal is to quantify the relationship between hit points and damage reduction.

In order to compare characters with different resistances and HP, it is necessary to eliminate the armor and resistance entirely and focus on only a single point of comparison that summarizes the effects of all of the attributes, which is known as ‘Effective HP.’ If a character with 90% damage reduction is hit and suffers 10,000 HP worth of damage, by inverting the equation we can find that the attack must have done 100,000 HP of damage originally, and so, an equivalent character with zero armor and zero resist would have an effective 100k HP for each 10k HP that our character has. The direct formula for effective HP from actual HP and damage reduction is:

HP_e=\frac{HP}{1-DR}

At this point, more derivatives could be calculated to find the effects of changing vitality, armor, or resistance on effective HP, but it is much simpler to create a spreadsheet that computes the effective HP for a given triple of vitality (plus your character’s base hit points, which is not zero), armor, and all resistance, and then using that to compare different gear setups. Intuitively, more effective HP is better, as it means you will survive longer against elites and champions, regardless of whether your actual HP increased or decreased. The same is true for your damage reduction; your effective HP can increase despite damage reduction decreasing, if your base HP is sufficiently increased at the same time. It is also worth noting that all HP regeneration becomes more effective as damage reduction goes up—the effective HP regeneration can be calculated in exactly the same way as effective HP is calculated.

Hopefully it is clear that selecting Diablo III gear is a constrained optimization problem. Maybe one day I’ll take a stab at writing a program to optimize stats or provide some kind of discussion on the actual tradeoffs between DPS and HP as they relate to killing monsters, but that sounds like a very painful exercise when approximate solutions can be found just by thinking +effective HP and +damage are good.