GHOST: A Combinatorial Optimization Framework for Real-Time Problems PDF

IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 8, NO. 4, DECEMBER 2016 377 GHOST: A Combinatorial Optimization Framework for Real-Time Problems...

IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 8, NO. 4, DECEMBER 2016 377 GHOST: A Combinatorial Optimization Framework for Real-Time Problems Florian Richoux, Alberto Uriarte, and Jean-François Baffier Abstract—This paper presents GHOST, a combinatorial opti- (CSP/COP) models. Among others, branch and bound algo- mization framework that a real-time strategy (RTS) AI developer rithms have been used to optimize build order (BO) in Churchill can use to model and solve any problem encoded as a constraint and Buro. Genetic algorithms have been used offline to op- satisfaction/optimization problem (CSP/COP). We show a way to model three different problems as a CSP/COP, using instances from timize BOs with multiple objectives, and have been analyzed in the RTS game StarCraft as test beds. Each problem belongs to a Kuchem et al.. Also, a population-based algorithm has been specific level of abstraction (the target selection as reactive con- used for multiobjective procedural aesthetic map generation in trol problem, the wall-in as a tactics problem, and the build order Lara-Cabrera et al.. Still, CSP/COP offers a convenient, ho- planning as a strategy problem). In our experiments, GHOST shows mogeneous framework that is able to model a large number of good results computed within some tens of milliseconds. We also show that GHOST outperforms state-of-the-art constraint solvers, combinatorial optimization problems, and proposes various sets matching them on the resources allocation problem, a common of algorithms to solve them. combinatorial optimization problem. CSP/COP is widely used in AI to solve problems, such us Index Terms—Combinatorics, constraint optimization problem pathfinding, scheduling, and logistics. Unlike mathematical (COP), constraint satisfaction problem (CSP), game artificial in- programming, CSP/COP algorithms are not usually designed to telligence (AI), optimization, real-time strategy (RTS), solver, solve one specific problem but are general, i.e.they are able to StarCraft. manage any problem modeled in that framework. Besides the generality, it is also easy and intuitive to model a problem with a I. INTRODUCTION CSP/COP. Altogether, these bring ideal conditions to design and develop a user-friendly, easy-to-extend, and generalized solver. NE can see games as a simplification of the world: the O domain is smaller and the rules are easier and less nu- merous, thus possibilities are more limited. However, games A. RTS problem families are rich enough to propose complex and dynamic environments Ontañón et al. propose in to decompose RTS problems where it remains difficult for a computer to make predictions, into three families, according to their level of abstraction. From have a global understanding of the current situation, and then the higher to the lower level, these families are as follows. make a decision. This is especially true when information is 1) Strategy corresponds to the high-level decision-making incomplete, forcing the computer to infer the global state of the process. This is the highest level of abstraction for game game from pieces of information. This is the case with real-time comprehension. Finding an efficient strategy or counter- strategy (RTS) games, where a Clausewitz’s fog of war hides the strategy against a given opponent is key in RTS games. opponent’s moves. Hence, RTS games are a good domain for It concerns the whole set of units and buildings a player testing AI techniques that could be applied afterward in other owns. domains. 2) Tactics are the implementation of the current strategy. It As compiled in the surveys from Ontañón et al. and implies army and building positioning, movements, tim- Robertson and Watson , many AI techniques have been ing, and so on. Tactics concerns a group of units. explored in RTS games. However, there are few works in 3) Reactive control is the implementation of tactics. This RTS game AI using constraint programming techniques, in consists in moving, targeting, firing, fleeing, hit-and-run particular through constraint satisfaction/optimization problem techniques (also known as “kiting”) during battle. Reac- tive control focuses on a specific unit. Manuscript received September 30, 2014; revised December 31, 2015 and Problems from different families usually involve different April 18, 2016; accepted May 21, 2016. Date of publication May 26, 2016; date of current version December 13, 2016. algorithms to solve them. In this paper, we model one problem F. Richoux is with the Le Laboratoire d’informatique de Nantes Atlan- for each of these three families. Then, we use our framework tique, Université de Nantes, Nantes 44322, France and also with the Japanese– GHOST to solve them without any modifications of its inner French Laboratory for Informatics, University of Tokyo, Tokyo 113-0033, Japan (e-mail: [email protected]). solver. A. Uriarte is with the Computer Science Department, Drexel University, Philadelphia, PA 19104 USA (e-mail: [email protected]). J.-F. Baffier is with the Japan Science and Technology Agency-ERATO Kawarabayashi Large Graph Project, National Institute of Informatics, Tokyo B. StarCraft: Brood War 101-8430, Japan (e-mail: [email protected]). StarCraft: Brood War is an RTS game, where three different Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. races (Terran, Protoss, and Zerg) can be played, giving an asym- Digital Object Identifier 10.1109/TCIAIG.2016.2573199 metric but well-balanced strategy game. In this paper, the term 1943-068X © 2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications standards/publications/rights/index.html for more information. 378 IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 8, NO. 4, DECEMBER 2016 “StarCraft” will actually refer to the game plus its expansion exist to solve them. Then, we present GHOST architecture, what StarCraft: Brood War. user is targeted, how to use it to solve an already encoded prob- StarCraft has been a worldwide success, and as of time of lem, and how to write your own problems via GHOST. Sections publication, it remains the most sold RTS game with nearly 10 III, IV, and V give details about three different problems, each millions of copies distributed.1 It has been (and still is until now) one from a specific level of abstraction (from the lower to the particularly popular in South Korea, where a StarCraft league higher: reactive control, tactics, and strategy), how we model has been specially created for the game, organizing televised them into a CSP/COP, and what results we obtain by applying tournaments between sponsored players and teams. Korean pro- GHOST. Section VI matches GHOST with state-of-the-art con- fessional players, or pro-gamers, are reputed to be among the straint solvers. Finally, this paper concludes with future work. best StarCraft pro-gamers in the world. A player has to gather two types of resources (minerals and II. GHOST: A GENERAL METAHEURISTIC OPTIMIZATION gas) in order to construct buildings. Those buildings are nec- SOLVING TOOL essary to produce units, to upgrade properties such as damage GHOST is a combinatorial optimization framework designed points or armor, and to unlock technologies and special abilities. to tackle real-time problems, helping a programmer to model Producing units costs resources depending on their properties his/her problem and to solve it using the inner solver, without (hit points, damage points, or size). needing parameter tuning or advanced knowledge in constraint The game is played on a rectangular map, discretized into programming. RTS games exhibit many real-time combinatorial two types of tiles: walkable tiles, composed of 8 × 8 pixels and optimization problems that can be modeled and solved via a buildable tiles composed of 4 × 4 walkable tiles, i.e., 32 × 32 constraint programming framework. Moreover, a solver dealing pixels. The difference between these two types of tiles would be with such problems must be fast: in the game industry, only a explained in Section IV while introducing the wall-in problem. small percentage of CPU time is allocated for AI (usually no Like most RTS games, the map is covered by a fog of war more than 10%). This is particularly true for RTS games, where that obscures players vision of the map everywhere beyond the the AI has a small amount of time (often less than 100 ms) range of their own (or allied) units/buildings. This means that to solve a problem. For instance, while some problems can the player cannot know at any time the full state of the game, be solved within several frames, other problems such us target unless the whole map is within their vision. Also, the player has selection or pathfinding need a solution as soon as possible to deal with a supply capacity, limiting the number of units he (optimally within one frame). can have. The player can increase it by constructing the right building or producing the right unit, according to the race. The flow of time in StarCraft is complex: the game has seven A. Brief Introduction to CSP/COP speed modes from “slowest” to “fastest” where “normal” cor- CSP and COP are two close formalisms extensively used in responds to the regular frame rate (14.96 logical frames per AI to solve combinatorial optimization problems. Constraint second, against 23.81 for the fastest mode). This is why when programming allows an intuitive and uniform way to model we will write about in-game time, all along this paper and in par- problems, as well as different general algorithms able to solve ticular in Section V, we will refer to logical frames (simply de- any (decidable) problems modeled by a CSP or a COP. noted as frames) rather than seconds to avoid confusions. In the The difference between a CSP and a COP is simple. fastest mode, one logical game frame takes 42 ms. In StarCraft 1) A CSP models a satisfaction problem, i.e., a problem AI competitions, it is necessary for bots to perform calculations where all solutions are equivalent; the goal is then to just in under 55 ms per frame; a bot that takes more than 55 ms per find one of them, if any. For instance, finding a solution of frame in 200 frames or more automatically loses the game. a Sudoku grid. Several solutions may exist, but finding one is sufficient, and no solutions seem better than another one. C. Goals and Summary 2) A COP models an optimization problem, where some solutions are better than others. For instance, several paths The research presented in this paper is an extension of Ri- may exist from home to workplace, but one of them is the choux et al. , where the problem to make a wall at a given shortest. chokepoint (a narrow passage) in StarCraft has been modeled Formally, a CSP is defined by a tuple (V , D, C) such that: and solved thanks to an ad hoc algorithm. 1) V is a set of variables; The research presented in this paper has two goals: 2) D is a domain, i.e., a set of values for variables in V ; 1) to present to the RTS AI community our framework 3) C is a set of constraints. GHOST, its architecture, how to model different problems A constraint c ∈ C can be seen as a k-ary predicate c : V k → with it, and the results we obtained; {, ⊥}, where  can be semantically interpreted as true and ⊥ 2) to show that constraint programming can be successfully as false. Thus, regarding the value of the vector V k , we say that used in RTS AI at any level of abstraction. c is either satisfied (equal to ) or unsatisfied (equal to ⊥). The paper is organized as follows. In Section II, we give a Notice also that D should formally be the set of the domain short introduction on constraint satisfaction/optimization prob- for each variable in V , thus a set of sets of values. However, it lems, how they model problems, and what kind of algorithms is common to define the same set of values for all variables of V , thus one can simplify D to be the set of values each variable 1 http://www.msnbc.msn.com/id/18925251/ in V can take. RICHOUX et al.: GHOST: A COMBINATORIAL OPTIMIZATION FRAMEWORK FOR REAL-TIME PROBLEMS 379 A COP is defined by a tuple (V , D, C, f ) where V , D, and C represent the same sets as a CSP, and f is an objective function to minimize or maximize. Upon a CSP or a COP, one can build a CSP formula or a COP formula, respectively. A CSP/COP formula is a con- junction of constraints from C, each constraint taking their variables from V. We say a CSP/COP formula is satisfied if there exists an assignment q : V → D such that each constraint of the formula is satisfied. Considering the vector v ∈ V n of Fig. 1. GHOST architecture: in red, the satisfaction inner loop, running for variables used in a CSP/COP formula, a vector z ∈ Dn such x microseconds top; in blue, optimization mechanisms. The whole process, that ∀i ∈ {1, n}, z[i] = q(v[i]) is called a configuration. Since excluding optimization postprocess, runs under y microseconds. Both x and y CSP/COP models a specific problem P, a CSP/COP formula are user inputs. represents an instance of P. Roughly speaking, there are two different kinds of algorithms could implement, in particular those concerning AI and RTS to solve CSP/COP problems. games. Two different users are targeted. 1) Tree-based search algorithms, also called complete algo- 1) The casual user, who only wants to use GHOST to solve rithms, completely explore the search space for solutions. an already encoded problem, like the three problems pre- These algorithms use smart moves (such as backtracking sented in the next sections. This user only needs to in- or forward checking) to localize and avoid dead-ends in stantiate variables, the domain, constraints and possibly the search space. an objective to describe the instance of his problem, and 2) Metaheuristics, also called incomplete algorithms, are to call the function solve of the inner solver to run the based upon local moves to find optimums, rather than search. This is done in five short C++ lines. looking at the problem as a whole. In practice, these al- 2) The developer user, who has a specific problem not written gorithms are more suitable to handle industrial-size prob- with GHOST yet. GHOST has been designed to make easy lems within a reasonable runtime. On the other hand, they the implementation of new problems without changing a cannot prove they have found an optimal solution, nei- single line in the solver and the existing code, and without ther they cannot prove there are no solutions to the given expertise needed in constraint programming. Also, GHOST problem. inner solver has been designed to have as few parameters GHOST uses a metaheuristic algorithm, Adaptive Search from as possible, to avoid tedious and time-consuming param- Codognet and Diaz , as the heart of its solver. The reason we eters tuning before obtaining interesting results. have chosen a metaheuristics is simple: to solve combinatorial GHOST is implemented around five main C++ classes: Vari- optimization problems while playing a RTS game, the solver able, Domain, Constraint, Objective and Solver.3 needs to find a solution very quickly, often within some tens The function solve defined in Solver follows the steps of milliseconds, which is virtually impossible with tree-based exposed in Fig. 1. It is composed of two main loops: the outer search algorithms. Although it is not a well-known algorithm, loop for optimization, containing the inner loop for satisfac- we have chosen Adaptive Search because it is currently, to our tion. The satisfaction part, in red in Fig. 1, only tries to find a knowledge , one of the fastest metaheuristic algorithm. possible solution among all configurations, i.e., tries to find an In next sections, we will see that looking for the optimal assignment of each variable such that all constraints of the CSP solution is not always an interesting strategy for RTS games. are satisfied. It is possible to call Solver::solve without Indeed, it is sufficient to have a solution “optimal enough” in defining any objective functions. In that case, a default objec- some tens of milliseconds rather than spending seconds to find a tive is applied, doing nothing special, and the solver will output global optimum. Also, the reader has to keep in mind that since a solution that satisfied all constraints, if it finds one. metaheuristics are stochastic methods, two runs on the same If a “real” objective function is set, then the optimization problem instance can produce two different solutions within the part, in blue in Fig. 1, is triggered. Furthermore, it will influence same runtime. This is why results in this paper are the aver- the satisfaction part (finding a valid solution) if the objective age of 10 to 100 repeated experiments, regarding the problem. implements optional heuristics to select the variable to change These results with GHOST are very good on all tested problems, and the value to assign, in case the current configuration is not and often better than those produced by current state-of-the-art a solution. techniques. The optimization part also applies two optional postprocess optimizations: one on the output of the satisfaction loop, and one B. GHOST Architecture on the final output, giving the solution returned by the solver. We will detail the purpose of such functions later, in particular GHOST is a C++11 framework,2 under the GNU GPL v3 li- in Section IV. cense, designed to solve CSP/COP problems a game developer 3 See GHOST manual pages (http://richoux.github.io/GHOST/) for more 2 Source code available at https://github.com/richoux/GHOST details. 380 IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 8, NO. 4, DECEMBER 2016 The fundamental part in the optimization part is the opti- solve. The choice of designing a mono-objective framework mization loop itself. To explain how this loop works, we have to is pragmatic: multiobjective solvers are in general significantly introduce the two temporal parameters in GHOST. The function slower, since dealing with more complex problems. Multiobjec- solve takes two parameters: the first one (which is mandatory) tive solvers are also more difficult to implement, which makes is the satisfaction timeout x in μs, i.e., if a valid solution is not harder one goal of GHOST: to propose a framework both easy to found within x μs, we leave the satisfaction loop without a valid use and easy to extend by implementing new problems. one. The second parameter (which is optional) is the optimiza- In the next three sections, we explain how we modeled a re- tion timeout y in μs. It corresponds also to the total runtime active control problem, a tactic problem and a strategy problem of GHOST, modulo the postprocess after the optimization loop with a respective CSP/COP, and what results we obtained by (which is negligible in practice and should be about 100 times applying GHOST. We would like to emphasize that neither mod- smaller than y). If the y parameter is not given, then it is set to ifications or optimizations of the solver have been done to man- 10 times x. age these different problems, as well as the resources allocation Thus, the optimization loop repeats n times the satisfaction problem in Section VI. The core of the solver, i.e., everything in loop, and receives m ≤ n valid solutions. After receiving a new the Solver class, remains unchanged. Even if postprocesses solution from the satisfaction loop, and applying an eventual are defined differently in their respective Objective classes, satisfaction postprocess, it calls the objective function to com- the way they are included and called into the solver is rigorously pute the optimization cost, compares it with its saved solution (if the same. any) and keeps the solution with the lower cost. Then, it repeats the satisfaction loop to obtain a new solution, and so on, until y III. REACTIVE CONTROL PROBLEM: TARGET SELECTION μs are reached. Reactive control problems have been fairly well studied for In a way, GHOST is applying a sort of Monte Carlo sam- StarCraft, with many different techniques applied. Synnaeve pling. Notice that this is not Monte Carlo tree search (MCTS). and Bessière propose a Bayesian model allowing units to It would certainly be possible to implement a MCTS though move in groups without being in each other’s way or finding the GHOST, by using derived classes from Variable, Domain, right distance to attack. Uriarte and Ontañón use influence Constraint, and Objective. However, the authors do not maps for kiting, i.e., moving backward while the weapon is in recommend using GHOST in this way, since it should be more cooldown and then attacking forward when it is ready to shoot. efficient to develop a more robust MCTS implementation. Finally, Churchill et al. , present a heuristic search There is a third and last parameter in the solver: the length method that makes combat outcome predictions. These two last of the tabu list. Indeed, Adaptive Search contains a tabu list of papers are also among the rare ones dealing with the target explored variables in order to not revisit the same variable too selection problem in StarCraft. soon during the search. The tabu parameter is then a number expressing how long the solver has to wait before being allowed to revisit an explored variable. Actually, we also have imple- A. Problem Statement and Model mented escape mechanisms to not make this tabu list strict, by The target selection problem is a classical reactive control allowing the solver to draw a tabu variable if there are really no problem that a player has to deal with it several times in each other interesting variables. GHOST’s tabu list is thus more like a fight. Its satisfaction version is simple; it assigns to each unit of priority list. During our experiments, we found that a tabu length a fighting group a reachable target, i.e., an enemy unit within of |V | − 1 provided optimal performance. It is then a priori not our unit range. necessary to tune this parameter, however this remains possible In addition, one has also to take into account the waiting time to the developer user. between shots, also known as cooldown. Each unit type has A developer user has to build his own classes upon Vari- different cooldowns. We can now describe the target selection able, Domain, Constraint, and Objective, by inher- problem with the following CSP. iting from them. For instance, to create a class of variables CSP model for the target selection problem: representing units, this is done by class Unit : pub- Variables: A group of our units. lic Variable. Classes composed of other classes, like Do- Domain: A group of enemy units. main, which needs to know on what variables it will work with, Constraints: Each living, ready-to-shoot unit must aim a must instantiate the right templates. Thus, declaring the domain living enemy within its range, if any. for the target selection problem is done by class Target- Domain : public Domain. The target selection problem is a frame-by-frame problem: Concerning objective functions, GHOST has been designed to We only consider the question, “what enemy should I shoot minimize their value. If a developer user needs to maximize an this frame?” without looking at micromanagement moves like objective function f , this can be simply adapted to GHOST by kiting. This problem has been studied by Furtak and Buro defining objective functions 1/f or −f. Our framework is de- as an attrition game where they proved that this problem is in signed to deal with mono-objective optimization problem only, P-SPACE. thus, one can only choose at most one objective function at the Usually, RTS games define specific properties to each unit time before running the solve function. However, the objec- type making the target selection more subtle. Thus, in Star- tive function can be dynamically changed between two calls of Craft, each unit type has a size (small, medium, or large), and a RICHOUX et al.: GHOST: A COMBINATORIAL OPTIMIZATION FRAMEWORK FOR REAL-TIME PROBLEMS 381 TABLE I they aim the unit with the lowest current HP/initial HP ratio, or DAMAGE EFFICIENCY MATRIX IN StarCraft in other words, the unit which is the most likely to die soon. If several units share the same lowest ratio, then enemy units Damage Type select randomly one among them. Size Concussive Normal Explosive Our simulator does not implement the following: Small 100% 100% 50% 1) healing, repair, HPs, or shield regeneration; Medium 50% 100% 75% 2) terrain level (high/low ground); Large 25% 100% 100% 3) air shots (there is a small chance to miss the target); 4) friendly fire; 5) firebat’s unique splash damage, both linear and radial. damage type (concussive, normal, or explosive). Table I shows We ran 100 simulations for both objective functions until one the damage efficiency according to the aimed unit size and the group is completely annihilated, calling GHOST at each Star- shooter damage type. For instance, a normal-damage unit will Craft unit time. Potentially, the two groups can kill each other, always afflict a target with full damage, whatever the target size. leading to a draw. At the end of the simulation, we compute GHOST’s win rate, the average number of living units and the But a concussive-damage unit, like a Terran Vulture, will only inflict 5 damage points against a large unit like a Terran Tank, average HP of those units. For these experiments, we first fixed instead of 20 damage points as usual. the x satisfaction timeout and y optimization timeout param- Moreover, some units have a splash damage, afflicting dam- eters respectively to 1000 μs and 3000 μs, and we ran a new age to any unit inside an area. In StarCraft, there are two types series of experiments with parameters x = 2000 and y = 5000. of splash damage: the linear splash, where the damage area is In , , Churchill et al. propose an Alpha-Beta search with a line to the target; and the radial splash, where the damage a timeout of 5 ms (5000 μs). This is why we have chosen to area is a circled shockwave around the target with three splash set the optimization timeout to 3000 and 5000 μs to be able to radiuses. The first radius afflicts 100% of damage, the second compare our results with the same timeout and with a shorter one 50% and the last one 25%. one. Although, a direct comparison is not possible since their Splash damage combined with damage efficiency leads to goal is to guide the action selection and not only to decide the interesting optimization opportunities. In this paper, we investi- target selection. For this problem, we do not need any particular gate two different objective functions: postprocessing optimization. 1) Max Damage, where our group tries to deal as much dam- Table II4 shows that, if we allow 5 ms to GHOST to do com- age as possible within the current frame; putations, the Max Damage objective (shooting with the simple 2) Max Kill, where our group tries to kill as much enemy lowest HP ratio strategy exposed above) wins 99% of the time units as possible within the current frame. against the mirror unit group (and 98% within 3 ms). The Max Notice that these two objectives are more complex than look- Kill objective seems marginally less efficient with a win rate of ing for the maximal damage or the maximal dead enemies each 96% within 5 ms (94% within 3 ms). One explanation is that unit can achieve independently. For example, imagine a scenario Max Kill may not be as good a heuristic as Max Damage when where we have two units U1 and U2 and two enemies E1 and enemy units have their full HP. It would be interesting to cross E2 , such that U1 can afflict ten damage points to E1 and nine these two objectives to see if it leads to better results. to E2 , U2 can afflict eight damage points to E1 , but E2 is out For both objectives, we see that GHOST victories are undeni- of range, and E1 has five hit points (HPs) left. The best global able, with in average 2.75 remaining units after the simulation, assignment is U1 to E2 and U2 to E1 , even if U1 deals more whereas the rare losses are tight, with just one living enemy unit damage to E1. at the end of the combat. The average of total remaining HP is also very clearly in favor of GHOST. The enemy target selection heuristics actually leads to a list B. GHOST Implementation and Results of local optimums for each enemy unit independently, without Our instance is a mirror setup composed of four lines of units. considering the global situation, i.e., choices taken for partners. Line 1 contains five marines; line 2 has two Goliaths and two At the opposite, GHOST allows to look at the big picture and Vultures; line 3 has two Siege Tanks in tank mode and two search for a global optimum instead of a compilation of local Ghosts; and line 4 has one Siege Tank in siege mode. We chose ones. Results show this clearly make the difference. Terran units since many of them are long-range attack units and this makes the target selection problem more interesting. Also, C. Future Work we place them close to each other to make the Terran Siege To go further, we could implement additional objective func- Tank’s splash damage more significant. tions for the target selection problem, like minimizing damage We use a custom simulator to emulate combats between two waste, i.e., to try to be as close as zero HPs while killing an group of units. The simulator takes care of cooldowns, each unit enemy unit, or in another words trying to avoid to attack with a HP, damages and Euclidean distances between units. Ranges, 20 damage weapon a unit with only five HPs left. Even if GHOST damage efficiency, and splash damage are directly managed by GHOST. It is important to emphasize that, in this simulator, 4 All target experiment results and the simulator can be found at enemy units are applying very simple target selection heuristics: https://github.com/richoux/GHOST_paper/tree/master/xp/target 382 IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 8, NO. 4, DECEMBER 2016 TABLE II AVERAGE RESULTS OVER 100 SIMULATIONS FOR BOTH OBJECTIVE FUNCTIONS GHOST Victory Opponent Victory Objective Wins Draws Loses #Avg. living units Avg. HP #Avg. living units Avg. HP 3 ms Max Damage 98 1 1 2.8 237.9 1.0 12.0 Max Kill 94 5 1 3.0 250.8 1.0 3.0 5 ms Max Damage 99 1 0 2.6 231.9 0.0 0.0 Max Kill 96 4 0 2.6 233.6 0.0 0.0 The first table shows experiments where calls to GHOST lasts for 3 ms, and the second table calls lasting for 5 ms. is a mono-objective framework, we could craft new objectives by mixing already encoded ones, by simply applying a priority heuristics, like “maximize kills first, and consider maximizing damage as a tiebreaker.” The current implementation only deals with Terran ground units for the target selection problem. Extending it to all Star- Craft units would be easy. Finally, improving the current simu- lator or using SparCraft would make our experiments more accurate. IV. TACTICS PROBLEM: WALL-IN To our knowledge to our knowledge, tactics problems have not been intensively investigated for StarCraft. The exceptions are studies dealing with the wall-in problem like Certicky and the wall-in solver by Richoux et al.. As we already said, the latter provides the basis for this paper. A. Problem Statement and Model Fig. 2. Constraint are: Overlap (upper-left), Buildable (upper-right), NoHoles (bottom-left), and StartingTargetTile (bottom-right). Dark gray tiles represent A classic tactic to defend a base in RTS games is to make a unwalkable and unbuildable tiles. Light gray tiles are walkable but unbuildable wall, i.e., construct buildings side by side in order to close or to tiles. narrow the base entrance. Closing a base gives the player extra time to prepare a defense, or helps him to hide some pieces of information about his current strategy. Narrowing an entrance The wall-in problem has been first modeled in CSP by creates a bottleneck, which is easier to defend in case of invasion. Certicky in. Then, Richoux et al. proposed a differ- In this section, we focus only on walls constructed by buildings, ent model, always in CSP, in. The work published in discarding small narrow passages that can be closed by small the latter has been GHOST foundation. One can see GHOST units like workers. has a deep extension and generalization of the solver used We define two properties of buildings: their build size, and in. their real size. The build size is a pair (w, h) of build tiles. In For GHOST, the model of the wall-in problem is identical to order to create such a building, we need a rectangle of buildable the one in. tiles in the map (w build tiles for the width and h build tiles for the height). The real size is a pair (wp , hp ), such that wp ≤ 32 × w CSP model for the Wall-in problem and hp ≤ 32 × h, representing the actual size of the building in Variables: Buildings of the player race. pixels once it is constructed in the game, where 32 is the size Domain: Possible positions around the chokepoint. in pixels of a build tile in StarCraft. The real size of a building Constraints: Overlap, Buildable, NoHoles, and can then be smaller than its build size. This is actually always StartingTargetTile. the case in StarCraft. Constraints of our model are illustrated in Fig. 2. They are This means that two buildings constructed side by side are defined as follows. still separated by a gap which may be big enough to let small 1) Overlap: Buildings do not overlap each other’s. units go through. In this paper, we will call significant gap a 2) Buildable: Buildings do not overlap unbuildable tiles. gap that allows Zerglings, the smallest unit in StarCraft with 3) NoHoles: No holes of the size of a build tile (or greater) 16 × 16 pixels, to cross a wall. in the wall. RICHOUX et al.: GHOST: A COMBINATORIAL OPTIMIZATION FRAMEWORK FOR REAL-TIME PROBLEMS 383 TABLE III TABLE IV RESULTS OVER 48 CHOKEPOINTS EXTRACTED FROM 7 StarCraft MAPS PERCENTAGE OF SOLUTIONS FOUND FOR EACH MAP Objective Satisfaction run Optimization run %Solved (Opti) Map name Solved Building 4.05 2.56 98.04% Python 100 Gap 1.32 0.03 97.50% Heartbreak Ridge 100 TechTree 1.99 1.35 97.54% Circuit Breaker 99 Benzene 99 Results are the average of 100 runs for each chokepoint. Each calls of Aztec 97 GHOST lasts for 150 ms. Andromeda 96 Fortress 90 4) StartingTargetTile: There are exactly one building con- TABLE V structed on a given starting tile s, and one building (it can AVERAGE TIME OVER 20 RUNS TO FIND A SOLUTION be the same one) on a given target tile t. Actually, Overlap, Buildable, and NoHoles are sufficient to Chokepoint Buildings GHOST Clingo make a wall. We added the StartingTargetTile constraint to help width (pixels) needed Avg. time (ms) Avg. time (ms) the solver to find how to surround a chokepoint. 65 2 46.8 362.8 250 2 33.5 408.8 B. ghost Implementation and Results Like the target selection problem, we focus on the Terran race for our experiments. The wall-in problem offers many interest- 150 000, respectively. We can see in Table III5 that optimization ing optimization opportunities. Therefore, we have implemented runs lead to real improvements compared to satisfaction runs. three different objective functions, aiming to minimize. This is particularly true with the Gap objective, where signifi- 1) Building: The number of buildings in the wall, cant gaps are almost completely eliminated: 4680 of 4800 walls 2) Gap: The number of significant gaps in the wall, have been found (97.50%), and 4527 of them are perfect walls 3) TechTree: The required technology level in the game. In (i.e., without any significant gaps). In other words, 96.73% of games like StarCraft, some buildings are unlocked after walls found by GHOST are perfect. developing specific technologies. Therefore, it is interest- Since GHOST code has been improved compared to the solver ing to build walls with buildings of low technology. in , we obtained slightly better results. The percentage of To evaluate the technology level of a wall, we simply take the problems solved goes from 95%–96% to 97%–98%; walls de- depth in the technology tree of the most technological building cided with the Building objective were composed of 2.65 build- composing the wall. Thus, a Command Center has a depth 0, a ings against 2.56 now; the number of significant gaps goes Barracks a depth 1, a Factory a depth 2, and so on. from 0.05 to 0.03; and the technology level from 1.56 to 1.35. This time, the satisfaction postprocessing is important for Table IV shows the percentage of walls found in each of the these three objective functions, and the optimization postpro- seven maps from where chokepoints were extracted. These num- cessing really helps to improve the Gap and the TechTree bers correspond to pure satisfaction runs, since they do not differ objectives. significantly from optimization runs. We can see that GHOST has The role of the satisfaction postprocessing is to “clean” the more difficulties to find a wall for Fortress chokepoints. Actu- proposed wall, i.e., to remove all unnecessary buildings in the ally, it is failing from time to time on the same chokepoint, where valid solution, such that the resulting wall still satisfies the four a valid solution can only be achieved by using two 3 × 2-sized constraints of the model. The optimization postprocessing used buildings. with the Gap and TechTree objectives tries to swap each build- We also performed a comparison between GHOST and the ing of the proposed wall with another building from the set of state of the art for the walling problem, in this case the work variables V , of the same size and not already used in the wall. presented by Certicky. First, we limited the number of This simple permutation can drastically decrease the number possible buildings to be considered to the number of buildings of significant gaps between buildings and the technology level in Certicky’s work (two barracks and four supply depots) and required. Satisfaction runs in Table III are GHOST runs with- recorded the time to find a solution in two different cases: a small out any objective functions and with a satisfaction timeout of chokepoint (width of 65 pixels) and a big chokepoint (width of 160 000 μs, like in with the difference that in Richoux et al.’s 250). In Table V,6 we can see the average results of both solvers. paper, they compiled eight satisfaction runs of 20 000 μs (20 ms) The times include the computation needed for setting the solvers each to have great chances to find a valid solution. We measure parameters, the time to solve the problem, and the time to parse their average number of buildings, significant gaps, and technol- the solution (in the case of Certicky’s solution, we need to make ogy level in order to match them with optimization runs. Always following the experiment methodology of , optimization runs 5 All wall-in data and experiment results can be found at https://github.com/ are slightly disfavored since their global timeout is 150 000 μs, richoux/GHOST_paper/tree/master/xp/wallin thus 10 000 μs (10 ms) shorter than satisfaction runs. For op- 6 Comparison experiments can be found at https://bitbucket.org/auriarte/ timization runs, x and y parameters were fixed to 20 000 and bwta2/src 384 IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 8, NO. 4, DECEMBER 2016 an external call to Clingo solver). As we can see, GHOST is at The CSP model we propose for the BO plan problem is the least 7.8 times faster than Clingo in our experiments. GHOST is following one: faster in the wider chokepoint because the smaller one is a ramp and there is an overhead of computing the extremes of the ramp. CSP model for the BO Plan problem Variables: All actions we need to reach our goal. Domain: Order of actions. C. Future Work Constraints: Each dependency of an action α must occur For the wall-in problem, we could add new objective functions before α. to widen possibilities. For example, trying to make a wall by minimizing the cost, or the makespan. This last objective is harder and related to the next section (it is somehow the wall-in B. GHOST Implementation and Results problem combined with the BO problem). We have chosen to focus on Protoss to test GHOST on the BO Most importantly, since the required runtime to correctly op- problem. The current implementation can deal with any Protoss timize a wall is longer than a StarCraft frame duration, we could buildings, units, research works, and upgrades. implement GHOST in order to support computation pauses and For this problem, we have implemented one objective func- resumes. Actually, GHOST architecture has been designed with tion only: minimizing the BO makespan. With this objective this feature in mind. The satisfaction part is executed in 20 ms, function, we had not implemented a special satisfaction postpro- i.e., it can be executed within one StarCraft frame in the fastest cessing, but we did for the optimization postprocessing. Imagine speed. Marking a pause after each satisfaction loop and resume the case where the user asked, among others, to produce n units GHOST at the next frame until the computation ends would not of type U. Thus, GHOST will automatically add, recursively, all be difficult to do. This is discussed more in detail in Section VII. dependencies of U into the variable set. Suppose the unit type In addition to extend the current code to manage all StarCraft U is produced by the building of type B, and the user eventually races, results in Table IV give us the feeling that our wall-in asked for m < n buildings of type B. After having computed model can be refined again to reach a higher percentage of an optimized a BO, the optimization postprocessing will retake found solutions. this solution and try to see if it can shorten the makespan even more by constructing more buildings of type B, to speed up the production of units of type U. This postprocessing optimization V. STRATEGY PROBLEM: THE BO is significantly efficient in cases where the user asks for a high The reader can find an extensive literature about BO planner number n of the same unit U , and none or a low number m and prediction for StarCraft. Churchill and Buro propose in a of B. BO planner using a branch and bound technique, Kuchem et al. Unlike the target selection problem, this time we need to in- analyze BO tools for StarCraft II in , Cho et al. presented tegrate a simulator inside GHOST to emulate a game (without a strategy prediction and a BO adaptation system learning from combat) and be able to compute the makespan of BOs. Thus, replays, and in Synnaeve and Bessière show a Bayesian this simulator must emulate resource gathering, unit production model to predict the opponent BO. (including workers), supply capacity and construction. Our sim- ulator always tries to produce workers until reaching saturation (24 workers per base), as well as maintaining supply in order A. Problem Statement and Model to never be “supply blocked” (unable to produce a unit because A BO plan is a series of actions following a specific timing, we reached the supply capacity limit). in order to achieve a goal. Such a goal is a combination of build- In , Churchill and Buro give details about the simulator ings, units, upgrades, and research works produced. Usually, the they developed for their BO planner. We first used the same set- objective for a player is to reach a fixed goal, the fastest possible tings, but after matching GHOST results against BO from Korean way. However, alternatives can also be considered, like reaching pro-gamers, we realized that these settings were a bit too ad- the goal without sacrificing the economy, or focusing first on vantageous for the simulator. Then, we closely analyzed some units in order to have an army as soon as possible. replays from Korean pro-gamers to refine our simulator settings, A BO plan can be intuitively modeled by a CSP as a permu- listed in frames as follows: tation problem, where a bijection maps the set of variables to 1) time to go build something: 74 frames (96 in ); the domain. Changing the value of one variable is then actually 2) time to go back gathering minerals after building some- swapping its value with another variable. thing: 60 (0 in ); All actions have a (potentially empty) dependency list, i.e., 3) time to go from the base to mineral patches to start mining: an action α has a list of actions that are required before starting 74 (0 in ); α. For instance, to start the Air Weapons Upgrade level 2, it 4) time for a worker to switch from mineral to gas: 74 (0 in is required to have finished the Air Weapons Upgrade level 1. ); Notice that we can dive recursively into these dependency lists. 5) mineral gathering rate: 0.045 mineral per worker per frame Thus, if someone aims to do Air Weapons Upgrade level 2 for (like in ); Protoss, it requires Air Weapons Upgrade level 1, which requires 6) gas gathering rate: 0.077 gas per worker per frame (0.07 itself a Cybernetics Core, which requires a Gateway. in ). RICHOUX et al.: GHOST: A COMBINATORIAL OPTIMIZATION FRAMEWORK FOR REAL-TIME PROBLEMS 385 TABLE VI OUR SIMULATOR EXECUTION MATCHED AGAINST THE PRO-GAMER BISU DURING THE FIRST 1900 FRAMES (I.E., 80 S) Simulator in GHOST Bisu Action Frames Mineral Supply (Used/Capacity) Mineral Supply (Used/Capacity) Simulator starts a probe 298 40.8 5/9 40 5/9 Simulator starts a probe 656 19.7 7/9 20 7/9 Simulator starts a probe 955 46.5 8/9 50 8/9 Simulator starts a pylon 1119 – – – – Bisu starts a pylon 1164 – – – – Simulator starts a probe 1328 1.2 9/9 12 9/9 Simulator starts a probe 1627 60.0 10/17 132 9/17 Bisu starts a gateway 1731 – – – – Simulator starts a gateway 1866 – – – – Simulator starts a probe 1866 1.8 11/17 78 9/17 TABLE VII frames BOs (about 7 min) and 394 frames of gain considering AVERAGE MAKESPAN OF HUMANS AND GHOST BOS IN FRAMES OVER 3647 GAMES 7800 frames BOs (about 5 min), all match-ups taken together. We have also analyzed some replays played by top Ko- rean pro-gamers: Protoss players “Bisu,” “BeSt,” “Violet,” and Games till 10 000 frames “Cure”; Zerg players “Jaedong” and “sAviOr”; and Terran Match-up Humans GHOST %Solved Gain player “Flash.” We have only downloaded eight of them, giving All 9794 9250 94.4 544 us a set of eight BOs to give to GHOST. PvP 9727 9078 95.0 649 Results against these pro-gamers are shown at the very last PvT 9861 9378 93.9 483 line of Table VII. We can see that GHOST obtains better BOs PvZ 9692 9097 95.0 595 All pro 9605 8916 96.3 689 than Protoss Korean pro-gamers listed above, with a gain of 689 Games till 7800 frames frames for 10 000 frames BOs and 306 frames for 7800 frames BOs. We have to lower the first result by emphasizing that pro- Match-up Humans GHOST %Solved Gain gamers are often already engaged in a fight before 10 000 frames All 7726 7332 98.8 394 PvP 7630 7249 99.3 381 and/or they are applying outside-the-book strategies, and thus PvT 7800 7564 98.3 236 minimizing the BO makespan may not be their first priority PvZ 7626 6841 99.7 785 anymore. To a lesser extent, this is also true with 7800 frames All pro 7485 7179 100 306 BOs. Each calls of GHOST lasts for 30 ms. Computation time is only 20 ms for satisfaction runs and 30 ms for the (global) optimization run. This means that GHOST To be sure these parameters make our simulator realistic, we can compute a highly optimized BO within only one StarCraft matched its execution against the first 1900 frames of games frame at the fastest speed. In , Churchill and Buro’s branch (i.e., 80 s) played by Korean pro-gamers. Table VI gives an and bound method is computing 90% of the time BOs with the example of our simulator matched against the Protoss Korean same makespan as pro-gamers in about 3.735 s (for BOs with pro-gamer “Bisu.” Gas is not revealed since it remained 0 for a makespan up to 249 s, i.e., 5928 frames), giving thus a CPU both “Bisu” and the simulator during the first 1900 frames. Each time/makespan ratio of 1.5%. Considering GHOST is computing time the simulator started to produce a probe, i.e., a worker, we in average BOs with a makespan of 9250 frames within 30 ms. write down the simulator and “Bisu” mineral stock and supply In the fastest mode, 9250 frames corresponds to about 388 s; situation (used supply over supply capacity). One can see that leading to a CPU time/makespan ratio of 0.007%. these two early games are very similar, with a slight advantage Planning a BO is easier than a wall-in for GHOST because to the simulator since its probe production is nearly perfect. a BO plan can be modeled in CSP by a permutation problem, For Table VII,7 GHOST has been run ten times on each BO. which drastically decrease the combinatorial complexity of the We run experiments on two sets of BOs: those extracted from problem. Also, the satisfaction part for the target selection and replays by Gabriel Synnaeve and refined by Glen the BO problems are not difficult to compute, since constraints Robertson,8 and those extracted from top Korean pro-gamers. modeling these problems are trivial. This is not the case for In total, the first set is composed of 3647 BOs: 768 Protoss the wall-in problem, where even getting a nonoptimized valid versus Protoss, 2043 Protoss versus Terran, and 836 Protoss solution is hard. versus Zerg. Table VII shows that GHOST outperforms human BOs by far, with a mean of 544 frames of gain considering 10 000 C. Future Work 7 All As for all other problems, we could implement another ob- BO data, experiment results and the simulator can be found at https://github.com/richoux/GHOST_paper/tree/master/xp/build_order jective function for the BO problem. For instance, it would 8 http://scidrive.uoa.auckland.ac.nz/gameai/scdata/files.txt be natural to propose an objective function trying to first 386 IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 8, NO. 4, DECEMBER 2016 minimize the makespan of all army units asked by the user, local search-based algorithm listed on the MiniZinc software and then to minimize the makespan of remaining actions (build- web page.11 ings, research works, upgrades). This would allow the user to Rather than matching GHOST results with state-of-the-art first secure his base with an army. solvers on the three problems presented above, we chose to compare these algorithms on a resources allocation problem. VI. MATCHING STATE-OF-THE-ART CONSTRAINT SOLVERS The reason is simple: the target selection and BO problems re- quire a simulator to recreate the game environment, which is One of GHOST’s main goals is to provide a user-friendly and both complicated and time consuming for solvers we do not flexible interface to make the combinatorial problem model- know so well, even for a simple simulator like the one used for ing easier for nonspecialists, using GHOST’s inner solver as a target selection. The wall-in problem is actually quite complex blackbox to solve these models. A previous study has shown to model through MiniZinc, with a lot of data related to the GHOST to be both robust and flexible , robust in the sense model variables (size of buildings, pixel gap size on each side, that GHOST inner solver shows good behavior to solve prob- etc.). Performances depend a lot on the quality of the MiniZinc lems that it is not designed for, and flexible since proposing model, where a good use of global constraints is critical. We lack different models to the same problem only requires shallow the expertise in both MiniZinc and global constraints to provide modifications. an efficient model for the wall-in problem. A model that is not well-optimized would have been a great disadvantage for other A. State-of-the-Art Constraint Solvers solvers. The MiniZinc model we use for the resources alloca- In this section, we compare GHOST inner solver performances tion problem is a slight modification of the simple-prod- with the state-of-the-art constraint solvers, namely Opturion planning model provided by MiniZinc authors, therefore, we CPX9 and Gecode. We chose these two solvers for two are sure to have a well-optimized model for this problem. reasons: first, both are able to parse MiniZinc code, a common language to model COP. Therefore, we only need to model a B. Benchmark and Experiments problem once and give this model to different solvers to mea- sure their performances. Second, Opturion CPX and Gecode Our resources allocation problem is the same as studied are well-known state-of-the-art solvers, participation to the an- in : given an amount of minerals, gas, and supply, what nual MiniZinc Challenges. Gecode won all gold medals in units should we train to maximize the global damage per second all categories (fixed, free, and parallel) at the MiniZinc Chal- (DPS) on ground units. In other words, what is the list of units lenges from 2008 to 2012. Starting from 2013, MiniZinc Chal- you should train to maximize the sum of their ground DPS if we lenges are composed of four categories: fixed, free, parallel, give you fixed stocks of resources. This is actually an instance of and open.10 Opturion CPX won two gold medals (fixed and the multidimensional knapsack problem with three dimensions free categories) and two bronze medals (parallel and open (one per resource type). The regular knapsack problem is well categories) in 2013, the four silver medals in 2014 and two known to be NP-complete, and its multidimensional version is gold medals (fixed and free), one silver medal (parallel), and even harder: unlike the original knapsack problem, there is no one bronze medal (open) in 2015. Therefore, Gecode was the efficient polynomial-time approximation scheme starting from dominant constraint solver until 2012, and from 2013 Op- two dimensions (unless P = NP). turion CPX becomes and remains the current leading constraint To compare solvers on significant problem instances, we solver. chose to optimize ground DPS for Zerg, Protoss, and Terran However, these two solvers implement a complete algorithm, factions with 20 000 mineral units, 14 000 gas units, and 380 i.e., an algorithm that explores the whole search space to find supply units. Although these values are unrealistic within a (and prove) the optimal solution. GHOST inner solver imple- StarCraft game, they are large enough to challenge constraint ments a local search metaheuristics, i.e., an incomplete algo- solvers. Indeed, it is harder to match solvers if all of them return rithm. It is unable to prove the optimality of a solution, but in a solution within a couple of milliseconds. practice these algorithms are very efficient to quickly find an Results matching GHOST inner solver with Opturion CPX and optimal or near-optimal solution. To match GHOST inner solver Gecode are compiled in Table VIII.12 Since Opturion CPX and to other local search metaheuristics, we also run experiments Gecode implement complete, deterministic algorithms, running with Oscar/CBLS MinZinc interface. We chose this solver them once on each problem instance is sufficient. That means again for two reasons: first, it is one of the rare solver programs runs on the same input are identical regarding solution qual- that implements a metaheuristics able to parse MiniZinc code. ity and runtimes. For GHOST, we set the runtime to the lowest Other frameworks such as ORtools or EasyLocal++ can also time (empirically found) where more than 50% of solutions are parse MiniZinc code, but they are frameworks like GHOST, i.e., the optimal solution. We allow the Opturion CPX and Gecode they do not provide any executable, but a library to implement solvers 6 h to produce a solution for each problem instance. your own executable upon their solver. Second, Oscar/CBLS is a very recent solver (last release from late 2015), and the only 11 http://www.minizinc.org/software.html 12 All experiment results can be found at https://github.com/richoux/ 9 http://www.opturion.comwww.opturion.com GHOST_paper/tree/master/xp/other_solvers/resource and https://github.com/ 10 See http://www.minizinc.org/challenge.html for further details. richoux/GHOST_paper/tree/master/xp/resource RICHOUX et al.: GHOST: A COMBINATORIAL OPTIMIZATION FRAMEWORK FOR REAL-TIME PROBLEMS 387 TABLE VIII SOLVERS’ COMPARISON ON THE RESOURCES ALLOCATION PROBLEM Opturion CPX Gecode GHOST (100 runs) Oscar/CBLS (10 runs) Optimal DPS Runtime Runtime % Opt. found Mean DPS Runtime Mean DPS Best DPS Mean runtime Zerg 11400.00 200 ms 99580 ms 59 11387.70 80 ms 11400.00 11400.00 562 ms Protoss 4916.38 1620 ms – 54 4907.70 1300 ms 3445.21 4480.00 1200 ms Terran 6632.73 3 h 19 min – 53 6619.30 130 ms 3035.73 5767.55 1390 ms Results matching GHOST inner solver with Oscar/CBLS can Although the Protoss instance has a smaller search space than be found in Table VIII. Notice that, like GHOST, Oscar/CBLS the Zerg instance, all algorithms need more time to find a solu- implements a stochastic algorithm. As such, we must run the tion. This is because Zerg units’ properties make the Zergling same problem multiple times to compute a fair mean of the unit clearly more challenging to maximize the ground DPS, runtime and solution quality. Since Oscar/CBLS does not let having by far the best DPS/cost ratio among Zerg units. There- us define a runtime timeout, we manually stopped the execution fore, the strategy to maximize the Zerg ground DPS is trivial: after one minute and then we collected, for each run, the runtime just train as many Zerglings as resources allow. This is not the when it reached its highest DPS. This is the reason why we only case with the Protoss instance, where a composition of different have 10 Oscar/CBLS runs on each problem instance, against units (for our instance, a mix of Zealots and Dark Templars) is 100 runs for GHOST. required to reach the optimal solution. Notice that the GHOST inner solver is faster to find a solution for the Terran instance rather than the Protoss instance, because Terrans have also a triv- C. Results Analysis ial optimal strategy: just produce as many Firebats as resources allow. However, for complete solvers, the search space remains Table VIII clearly shows that the GHOST inner solver too large to explore in order to prove the solution’s optimality. outperforms the state-of-the-art constraint solvers Opturion Table VIII shows that the GHOST inner solver also outperforms CPX and Gecode on our resources allocation problem instances. the local search metaheuristics implemented in Oscar/CBLS. Gecode was only able to output a solution for the Zerg instance. Except for the Zerg instance, the best solution found by Os- For both Protoss and Terran instances, no solutions were found car/CBLS was very far from the optimal solution, and finds in after 6 h of computation. On the Zerg instance, Gecode found average poor-quality solutions usually within much longer time the optimal solution in 99.58 s, where GHOST found 59% of the than GHOST to find a near-optimal solution. It requires about time the optimal solution in 80 ms. In average, GHOST finds a 562 ms to Oscar/CBLS to find the optimal solution of the Zerg DPS of 11 387.7 where the optimal is 11 400. Thus, the average instance, while GHOST finds the optimal or a near-optimal solu- output quality from GHOST within 80 ms corresponds to 99.89% tion within 80 ms. the optimal solution quality. Opturion CPX finds the optimal For the Protoss instance, GHOST needs 1.3 s to find the op- solution in 200 ms, i.e., 2.5 times longer than GHOST needs to timal (DPS = 4916.38) or a near-optimal solution; in average, reach the optimal solution at least 50% of the time. Oscar/CBLS requires 1.2 s to find a solution with a mean DPS of On the Protoss instance, GHOST found 54% of the time the 3445.21, that is, 70.08% of the optimal solution quality (against optimal solution in 1.3 s with an average DPS of 4907.7 where 99.82% for GHOST). The best solution found by Oscar/CBLS the optimal is 4916.38, i.e., 99.82% the optimal solution quality. has a DPS of 4480 (91.12% the optimal) while GHOST reaches Opturion CPX found the optimal solution in 1.62 s, thus slightly the optimal solution in 54% of the time. more time than GHOST needs to reach the optimal solution at least Finally, for the Terran instance, GHOST computes the optimal 50% of the time. (DPS = 6632.73) or a near-optimal solution within 130 ms, The real difference between GHOST and Opturion CPX oc- while Oscar/CBLS takes 1.39 s in average to find a solution curs on the Terran instance. GHOST finds the optimal solution with a mean DPS of 3035.73. This represents 45.77% of the 53% of the time in 130 ms, with an average DPS of 6619.3 optimal solution quality, against 99.80% for GHOST. The best where the optimal is 6632.73, i.e., 99.80% the optimal solution solution found by Oscar/CBLS has a DPS of 5767.55 (86.96% quality. Opturion CPX finds the optimal solution in 3 h and the optimal) when GHOST outputs 53% of the time the optimal 19 min! solution. Runtimes obtained on these three instances can be explained We should also emphasize that Oscar/CBLS uses many cores as follow: in StarCraft, six different Zerg and Protoss units can to compute a solution,13 whereas GHOST inner solver remains se- hit ground units, against nine Terran units (without taking into quential. Besides this difference, results compiled in Table VIII account buildings such as Sunken Colony or Photon Cannon). show that GHOST outperforms Oscar/CBLS both in terms of This difference is sufficient to make the Terran instance search quality outputs and runtimes. space considerably wider than the other two (about 1.57 × 1020 configurations for the Terran instance against 1.55 × 1013 and 13 Experiments have been conducted on an Intel i7 quad-core CPU, with 4 GB 1.33 × 1012 , respectively, for the Zerg and Protoss instances). of memory, under Ubuntu 14.04 64-bit. 388 IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 8, NO. 4, DECEMBER 2016 VII. DISCUSSION AND CONCLUSION through formalisms like soft constraints or fuzzy constraints. However, up to our knowledge, none of these formalisms favor In this paper, we introduced GHOST, a combinatorial opti- mization framework to solve any (decidable) problems encoded the design of efficient solvers. Thus, far beyond the scope of this paper, we would like to investigate a new CSP formalism that by a constraint satisfaction/optimization problem. We presented could manage uncertainty efficiently. three different RTS problems belonging to a specific level of abstraction, and proposed a CSP/COP model for each. Exper- iments applying GHOST on these models shown very good re- REFERENCES sults computed within some tens of milliseconds, without any S. Ontañón et al., “A survey of real-time strategy game AI research and modification or optimization of the solver source code. Results competition in StarCraft,” IEEE Trans. Comput. Intell. AI Games, vol. 5, no. 4, pp. 293–311, Dec. 2013. obtained are often better than the ones we can find in the current G. Robertson and I. Watson, “A review of real-time strategy game AI,” literature. Artif. Intell. Mag., 2014. One claim written in Section II is now clear: looking for the D. Churchill and M. Buro, “Build order optimization in StarCraft,” in Proc. AAAI Conf. Artif. Intell. Interactive Digit. Entertainment, 2011, absolute optimal solution may not be the best strategy for RTS pp. 14–19. games; this is confirmed by complete algorithms runtimes from M. Kuchem, M. Preuss, and G. Rudolph, “Multi-objective assessment of Section VI. Fast metaheuristics can output an “optimal enough” pre-optimized build orders exemplified for StarCraft 2,” in Proc. IEEE Comput. Intell. Games, 2013, pp. 1–8. solution in some tens of milliseconds, and if no good enough R. Lara-Cabrera, C. Cotta, and A. J. Fernández-Leiva, “A self-adaptive solution has been found, the user can always rerun the solver on evolutionary approach to the evolution of aesthetic maps for a RTS the next frame. game,” presented at the IEEE World Congress Computational Intelligence, Beijing, China, 2014. Some improvements we have in mind concern the imple- G. Verfaillie and N. Jussien, “Constraint solving in uncertain and dy- mentation of a pause/resume system, that will allow GHOST to namic environments: A survey,” Constraints, vol. 10, no. 3, pp. 253–281, start a long computation and to hash it into small pieces fit- 2005. F. Richoux, A. Uriarte, and S. Ontañón, “Walling in strategy games via ting within one frame. GHOST architecture has been designed to constraint optimization,” in Proc. AAAI Conf. Artif. Intell. Interactive make such an implementation easy to do, in particular thanks to Digit. Entertainment, 2014, pp. 52–58. the decoupling satisfaction loop—optimization loop. Another P. Codognet and D. Diaz, “Yet another local search method for constraint solving,” in Stochastic Algorithms: Foundations and Applications. New improvement would be to let the solver check how many cores York, NY, USA: Springer-Verlag, 2001, pp. 73–90. are available in the machine running it, and use all of them to Y. Caniou, P. Codognet, F. Richoux, D. Diaz, and S. Abreu, “Large-scale speed up the search. This can also be done easily since Adaptive parallelism for constraint-based local search: The costas array case study,” Constraints, vol. 19, no. 4, pp. 1–27, 2014. Search is known to be very efficient with a straightforward paral- G. Synnaeve and P. Bessière, “A Bayesian model for RTS units control lel scheme (see Caniou et al. ). Indeed, this algorithm has been applied to StarCraft,” presented at the IEEE Conf. Computational Intelli- parallelized on a super-computer and it shows linear speed-ups gence Games, Seoul, South Korea, 2011. A. Uriarte and S. Ontañón, “Kiting in RTS games using influence over 8192 cores on some problems (and fairly good speed-ups maps,” in Proc. AAAI Conf. Artif. Intell. Interactive Digit. Entertainment, on others), which are impressive parallel performances. 2012, published online. GHOST has also been designed following the famous Object D. Churchill, A. Saffidine, and M. Buro, “Fast heuristic search for RTS game combat scenarios,” in Proc. AAAI Conf. Artif. Intell. Interactive Oriented Programming “open-close principle,” to let the door Digit. Entertainment, 2012, published online. open for extensions without the need to modify the already D. Churchill and M. Buro, “Incorporating search algorithms into RTS written classes. It is easy to implement and to include new prob- game agents,” presented at the AIIDE Workshop Artificial Intelligence Adversarial Real-Time Games, Stanford, CA, USA, 2012. lems in GHOST, and the authors highly encourage contributors to T. Furtak and M. Buro, “On the complexity of two-player attrition games propose implementations of new problems to integrate into the played on graphs,” presented at the 6th AAAI Conf. Artificial Intelligence library. We would like GHOST to be broadly used among both Interactive Digital Entertainment, Stanford, CA, USA, 2010. D. Churchill, “Sparcraft: Open source starcraft combat simulation,” 2013. amateur and professional RTS AI developers. A proprietary C# [Online]. Available: https://code.google.com/p/sparcraft/ version of GHOST has been transferred in favor of the game studio M. Čertický, “Implementing a wall-in building placement in star- Insane Unity14 for their MMORTS Win That War!15 currently in craft with declarative programming,” CoRR, vol. abs/1306.4460, 2013, http://arxiv.org/abs/1306.4460. alpha version. GHOST is used both for developing an adversary H.-C. Cho, K.-J. Kim, and S.-B. Cho, “Replay-based strategy prediction AI player, but also for making a taking-the-reins AI when the and build order adaptation for starcraft AI bots,” presented at the IEEE player is not connected, since this massively multiplayer online Conf. Computational Intelligence Games, Niagara Falls, ON, Canada, 2013. real-time strategy (MMORTS) is a persistent world. G. Synnaeve and P. Bessière, “A Bayesian model for opening prediction Finally, this paper leads us to take a global view on CSP/COP, in rts games with application to starcraft,” presented at the IEEE Conf. and to consider the following: even if a huge number of combi- Computational Intelligence Games, Seoul, South Korea, 2011. G. Synnaeve and P. Bessière, “A dataset for StarCraft AI & an example natorial optimization problems can be modeled with CSP/COP, of armies clustering,” presented at the AAAI Conf. Artificial Intelligence this framework is not well adapted to deal with uncertainty Interactive Digital Entertainment, Palo Alto, CA, USA, 2012. or incomplete information. This is penalizing for many RTS- J. Fradin and F. Richoux, “Robustness and flexibility of GHOST,” in Proc. AIIDE Workshop Artif. Intell. Adversarial Real-Time Games, 2015, related problems, where most interesting challenges come from pp. 9–14. the fact that information is incomplete. Some variations of con- C. Schulte and P. J. Stuckey, “Efficient constraint propagation engines,” straint programming propose to take into account uncertainty ACM Trans. Program. Languages Syst., vol. 31, no. 1, pp. 2:1–2:43, 2008. G. Björdal, J.-N. Monette, P. Flener, and J. Pearson, “A constraint-based local search backend for MiniZinc,” Constraints, vol. 20, no. 3, pp. 325– 14 http://www.insaneunity.comwww.insaneunity.com 345, 2015. A. Kulik and H. Shachnai, “There is no EPTAS for two-dimensional 15 http://www.winthatwar.com knapsack,” Inf. Process. Lett., vol. 110, no. 16, pp. 707–710, 2010.