Finding optimal League of Legends builds via linear optimization

I was wondering on how I could optimize the expected time wasted (xTM) metric of my day, so I figured a good way to do it would be to combine the two biggest time-sinks of my life:

1. Fantasy Football
2. League of Legends

Linear optimization plays a very major role in analytics-based FPL and I figured a good way to learn more about linear programming would be to find a relatively easy use case for it in my life and see if I could implement it successfully.

References

This article was heavily inspired by the following article on the same topic. Check it out, it is quite cool and the website is wicked sick.

Source code

The source code for the project can be found on my GitHub on the kighza repository.

Information

League of Legends version

This article is written at the time of $15.10$ being the latest version of the game. Some of the numbers used may vary in the future.

Before we get started, it is important to know a few things about League of Legends. If you are familiar with League of Legends, feel free to skip by clicking here.

League of Legends is a MOBA in which you can upgrade your character’s stats via items, while being limited to 6 item slots. Items cost gold and gold can be earned in a few ways:

1. Killing minions. Minions come at waves, in which there is:

   1. $3$ caster minions, which grant $14$ gold

   2. $3$ melee minions, which grant $21$ gold

   3. $1$ siege/cannon minion, which grants anywhere between $60$ and $90$ gold, depending on the in-game timer. Cannon waves only appear once every $3$ waves.

   On average, you can earn $125\to 147\to 150\to 195$ gold from farming waves, with the value increasing the longer the game goes.

2. Killing champions Killing other players grants anywhere from $300\to 420$ base gold, however, performing well is going to put a kill bounty on you. The bounty can also be negative as to prevent people “farming” players who are not doing well and thus snowballing the game.

   I don’t need to go into a detailed explanation as to how gold bounties work, however it is important to note that while a kill may grant more gold value to a player, it could very well come at a cost such as:

   • Using spells with high cooldowns (such as your ultimate ability or your summoner spells). Although spells have no realized value as you are free to cast them regardless of your gold, using them leads to decreasing the potential value in the longer term. ex: using an ulting (1) for an enemy worth $200$ gold could mean you get to a powerspike (2) quicker, but it could leave you vulnerable to enemies for the next $40-120$ seconds, depending on the cooldown, and it also means you will not be able to gain $400$ gold from another enemy.
   • Risking the enemies turning the play around. Sometimes, the enemy is just more coordinated than your team ¯\_(ツ)_/¯

   In higher levels of play, waves are usually valued way more than what a player with a lower skill may value it, however it is hard to put a blanket statement on which way of acquiring gold is better as it heavily depends on the game state.

Items are divided in a few tiers, but for our purposes:

1. Components - All items have recipes which contain components. They provide less stats than the full item and can later be upgraded into the full item from the recipe
2. The full item - The result of a recipe combining multiple components

Note

Full items will be underlined to prevent the need of having to know every item.

Kai’Sa is a League of Legends champion with a fairly unique mechanic - her spells can be evolved depending on her stats. As of patch 15.10, the way it works is:

1. Reaching $100$ Attack Damage will upgrade Icathian Rain, her primary wave clear and damage ability. The evolved version of the ability fires double the missiles.
2. Reaching $100$ Ability Power will upgrade Void Seeker, her long range, sniper poke ability. The evolved version of the ability refunds $75\%$ of the cooldown upon hit.
3. Reaching $1.00$ Attack Speed will upgrade Supercharge, her primary movement ability. The evolved version of the ability grants $0.5$ seconds of invisibility.

Usually the way people play Kai’Sa is picking one of two paths:

1. Physical damage: building AD (3) and attack speed (5). It is the primary Kai’Sa build around which, I believe, she is balanced by Riot Games.
2. Magic damage: building AP (4). It is the more rare way of playing Kai’Sa and is mostly only meta after an AP Kai’Sa buff. Riot seems keen to not make this build too strong as it is quite game-warping.

…however. There is a third way of playing Kai’Sa… it involves the dark art of…

Problem 1. Hybrid Kai’Sa

It is possible to upgrade all three of Kai’Sa’s abilities, by sacrificing being super good at one thing and becoming a jack of all trades. For that, you will need to get all three requirements: $100$ AP, $100$ AD and $1.00$ AS.

We can formulate this as a linear programming problem. Our goal is finding cheapest build (a.k.a. minimizing cost) that lets us evolve all 3 spells.

$$f(x_1,x_2,\dots ,x_n)=a_1\times x_1+a_2\times x_2+\cdots +a_n\times x_n$$

Our variables $x$ represent the item’s gold cost. As of right now, we will assume that every single item can be bought as many times as needed.

The coefficients $a$ represent the amount of times we have bought that item.

We also need constraints for each of our goals, so:

$$\begin{array}{r}\{\begin{array}{ll}\text{A constraint that requires at least 100 AP }& \to {\text{amount}}_1\times {\text{ap}}_1+\cdots +{\text{amount}}_n\times {\text{ap}}_n\ge 100\\ \text{A constraint that requires at least 100 AD }& \to {\text{amount}}_1\times {\text{ad}}_1+\cdots +{\text{amount}}_n\times {\text{ad}}_n\ge 100\\ \text{A constraint that requires at least 1.00 AS }& \to {\text{amount}}_1\times {\text{as}}_1+\cdots +{\text{amount}}_n\times {\text{as}}_n\ge 1.00\\ & \\ \text{A constraint that requires at most 6 items }& \to {\text{amount}}_1+\cdots +{\text{amount}}_n\le 6\end{array}\end{array}$$

Implementing a $1:1$ translation of the problem described above in your software of choice will likely result in you noticing a fairly obvious flaw. For example, your output could be something like this:

Purchase amount	Item name	Item AD	Item AP	Item AS	Item Cost
$2$	B.F. Sword	$40$	$0$	$0.0$	$1300$
$1.749(9)$	Dagger	$0$	$0$	$0.1$	$250$
$1$	Hearthbound Axe	$20$	$0$	$0.2$	$1200$
$1.25$	Nashor’s Tooth	$0$	$80$	$0.5$	$2900$
Total		100	100	1.00	7863

Despite being a $1:1$ translation of the problem, we are running into an issue! How are we able to buy $0.749(9)$ of a Dagger?! And what does a quarter of a Nashor’s Tooth truly mean?! Are we just getting Nashor’s Root?!?!

This is where integer programming comes into play. The reason why this is happening is because the optimizer does not know what we know - we have not told it that an item’s purchase amount can only be an integer. How stupid of us!

Or, well, it might be just me when I first wrote the code for this article, but at least using my experience lurking in Fantasy Premier League Discord servers, I quickly realized what the issue was.

Solution

Programming language and linear optimization library

For this project, I decided to use Zig , because I really like it, and HiGHS, because it is the library of choice of Sertalp’s FPL solver.

There is no reason to use Zig with a dynamically linked HiGHS binary over Python and highspy. HiGHS is certainly not the only linear optimization library which can be used for this project, however if you are looking to implement it in a different library, choosing one with Mixed-Integer Linear Programming support is a requirement.

All of the code in this article will be somewhat pseudocodey as to avoid talking about irrelevant stuff, however if you want to check the code out, it is open-source.

for (item_list, 0..) |item, i| {
    try highs.addVariable(0, highs.getInf()); // We can purchase an item 0 or infinitely many times 
    try highs.changeColIntegrality(i, .Integer); // We turn the problem into a MILP problem
    try highs.changeColCost(i, item.cost); // We change the cost of the column to be equal to the cost of the item
}
// AD constraint
try highs.addRow(.{ .lower = 100, .upper = highs.getInf() }, item_list.len, index, attack_damage_list); // List of all item's attack damage values
// AP constraint
try highs.addRow(.{ .lower = 100, .upper = highs.getInf() }, item_list.len, index, ability_power_list); // List of all item's ability power values
// AS constraint
try highs.addRow(.{ .lower = 1.00, .upper = highs.getInf() }, item_list.len, index, attack_speed_list); // List of all item's attack speed values
// Limit to 6 items
try highs.addRow(.{ .lower = -highs.getInf(), .upper = 6 }, item_list.len, index, ones); // "ones" is an array of 1s with the length of the amount of items we have

Populating the list of items item_list is fairly trivial as there is a publicly-accessible endpoint with all the information needed. All of the information needed… for now (remember this)

Running this gives us the following result:

Purchase amount	Item name	Item AD	Item AP	Item AS	Item Cost
$1$	B.F. Sword	$40$	$0$	$0.0$	$1300$
$1$	Amplifying Tome	$0$	$20$	$0.0$	$400$
$3$	Hearthbound Axe	$20$	$0$	$0.2$	$1200$
$1$	Nashor’s Tooth	$0$	$80$	$0.5$	$2900$
Total		100	100	1.10	8200

Now that’s more like it.

Fun Fact

When accounting for Nashor’s Tooth’s buff in patch 15.10, we can see that the result is the same as Annie’s (versary.town).

Problem 2: Twitch

Similar to Kai’Sa, Twitch is a champion, primarily played as an ADC (6), however his kit has a bit of an identity crisis. For one, he uhh… lacks useful spells. His W is less than meaningless and his E is entirely reliant on on his terrible passive in order to deal damage.

👀However… the AP scalings on his passive and E are incredible, which has given birth to AP Twitch. The playstyle revolves around leaving Q stealth, autoing (3) a few times and then clicking E for massive damage. Usually when you are fed (7), you would usually need at least $7-8$ auto-attacks before you would have lethal damage on your opponent, which means you would need some attack speed. This lead me to want to figure out, how would I describe this as a linear optimization problem?

The approach I went with is the following:

$$f(x_1,x_2,\dots ,x_n)=a_1\times x_1+a_2\times x_2+\cdots +a_n\times x_n$$

The function remains the same, however what has changed is the variable $x$.

$$x=w_{ap}\times ap+w_{as}\times as-w_{cost}\times cost$$

The variable $x$ is now represented as a the sum of the ability power, attack speed and cost, with weights applied to allow for flexibility in how much we want either of the stats. For example, we might want to describe the variable the following way:

$$x=100\times ap+100\times as-0.01\times cost$$

However there is one big issue. The average ability power item grants $\approx 56.5$ AP, however the average attack speed item grants $\approx 0.31$ AS. This means that running the solver in the current form will result in it always going for full ability power builds and at times sneaking in Nashor’s Tooth as its only attack speed, due to the AP it gives.

I decided to do the following

$$\{\begin{array}{l}A{P}_{scaled}=\frac{A{P}_{item}}{A{P}_{max}}\\ A{S}_{scaled}=\frac{A{S}_{item}}{A{S}_{max}}\end{array}⟶x=100\times A{P}_{scaled}+100\times A{S}_{scaled}-0.01\times cost$$

By scaling relative to the maximum attack speed item, we are able to have a metric in the range of $[0,1]$, which makes comparing the two stats easier.

Note

I am not sure how good of a method this is and I could not think of a better way of dealing with it, given the information that we have. If you have any suggestions, feel free to contact me!

Warning

Item passives are not considered. It would be more or less impossible to accurately represent every item’s value in a way that does not go beyond the scope of this article. An optimal solution for this problem may not be optimal in-game, but it will be optimal for a game without item passives 😅

Solution

for (item_list, 0..) |item, i| {
    try highs.addVariable(0, highs.getInf()); // We can purchase an item 0 or infinitely many times 
    try highs.changeColIntegrality(i, .Integer); // We turn the problem into a MILP problem
    try highs.changeColCost(i, ap_weight * ap + ats_weight * ats - cost_weight * cost); // All we do is change this
}
// Limit to 6 items
try highs.addRow(.{ .lower = -highs.getInf(), .upper = 6 }, item_list.len, index, ones); // "ones" is an array of 1s with the length of the amount of items we have

The output is the following

Purchase amount	Item name	Item AD	Item AP	Item AS	Item Cost
$6$	Nashor’s Tooth	$0$	$80$	$0.5$	$2900$
Eval		$695$

Uhm… Well.

Remember when I told you that the “API has all the information we need”? Sadly, it does not. Within the API, there is no information on which items can be bought multiple times and which cannot. That is why for this problem, I am going to assume that all items can only be bought once. This shouldn’t affect the optimal solution of the problem, as I don’t think a line in which we use up an item slot but we do not use it to it’s full potential is going to be optimal.

If you work with Riot’s API or with the CommunityDragon and you know how to solve this issue, shoot me a message and I will edit this part of the article.

Anyways.

Assuming items are unique, we get the following solution:

Purchase amount	Item name	Item AD	Item AP	Item AS	Item Cost
$1$	Phantom Dancer	$0$	$0$	$0.6$	$2650$
$1$	Rabadon’s Deathcap	$0$	$130$	$0.0$	$3500$
$1$	Wit’s End	$0$	$0$	$0.5$	$2800$
$1$	Nashor’s Tooth	$0$	$80$	$0.5$	$2900$
$1$	Horizon Focus	$0$	$110$	$0.0$	$2900$
$1$	Shadowflame	$0$	$110$	$0.0$	$3200$
Eval		$418$

Problem 3: Gold efficiency

The concept of item value and gold efficiency in League can be approached in many different ways. You can use in-game statistics gathered from actual matches to estimate the win probability at any given moment, which would grant you the ability to see the “win probability added” {1}. While this is an incredibly interesting topic which will nerd-snipe me sooner rather than later, this will not be what I will be doing this time.

The other, more barebones way you can judge item value is by how gold efficient it is. Gold efficiency is the ratio of gold you pay for an item and the gold equivalent of stats you get in return.

$$x_{\text{eff}}=\frac{x_{stat\_value}}{x_{cost}}$$

As so far we have only worked with three types of stats (AD, AP and AS), we are going to do the same here too, however an item is obviously as valuable as the every stat it has and not just those $3$. An item’s stat value is defined as the sum of the stats, multiplied by a constant number, derived from the cheapest item which gives that stat. A list of those constants can be found here, however the important ones for us are:

Stat	Item name	Item cost	Value per stat point
Attack Damage	Long Sword	$350$	$35$
Ability Power	Amplifying Tome	$400$	$20$
Attack Speed	Dagger	$250$	$25$

$$x_{stat\_value}=\sum stat\times value\_per\_stat$$

We can describe it as a linear programming problem by using the same function as before, however replacing the column cost with the item efficiency.

The output is the following:

Purchase amount	Item name	Item AD	Item AP	Item AS	Item Cost
$1$	Blasting Wand	$0$	$45$	$0.0$	$850$
$1$	Long Sword	$10$	$0$	$0.0$	$350$
$1$	Pickaxe	$25$	$0$	$0.0$	$875$
$1$	B.F. Sword	$40$	$0$	$0.0$	$1300$
$1$	Amplifying Tome	$0$	$20$	$0.0$	$400$
$1$	Needlessly Large Rod	$0$	$65$	$0.0$	$1200$
Gold spent	$4975$
Stat value	$5225$
Average item efficiency	$103.65\%$

Fun Fact

The most gold efficient item in the game is every support ward item upgrade at $264.58\%$. Excluding support ward items, it is Doran’s Blade at $160.89\%$. Out of the items we considered, it is Needlessly Large Rod at $108.33\%$

Bonus round

Lets say we need to figure out the most gold efficient way to spend $3000$ gold. All that needs to be done is we need to add a constraint:

$$amoun{t}_1\times x_1+\dots amoun{t}_n\times x_n\le 3000$$

try highs.addRow(.{ .lower = 0, .upper = 3000 }, item_list.len, index, cost_list);

now i am going to slowly waddle away to pretend I haven’t just written $\approx 3,600$ words worth of explanation for a variation of a 0-1 knapsack problem

Where to go from here / future nerd-snipes

1. Investigating evaluating builds based on how useful they can be in later stages of the game as components get turned into items.

2. Evaluating item efficiency via their effect on win probability {1}

Notes

1. Yes, the repository is called kighza as a pun for $\text{Kai’Sa}+\text{HiGHS}=\text{kighza}$ . I am so sorry.

Terminology

1. Ulting - using an ultimate ability

2. Powerspike - spike in relative power level of a champion. Often associated with spending gold (ex. finishing a legendary item), but also used for champion specific mechanics, like Nasus’s Q stacks or, more relevant for this article, Kai’Sa reaching a stat threshold allowing her to evolve a given ability.

3. Attack Damage (a.k.a. AD) - the amount of physical damage dealt by a single basic attack, however spells may have damage ratios that scale with attack damage. Basic attacks are a form of attack every single champion has. Physical damage gets countered by armor. More information can be found here.

4. Ability Power (a.k.a. AP) - the amount of magic damage dealt by a spell. Magic damage gets countered by magic resist. More information can be found here.

5. Attack Speed (a.k.a. AS) - the rate at which basic attacks can be used. More information can be found here.

6. Attack Damage Carry (a.k.a. ADC) - the primary physical damage dealer of the team, who plays in the botlane. Has become synonymous with “botlaner” due to the fact AD marksmen are the most common class in the role.

7. Fed - verb, used as synonym for strong.

References

1. Win probability estimation for strategic decision-making in esports - xPetu