2025-01-20
word count: 2160
approx reading time: 12 mins
i've recently started playing league of legends again. yes, i know. but the Worlds 2024 into Arcane Season 2 two-punch combo hit me harder than i expected. what can i say. sometimes you can see that the path ahead is dark and full of monsters, yet you're still compelled to march on.
but i digress. i've been playing a bit of Kai'Sa, since she has really fun abilities that make for assassin-like gameplay. she also has an interesting passive ability: her three active abilities evolve once she reaches certain thresholds in three respective stats gained from items.
for example, upon gaining 100 Attack Damage (AD), her Icathian Rain ability evolves, upgrading from shooting 6 missiles to 12. to get over that threshold, we could (for instance) buy 5 Hearthbound Axes, since they give 20 AD each.
your main macro-goal when playing Kai'Sa is to evolve your abilities. as such, people focus on finding the most optimized builds — the cheapest set of items that will take you over the required stat thresholds for all three abilities.
i thought this would be a fun excuse to start messing around with linear programming (LP) and optimization problems, since i've never really had a good use-case before. i prefer learning through solving problems that interest me, rather than delving in academically, without a real-life problem to put it into context.
in linear programming, we define one function we want to optimize, and a set constraints we want our solution to meet. these constraints are expressed as (in)equalities.
in other terms, given a function f over n variables:
f(x_1, ..., x_n) = c_1 * x_1 + ... + c_n * x_n
and a set of constraints:
a_11 * x_1 + ... + a_1n * x_n >= b_1 a_21 * x_1 + ... + a_2n * x_n >= b_2 ...
we want to find a set of values x_1, ..., x_n such that all inequalities hold, and the value of f(x_1, ..., x_n) is minimal.
in our case, we want to find the cheapest build, so our function to optimize will be the gold cost of the build.
this is given by adding together the cost of all items, which we can express as cost_1 * count_1 + ... + cost_2 * count_2,
where cost_i is the gold cost of the i-th item, and count_i is the number of times we're going to buy that item.
count_i will be 0 for items that will not be included in the build.
our constraints will force that the stats provided by the items is enough to evolve her three abilities. since each ability evolves based on a different stat, we will want three constraints:
Icathian Rain evolves when her Attack Damage (AD) is above 100.
Void Seeker evolves when her Ability Power (AP) is above 100.
Supercharge evolves when her Attack Speed (AS) is above 100%.1
which we can formulate as:
ad_1 * count_1 + ... + ad_n * count_n >= 100 ap_1 * count_1 + ... + ap_n * count_n >= 100 as_1 * count_1 + ... + as_n * count_n >= 100
where ad_i, ap_i, and as_i are the i-th item's AD, AP, and AS, respectively.
additionally, in league of legends we can only hold 6 items at a time.2 as such, we'll write one more constraint, to ensure that our build is 6 items or fewer:
count_1 + ... + count_n <= 6
a point to note is that we are not allowed to buy 0.7914 of an item, so we are limited to only considering solutions where every count_i is an integer.
due to how LP solvers work, we can't just find a solution where the variables are real numbers, and then round those up to get an integer. if we did that, we could end up in awkward situations where the rounded value is less optimal than other solutions.
for example: imagine the optimal solution is to buy item A 2.5 times, for a total cost of 250 gold. buying 3 instances would bring the cost up to 300, but there might be a more optimal solution that costs 270 gold buying item B 3 times.
by rounding up an optimal real number solution, we might be missing out on better solutions, so for our use case, we'll have to use an LP solver that has support for integer variables.
i decided to write this in rust since it's what i'm most comfortable with, but there are good LP libraries in practically every language. i decided to go with good_lp. it provides a nice interface and multiple backend choices, from which i chose SCIP. it supports integer variables, it's fast, and its rust crate provides a precompiled bundled binary, so it's easy to run.
i created this struct to hold our item information:
pub struct Item { // item's display name pub name: String, // league's numerical id for this item pub id: String, // gold cost pub cost: u16, // Attack Damage pub ad: u16, // Ability Power pub ap: u16, // Attack Speed pub asp: u16, // maximum times we can have this item pub limit: u16, }
we'll have a list of Item once we get the information from all the items from the game later.
the core of our logic will be defined in a solve function, which will take a list of items, and then find and print the most optimal build.
we'll start by declaring a ProblemVariables, which will keep track of our variables.
then we can create a few Expressions, which will be our function and constraints:
fn solve(items: &[Item]) { // declarations let mut vars = ProblemVariables::new(); // cost. function we'll optimize let mut cost = Expression::from(0); // Constraints: // Attack Damage let mut ad = Expression::from(0); // Ability Power let mut ap = Expression::from(0); // Attack Speed let mut asp = Expression::from(0); // there are a total of 6 slots let mut slots = Expression::from(0); // TODO construct expressions // TODO find best solution // TODO print solution }
we initialize these expressions with a value of 0.
next, we loop through each item, registering a variable that corresponds to the item's count, and then use that to add to the expressions:
fn solve(items: &[Item]) { // ...declarations // construct expressions let item_counts: Vec<(Variable, &Item)> = items .iter() .map(|item| { // register the variable let count = vars.add(variable().integer().min(0).max(item.limit)); // add this item to the expressions ad += count * item.ad; ap += count * item.ap; asp += count * item.asp; slots += count; cost += count * item.cost; (count, item) }) .collect::<Vec<_>>(); // TODO find best solution // TODO print solution }
when registering the variables, we declare them as integers with a minimum of 0 and a maximum of whatever the item's limit is.
we store pairs of (count, item) in a new item_counts array, so we can reference the variables later.
finally, we can solve and print the solution:
fn solve(items: &[Item]) { // ...declarations // ...construct expressions // find best solution let solution = vars // expression to minimize .minimise(cost.clone()) // solver to use .using(good_lp::default_solver) // constraints .with(ad.geq(100)) .with(ap.geq(100)) .with(asp.geq(100)) .with(slots.leq(6)) .solve() .unwrap(); // print solution // evaluate cost expression to get the total cost let total_cost: f64 = solution.eval(cost); println!("Total cost for build: {total_cost}"); // print the solution for (variable, item) in &item_counts { let count: f64 = solution.value(*variable); println!("{} should be bought {} times", item.name, count); } }
constructing the solution is easy: we call the minimise function on the cost expression
and provide a default solver, since we don't have a preference about which one we use.
then we call the with method to specify all the constraints, using geq (greater than or equal to) and leq (less than or equal to) to convert the expressions into inequalities.
after that, we can use the eval function in solution to evaluate the cost expression, obtaining the total cost of this build.
similarly, we can use value to get the value of a specific variable, so we can get the count for each item.
with this, we have everything we need! except, not really. league of legends has hundreds of items, and i do not feel like writing their stats and cost down by hand. so, our next step is:
thankfully,
someone at riot saw they can save lots of money if they let the community build things they don't want to, so
riot provides an export of all values, descriptions, and images from the game.
this includes items, champions, runes, maps, and basically every stat and text used by the game.
this means we don't have to scrape this data from a wiki, or rely on some data-mined export.
neat!
the service where this export is served is Data Dragon.
it contains various json and image files, going back to every past patch since it started.
in our case, we are interested in item.json, which is available at:
http://ddragon.leagueoflegends.com/cdn/15.1.1/data/en_US/item.json
15.1.1 is the latest patch at the time of writing.
in the future, we'll be able to get later patches by replacing that part of the url.
this file's schema looks something like the following (in pseudo-typescript types, since they're useful for describing json):
type Items = { type: "item", version: "15.1.1", // default values for items basic: Item, // list of all items data: { [itemId: string]: Partial<Item>, }, // list of groups (more info on groups later) groups: { [groupId: string]: { id: string, // different from groupId MaxGroupOwnable: string, } }, // tree is not relevant for us tree: { ... }, }; type Item = { // display name of the item name: string, // gold cost gold: { // total gold cost total: number, // whether this item can be bought in the shop purchasable: bool, }, // whether this item can be bought in the shop inStore: bool, // it's number stats stats: { // there are more than 40 different stats! [stat: string]: number, }, // maps this item is available in. // each game mode has it's own map maps: { [mapId: string]: bool, }, // number of times this item can be stacked in your inventory stacks: number, // and a lot of other keys here, but relevant to use are: };
there's a few other fields in item.json, but i'm choosing to only include the ones that contain information relevant to us.
the stats object contains over 65 different fields, of which we only care about three:
for Attack Damage: "FlatPhysicalDamageMod"
for Ability Power: "FlatMagicDamageMod"
for Attack Speed: "PercentAttackSpeedMod"
items can give a few different types of modifiers to each type of stat, but the ones that contribute towards Kai'Sa's passive are those three.
note how in the case of Attack Speed, we want the Percent version of the modifier, and not the Flat. this is because AD and AP are flat stats (they increment additively), while Attack Speed is percent-based.
the passive does not take stat multipliers into account, only base stats given by items. this means we don't have to do any calculations with multipliers.
item.json contains all items in in the game, so it includes items that are not available anymore, items that have restrictions on acquisition (e.g. locked to one champion), or items that are only available in other game modes.
in order to find builds that we can actually buy in game, we'll have to filter out all these irrelevant items.
first of all, we'll remove items that are flat out not purchasable.
these are the ones that have gold.purchasable or inStore set to false.
we also want to remove items that are not available in the main game mode.
this can be checked through the maps property, which indicates what maps an item is available in.
in our case, we only care about "11", which is the Summoner's Rift, the main game mode.
we'll filter out any items that have that set to false.
as an optimization, we'll also remove items that don't contribute to the three stats we care about. the fewer items we have, the fewer variables in our expressions, and the less time the LP solver will need to get to a solution. for this, we simply filter out items that provide 0 Attack Damage, 0 Ability Power, and 0 Attack Speed.
this leaves us, as of version 15.1.1, with 128 items that fit our criteria.
with that, we have everything we need to find the optimal build! we can run our program and get the following output, after improving the printing code a bit:
Found 128 items that contribute to desired stats Found solution in 14.57ms ----- Best build Total cost: 8300 count name cost ad ap attack speed movement speed 1 B. F. Sword 1300 40 0 0 0 1 Amplifying Tome 400 0 20 0 0 3 Hearthbound Axe 1200 20 0 20 0 1 Nashor's Tooth 3000 0 80 50 0 ----- total 8300 100 100 110 0
and that's it! that's the cheapest build that will get us past the required thresholds to evolve Kai'Sa's abilities.
this is a useful result theoretically, but it's not very practical in game. in league of legends, items can be built out of other items (it's components). this consumes the components and some additional gold, and gives you the new item. this means that buying 3 Hearthbound Axes might not be a very good investment towards your end game build. for example, Hearthbound Axe builds into only three items: Kraken Slayer, Terminus, and Trinity Force. usually, if you are playing the usual AD Carry (adc) role, building Trinity Force on Kai'Sa doesn't make a lot of sense, since it gives some stats that we don't care much about.
we are also ignoring that in most games, we want some amount of movement speed. this usually comes from a Boots descendant item like Berserker's Greaves, which gives 45 movement speed. in our optimal build, we get 0 movement speed from items, which is usually not a great idea.
if we add a constraint requiring for example 25 movement speed, we end with the following build:
Found 128 items that contribute to desired stats Found solution in 70.04ms ----- Best build Total cost: 12400 count name cost ad ap attack speed movement speed 1 Dark Seal 350 0 15 0 0 1 Phantom Dancer 2650 0 0 60 8 1 Aether Wisp 900 0 30 0 4 1 Youmuu's Ghostblade 2800 55 0 0 4 1 Shurelya's Battlesong 2600 0 65 0 6 1 Kraken Slayer 3100 45 0 40 4 ----- total 12400 100 110 100 26
it's 4100 gold more than our most optimal build, while giving 25 movement speed, which is a decent amount, but considering the basic Boots give 25 movement speed for 300 gold, it's disappointing.
another option we have is lowering our slots constraint to 5, reserving the 6th one for Berserker's Greaves.
this item gives 25% attack speed, which means we get to lower our Attack Speed constraint to being greater than or equal to 75!
the optimal build is then:
Found 128 items that contribute to desired stats Found solution in 35.05ms ----- Best build Total cost: 7950 count name cost ad ap attack speed movement speed 1 Long Sword 350 10 0 0 0 1 B. F. Sword 1300 40 0 0 0 1 Amplifying Tome 400 0 20 0 0 1 Yun Tal Wildarrows 2900 50 0 25 0 1 Nashor's Tooth 3000 0 80 50 0 ----- total 7950 100 100 75 0
including the 1100 gold cost of Berserker's Greaves, the total cost is 9050, which is only 750 more gold than our ideal optimal build. neat!
we have found some optimal solutions, but there might be more! there could exist other builds that cost exactly the same as our most optimal build. there might also be other builds that cost a bit more gold, but that scale significantly better into the late game, or that include items that provide stronger passive effects, or that are better in specific match-ups.
it'd be useful to be aware of what other options we have, even though they might not be exactly optimal. this would give us some flexibility and allow us to pick an optimized build that works great on a specific match.
the way we find these other solutions is by adding additional constraints that exclude the optimal solutions we find (for example cost >= 8301, or item17_count != 1).
this will give us other different solutions, which will still fit into our original set of constraints.
we can recursively do this, getting different solutions each time.
we can also add more constraints that focus on building up towards late game items using components, having a build that's optimal early game and that builds into a powerful, viable late game build.
we could also add some constraints to focus on evolving the abilities in order. we might consider Icathian Rain's evolution to be much more powerful than the other two, and that we therefore want to rush it, finding the build that gets us there for the least amount of gold, and then reaches the other two thresholds later.
all of these options are more complex, and i'm not even sure they can be fully expressed as simple linear programming problems. we might need more powerful tools to explore these! i leave this exploration as an exercise to the reader3 :p
