Building a League of Legends Genetic Algorithm

League of Legends (LoL) is a prominent Multiplayer Online Battle Arena (MOBA) game with over 115 million active monthly players reported as of 2019. Players are split into two teams of five with the objective of destroying the other team’s base first. Each player controls one of 148 unique champions for the duration of the game. The 5 unique champions piloted by each team are known as the team composition, and it is a pivotal strategy in competitive games.

The Importance of Counter Picking

Champions are known to perform well against some, and poorly against others. Similarly, champions have synergies that augment their respective strengths when played together. As a result, team compositions have a huge impact on the results of a game. Therefore, not only is it important to pick the best possible champions, but it is also important to pick champions that perform well against the other team’s team composition.

So What's the Solution?

Genetic Algorithms simulate natural selection as a method to find optimized solutions over a large search space. A random population of individuals are provided with a set of properties. These properties can be mutated or traded between individuals across each iteration, or generation. A fitness function is then used to objectively evaluate the strength of each individual, and the strongest carry on to the next generation. We built a genetic algorithm as a way to determine the best possible team composition to counter a given team.

How does it work?

The individuals in this problem are randomly selected team compositions. Each team composition has five champions, each with their own unique statistics against all other champions in the game. These team compositions are evaluated on their performance against the given team composition, taking win rates and the number of games played into consideration to produce a confidence score against the given team. The higher the confidence, the higher the fitness score.

Crossover

To create the new generation of individuals, “parents” pair together to produce “children” which inherit traits from both parents. When crossing over our team compositions, A single champion from both parents swap place, creating two new team compositions.

Mutation

Mutations serve as a way to explore the search space and maintain genetic diversity within the population. When a team composition is mutated, a random champion is replaced with a new champion. Doing so enables the algorithm to find more unique team compositions that might perform better than the current best composition.

Fitness

A team composition’s fitness is a calculation of the performance of each champion against all champions in the given team composition. Each champion’s performance is calculated using the Wilson score interval with a confidence of 95%. This results in an improved normalized probability that considers both the champion’s win rate and the number of games played against that champion in its calculation. The overall fitness is the average of all confidence calculations for each champion.

Selection

Only a portion of the existing population is carried on to the next generation. Team compositions are selected based on their fitness calculated in the prior step. Two individuals in the population are randomly chosen, and the stronger of the two is selected for the next generation. However, both individuals can be picked again in the selection process, so the weaker one has a chance of being selected for the next generation. Likewise, the stronger individual can have more than one copy in the next generation as well.

How does it Perform?

Mutation and crossover allow the algorithm to explore the search space more drastically in an effort to find the global maximum. This might cause dips in the average fitness of the individuals across generations, but the algorithm will always return the most fit individual across all generations.

Future Improvements

The biggest shortcoming is the limited amount of game data captured. Game information data was collected with the help of other third party developers such as myself. This data was a one time data dump and does not update dynamically from patch to patach. As it gets more popular, this is something I would love to implement in the future.