A literature review of genetic algorithm applied to games

Abstract

In this paper, the following work is done: The application of genetic algorithms in games is discussed, and based on reading relevant references, the design of the algorithm is explained in detail; the current situation of combining algorithms with games is analyzed; the novelty of combining algorithms with games is explained; and the paper concludes with a summary of the considerations and the scope of application of using genetic algorithms in games. The aim of the study is to reduce the cost of consultation and understanding for game makers and researchers, allowing them to focus on the specific application of genetic algorithms in games to make the AI of the game evolvable and intelligent to the level of the players.

Keywords

Artificial intelligence genetic algorithm neural networks game

1. Introduction

Many interesting things and phenomena are presented in the form of games, such as military and life. Therefore, the game is a great place to simulate and solve problems. Therefore, using genetic algorithm to simulate solving problems is often presented in the form of game.

Compared with the forward position research, the current stage of the game intelligence is still not enough. The NPC is still mainly on the traditional logic mechanism for example behavioral tree, state machine, etc. The genetic algorithm has not been adopted for the intelligent design of NPCs on a large scale.

In order to give readers a deeper understanding of what genetic algorithm is, hence, we describe some basic biological knowledge. Then popularizing the standard genetic algorithm.

As known to all, one of life phenomenon is inheritance which can make them hold some of trait from progenitor. That is called genetic. Cell is the basic structure and remove a unit to constitute life. Also, it has genes, which control biological traits. In order for trait to be inherited by future generation, cell passes genes to offspring through dividing and replicating, thus retaining this trait. After the systematic studies, it was found that the substance of determining the bio-genetic shape is a substance called a deoxycodide which is arranged in an orderly manner in the chromosome. The substantially constituent unit of deoxycodide is nucleotide. The nucleotide forms a long chain structure by combining a phosphate diester bond. Long chain is curving through hydrogen bond, finally retouching the double helix structure. A gene is given a point or segment in the chromosome, which is called a locus. The sum of all genetic substance is called the genome. Homologous staining produces new chromosomes by crossover. In germ cells, mutation is an important concept that can not be ignored. It is usually caused by error repairing after DNA replication error or DNA damage. It also can introduce a new alleles into biological population, thus increasing the genetic variation of population.

Attempting to make their own multiply, in order to adapt to the living environment, organisms will continue to change the genetic traits; this phenomenon is called evolution. According to Darwin’s theory of natural selection, when genes for survival are increasing, the pupulation will develop in the direction of adaptation to its environment, resulting in superior species.

On this basis, it leads to the key point of this paper-genetic algorithm. Genetic algorithms were designed and put forward by John Holland [1] in 1970s according to the evolution law of nature. The algorithm is simulated by computer in mathematical way, and it is an adaptive global optimization probability search algorithm. The main behaviors are as follows.

Initialization: Generate random populations with a sufficient number of individuals. Calculate fitness: Calculate the merit of individuals by means of a designed fitness function. Selection: Select the best individuals from the population. Crossover: Swap two chromosomes. Mutation: Mutation of a gene in a chromosome.

In the 1980s, it was summarized by Goldberg, and finally formed the basic framework of genetic algorithm.

Figure 1.

The basic framework of genetic algorithm.

It is important to know that, compared with other algorithms, the genetic algorithm is a robust search algorithm that can be used in complex systems and optimize computation. Using the value of the objective function as the search information, the search direction and scope are determined, which avoids the problems of function derivation, function optimization, combinatorial optimization and so on. At the same time, it has implicit parallelism and searches for the optimal solution of multiple individuals. It avoids stagnation by local optimal solution causing.

2. Application of genetic algorithm in games

All kinds of new algorithms and improved algorithms emerge in an endless stream with the progress of hardware and other technical conditions in today’s society. Also according to the evolutionary characteristics of genetic algorithms, the following narrative is made.

2.1. Suchen et al. [2] combined GA with decision making and tried to realize the ability to adapt to unknown environment artificially. That is, in a finite area with obstacles (a maze), the simulation tests how fast the machine can move from a defined point to another. Genes are represented by an array of 16 pairs, each of which has four unlabeled integers, each of which corresponds to the probability of moving in the direction.

For assessment purposes, time limits and achievement scores are given within the framework. The robot tries to move. The score is increased by 1 when the robot reaches the target point. Then it returns to the newly formed starting point and repeats the process until the end of time. Achievement scores will be included in the replication process as a fitness function.

In the experiment, a total of three different maps were used. The first map A is used for the machine to learn, and the other two maps B with mirrored structures are compared with C. It should be noted that map B is similar to map A. In the process, the robot scored higher when the maze map was similar. The results showed that the robot could understand the intent of the maze.

2.2. Zensho et al. [3] applied GA to the game of rock-paper-scissors. Adopting the rule of looking at the outcome of the last few rounds of the game and making a deterministic decision. At the same time, researchers pointed out in the paper that a wise strategy must need to pay attention to two aspects: (1) To collect the information of the opponent. (2) Don’t give so much information about yourself.

According to the situation that will occur, the researchers designed a 3-digit code length for the chromosome code to represent the last three games (each with 3 integers, that is, 0 represent the scissors, 1 represent the paper, and 2 represent the stone), a total of 27 strategies. Therefore, the code length of 27 bits is set (at this time, each bit represents the position, but also indicates the situation of the last three games at that time), and the number in each bit indicates the decision made.

In the experiment, compared with the system strategy, GA obviously has the advantage of predicting the behavior of opponents. But it is not accurate when faced with human players, because the behavior of human players is extremely difficult to predict.

2.3. Timothy et al. [4] choose to apply genetic algorithms to generate war game strategies based on the fact that the strategies of military exercises may contain uncertainties. Using the naval blockade as the scenario, Red is the opponent and Blue is the side that needs to make decisions. The game is won by making the blue side break the red side’s blockade. Red’s strength and strategy are fixed, and the information that can be known about Blue is the number of ships, their type, and their position over time.

The encoding is in the form of 12 groups with 33 bits as a group. Each group can represent a task group or a ship group. Bits 1 to 3 in a group are used to specify the type of ship, bits 4 to 5 are used to specify the number of ships, and the remaining 28 bits are used to specify movement at a given time.

And the fitness function is given as the following equation:

$\displaystyle\text{fitness}=\text{benefit}-(\text{Blue force cost}\ast(\text{% benefit}/\text{max. poss. benefit})\ast\text{weight}-\text{force}){}-(\text{game time cost}\ast(\text{% benefit}/\text{max. poss. benefit})\ast\text{weight}-\text{time})$ (1)

Two methods of estimating benefit items that have successfully achieved the goal of victory are used in terms of the overall design, which boil down to the combination of elite individual and measurement method.

2.4. Jun et al. [5] proposed a path planning and obstacle avoidance algorithm for soccer robot based on artificial potential field method and genetic algorithm.

Specifically, the sequence of line segment points connected from the starting point to the end point will be chosen as the initial sequence of path points of the first path. Secondly, the path point sequence randomly distributed in the obstacle avoidance area is used as the initial path point sequence of other paths. Then the path planning algorithm of the traditional artificial potential field method is used to make the initial sequence of path points form different obstacle avoidance paths, which forms the initial population. The details are as follows:

$\displaystyle L_{i}^{1}=||R_{i}^{1}||=\sum\limits_{j=1}^{n-1}{\sqrt{(x_{i,j+1}% ^{1}-x_{i,j}^{1})^{2}+(y_{i,j+1}^{1}-y_{i,j}^{1})^{2}}}$ (2)

$L_{i}^{1}$ is the length of the i-th path of the first generation. And the shortest distance in this set of paths can be found by Eq. (3) as the optimal individual of the first generation path.

$\displaystyle L_{\min}^{1}=\mathop{\min}\limits_{i=1}^{n-1}(L_{i}^{1})$ (3)

Individuals of each generation are seeking the shortest path, so the fitness function is designed as the difference between the longest path in a generation group and the path length of the current individual.

$\displaystyle F_{i}^{j}=\max(L_{i}^{j})-L_{i}^{j}$ (4)

If the individual path is longer, the value of the adaptation function is smaller. On the contrary, the shorter the individual path is, the larger the value of the adaptation function is, and the more it meets the demand. The selection probability of each individual was calculated by the ratio of the fitness value of each individual to the total fitness value. The sequence of points with a large distance difference has a higher probability of recombination.

Finally, the shortest path is fitted by the least square method to make it a smooth and continuous curve. It is convenient for soccer robot to control. The experimental results show that this algorithm can effectively generate obstacle avoidance paths.

2.5. Gabriella et al. [6] applied genetic algorithm to the field of checkers. According to the characteristics of checkers, GA is modified to adapt and realize the characteristics of the game. That is, each step of the operation will produce a new chromosome, regardless of whether the situation is good or bad, and the adaptation factor is used to evaluate the movement represented by the chromosome. Given several strategies, they are arranged in order of priority as follows: 1. capture more opponent pieces; 2. lose as few pieces as possible; 3. make random movements; And at the same time, setting weights for movement. With a simple moving weight of 1; The action of moving to lose pieces to the opponent, the weight of which is $-$ 5; The action of keeping the captured pieces, the weight of which is 2; The action of capturing the opponent’s pieces, the weight of which is 3.

When the algorithm is applied to checkers games, it is required as a whole to minimize the number of pieces lost by the computer, maximize the number of pieces lost by users, and avoid actions that lead to bad results. Two kinds of tests are carried out in this paper. In the first kind of human players against artificial intelligence, the AI win rate reached 52.5% in 40 games, and the second compared the performance of two different genetic algorithms in millisecond average time. Finally, the author also said that although the results are satisfactory, the random factors of the algorithm make the application less stable. And expect to add the mobile tree in the next version; the performance of the algorithm will be significantly improved through the depth tree search.

2.6. Warcraft 3 is a real-time strategy game that includes elements such as gathering resources, building bases and commanding battles. The final victory condition is determined by the destruction of the enemy race’s main base.

Figure 2.

A scene from Warcraft 3.

Jason et al. [7] used genetic algorithm to evolve the weights of artificial neural networks (ANNs), and applied it to Warcraft 3. In the game, it plays a role in deciding which units to produce to defeat the opponent. The researchers took the number of enemies of each unit type as input and the number of each unit type produced by the agent as output. At the same time, there is a limit on the number of units. The generation of units will consume food.

The residual food of the agent unit is subtracted from the remaining food of the enemy as the fitness function in the design.

$\displaystyle F=UF-EF$ (5)

The concept of elite is introduced to avoid losing good individuals in the process of optimization. Experiments show that this combination algorithm can be used as an effective adjustment technology for unit generation, and the resulting troops can also effectively defeat opponents. In the end, the researchers also pointed out a more specific research direction, that is, incremental learning and multi-objective concepts may lead to better solutions to the problem.

2.7. Hyun-Tae Kim et al. [8] successfully applied genetic algorithms to the Geometry Friends game. This is a CIC two-player competition game that involves many physics elements. Players need to go through the diamond collection by cooperating in a short time.

Figure 3.

A scene from Geometry Friends.

Then for the game, the authors et al. performed the following fitness function design.

$\displaystyle\textit{Score}=(N_{\textit{get}}\ast V_{\textit{get}})+V_{\textit% {bonus}}\ast(\max\textit{Time}-\textit{playTime})/\max\textit{Time}$ (6)

Indicates the number of diamonds collected and indicates the value of diamonds. It is a reward that will be given only after the player has collected all diamonds. Then denotes the longest game time, which indicates how long the player has been playing the game.

Based on the above adaptive functions, elite population land reservation is performed, which leads to iterations. The final set of quality parameters under rule-based is obtained.

2.8. Junru et al. [9] apply genetic algorithm to the game of gobang on a 15*15 board with two-player strategy game. This type of game is played with two players competing against each other. The victory condition is to first obtain an unbroken line of five pieces horizontally, vertically or diagonally. Based on the original population of Gobang, it is limited to a certain extent. That is, when other pieces are in the center of the chessboard, the pieces placed on the boundary are meaningless; The original total group needs to be diversified, usually composed of thousands of individuals; The roulette selection algorithm is used to randomly select the crossing points in population; Mutant genes are also randomly selected. There are also 12 chessboard modes, each with a corresponding value.

When an action makes itself about to reach a certain mode, it corresponds to its own attack value. Or when the opponent is prevented from reaching a certain mode, it corresponds to its own defense value, resulting in the fitness function is defined.

$\displaystyle f(c)=\sum\limits_{i=1}^{7}{(\textit{atk}(p_{i})+\textit{def}(p_{% i}))}$ (7)

At the same time, in order to prevent AI who attempt to obtain a higher score from choosing to not end the game, the sooner AI wins more in the game, the greater the score is given. In the experiment, the initial population was 2000 and the peak was 3500. Each time 200 individuals with the highest fitness were retained to produce the next generation. When the genotypes of the best individuals are stable for five consecutive generations, the genetic algorithm converges. The experimental results show that in the Gobang game, the genetic algorithm has a deeper search than the traditional algorithm based on a game tree, resulting in a better and more efficient solution.

2.9. Angry Birds is a game with two camps, the player’s camp is the bird camp. The victory condition is that the player needs to attack the pigs by continuously catapulting the birds and needs to defeat all the pigs in order to win.

Figure 4.

A scene of Angry Birds.

Misaki [10] of Limengguan University and others use the GA algorithm to automatically create levels for the game AngryBirds. According to the player’s current game results, the level suitable for the player’s skill level is generated by improving the fitness function and adjusting the fitness function parameters. That is, the function designed by the researchers at this time focuses on balancing the number of blocks, pigs and birds to prevent any variable from being too large or too small, thus ensuring the difficulty of the next level. The fitness function is given as the following equation.

$\displaystyle\min f_{\textit{ind}}=\frac{1}{n}\sum\limits_{i=0}^{n-1}{v_{i}+% \frac{\sqrt{(b-B)^{2}}}{M_{b}-B}}+\tanh\left(\frac{|P-p|}{2}\right)$ (8)

$v_{i}$ denotes the average magnitude of the velocity vector, $b$ and $p$ denote the number of initialized squares and pigs in the game level of interest, respectively. Also define $n=b+p$ . The parameter $B$ indicates the desired number of squares. The parameter $M_{b}$ indicates the maximum number of squares in a level segment. The parameter $P$ indicates the desired number of pigs.

In the experiment, the parameters are adjusted in real time, and 12 players are invited to test. The results show that the method proposed by the researchers can well generate game levels suitable for players, especially for players who can not play Angry Birds well.

2.10. As an RTS game, the choice of action can lead to the success or failure of a single conflict. And the overall success of the game is often based on a few skirmishes. Hsu et al. [11] tried to apply GA to StarCraft and run AI code through BWAPI.

Unlike most other AI using the three abstract levels of strategy, tactics, and reactive control, the researchers proposed in the experiment that for the actions taken by a unit, the learning model needs to be selected from a pre-set set of actions. Actions include kites that are hit and run, distance priority that is attacking the closest enemy, and blood volume priority that is attacking the enemy unit that has the lowest Hp.

And design three scenes to correspond to the above three actions. Scenario 1: Allied tanks have a longer range of attack than enemy marines. Taking action A. Scenario B: The enemy tank in the lower left corner is within range of the ally tank. Taking action B. Scenario C: It is better for all units to focus on one enemy than for each unit to engage in one-on-one combat. Action C will be taken.

Figure 5.

A scene from StarCraft.

When a chromosome is encoded, 15 gene sites are assigned to it. The first 12 bits are interpreted as whether action will be taken, and the last three indicate the priority of the operation.

Three experiments were designed for testing. They are the operation selection of unit type, the cooperation between units, and the cooperation of ground and air forces. It is noted that the length of chromosome will be changed when the last emperiment is tested.

The final experiments show that the learning model of the current framework enables troops to take appropriate actions and collaborate with other allies. At the same time, the potential research directions in the future are pointed out, such as the generation of automatic action, the competition of individuals generated by genetic algorithms, and so on.

2.11. Giovanna, Richard et al. [12] used GA’s special case GP algorithm. The GP algorithm is used to refine character combat strategies, which are initially created through a random process. The main goal is to build interesting AI characters without the need for professional developers.

In addition, there are some limitations in order to be able to fully implement the GP algorithm in games. First, the characters must follow the same rules as the human player, such as moves or tactics that can’t physically be reproduced by the human player, and the AI also can’t appear. Second, the AI’s reaction time should be on par with the human, not faster than the human player.

When the initial population is created, the actions of the game characters are manipulated by genetic operators. When defining the fitness function, the differences in individual performance should be taken into account. The selected system should be robust, not just based on simple wins and losses.

That is to say, the opponent’s technology and whether the result is achieved should be considered. Therefore, the expected score of the player is calculated using the following formula: P1 and P2 correspond to player one and player two, respectively. The rating R is adjusted whenever the game is over. K is used to control the intensity factor adjustment. S denotes the bool value regarding victory and defeat.

$\displaystyle E_{P1}=\frac{1}{1+10^{(R_{P2}-R_{P1})/400}}$ (9) $\displaystyle E_{P2}=\frac{1}{1+10^{(R_{P1}-R_{P2})/400}}$ (10) $\displaystyle R^{\prime}_{P1}=R_{P1}+K(S_{P1}-E_{P1})$ (11)

The selection method is defined by preserving the top individuals and using crossover operators to produce offspring with the chance of mutation.

They added elite individuals, descendants of elite individuals, and random individuals to the new population. Building AI characters in an evolutionary way can save a lot of costs and automatically generate a lot of different characters.

Finally, the procedure is able to create a wide diversity of participants with different strategic skills, which could be potentially used as a starting point for further adaptive process.

2.12. The pathfinding function is inevitably used in the game. The current general algorithms are A* and DijkStral, but both depend on a specific design. The former requires a static environment, while the latter needs a graph as a map. Considering that the standard genetic algorithm can not take characteristic of the advantages of the construction module. Gabriel [13] and others put forward a genetic algorithm to build the module to achieve virus infection, so that it can provide a new path to find the way when the environment changes dynamically.

Specifically, implement a function that creates a virus and propagates the virus to individual population based on the biological virus behavior. In the design of chromosome coding, the number of genes is equal to the number of points to be passed. That is, the length of genes is 8 bits.

At the same time, the fitness function is given as the following equation.

$\displaystyle f_{i}=\frac{l_{i}}{\sum\nolimits_{j=0}^{n}{d_{i,j}}}$ (12)

The individual $i$ , the life value $l_{i}$ and the distance $d_{i,j}$ together form the fitness function $f_{i}$ . $d_{i,j}$ denotes the distance of individual $i$ from waypoint $j$ to the next waypoint in the process from the starting point to the end point. And the enemy is designed on the path to be passed, and the individual needs to avoid the enemy. The virus will invade weaker individuals. And if it does sucessfully, it will randomly change the gene block. That is, if the same virus acts on the same individual, it will randomly produce different results. Once the virus has improved the fitness of the individual, its infectivity will increase. If the opposite happens, then infectivity is reduced until the virus is destroyed and new viruses are created.

After the comparison of experiments, it is shown that mutation is the key point to solve the problem of pathfinding. Among the four algorithms compared, the standard GA $+$ custom mutation algorithm and the standard GA $+$ custom mutation $+$ virus infection algorithm are more suitable for solving the pathfinding problem. At the same time, the author suggests that the crossover rate and mutation rate should be defined respectively between 70%, 80% and 5%, 10%.

2.13. Combining the advantages of various technologies into games has become a mainstream trend. Eliot et al. [14] tried to combine genetic algorithm and neural network and apply it to Super Mario in independent games. The researchers expect the combination of the two algorithms to produce an agent that can overcome the obstacles presented in the game to improve and evolve itself through the game.

Specific design-neural network part: each group has a random and exclusive neural network. What needs to be evaluated are the neural networks that lead the agents to victory. The vertical coordinate of the agent, the horizontal distance of the nearest obstacle in front of the agent and the height of the nearest obstacle in front of the agent are designed as the input layer, and the forward movement and jump are designed as the output layer.

Specific design-genetic algorithm part: the initial population has 20 individuals, each agent has its own neural network, and the weight in the neural network is randomly generated; The fitness function design is relatively simple to achieve the target score; In the selection function, each agent has the opportunity to be selected to participate in the generation of offspring, but the agent with the highest adaptability is more likely to be chosen; In the crossover function, only the replication process is performed. In the catastrophe function, the weight will be changed randomly.

2.14. Sarthak [15] and others use artificial genetic learning algorithms based on neural networks to simulate space Mario games. The input layers of 7 neurons are designed, including the vertical coordinates of the character, the vertical distance from 3 flames and the horizontal distance from 3 flames, 5 hidden layers containing 144, 72, 36, 24 and 12 neurons, respectively, and the output layer containing 1 neuron is used to control the character to avoid obstacles.

Other genetic algorithms are not much different from the standard GA.

2.15. A serious game for obstructive sleep apnea, this game requires players to participate and diagnose the condition of NPCs. The game is played mainly through debates with NPCs. The debate is simulated by means of cards. Each card has specific attributes and opinions. The player plays against the NPC in a card battle and wins this time when the player eliminates all the cards of the NPC. Kalafatis et al. [16] successfully applied genetic algorithms to a serious game for obstructive sleep apnea. For the chromosome design, a 7 genes in one chromosome were used, and the attributes contained Smoking, Alcohol, Medication, Sleeping Position, Obesity, Hypertension, and Depression. When an NPC has one of these attributes, it is assigned a value of 1, otherwise it is assigned a value of 0.

At the same time, in order to improve user engagement and provide user-friendly educational materials, it is necessary to continuously optimize the offspring. Therefore, iterative operations are performed by means of two adaptation functions. The following equations are used.

$\displaystyle\textit{WFS}=W_{a}\ast a+W_{b}\ast b+\cdot\cdot\cdot+W_{x}\ast x$ (13) $\displaystyle\textit{LFS}=L_{a}\ast a+L_{a}\ast b+\cdot\cdot\cdot+L_{a}\ast x$ (14)

WFS denotes fitness function of winning. LFS denotes fitness function of failure. Once any of $x$ linked to the user card is played wrongly or left unplayed, $W_{x}$ will add one; otherwise, $W_{x}$ will subtract one. Meanwhile, $L_{x}$ is just the opposite of $W_{x}(a,b,\ldots,x)$ represents the binary code of the individual gene. The final result of the experiment confirms the potential of genetic algorithms in serious games.

2.16. Hearthstone is a two-player turn-based game in which both players combine and play cards based on their own and their opponent’s stats. The final victory condition is to clear the opponent’s blood level to 0.

Figure 6.

A scene from Hearthstone.

H.C. Chia et al. [17] applied genetic algorithms with the expectation of finding a good chessboard evaluation criterion in order to choose the best action based on it. Thus, they designed their own fitness function after referring to others’ fitness functions. The fitness function is given as the following equation.

$\displaystyle f(x)=\sum\nolimits_{i=1}^{4}{(P_{i})}-\sum\nolimits_{i=1}^{4}{(O% _{i})+W\cdot 30}$ (15)

$P_{i}$ indicates the attributes of its own player, including blood $P_{1}$ , number of cards in hand $P_{2}$ , number of remaining cards $P_{3}$ , pawn attack points and health points $P_{4}$ ; opponent’s attributes $O_{i}$ , also as above. $W$ indicates the number of games won by the player.

An elitist structure was used for both selection and reproduction, with the top 5% of individuals retained and crossover and mutation based on a 9:1 ratio. The genetic algorithm was used to establish the board evaluation criteria for the Hearthstone game.

2.17. Legends of Code and Magic is a turn-based two-player game that requires players to select cards to build a deck at the beginning of the game. Cards have attributes such as attack, defense, and even special abilities. When the opponent’s blood level is reduced to 0, the game is won.

Figure 7.

A scene from Legends of Code and Magic.

Y. Yang et al. [18] applied genetic algorithms to the evaluation of cards by scoring functions, and then selected the corresponding cards into the deck to increase the player’s win rate. They designed three coding schemes to correspond to three adaptation functions, respectively.

In the first one, the chromosome length is 160 (corresponding to 160 cards in the game) and the score of the corresponding card is at the gene. The agent can select the card with the highest score value into the deck; the second one differentiates attributes and special abilities, and then calculates the score of the card by weighting. The third option is an extension of the second one. The genome is added to option two, representing the desired number of cards with different mana costs. While the first two adaptation functions are simpler, we show the third adaptation function formula.

$\displaystyle\textit{urgency}(i)=n_{i}/30-d_{i}/t$ (16)

$t$ indicates the current round ( $1\leqslant t\leqslant 30$ ). $n_{i}$ denotes the expected number of taps with power cost $i$ . $d_{i}$ denotes the number of cards in the current deck with mana value $i$ . Each of the design options has been subsequently used to achieve the desired effect in different experimental scenarios.

2.18. Card Wars is a game that uses MiniMax to determine the ability of the game agent, but the determination of this algorithm lies in the fact that multiple attributes of the game (attack, defense, etc.) cannot be considered simultaneously, and therefore the decisions made by the game agent are often not optimal. This led Phillip et al. [19] to consider the application of genetic algorithms to the Card Wars. The fitness function is given as the following equation.

$\displaystyle\textit{Fitness}=\frac{\sum\nolimits_{i=1}^{n}{\raise 3.01pt\hbox% {${HP_{i}}$}\!\mathord{\left/{\vphantom{{HP_{i}}2}}\right.\kern-1.2pt}\!\lower 3% .01pt\hbox{$2$}+\textit{damaga}[\textit{position}]_{i}})}{1+((\raise 3.01pt% \hbox{${total\cos t}$}\!\mathord{\left/{\vphantom{{\textit{total}\cos t}9}}% \right.\kern-1.2pt}\!\lower 3.01pt\hbox{$9$})\textit{diffSP})}$ (17)

$HP_{i}$ indicates the life value possessed by the card $i$ . $\textit{damaga}[\textit{position}]_{i}$ indicates the damage taken by the opponent. $\textit{total}\cos t$ indicates the $S P$ required to summon the desired card. diffSP indicates the difference between the opponent’s $S P$ and the NPC’s $S P$ . Successfully optimized agents have abilities that they did not have before. Not only can you save $S P$ effectively, but also can summon more powerful cards to play against.

3. Practical aspects about the application of genetic algorithms

Most of the AI systems in commercial games rely on the designs of game designers. And most of the game designers are not academic researchers. They love games, but their lack of knowledge about mathematics and science makes them rely more on experience. So, for AI design, state machines, behavior trees, and other approaches are usually used. Therefore, genetic algorithms are actually used less in commercial games.

4. The novelty of combining the genetic algorithm with the game

We need to know that genetic algorithms are usually used in image processing and robotics. In image processing, it is mainly used for image enhancement, image recovery, etc., while in robotics, it is mainly used for behavior planning, path planning, etc.

In games, state machines and behavior trees are usually used to structure AI systems. When the state machine structure is simple, it is clear at a glance and gives the AI a certain degree of intelligence. However, once the states and conditions are increased, the state machine becomes complex and the intelligence of the AI is affected to some extent, while the behavior tree uses an object-oriented design concept, which strips the behavior logic from the state data. The use of tree structure improves visualization and facilitates problem troubleshooting. It allows NPCs to perform different actions in parallel, randomly, selectively or sequentially. At the same time, the degree of AI intelligence merit at this point relies more on the designer’s experience.

The NPCs with genetic algorithm, on the other hand, are able to correspond to the player’s level. When the preliminary work is well prepared, it is equipped with evolutionary nature in the later training process. The level of intelligence of the corresponding NPC can be adjusted according to the player level.

In a small way, we need to know that the advantage of combining genetic algorithms with games is that the AI designed using it is instantaneous and diverse. The combination of the two will make the whole game rich and hierarchical. This combination is full of uncertainty compared to traditional approaches, such as using state machines. This is what players love.

On the larger side, the combination of games and genetic algorithms that we have seen in the paper has a part that requires the researcher to re-architect the corresponding game, which is an extremely time-consuming act. The other part is that the developer opens up the game framework, allowing the researcher to better apply the genetic algorithm to it. It is true that, as stated above, it is extremely rare to apply genetic algorithms to commercial games. The reason is that this combined capability is not available to smaller game companies. The companies that have both capabilities are mostly large companies. This increases the inequality of the market.

Therefore, we want to give templates that can reduce the cost of understanding for game makers about the combination of genetic algorithms and games. Make the game AI more intelligent, correspond to the level of players and keep up with the market demand. In turn, better drive the whole game market.

5. Conclusion

5.1 The following considerations should be noted

Keeping the best problem-solving game AI samples; In order to ensure that there is still space for development in the anaphase, it is necessary to retain the diversity of the game AI. According to the difference of the game, it is necessary to design the corresponding strategies that the agent will adopt to solve the problem. It is necessary to design the corresponding chromosome coding according to the type of game and the experimental test object, which focuses on the design of the corresponding meaning of code length and code. When designing the fitness function, it is necessary to design the function in line with the current situation of the game, which can be compared after multiple experiments. The difference of fitness function will have an important effect on sample generation and convergence. The probability of beneficial evolution needs to be increased appropriately based on the principles of mutation and crossover. The probability value can not be set at will. It needs to be determined after verification and comparison.

When GA is applied in games, sometimes the obtained NPCs are not intelligent enough due to premature convergence. This requires that the population size is large enough when training is performed. When GA is used in games, it increases the amount of algorithm and time of the system. These are the things that need to be noted.

5.2 After combining other algorithms, the main points for attention are

The focus will not be on the most basic chromosome coding, but on the use of genetic algorithms to embed other algorithms as a whole. For example, when genetic algorithm is combined with neural networks, we can not only cross-reorganize the neural network structure, but also focus on choosing the neural network that scores better in the game or performs better in other ways. It is necessary to make behavior design correspond to solving game problems in the context of combination. The focus can be placed on other algorithms at this point, such as the design of the input layer and output layer of the neural network. The distance solution of the point sequence under the artificial potential field method, and so on.

In general, the most important point of genetic algorithm is its evolution. Choosing the best samples at the moment by constantly simulating natural selection. Thus, when the genetic algorithm is applied to a game, it is natural to select the AI population that is best suited to the game environment. At the same time, the AI can be updated to make the game smarter by constantly changing and optimizing the fitness function.

For game companies, AI with varying degrees of intelligence under the genetic algorithm can be retained to correspond to players of different game levels. In the guarantee of competitive at the same time, there is no lack of entertainment (The level of the player and the AI level are equal).

5.3 The scope of application of genetic algorithms combined with games

At the same time, genetic algorithm has a biased choice for game types. Competition NPCs in games such as real-time strategy, FPS, fighting and adventure are the primary embedded object of genetic algorithm. Uncertainty and immediacy are the most desired and significant features of real-time strategy, FPS, combat and adventure games. Genetic algorithms are used to frame the chromosomes and design the corresponding adaptive functions according to the game situation, which eventually allows the NPCs in the system to react differently and instantaneously. Therefore, genetic algorithms are mainly used for the design of NPCs in real-time strategy, FPS, combat and adventure games.

For drama, romance and other games, they mainly interact with the player through drama, unlocking and collecting cards. The immediate feedback of the game is fixed by the staff and there is no possibility of changing it. Genetic algorithms, on the other hand, are characterized by the need to frame the chromosomes and design the corresponding adaptive functions. This property is what allows the NPCs in the system to react differently instantly. So they are not in the range of games where genetic algorithms need to be applied. Therefore, genetic algorithms are not applicable to games in drama, romance, etc.

Footnotes

Acknowledgments

This research work is funded by project 0054/2021/A granted by the Science and Technology Development Fund of Macau (FDCT). The authors would like to express their appreciation for the support provided by the fund.

References

Holland

. Outline for a logical theory of adaptive systems. Journal of the ACM. 1962; 9(3): 297-314.

Tsuchiya

. Learning of a maze using a genetic algorithm. Proceedings of IECON ’93 – 19th Annual Conference of IEEE Industrial Electronics. IEEE; 1993. pp. 376-379.

Chen

Ali

Nakao

. Playing the Rock-Paper-Scissors game with a genetic algorithm. Proceedings of the 2000 Congress on Evolutionary Computation CEC00 (Cat No00TH8512). IEEE; 2000. pp. 741-745.

Revello

McCartney

. Generating war game strategies using a genetic algorithm. Proceedings of the 2002 Congress on Evolutionary Computation CEC’02 (Cat No02TH8600). IEEE; 2002. pp. 1086-1091.

Xie

. Path Planning and Obstacle-Avoidance for Soccer Robot Based on Artificial Potential Field and Genetic Algorithm. 2006 6th World Congress on Intelligent Control and Automation. IEEE; 2006. pp. 3494-3498.

Barros

GAB

Carvalho

LFBS

Silva

VRM

Lopes

RVV

. An Application of Genetic Algorithm to the Game of Checkers. 2011 Brazilian Symposium on Games and Digital Entertainment. IEEE; 2011. pp. 63-69.

Tong

Teo

Kiring

AMK

. Evolving Neural Controllers Using GA for Warcraft 3-Real Time Strategy Game. 2011 Sixth International Conference on Bio-Inspired Computing: Theories and Applications. IEEE; 2011. pp. 15-20.

Kim

. Hybrid of rule-based systems using genetic algorithm to improve platform game performance. Procedia Computer Science. 2013; 24: 114-120.

Wang

Huang

. Evolving Gomoku solver by genetic algorithm. 2014 IEEE Workshop on Advanced Research and Technology in Industry Applications (WARTIA). IEEE; 2014. pp. 1064-1067.

10.

Kaidan

Chu

Harada

Thawonma

. Procedural generation of angry birds levels that adapt to the player’s skills using genetic algorithm. 2015 IEEE 4th Global Conference on Consumer Electronics (GCCE). IEEE; 2015. pp. 535-536.

11.

Hsu

Chen

. Learning to select actions in starcraft with genetic algorithms. 2016 Conference on Technologies and Applications of Artificial Intelligence (TAAI). IEEE; 2016. pp. 270-277.

12.

Giovanna

Cant

Woods

. Creating AI Characters for Fighting Games Using Genetic Programming. IEEE Transactions on Computational Intelligence and AI in Games. 2017; 9(4): 423-434.

13.

Galam

Dias

Remedio

TPR

. Viral Infection Genetic Algorithm with Dynamic Infectability for Pathfinding in a Tower Defense Game. 2019 18th Brazilian Symposium on Computer Games and Digital Entertainment (SBGames). IEEE; 2019. pp. 198-207.

14.

Bytyçi

Hulaj

Aliu

. Combination of Genetic Algorithm and Neural Network for Independent Game Playing. 2020 International Conference on Intelligent Data Science Technologies and Applications (IDSTA). IEEE; 2020. pp. 106-109.

15.

Rawat

Nijhawan

. Neural Networks based Hand-crafted genetic learning approach to simulate Space Mario Game. 2020 International Conference on Smart Electronics and Communication (ICOSEC). IEEE; 2020. pp. 1-5.

16.

Mitsis

Kalafatis

Zarkogiann

Mourkousis

Nikita

. Procedural content generation based on a genetic algorithm in a serious game for obstructive sleep apnea. 2020 IEEE Conference on Games (CoG). IEEE; 2020. pp. 694-697.

17.

Chia

Yeh

Chiang

. Designing Card Game Strategies with Genetic Programming and Monte-Carlo Tree Search: A Case Study of Hearthstone. 2020 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE; 2020. pp. 2351-2358.

18.

Yang

Yeh

Chiang

. Deck Building in Collectible Card Games using Genetic Algorithms: A Case Study of Legends of Code and Magic. 2021 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE; 2021. pp. 01-07.

19.

Phillip

Permana

SDH

Cendana

. Modification of game agent using genetic algorithm in card battle game. IOP Conference Series Materials Science and Engineering. 2021; 1098(6): 062011.