Using the Excel Nonlinear Solver to Optimize Skill Trees with Borderlands 3 Example

Using the Excel Nonlinear Solver to Optimize Skill Trees with Borderlands 3 Example

I used Borderlands 3 for an example because it is an easy one to create and understand. There are some complex skill trees out there, and this one is restricted to 18 decision variables with the only contingencies being previous skills. This solution may not be optimized for your specific play style of Borderlands 3, but it is optimized at one very specific thing (for the most part, as this is not a perfect recreation of the skill tree).

Every numerical solver for an optimization problem needs three things: an objective function, decision variables, and constraints. I will describe all three in an order that makes the most sense with my excel file for reference at this download link
https://drive.google.com/open?id=1nSft-2OV0lfmIXcfaenflDBmUigUM2Ja

Objective Function:
This is a specific function of the decision variables to be either minimized or maximized. For this game, I was using a specific ability called Fade Away, where every shot deals critical damage in addition to base damage. Therefore the objective function is maximizing total damage dealt during Fade Away, namely a product of base damage, crit damage, fire rate, and duration.

Max: Damage = Base x Crit x Fire Rate x Duration

What you will see on the cell for the objective function calculation, is a sum of calculations above it. The damage value for one of them will be zero, because they are mutually exclusive skills, and I used IF() statements to reflect that. If a skill is selected, the first calculation is zero, and the second is nonzero, and vice versa. We want to maximize possible damage including either, so the solver uses the cell B25 for an objective function, the sum of the two above them. The calculations themselves are simply a product of the four variables to the right, and below is input variables that you control depending on your specific gun.

Decision Variables:

The decision variables are skills that can be chosen. They have a set number of integer values to take on, which are the invested skill points. The implicit variables of base damage, crit damage, fire rate, and duration are functions of the values in their corresponding matrices, and the values are chosen by the decision variables. Our goal of maximizing total Fade Away damage is by finding the right combination of decision variable values.

The decision variables are organized by color, since they belong to separate skill trees, and will be constrained by their appropriate tree. There is one specific variable called "misc green", and one called "misc red", and those exist to satisfy the skill prerequisite constraints, and in the game, those are skills which do not have relevant modifications to our objective function. They may be related to health, shields, grenades, etc. 

There are three green decision variables that are separated from the rest of the list, and those are conditional rewards for investing into the skill tree. They do not add to prerequisite skill points, but have prerequisite requirements themselves. Their values are either 0 or 1, and do not contribute to the total sum of available skill points either.

The benefits of the skills are described in the game as additive percentages. For example, the benefits of Furious Attack are +8.3% base damage and +4% fire rate, +16.7% damage and +8% fire rate, or +25% damage and 12% fire rate depending on the respective number of skill points invested. To make this computable, +8.3% is converted to x1.083. For example, 10 total damage over the duration with a sum of +10% and +15% is computed by 10 x 1.1 x 1.15 = 12.65.

Three sets of matrices are found, where the columns are the number of points invested into the skill, the rows are the separate skills, and the entries are the value to be multiplied through. The matrices are differentiated horizontally by the specific implicit variables they affect. The sets of matrices are differentiated vertically as raw percentages, relative percentages, and computed values.

Raw percentages are the additive percentages pulled from the skill trees converted into values. Relative percentages show the increase in percentage by raising a skill to that level. An increase of zero is replaced with a value of one as we are multiplying through values instead of adding through. The computed value matrices have entries that reference the relative percentages matrices for the appropriate decision variable combinations. Any decision variable not chosen takes on the value 1 as well. Therefore, computing the values of the implicit variables is just the product of every value in the appropriate matrix.

Constraints:

The decision variables need constraints to bound the value of the objective function. The first constraint is the total number of skill points spent is 48. Each decision variable has an associated maximum number of points that can be allocated. Most decision variables have a prerequisite amount of points to be dedicated into the skill tree of that color before any may be allocated to that skill. There is a column called "if prereq met" that takes values 0 or 1 to be multiplied through if that prerequisite is met. Therefore, any decision variables chosen that do not have a prerequisite met will multiply their modifications by 0 and not be part of the optimal solution. This is determined by summing the amount of points invested into skill tree and see if they meet the given prerequisite value.

Considerations:

Many of these skills were chosen with the assumption their value is active, while they have conditional activations. Some skills need to land hits to stack the bonus before it is totally activated. Some skills have values that depend on the player's health, or enemies being fought, or several other situations. This makes optimization very difficult, as we need certainty of our numbers. Therefore this exercise is only an estimation of the actual resulting values.

Despite that, this is a great example since the feasible solutions are only going to be chosen from how to dedicate points into about 4 final skills. 

Interpreting the relevant decisions:

The first decision is between Guerillas in the Mist or not having it. This ability is one of the skill rewards which functionally affects the duration of Fade Away at the cost of crit damage. The model is set up in a way that it is better to use Guerillas in the Mist since the extra duration yields higher total damage than without it. This is not a surprising result after playing the game. The only way someone would not use this ability or Gunslinger's Jabber is if the prerequisite skill requirements were not met.

The next decisions are between the number of points in Two Fang, investing points into unlocking Galactic Shadow, and Grim Harvest, investing a point into Power Inside, and finally investing points into Persistence Hunter. What the solver determined is Power Inside yielded higher total damage during Fade Away than any combination of Grim Harvest and Galactic Shadow, whether we consider the condition of +25% crit damage from Power Inside or +50% crit damage. In fact it also thought investing totally into Persistence Hunter yielded enough damage and duration to outweigh any points of Grim Harvest and Galactic Shadow, and only four points into Two Fang instead of five.

Some avid players of this class might notice I did not incorporate Megavore into this optimization because it frankly does nothing during Fade Away. It does not help maximize the damage dealt during since crits are already guaranteed. This does not help answer the question of whether Megavore is worth having when Fade Away is not active, but it might be worth reconsidering Megavore since pursuing it means trading Persistence Hunter and Power Inside for Galactic Shadow and Grim Harvest, which we already know is a sub-optimal path for Fade Away.

Limitations of this method:

As I have already mentioned, there are some limitations by optimizing for anything that cannot be simplified into an objective function. For a more complex build involving balancing crowd control and healing ability, this can only focus on one objective at a time.

What can be done, is incorporating things like equipment choices into this model. Add them as mutually exclusive decision variables, put the appropriate modification values into the matrices, incorporate that into relevant implicit variable calculations, and run the solver.

You are further ahead to look up guides on how to download and use the solver package in Excel than me explaining it, but I hope this is a great inspiration for more numerical optimizations of popular games.

follow me on twitter @kevgk2 for more blog updates!