Generating Behavior-Diverse Game AIs with Evolutionary Multi-Objective Deep Reinforcement Learning

1 Introduction

Gaming is at the heart of the entertainment business, and the game market is rapidly growing along with fierce competition. According to the latest Global Games Market Report [Newzoo, 2019], there are over 2.5 billion active gamers across the world, and over $164 billion will be spent on games in 2020. With such a vast and competitive market, the game quality like the entertainment and attraction becomes especially important, as they greatly determinate the success of a game. For instance, a Game AI with monotonous behaviors in a battle game is tedious and will sharply degrade the player's enthusiasm, resulting in losing users or even the failure of a game. To keep the entertainment, game companies put many efforts (e.g., continuously creating new behaviors), but often achieve limited progress [Alt, 2004]. Consequently, a more effective approach to create behavior-diverse Game AIs is of great importance and meaning for game companies.

⋇ The first two authors contributed equally.

† Corresponding author.

One simple way to create Game AIs is to model the human players' behavior [Holmg˚ard et al., 2014; Ortega et al., 2013; Drachen et al., 2009] using collected data. However, sufficient data is required in advance and the resulting AI's behavior is prone to biased to the training data. Another piratical way is behavior tree (BT) [Millington, 2019], which is extensively adopted in designing Game AIs, including Red Dead Redemption [Rockstar Games, 2018] and Halo [Isla, 2008]. However, BT is a rule-based method, requiring abundant designer expert knowledge and labor cost in designing rules. Besides, contrived rules may be contradictory, leading to potential bugs. Lastly, the more rules in BT, the harder it can be maintained, restricting its effectiveness in large scale games. Meantime, evolutionary algorithm (EA) has also been utilized to generate diverse game AIs [Mouret and Clune, 2015; Lehman and Stanley, 2011; Agapitos et al., 2008]. However, EAs adopts heuristic search which may be inefficient in modern complex games [Szita et al., 2009].

Deep reinforcement learning (DRL) has achieved great success in generating competitive Game AIs for various kinds of games [Zheng et al., 2019; Zheng et al., 2018; Mnih et al., 2015]. However, DRL mostly focuses on winning the game, restricting its ability to generate diverse behaviors. The aforementioned Game AIs design methods suffer from the following limitations: 1) the necessity of human behavioral data; 2) heavy dependence of designer expert knowledge and substantial labor costs in searching a desirable behavior; 3) lacking the ability to generate diverse behaviors.

To address these, we propose a new framework, named Evolutionary Multi-Objective Game Intelligence (EMOGI), combining the power of evolutionary multi-objective optimization (EMO) and DRL to generate behavior-diverse Game AIs with barely prior human knowledge. It is worth mentioning that EMOGI requires no pre-collected human behavioral data and directly generates Game AIs from scratch. To minimize the dependence of prior knowledge and labor costs in behavior searching, EMOGI leverages the power of evolutionary algorithm to achieve automatic parameter tuning of the reward function in DRL, guiding the policy learning towards the desirable behavior automatically. On the other hand, to generate diverse behaviors, the prioritized multiobjective optimization is introduced, which leverages the non-dominated sorting and crowding distance sorting to ensure the learned policies distributed among multiple objectives, where various kinds of behavior-diverse Game AIs can be selected for games.

For evaluation, EMOGI is adopted to design behaviordiverse Game AIs for a Atari game and a commercial massively multiplayer online game. Empirical results show that, compared to existing baselines, EMOGI can achieve not only generate Game AIs with barely prior human knowledge but also behavior-diverse Games AIs effectively and efficiently.

2 Preliminaries

2.1 Markov Decision Process

Game playing is a process of successive interactions where the player (i.e., agent) need to take a sequence of actions based the observations (e.g., images) to achieve a specific objective (e.g., winning). Game playing can be modeled as a Markov Decision Process (MDP), which consists of a tuple (S,A,R, T, γ), where S is the set of states and usually referred to as the observations, A is the action space that the player used for game playing, R(s, a) is the reward function S × A → R giving an immediate feedback after taking action a at state s , T(s, a, s′ ) is the transition function S ×A× S → [0, 1] giving the probability of transiting into the new state s′ after taking action a at state s, and γ ∈ [0, 1] is a discount factor [Sutton and Barto, 2018].

2.2 Asynchronous Advantage Actor-Critic

Asynchronous Advantage Actor-Critic (A3C) [Mnih et al., 2016] is one of the state-of-the-art DRL algorithms, aiming to train agents to play games. A3C maintains a policy π(a|s; θ) and an estimation of the value function V (s; θv) parameterized by θ and θv, respectively. During game playing, the agent (actor) will execute action a following π(a|s; θ) and receive an immediate reward signal rt, which will be used by the critic to learn the value function V (s; θv). The value function V (s; θv) will be used to optimize the policy π(a|s; θ) to maximize the cumulative rewards ∑∞t=1 rt received during entire game playing using the gradient as follows:

where st, at, rt, st+1 are sampled by the actor. Notable, A3C leverages multiple asynchronous agents (critics) to simultaneously explore the environment, dramatically speeding up the efficiency of exploring, sampling and policy learning.

2.3 Multi-Objective Optimization

Evolutionary multi-objective optimization (EMO) [Deb et al., 2000] is an effective method for solving optimization problems with multiple objectives. Different from the standard evolutionary algorithm (e.g., genetic algorithm) which evaluates the solution using a scalar fitness value and optimizes from a single objective perspective, EMO uses vectors and achieve optimization from a multi-objective perspective. In such a way, offspring evolved from the EMO can simultaneously achieve high performance regarding multiple objectives and better diversity among multiple objectives.

3 ProblemFormulation

Generating behavior-diverse Game AIs is critical for guaranteeing a game's entertainment and popularity. This section formulates this problem by three parts: 1) necessary notions; 2) generating a policy with desirable behaviors and 3) the challenges in generating diverse behaviors.

Notions

Game AI refers to an intelligent agent who can play games using different policies π, resulting in different behaviors. From the design perspective, behaviors with strong characteristics are more attractive (e.g., an aggressive Game AI in combat games). To measures aggressiveness, a natural way is to count the opposite duration spent in games, as an aggressive Game AI tends to finish the game quickly. Similarly, the average distance between agents is a feasible measurement for defensiveness since a defensive Game AI will keep a large distance from the opponent to avoid damage.

Formally, the opposite duration and average distance are referred to as the game business indicators (denoted by Iduration 1 and Idistance). Given a policy π, the aggressiveness and defensiveness can be measured by:

where Sagg(π) and Sdef(π) denote the extent of a policy exhibiting an aggressive/defensive behavior, respectively. It is worth mentioning that S(π) is used for measuring the policy after the policy is learned, not guiding policy learning.

Behavior Generation

Utilizing DRL to generate a policy with desirable behavior characteristics is non-trivial, requiring tremendous domain knowledge and labor-costs. One reason is that the behavior of the policy π depends on the reward function R(s, a), which mostly focuses on winning the game. To generate desirable behaviors, one effective method is the reward shaping, adding behavior-related reward items in R(s, a) to affect a policy's behavior [Oh et al., 2019; Suay et al., 2016]. The reward function can be shaped as follows:

where ri is a reward shaping item associated with weight wi. For instance, we can set Rw(s, a) = w1 ∗rdamage +w2 ∗rinjury, where rdamage and rinjury are adopted to encourage damaging the opponent and avoiding getting hurts, respectively. Different weights w = {w1,w2} may lead to different behaviors. Increasing w1 and w2 tends to create aggressive and defensive behaviors, respectively. Therefore, adjusting weights contributes to guiding DRL towards desirable behaviors.

1 Iduration = 1 - t, where t is the normalized time spent in games.

It should be emphasized that the reward shaping item ri and indicator value I are different. The former constitutes the reward function, guiding DRL towards a desirable behavior, and the latter measures the degree of a policy having a certain behavior characteristic. Besides, indicators like Iduration and Idistance can only be measured after playing, making them unusable in the reward shaping.

Challenges

Manual weights tuning requires abundant domainknowledge. Even a slight change in the weight may result in unpredictable behaviors. Fig. 2 is a schematic diagram briefly describing the relationship between weights and an aggressive behavior, where one can find that most of the combinations (in the x- and y-axis) are incapable of achieving significant aggressiveness (yellow areas). Only a few combinations (around the red dot R∗ ) can create target behavior, which are hard to find by manual weight tuning.

4 EMOGI

We propose a new framework, named EMOGI, to generate behavior-diverse Game AIs with barely prior human knowledge. Overall, EMOGI is built on an evolutionary framework like population-based training (PBT) [Li et al., 2019; Jaderberg et al., 2017]. However, in addition to the policy, EMOGI treats the reward function as a part of the candidate

Algorithm 1: EMOGI

• 16 until the stop criteria is satisfied;
• 17 return P;

(denoted by (πiθ , Riw ) in Fig. 1). By evolving the w, EMOGI achieve automatic weights tuning, guiding DRL learning towards the desirable behavior. Another innovative difference is that EMOGI leverages multi-objective optimization to select policies with different behaviors, guaranteeing the diversity of the populations.

4.1 Generating Single Behavior

EMOGI aims at generating desirable behaviors by automatic weights tuning without human intervention. Specifically, as shown in Alg. 1, EMOGI initializes a population of candidates, each of which is a pair of πθ (a neural network parameterized by θ) and Rw(s, a) (parameterized by w). To create new offspring, EMOGI performs single-point crossover (SPX) on network parameters with a minimal performance loss, and simulated binary crossover (SBX) on reward weights (Line 8-10) [Deb and Agrawal, 1994]. Then Gaussian noise (GN) is adopted to mutate both parameters. As shown in Fig.1, SPX and GN are adopted to crossover and mutate the network parameters θ, leading to new θ′ . As for reward weights w, EMOGI uses the SBX and GN to achieve crossover and mutation, resulting in new w′ . Once finished, the newborn policy πθ′ is trained using a DRL algorithm, guided by the newly tuned reward function Rw′ towards new behaviors (line 10). After training, each candidate is evaluated to obtain their performance regarding a given game business indicator. Assume an aggressive behavior is required and duration indicator Iduration is adopted to measure a policy's aggressiveness (i.e., Sagg(π) = Iduration). Individuals with higher Iduration will be kept for further evolution, while the rests are eliminated. This evolutionary cycle repeats until reaching a certain number of iterations. In this way, policies in the last population will have high Sagg(π) = Iduration, achieving a significant aggressive behavior without any manual parameters tuning.

To boost efficiency, EMOGI divides the population and distributes them to multiple servers to achieve asynchronized evolution including: crossover, mutation, DRL training and evaluation (asynchronized part in Alg. 1). Each evolved candidates will be sent to the collector server and added into a synchronized set Q. Once the size of Q reached a threshold n, PMOO is adopted to select better offspring as the next new population (line 14 in Alg. 1).

4.2 Generating Diverse Behaviors

Evolving the whole population towards one behavior style will restrict the population's behavioral diversity. To address this, EMOGI proposes the prioritized multi-objective optimization (PMOO), where different behavior styles are regarded as different optimization objectives. PMOO optimizes policies towards multiple styles, requiring policies to be evaluated from multiple aspects and resulting in two differences: 1) the policy measurement and 2) the offspring selection.

PMOO uses multiple indicators to measure a policy's performance regarding different behavioral characteristics. Take a combat game for instance, given a policy π, the duration and distance indicators Iduration, Idistance are adopted to respectively measure the aggressiveness and defensiveness of π (denoted by Sagg(π), Sagg(π)). Thus, policy π can be measured regarding two kinds of behavioral styles as follow:

where Sagg(π) and Sdef(π) are regarded as two optimization objectives, spanning a two-dimensional optimization space, where each policy is located (right part in Fig. 1).

For offspring selection, PMOO proposes the domination relation to achieve vector-based comparison between policies. Specifically, we say policy π0 dominates π1 (denoted as π0 ≻ π1) if and only if (Sagg(π0) > Sagg(π1) ∧ Sdef(π0) ≥ Sdef(π1)) or (Sagg(π0) ≥ Sagg(π1) ∧Sdef(π0) > Sdef(π1)). Intuitively, π0 ≻ π1 means π0 is better than π1 regarding at least one optimization objective, while the rest no worse.

The set of all "best" candidates constitutes a Pareto-optimal frontier (denoted by Fi in Fig. 1). Each policy in Fi cannot dominate each other (e.g., π0 is more aggressive while π1 is more defensive). The visualization of offspring selection is depicted in Fig. 1 (right part), and the pseudo-code is outlined in Alg. 2. Given a population P , the Pareto-optimal frontier is identified using the non-dominated sorting [Deb et al., 2000], and added into the new population, then removed from the original population (e.g., F1, F2, F3, ... in Fig. 1). This process repeats until the size of the new population reaches a

Input : P: the population, n ≤ |P|: the number of candidates to be selected Output: P ′ : the selected population 1 P ′ ← ∅ 2 loop 3 F = ND Sort(P) ▷ select the Pareto frontier fromP 4 if |P ′ | + |F | ≤ n then 5 P ′ ←P ′ ∪F 6 P = P \ F 7 else 8 F ′ ← CD Select(F, n - |P ′ |) ▷ squash set. 9 P ′ ←P ′ ∪F ′ 10 break 11 return P ′

pre-defined threshold (line 3-7 in Alg. 2). Note that, F1 generally exceeds F2 because ∀π ∈ F1.(∄π′ ∈ F2, π′ ≻ π). Once the size of the new population P ′ adding the current Pareto frontier Fi exceeds the threshold n, only n- |P ′ | candidates in the Fi can be selected in to the P ′ (Line 8-10). An intuitive example is given in Fig. 1, where only part of the F3 can be selected. To achieve this, PMOO measures the density of each candidate in F3 and selects sparse candidates to construct a more diverse offspring (line 8). Intuitively, the density of π1 is computed based on the distance between two nearest surrounding neighbors regarding in terms of two objectives (i.e., d1 + d2 + d3 + d4). Candidates with sparser density will be selected as the new offspring.

In this way, EMOGI can generate not only desirable behaviors by evolving policy towards two objectives (aggressive/defensive styles), but also behaviors (e.g., a neutral style) evenly distributed among two objectives. As such, where designers can conveniently choose whichever in need of games.

4.3 Generating Complex Behaviors

A single indicator is insufficient to create complex behaviors like "hit-and-run", which exhibits a defensive behavior but need to win eventually. Maximizing Idistance will result in a behavior that is always avoiding without attacking.

To create such complex behaviors, EMOGI proposes to evaluate the extent of a policy exhibiting complex behaviors as follows:

where the win rate indicator Iwin-rate is introduced and Iwin-rate measures the win rate of a given policy. To compare policies regarding a complex behavior (e.g., "hit-and-run"), we propose a prioritized element-wise comparison as a complement to the domination relation. For instance, π0 is better than π1 in achieving a "hit-and-run" behavior only when: 1) it has a larger Iwin-rate regardless of Idistance; or 2) the same Iwin-rate but larger Idistance. This comparison guarantees that indicators in the front will be firstly considered than the latter. In this way, PMOO will select offspring with higher value in both [Iwin-rate, Idistance], whereby the "hit-and-run" behavior is achievable.

Consecutive frames before the Game AI score the 21st point (win)

5 Experiments

This section presents empirical results on an Atari game pong and a commercial game Justice Online (JO). Both games use build-in AIs as the opponents. Comparisons between EMOGI and A3C are conducted to verify their effectiveness in generating behavior-diverse Game AIs. Besides, we visualize all generated behaviors for further comparison 2 . It is worth mentioning that, due to parameters tuning heavily dependents on domain knowledge, to ensure the fairness, experienced frontline designers are invited to tune the weights in reward function for A3C, and all baselines use the same hyper-parameters defined in [Mnih et al., 2016].

5.1 Atari Game

Atari pong is a widely used benchmark where an agent controls the green paddle (using 6 actions) to play the game. We investigate the effectiveness of EMOGI in generating competitive Game AIs with diverse behaviors (e.g., busy/lazy styles). To be fair, all methods uses the same reward function as follows:

where rwin, rpaddle-move and ract encourage the agent to win, move positions and take fewer actions, respectively. Specifically, the rwin = 1 if the agent scores otherwise 0. The rpaddle-move = 1 if the the paddle's position changes otherwise 0 (the red rectangle). The ract = -1 if any actions is taken otherwise 0. In A3C, weights are manually tuned by designers to create Game AIs, however, EMOGI leverages automatic tuning. The busy/lazy styles are treated as two optimizing objectives by EMOGI, which can be measured as follows:

where Iwin-rate is the win rate. Imove-rate calculates the percentage of frames when the paddle moves, and Ino-act-rate counts the percentage of frames when the agent takes no actions.

Generating Diverse Behaviors. Fig. 3 visualizes the different behaviors generated by EMOGI, where one can find that two styles vary greatly. Both AIs can win the game, but the busy one moves more frequently than the laze one 3 . Another evidence is that busy AI has a dense position distribution than laze AI. These complex behaviors are achieved by EMOGI with automatic parameter tuning without human intervention.

2 More details in https://sites.google.com/view/ijcai20-emogi

Quantitative Comparisons. To investigate the effectiveness of EMOGI in generating diverse behaviors, Game AIs' behaviors are evaluated quantitatively regarding related game business indicators. Fig. 4 (left) visualizes the distribution of all Game AIs created by EMOGI among two optimization objectives (i.e., busy/lazy styles). EMOGI can generate not only extreme styles (lazy- and busy styles) along with two objectives but also more neutral AIs evenly distributed among them. Fig. 4 (right) demonstrates that all Game AIs can win the game (green bar) but exhibits different behaviors.

Evaluation results of Game AIs generated by EMOGI and A3C are summarized in Tab. 1. To be fair, both A3C and EMOGI are trained using the same number of runs (around 1 million episodes). One can find that A3C has limitations in generating desirable behaviors via manual parameter tuning. For instance, the busy AI high value in Imove-rate but fails to win. Besides, the neutral AI, generated by A3C, not only lose the game but also fails to perform neutrally.

By contrast, the busy and lazy AIs created by EMOGI not only achieve higher busy (0.954) and lazy degree (0.966) than the ones learned by A3C, but also be able to win the game. This demonstrates the effectiveness of EMOGI in learning complex style automatically. Another advantage is that the neutral AI, generated by EMOGI, achieves 0.557 busy degree and 0.531 lazy degree, making itself a suitable neutral Game AI, which, however, is hard to obtained by A3C.

3 Video of busy/lazy styles: https://youtu.be/1uEWhIxmGVc

5.2 Justice Online

In Fig. 5, a commercial game (JO) is adopted for evaluation. To make our study feasible, we only select one combat scenario, where an easy-to-kill wizard needs to uses 17 different actions to beat a hard-to-kill fighter. EMOGI and A3C are adopted to create (aggressive/defensive) behaviors for the wizard by tuning the reward function as follow:

where rwin, rdamage and rinjury encourage to win, attack and avoid the opponent, respectively. The rwin will be a large positive scalar if the agent wins otherwise 0. The rdamage, rinjury are the damages to the enemy and the agent received, respectively. The agg/def styles are treated as two optimizing objectives by EMOGI, which can be measured as follows:

where Iwin-rate, Iduration and Idistance measure the win rate, opposite duration spent in game and averaged distance between agents, respectively. Note that, high Iduration means finish game quickly.

Generating Diverse Behaviors. Fig. 5 (c,d) visualizes the behavior of the aggressive/defensive AIs (denoted by Agg/Def AI) generated by EMOGI, where two styles vary greatly. The Agg AI always attack, barely moving, producing shorter trajectories. By contrast, Def AI creates longer paths by running around the field to avoid the opponent (known as the "hit-and-run"). More importantly, both styles succeed in defeating the opponent, confirming the ability of EMOGI in generating complex and diverse behaviors (see video: https://youtu.be/5eps0YLY-lM).

Quantitative Comparisons. Fig. 6 (left) visualizes the distribution of all Game AIs created by EMOGI among two optimization objectives. In Fig. 6 (right), all generated Game AIs can defeat the opponent in different ways. Def AI defeats the opponent by keeping a safe distance (in Fig. 5(d)). Agg AI exhibits aggressive behavior, like constant attack without moving (in Fig. 5(c)). Tab. 2 shows that EMOGI can generate better behaviors than A3C from a numerical perspective (e.g., Agg/Def AI with bold values). Besides, A3C fails to create an Agg AI to win, which, however, can be generated by EMOGI. Both A3C and EMOGI are trained using the same number of runs (around 27 million episodes). But A3C still fails to find a desirable behavior (e.g., Agg AI and Netural AI).

6 Conclusion

This paper proposes EMOGI, aiming to efficiently generate behavior-diverse Game AIs by leveraging EA, PMOO and DRL. Empirical results show the effectiveness of EMOGI in creating diverse and complex behaviors. To deploy AIs in commercial games, the robustness of the generated AIs is worth investigating as future work [Sun et al., 2020].

Acknowledgments

The work is supported by the National key R&D program of China (Grant Nos.: 2018YFB1701700), National Natural Science Foundation of China (Grant Nos.: 61702362, U1836214), new Generation of Artificial Intelligence Science and Technology Major Project of Tianjin (Grant Nos.: 19ZXZNGX00010), Singapore National Research Foundation, under its National Cybersecurity R&D Program (Grant Nos.: NRF2018NCR-NCR005-0001), National Satellite of Excellence in Trustworthy Software System (Grant Nos.: NRF2018NCR-NSOE003-0001) and NRF Investigatorship (Grant Nos.: NRFI06-2020-0022).