So Imba, I am going to quit the game! (Part 2)
Detailed explanantion on how this AI empowered game balance system works with a simple example implemented using genetic algorithm (GA).
After reading this, you will be able to understand how GA works and how to implement GA on your own for various scenarios.
More details will be disclosed in this post regarding the game balance system. Before we get started, let’s have a look at how part of this system will be like.
If you are unaware of what game balance is and why we are at this stage, please refer to the Medium post blow.
Game 😍
Ok, let’s begin. To start with, I think it is essential for you to understand the game we are dealing with and the complexities laying behind.
The game we are focusing here is called Junior Three Kingdoms Zero (少年三国志零).
This is a Chinese mobile card strategy game where players will need to plan ahead which set of cards they want to use on the battle field (a 4x4 grid) with certain line-up and placement strategies in order to win the battle.
Inside the game, there are mainly two different types of cards, commanders and counsellors. Each has distinct types and abilities. Commanders can couple with various kinds of soldiers. Each of these in-game characters have their own growth dimensions (e.g. commanders have levels, armors, skills, leadership, card qualities and etc). Before battling, the team line-up need to follow certain rules. For instance, commanders of type Shield can only be placed at the first two rows and can only be coupled with soldiers of the same type. Moreover, while battling, different card combinations can have different effects. For example, cards with skills of type wind can increase the damage caused by skills of the fire type.
Before confusing you more, I think I will save my words on descibing further here. At least now you got a taste on how complex this game could be. Below are some screenshots of how the game looks like.
Genetic Algorithm (GA)
After understanding the complexity of the game, it’s important to narrow down the balance target and stay focused to get started. Here I will only discuss how GA fits into the game balance for PVP case (PVE is too much to discuss here).
PVP, or player vs player, is a game mode where players play against each other. The reason to start with PVP balance is that it is easier to verify assuming players are now at the same or fixed development levels. The only things that matter are choices of commanders, counsellors, soldiers and placements in the battle fields.
Let’s review GA again, it usually contains five different stages: initialization, evaluation, selection, breeding and mutation.
Now Initialization
With the growth status predefined and fixed, the population is randomly initialised from pools of commanders, counsellors and soldiers. These choices, combinations and placements from initialization stage must comply with some in-game constraints (e.g. commanders of type shield can only couple with soldier of type shield).
Dont worry, code is coming … (in easy mode)
Let’s create an easy demo PVP game. In this demo game, each player will create a line-up with 0s and 1s. Combat power for a specific line-up will be determined by the number of 1s it has. More 1s means more combat power. When fighting, lineup with higher combat power will win. Now intuitively, we know that line-up with all 1s are the strongest one. Let’s unveil this with GA.
First is to create a line-up class:
Class Lineup defines a line-up as a gene squence of 0s and 1s. Each line-up is initialized with a random gene sequence of length 20. Total number of 1s indicates the combat_power of that specific line-up. Score here is prepared for future use. Name is of course only for fun.
Let’s randomly initialize 3 different line-ups with an initial score of 50:
Results:
Fitness Evaluation
After initialization, the next step is to decide how to evaluate the fitness value of each line-ups. One of the most common ways to evaluate how good a line-up can be is through ladder ranking system (e.g. Dota II).
Specifically, in this case, each of the line-ups is given a starting fitness value of 50. Within the generation pool, pairs of line-ups are randomly selected without replacement. Each pair will then fight each other, the winner get some scores, the loser lost some.
For the real game, there is a simulator which takes battle configurations and return a battle result. In the dummy game, we can utilize a fight function to simulate the process.
Codes showns below demonstrate the idea of calculating fitness value in a ranking system.
Class Battle stores battle informaiton.
Funciton fight compares two line-ups on number of 1s.
Function evaluate recalculates the ranking score based on the fight outcome for each line-up.
Code above populated initial generation of size 20, randomly matched pairs for fight and evaluated ranking score accordingly.
Results:
Selection
Once evaluation is done, the selection process is started. The purpose of selection is to keep the better genes and pass them to the population in next generation. In order to maintain good properties from a line-up and ensure fast convergence, the concept of elitism is ultilized. Elitism basically means brings some individuals from the current generation to the next generation. Specifically in the PVP case, 10% of the top line-ups are kept to the next generation, the rest 80% are selected for mutation and last 10% are discarded.
In the real game, the gene is the combination of different characters and their corresponding placement. For our dummy game, gene is the composation of 1s and 0s in the gene sequence.
Code below demonstrates the selection idea with the dummy line-ups:
Select will take scored line-ups and return elites and mutation pools.
Breeding
Now we already have 10% of the line-ups from previous generation, we need to fill up the rest population. One way is through breeding. Essentially, breeding is to swap genes of parents. In the real game, parents pairs are selected randomly from elite pool. Then components (e.g. commanders, counsellors and soldiers and grid position) from parent line-ups can all be swapped while complying in-game rules.
Even though this may sound easy, it is actually quite tricky. We need to consider whether two parents are different enough for breeding. Also, in-game constrants will add a lot of compelxity.
However, with our dummy game, the idea is quite simple, we need to check whether two parents are breedable and if so swap 0s and 1s among parents to generate the next generation. The elite selected are then used as parents to produce 10% of the next generation.
Run:
Current population:
Mutation
Up to now, there are still 80% of the population left. The new 80% will be mutations from the normal 80% remained in the selection process.
Basically, mutation means to change one trait of a line-up to others.
In the real game, mutation includes change of commanders, placements, counsellors and soldiers. However, in the demo game, it will simply be a flip of the digit, from 1 to 0 or vice versa.
Generally, in order to speed up convergence, mutations should have a good chance to be in better directions but remain a small chance for exploration. Specifically, given our game context, mutation should happen more on the 0 digit (change from 0 to 1) and less on the 1 digit (change from 1 to 0).
The probability is set to be 0.9 to mutate from 0 to 1 and 0.1 for 1 to 0.
During mutation, each line-ups will inherite score from the least score in the mutation pool. The heuristic behind is that if the mutated new-lineup is not performing, it will likely be discarded after the next generation.
Result:
Inception — loop around
At this stage, we are back to the begining. New population will be examined in the fighting environment again, next generation will be created and loop will continue.
This jupyter notebook contains all the codes assembled together. Feel free to try out.
Below is the combat_power change for 10 generations:
Some thoughts
At this stage, we have implemented GA on a dummy game. Now I hope you have a in-depth view of how this algorithm works to identify the better line-ups. However, there are some areas that we could improve on top of this.
Ranking system: in the real game, more criteria (such as time defeated, damage caused, and number of character left and etc.) can be used to further estimate the relative strength of a specific line-up.
Breeding: while breeding, it is possible to exchange more genes rather than a single one. Moreoever, do we really need a breeding stage? Can the mutation on its own improve the line-up quality?
Mutation: the mutation strategy we demostrated here is quite basic. There are other mutation methods like probability based and sequential based mutations.
Match making: during match making, if the fighting rules have no probability involved, we could also remove duplicated matches since they will always turn out to be the same results.
Individual generation: in every individual generation stages (breeding and mutation), we could also eliminate the offspings with the existed gene sequence as those are already tested in the environment.
MORE
If you are at this stage, thank you for reading through or simply skipping through. One of the question you may ask is where is the tutorial on the system I showed in the very beginning.
This is merely a summary generated based on the fight results that we obtained through the GA process. if you are wondering what did we used to generate this fancy visualizaiton, below are some tools that you may be interested in.
Hope you find this helpful. Have fun and stay tuned. See ya!
