Reading Literature

IMPROVING ADAPTIVE GAME AI WITH EVOLUTIONARY LEARNING

Since the birth of computer games, artificial intelligence (AI) has been a standard feature of games - especially with developers' emphasis on single-player games, which today still represent the majority of released titles.

1.2.1 Online Learning

Online learning entails that the AI will adapt during play after the game has been released. It allows opponents to automatically repair weaknesses in their scripts that are exploited by the human player, and to adapt to changes in human player tactics and playing style. For online learning to work in practice, it must be fast, effective, robust and efficient.

• Fast: Since online learning takes place during gameplay, the learning algorithm should be computationally fast, lest it will disrupt the pacing of the game.

• Effective: Adapted scripts should be at least as challenging as manually designed ones, and therefore the learning mechanism must guarantee the generation of mostly effective AI. This requirement excludes random learning methods, such as evolutionary algorithms.

• Robust: The learning mechanism must be able to cope with a significant amount of randomness inherent in most commercial gaming mechanisms.

• Efficient: The learning process should learn efficiently, relying on just a small number of trials. This requirement excludes slow-learning techniques, such as neural networks, evolutionary algorithms and reinforcement learning.

Dynamic scripting (Spronck et al, 2003) is an unsupervised online learning technique for commercial computer games. In dynamic scripting, the rules used in a script that controls an opponent are extracted from an adaptive rulebase that contains only manually designed rules. The probability that a rule is selected for a script is influenced by a weight value that is associated with each rule. The rulebase adapts by changing the weight values to reflect the success or failure rate of the corresponding rules in scripts.

The dynamic scripting technique meets all four requirements. First, it is computationally fast, because it only requires the extraction of rules from a rulebase and the updating of weights once per game. Second, it is effective, because all rules in the rulebase are based on domain knowledge. Third, it is robust because rules are not removed immediately when punished. Finally, Spronck et al. (2003) showed that in a simulated as well as a commercial game environment dynamic scripting can adapt rapidly to static or changing tactics, and therefore it is also efficient.

1.2.2 Offline Learning

Offline learning entails that the AI will adapt by self-play, without human intervention. Adaptive technologies are giving developers a tool that can help them optimize computer game AI parameters offline during the Quality Assurance phase of game development. AI tuning is always somewhat problematic; in commercial games

there can be hundreds of parameters that can affect the AI’s style of play. Testing every combination is an impossible task, especially given the short amount of time available for AI tuning. Over time, an offline learning mechanism can test out many more AI variations than an individual developer could.

An interesting application of offline learning is creating new strategies and tactics for opponent AI by self-play. Offline learning therefore provides the means of improving the dynamic scripting process by discovering new strategies and tactics that can be added to the dynamic scripting rulebase. This can make the dynamic scripting

technique more effective in dealing with human player tactics which the developers did not foresee, and for which they did not add any rules to the rulebase as countermeasures.

Research Question 1: Is it possible to design and implement an evolutionary algorithm that discovers new tactics and strategies for real-time strategy games? Research Question 2: Will offline discovered tactics and strategies enhance the performance for the dynamic scripting rulebase?

1.4 APPROACH

To answer the research question, we address four main objectives:

1) Selecting a flexible, state-of-the-art RTS game environment for our experimental research.

2) Designing and implementing the dynamic scripting technique in the selected RTS game and demonstrating that it works against several opponent strategies on several maps.

3) Applying offline learning using an evolutionary algorithm to discover new strategies and tactics in the selected RTS game.

4) Translating offline-discovered strategies and tactics into rules for the rulebase and show that these additions enhance performance for dynamic scripting in the selected RTS game.

2.1 RULE BASED ARTIFICIAL INTELLIGENCE IN GAMES

Rules-based AI is currently the technology of choice for AI development because (1) these approaches are familiar, taking their principles from familiar programming paradigms, (2) rule based designs are generally predictable, hence easy to test and debug and (3) most developers lack any training in, or knowledge of, the more complex AI technologies, and thus don't use them when deadlines are approaching fast. Currently the most dominant rule based AI techniques for computer games include scripting and state machines.

Scripts have four main advantages; they are (1) understandable, (2) easy to implement, (3) easily extendable, and (4) useable by nonprogrammers (Tozour 2002b).

A finite state machine is a logical hierarchy of rules and conditions that can only be in a finite number of states, each state having its own behavior, and its own trigger. Finite state machines are used more frequently in computer games than any other AI technique (Sweetser 2002) because they are (1) simple to program, (2) easy to understand and debug, and (3) generally enough to be used for any problem (Rabin 2002). One drawback is that using simple finite state machines leads to predictability of game AI. When using fuzzy states and fuzzy transitions rather than a finite set of states and transitions, a variety of different responses to a given set of stimuli can be generated, consequently producing ‘unpredictable’ behavior.

2.2 MACHINE LEARNING AND ADAPTATION IN GAMES

Indirect adaptation: Indirect adaptation occurs when alternations are made to certain aspects of behaviour based on statistics in the game world. The decisions as to what statistics are extracted and their interpretation in terms of necessary changes in behavior are all made by the AI designer (Manslow 2002).

Direct adaptation: Direct adaptation applies optimization or reinforcement learning algorithms to directly change the AI’s behavior on the basis of assessments of its performance in the game world (Manslow 2002). Basically, the learning algorithms searches for AI parameters that offer the best performance, i.e. search for the best behavior. Direct adaptation is generally not efficient and hard to control, making it difficult to debug. Furthermore, it is difficult to design an appropriate performance

measure (fitness function). However, direct adaptation has the major advantage of not limiting the opponents’ AI behavior and it requires minimal human direction. BLACK & WHITE, illustrated in Figure 1, proves that direct learning can successfully be applied in computer games (Barnes 2002).

2.3 INTRODUCTION TO EVOLUTIONARY ALGORITHMS IN GAMES

Traditionally, optimization techniques start with one potential solution to a problem and then gradually adapt this solution in order to reach an optimum. Evolutionary algorithms (EA’s) work with a population of solutions. These solutions are often encoded and are then called chromosomes. Each gene in a chromosome represents a variable or aspect of the solution. The chromosomes in the population are assigned a fitness value. The fitness value indicates how successful this solution is in solving the problem, compared to other solutions in the population. To generate new solutions, the EA applies genetic operators to existing solutions. Genetic operators that need only one parent solution are called mutation operators. Mutation takes one chromosome as parent and inserts, deletes or replaces genes to produce a new child. Genetic operators that need more parents are called crossover operators. Crossover occurs when parent chromosomes are combined to form a child chromosome.

REAL-TIME STRATEGY GAMES

3.1 INTRODUCTION TO REAL-TIME STRATEGY GAMES

In most RTS games, the key to winning lies in efficiently collecting and managing resources,

and appropriately distributing these resources over the various game elements. Typical game elements in RTS games include the construction of buildings, the research of new technologies, and combat.

Planning for military success in a RTS game can be divided into two separate categories: strategies and tactics. While tactics cover small-scale interactions, such as scouting the battlefield or capturing an enemy city, strategies are all encompassing (Ramsey 2004). Generally, the most valued strategic principles are unity of command (desire for one central leader), control of an objective (having a battle plan and sticking to it), flexibility (the ability to change battle plans), economy of force (divide forces

and resources appropriately among potential conflicts), initiative and mass (Dunningan 2003).

3.3 SELECTION REQUIREMENTS FOR THE GAME ENVIRONMENT

1) The game environment required being easily accessible and changeable

2) The game environment should include a scripting language, preferably with a sophisticated AI API, able to support learning techniques.

3) Preferably experiments in the environment should be fast.

4) The game environment must be state-of-the-art in terms of gameplay, meaning that game will have to incorporate non-trivial AI.

3.4 STRATAGUS

Stratagus is a sophisticated RTS engine that can be used to build real-time strategy games similar to WARCRAFT II, COMMAND & CONQUER, STARCRAFT, AGES OF EMPIRES, etc.

Scripts in Stratagus are defined in the high-level scripting language LUA, currently one of the most popular scripting languages for games. LUA is a powerful but surprisingly comfortable scripting language and is perfectly able to implement sophisticated AI techniques such as dynamic scripting and evolutionary algorithms.

DYNAMIC SCRIPTING FOR REAL-TIME

STRATEGY GAMES

4.1 DYNAMIC SCRIPTING APPLIED IN REAL-TIME STRATEGY GAMES

The learning mechanism in the dynamic scripting technique is inspired by reinforcement learning techniques (Russell and Norvig 1995).

In dynamic scripting an adaptive rulebase is used for the generation of intelligent opponents on the

fly. Rules are extracted from a rulebase to form a new script that controls the dynamic players’ behavior. The probability that a rule is selected for a script is proportional to a weight value that is associated with each rule i.e., rules with larger weights have a higher probability of being selected. The idea behind dynamic scripting is that the rulebase adapts by changing the weight values to reflect the success or failure rate of the corresponding rules in scripts. After every game, the weights of rules employed in the combat are increased when having a positive contribution to the outcome and

decreased when having a negative contribution. The remaining rules get updated so that the total weight of the rules in the rulebase remains unchanged.