Reading Literature

Experiments with Online Reinforcement Learning in Real-Time Strategy Games

A Real-Time Strategy (RTS) game is a computer game in which players intend to defeat opponents by gathering resources, building bases, and exploring game fields. It demands players to monitor opponents’ behaviors and to be adaptive on taking counter strategies.

Most of game developers use RL or other learning algorithms in the test phase of game programming or around this phase (Laird and van Lent 2005). The learning algorithm is well tested before a game product is shipped out to the target customers.

We compare a basic RL technique, SARSA (Sutton and Barto 1998), with a more sophisticated method, Q-learning (Watkins 1989), within the proposed framework in the game. As expected, the Q-learning performs beter than the SARSA in the studied game.

2.2 RTS - Real Time Strategy

The RTS game is often split into a campaign part and a skirmish part. In the campaign part human players are playing a battle against computer players with a lower or greater amount of units/buildings. In a skirmish game both sides start on an equal size, and therefore the strategies to beat the computer players depends much on players’ skills. It differs from the

campaign part where the strategies rely on a level setup in the game. Using RL in the campaign part of an RTS game seems over-skilled and is essentially not needed because computer players can be easily hard-coded without being dull for human players to defeat. The skirmish part on the other hand demands to have RL since the policy could be primed against certain types of behaviors while still being improved after a single skirmish

game is ended. Some part of the policy table might also be updated during the course of games. RL implementation seems quite difficult, but the potential is certainly present.

2.3 TBS - Turn Based Strategy

Turn based games are traditionally divided into turns where only one player/opponent is allowed to make decisions regarding his/her play. The turn offers RL to have sufficient time to update policies and execute them. In the typical game Civilization (Civilization 1991) RL residing in the top level could decide to put a city near a certain resource, but the follow-up actions, such as creating units, moving them to the spot and starting up cities, might challenge RL. Some TBS games adopt simultaneous turns to make opponents act at the

same time as computer players, which turns the TBS almost into real time movement. This structure allows little time to learn the policy, but would not be impossible for RL use.

The TBS game structure gives RL opportunity to have reasonable time to make up the policy; however, this must still be fast since players will not be pleased with waiting for too long before they can take a new turn. In general, RL is quite suitable in the TBS genre.

Initialize for all states s 2 S and actions a 2 A the value Q(s, a)

to a constant value

Repeat for each episode:

Initialize s

Choose a for s using the policy _

Repeat for each step in the episode, until s is terminal:

Execute action a and save reward r and next state s0

Choose a0 for s0 using _

Q(s, a) = Q(s, a) + _[r + Q(s0, a0) − Q(s, a)]

s = s0 and a = a0

Figure 2: The SARSA calculates the Q-value for each non-terminal state

where _ is the step-size parameter and the reward discount factor.

Initialize for all s 2 S and a 2 A the value Q(s, a) to a constant value

Repeat for each episode:

Initialize s

Repeat for each step in the episode, until s is terminal:

Choose a for s using _

Execute action a and save reward r and next state s0

Q(s, a) = Q(s, a) + _[r + maxa0Q(s0, a0) − Q(s, a)]

s = s0

Figure 3: The Q-learning updates the Q-value whenever action a is executed

in state s leading to new state s0.

4.2 Test 1: SARSA versus Q-learning

The first test aims for a comparison between two RL techniques: the SARSA and the Q-learning. As we expect the computer game using the RL does really better than the scripted player and the Q-learning technique outperforms the SARSA, which verifies the online RL benefit and fast convergence in the Q-learning.

Reading Literature

Reward Functions for Accelerated Learning

Reinforcement learning (RL) has become the methodology of choice for learning in a variety of different domains.

Delayed reinforcement is related to the way goals are formulated in a learning system. One of the main properties of situated domains is that agents pursues multiple goals, some of which are maintained continuously, while others are achieved and terminated.

intermittent reinforcement can be used similarly, by weighting the reward according to the accomplished progress. Intermediate reinforcement can be introduced in two ways: 1) by reinforcing multiple goals, and 2) by using progress estimators.

Progress estimators are partial internal critics. They are associated with specific goals and, when active, provide a metric of improvement relative to those goals.

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.