Abstract

In the first part of this thesis, we review the current solutions to problems raised by multi-player game AI, by outlining the types of computational and cognitive complexities in the main gameplay types. From here, we sum up the transversal categories of problems, introducing how Bayesian modeling can deal with all of them. We then explain how to build a Bayesian program from domain knowledge and observations through a toy role-playing game example. In the second part of the thesis, we detail our application of this approach to RTS AI, and the models that we built up. For reactive behavior (micro-management), we present a real-time multi-agent decentralized controller inspired from sensory motor fusion. We then show how to perform strategic and tactical adaptation to a dynamic opponent through opponent modeling and machine learning (both supervised and unsupervised) from highly skilled players’ traces. These probabilistic player-based models can be applied both to the opponent for prediction, or to ourselves for decision-making, through different inputs. Finally, we explain our StarCraft robotic player architecture and precise some technical implementation details.

Beyond models and their implementations, our contributions are threefolds: machine learning based plan recognition/opponent modeling by using the structure of the domain knowledge, multi-scale decision-making under uncertainty, and integration of Bayesian models with a real-time control program.

Contents

Notations

Symbols

Variables

X and V ariable	random variables (or logical propositions)
x and value	values
#s =	cardinal of the set s
#X =	shortcut for “cardinal of the set of the values of X”
X1:n	the set of n random variables X1…Xn
{x ∈ Ω|Q(x)}	the set of elements from Ω which verify Q

Probabilities

Conventions

Chapter 1
Introduction

1.1 Context

1.1.1 Motivations

There is more to playing than entertainment, particularly, playing has been found to be a basis for motor and logical learning. Real-time video games require skill and deep reasoning, attributes respectively shared by music playing and by board games. On many aspects, high-level real-time strategy (RTS) players can be compared to piano players, who would write their partition depending on how they want to play a Chess match, simultaneously to their opponent.

Research on video games rests in between research on real-world robotics and research on simulations or theoretical games. Indeed artificial intelligences (AI) evolve in a simulated world that is also populated with human-controlled agents and other AI agents on which we have no control. Moreover, the state space (set of states that are reachable by the players) is much bigger than in board games. For instance, the branching factor* in StarCraft is greater than 1.10⁶, compared to approximatively 35 in Chess and 360 in Go. Research on video games thus constitutes a great opportunity to bridge the gap between real-world robotics and simulations.

Another strong motivation is that there are plenty of highly skilled human video game players, which provides inspiration and incentives to measure our artificial intelligences against them. For RTS* games, there are professional players, whose games are recorded. This provides datasets consisting in thousands human-hours of play, by humans who beat any existing AI, which enables machine learning. Clearly, there is something missing to classical AI approaches to be able to handle video games as efficiently as humans do. I believe that RTS AI is where Chess AI was in the early 70s: we have RTS AI world competitions but even the best entries cannot win against skilled human players.

Complexity, real-time constraints and uncertainty are ubiquitous in video games. Therefore video games AI research is yielding new approaches to a wide range of problems. For instance in RTS* games: pathfinding, multiple agents coordination, collaboration, prediction, planning and (multi-scale) reasoning under uncertainty. The RTS framework is particularly interesting because it encompasses most of these problems: the solutions have to deal with many objects, imperfect information, strategic reasoning and low-level actions while running in real-time on desktop hardware.

1.1.2 Approach

Games are beautiful mathematical problems with adversarial, concurrent and sometimes even social dimensions, which have been formalized and studied through game theory. On the other hand, the space complexity of video games make them intractable problems with only theoretical tools. Also, the real-time nature of the video games that we studied asks for efficient solutions. Finally, several video games incorporate different forms of uncertainty, being it from partial observations or stochasticity due to the rules. Under all these constraints, taking real-time decisions under uncertainties and in combinatorics spaces, we have to provide a way to program robotic video games players, whose level matches amateur players.

We have chosen to embrace uncertainty and produce simple models which can deal with the video games’ state spaces while running in real-time on commodity hardware: All models are wrong; some models are useful. (attributed to Georges Box). If our models are necessarily wrong, we have to consider that they are approximations, and work with probabilities distributions. The other reasons to do so confirm us in our choice:

• Partial information forces us to be able to deal with state uncertainty.
• Not only we cannot be sure about our model relevance, but how can we assume “optimal” play from the opponent in a so complex game and so huge state space?

The unified framework to reason under uncertainty that we used is the one of plausible reasoning and Bayesian modeling.

As we are able to collect data about high skilled human players or produce data through experience, we can learn the parameters of such Bayesian models. This modeling approach unifies all the possible sources of uncertainties, learning, along with prediction and decision-making in a consistent framework.

1.2 Contributions

We produced tractable models addressing different levels of reasoning, whose difficulty of specification was reduced by taking advantage of machine learning techniques, and implemented a full StarCraft AI.

• Models breaking the complexity of inference and decision in games:
  • We showed that multi-agent behaviors can be authored through inverse programming (specifying independently sensor distribution knowing the actions), as an extension of [Hy, 2007]. We used decentralized control (for computational efficiency) by considering agents as sensory motor-robots: the incompleteness of not communicating with each others is transformed into uncertainty.
  • We took advantage of the hierarchy of decision-making in games by presenting and exploiting abstractions for RTS games (strategy & tactics) above units control. Producing abstractions, being it through heuristics or less supervised methods, produces “bias” and uncertainty.
  • We took advantage of the sequencing and temporal continuity in games. When taking a decision, previous observations, prediction and decisions are compressed in distributions on variables under the Markovian assumption.
• Machine learning on models integrating prediction and decision-making:
  • We produced some of our abstractions through semi-supervised or unsupervised learning (clustering) from datasets.
  • We identified the parameters of our models from human-played games, the same way that our models can learn from their opponents actions / past experiences.
• An implementation of a competitive StarCraft AI able to play full games with decent results in worldwide competitions.

Finally, video games is a billion dollars industry ($65 billion worldwide in 2011). With this thesis, we also hope to deliver a guide for industry practitioners who would like to have new tools for solving the ever increasing state space complexity of (multi-scale) game AI, and produce challenging and fun to play against AI.

1.3 Reading map

First, even though I tried to keep jargon to a minimum, when there is a precise word for something, I tend to use it. For AI researchers, there is a lot of video games’ jargon; for game designers and programmers, there is a lot of AI jargon. I have put everything in a comprehensive glossary.

Chapter 2 gives a basic culture about (pragmatic) game AI. The first part explains minimax, alpha-beta and Monte-Carlo tree search by glossing over Tic-tac-toe, Chess and Go respectively. The second part is about video games’ AI challenges. The reader novice to AI who wants a deep introduction on artificial intelligence can turn to the leading textbook [Russell and Norvig, 2010]. More advanced knowledge about some specificities of game AI can be acquired by reading the Quake III (by iD Software) source code: it is very clear and documented modern C, and it stood the test of time in addition to being the canonical fast first person shooter. Finally, there is no substitute for the reader novice to games to play them in order to grasp them.

We first notice that all game AI challenge can be addressed with uncertain reasoning, and present in chapter 3 the basics of our Bayesian modeling formalism. As we present probabilistic modeling as an extension of logic, it may be an easy entry to building probabilistic models for novice readers. It is not sufficient to give a strong background on Bayesian modeling however, but there are multiple good books on the subject. We advise the reader who want a strong intuition of Bayesian modeling to read the seminal work by Jaynes [2003], and we found the chapter IV of the (free) book of MacKay [2003] to be an excellent and efficient introduction to Bayesian inference. Finally, a comprehensive review of the spectrum of applications of Bayesian programming (until 2008) is provided by [Bessière et al., 2008].

Chapter 4 explains the challenges of playing a real-time strategy game through the example of StarCraft: Broodwar. It then explains our decomposition of the problem in the hierarchical abstractions that we have studied.

Chapter 5 presents our solution to the real-time multi-agent cooperative and adversarial problem that is micro-management. We had a decentralized reactive behavior approach providing a framework which can be used in other games than StarCraft. We proved that it is easy to change the behaviors by implementing several modes with minimal code changes.

Chapter 6 deals with the tactical abstraction for partially observable games. Our approach was to abstract low-level observations up to the tactical reasoning level with simple heuristics, and have a Bayesian model make all the inferences at this tactical abstracted level. The key to producing valuable tactical predictions and decisions is to train the model on real game data passed through the heuristics.

Chapter 7 shows our decompositions of strategy into specific prediction and adaptation (under uncertainty) tasks. Our approach was to reduce the complexity of strategies by using the structure of the game rules (technology trees) of expert players vocable (openings) decisions (unit types combinations/proportions). From partial observations, the probability distributions on the opponent’s strategy are reconstructed, which allows for adaptation and decision-making.

Chapter 8 describes briefly the software architecture of our robotic player (bot). It makes the link between the Bayesian models presented before and their connection with the bot’s program. We also comment some of the bot’s debug output to show how a game played by our bot unfolds.

We conclude by putting the contributions back in their contexts, and opening up several perspectives for future work in the RTS AI domain.

Chapter 2
Game AI

2.1 Goals of game AI

2.1.1 NPC

Non-playing characters (NPC*), also called “mobs”, represent a massive volume of game AI, as a lot of multi-player games have NPC. They really represents players that are not conceived to be played by humans, by opposition to “bots”, which corresponds to human-playable characters controlled by an AI. NPC are an important part of ever more immersive single player adventures (The Elder Scrolls V: Skyrim), of cooperative gameplays* (World of Warcraft, Left 4 Dead), or as helpers or trainers (“pets”, strategy games). NPC can be a core part of the gameplay as in Creatures or Black and White, or dull “quest giving poles” as in a lot of role-playing games. They are of interest for the game industry, but also for robotics, to study human cognition and for artificial intelligence in the large. So, the first goal of game AI is perhaps just to make the artificial world seem alive: a paint is not much fun to play in.

2.1.2 Win

During the last decade, the video game industry has seen the emergence of “e-sport”. It is the professionalizing of specific competitive games at the higher levels, as in sports: with spectators, leagues, sponsors, fans and broadcasts. A list of major electronic sport games includes (but is not limited to): StarCraft: Brood War, Counter-Strike, Quake III, Warcraft III, Halo, StarCraft II. The first game to have had pro-gamers* was StarCraft: Brood War*, in Korea, with top players earning more than Korean top soccer players. Top players earn more than $400,000 a year but the professional average is below, around $50-60,000 a year [Contracts, 2007], against the average South Korean salary at $16,300 in 2010. Currently, Brood War is being slowly phased out to StarCraft II. There are TV channels broadcasting Brood War (OnGameNet, previously also MBC Game) or StarCraft II (GOM TV, streaming) and for which it constitutes a major chunk of the air time. “E-sport” is important to the subject of game AI because it ensures competitiveness of the human players. It is less challenging to write a competitive AI for game played by few and without competitions than to write an AI for Chess, Go or StarCraft. E-sport, through the distribution of “replays*” also ensures a constant and heavy flow of human player data to mine and learn from. Finally, cognitive science researchers (like the Simon Fraser University Cognitive Science Lab) study the cognitive aspects (attention, learning) of high level RTS playing [Simon Fraser University].

Good human players, through their ability to learn and adapt, and through high-level strategic reasoning, are still undefeated. Single players are often frustrated by the NPC behaviors in non-linear (not fully scripted) games. Nowadays, video games’ AI can be used as part of the gameplay as a challenge to the player. This is not the case in most of the games though, in decreasing order of resolution of the problem¹ : fast FPS* (first person shooters), team FPS, RPG* (role playing games), MMORPG* (Massively Multi-player Online RPG), RTS* (Real-Time Strategy). These games in which artificial intelligences do not beat top human players on equal footing requires increasingly more cheats to even be a challenge (not for long as they mostly do not adapt). AI cheats encompass (but are not limited to):

• RPG NPC often have at least 10 times more hit points (health points) than their human counterparts in equal numbers,
• FPS bots can see through walls and use perfect aiming,
• RTS bots see through the “fog of war*” and have free additional resources.

How do we build game robotic players (“bots”, AI, NPC) which can provide some challenge, or be helpful without being frustrating, while staying fun?

2.1.3 Fun

The main purpose of gaming is entertainment. Of course, there are game genres like serious gaming, or the “gamification*” of learning, but the majority of people playing games are having fun. Cheating AI are not fun, and so the replayability* of single player games is very low. The vast majority of games which are still played after the single player mode are multi-player games, because humans are still the most fun partners to play with. So how do we get game AI to be fun to play with? The answer seems to be 3-fold:

• For competitive and PvP* (players versus players) games: improve game AI so that it can play well on equal footing with humans,
• for cooperative and PvE* (players vs environment) games: optimize the AI for fun, “epic wins”: the empowerment of playing your best and just barely winning,
• give the AI all the tools to adapt the game to the players: AI directors* (as in Left 4 Dead* and Dark Spore*), procedural content generation (e.g. automatic personalized Mario [Shaker et al., 2010]).

In all cases, a good AI should be able to learn from the players’ actions, recognize their behavior to deal with it in the most entertaining way. Examples for a few mainstream games: World of Warcraft instances or StarCraft II missions could be less predictable (less scripted) and always “just hard enough”, Battlefield 3 or Call of Duty opponents could have a longer life expectancy (5 seconds in some cases), Skyrim’s follower NPC* could avoid blocking the player in doors, or going in front when they cast fireballs.

2.1.4 Programming

How do game developers want to deal with game AI programming? We have to understand the needs of industry game AI programmers:

• computational efficiency: most games are real-time systems, 3D graphics are computationally intensive, as a result the AI CPU budget is low,
• game designers often want to remain in control of the behaviors, so game AI programmers have to provide authoring tools,
• AI code has to scale with the state spaces while being debuggable: the complexity of navigation added to all the possible interactions with the game world make up for an interesting “possible states coverage and robustness” problem,
• AI behaviors have to scale with the possible game states (which are not all predictable due to the presence of the human player),
• re-use accross games (game independant logic, at least libraries).

As a first approach, programmers can “hard code” the behaviors and their switches. For some structuring of such states and transitions, they can and do use state machines [Houlette and Fu, 2003]. This solution does not scale well (exponential increase in the number of transitions), nor do they generate autonomous behavior, and they can be cumbersome for game designers to interact with. Hierarchical finite state machine (FSM)* is a partial answer to these problems: they scale better due to the sharing of transitions between macro-states and are more readable for game designers who can zoom-in on macro/englobing states. They still represent way too much programming work for complex behavior and are not more autonomous than classic FSM. Bakkes et al. [2004] used an adaptive FSM mechanism inspired by evolutionary algorithms to play Quake III team games. Planning (using a search heuristic in the states space) efficiently gives autonomy to virtual characters. Planners like hierarchical task networks (HTNs)* [Erol et al., 1994] or STRIPS [Fikes and Nilsson, 1971] generate complex behaviors in the space of the combinations of specified states, and the logic can be re-used accross games. The drawbacks can be a large computational budget (for many agents and/or a complex world), the difficulty to specify reactive behavior, and less (or harder) control from the game designers. Behavior trees (Halo 2 [Isla, 2005], Spore) are a popular in-between HTN* and hierarchical finite state machine (HFSM)* technique providing scability through a tree-like hierarchy, control through tree editing and some autonomy through a search heuristic. A transversal technique for ease of use is to program game AI with a script (LUA, Python) or domain specific language (DSL*). From a programming or design point of view, it will have the drawbacks of the models it is based on. If everything is allowed (low-level inputs and outputs directly in the DSL), everything is possible at the cost of cumbersome programming, debugging and few re-use.

Even with scalable² architectures like behavior trees or the autonomy that planning provides, there are limitations (burdens on programmers/designers or CPU/GPU):

• complex worlds require either very long description of the state (in propositional logic) or high expressivity (higher order logics) to specify well-defined behaviors,
• the search space of possible actions increases exponentially with the volume and complexity of interactions with the world, thus requiring ever more efficient pruning techniques,
• once human players are in the loop (is it not the purpose of a game?), uncertainty has to be taken into account. Previous approaches can be “patched” to deal with uncertainty, but at what cost?

Our thesis is that we can learn complex behaviors from exploration or observations (of human players) without the need to be explicitely programmed. Furthermore, the game designers can stay in control by choosing which demonstration to learn from and tuning parameters by hand if wanted. Le Hy et al. [2004] showed it in the case of FPS AI (Unreal Tournament), with inverse programming to learn reactive behaviors from human demonstration. We extend it to tactical and even strategic behaviors.

2.2 Single-player games

Single player games are not the main focus of our thesis, but they present a few interesting AI characteristics. They encompass all kinds of human cognitive abilities, from reflexes to higher level thinking.

2.2.1 Action games

Platform games (Mario, Sonic), time attack racing games (TrackMania), solo shoot-them-up (“schmups”, Space Invaders, DodonPachi), sports games and rhythm games (Dance Dance Revolution, Guitar Hero) are games of reflexes, skill and familiarity with the environment. The main components of game AI in these genres is a quick path search heuristic, often with a dynamic environment. At the Computational Intelligence and Games conferences series, there have been Mario [Togelius et al., 2010], PacMan [Rohlfshagen and Lucas, 2011] and racing competitions [Loiacono et al., 2008]: the winners often use (clever) heuristics coupled with a search algorithm (A* for instance). As there are no human opponents, reinforcement learning and genetic programming works well too. In action games, the artificial player most often has a big advantage on its human counterpart as reaction time is one of the key characteristics.

2.2.2 Puzzles

Point and click (Monkey Island, Kyrandia, Day of the Tentacle), graphic adventure (Myst, Heavy Rain), (tile) puzzles (Minesweeper, Tetris) games are games of logical thinking and puzzle solving. The main components of game AI in these genres is an inference engine with sufficient domain knowledge (an ontology). AI research is not particularly active in the genre of puzzle games, perhaps because solving them has more to do with writing down the ontology than with using new AI techniques. A classic well-studied logic-based, combinatorial puzzle is Sudoku, which has been formulated as a SAT-solving [Lynce and Ouaknine, 2006] and constraint satisfaction problem [Simonis, 2005].

2.3 Abstract strategy games

2.3.1 Tic-tac-toe, minimax

Tic-tac-toe (noughts and crosses) is a solved game*, meaning that it can be played optimally from each possible position. How did it came to get solved? Each and every possible positions (26,830) have been analyzed by a Minimax (or its variant Negamax) algorithm. Minimax is an algorithm which can be used to determine the optimal score a player can get for a move in a zero-sum game*. The Minimax theorem states:

Applying this theorem to Tic-tac-toe, we can say that winning is +1 point for the player and losing is -1, while draw is 0. The exhaustive search algorithm which takes this property into account is described in Algorithm 1. The result of applying this algorithm to the Tic-tac-toe situation of Fig. 2.1 is exhaustively represented in Fig. 2.2. For zero-sum games (as abstract strategy games discussed here), there is a (simpler) Minimax variant called Negamax, shown in Algorithm 7 in Appendix A.

2.3.2 Checkers, alpha-beta

Checkers, Chess and Go are also zero sum, perfect-information*, partisan*, deterministic strategy game. Theoretically, they all can be solved by exhaustive Minimax. In practice though, it is often intractable: their bounded versions are at least in PSPACE and their unbounded versions are EXPTIME-hard [Hearn and Demaine, 2009]. We can see the complexity of Minimax as O(b^d) with b the average branching factor* of the tree (to search) and d the average length (depth) of the game. For Checkers b ≈ 8, but taking pieces is mandatory, resulting in a mean adjusted branching factor of ≈ 4, while the mean game length is 70 resulting in a game tree complexity of ≈ 10³¹ [Allis, 1994]. It is already too large to have been solved by Minimax alone (on current hardware). From 1989 to 2007, there were artificial intelligence competitions on Checkers, all using at least alpha-beta pruning: a technique to make efficient cuts in the Minimax search tree while not losing optimality. The state space complexity of Checkers is the smallest of the 3 above-mentioned games with ≈ 5.10²⁰ legal possible positions (conformations of pieces which can happen in games). As a matter of fact, Checkers have been (weakly) solved, which means it was solved for perfect play on both sides (and always ends in a draw) [Schaeffer et al., 2007a]. Not all positions resulting from imperfect play have been analyzed.

Alpha-beta pruning (see Algorithm 2) is a branch-and-bound algorithm which can reduce Minimax search down to a O(b^d∕2) = O() complexity if the best nodes are searched first (O(b^3d∕4) for a random ordering of nodes). α is the maximum score that we (the maximizing player) are assured to get given what we already evaluated, while β is the minimum score that the minimizing player is assured to get. When evaluating more and more nodes, we can only get a better estimate and so α can only increase while β can only decrease.

If we find a node for which β becomes less than α, it means that this position results from sub-optimal play. When it is because of an update of β, the sub-optimal play is on the side of the maximizing player (his α is not high enough to be optimal and/or the minimizing player has a winning move faster in the current sub-tree) and this situation is called an α cut-off. On the contrary, when the cut results from an update of α, it is called a β cut-off and means that the minimizing player would have to play sub-optimally to get into this sub-tree. When starting the game, α is initialized to -∞ and β to +∞. A worked example is given on Figure 2.3.

Alpha-beta is going to be helpful to search much deeper than Minimax in the same allowed time. The best Checkers program (since the 90s), which is also the project which solved Checkers [Schaeffer et al., 2007b], Chinook, has opening and end-game (for lest than eight pieces of fewer) books, and for the mid-game (when there are more possible moves) relies on a deep search algorithm. So, apart for the beginning and the ending of the game, for which it plays by looking up a database, it used a search algorithm. As Minimax and Alpha-beta are depth first search heuristics, all programs which have to answer in a fixed limit of time use iterative deepening. It consists in fixing limited depth which will be considered maximal and evaluating this position. As it does not relies in winning moves at the bottom, because the search space is too big in branching^depth, we need moves evaluation heuristics. We then iterate on growing the maximal depth for which we consider moves, but we are at least sure to have a move to play in a short time (at least the greedy depth 1 found move).

2.3.3 Chess, heuristics

With a branching factor* of ≈ 35 and an average game length of 80 moves [Shannon, 1950], the average game-tree complexity of chess is 35⁸⁰ ≈ 3.10¹²³. Shannon [1950] also estimated the number of possible (legal) positions to be of the order of 10⁴³, which is called the Shannon number. Chess AI needed a little more than just Alpha-beta to win against top human players (not that Checkers could not benefit it), particularly on 1996 hardware (first win of a computer against a reigning world champion, Deep Blue vs. Garry Kasparov). Once an AI has openings and ending books (databases to look-up for classical moves), how can we search deeper during the game, or how can we evaluate better a situation? In iterative deepening Alpha-beta (or other search algorithms like Negascout [Reinefeld, 1983] or MTD-f[Plaat, 1996]), one needs to know the value of a move at the maximal depth. If it does not correspond to the end of the game, there is a need for an evaluation heuristic. Some may be straight forward, like the resulting value of an exchange in pieces points. But some strategies sacrifice a queen in favor of a more advantageous tactical position or a checkmate, so evaluation heuristics need to take tactical positions into account. In Deep Blue, the evaluation function had 8000 cases, with 4000 positions in the openings book, all learned from 700,000 grandmaster games [Campbell et al., 2002]. Nowadays, Chess programs are better than Deep Blue and generally also search less positions. For instance, Pocket Fritz (HIARCS engine) beats current grandmasters [Wikipedia, Center] while evaluating 20,000 positions per second (740 MIPS on a smartphone) against Deep Blue’s (11.38 GFlops) 200 millions per second.

2.3.4 Go, Monte-Carlo tree search

With an estimated number of legal 19x19 Go positions of 2.081681994 * 10¹⁷⁰ [Tromp and Farnebäck, 2006] (1.196% of possible positions), and an average branching factor* above Chess for gobans* from 9x9 and above, Go sets another limit for AI. For 19x19 gobans, the game tree complexity is up to 10³⁶⁰ [Allis, 1994]. The branching factor varies greatly, from ≈ 30 to 300 (361 cases at first), while the mean depth (number of plies in a game) is between 150 to 200. Approaches other than systematic exploration of the game tree are required. One of them is Monte Carlo Tree Search (MCTS*). Its principle is to randomly sample which nodes to expand and which to exploit in the search tree, instead of systematically expanding the build tree as in Minimax. For a given node in the search tree, we note Q(node) the sum of the simulations rewards on all the runs through node, and N(node) the visits count of node. Algorithm 3 details the MCTS algorithm and Fig. 2.4 explains the principle.

The MoGo team [Gelly and Wang, 2006, Gelly et al., 2006, 2012] introduced the use of Upper Confidence Bounds for Trees (UCT*) for MCTS* in Go AI. MoGo became the best 9x9 and 13x13 Go program, and the first to win against a pro on 9x9. UCT specializes MCTS in that it specifies EXPANDFROM (as in Algorithm. 4) tree policy with a specific exploration-exploitation trade-off. UCB1 [Kocsis and Szepesvári, 2006] views the tree policy as a multi-armed bandit problem and so EXPANDFROM(node) UCB1 chooses the arms with the best upper confidence bound:

Kocsis and Szepesvári [2006] showed that the probability of selecting sub-optimal actions converges to zero and so that UCT MCTS converges to the minimax tree and so is optimal. Empirically, they found several convergence rates of UCT to be in O(b^d∕2), as fast as Alpha-beta tree search, and able to deal with larger problems (with some error). For a broader survey on MCTS methods, see [Browne et al., 2012].

---

Algorithm 4: UCB1 EXPANDFROM

 function EXPANDFROM(node)
  if node is terminal then
  return node terminal
  end if
  if ∃c ∈ node.children s.t. N(c) = 0 then
  return c grow
  end if
  return EXPANDFROM(argmax_{c∈node.children)} + k) select
 end function

---

With Go, we see clearly that humans do not play abstract strategy games using the same approach. Top Go players can reason about their opponent’s move, but they seem to be able to do it in a qualitative manner, at another scale. So, while tree search algorithms help a lot for tactical play in Go, particularly by integrating openings/ending knowledge, pattern macthing algorithms are not yet at the strategical level of human players. When a MCTS algorithm learns something, it stays at the level of possible actions (even considering positional hashing*), while the human player seems to be able to generalize, and re-use heuristics learned at another level.

2.4 Games with uncertainty

An exhaustive list of games, or even of games genres, is beyond the scope/range of this thesis. All uncertainty boils down to incompleteness of information, being it the physics of the dice being thrown or the inability to measure what is happening in the opponent’s brain. However, we will speak of 2 types (sources) of uncertainty: extensional uncertainty, which is due to incompleteness in direct, measurable information, and intentional uncertainty, which is related to randomness in the game or in (the opponent’s) decisions. Here are two extreme illustrations of this: an agent acting without sensing is under full extensional uncertainty, while an agent whose acts are the results of a perfect random generator is under full intentional uncertainty. The uncertainty coming from the opponent’s mind/cognition lies in between, depending on the simplicity to model the game as an optimization procedure. The harder the game is to model, the harder it is to model the trains of thoughts our opponents can follow.

2.4.1 Monopoly

In Monopoly, there is few hidden information (Chance and Community Chest cards only), but there is randomness in the throwing of dice³ , and a substantial influence of the player’s knowledge of the game. A very basic playing strategy would be to just look at the return on investment (ROI) with regard to prices, rents and frequencies, choosing what to buy based only on the money you have and the possible actions of buying or not. A less naive way to play should evaluate the questions of buying with regard to what we already own, what others own, our cash and advancement in the game. The complete state space is huge (places for each players × their money × their possessions), but according to Ash and Bishop [1972], we can model the game for one player (as he has no influence on the dice rolls and decisions of others) as a Markov process on 120 ordered pairs: 40 board spaces × possible number of doubles rolled so far in this turn (0, 1, 2). With this model, it is possible to compute more than simple ROI and derive applicable and interesting strategies. So, even in Monopoly, which is not lottery playing or simple dice throwing, a simple probabilistic modeling yields a robust strategy. Additionally, Frayn [2005] used genetic algorithms to generate the most efficient strategies for portfolio management.

Monopoly is an example of a game in which we have complete direct information about the state of the game. The intentional uncertainty due to the roll of the dice (randomness) can be dealt with thanks to probabilistic modeling (Markov processes here). The opponent’s actions are relatively easy to model due to the fact that the goal is to maximize cash and that there are not many different efficient strategies (not many Nash equilibrium if it were a stricter game) to attain it. In general, the presence of chance does not invalidate previous (game theoretic / game trees) approaches but transforms exact computational techniques into stochastic ones: finite states machines become probabilistic Bayesian networks for instance.

2.4.2 Battleship

Battleship (also called “naval combat”) is a guessing game generally played with two 10 × 10 grids for each players: one is the player’s ships grid, and one is to remember/infer the opponent’s ships positions. The goal is to guess where the enemy ships are and sink them by firing shots (torpedoes). There is incompleteness of information but no randomness. Incompleteness can be dealt with with probabilistic reasoning. The classic setup of the game consist in two ships of length 3 and one ship of each lengths of 2, 4 and 5; in this setup, there are 1,925,751,392 possible arrangements for the ships. The way to take advantage of all possible information is to update the probability that there is a ship for all the squares each time we have additional information. So for the 10 × 10 grid we have a 10 × 10 matrix O_1:10,1:10 with O_i,j ∈{true,false} being the ith row and jth column random variable of the case being occupied. With ships being unsunk ships, we always have:

Battleship is a game with few intensional uncertainty (no randomness), particularly because the goal quite strongly conditions the action (sink ships as fast as possible). However, it has a large part of extensional uncertainty (incompleteness of direct information). This incompleteness of information goes down rather quickly once we act, particularly if we update a probabilistic model of the map/grid. If we compare Battleship to a variant in which we could see the adversary board, playing would be straightforward (just hit ships we know the position on the board), now in real Battleship we have to model our uncertainty due to the incompleteness of information, without even beginning to take into account the psychology of the opponent in placement as a prior. The cost of solving an imperfect information game increases greatly from its perfect information variant: it seems to be easier to model stochasticity (or chance, a source of randomness) than to model a hidden (complex) system for which we only observe (indirect) effects.

2.4.3 Poker

Poker⁴ is a zero-sum (without the house’s cut), imperfect information and stochastic betting game. Poker “AI” is as old as game theory [Nash, 1951], but the research effort for human-level Poker AI started in the end of the 90s. The interest for Poker AI is such that there are annual AAAI computer Poker competitions⁵ . Billings et al. [1998] defend Poker as an interesting game for decision-making research, because the task of building a good/high level Poker AI (player) entails to take decisions with incomplete information about the state of the game, incomplete information about the opponents’ intentions, and model their thoughts process to be able to bluff efficiently. A Bayesian network can combine these uncertainties and represent the player’s hand, the opponents’ hands and their playing behavior conditioned upon the hand, as in [Korb et al., 1999]. A simple “risk evaluating” AI (folding and raising according to the outcomes of its hands) will not prevail against good human players. Bluffing, as described by Von Neumann and Morgenstern [1944] “to create uncertainty in the opponent’s mind”, is an element of Poker which needs its own modeling. Southey et al. [2005] also give a Bayesian treatment to Poker, separating the uncertainty resulting from the game (draw of cards) and from the opponents’ strategies, and focusing on bluff. From a game theoretic point of view, Poker is a Bayesian game*. In a Bayesian game, the normal form representation requires describing the strategy spaces, type spaces, payoff and belief functions for each player. It maps to all the possible game trees along with the agents’ information state representing the probabilities of individual moves, called the extensive form. Both these forms scale very poorly (exponentially). Koller and Pfeffer [1997] used the sequence form transformation, the set of realization weights of the sequences of moves⁶ , to search over the space of randomized strategies for Bayesian games automatically. Unfortunately, strict game theoretic optimal strategies for full-scale Poker are still not tractable this way, two players Texas Hold’em having a state space ≈ O(10¹⁸). Billings et al. [2003] approximated the game-theoretic optimal strategies through abstraction and are able to beat strong human players (not world-class opponents).

Poker is a game with both extensional and intentional uncertainty, from the fact that the opponents’ hands are hidden, the chance in the draw of the cards, the opponents’ model about the game state and their model about our mental state(s) (leading our decision(s)). While the iterated reasoning (“if she does A, I can do B”) is (theoretically) finite in Chess due to perfect information, it is not the case in Poker (“I think she thinks I think...”). The combination of different sources of uncertainty (as in Poker) makes it complex to deal with it (somehow, the sources of uncertainty must be separated), and we will see that both these sources of uncertainties arise (at different levels) in video games.

2.5 FPS

2.5.1 Gameplay and AI

First person shooters gameplay* consist in controlling an agent in first person view, centered on the weapon, a gun for instance. The firsts FPS popular enough to bring the genre its name were Wolfeinstein 3D and Doom, by iD Software. Other classic FPS (series) include Duke Nukem 3D, Quake, Half-Life, Team Fortress, Counter-Strike, Unreal Tournament, Tribes, Halo, Medal of Honor, Call of Duty, Battlefield, etc. The distinction between “fast FPS” (e.g. Quake series, Unreal Tournament series) and others is made on the speed at which the player moves. In “fast FPS”, the player is always jumping, running much faster and playing more in 3 dimensions than on discretely separate 2D ground planes. Game types include (but are not limited to):

• single-player missions, depending of the game design.
• capture-the-flag (CTF), in which a player has to take the flag inside the enemy camp and bring it back in her own base.
• free-for-all (FFA), in which there are no alliances.
• team deathmatch (TD), in which two (or more) teams fight on score.
• various gather and escort (including hostage or payload modes), in which one team has to find and escort something/somebody to another location.
• duel/tournament/deathmatch, 1 vs 1 matches (mainly “fast FPS”).

From these various game types, the player has to maximize its damage (or positive actions) output while staying alive. For that, she will navigate her avatar in an uncertain environment (partial information and other players intentions) and shoot (or not) at targets with specific weapons.

Some games allow for instant (or delayed, but asynchronous to other players) respawn (recreation/rebirth of a player), most likely in the “fast FPS” (Quake-like) games, while in others, the player has to wait for the end of the round to respawn. In some games, weapons, ammunitions, health, armor and items can be picked on the ground (mainly “fast FPS”), in others, they are fixed at the start or can be bought in game (with points). The map design can make the gameplay vary a lot, between indoors, outdoors, arena-like or linear maps. According to maps and gameplay styles, combat may be well-prepared with ambushes, sniping, indirect (zone damages), or close proximity (even to fist weapons). Most often, there are strong tactical positions and effective ways to attack them.

While “skill” (speed of the movements, accuracy of the shots) is easy to emulate for an AI, team-play is much harder for bots and it is always a key ability. Team-play is the combination of distributed evaluation of the situation, planning and distribution of specialized tasks. Very high skill also requires integrating over enemy’s tactical plans and positions to be able to take indirect shots (grenades for instance) or better positioning (coming from their back), which is hard for AI too. An example of that is that very good human players consistently beat the best bots (nearing 100% accuracy) in Quake III (which is an almost pure skill “fast FPS”), because they take advantage of being seen just when their weapons reload or come from their back. Finally, bots which equal the humans by a higher accuracy are less fun to play with: it is a frustrating experience to be shot across the map, by a bot which was stuck in the door because it was pushed out of its trail.

2.5.2 State of the art

FPS AI consists in controlling an agent in a complex world: it can have to walk, run, crouch, jump, swim, interact with the environment and tools, and sometimes even fly. Additionally, it has to shoot at moving, coordinated and dangerous, targets. On a higher level, it may have to gather weapons, items or power-ups (health, armor, etc.), find interesting tactical locations, attack, chase, retreat...

The Quake III AI is a standard for Quake-like games [van Waveren and Rothkrantz, 2002]. It consists in a layered architecture (hierarchical) FSM*. At the sensory-motor level, it has an Area Awareness System (AAS) which detects collisions, accessibility and computes paths. The level above provides intelligence for chat, goals (locations to go to), and weapons selection through fuzzy logic. Higher up, there are the behavior FSM (“seek goals”, chase, retreat, fight, stand...) and production rules (if-then-else) for squad/team AI and orders. A team of bots always behaves following the orders of one of the bots. Bots have different natures and tempers, which can be accessed/felt by human players, specified by fuzzy relations on “how much the bot wants to do, have, or use something”. A genetic algorithm was used to optimize the fuzzy logic parameters for specific purposes (like performance). This bot is fun to play against and is considered a success, however Quake-like games makes it easy to have high level bots because very good players have high accuracy (no fire spreading), so they do not feel cheated if bots have a high accuracy too. Also, the game is mainly indoors, which facilitates tactics and terrain reasoning. Finally, cooperative behaviors are not very evolved and consist in acting together towards a goal, not with specialized behaviors for each agent.

More recent FPS games have dealt with these limitations by using combinations of STRIPS planning (F.E.A.R. [Orkin, 2006]), HTN* (Killzone 2 [Champandard et al., 2009] and ArmA [van der Sterren, 2009]), Behavior trees (Halo 2 [Isla, 2005]). Left4Dead (a cooperative PvE FPS) uses a global supervisor of the AI to set the pace of the threat to be the most enjoyable for the player [Booth, 2009].

In research, Laird [2001] focused on learning rules for opponent modeling, planning and reactive planning (on Quake), so that the robot builds plan by anticipating the opponent’s actions. Le Hy et al. [2004], Hy [2007] used robotics inspired Bayesian models to quickly learn the parameters from human players (on Unreal Tournament). Zanetti and Rhalibi [2004] and Westra and Dignum [2009] applied evolutionary neural networks to optimize Quake III bots. Predicting opponents positions is a central task to believability and has been solved successfully using particle filters [Bererton, 2004] and other models (like Hidden Semi-Markov Models) [Hladky and Bulitko, 2008]. Multi-objective neuro-evolution [Zanetti and Rhalibi, 2004, Schrum et al., 2011] combines learning from human traces with evolutionary learning for the structure of the artificial neural network, and leads to realistic (human-like) behaviors, in the context of the BotPrize challenge (judged by humans) [Hingston, 2009].

2.5.3 Challenges

Single-player FPS campaigns immersion could benefit from more realistic bots and clever squad tactics. Multi-player FPS are competitive games, and a better game AI should focus on:

• believability requires the AI to take decisions with the same informations than the human player (fairness) and to be able to deal with unknown situation.
• surprise and unpredictability is key for both performance and the long-term interest in the human player in the AI.
• performance, to give a challenge to human players, can be achieved through cooperative, planned and specialized behaviors.

2.6 (MMO)RPG

2.6.1 Gameplay and AI

Inspired directly by tabletop and live action role-playing games (Dungeon & Dragons) as new tools for the game masters, it is quite natural for the RPG to have ended up on computers. The firsts digital RPG were text (Wumpus) or ASCII-art (Rogue, NetHack) based. The gameplay evolved considerably with the technique. Nowadays, what we will call a role playing game (RPG) consist in the incarnation by the human player of an avatar (or a team of avatars) with a class: warrior, wizard, rogue, priest, etc., having different skills, spells, items, health points, stamina/energy/mana (magic energy) points. Generally, the story brings the player to solve puzzles and fight. In a fight, the player has to take decisions about what to do, but skill plays a lesser role in performing the action than in a FPS game. In a FPS, she has to move the character (egocentrically) and aim to shoot; in a RPG, she has to position itself (often way less precisely and continually) and just decide which ability to use on which target (or a little more for “action RPG”). The broad category of RPG include: Fallout, The Elders Scrolls (from Arena to Skyrim), Secret of Mana, Zelda, Final Fantasy, Diablo, Baldur’s Gate. A MMORPG (e.g. World of Warcraft, AION or EVE Online) consist in a role-playing game in a persistent, multi-player world. There usually are players-run factions fighting each others’ (PvP) and players versus environment (PvE) situations. PvE* may be a cooperative task in which human players fight together against different NPC, and in which the cooperation is at the center of the gameplay. PvP is also a cooperative task, but more policy and reactions-based than a trained and learned choregraphy as for PvE. We can distinguish three types (or modality) of NPC which have different game AI needs:

• world/neutral/civilian NPC: gives quests, takes part in the world’s or game’s story, talks,
• “mob”/hostile NPC that the player will fight,
• “pets”/allied NPC: acts by the players’ sides.
• persistent character AI could maintain the players’ avatars in the world when they are disconnected.

NPC acting strangely are sometimes worse for the player’s immersion than immobile and dull ones. However, it is more fun for the player to battle with hostile NPC which are not too dumb or predictable. Players really expect allied NPC to at least not hinder them, and it is even better when they adapt to what the player is doing.

2.6.2 State of the art

Methods used in FPS* are also used in RPG*. The needs are sometimes a little different for RPG games: for instance RPG need interruptible behaviors, behaviors that can be stopped and resumed (dialogs, quests, fights...) that is. RPG also require stronger story-telling capabilities than other gameplay genres, for which they use (logical) story representations (ontologies) [Kline, 2009, Riedl et al., 2011]. Behavior multi-queues [Cutumisu and Szafron, 2009] resolve the problems of having resumable, collaborative, real-time and parallel behavior, and tested their approach on Neverwinter Nights. Basically they use prioritized behavior queues which can be inserted (for interruption and resumption) in each others. AI directors are control programs tuning the difficulty and pace of the game session in real-time from player’s metrics. Kline [2011] used an AI director to adapt the difficulty of Dark Spore to the performance (interactions and score) of the player in real-time.

2.6.3 Challenges

There are mainly two axes for RPG games to bring more fun: interest in the game play(s), and immersion. For both these topics, we think game AI can bring a lot:

• believability of the agents will come from AI approaches than can deal with new situations, being it because they were not dealt with during game development (because the “possible situations” space is too big) or because they were brought by the players’ unforeseeable actions. Scripts and strict policies approaches will be in difficulty here.
• interest (as opposed to boredom) for the human players in the game style of the AI will come from approaches which can generate different behaviors in a given situation. Expectable AI particularly affects replayability negatively.
• performance relative to the gameplay will come from AI approaches than can fully deal with cooperative behavior. One solution is to design mobs to be orders of magnitude stronger (in term of hit points and damages) than players’ characters, or more numerous. Another, arguably more entertaining, solution is to bring the mobs behavior to a point where they are a challenge for the team of human players.

Both believability and performance require to deal with uncertainty of the game environment. RPG AI problem spaces are not tractable for a frontal (low-level) search approach nor are there few enough situations to consider to just write a bunch of script and puppeteer artificial agents at any time.

2.7 RTS Games

As RTS are the central focus on this thesis, we will discuss specific problems and solution more in depth in their dedicated chapters, simply brushing here the underlying major research problems. Major RTS include the Command&Conquer, Warcraft, StarCraft, Age of Empires and Total Annihilation series.

2.7.1 Gameplay and AI

RTS gameplay consist in gathering resources, building up an economic and military power through growth and technology, to defeat your opponent by destroying his base, army and economy. It requires dealing with strategy, tactics, and units management (often called micro-management) in real-time. Strategy consist in what will be done in the long term as well as predicting what the enemy is doing. It particularly deals with the economy/army trade-off estimation, army composition, long-term planning. The three aggregate indicators for strategy are aggression, production, and technology. The tactical aspect of the gameplay is dominated by military moves: when, where (with regard to topography and weak points), how to attack or defend. This implies dealing with extensional (what the invisible units under “fog of war*” are doing) and intentional (what will the visible enemy units do) uncertainty. Finally, at the actions/motor level, micro-management is the art of maximizing the effectiveness of the units i.e. the damages given/damages received ratio. For instance: retreat and save a wounded unit so that the enemy units would have to chase it either boosts your firepower or weakens the opponent’s. Both [Laird and van Lent, 2001] and Gunn et al. [2009] propose that RTS AI is one of the most challenging genres, because all levels in the hierarchy of decisions are of importance.

More will be said about RTS in the dedicated chapter 4.

2.7.2 State of the art & challenges

Buro [2004] called for AI research in RTS games and identified the technical challenges as:

• adversarial planning under uncertainty, and for that abstractions have to be found both allowing to deal with partial observations and to plan in real-time.
• learning and opponent modeling: adaptability plays a key role in the strength of human players.
• spatial and temporal reasoning: tactics using the terrain features and good timings are essential for higher level play.

To these challenges, we would like to add the difficulty of inter-connecting all special cases resolutions of these problems: both for the collaborative (economical and logistical) management of the resources, and for the sharing of uncertainty quantization in the decision-making processes. Collaborative management of the resources require arbitrage between sub-models on resources repartition. By sharing information (and its uncertainty) between sub-models, decisions can be made that account better for the whole knowledge of the AI system. This will be extended further in the next chapters as RTS are the main focus of this thesis.

2.8 Games characteristics

All the types of video games that we saw before require to deal with imperfect information and sometimes with randomness, while elaborating a strategy (possibly from underlying policies). From a game theoretic point of view, these video games are close to what is called a Bayesian game* [Osborne and Rubinstein, 1994]. However, solving Bayesian games is non-trivial, there are no generic and efficient approaches, and so it has not been done formally for card games with more than a few cards. Billings et al. [2003] approximated a game theoretic solution for Poker through abstraction heuristics, it leads to believe than game theory can be applied at the higher (strategic) abstracted levels of video games.

We do not pretend to do a complete taxonomy of video games and AI (e.g. [Gunn et al., 2009]), but we wish to provide all the major informations to differentiate game genres (gameplays). To grasp the challenges they pose, we will provide abstract measures of complexity.

2.8.1 Combinatorics

“How does the state of possible actions grow?” To measure this, we used a measure from perfect information zero-sum games (as Checkers, Chess and Go): the branching factor* b and the depth d of a typical game. The complexity of a game (for taking a decision) is proportional to b^d. The average branching factor for a board game is easy to compute: it is the average number of possible moves for a given player. For Poker, we set b = 3 for fold, check and raise. d should then be defined over some time, the average number of events (decisions) per hour in Poker is between 20 to 240. For video-games, we defined b to be the average number of possible moves at each decision, so for “continuous” or “real-time” games it is some kind of function of the useful discretization of the virtual world at hand. d has to be defined as a frequency at which a player (artificial or not) has to take decisions to be competitive in the game, so we will give it in d∕time_unit. For instance, for a car (plane) racing game, b ≈ 50 - 500 because b is a combination of throttle (ẍ) and direction (θ) sampled values that are relevant for the game world, with d∕min at least 60: a player needs to correct her trajectory at least once a second. In RTS games, b ≈ 200 is a lower bound (in StarCraft we may have between 50 to 400 units to control), and very good amateurs and professional players perform more than 300 actions per minute.

The sheer size of b and d in video games make it seem intractable, but humans are able to play, and to play well. To explain this phenomenon, we introduce “vertical” and “horizontal” continuities in decision making. Fig. 2.6 shows how one can view the decision-making process in a video game: at different time scales, the player has to choose between strategies to follow, that can be realized with the help of different tactics. Finally, at the action/output/motor level, these tactics have to be implemented one way or another. So, matching Fig. 2.6, we could design a Bayesian model:

• S^t,t-1 ∈ Attack,Defend,Collect,Hide, the strategy variable
• T^t,t-1 ∈ Front,Back,Hit - and - run,Infiltrate, the tactics variable
• A^t,t-1 ∈ low_level_actions, the actions variable
• O_1:n^t ∈{observations}, the set of observations variables

• P(S^t|S^t-1,O_1:n^t) should be read as “the probability distribution on the strategies at time t is determined/influenced by the strategy at time t- 1 and the observations at time t”.
• P(T^t|S^t,T^t-1,O_1:n^t) should be read as “the probability distribution on the tactics at time t is determined by the strategy at time t, tactics at time t - 1 and the observations at time t”.
• P(A^t|T^t,A^t-1,O_1:n^t) should be read as “the probability distribution on the actions at time t is determined by tactics at time t, the actions at time t - 1 and the observations at time t”.

Vertical continuity

In the decision-making process, vertical continuity describes when taking a higher-level decision implies a strong conditioning on lower-levels decisions. As seen on Figure 2.7: higher level abstractions have a strong conditioning on lower levels. For instance, and in non-probabilistic terms, if the choice of a strategy s (in the domain of S) entails a strong reduction in the size of the domain of T, we consider that there is a vertical continuity between S and T. There is vertical continuity between S and T if ∀s ∈{S},{P(T^t|[S^t = s],T^t-1,O_1:n^t) > ϵ} is sparse in {P(T^t|T^t-1,O_1:n^t) > ϵ}. There can be local vertical continuity, for which the previous statement holds only for one (or a few) s ∈{S}, which are harder to exploit. Recognizing vertical continuity allows us to explore the state space efficiently, filtering out absurd considerations with regard to the higher decision level(s).

Horizontal continuity

Horizontal continuity also helps out cutting the search in the state space to only relevant states. At a given abstraction level, it describes when taking a decision implies a strong conditioning on the next time-step decision (for this given level). As seen on Figure 2.8: previous decisions on a given level have a strong conditioning on the next ones. For instance, and in non-probabilistic terms, if the choice of a tactic t (in the domain of T^t) entails a strong reduction in the size of the domain of T^t+1, we consider that T has horizontal continuity. There is horizontal continuity between T^t-1 and T^t if ∀t ∈{T},{P(T^t|S^t,[T^t-1 = t],O_1:n^t) > ϵ} is sparse in {P(T^t|S^t,O_1:n^t) > ϵ}. There can be local horizontal continuity, for which the previous state holds only for one (or a few) t ∈{T}. Recognizing horizontal continuity boils down to recognizing sequences of (frequent) actions from decisions/actions dynamics and use that to reduce the search space of subsequent decisions. Of course, at a sufficiently small time-step, most continuous games have high horizontal continuity: the size of the time-step is strongly related to the design of the abstraction levels for vertical continuity.

2.8.2 Randomness

Randomness can be inherent to the gameplay. In board games and table top role-playing, randomness often comes from throwing dice(s) to decide the outcome of actions. In decision-making theory, this induced stochasticity is dealt with in the framework of a Markov decision process (MDP)*. A MDP is a tuple of (S,A,T,R) with:

• S a finite set of states
• A a finite set of actions
• T_a(s,s′) = P([S^t+1 = s′]|[S^t = s],[A^t = a]) the probability that action a in state s at time t will lead to state s′ at time t + 1
• R_a(s,s′) the immediate reward for going from state s to state s′ with action a.

MDP can be solved through dynamic programming or the Bellman value iteration algorithm [Bellman, 1957]. In video games, the sheer size of S and A make it intractable to use MDP directly on the whole AI task, but they are used (in research) either locally or at abstracted levels of decision. Randomness inherent to the process is one of the sources of intentional uncertainty, and we can consider player’s intentions in this stochastic framework. Modeling this source of uncertainty is part of the challenge of writing game AI models.

2.8.3 Partial observations

Partial information is another source of randomness, which is found in shi-fu-mi, poker, RTS* and FPS* games, to name a few. We will not go down to the fact that the throwing of the dice seemed random because we only have partial information about its physics, or of the seed of the deterministic random generator that produced its outcome. Here, partial observations refer to the part of the game state which is deliberatively hidden between players (from a gameplay point of view): hidden hands in poker or hidden units in RTS* games due to the fog of war*. In decision-making theory, partial observations are dealt with in the framework of a partially observable Markov decision process (POMDP)* [Sondik, 1978]. A POMDP is a tuple (S,A,O,T,Ω,R) with S,A,T,R as in a MDP and:

• O a finite set of observations
• Ω conditional observations probabilities specifying: P(O^t+1|S^t+1,A^t)

In a POMDP, one cannot know exactly which state they are in and thus must reason with a probability distribution on S. Ω is used to update the distribution on S (the belief) uppon taking the action a and observing o, we have: P([S^t+1 = s′]) ∝ Ω(o|s′,a).∑ _s∈ST_a(s,s′).P([S^t = s]). In game AI, POMDP are computationally intractable for most problems, and thus we need to model more carefully (without full Ω and T) the dynamics and the information value.

2.8.4 Time constant(s)

For novice to video games, we give some orders of magnitudes of the time constants involved. Indeed, we present here only real-time video games and time constants are central to comprehension of the challenges at hand. In all games, the player is taking actions continuously sampled at the minimum of the human interface device (mouse, keyboard, pad) refreshment rate and the game engine loop: at least 30Hz. In most racing games, there is a quite high continuity in the input which is constrained by the dynamics of movements. In other games, there are big discontinuities, even if fast FPS* control resembles racing games a lot. RTS* professional gamers are giving inputs at ≈ 300 actions per minute (APM*).

There are also different time constants for a strategic switch to take effect. In RTS games, it may vary between the build duration of at least one building and one unit (1-2 minutes) to a lot more (5 minutes). In an RPG or a team FPS, it may even be longer (up to one full round or one game by requiring to change the composition of the team and/or the spells) or shorter by depending on the game mode. For tactical moves, we consider that the time for a decision to have effects is proportional to the mean time for a squad to go from the middle of the map (arena) to anywhere else. In RTS games, this is usually between 20 seconds to 2 minutes. Maps variability between RPG* titles and FPS* titles is high, but we can give an estimate of tactical moves to use between 10 seconds (fast FPS) to 5 minutes (some FPS, RPG).

2.8.5 Recapitulation

We present the main qualitative results for big classes of gameplays (with examples) in a table page 81.

2.9 Player characteristics

In all these games, knowledge and learning plays a key role. Humans compensate their lack of (conscious) computational power with pattern matching, abstract thinking and efficient memory structures. Particularly, we can classify required abilities for players to perform well in different gameplays by:

• Virtuosity: the technical skill or ease of the player with given game’s actions and interactions. At high level of skills, there is a strong parallel with playing a music instrument. In racing games, one has to drive precisely and react quickly. In FPS* games, players have to aim and move, while fast FPS motions resemble driving. In RPG* games, players have to use skill timely as well as have good avatar placement. Finally, in RTS* games, players have to control several units (in “god’s view”), from tens to hundreds and even sometimes thousands. They can use control groups, but it does not cancel the fact that they have to control both their economy and their armies.
• Deductive reasoning: the capacity to follow logical arguments, forward inference: [A ⇒ B] ∧ A ⇒ B. It is particularly important in Chess and Go to infer the outcomes of moves. For FPS games, what is important is to deduce where the enemy can be from what one has seen. In RPG games, players deduce quests solutions as well as skills/spells combinations effects. In RTS games, there is a lot of strategy and tactics that have to be infered from partial information.
• Inductive reasoning: the capacity for abstraction, generalization, going from simple observations to a more general concept. A simple example of generalization is: [Q of the sample has attribute A] ⇒ [Q of the population has attribute A]. In all games, it is important to be able to induce the overall strategy of the opponent’s from action-level observations. In games which benefit from a really abstract level of reasoning (Chess, Go, RTS), it is particularly important as it allows to reduce the complexity of the problem at hand, by abstracting it and reasoning in abstractions.
• Decision-making: the capacity to take decisions, possibly under uncertainty and stress. Selecting a course of actions to follow while not being sure of their effect is a key ability in games, particularly in (very) partial information games as Poker (in which randomness even adds to the problem) and RTS games. It is important in Chess and Go too as reasoning about abstractions (as for RTS) brings some uncertainty about the effects of moves too.
• Knowledge: we distinguish two kinds of knowledge in games: knowledge of the game and knowledge of particular situations (“knowledge of the map”). The duality doesn’t exist in Chess, Go and Poker. However, for instance for racing games, knowledge of the map is most often more important than knowledge of the game (game mechanics and game rules, which are quite simple). In FPS games, this is true too as good shortcuts, ambushes and efficient movements comes from good knowledge of the map, while rules are quite simple. In RPG, rules (skills and spells effects, durations, costs...) are much more complex to grasp, so knowlege of the game is perhaps more important. Finally, for RTS games, there are some map-specific strategies and tactics, but the game rules and overall strategies are also already complex to grasp. The longer are the rules of the game to explain, the higher the complexity of the game and thus the benefit from knowledge of the game itself.
• Psychology: the capacity to know the opponent’s move by knowing them, their style, and reasoning about what they think. It is particularly important in competitive games for which there are multiple possible styles, which is not really the case for Chess, Go and racing games. As players have multiple possible valid moves, reasoning about their decision-making process and effectively predicting what they will do is what differentiate good players from the best ones.

Finally, we made a quick survey among gamers and regrouped the 108 answers in table 2.9 page 85. The goal was a to get a grasp on which skills are correlated to which gameplays. The questions that we asked can be found in Appendix A.2. Answers mostly come from good to highly competitive (on a national level) amateurs. To test the “psychology” component of the gameplay, we asked players if they could predict the next moves of their opponents by knowing them personally or by knowing what the best moves (best play) was for them. As expected, Poker has the strongest psychological dimension, followed by FPS and RTS games.

Chapter 3
Bayesian modeling of multi-player games

3.1 Problems in game AI

We sum up the problems that we have detailed in the previous chapter to make a good case for a consistent reasoning scheme which can deal with uncertainty.

3.1.1 Sensing and partial information

If the AI has perfect information, behaving realistically is the problem. Cheating bots are not fun, so either AI should just use information available to the players, or it should fake having only partial information. That is what is done is FPS* games with sight range (often ray casted) and sound propagation for instance. In probabilistic modeling, sensor models allow for the computation of the state S from observations O by asking P(S|O). One can easily specify or learn P(O|S): either the game designers specify it, or the bot uses perfect information to get S and learns (counts) P(O|S). Then, when training is finished, the bot infers P(S|O) = (Bayes rule). Incompleteness of information is just uncertainty about the full state.

3.1.2 Uncertainty (from rules, complexity)

Some games have inherent stochasticity part of the gameplay, through random action effects of attacks/spells for instance. This has to be taken into account while designing the AI and dealt with either to maximize the expectation at a given time. In any case, in a multi-player setting, an AI cannot assume optimal play from the opponent due to the complexity of video games. In the context of state estimation and control, dealing with this randomness require ad-hoc methods for scripting of boolean logic, while it is dealt with natively through probabilistic modeling. Where a program would have to test for the value of an effect E to be in a given interval to decide on a given course of action A, a probabilistic model just computes the distribution on A given E: P(A|E) = .

3.1.3 Vertical continuity

As explained in section 2.8.1, there are different levels of abstraction use to reason about a game. Abstracting higher level cognitive functions (strategy and tactics for instance) is an efficient way to break the complexity barrier of writing game AI. Exploiting the vertical continuity, i.e. the conditioning of higher level thinking on actions, is totally possible in a hierarchical Bayesian model. With strategies as values of S and tactics as values of T, P(T|S) gives the conditioning of T on S and thus enables us to evaluate only those T values that are possible with given S values.

3.1.4 Horizontal continuity

Real-time games may use discrete time-steps (24Hz for instance for StarCraft), it does not prevent temporal continuity in strategies, tactics and, most strongly, actions. Once a decision has been made at a given level, it may conditions subsequent decisions at same level (see section 2.8.1). There are several Bayesian models able to deal with sequences, filter models, from which Hidden Markov Models (HMM*) [Rabiner, 1989], Kalman filters [Kalman, 1960] and particle filters [Arulampalam et al., 2002] are specializations of. With states S and observations O, filter models under the Markov assumption represent the joint P(S⁰).P(O⁰|S⁰).∏ _t=1^T[P(S^t|S^t-1).P(O^t|S^t)]. Thus, from partial informations, one can use more than just the probability of observations knowing states to reconstruct the state, but also the probability of states transitions (the sequences).

3.1.5 Autonomy and robust programming

Autonomy is the ability to deal with new states: the challenge of autonomous characters arises from state spaces too big to be fully specified (in scripts / FSM). In the case of discrete, programmer-specified states, the (modes of) behaviors of the autonomous agent are limited to what has been authored. Again, probabilistic modeling enables one to recognize unspecified states as soft mixtures of known states. For instance, with S the state, instead of having either P(S = 0) = 1.0 or P(S = 1) = 1.0, one can be in P(S = 0) = 0.2 and P(S = 1) = 0.8, which allows to have behaviors composed from different states. This form of continuum allows to deal with unknown state as an incomplete version of a known state which subsumes it. Autonomy can also be reached through learning, being it through online or offline learning. Offline learning is used to learn parameters that does not have to be specified by the programmers and/or game designers. One can use data or experiments with known/wanted situations (supervised learning, reinforcement learning), or explore data (unsupervised learning), or game states (evolutionary algorithms). Online learning can provide adaptability of the AI to the player and/or its own competency playing the game.

3.2 The Bayesian programming methodology

3.2.1 The hitchhiker’s guide to Bayesian probability

The reverend Thomas Bayes is the first credited to have worked on inversing probabilities: by knowing something about the probability of A given B, how can one draw conclusions on the probability of B given A? Bayes theorem states:

Later, by extending logic to plausible reasoning, Jaynes [2003] arrived at the same properties than the theory of probability of Kolmogorov [1933]. Plausible reasoning originates from logic, whose statements have degrees of plausibility represented by real numbers. By turning rules of inferences into their probabilistic counterparts, the links between logic and plausible reasoning are direct. With C = [A ⇒ B], we have:

• modus ponens, A entails B and A = true gives us B = false: translates to As P(A,B|C) = P(A|C) we have P(B|A,C) = 1
• modus tollens, A entails B and B = false gives us A = false (otherwise B = true): translates to As P(A¬B|C) = 0 we have P(A|¬B,C) = 0, so P(¬A|¬B,C) = 1

Also, additionally to the two strong logic syllogisms above, plausible reasoning gets two weak syllogisms, from:

• we get If A stands for “the enemy has done action a” and B for “the enemy is doing action b”: “the enemy is doing b so it is more probable that she did a beforehand (than if we knew nothing)”. Because there are only a (not strict) subset of all the possible states (possibly all possible states) which may lead in new states, when we are in these new states, the probability of their origin states goes up.
• we get Using the same meanings for A and B as above: “the enemy has not done a so it is less probable that she does b (than if we knew nothing)”. Because there are only a (not strict) subset of all the possible states (possibly all possible states) which may lead in new states, when we are not in one of these origin states, there are less ways to go to new states.

A reasoning mechanism needs to be consistent (one cannot prove A and ¬A at the same time). For plausible reasoning, consistency means: a) all the possible ways to reach a conclusion leads to the same result, b) information cannot be ignored, c) two equal states of knowledge have the same plausibilities. Adding consistency to plausible reasoning leads to Cox’s theorem [Cox, 1946], which derives the laws of probability: the “product-rule” (P(A,B) = P(A ∩ B) = P(A|B)P(B)) and the “sum-rule” (P(A + B) = P(A) + P(B) - P(A,B) or P(A ∪ B) = P(A) + P(B) - P(A ∩ B)) of probabilities.

Indeed, this was proved by Cox [1946], producing Cox’s theorem (also named Cox-Jayne’s theorem):

So, the degrees of belief, of any consistent induction mechanism, verify Kolmogorov’s axioms. Finetti [1937] showed that if reasoning is made in a system which is not isomorphic to probability theory, then it is always possible to find a Dutch book (a set of bets which guarantees a profit regardless of the outcomes). In our quest for a consistent reasoning mechanism which is able to deal with (extensional and intentional) uncertainty, we are thus bound to probability theory.

3.2.2 A formalism for Bayesian models

Inspired by plausible reasoning, we present Bayesian programming, a formalism that can be used to describe entirely any kind of Bayesian model. It subsumes Bayesian networks and Bayesian maps, as it is equivalent to probabilistic factor graphs Diard et al. [2003]. There are mainly two parts in a Bayesian program (BP)*, the description of how to compute the joint distribution, and the question(s) that it will be asked.

The description consists in exhibiting the relevant variables {X¹,…,Xⁿ} and explain their dependencies by decomposing the joint distribution P(X¹…Xⁿ|δ,π) with existing preliminary (prior) knowledge π and data δ. The forms of each term of the product specify how to compute their distributions: either parametric forms (laws or probability tables, with free parameters that can be learned from data δ) or recursive questions to other Bayesian programs.

Answering a question is computing the distribution P(Searched|Known), with Searched and Known two disjoint subsets of the variables.

General Bayesian inference is practically intractable, but conditional independence hypotheses and constraints (stated in the description) often simplify the model. There are efficient ways to calculate the joint distribution like message passing and junction tree algorithms [Pearl, 1988, Aji and McEliece, 2000, Naïm et al., 2004, Mekhnacha et al., 2007, Koller and Friedman, 2009]. Also, there are different well-known approximation techniques: either by sampling with Monte-Carlo (and Monte-Carlo Markov Chains) methods [MacKay, 2003, Andrieu et al., 2003], or by calculating on a simpler (tractable) model which approximate the full joint as with variational Bayes [Beal, 2003].

We sum-up the full model by what is called a Bayesian program, represented as:

For the use of Bayesian programming in sensory-motor systems, see [Bessière et al., 2008]. For its use in cognitive modeling, see [Colas et al., 2010]. For its first use in video game AI, applied to the first person shooter gameplay (Unreal Tournament), see [Le Hy et al., 2004].

To sum-up, by using probabilities as an extension of propositional logic, the method to build Bayesian models gets clearer: there is a strong parallel between Bayesian programming and logic or declarative programming. In the same order as the presentation of Bayesian programs, modeling consists in the following steps:

1.

Isolate the variables of the problem: it is the first prior that the programmer puts into the system. The variables can be anything, from existing input or output values of the problem to abstract/aggregative values or parameters of the model. Discovering which variable to use for a given problem is one of the most complicated form of machine learning.

2.

Suppose and describe the influences and dependencies between these variables. This is another prior that the programmer can have on the problem, and learning the structure between these variables is the second most complicated form of learning [François and Leray, 2004, Leray and Francois, 2005].

3.

Fill the priors and conditional probabilities parameters. The programmer needs to be an expert of the problem to put relevant parameters, although this is the easiest to learn from data once variables and structure are specified. Learning the structure can be seen as learning the parameters of a fully connected model and then removing dependencies where are the less influent parameters.

In the following, we present how we applied this method to a simulated MMORPG* fight situation as an example.

By following these steps, one may have to choose among several models. That is not a problem as there are rational ground to make this choices, “all models are wrong; some are useful” (George Box). Actually, the full question that we ask is P(Searched|Known,π,δ), it depends on the modeling assumptions (π) as well as the data (δ) that we used for training (if any). A simple way to view model selection is to pick the model which makes the fewest assumptions (Occam’s razor). In fact, Bayesian inference carries Occam’s razor with it: we shall ask what is the plausibility of our model prior knowledge in the light of the data P(π|δ).

Indeed, when evaluating two models π₁ and π₂, doing the ratio of evidences for the two modeling assumption helps us choose:

(3.4)

If our model is complicated, its expressiveness is higher, and so it can model more complex causes of/explanations for the dataset. However, the probability mass will be spread thiner on the space of possible datasets than for a simpler model. For instance, in the task of regression, if π₁ can only encode linear regression (y = Ax + b) and π₂ can also encore quadratic regression (y = Ax + Bx² + c), all the predictions for π₁ are concentrated on linear (affine) functions, while for π₂ the probability mass of predictions is spread on more possible functions. If we only have data δ of linear functions, the evidence for π₁, P(π₁|δ) will be higher. If δ contains some quadratic functions, the evidence ratio will shift towards π₂ as the second model has better predictions: the shift to π₂ happens when the additional model complexity of π₂ and the prediction errors of π₁ balance each other.

3.3 Modeling of a Bayesian MMORPG player

3.3.1 Task

We will now present a model of a MMORPG* player with the Bayesian programming framework [Synnaeve and Bessière, 2010]. A role-playing game (RPG) consist in the incarnation by the human player of an avatar with specific skills, items, numbers of health points (HP) and stamina or mana (magic energy) points (we already presented this gameplay in section 2.6). We want to program a robotic player which we can substitute to a human player in a battle scenario. More specifically here, we modeled the “druid” class, which is complex because it can cast spells to deal damages or other negative effects as well as to heal allies or enhance their capacities (“buff” them). The model described here deals only with a sub-task of a global AI for autonomous NPC.

The problem that we try to solve is: how do we choose which skill to use, and on which target, in a PvE* battle? The possible targets are all our allies and foes. There are also several skills that we can use. We will elaborate a model taking all our perceptions into account and giving back a distribution over possible target and skills. We can then pick the most probable combination that is yet possible to achieve (enough energy/mana, no cooldown/reload time) or simply sample in this distribution.

An example of a task that we have to solve is depicted in Figure 3.2, which shows two different setups (states) of the same scenario: red characters are foes, green ones are allies, we control the blue one. The “Lich” is inflicting damages to the “MT” (main tank), the “Add” is hitting the “Tank”. In setup A, only the “Tank” is near death, while in setup B both the “Tank” and the “Add” are almost dead. A first approach to reason about these kind of situations would be to use the combination of simple rules and try to give them some priority.

• if an ally has less than X (threshold) HP then use a “heal” on him.
• if the enemy receiving most damage has resistances (possibly in a list), lower them if possible.
• if allies (possibly in a list) are not “buffed” (enhanced), buff them if possible.
• default: shoot at the most targeted enemy.
• self-preservation, etc.

The problem with such an approach is that tuning or modifying it can quickly be cumbersome: for a game with a large state space, robustness is hard to ensure. Also, the behavior would seem pretty repetitive, and thus predictable.

3.3.2 Perceptions and actions

To solve this problem without having the downsides of this naive first approach, we will use a Bayesian model. We now list some of the perceptions available to the player (and thus the robot):

• the names and positions of all other players, this gives their distances, which is useful to know which abilities can be used.
• hit points (also health points, noted HP) of all the players, when the HP of a player fall to 0, her avatar dies. It cannot be resurrected, at least in the situations that we consider (not for the fight).
• the natures of other players (ally or foe).
• the class of other players: some have a tanking role (take incoming damages for the rest of the group), others are damage dealers (either by contact or ranged attacks), the last category are healers, whose role is to maintain everyone alive.
• an approximation of the resistance to certain types of attacks for every player.

Actions available to the players are to move and to use their abilities:

• damage over time attacks (periodic repeated damage), or quick but low damage attacks, and slow but high damage attacks
• energy/mana/stamina regenerators
• heal over time (periodic heal to selected allies), or quick but small heals, and slow but big heals
• immobilizations, disabling effects (“stun”)
• enhancement of the selected allies HP/attack/speed... and crippling attacks (enhancing future attacks), maledictions
• removing maledictions...

Here, we consider that the choice of a target and an ability to use on it strongly condition the movements of the player, so we will not deal with moving the character.

3.3.3 Bayesian model

We recall that write a Bayesian model by first describing the variables, their relations (the decomposition of the join probability), and the forms of the distribution. Then we explain how we identified the parameters and finally give the questions that will be asked.

Variables

A simple set of variables is as follows:

• Target: T^t-1,t ∈ {t₁…t_n} at t and t - 1 (previous action). T^t is also abusively noted T in the rest of the model. We have the n characters as possible targets; each of them has their own properties variables (the subscripting in the following variables).
• Hit Points: HP_{i∈⟦1…n⟧} ∈ [0…9] is the hit points value of the ith player. Health/Hit points (HP) are discretized in 10 levels, from the lower to the higher.
• Distance: D_{i∈⟦1…n⟧} ∈ {Contact,Close,Far,V eryFar} is the distance of the ith player to our robotic character. Distance (D) is discretized in 4 zones around the robot character: contact where it can attack with a contact weapon, close, far and (very far) to the further for which we have to move even for shooting the longest distance weapon/spell.
• Ally: A_{i∈⟦1…n⟧}∈{true,false} is true is the ith player is an ally, and false otherwise.
• Derivative Hit Points: ΔHP_{i∈⟦1…n⟧} ∈ {-,0,+} (decreasing, stable, increasing) is the evolution of the hit points of the ith player. ΔHP is a 3-valued interpolated value from the previous few seconds of fight that informs about the ith character getting wounded or healed (or nothing).
• Imminent Death: ID_{i∈⟦1…n⟧} ∈ {true,false} tells if the ith player is in danger of death. Imminent death (ID) is an interpolated value that encodes HP, ΔHP and incoming attacks/attackers. This is a Boolean variable saying if the ith character if going to die anytime soon. This is an example of what we consider that an experienced human player will infer automatically from the screen and notifications.
• Class: C_i∈⟦1…n ∈{Tank,Contact,Ranged,Healer} is the class of the ith player. Class (C) is simplified over 4 values: a Tank can take a lot of damages and taunt enemies, a Contact class which can deal huge amounts of damage with contact weapons (rogue, barbarian...), Ranged stands for the class that deals damages from far away (hunters, mages...) and Healers are classes that can heal in considerable amounts.
• Resists: R_{i∈⟦1…n⟧} ∈ {Nothing,Fire,Ice,Nature,FireIce,IceNat,FireNat,All} informs about the resistances of the ith player. The resist variable is the combination of binary variables of resistance to certain types of (magical) damages into one variable. With 3 possible resistances we get (2³) 8 possible values. For instance “R_i = FireNat” means that the ith character resists fire and nature-based damages. Armor (physical damages) could have been included, and the variables could have been separated.
• Skill: S ∈{Skill₁…Skill_m}. The skill variable takes all the possible skills for the given character, and not only the available ones to cast at the moment to be able to have reusable probability tables (i.e. it is invariant of the dynamics of the game).

Decomposition

The joint distribution of the model is:

• The probability of a given target depends on the previous one (it encodes the previous decision and so all previous states).
• The health (or hit) points (HP_i) depends on the facts that the ith character is an ally (A_i), on his class (C_i), and if he is a target (T). Such a conditional probability table should be learned, but we can already foresee that a targeted ally with a tanking class (C = tank) would have a high probability of having low hit points (HP) because taking it for target means that we intend to heal him.
• The distance of the unit i (D_i) is more probably far if unit i is an enemy (A_i = false) and we target it (T = i) as our kind of druid attacks with ranged spells and does not fare well in the middle of the battlefield.
• The probability of the ith character being an ally depends on if we target allies of foes more often: that is P(A_i|S,T) encodes our propensity to target allies (with heals and enhancements) or foes (with damaging or crippling abilities).
• The probability that the ith units is losing hit points (ΔHP_i = minus) is higher for foes (A_i = false) with vulnerable classes (C_i = healer) that are more susceptible to be targeted (T = i), and also for allies (A_i = true) whose role is to take most of the damages (C_i = tank). As for A_i, the probability of ID_i is driven by our
• Obviously, the usage of skills depends on their efficiency on the target (R, resistances), and on their class. As a result, we have P(R_i|C_i,S,T) as the conditional distribution on “resists”. The probability of the resist to “nature based effects” (R_i = nature) for skills involving “nature” damage (s ∈{nature_damage}) will be very low as it will be useless to use spells that the receiver is protected against.
• The probability that the ith character will die soon (ID_i) will be high if i is targeted (T = i) with a big heal or big instant damage (S = big_heal or S = big_damage, depending on whether i is an ally or not).

Parameters

• P(T^t-1) is unknown and unspecified (uniform). In the question, we always know what was the previous target, except when there was not one (at the beginning).
• P(T|T^t-1) is a probability corresponding to the propensity to switch targets. It can be learned, or uniform if there is no previous target (it the prior on the targets then).
• P(S) is unknown and so unspecified, it could be a prior on the preferred skills (for style of for efficiency).
• P(HP_i|A_i,C_i,S,T) is a 2 × 4 ×m× 2 probability table, indexed on if the ith character is an ally or not, on its class, on the skills (#S = m) and on where it is the target or not. It can be learned (and/or parametrized), for instance P(HP_i = x|a_i,c_i,s,t) = .
• P(D_i|A_i,S,T) is a 4 × 2 × m × 2 (possibly learned) probability table.
• P(A_i|S,T) is a 2 × m × 2 (possibly learned) probability table.
• P(ΔHP_i|A_i,S,T) is a 3 × 2 × m × 2 (possibly learned) probability table.
• P(R_i|C_i,S,T) is a 8 × 4 × m × 2 (possibly learned) probability table.
• P(C_i|A_i,S,T) is a 4 × 2 × m × 2 (possibly learned) probability table.

Identification

In the following Results part however, we did not apply learning but instead manually specified the probability tables to show the effects of gamers’ common sense rules and how it/they can be correctly encoded in this model.

About learning: if there were only perceived variables, learning the right conditional probability tables would just be counting and averaging. However, some variables encode combinations of perceptions and passed states. We could learn such parameters through the EM algorithm but we propose something simpler for the moment as our “not directly observed variables” are not complex to compute, we compute them from perceptions as the same time as we learn. For instance we map in-game values to their discrete values for each variables online and only store the resulting state “compression”.

Questions

In any case, we ask our (updated) model the distribution on S and T knowing all the state variables:

(3.8)

We then proceed to choose to do the highest scoring combination of S ∧T that is available (skills may have cooldowns or cost more mana/energy that we have available).

As (Bayes rule) P(S,T) = P(S|T).P(T), if we want to decompose this question, we can ask:

Bayesian program

Here is the full Bayesian program corresponding to this model:

3.3.4 Example

This model has been applied to a simulated situation with 2 foes and 4 allies while our robot took the part of a druid. We display a schema of this situation in Figure 3.2. The arrows indicate foes attacks on allies. HOT stands for heal over time, DOT for damage over time, “abol” for abolition and “regen” for regeneration, a “buff” is an enhancement and a “dd” is a direct damage. “Root” is a spell which prevents the target from moving for a short period of time, useful to flee or to put some distance between the enemy and the druid to cast attack spells. “Small” spells are usually faster to cast than “big” spells. The difference between setup A and setup B is simply to test the concurrency between healing and dealing damage and the changes in behavior if the player can lower the menace (damage dealer).

To keep things simple and because we wanted to analyze the answers of the model, we worked with manually defined probability tables.In the experiments, we will try different values P(ID_i|T = i), and see how the behavior of the agent changes.

We set the probability to target the same target as before (P(T^t = i|T^t-1 = i)) to 0.4 and the previous target to “Lich” so that the prior probability for all other 6 targets is 0.1 (4 times more chances to target the Lich than any other character).

We set the probability to target an enemy (instead of an ally) P(A_i = false|T = i) to 0.6. This means that our Druid is mainly a damage dealer and just a backup healer.

When we only ask what the target should be:

When we ask what skill we should use:

• in setup A (left), we evolve with the increase of P(ID_i = true|T = i) to choose to heal (our ally),
• in setup B (right), to deal direct damage (and hopefully, kill) the foe attacking our ally.

As you can see here, when we have the highest probability to attack the main enemy (“Lich”, when P(ID_i = true|T = i) is low), who is a C = tank, we get a high probability for the skill debuff_armor. We need only cast this skill if the debuff is not already present, so perhaps that we will cast small_dd instead.

To conclude this example, we ask the full question, what is the distribution on skill and target:

3.3.5 Discussion

This limited model served the purpose of presenting Bayesian programming in practice. While it was used in a simulation, it showcases the approach one can take to break down the problem of autonomous control of NPC*. The choice of the skill or ability to use and the target on which to use it puts hard constraints on every others decisions the autonomous agent has to take to perform its ability action. Thus, such a model shows that:

• cooperative behavior is not too hard to incorporate in a decision (instead of being hard-coded),
• it can be learned, either from observations of a human player or by reinforcement (exploration),
• it is computationally tractable (for use in all games).

Moreover, using this model on another agent than the one controlled by the AI can give a prediction on what it will do, resulting in human-like, adaptive, playing style.

We did not kept at the research track of Bayesian modeling MMORPG games due to the difficulty to work on these types of games: the studios have too much to lose to “farmer” bots to accept any automated access to the game. Also, there are no sharing format of data (like replays) and the invariants of the game situations are fewer than in RTS games. Finally, RTS games have international AI competitions which were a good motivation to compare our approach with other game AI researchers.

Chapter 4
RTS AI: StarCraft: Broodwar

4.1 How does the game work

4.1.1 RTS gameplay

We first introduce the basic components of a real-time strategy (RTS) game. The player is usually referred as the “commander” and perceives the world in an allocentric “God’s view”, performing mouse and keyboard actions to give orders to units (or squads of units) within a circumvented area (the “map”). In a RTS, players need to gather resources to build military units and defeat their opponents. To that end, they often have worker units (or extraction structures) that can gather resources needed to build workers, buildings, military units and research upgrades. Workers are often also builders (as in StarCraft) and are weak in fights compared to military units. Resources may have different uses, for instance in StarCraft: minerals* are used for everything, whereas gas* is only required for advanced buildings or military units, and technology upgrades. Buildings and research upgrades define technology trees (directed acyclic graphs) and each state of a tech tree* (or build tree*) allow for different unit type production abilities and unit spells/abilities. The military units can be of different types, any combinations of ranged, casters, contact attack, zone attacks, big, small, slow, fast, invisible, flying... In the end, a central part of the gameplay is that units can have attacks and defenses that counter each others as in a soft rock-paper-scissors. Also, from a player point of view, most RTS games are only partially observable due to the fog of war* which hides units and new buildings which are not in sight range of the player’s units.

In chronological order, RTS include (but are not limited to): Ancient Art of War, Herzog Zwei, Dune II, Warcraft, Command & Conquer, Warcraft II, C&C: Red Alert, Total Annihilation, Age of Empires, StarCraft, Age of Empires II, Tzar, Cossacks, Homeworld, Battle Realms, Ground Control, Spring Engine games, Warcraft III, Total War, Warhammer 40k, Sins of a Solar Empire, Supreme Commander, StarCraft II. The differences in gameplay are in the order of number, nature and gathering methods of resources; along with construction, research and production mechanics. The duration of games vary from 15 minutes for the fastest to (1-3) hours for the ones with the biggest maps and longest gameplays. We will now focus on StarCraft, on which our robotic player is implemented.

4.1.2 A StarCraft game

StarCraft is a science-fiction RTS game released by Blizzard Entertainment^TM in March 1998. It was quickly expanded into StarCraft: Brood War (SC: BW) in November 1998. In the following, when referring to StarCraft, we mean StarCraft with the Brood War expansion. StarCraft is a canonical RTS game in the sense that it helped define the genre and most gameplay* mechanics seen in other RTS games are present in StarCraft. It is as much based on strategy than tactics, by opposition to the Age of Empires and Total Annihilation series in which strategy is prevalent. In the following of the thesis, we will focus on duel mode, also known as 1 vs. 1 (1v1). Team-play (2v2 and higher) and “free for all” are very interesting but were not studied in the framework of this research. These game modes particularly add a layer of coordination and bluff respectively.

A competitive game

StarCraft sold 9.5 millions licenses worldwide, 4.5 millions in South Korea alone [Olsen, 2007], and reigned on competitive RTS tournaments for more than a decade. Numerous international competitions (World Cyber Games, Electronic Sports World Cup, BlizzCon, OnGameNet StarLeague, MBCGame StarLeague) and professional gaming (mainly in South Korea [Chee, 2005]) produced a massive amount of data of highly skilled human players. In South Korea, there are two TV channels dedicated to broadcasting competitive video games, particularly StarCraft. The average salary of a pro-gamer* there was up to 4 times the average South Korean salary [MYM, 2007] (up to $200,000/year on contract for NaDa). Professional gamers perform about 300 actions (mouse and keyboard clicks) per minute while following and adapting their strategies, while their hearts reach 160 beats per minute (BPM are displayed live in some tournaments). StarCraft II is currently (2012) taking over StarCraft in competitive gaming but a) there is still a strong pool of highly skilled StarCraft players and b) StarCraft II has a really similar gameplay.

Replays

StarCraft (like most RTS) has a replay* mechanism, which enables to record every player’s actions such that the state of the game can be deterministically re-simulated. An extract of a replay is shown in appendix in Table B.1. The only piece of stochasticity comes from “attack miss rates” (≈ 47%) when a unit is on a lower ground than its target. These randomness generator seed is saved along with the actions in the replay. All high level players use this feature heavily either to improve their play or study opponents’ styles. Observing replays allows player to see what happened under the fog of war*, so that they can understand timing of technologies and attacks, and find clues/evidences leading to infer the strategy as well as weak points.

Factions

In StarCraft, there are three factions with very different units and technology trees:

• Terran: humans with strong defensive capabilities and balanced, averagely priced biological and mechanical units.
• Protoss: advanced psionic aliens with expensive, slow to produce and resistant units.
• Zerg: insectoid alien race with cheap, quick to produce and weak units.

The races are so different that learning to play a new race competitively is almost like learning to play with new rules.

Economy

All factions use workers to gather resources, and all other characteristics are different: from military units to “tech trees*”, gameplay styles. Races are so different that highly skilled players focus on playing with a single race (but against all three others). There are two types of resources, often located close together, minerals* and gas*. From minerals, one can build basic buildings and units, which opens the path to more advanced buildings, technologies and units, which will in turn all require gas to be produced. While minerals can be gathered at an increasing rate the more workers are put at work (asymptotically bounded) , the gas gathering rate is quickly limited to 3 workers per gas geyser (i.e. per base). There is another third type of “special” resource, called supply*, which is the current population of a given player (or the cost in population of a given unit), and max supply*, which is the current limit of population a player can control. Max supply* can be upgraded by building special buildings (Protoss Pylon, Terran Supply Depot) or units (Zerg Overlord), giving 9 to 10 additional max supply*, up to a hard limit of 200. Some units cost more supply than others (from 0.5 for a Zergling to 8 for a Protoss Carrier or Terran Battlecruiser). In Figure 4.1, we show the very basics of Protoss economy and buildings. Supply will sometimes be written supply/max supply (supply on max supply). For instance 4/9 is that we currently have a population of 4 (either 4 units of 1, or 2 of 2 or ...) on a current maximum of 9.

Openings and strategy

To reach a competitive amateur level, players have to study openings* and hone their build orders*. An opening corresponds to the first strategic moves of a game, as in other abstract strategy games (Chess, Go). They are classified/labeled with names from high level players. A build-order is a formally described and accurately timed sequence of buildings to construct in the beginning. As there is a bijection between optimal population and time (in the beginning, before any fight), build orders are indexed on the total population of the player as in the example for Protoss in table 4.1. At the highest levels of play, StarCraft games usually last between 6 (shortest games, with a successful rush from one of the player) to 30 minutes (long economically and technologically developed game).

Figure 4.2: Start and economical parts of a StarCraft game. The order of the screenshots goes from left to right and from top to bottom.

Figure 4.3: Military moves from a StarCraft (PvT) game. The order of the screenshots goes from left to right and from top to bottom.

A commented game

We now present the evolution of a game (Figures 4.2 and 4.3) during which we tried to follow the build order presented in table 4.1 (“2 Gates Goon Range”¹ ) but we had to adapt to the fact that the opponent was Zerg (possibility for a faster rush) by building a Gateway at 9 supply and building a Zealot (ground contact unit) before the first Dragoon. The first screenshot (image 1 in Figure 4.2) is at the very start of the game: 4 Probes (Protoss workers), and one Nexus (Protoss main building, producing workers and depot point for resources). At this point players have to think about what openings* they will use. Should we be aggressive early on or opt for a more defensive opening? Should we specialize our army for focused tactics, to the detriment of being able to handle situations (tactics and armies compositions) from the opponent that we did not foresee? In picture 2 in the same Figure (4.2), the first gate is being built. At this moment, players often send a worker to “scout” the enemy’s base, as they cannot have military units yet, it is a safe way to discover where they are and inquiry about what they are doing. In picture 3, the player scouts their opponent, thus gathering the first bits of information about their early tech tree. Thus, knowing to be safe from an early attack (“rush”), the player decides to go for a defensive and economical strategy for now. Picture 4 shows the player “expanding”, which is the act of making another base at a new resource location, for economical purposes. In picture 5, we can see the upgrading of the ground weapons along with 4 ranged military units, staying in defense at the expansion. This is a technological decision of losing a little of potential “quick military power” (from military units which could have been produced for this minerals and gas) in exchange of global upgrade for all units (alive and to be produced), for the whole game. This is an investment in both resources and time. Picture 6 showcases the production queue of a Gateway as well as workers transferring to a second expansion (third base). Being safe and having expanded his tech tree* to a point where the army composition is well-rounded, the player opted for a strategy to win by profiting from an economical lead. Figure 4.3 shows the aggressive moves of the same player: in picture 7, we can see a flying transport with artillery and area of effect “casters” in it. The goal of such an attack is not to win the game right away but to weaken the enemy’s economy: each lost worker has to be produced, and, mainly, the missing gathering time adds up quite quickly. In picture 8, the transport in unloaded directly inside the enemy’s base, causing huge damages to their economy (killing workers, Zerg Drones). This is the use of a specialized tactics, which can change the course of a game. At the same time, it involves only few units (a flying transport and its cargo), allowing for the main army to stay in defense at base. It capitalizes on the manoeuverability of the flying Protoss Shuttle, on the technological advancements allowing area of effects attacks and the large zone that the opponent has to cover to defend against it. In picture 9, an invisible attacking unit (circled in white) is harassing the oblivious enemy’s army. This is an example of how technology advance on the opponent can be game changing (the opponent does not have detection in range, thus is vulnerable to cloaked units). Finally, picture 10 shows the final attack, with a full ground army marching on the enemy’s base.

4.2 RTS AI challenges

In combinatorial game theory terms, competitive StarCraft (1 versus 1) is a zero sum, partial-information, deterministic² strategy game. StarCraft subsumes Wargus (Warcraft II open source clone), which has an estimated mean branching factor 1.5.10³ [Aha et al., 2005] (Chess: ≈ 35, Go: < 360): Weber [2012] finds a branching factor greater than 1.10⁶ for StarCraft. In a given game (with maximum map size) the number of possible positions is roughly of 10¹¹⁵⁰⁰, versus the Shannon number for Chess (10⁴³) [Shannon, 1950]. Also, we believe strategies are much more balanced in StarCraft than in most other games. Otherwise, how could it be that more than a decade of professional gaming on StarCraft did not converge to a finite set of fixed (imbalanced) strategies?

Humans deal with this complexity by abstracting away strategy from low level actions: there are some highly restrictive constraints on where it is efficient (“optimal”) to place economical main buildings (Protoss Nexus, Terran Command Center, Zerg Hatchery/Lair/Hive) close to minerals spots and gas geysers. Low-level micro-management* decisions have high horizontal continuity and humans see these tasks more like playing a musical instrument skillfully. Finally, the continuum of strategies is analyzed by players and some distinct strategies are identified as some kinds of “invariants”, or “entry points” or “principal components”. From there, strategic decisions impose some (sometimes hard) constraints on the possible tactics, and the complexity is broken by considering only the interesting state space due to this high vertical continuity.

Most challenges of RTS games have been identified by [Buro, 2003, 2004]. We will try to anchor them in the human reasoning that goes on while playing a StarCraft game.

• Adversarial planning under uncertainty (along with resource management): it diverges from traditional planning under uncertainty in the fact that the player also has to plan against the opponent’s strategy, tactics, and actions. From the human point of view, he has to plan for which buildings to build to follow a chosen opening* and subsequent strategies, under a restricted resources (and time) budget. At a lower level, and less obvious for humans, are the plans they make to coordinate units movements.
• Learning and opponent modeling, Buro accurately points out that human players need very few (“a couple of”) games to spot their opponents’ weaknesses. Somehow, human opponent modeling is related to the “induction scandal”, as Russell called it: how do humans learn so much so fast? We learn from our mistakes, we learn the “play style” of our opponent’s, we are quickly able to ask ourselves: “what should I do now given what I have seen and the fact that I am playing against player XYZ?”. “Could they make the same attack as last time?”. To this end, we use high level representations of the states and the actions with compressed invariants, causes and effects.
• Spatial and temporal reasoning (along with decision making under uncertainty), this is related to planning under uncertainty but focuses on the special relations between what can and what cannot be done in a given time. Sadly, it was true in 2004 but is still true today: “RTS game AI [...] falls victim to simple common-sense reasoning”. Humans learn sequences of actions, and reason only about actions coherent with common sense. For AI of complex systems, this common-sense is hard to encode and to use.
• Collaboration (teamplay), which we will not deal with here: a lot has to do with efficient communication and “teammate modeling”.

As we have seen previously more generally for multi-player video games, all these challenges can be handled by Bayesian modeling. While acknowledging these challenges for RTS AI, we now propose a different task decomposition, in which different tasks will solve some parts of these problems at their respective levels.

4.3 Tasks decomposition and linking

We decided to decompose RTS AI in the three levels which are used by the gamers to describe the games: strategy, tactics, micro-management. We remind the reader that parts of the map not in the sight range of the player’s units are under fog of war*, so the player has only partial information about the enemy buildings and army. The way by which we expand the tech tree, the specific units composing the army, and the general stance (aggressive or defensive) constitute what we call strategy. At the lower level, the actions performed by the player (human or not) to optimize the effectiveness of its units is called micro-management*. In between lies tactics: where to attack, and how. A good human player takes much data in consideration when choosing: are there flaws in the defense? Which spot is more worthy to attack? How much am I vulnerable for attacking here? Is the terrain (height, chokes) to my advantage? The concept of strategy is a little more abstract: at the beginning of the game, it is closely tied to the build order and the intention of the first few moves and is called the opening, as in Chess. Then, the long term strategy can be partially summed up by three signals/indicators:

• aggression: how much is the player aggressive or defensive?
• initiative: how much is the player adapting to the opponent’s strategy vs. how much is the player being original?
• technology/production/economy (tech/army/eco) distribution of resources: how much is the player spending (relatively) in these three domains?

At high levels of play, the tech/army/eco balance is putting a hard constraint on the aggression and initiative directions: if a player invested heavily in their army production, they should attack soon to leverage this investment. To the contrary, all other things being equal, when a player expands*, they are being weak until the expansion repaid itself, so they should play defensively. Finally, there are some technologies (researches or upgrades) which unlocks an “attack timing” or “attack window”, for instance when a player unlocks an invisible technology (or unit) before that the opponent has detection technology (detectors). On the other hand, while “teching” (researching technologies or expanding the tech tree*), particularly when there are many intermediate technological steps, the player is vulnerable because of the immediate investment they made, which did not pay off yet.

From this RTS domain tasks decomposition, we can draw the mind map given in Figure 4.4. We also characterized these levels of abstractions by:

• the conditioning that the decisions on one abstraction level have on the other, as discussed above: strategy conditions tactics which conditions low-level actions (that does not mean than there cannot be some feedback going up the hierarchy).
• the quantity of direct information that a player can hope to get on the choices of their opponent. While a player can see directly the micro-management of their enemy (movements of units on the battlefront), they cannot observe all the tactics, and a big part of tactics gameplay is to hide or fake them well. Moreover, key technological buildings are sometimes hidden, and the player has to form beliefs about the long term strategy of the opponent (without being in their head).
• the time which is required to switch behaviors of a given level. For instance a change of strategy will require to either a) (technology) build at least two buildings or a building and a research/upgrade, b) (army) build a few units, c) take a new expansion (new base). A change of tactics corresponds to a large repositioning of the army(ies), while a change in micro-management is very quick (like moving units out of an area-of-effect damage zone).

This is shown in Figure 4.5. We will discuss the state of the art for the each of these subproblems (and the challenges listed above) in their respective parts.

Figure 4.5: Gameplay levels of abstraction for RTS games, compared with their level of direct (and complete) information and orders of magnitudes of time to chance their policies.

To conclude, we will now present our works on these domains in separate chapters:

• Micro-management: chapter 5,
• Tactics: chapter 6,
• Strategy: chapter 7,
• Robotic player (bot): chapter 8.

In Figure 4.6, we present the flow of informations between the different inference and decision-making parts of the bot architecture. One can also view this problem as having a good model of one’s strategy, one’s opponent strategy, and taking decisions. The software architecture that we propose is to have services building and maintaining the model of the enemy as well as our state, and decision-making modules using all this information to give orders to actuators (filled in gray in Fig. 4.6).

Chapter 5
Micro-management

This work was published at Computational Intelligence in Games (IEEE CIG) 2011 in Seoul [Synnaeve and Bessière, 2011a].

• Problem: optimal control of units in a (real-time) huge adversarial actions space (collisions, accelerations, terrain, damages, areas of effects, foes, goals...).
• Problem that we solve: efficient coordinated control of units incorporating all low level actions and inputs, plus higher level orders and representations.
• Type: it is a problem of multi-agent control in an adversarial environment¹ .
• Complexity: PSPACE-complete [Papadimitriou and Tsitsiklis, 1987, Viglietta, 2012]. Our solutions are real-time on a laptop.

5.1 Units management

5.1.1 Micro-management complexity

In this part, we focus on micro-management*, which is the lower-level in our hierarchy of decision-making levels (see Fig. 4.5) and directly affect units control/inputs. Micro-management consists in maximizing the effectiveness of the units i.e. the damages given/damages received ratio. These has to be performed simultaneously for units of different types, in complex battles, and possibly on heterogeneous terrain. For instance: retreat and save a wounded unit so that the enemy units would have to chase it either boosts your firepower (if you save the unit) or weakens the opponent’s (if they chase).

StarCraft micro-management involves ground, flying, ranged, contact, static, moving (at different speeds), small and big units (see Figure 5.2). Units may also have splash damage, spells, and different types of damages whose amount will depend on the target size. It yields a rich states space and needs control to be very fast: human progamers can perform up to 400 “actions per minute” in intense fights. The problem for them is to know which actions are effective and the most rewarding to spend their actions efficiently. A robot does not have such physical limitations, but yet, badly chosen actions have negative influence on the issue of fights.

Let U be the set of the m units to control, A = {∪_i }∪S be the set of possible actions (all n possible directions, standing ground included, and Skills, firing included), and E the set of enemies. As |U| = m, we have |A|^m possible combinations each turn, and the enemy has |A|^|E|. The dimension of the set of possible actions each micro-turn (for instance: 1/24th of a second in StarCraft) constrains reasoning about the state of the game to be hierarchical, with different levels of granularity. In most RTS games, a unit can go (at least) in its 24 surrounding tiles (see Figure 5.2, each arrow correspond to a ) ) stay where it is, attack, and sometimes cast different spells: which yields more than 26 possible actions each turn. Even if we consider only 8 possible directions, stay, and attack, with N units, there are 10^N possible combinations each turn (all units make a move each turn). As large battles in StarCraft account for at least 20 units on each side, optimal units control hides in too big a search space to be fully explored in real-time (sub-second reaction at least) on normal hardware, even if we take only one decision per unit per second.

Figure 5.2: Screen capture of a fight in which our bot controls the bottom-left units in StarCraft. The 25 possible directions (…) are represented for a unit with white and grey arrows around it. Orange lines represent units’ targets, purple lines represent units’ priority targets (which are objective directions in fightMove() mode, see below).

5.1.2 Our approach

Our full robot has separate agents types for separate tasks (strategy, tactics, economy, army, as well as enemy estimations and predictions): the part that interests us here, the unit control, is managed by Bayesian units directly. Their objectives are set by military goal-wise atomic units group, themselves spawned to achieve tactical goals (see Fig. 5.1). Units groups tune their Bayesian units modes (scout, fight, move) and give them objectives as sensory inputs. The Bayesian unit is the smallest entity and controls individual units as sensory-motor robots according to the model described above. The only inter Bayesian units communication about attacking targets is handled by a structure shared at the units group level. This distributed sensory-motor model for micro-management* is able to handle both the complexity of unit control and the need of hierarchy (see Figure 5.1). We treat the units independently, thus reducing the complexity (no communication between our “Bayesian units”), and allowing to take higher-level orders into account along with local situation handling. For instance: the tactical planner may decide to retreat, or go through a choke under enemy fire, each Bayesian unit will have the higher-level order as a sensory input, along with topography, foes and allies positions. From its perception, our Bayesian robot [Lebeltel et al., 2004] can compute the distribution over its motor control. The performances of our models are evaluated against the original StarCraft AI and a reference AI (based on our targeting heuristic): they have proved excellent in this benchmark setup.

5.2 Related work

Technical solutions include finite states machines (FSM) [Rabin, 2002], genetic algorithms (GA) [Ponsen and Spronck, 2004, Bakkes et al., 2004, Preuss et al., 2010], reinforcement learning (RL) [Marthi et al., 2005, Madeira et al., 2006], case-based reasoning (CBR) [Aha et al., 2005, Sharma et al., 2007], continuous action models [Molineaux et al., 2008], reactive planning [Weber et al., 2010b], upper confidence bounds tree (UCT) [Balla and Fern, 2009], potential fields [Hagelbäck and Johansson, 2009], influence maps[Preuss et al., 2010], and cognitive human-inspired models [Wintermute et al., 2007].

FSM are well-known and widely used for control tasks due to their efficiency and implementation simplicity. However, they don’t allow for state sharing, which increases the number of transitions to manage, and state storing, which makes collaborative behavior hard to code [Cutumisu and Szafron, 2009]. Hierarchical FSM (HFSM) solve some of this problems (state sharing) and evolved into behavior trees (BT, hybrids HFSM) [Isla, 2005] and behavior multi-queues (resumable, better for animation) [Cutumisu and Szafron, 2009] that conserved high performances. However, adaptability of behavior by parameters learning is not the main focus of these models, and unit control is a task that would require a huge amount of hand tuning of the behaviors to be really efficient. Also, these architectures does not allow reasoning under uncertainty, which helps dealing with local enemy and even allied units. Our agents see local enemy (and allied) units but do not know what action they are going to do. They could have perfect information about the allied units intentions, but this would need extensive communication between all the units.

Some interesting uses of reinforcement learning (RL)* [Sutton and Barto, 1998] to RTS research are concurrent hierarchical (units Q-functions are combined higher up) RL* [Marthi et al., 2005] to efficiently control units in a multi-effector system fashion. Madeira et al. [2006] advocate the use of prior domain knowledge to allow faster RL* learning and applied their work on a large scale (while being not as large as StarCraft) turn-based strategy game. In real game setups, RL* models have to deal with the fact that the state spaces to explore is enormous, so learning will be slow or shallow. It also requires the structure of the game to be described in a partial program (or often a partial Markov decision process) and a shape function [Marthi et al., 2005]. RL can be seen as a transversal technique to learn parameters of an underlying model, and this underlying behavioral model matters. Ponsen and Spronck [2004] used evolutionary learning techniques, but face the same problem of dimensionality.

Case-based reasoning (CBR) allows for learning against dynamic opponents [Aha et al., 2005] and has been applied successfully to strategic and tactical planning down to execution through behavior reasoning rules [Ontañón et al., 2007a]. CBR limitations (as well as RL) include the necessary approximation of the world and the difficulty to work with multi-scale goals and plans. These problems led respectively to continuous action models [Molineaux et al., 2008]and reactive planning [Weber et al., 2010b]. Continuous action models combine RL and CBR. Reactive planning use a decomposition similar to hierarchical task networks [Hoang et al., 2005] in that sub-plans can be changed at different granularity levels. Reactive planning allows for multi-scale (hierarchical) goals/actions integration and has been reported working on StarCraft, the main drawback is that it does not address uncertainty and so can not simply deal with hidden information (both extensional and intentional). Fully integrated FSM, BT, RL and CBR models all need vertical integration of goals, which is not very flexible (except in reactive planning).

Monte-Carlo planning [Chung et al., 2005] and upper Upper confidence bounds tree (UCT) planning (coming from Go AI) [Balla and Fern, 2009] samples through the (rigorously intractable) plans space by incrementally building the actions tree through Monte-Carlo sampling. UCT for tactical assault planning [Balla and Fern, 2009] in RTS does not require to encode human knowledge (by opposition to Monte-Carlo planning) but it is too costly, both in learning and running time, to go down to units control on RTS problems. Our model subsumes potential fields [Hagelbäck and Johansson, 2009], which are powerful and used in new generation RTS AI to handle threat, as some of our Bayesian unit sensory inputs are based on potential damages and tactical goodness (height for the moment) of positions. Hagelbäck and Johansson [2008] presented a multi-agent potential fields based bot able to deal with fog of war in the Tankbattle game. Avery et al. [2009] and Smith et al. [2010] co-evolved influence map trees for spatial reasoning in RTS games. Danielsiek et al. [2008] used influence maps to achieve intelligent squad movement to flank the opponent in a RTS game. A drawback for potential field-based techniques is the large number of parameters that has to be tuned in order to achieve the desired behavior. Our model provides flocking and local (subjective to the unit) influences on the pathfinding as in [Preuss et al., 2010], which uses self-organizing-maps (SOM). In their paper, Preuss et al. are driven by the same quest for a more natural and efficient behavior for units in RTS. We would like to note that potential fields and influence maps are reactive control techniques, and as such, they do not perform any form of lookahead. In their raw form (without specific adaptation to deal with it), they can lead units to be stuck in local optimums (potential wells).

Pathfinding is used differently in planning-based approaches and reactive approaches. Danielsiek et al. [2008] is an example of the permeable interface between pathfinding and reactive control with influence maps augmented tactical pathfinding and flocking. As we used pathfinding as the mean to get a sensory input towards the objective, we were free to use a low resolution and static pathfinding for which A* was enough. Our approach is closer to the one of [Reynolds, 1999]: combining a simple path for the group with flocking behavior. In large problems and/or when the goal is to deal with multiple units pathfinding taking collisions (and sometimes other tactical features), more efficient, incremental and adaptable approaches are required. Even if specialized algorithms, such as D*-Lite Koenig and Likhachev [2002] exist, it is most common to use A* combined with a map simplification technique that generates a simpler navigation graph to be used for pathfinding. An example of such technique is Triangulation Reduction A*, that computes polygonal triangulations on a grid-based map Demyen and Buro [2006]. In recent commercial RTS games like Starcraft 2 or Supreme Commander 2, flocking-like behaviors are inspired of continuum crowds (“flow field”) Treuille et al. [2006]. A comprehensive review about (grid-based) pathfinding was recently done by Sturtevant Sturtevant [2012].

Finally, there are some cognitive approaches to RTS AI [Wintermute et al., 2007], and we particularly agree with Wintermute et al. analysis of RTS AI problems. Our model has some similarities: separate agents for different levels of abstraction/reasoning and a perception-action approach (see Figure 5.1).

5.3 A pragmatic approach to units control

5.3.1 Action and perception

Movement

The possible actions for each unit are to move from where they are to wherever on the map, plus to attack and/or use special abilities or spells. Atomic moves (shown in Fig. 5.2 by white and gray plain arrows) correspond to move orders which will make the unit go in a straight line and not call the pathfinder (if the terrain is unoccupied/free). There are collisions with buildings, other units, and the terrain (cliffs, water, etc.) which denies totally some movements for ground units. Flying units do not have any collision (neither with units, nor with terrain obviously). When a move order is issued, if the selected position is further than atomic moves, the pathfinder function will be called to decide which path to follow. We decided to use only atomic (i.e. small and direct) moves for this reactive model, using other kinds of moves is discussed later in perspectives.

Attacks

To attack another unit, a given unit has to be in range (different attacks or abilities have different ranges) it has to have reloaded its weapon, which can be as quick as 4 times per second up to ≈3 seconds (75 frames) per attack. To cast a spell or use an ability also requires energy, which (re)generates slowly and can be accumulated up to a limited amount. Also, there are different kinds of attacks (normal, concussive, explosive), which modify the total amount of damages made on different types of units (small, medium, big), and different spread form and range of splash damages. Some spells/abilities absorb some damages on a given unit, others make a zone immune to all range attacks, etc. Finally, ranged attackers at a lower level (in terrain elevation) than their targets have an almost 50% miss rate. These reasons make it an already hard problem just to select what to do without even moving.

Perceptions: potential damage map

Perceptions are of different natures: either they are direct measurements inside the game, or they are built up from other direct measurements or even come from our AI higher level decisions. Direct measurements include the position of terrain elements (cliffs, water, space, trees). Built up measurements comes from composition of informations like the potential damage map (see Fig. 5.3.1. We maintain two (ground and air) damage maps which are built by summing all enemy units attack damages, normalized by their attack speed, for all positions which are in their range. These values are then discretized in levels {No,Low,Medium,High} relative to the hit (health) points (HP) of the unit that we are moving. For instance, a tank (with many HP) will not fear going under some fire so he may have a Low potential damage value for a given direction which will read as Medium or High for a light/weak unit like a marine. This will act as subjective potential fields [Hagelbäck and Johansson, 2009] in which the (repulsive) influence of the potential damages map depends on the unit type. The discrete steps are:

Repulsion/attraction

For repulsion/attraction between units (allied or enemies), we could consider the instantaneous position of the units but it would lead to squeezing/expanding effects when moving large groups. Instead, we use their interpolated position at the time at which the unit that we move will be arrived in the direction we consider. In the right diagram in Figure 5.4, we want to move the unit in the center (U). There is an enemy (E) unit twice as fast as ours and an allied unit (A) three times as fast as ours. When we consider moving in the direction just above us, we are on the interpolated position of unit E (we travel one case when they do two); when we consider moving in the direction directly on our right (East), we are on the interpolated position of unit A. We consider where the unit will be time later, but also its size (some units produce collisions in a smaller scale than our discretization).

Objective

The goals coming from the tactician model (see Fig. 5.1) are broken down into steps which gives objectives to each units. The way to incorporate the objective in the reactive behavior of our units is to add an attractive sensory input. This objective is a fixed direction and we consider the probabilities of moving our unit in n possible directions … (in our StarCraft implementation: n = 25 atomic directions). To decide the attractiveness of a given direction with regard to the objective , we consider a weight which is proportional to the dot product ⋅, with a threshold minimum probability, as shown in Figure 5.4.

5.3.2 A simple unit

Greedy pragmatism

Is staying alive better than killing an enemy unit? Is a large splash damage better than killing an enemy unit? Is it better to fire or move? In that event, where? Even if we could compute to the end of the fight and apply the same approach that we have for board games, how do we infer the best “set of next moves” for the enemy? For enemy units, it would require exploring the tree of possible plans (intractable) whose we could at best only draw samples from [Balla and Fern, 2009]. Even so, taking enemy minimax (to which depth?) moves for facts would assume that the enemy is also playing minimax (to the same depth) following exactly the same valuation rules as ours. Clearly, RTS micro-management* is more inclined to reactive planning than board games reasoning. That does not exclude having higher level (strategic and tactic) goals. In our model, they are fed to the unit as sensory inputs, that will have an influence on its behavior depending on the situation/state the unit is in. We should at least have a model for higher-level decisions of the enemy and account for uncertainty of moves that could be performed in this kind of minimax approach. So, as complete search through the min/max tree is intractable, we propose a first simple solution: have a greedy target selection heuristic leading the movements of units to benchmark our Bayesian model against. In this solution, each unit can be viewed as an effector, part of a multi-body (multi-effector) agent, grouped under a units group.

Targeting heuristic

The idea behind the heuristic used for target selection is that units need to focus fire (which leads to less incoming damages if enemy units die faster) on units that do the most damages, have the less hit points, and take the most damages from their attack type. This can be achieved by using a data structure, shared by all our units engaged in the battle, that stores the damages corresponding to future allied attacks for each enemy units. Whenever a unit will fire on a enemy unit, it registers there the future damages on the enemy unit. As attacks are not all instantaneous and there are reload times, it helps focus firing² . We also need a set of priority targets for each of our unit types that can be drawn from expert knowledge or learned (reinforcement learning) battling all unit types. A unit select its target among the most focus fired units with positive future hit point (current hit points minus registered damages), while prioritizing units from the priority set of its type. The units group can also impose its own priorities on enemy units (for instance to achieve a goal). The target selection heuristics is fully depicted in 8 in the appendices.

Fight behavior

Based on this targeting heuristic, we design a very simple FSM* based unit as shown in Figure 5.6 and Algorithm 5.5: when the unit is not firing, it will either flee damages if it has taken too much damages and/or if the differential of damages is too strong, or move to be better positioned in the fight (which may include staying where it is). In this simple unit, the flee() function just tries to move the unit in the direction of the biggest damages gradient (towards lower potential damages zones). The fightMove() function tries to position the units better: in range of its priority target, so that if the priority target is out of reach, the behavior will look like: “try to fire on target in range, if it cannot (reloading or no target in range), move towards priority target”. As everything is driven by the firing heuristic (that we will also use for our Bayesian unit), we call this AI the Heuristic Only AI (HOAI).

5.3.3 Units group

The units group (UnitsGroup, see Fig. 5.1) makes the shared future damage data structure available to all units taking part in a fight. Units control is not limited to fight. As it is adversarial, it is perhaps the hardest task, but units control problems comprehends efficient team maneuvering and other behaviors such as scouting or staying in position (formation). The units group structure helps for all that: it decides of the modes in which the unit has to be. We implemented 4 modes in our Bayesian unit (see Fig. 5.7): fight, move, scout, inposition. When given a task, also named goal, by the tactician model (see Fig. 5.1), the units group has to transform the task objective into sensory inputs for the units.

• In scout mode, the (often quick and low hit points) unit avoids danger by modifying locally its pathfinding-based, objectives oriented route to avoid damages.
• In move mode, the objective is extracted for the pathfinder output: it consists in key waypoints near the units. When moving by flocking, our unit moves are influenced by other near allied units that repulse or attract it depending on its distance to the interpolation of the allied unit. It allows our units to move more efficiently by not splitting around obstacles and colliding less. As it causes other problems, we do not use the flocking behavior in full competitive games.
• In the inposition mode, the objective is the final unit formation position. The unit can be “pushed” by other units wanting to pass through. This is useful at a tactical level to do a wall of units that our units can traverse but the opponent’s cannot. Basically, there is an attraction to the position of the unit and a stronger repulsion of the interpolation of movements of allied units.
• In fight mode, our unit will follow the damages gradient to smart positions, for instance close to tanks (they cannot fire too close to their position) or far from too much contact units if our unit can attack with range (something called “kiting”). Our unit moves are also influenced by its priority targets, its goal/objective (go through a choke, flee, etc.) and other units. The objective depends of the confidence of the units group in the outcome of the battle:
  • If the units group is outnumbered (in adjusted strength) and the task is not a suicidal one, the units group will “fall back” and give objectives towards retreat.
  • If the fight is even or manageable, the units group will not give any objective to units, which will set their own objectives either to their priority targets in fightMove() or towards fleeing damages (towards lowest potential damages gradient) in flee().
  • If the units group is very confident in winning the fight, the objectives sensory inputs of the units will be set at the task objectives waypoints (from the pathfinder).

5.4 A Bayesian model for units control

5.4.1 Bayesian unit

We use Bayesian programming as an alternative to logic, transforming incompleteness of knowledge about the world into uncertainty. In the case of units management, we have mainly intensional uncertainty. Instead of asking questions like: where are other units going to be 10 frames later? Our model is based on rough estimations that are not taken as ground facts. Knowing the answer to these questions would require for our own (allied) units to communicate a lot and to stick to their plan (which does not allow for quick reaction nor adaptation).

We propose to model units as sensory-motor robots described within the Bayesian robot programming framework [Lebeltel et al., 2004]. A Bayesian model uses and reasons on distributions instead of predicates, which deals directly with uncertainty. Our Bayesian units are simple hierarchical finite states machines (states can be seen as modes) that can scout, fight and move (see Figure 5.7). Each unit type has a reload rate and attack duration, so their fight mode will be as depicted in Figure 5.6 and Algorithm 5.5. The difference between our simple HOAI presented above and Bayesian units are in flee() and fightMove() functions.

The unit needs to determine where to go when fleeing and moving during a fight, with regard to its target and the attacking enemies, while avoiding collisions (which results in blocked units and time lost) as much as possible. We now present the Bayesian program used for flee(), fightMove(), and while scouting, which differ only by what is inputed as objective:

Variables

• Dir_{i∈⟦1…n⟧}∈{True,False}: at least one variable for each atomic direction the unit can go to. P(Dir_i = True) = 1 means that the unit will certainly go in direction i (⇔). For example, in StarCraft we use the 24 atomic directions (48 for the smallest and fast units as we use a proportional scale) plus the current unit position (stay where it is) as shown in Figure 5.2.
• Obj_{i∈⟦1…n⟧}∈{True,False}: adequacy of direction i with the objective (given by a higher rank model). In our StarCraft AI, we use the scalar product between the direction i and the objective vector (output of the pathfinding) with a minimum value (0.3 in move mode for instance) so that the probability to go in a given direction is proportional to its alignment with the objective.
  • For flee(), the objective is set in the direction which flees the potential damage gradient (corresponding to the unit type: ground or air).
  • For fightMove(), the objective is set (by the units group) either to retreat, to fight freely or to march aggressively towards the goal (see 5.3.3).
  • For the scout behavior, the objective () is set to the next pathfinder waypoint.
• Dmg_{i∈⟦1…n⟧}∈{no,low,medium,high}: potential damage value in direction i, relative to the unit base health points, in direction i. In our StarCraft AI, this is directly drawn from two constantly updated potential damage maps (air, ground).
• A_{i∈⟦1…n⟧}∈{free,small,big}: occupation of the direction i by an allied unit. The model can effectively use many values (other than “occupied/free”) because directions may be multi-scale (for instance we indexed the scale on the size of the unit) and, in the end, small and/or fast units have a much smaller footprint, collision wise, than big and/or slow. In our AI, instead of direct positions of allied units, we used their (linear) interpolation (time it takes the unit to go to ) frames later (to avoid squeezing/expansion).
• E_{i∈⟦1…n⟧}∈{free,small,big}: occupation of the direction i by an enemy unit. As above.
• Occ_{i∈⟦1…n⟧}∈{free,building,staticterrain}: Occupied, repulsive effect of buildings and terrain (cliffs, water, walls).

There is basically one set of (sensory) variables per perception in addition to the Dir_i values.

Decomposition

The joint distribution (JD) over these variables is a specific kind of fusion called inverse programming [Le Hy et al., 2004]. The sensory variables are considered conditionally independent knowing the actions, contrary to standard naive Bayesian fusion, in which the sensory variables are considered independent knowing the phenomenon.

Forms

• P(Dir_i) prior on directions, unknown, so unspecified/uniform over all i. P(dir_i) = 0.5.
• P(Obj_i|Dir_i) for instance, “probability that this direction is the objective knowing that we go there” P(obj_i|dir_i) = threshold + (1.0 -threshold) × max(0,veco ⋅). We could have different thresholds depending on the mode, but this was not the case in our hand-specified tables: threshold = 0.3. The right diagram on Figure 5.4 shows P(Obj_i|Dir_i) for each of the possible directions (inside the thick big square boundaries of atomic directions) with red being higher probabilities.
• P(Dmg_i|Dir_i) probability of damages values in direction i knowing this is the direction that we are headed to. P(Dmg_i = high|Dir_i = T) has to be small in many cases for the unit to avoid going to positions it could be killed instantly. Probability table:
  

  Dmgi	diri	diri
  no	0.9	0.25
  low	0.06	0.25
  medium	0.03	0.25
  high	0.01	0.25

• P(A_i|Dir_i) probability that there is an ally in direction i knowing this is the unit direction. It is used to avoid collisions by not going where allied units could be in the near future. Probability table:
  

  Ai	diri	diri
  free	0.9	0.333
  small	0.066	0.333
  big	0.033	0.333

• P(E_i|Dir_i) same explanation and use as above but with enemy units, it can have different parameters as we may want to be stucking enemy units, or avoid them (mostly depending on the unit type). In a repulsive setting (what we mostly want), the left diagram in Figure 5.4 can be seen as P(A_i,E_i|Dir_i) if red corresponds to high probabilities (P(A_i,E_i|Dir_i) if red corresponds to lower probabilities). In our hand-specified implementation, for flee() and fightMove(), this is the same probability table as above (for P(A_i|Dir_i)).
• P(Occ_i|Dir_i) probability table that there is a blocking building or terrain element is some direction, knowing this is the unit direction, P(Occ_i = Static|Dir_i = T) will be very low, whereas P(Occ_i = Building|Dir_i = T) will also be very low but triggers building attack (and destruction) when there are no other issues. Probability table:
  

  Occi	diri	diri
  free	0.999899	0.333
  building	0.001	0.333
  static	0.000001	0.333

Identification

Parameters and probability tables can be learned through reinforcement learning [Sutton and Barto, 1998, Asmuth et al., 2009] by setting up different and pertinent scenarii and search for the set of parameters that maximizes a reward function (more about that in the discussion). In our current implementation, the parameters and probability table values are hand specified.

Question

When in fightMove() and flee(), the unit asks:

(5.5)

From there, the unit can either go in the most probable Dir_i or sample through them. We describe the effect of this choice in the next section (and in Fig. 5.12). A simple Bayesian fusion from 3 sensory inputs is shown in Figure 5.8, in which the final distribution on Dir peaks at places avoiding damages and collisions while pointing towards the goal. Here follows the full Bayesian program of the model (5.9):

Figure 5.9: Bayesian program of flee(), fightMove() and the scouting behaviors.

There are additional variables for specific modes/behaviors, also probability tables may be different.

Move

Without flocking
When moving without flocking (trying to maintain some form of group cohesion), the model is even simpler. The objective () is set to a path waypoint. The potential damage map is dropped from the JD (because it is not useful for moving when not fighting), the question is:

(5.6)

With flocking
To produce a flocking behavior while moving, we introduce another set of variables: Att_{i∈⟦1…n⟧} ∈{True,False}, allied units attractions (or not) in direction i.

A flocking behavior [Reynolds, 1999] requires:

• Separation: avoid collisions, short range repulsion,
• Alignment: align direction with neighbours,
• Cohesion: steer towards average position of neighbours.

Separation is dealt with by P(A_i|Dir_i) already. As we use interpolations of units at the time at which our unit will be arrived at the Dir_i under consideration, being attracted by Att_i gives cohesion as well as some form of alignment. It is not strictly the same as having the same direction and seems to fare better is complex terrain. We remind the reader that flocking was derived from birds flocks and fish schools behaviors: in both cases there is a lot of free/empty space.

A vector is constructed as the weighted sum of neighbour³ allied units. Then P(Att_i|Dir_i)for all i directions is constructed as for the objective influence (P(Obj_i|Dir_i)) by taking the dot product ⋅ with a minimum threshold (we used 0.3, so that the flocking effect is as strong as objective attraction):

The JD becomes JD × Π_i=1ⁿP(Att_i|Dir_i).

Figure 5.10: Bayesian program of the move behavior without and with flocking.

In position

The inposition mode corresponds to when some units are at the place they should be (no new objective to reach) and not fighting. This happens when some units arrived at their formation end positions and they are waiting for other (allied) units of their group, or when units are sitting (in defense) at some tactical point, like in front of a base for instance. The particularity of this mode is that the objective is set to the current unit position. It will be updated to always point to this “final formation position of the unit” as long as the unit stays in this mode (inposition). This is useful so that units which are arriving to the formation can go through each others and not get stuck. Figure 5.11 shows the effect of using this mode: the big unit (Archon) goes through a square formation of the other units (Dragoons) which are in inposition mode. What happens is an emerging phenomenon: the first (leftmost) units of the square get repulsed by the interpolated position of the dragoon, so they move themselves out of its trajectory. By moving, they repulse the second and then third line of the formation, the chain repulsion reaction makes a path for the big unit to pass through the formation. Once this unit path is no longer colliding, the attraction of units for their objective (their formation position) takes them back to their initial positions.

Figure 5.11: Sequence of traversal of an Archon (big blue unit which is circled in green) through a square formation of Dragoons (four legged red units) in inposition mode.

5.5 Results on StarCraft

5.5.1 Experiments

We produced three different AI to run experiments with, along with the original AI (OAI) from StarCraft:

• Heuristic only AI (HOAI), as described above (5.3.2): this AI shares the target selection heuristic with our Bayesian AI models and will be used as a baseline reference to avoid the bias due to the target selection heuristic.
• Bayesian AI picking best (BAIPB): this AI follows the model of section 5.4 and selects the most probable Dir_i as movement.
• Bayesian AI sampling (BAIS): this AI follows the model of section 5.4 and samples through Dir_i according to their probability (i.e. it samples a direction in the Dir distribution).

The experiments consisted in having the AIs fight against each others on a micro-management scenario with mirror matches of 12 and 36 ranged ground units (Dragoons). In the 12 units setup, the unit movements during the battle is easier (less collision probability) than in the 36 units setup. We instantiate only the army manager (no economy in this special scenarii/maps), one units group manager and as many Bayesian units as there are units provided to us in the scenario. The results are presented in Table 5.1.

These results show that our heuristic (HAOI) is comparable to the original AI (OAI), perhaps a little better, but induces more collisions as we can see its performance diminish a lot in the 36 units setup vs OAI. For Bayesian units, the “pick best” (BAIPB) direction policy is very effective when battling with few units (and few movements because of static enemy units) as proved against OAI and HOAI, but its effectiveness decreases when the number of units increases: all units are competing for the best directions (to flee() or fightMove()) and they collide. The sampling policy (BAIS) has way better results in large armies, and significantly better results in the 12 units vs BAIPB. BAIPB may lead our units to move inside the “enemy zone” a lot more to chase priority targets (in fightMove()) and collide with enemy units or get kill. Sampling entails that the competition for the best directions is distributed among all the “bests to good” positions, from the units point of view. We illustrate this effect in Figure 5.12: the units (on the right of the figure) have good reasons to flee on the left (combinations of sensory inputs, for instance of the damage map), and there may be a peak of “best position to be at”. As they have not moved yet, they do not have interpolation of positions which will collide, so they are not repulsing each other at this position, all go together and collide. Sampling would, on average, provide a collision free solution here.

We also ran tests in setups with flying units (Zerg Mutalisks) in which BAIPB fared as good as BAIS (no collision for flying units) and way better than OAI.

5.5.2 Our bot

This model is currently at the core of the micro-management of our StarCraft bot. In a competitive micro-management setup, we had a tie with the winner of AIIDE 2010 StarCraft micro-management competition, winning with ranged units (Protoss Dragoons), losing with contact units (Protoss Zealots) and having a perfect tie (the host wins thanks to a few less frames of lag) in the flying units setting (Zerg Mutalisks and Scourges).

This model can be used to specify the behavior of units in RTS games. Instead of relying on a “units push each other” physics model for handling dynamic collision of units, this model makes the units react themselves to collision in a more realistic fashion (a marine cannot push a tank, the tank will move). More than adding realism to the game, this is a necessary condition for efficient micro-management in StarCraft: Brood War, as we do not have control over the game physics engine and it does not have this “flow-like” physics for units positioning.

5.6 Discussion

5.6.1 Perspectives

Adding a sensory input: height attraction

We make an example of adding a sensory input (that we sometimes use in our bot): height attraction. From a tactical point of view, it is interesting for units to always try to have the higher ground as lower ranged units have a high miss rate (almost 50%) on higher positioned units. For each of the direction tiles Dir_i, we just have to introduce a new set of sensory variables: H_{i∈⟦0…n⟧}∈{normal,high,very_high,unknown} (unknown can be given by the game engine). P(H_i|Dir_i) is just an additional factor in the decomposition: JD ← JD × Π_i=1ⁿP(H_i|Dir_i). The probability table looks like:

Even more realistic behaviors

The realism of units movements can also be augmented with a simple-to-set P(Dir^t-1|Dir^t) steering parameter, although we do not use it in the competitive setup. We introduce Dir_{i∈⟦1…n⟧}^t-1 ∈{True,False}: the previous selected direction, Dir_i^t-1 = T iff the unit went to the direction i, else False for a steering (smooth) behavior. The JD would then be JD × Π_i=1ⁿP(Dir_i^t-1|Dir_i), with P(Dir_i^t-1|Dir_i) the influence of the last direction, either a dot product (with minimal threshold) as before for the objective and flocking, or a parametrized Bell shape over all the i.

Reinforcement learning

Future work could consist in using reinforcement learning [Sutton and Barto, 1998] or evolutionary algorithms [Smith et al., 2010] to learn the probability tables. It should enhance the performance of our Bayesian units in specific setups. It implies making up challenging scenarii and dealing with huge sampling spaces [Asmuth et al., 2009]. We learned the distribution of P(Dmg_i|Dir_i) through simulated annealing on a specific fight task (by running thousands of games). Instead of having 4 parameters of the probability table to learn, we further restrained P(Dmg_i|Dir_i) to be a discrete exponential distribution and we optimized the λ parameter. When discretized back to the probability table (for four values of Dmg), the parameters that we learned, by optimizing the efficiency of the army in a fixed fight micro-management scenario, were even more risk adverse than the table presented with this model. The major problem with this approach is that parameters which are learned in a given scenario (map, setup) are not trivially re-usable in other setups, so that boundaries have to be found to avoid over-learning/optimization, and/or discovering in which typical scenario our units are at a given time.

Reducing collisions

Also, there are yet many collision cases that remain unsolved (particularly visible with contact units like Zealots and Zerglings), so we could also try adding local priority rules to solve collisions (for instance through an asymmetrical P(Dir_i^t-1|Dir_i)) that would entails units crossing lines with a preferred side (some kind of “social rule”),

In collision due to concurrency for “best” positions: as seen in Figure. 5.12, units may compete for a well of potential. The solution that we use is to sample in the Dir distribution, which gives better results than picking the most probable direction as soon as there are many units. Another solution, inspired by [Marthi et al., 2005], would be for the Bayesian units to communicate their Dir distribution to the units group which would give orders that optimize either the sum of probabilities, or the minimal discrepancy in dissatisfaction, or the survival of costly units (as shown in Fig. 5.13). Ideally, we could have a full Bayesian model at the UnitsGroup level, which takes the P(Dir) distributions as sensory inputs and computes orders to units. This would be a centralized model but in which the complexity of micro-management would have been broken by the lower-level model presented in this chapter.

Tuning parameters

If we learn the parameters of such a model to mimic existing data (data mining) or to maximize a reward function (reinforcement learning), we can interpret the parameters that will be obtained more easily than parameters of an artificial neural network for instance. Parameters learned in one setup can be reused in another if they are understood. We claim that specifying or changing the behavior of this model is much easier than changing the behavior generated by a FSM, and game developers can have a fine control over it. Dynamic switches of behavior (as we do between the scout/flock/inposition/fight modes) are just one probability tables switch away. In fact, probability tables for each sensory input (or group of sensory inputs) can be linked to sliders in a behavior editor and game makers can specify the behavior of their units by specifying the degree of effect for each perception (sensory input) on the behavior of the unit and see the effect in real time. This is not restricted to RTS and could be applied to RPG* and even FPS* gameplays*.

Avoiding local optima

Local optimum could trap and struck our reactive, small look-ahead, units: concave (strong) repulsors (static terrain, very high damage field). A pragmatic solution to that is to remember that the Obj sensory inputs come from the pathfinder and have its influence to grow when in difficult situations (not moved for a long time, concave shape detected...). Another solution is inspired by ants: simply release a repulsive field (a repulsive “pheromone”) behind the unit and it will be repulsed by places it already visited instead of oscillating around the local optima (see Fig. 5.14).

Another solution would be to consider more than just the atomic directions. Indeed, if one decides to cover a lot of space with directions (i.e. use this model with path-planning), one needs to consider directions whose paths collide with each others: if a direction is no longer atomic, this means that there are at least two paths leading to it, from the current unit position. The added complexity of dealing with these paths (and their possible collision routes with allied units or going through potential damages) may not be very aligned with the very reactive behavior that we envisioned here. It is a middle between our proposed solution and full path-planning, for which it is costly to consider several dynamic different influences leading to frequent re-computation.

Probabilistic modality

Finally, we could use multi-modality [Colas et al., 2010] to get rid of the remaining (small: fire-retreat-move) FSM. Instead of being in “hard” modes, the unit could be in a weighted sum of modes (summing to one) and we would have:

5.6.2 Conclusion

We have implemented this model in StarCraft, and it outperforms the original AI as well as other bots. Our approach does not require a specific vertical integration for each different type of objectives (higher level goals), as opposed to CBR and reactive planning [Ontañón et al., 2007a, Weber et al., 2010b]: it can have a completely different model above feeding sensory inputs like Obj_i. It runs in real-time on a laptop (Core 2 Duo) taking decisions for every units 24 times per second. It scales well with the number of units to control thanks to the absence of communication at the unit level, and is more robust and maintainable than a FSM. Particularly, the cost to add a new sensory input (a new effect on the units behavior) is low.

Chapter 6
Tactics

This work was accepted for publication at Computational Intelligence in Games (IEEE CIG) 2012 in Grenada [Synnaeve and Bessière, 2012a] and will be presented at the Computer Games Workshop of the European Conference of Artificial Intelligence (ECAI) 2012 [Synnaeve and Bessière, 2012b].

• Problem: make the most efficient tactical decisions (attacks and defenses) in the absolute (knowing everything: armies positions, players intentions, effects of each possible actions).
• Problem that we solve: make the most efficient tactical decisions (in average) knowing what we saw from the opponent and our model of the game.
• Type: prediction is problem of inference or plan recognition from partial observations; adaptation given what we know is a problem of decision-making under uncertainty.
• Complexity: the complexity of tactical moves has not been studied particularly, as “tactics” are hard to bound. If taken form the low-level actions that units perform to produce tactics, the complexity is that of micro-management performed on the whole map and is detailed in section 4.2. Players and AI build abstractions on top of that, which enables them to reason about enemy tactics and infer what they should do from only partial observations. For these reasons, we think that tactics, at this abstract level, can be modeled as a POMDP* with partial observations of the opponent’s tactics (identifying them from low-level observations is already an arduous task), actions as our tactics, and transition probabilities defined by player’s skills and the game state. Our solutions are real-time on a laptop.

6.1 What are tactics?

6.1.1 A tactical abstraction

In their study on human like characteristics in RTS games, Hagelbäck and Johansson Hagelbäck and Johansson [2010] found out that “tactics was one of the most successful indicators of whether the player was human or not”. Tactics are in between strategy (high-level) and micro-management (lower-level), as seen in Fig. 4.5. When players talk about specific tactics, they use a specific vocabulary which represents a set of actions and compresses subgoals of a tactical goal in a sentence.

Units have different abilities, which leads to different possible tactics. Each faction has invisible (temporarily or permanently) units, flying transport units, flying attack units and ground units. Some units can only attack ground or air units, some others have splash damage attacks, immobilizing or illusion abilities. Fast and mobile units are not cost-effective in head-to-head fights against slower bulky units. We used the gamers’ vocabulary to qualify different types of tactics:

• ground attacks (raids or pushes) are the most normal kind of attacks, carried by basic units which cannot fly,
• air attacks (air raids), which use flying units’ mobility to quickly deal damage to undefended spots.
• invisible attacks exploit the weaknesses (being them positional or technological) in detectors of the enemy to deal damage without retaliation,
• drops are attacks using ground units transported by air, combining flying units’ mobility with cost-effectiveness of ground units, at the expense of vulnerability during transit.

This will be the only four types of tactics that we will use in this chapter: how did the player attack or defend? That does not mean that it is an exhaustive classification, nor that our model can not be adapted a) to other types of tactics b) to dynamically learning types of tactics.

RTS games maps, StarCraft included, consist in a closed arena in which units can evolve. It is filled with terrain features like uncrossable terrain for ground units (water, space), cliffs, ramps, walls. Particularly, each RTS game which allows production also give some economical (gathering) mechanism and so there are some resources scattered on the map, where players need to go collect. It is way more efficient to build expansion (auxiliary bases) to collect resources directly on site. So when a player decides to attack, she has to decide where to attack, and this decision takes into account how it can attack different places, due to their geographical remoteness, topological access posibilities and defense strengh. Choosing where to attack is a complex decision to make: of course it is always wanted to attack poorly defended economic expansions of the opponent, but the player has to consider if it places its own bases in jeopardy, or if it may trap her own army. With a perfect estimator of battles outcomes (which is a hard problem due to terrain, army composition combinatorics and units control complexity), and perfect information, this would result in a game tree problem which could be solved by alpha-beta. Unfortunately, StarCraft is a partial observation game with complex terrain and fight mechanics.

6.1.2 Our approach

The idea is to have (most probably biased) lower-level heuristics from units observations which produce information exploitable at the tactical level, and take advantage of strategic inference too. For that, we propose a model which can either predict enemy attacks or give us a distribution on where and how we should attack the opponent. Information from the higher-level strategy [Synnaeve and Bessière, 2011, Synnaeve and Bessière, 2011b] (Chapter 7) constrains what types of attacks are possible. As shown in Fig. 6, information from units’ positions (or possibly an enemy units particle filter as in [Weber et al., 2011] or Chapter 9.2) constrains where the armies can possibly be in the future. In the context of our StarCraft bot, once we have a decision: we generate a goal (attack order) passed to units groups, which set the objectives of the low-level Bayesian units control model [Synnaeve and Bessière, 2011a] (Chapter 5).

6.2 Related work

On spatial reasoning, Pottinger [2000] described the BANG engine implemented for the game Age of Empires II (Ensemble Studios), which provides terrain analysis functionalities to the game using influence maps and areas with connectivity information. Forbus et al. [2002] presented a tactical qualitative description of terrain for wargames through geometric and pathfinding analysis. Hale et al. [2008] presented a 2D geometric navigation mesh generation method from expanding convex regions from seeds. Perkins [2010] automatically extracted choke points and regions of StarCraft maps from a pruned Voronoi diagram, which we used for our regions representations (see below).

Hladky and Bulitko [2008] benchmarked hidden semi-Markov models (HSMM) and particle filters in first person shooter games (FPS) units tracking. They showed that the accuracy of occupancy maps was improved using movement models (learned from the player behavior) in HSMM. Bererton [2004] used a particle filter for player position prediction in a FPS. Kabanza et al. [2010] improve the probabilistic hostile agent task tracker (PHATT [Geib and Goldman, 2009], a simulated HMM for plan recognition) by encoding strategies as HTN, used for plan and intent recognition to find tactical opportunities. Weber et al. [2011] used a particle model for hidden units’ positions estimation in StaCraft.

Aha et al. [2005] used case-based reasoning (CBR) to perform dynamic tactical plan retrieval (matching) extracted from domain knowledge in Wargus. Ontañón et al. [2007a] based their real-time case-based planning (CBP) system on a plan dependency graph which is learned from human demonstration in Wargus. A case based behavior generator spawn goals which are missing from the current state and plan according to the recognized state. In [Mishra et al., 2008a, Manish Meta, 2010], they used a knowledge-based approach to perform situation assessment to use the right plan, performing runtime adaptation by monitoring its performance. Sharma et al. [2007] combined Case-Based Reasoning (CBR)* and reinforcement learning to enable reuse of tactical plan components. Bakkes et al. [2009] used richly parametrized CBR for strategic and tactical AI in Spring (Total Annihilation open source clone). Cadena and Garrido [2011] used fuzzy CBR (fuzzy case matching) for strategic and tactical planning (including expert knowledge) in StarCraft. Chung et al. [2005] applied Monte-Carlo planning for strategic and tactical planning to a capture-the-flag mode of Open RTS. Balla and Fern [2009] applied upper confidence bounds on trees (UCT: a MCTS algorithm) to tactical assault planning in Wargus.

In Starcraft, Weber et al. [2010a,b] produced tactical goals through reactive planning and goal-driven autonomy, finding the more relevant goal(s) to follow in unforeseen situations. Wintermute et al. [2007] used a cognitive approach mimicking human attention for tactics and units control in ORTS. Ponsen et al. [2006] developed an evolutionary state-based tactics generator for Wargus. Finally, Avery et al. Avery et al. [2009] and Smith et al. Smith et al. [2010] co-evolved influence map trees for spatial (tactical) reasoning in RTS games.

6.3 Perception and tactical goals

6.3.1 Space representation

The maps on which we play restrain movement and vision of ground units (flying units are not affected). As ground units are much more prevalent and more cost-efficient than flying units, being able to reason about terrain particularities is key for tactical reasoning. For that, we clustered the map in regions. We used two kinds of regions:

• BroodWar Terrain Analyser (BWTA)*¹ regions and choke-dependent (choke-centered) regions (CDR). BWTA regions are obtained from a pruned Voronoi diagram on walkable terrain [Perkins, 2010] and give regions for which chokes are the boundaries. We will note this regions “Reg” or regions.
• As battles often happens at chokes, choke-dependent regions are created by doing an additional (distance limited) Voronoi tessellation spawned at chokes, its regions set is (regions \ chokes) ∪ chokes. We will note this regions “CDR” or choke-dependent regions.

Figure 6.2 illustrate regions and choke-dependent regions (CDR). Results for choke-dependent regions are not fully detailed. Figure B.2 (in appendix) shows a real StarCraft map and its decomposition into regions with BWTA.

6.3.2 Evaluating regions

Partial observations

From partial observations, one has to derive meaningful information about what may be the state of the game. For tactics, as we are between micro-management and strategy, we are interested in knowing:

• enemy units positions. In this chapter, we consider that units we have seen and that are now under the fog of war* are at the last seen position for some time (≈ few minutes), and then we have no clue where they are (uniform distribution on regions which are not visible) but we know that they exist. We could diffuse their position (respecting the terrain constraints for ground units) proportionally to their speed, or use a more advanced particle filter as Weber et al. [2011] did for StarCraft, or as explained in section 8.1.5.
• enemy buildings positions. For that, we will simply consider that buildings do not move at all (that is not completely true as some Terran buildings can move, but a good assumption nevertheless). Once we have seen a building, if we have not destroyed it, it is there, even under the fog of war*.
• enemy strategy (aggressiveness and tech tree* for instance). Here, we will only use the estimation of the enemy’s tech tree as it is the output of a part of our strategy estimation in chapter 7.

The units and buildings perceptions are too low-level to be exploited directly in a tactical model. We will now present importance and defense scoring heuristics.

Scoring heuristics

To decide where and how to attack (or defend), we need information about the particularity of above-mentioned regions. For that, we built heuristics taking low-level information about enemy units and buildings positions, and giving higher level estimator. They are mostly encoding common sense. We do not put too much care into building these heuristics because they will also be used during learning and the learned parameters of the model will have adapted it to their bias.

The value of a unit is just minerals_value + gas_value + 50supply_value. For instance the value of an army with 2 dragoons and 1 zealot is: v_army = 2(125 + 50 + 50 × 2) + (100 + 50 × 2). Now, we note v_type^a(r) the value of all units of a given type from the attacker (^a) in region r. We can also use v^d for the defender. For instance v_dragoon^d(r) is the sum of the values of all dragoons in region r from the defender (^d). The heuristics we used in our benchmarks are:

• economical score: number of workers of the defender on her total number of workers in the game.
• tactical score: sum of the values of the defender’s armies forces in each regions, divided by the distance between the region in which each army is and the region at hand (to a power > 1). We used a power of 1.5 such that the tactical value of a region in between two halves of an army, each at distance 2, would be higher than the tactical value of a region at distance 4 of the full (same) army. For flying units, dist is the Euclidean distance, while for ground units it takes pathfinding into account.
• ground defense score: the value of the defender’s units which can attack ground units in region r, divided by the score of ground units of the attacker in region r.
• air defense score: the value of the defender’s units which can attack flying units in region r, divided by the score of flying units of the attacker in region r.
• invisible defense score: the number of the defender’s detectors (units which can view otherwise invisible units) in region r.

6.3.3 Tech tree

Our model also uses the estimation of the opponent’s tech tree* to know what types of attacks are possible from them. An introduction to the tech tree is given in section 4.1.1. The tech tree is the backbone of the strategy: it defines what can and what cannot be built by the player. The left diagram of Figure 6.3 shows the tech tree of the player after completion of the build order 4.1 in section 4.1.1. The strategic aspect of the tech tree is that it takes time (between 30 seconds to 2 minutes) to make a building, so tech trees and their evolutions through time result from a plan and reveal the intention of the player.

From partial observations, a more complete tech tree can be reconstructed: if an enemy unit which requires a specific building is seen, one can infer that the whole tech tree up to this unit’s requirements is available to the opponent’s. Further in section 7.5, we will show how we took advantage of probabilistic modeling and learning to infer more about the enemy build tree from partial observation. In this chapter, we will limit our use of tech trees to be an indicator of what types of attacks can and cannot be committed.

6.3.4 Attack types

With the discretization of the map into regions and choke-dependent regions, one can reason about where attacks will happen. The types of the attacks depends on the units types involved and their use. There may be numerous variations but we decided to keep the four main types of attacks in the vocabulary of gamers:

• ground attacks, which may use all types of units (and so form the large majority of attacks). They are constrained by the map topography and by units collisions so chokes are very important: they are an advantage for the army with less contact units but enough ranged units or simply more ranged units, and/or the higher ground.
• air raids, air attacks, which can use only flying units. They are not constrained by the map, and the mobility of most flying units (except the largest) allows the player to attack quickly anywhere. Flying units are most often not cost-effective against ranged ground units, so their first role is to harass the economy (workers, tech buildings) and fight when in large numerical superiority (interception, small groups) or against units which cannot attack air units, all thanks to their mobility and ease of repositioning.
• invisible (ground) attacks, which can use only a few specific units in each race (Protoss Dark Templars, Terran Ghosts, Zerg Lurkers). When detected, this units are not cost-effective. There are two ways to use invisible attacks: as an all-in as soon as possible (because reaching the technology required to produce such units is costly and long), before that the enemy has detection technology. This is a risky strategy but with a huge payoff (sometimes simply the quick win of the game). The second way is to try and sneak invisible units behind enemy lines to sap the opponent’s economy.
• drop attacks, which need a transport unit (Protoss Shuttle, Terran Dropship, Zerg Overlord with upgrade). Transports give the mobility of flying units to ground units, with the downsides that units cannot fire when inside the transport. The usefulness of such attacks comes from the fact that they are immediately available as soon as the first transport unit is produced (because the ground units can be produced before it) and that they do not sacrifice cost-efficiency of most of the army. The downside is that transports are unarmed and are at the mercy of interceptions. The goals of such attacks are either to sap the opponent’s economy (predominantly) or to quickly reinforce an army while maximizing micro-management of units.

The corresponding goal (orders) are described in section 8.1.2.

6.4 Dataset

6.4.1 Source

We downloaded more than 8000 replays* to keep 7649 uncorrupted, 1v1 replays from professional gamers leagues and international tournaments of StarCraft, from specialized websites^{2 3 4} . We then ran them using BWAPI⁵ and dumped units’ positions, pathfinding and regions, resources, orders, vision events, for attacks: types, positions, outcomes. Basically, every Brood War Application Programmable Interface (BWAPI)* event, plus attacks, were recorded, the dataset and its source code are freely available⁶ . The implication of considering only replays of very good player allows us to use this dataset to learn the behaviors of our bot. Otherwise, particularly regarding the economy, a simple bot (AI) coupled with a planner can beat the average player, who does not have a tightly timed build order and/or not the sufficient APM* to execute.

6.4.2 Information

Table 6.1 shows some metrics about the dataset. In this chapter, we are particularly interested in the number of attacks. Note that the numbers of attacks for a given race have to be divided by two in a given non-mirror match-up. So, there are 7072 Protoss attacks in PvP but there are not 70,089 attacks by Protoss in PvT but about half that.

By running the recorded games (replays*) through StarCraft, we were able to recreate the full state of the game. Time is always expressed in games frames (24 frames per second). We recorded three types of files:

• general data (see appendix B.3): records the players’ names, the map’s name, and all information about events like creation (along with morph), destruction, discovery (for one player), change of ownership (special spell/ability), for each units. It also shows attack events (detected by a heuristic, see below) and dumps the current economical situation every 25 frames: minerals*, gas*, supply* (count and total: max supply*).
• order data (see appendix B.4): records all the orders which are given to the units (individually) like move, harvest, attack unit, the orders positions and their issue time.
• location data (see appendix B.5): records positions of mobile units every 100 frames, and their position in regions and choke-dependent regions if they changed since last measurement. It also stores ground distances (pathfinding-wise) matrices between regions and choke-dependent regions in the header.

From this data, one can recreate most of the state of the game: the map key characteristics (or load the map separately), the economy of all players, their tech (all researches and upgrades), all the buildings and units, along with their orders and their positions.

6.4.3 Attacks

We trigger an attack tracking heuristic when one unit dies and there are at least two military units around. We then update this attack until it ends, recording every unit which took part in the fight. We log the position, participating units and fallen units for each player, the attack type and of course the attacker and the defender. Algorithm 5¹⁰ shows how we detect attacks.

---

Algorithm 5: Simplified attack tracking heuristic for extraction from games. The heuristics to determine the attack type and the attack radius and position are not described here. They look at the proportions of units types, which units are firing and the last actions of the players.

 list tracked_attacks
 function UNIT_DEATH_EVENT(unit)
  tmp ← tracked_attacks.which_contains(unit)
  if tmp≠∅ then
  tmp.update(unit) ⇔ update(tmp,unit)
  else
  tracked_attacks.push(attack(unit))
  end if
 end function
 function ATTACK(unit) new attack constructor
  self ⇔ this
  self.convex_hull ← propagate_default_hull(unit)
  self.type ← determine_attack_type(update(self,unit))
  return self
 end function
 function UPDATE(attack,unit)
  attack.update_hull(unit) takes units ranges into account
  c ← get_context(attack.convex_hull)
  self.units_involved.update(c)
  self.tick ← default_timeout()
  return c
 end function
 function TICK_UPDATE
  self.tick ← self.tick - 1
  if self.tick < 0 then
  self.destruct()
  end if
 end function

---

6.5 A Bayesian tactical model

6.5.1 Tactical Model

We preferred to map the continuous values from heuristics to a few discrete values to enable quick complete computations. Another strategy would keep more values and use Monte-Carlo sampling for computation. We think that discretization is not a concern because 1) heuristics are simple and biased already 2) we often reason about imperfect information and this uncertainty tops discretization fittings.

Variables

With n regions, we have:

• A_1:n ∈{true,false}, A_i: attack in region i or not?
• E_1:n ∈{no,low,high}, E_i is the discretized economical value of the region i for the defender. We choose 3 values: no workers in the regions, low: a small amount of workers (less than half the total) and high: more than half the total of workers in this region i.
• T_1:n ∈ discrete levels, T_i is the tactical value of the region i for the defender, see above for an explanation of the heuristic. Basically, T is proportional to the proximity to the defender’s army. In benchmarks, discretization steps are 0,0.05,0.1,0.2,0.4,0.8 (log₂ scale).
• TA_1:n ∈ discrete levels, TA_i is the tactical value of the region i for the attacker (as above but for the attacker instead of the defender).
• B_1:n ∈ {true,false}, B_i tells if the region belongs (or not) to the defender. P(B_i = true) = 1 if the defender has a base in region i and P(B_i = false) = 1 if the attacker has one. Influence zones of the defender can be measured (with uncertainty) by P(B_i = true) ≥ 0.5 and vice versa. In fact, when uncertain, P(B_i = true) is proportional to the distance from i to the closest defender’s base (and vice versa).
• H_1:n ∈{ground,air,invisible,drop}, H_i: in predictive mode: how we will be attacked, in decision-making: how to attack, in region i.
• GD_1:n ∈ {no,low,med,high}: ground defense (relative to the attacker power) in region i, result from a heuristic. no defense if the defender’s army is ≥ 1∕10th of the attacker’s, low defense above that and under half the attacker’s army, medium defense above that and under comparable sizes, high if the defender’s army is bigger than the attacker.
• AD_1:n ∈{no,low,med,high}: same for air defense.
• ID_1:n ∈{no detector,one detector,several}: invisible defense, equating to numbers of detectors.
• TT ∈ [∅,building₁,building₂,building₁ ∧ building₂,techtrees,…]: all the possible technological trees for the given race. For instance {pylon,gate} and {pylon,gate,core} are two different Tech Trees, see chapter 7.
• HP ∈{ground,ground∧air,ground∧invis,ground∧air∧invis,ground∧ drop,ground∧air∧drop,ground∧invis∧drop,ground∧air∧invis∧drop}: how possible types of attacks, directly mapped from TT information. This variable serves the purpose of extracting all that we need to know from TT and thus reducing the complexity of a part of the model from n mappings from TT to H_i to one mapping from TT to HP and n mapping from HP to H_i. Without this variable, learning the co-occurrences of TT and H_i is sparse in the dataset. In prediction, with this variable, we make use of what we can infer on the opponent’s strategy Synnaeve and Bessière [2011b], Synnaeve and Bessière [2011], in decision-making, we know our own possibilities (we know our tech tree as well as the units we own).