I've been working on a League of Legends Build Order optimizer.
I got the idea after hearing one of my new co-worker explaining that at his last job he worked in a team of five trying to create a build order optimizer for Dota 2 (another Moba game) via neural networks and they failed. More specifically, the builds were no better than what a standard player could come up with.
I recalled back to my PhD work on solving acquisition problems using generic algorithms and realized I could actually do it. One covid year later and I've almost finished it.
You give it the champion, the play style and divide up the abstract stats like Damage, Effective Health, Gap Close, etc... and the genetic algorithm gives an optimized build order for it.
The site is backed by ~450,000 pre-computed build orders, which took a week to generate on a 32 core box.
I've been talking to some challenger (really good) players and got a list of things that needed to be done. Basically being able to change the various options used by the model and being able to override runes/items.
Since it wouldn't be practical to run the whole genetic algorithm in a web browser, I've implemented a hill climber, which runs in the web browser, that accepts the output of the genetic algorithm, the user requested changes and then it hill climbs the build order back to the local optima.
The genetic algorithm was written in Kotlin (compiled to JVM) so I used Kotlin's compile to Javascript to create the web based hill climber.
I've also implemented guides so you save the builds you find from the optimizer. You can login as guest/guest.
The more I think about it, the players themselves and their match history can be thought of as agents in a GA simulation. The players with better builds tend to win more and their builds eventually dominate the gene pool. However, since most people just copy online builds, there's little experimentation so those builds may be stuck in a local optima.
Assuming you have robust mutations, were you able to discover any new novel (and effective) builds not previously known?
All the builds are generated from scratch. It's maths descriptions of the items/abilities + the lol formula. So the vast majority of the builds are novel. (Some of them happen to line up with what is currently played.)
Are they effective is a good question, basically that needs lots of play testing by real players. I've added guides so people can tell other people about good builds they have found.
So when developing it, I took some existing builds from the internet and I broke them down into a ratio of stats aka (1 damage: 1.5 cooldown (now AH): 1.2 late game health) and then had the GA reconstruct those builds from the ratios.
On the builds being played by the pros created by professional analysts, I got back very similar looking builds. On random builds from site like mobafire I got back completely different builds.
Thinking back, when Cloak of Agility was briefly buffed last year, it came back with the exact amount of them to spam and exactly when to do it. It took 10 minutes and the player base took 3 weeks to work it out.
One big unmodelled parameter is the enemy team composition. For example, against teams with easy-to-land poke, QSS is better than Banshee’s Veil.
If you modeled team composition, it may be possible to even model pick-ban phase via min-max search. A full exhaustive search would be computationally impossible, but you could approximate it AlphaGo style with a neural network estimator + Monte Carlo tree search. You may be able to sell such software to professional teams.
So in the work the PhD is built upon, you focus entirely on what you can do, ignoring the enemy side. It might not be correct but it's a strategy you can take. You can still sort of address it by saying you need to have the ability to deal with X.
Pick-ban phase optimization already exists at least for Dota 2.
I'd assume the problem with doing this for dota2 is that items have more complex effects and the optimum build can vary depending on the state of the game at any time, is a teammate getting this item?, is the enemy already building to counter it? A lot more complexity and situational evaluation required.
I could apply this to Dota 2 as well. I just went with LoL since I play LoL and it's more popular.
So the original team of 5 went with Dota 2 because it has a much better API they could get game data from. They poured the Dota 2 pro games into a neural network to create a build generator.
It couldn't make sense of the input data. Apparently Dota 2 pro players are trolls according to my ex co-worker.
I didn't work on it so I don't really know.
It doesn't affect my method since I'm taking in descriptions of the items, runes and champions and putting together the builds from scratch without looking at gameplay. It needs a couple of tweaks such as stating the average combat length for champions.
a lot of dota2 builds require very intentional use of very small advantages with narrow timings. you'll see pros go in for a 1v1 kill the moment they hit level 5 and come out the other end with barely any HP, but that HP will be due to a minor totem they bought or a bottle sip in between hits or something
There was some work using genetic algorithms determining build orders in Starcraft II. It produced some really innovative stuff.
When your tool optimizes for "gap closer" what are the characteristics of the items it selects for? Move speed? Ranged slows? Is there a consideration of item active vs. passive effects? For example, Stridebreaker is in a lot of bruiser build orders because it has an active (i.e. requires a button press) gap closing ability.
Seems alright, but there's some major mistakes like Lich Bane on Xerath late game, Kraken Slayer on Jhin, full Maw early on Talon.
Looks pretty good overall though. I'd love to see this, but vs specific matchups which is the most important part of build optimization. The hard part of builds is choosing which item in certain scenarios.
That's why the customize this build menu exists. It's looking at the raw number but if for game play reasons you need galeforce/eclipse you can just set that under force items.
Did my best to generate a jinx build, with high HP recovery and no lategame armor penetration (and no armor/mr). I also chose no gap-close because of jinx's passive and w. It generated:
I'm surprised to see this even with high hp recovery - I asked for no armor pen, but it decided to build dominik's anyways, and it doesn't buy a vamp scepter until after 3.5 completed items. If I went this build, about 99% of my games would end before I got ie, everything after that matters a lot less, and so I'm surprised to see it push everything non-"core" (including the armor pen I didn't want) into the end of the build.
I don't understand how this can be useful without taking into account your teammates and enemies. For example, as Caitlyn I wouldn't want to take Legend Bloodline if my support was a Soraka, but otherwise it's better than Legend Alacrity in most cases.
It suggests Triumph over Overheal for Aphelios even though that rune is much more synergistic due to his pistol.
I appreciate that the tool exists, but there are problems that are more easily solved by small critical thinking than machines.
It doesn't look like there are any guides for most of the champions. I've clocked on 5 or 6 and the only one I see is for the first champion alphabetically, so 1/6. It's a little hard for me to make anything of this unless it's relevant to familiar champions. Is this a bug of the website or to-do?
Good one. We also used GA as part of our game balancer. We found interesting/unforeseen behaviours in the character dynamics and also interesting tactics for players. One thing to note is that this is a dynamic problem and your build might go obsolete with the introduction of new game features.
Thanks. It takes a week for the whole thing to run. So I'm currently updating it from League of Legends PBE (next patch test) a week before each release.
I recalled back to my PhD work on solving acquisition problems using generic algorithms and realized I could actually do it. One covid year later and I've almost finished it.
You give it the champion, the play style and divide up the abstract stats like Damage, Effective Health, Gap Close, etc... and the genetic algorithm gives an optimized build order for it.
The site is backed by ~450,000 pre-computed build orders, which took a week to generate on a 32 core box.
I've been talking to some challenger (really good) players and got a list of things that needed to be done. Basically being able to change the various options used by the model and being able to override runes/items.
Since it wouldn't be practical to run the whole genetic algorithm in a web browser, I've implemented a hill climber, which runs in the web browser, that accepts the output of the genetic algorithm, the user requested changes and then it hill climbs the build order back to the local optima.
The genetic algorithm was written in Kotlin (compiled to JVM) so I used Kotlin's compile to Javascript to create the web based hill climber.
I've also implemented guides so you save the builds you find from the optimizer. You can login as guest/guest.
Build Orders: https://www.lolsolved.gg/builds/ Technical Explanation: https://www.lolsolved.gg/about User Guide: https://www.lolsolved.gg/help
I'm sticking around so feel free to ask questions.