Idea

Imagine a multiplayer online game, such as a MOBA, where players choose from a roster of characters or a real-time strategy game with various unit types players can recruit from.

It is exceptionally challenging and tedious to balance the classes or units, so no single strategy becomes overwhelmingly dominant or completely useless. However, the objective of having properly balanced parameters in a game is crucial to make it engaging, with diverse gameplay and -- ultimately -- successful. Not to mention that properly balanced online multiplayer games have the potential to be played in competitive or even e-sport settings.

Imagine a battle encounter in an RPG game, in which you want experienced players to win by a narrow margin. This can be a design goal to create suspense as the outcome remains uncertain until the very end. As the previous one, this task also requires finding the correct set of parameters from a vast, multi-dimensional space of possible values.

In both examples, properly used evolutionary algorithms can support you. More examples of use cases will be provided in the “Designing a Good Fitness Function“ section of this article.

We have conducted a very simple proof of concept. Earlier, before even applying evolutionary algorithms, we had developed a simple demo called Grailbots, which demonstrates one of the techniques offered by Grail.  In short, Grail (https://grail.com.pl/) is a middleware designed to implement AI in games using C++ or C#. It is suitable for various engines including custom ones, Unity, or Unreal.

Grailbots showcases the Utility AI technique implemented in Grail. This demo features two teams controlled by AI:

They resemble agents that could also be controlled by humans in a real-game.

Screenshot from the Grailbots demo (simple sample project). In this situation, one Grailbot has already been killed by the Enemies.

For this proof-of-concept, our aim was to select the set of parameters of Grailbots and Enemies, such that the Grailbots would typically win by the smallest possible margin. Ideally, the best outcome would be having just one Grailbot surviving with 1 HP after the three enemy waves.

This objective may sound artificial, but our idea was to test whether a design goal of this complexity could be feasibly achieved automatically using evolutionary algorithms.

In the following sections, we will continue to explore this use case but first let us provide a short background on this area. The Grailbots example will be continued in the final section.

Brief Introduction to Evolutionary Algorithms

Evolutionary algorithms (EA) draw inspirations from nature. In particular, the fundamental concepts that underpin their idea are natural selection, adaptation to the environment and survival of the fittest. These concepts were introduced in 1859 by Charles Darwin in a book titled “On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life”.

The classic way of solving problems on computers involves writing sequences of specific instructions. This significantly differs from evolutionary algorithms, which are an example of an Artificial Intelligence (AI) technique, albeit not as popular in recent years as Machine Learning. In EAs, as well as in broader AI, programmers only specify some measure of the quality for the end result without explicitly programming the way to achieve it. The solution is found automatically using a general, problem-agnostic approach.

They also belong to subclasses of AI called:

In EAs, a population of potential solutions to a problem is maintained. The initial population contains weak solutions, often generated randomly or using a simple heuristic. These potential solutions are then subjected to a process mimicking natural evolution. They can reproduce and mutate. The new offspring replace some or all of the previous generation, forming a new population. There is also a concept of fitness, which plays a key role in selection of the individuals for the new population. Some of the basic notions you should know are presented in the next section.

The evolutionary computation encompasses several techniques inspired by natural evolution. For example:

Basic Terminology

Individual - represents a single complete candidate solution to a problem that is solved using evolutionary computation. Individuals form a population and undergo evolutionary operations.

Genotype (chromosome) - represents the genetic encoding of the parameters of the individual. This is the representation used for evolutionary operations. For example, in genetic algorithms, a binary string is a commonly used encoding. One of the benefits of such an encoding is the ability to use the standard, well-established genetic operators with it.

Gene - a fundamental unit and building block of a genotype. Genes are typically located at fixed positions within a chromosome like cells in a vector.

Phenotype - this is the decoded representation, which is the actual form in which the solution is used in the real world. This representation is also referred to as “expressed” or “observable”. It contains features that are observable consequences of a particular genotype. Using the analogy to nature, while the genotype can be likened to a DNA sequence, the phenotype is the actual living organism that possesses this DNA sequence.

Population - a collection of individuals that together undergoes the evolutionary process. Individuals within the population compete with each other and may recombine. In other words, a population represents all potential solutions maintained at a given moment in the algorithm.

Fitness - assigned to individuals, is the numerical assessment of the quality of the candidate solution represented by the individual. Fitness is calculated by the fitness function and is typically defined as a floating-point number.

Crossover (recombination) - an operation that combines genetic information from two (or more in rare cases) parent individuals to create one or more offspring, analogous to biological reproduction. Many common crossover operations have been proposed. Most of them combine parts of the parents' encodings in some way with stochastic elements such as choosing the crossover point at random. Typically, fitter individuals (with higher fitness) have a higher chance of being selected for reproduction. Thus, crossover is often associated with exploitation, as it aims to exploit parts of the most promising candidate solutions.

Mutation - another genetic operation that introduces small random changes to individuals. Unlike crossover, mutation requires only one parent, subsequently mutates. Also, unlike crossover, mutation is typically applied with a very small probability (e.g., 0.05 - 0.1) to each individual. Mutation is often associated with exploration as random alterations to the encoding enable exploration of unknown regions in the solution space.

Children (offspring) - new individuals created through the application of genetic operations (crossover and mutation) to parent individuals.

Selection - the procedure of choosing individuals from the current population, including the results of mutation and recombination, for the next population. The next population will serve as parents in the next iteration. There are many selection methods, but most of them select individuals with higher fitness with higher probability.

Elitism - a mechanism that allows the best-evaluated individuals from the current (parent) generation to survive into the next generation without any change. Such individuals are called the elite ones. This mechanism ensures that the best solutions are not lost due to randomness introduced by the evolutionary operations.

Epoch - one iteration of the evolutionary algorithm. It consists of evaluating the population, applying the defined genetic operations (mutation and crossover), and selecting the individuals for the next population.

Books to Delve Deeper into the Topic

"Handbook of Evolutionary Computation" edited by Thomas Bäck, David B. Fogel, and Zbigniew Michalewicz. Published by Taylor & Francis Group. ISBN: 978-0-7503-0392-7.

"Evolutionary Computation: A Unified Approach" by Kenneth A. De Jong. Published by MIT Press. Online ISBN: 9780262255981.

“Evolutionary Computing: The Origins. In: Introduction to Evolutionary Computing” by Agoston E Eiben and Jim E. Smith. Published by Springer, Berlin, Heidelberg.

DOI: https://doi.org/10.1007/978-3-662-44874-8_2

Prerequisites

Let’s suppose you are deliberating whether some of your game’s parameters could be optimized using evolutionary algorithms.

There are two main prerequisites for this:

The next two sections will address these topics, respectively.

Designing a Good Fitness Function

Designing an effective evaluation function is often the most challenging aspect when applying evolutionary algorithms for optimization. This requires thinking about the desired outcomes in numeric terms. The value of the fitness function indicates the extent to which your design goals have been achieved.

The fitness function can be categorized as:

Additionally, the fitness function can be:

The deterministic & absolute fitness functions are the best in terms of speed and convergence of evolutionary algorithms. However, in game development, you will typically be dealing with non-deterministic & relative ones.

Below, I am showing boxes presenting some examples and inspirations for your games.

The first row of each box specifies the type of game and the optimization objective within it.

The second row describes the idea for the evaluation function.

Reliance of Human Players in Fitness Computations

In general, this evaluation procedure may involve human players but this makes both the implementation non-standard and the process to take extensively long.

It would be best if you could define an evaluation function that only requires to run bots.

What if you can’t?

What if you really need to evaluate your game against humans?

In such a case I would recommend defining the fitness value of a given individual (representing a given set of parameters) as an average value of outcomes from games played by humans against this particular individual. By doing it this way, we can compare results against a hopefully normal distribution of players and the more human players will play, the more confident the fitness value will be.

Let us estimate the effort.

The number of evaluations needed depends on the number of children produced in each iteration and the number of iterations.

The population size should depend on the problem complexity, but I recommend having a number between 60 and 300, because these are the sizes tested the most in various problems in the literature. For the number of iterations, I recommend from 40 to 200.

Let’s make a modest assumption of 80 iterations and 60 children produced per iteration. This requires 4800 evaluations, where each evaluation will be typically a game against a human player.

Let’s assume that one game episode lasts for 30 minutes making the whole workload equal to 2400 man-hours. Assuming an 8-hour work day, it totals to 300 mandays. This is expensive but doable given enough number of participants and a parallelized setup.

However, bear in mind that we have made low-end assumptions about the population size and the number of iterations. I really recommend setting the process using exclusively bots.

Making your Game Simulable

After reading the previous section, it is clear by now that most fitness evaluation functions for our purposes will require the ability to perform a vast number of simulations of the game.

To provide this ability, make sure that:

You either need to implement a robust state loading system or perform a hard reset, but pass the information about the current individual(s) to evaluate. In the latter case, your evolutionary algorithm object must persist between the restarts, or be written and read from the disk or executed on an external server that communicates with the machine that performs the simulations.

Headless simulations: if the simulation only involves bots, consider creating a headless version of the game, i.e., one without graphical rendering. This should be done unless graphics are essential for the proper functioning of the game. Excluding human players eliminates the need for graphics, which can significantly speed up the process.

Speed up time: try increasing the internal clock of the game to make it run faster. Again, this is only feasible in simulations without human players. However, do it carefully, as sometimes, increasing the rate at which the game is played may interfere with the physics calculations. Also, this acceleration is constrained if the bots in the game require a minimum amount of time to “think”. In practice, it is typically possible to increase the speed by at least a factor of 2-3.

Save and load of the EA state: implementing the functionality to fully serialize the current state of a running EA algorithm, including the current population, enables the process to be split across multiple sessions. This is particularly useful in scenarios, where computing resources are not always fully available or when human players are involved in the loop. For example, if human players are required to play the game, some machines can be allocated for this purpose. Whenever a player is ready to play, the system will load the current state of the EA. The player may then advance the progress of the algorithm by some steps, depending on the number of games played.

Parallelization: while not required, it will make the process significantly faster. EA algorithms are very convenient to parallelize and they can benefit a lot from this optimization. Parallel computing can be implemented either on a single machine (taking advantage of CPU threads) or many machines.

There are a lot of strategies for parallelizing the EAs. The most common ones are:

Our Implementation in Grailbots

The following seven parameters have been chosen for optimization:

This can be set up using the Grail library by inheriting from a class named Individual as shown in Listing 1. It allows to set selected member parameters as “optimizable”, meaning that they will become part of the encoding and they will be able to be changed through evolution.

These parameters must be defined as EvoParam<T> type, where T is the type of your actual parameter.

In the constructor of EvoParam you specify the domain, i.e., the available values (of type T) that the parameter can take.

Thanks to built-in implicit casting, EvoParams<T> can be used as follows:

Now we create the EAOptimizer object, which represents the interface of the evolutionary algorithm.

It is the expected value of the portion of the population that will mutate in each iteration.

It is the expected value of the portion of the population that will produce offspring in each iteration.

It is the portion of the top ranked population that is guaranteed to advance to the next generation.

Finally, it is time to start the evolutionary algorithm.

Our API features a RunInteractive(...) method, which allows us to integrate the game with EA.

It takes three callback functions:

In the provided OnEvaluate(...) method, we take the parameter values that should be verified and apply them to the game. Then, the Grailbots demo is played as it would from the beginning. Three waves of enemies, spawned with small intervals between them, are generated.

When the game is finished, we assign the fitness value to the cached individual.

We use a helper class called FitnessRepository that is responsible for updating the fitness to the average value of fitness scores obtained so far by individuals with the same encodings.

The score is computed as follows:

Whenever our game needs to be closed, we can save the progress of the evolutionary algorithm and continue from there the next time:

In this proof-of-concept, we decided:

Final remarks

The proof-of-concept was successful. The final set of parameters determined through evolutionary optimization was:

Evolutionary algorithms can be applied as a tool for game developers, enhancing the process of game design and balancing. These algorithms can efficiently explore vast parameter spaces. By simulating countless gameplay scenarios and evaluating them against defined criteria, they help create more balanced, engaging, and diverse gaming experiences.

The most challenging obstacles to overcome when applying this approach are:

While not replacing human creativity, evolutionary algorithms augment designer intuition, accelerate the balancing process, and can reveal unexpected insights. This approach is particularly valuable in complex games with numerous interacting elements, where manual tuning would be time-consuming and potentially overlook subtle interactions. Ultimately, the integration of evolutionary algorithms in game design represents a fusion of computational power and human creativity, potentially leading to more refined and enjoyable games.