Online strategy video games offer several unique challenges to the field of AI research. Due to their large state and action spaces, existing search algorithms have difficulties in making strategically strong decisions. Additionally, the nature of competitive on-line video games adds the requirement that game designers be able to tweak game properties regularly when strategic imbalances are found. This means that an AI system for a game like this needs to be robust to such changes and less reliant on expert knowledge. This paper makes two main contributions to advancing the state of the art for AI in modern strategy video games which have large state and action spaces.

Real-Time Strategy (RTS) games have shown to be very resilient to standard adversarial tree search techniques. Recently, a few approaches to tackle their complexity have emerged that use game state or move abstractions, or both. Unfortunately, the supporting experiments were either limited to simpler RTS environments (uRTS, SparCraft) or lack testing against state-of-the-art game playing agents. Here, we propose Puppet Search, a new adversarial search framework based on scripts that can expose choice points to a look-ahead search procedure. Selecting a combination of a script and decisions for its choice points represents a move to be applied next. Such moves can be executed in the actual game, thus letting the script play, or in an abstract representation of the game state which can be used by an adversarial tree search algorithm. Puppet Search returns a principal variation of scripts and choices to be executed by the agent for a given time span. We implemented the algorithm in a complete StarCraft bot. Experiments show that it matches or outperforms all of the individual scripts that it uses when playing against state-of-the-art bots from the 2014 AIIDE StarCraft competition.

Real-time heuristic search is suitable for time-sensitive pathfinding and planning tasks when an AI-controlled non-playable character must interleave its planning and plan execution. Since its inception in the early 90s, numerous real-time heuristic search algorithms have been proposed. Many of the algorithms also have control parameters leaving a practitioner with a bewildering array of choices. Recent work treated the task of algorithm and parameter selection as a search problem in itself. Such automatically found algorithms outperformed previously known manually designed algorithms on the standard video-game pathfinding benchmarks. In this paper we follow up by selecting an algorithm and parameters automatically per map. Our sampling-based approach is efficient on the standard video-game pathfinding benchmarks. We also apply the approach to per-problem algorithm selection and while it is effective there as well, it is not practical. We offer suggestions on making it so.

The ability to distract opponents is a key mechanic in many stealth games. Existing search-based approaches to stealth analysis, however, focus entirely on solving the non-detection problem, for which they rely on static, ahead-of-time models of guard movements that do not depend on player interaction. In this work we extend and optimize an approach based on heuristic search of stealth games to model variation in guard paths as dynamically triggered by player actions. Our design is expressive, accommodating different distraction designs, including remote activation and time delays. Using a Unity3D implementation, we show our enhanced search can solve distraction puzzles found in real games, as well as more complex, multiple-distraction level designs. Our work shows how heuristic search can be applied to dynamically determined contexts, and significantly extends the ability to model and solve stealth games.

Portfolio Online Evolution is a novel method for playing real-time strategy games through evolutionary search in the space of assignments of scripts to individual game units. This method builds on and recombines two recently devised methods for playing multi-action games: (1) Portfolio Greedy Search, which searches in the space of heuristics assigned to units rather than in the space of actions, and (2) Online Evolution, which uses evolution rather than tree search to effectively play games where multiple actions per turn lead to enormous branching factors. The combination of both ideas lead to the use of evolution to search the space of which script/heuristic is assigned to which unit. In this paper, we introduce the ideas of Portfolio Online Evolution and apply it to StarCraft micro, or individual battles. It is shown to outperform all other tested methods in battles of moderate to large size.

Applying game-tree search techniques to RTS games poses a significant challenge, given the large branching factors involved. This paper studies an approach to incorporate knowledge learned offline from game replays to guide the search process. Specifically, we propose to learn Naive Bayesian models predicting the probability of action execution in different game states, and use them to inform the search process of Monte Carlo Tree Search. We evaluate the effect of incorporating these models into several Multiarmed Bandit policies for MCTS in the context of StarCraft, showing a significant improvement in gameplay performance.

In this paper we introduce a computational model based on the concept of symmetry to generate visually pleasing maps of platform games. We cast the problem of generating symmetrical maps as an optimization task and propose a heuristic search algorithm to solve it. A user study using a platform game shows the advantage of our method over other approaches in terms of visual aesthetics and enjoyment. Another user study shows that our method is able to generate maps as visually pleasing as maps created by professional designers.

Novelty pruning is a simple enhancement that can be added to most planners. A node is removed unless it is possible to find a set of n literals which are true in the current state and have never all been true in any of that plan's previous states. Expanding on the success of the Iterated Width algorithm in classical planning and general game playing, we apply this technique to narrative planning. Using a suite of 8 benchmark narrative planning problems, we demonstrate that novelty pruning can be used with breadth-first search to solve smaller problems optimally and combined with heuristic search to solve larger problems faster. We also demonstrate that when many solutions to the same problem are generated, novelty pruning can produce a wider variety of solutions in some domains.

State of the art methods for generating non-player character (NPC) tactical behaviors typically depend on hard-coding actions or minimizing a given objective function. In many games however, it is hard to foresee how the NPC should behave to appear intelligent or to accommodate human player preferences for NPC tactics. In this paper we consider an alternative approach, by training NPC tactical behavior via demonstrations. We propose a heuristic search-based planning method based on previously-developed Experience Graphs, which facilitates the use of behavior demonstration data to plan goal-oriented NPC behavior. Our method provides a principled solution to the problem which tolerates some amount of differences in between the training demonstration and the actual problem and yet still grants guarantees on the quality of the solution output.

We extend the Expressionist project, and thereby the re-emerging area of grammar-based text generation, by applying a technique from software verification to a critical search problem related to content generation from grammars. In Expressionist, authors attach tags (corresponding to pertinent meanings) to nonterminal symbols in a context-free grammar, which enables the targeted generation of content that expresses requested meanings (i.e., has the requested tags). While previous work has demonstrated methods for requesting content with a single required tag, requests for multiple tags yields a search task over domains that may realistically span quintillions or more elements. In this paper, we reduce Expressionist grammars to symbolic visibly pushdown automata, which allows us to locate in massive search spaces generable outputs that satisfy moderately complex criteria related to tags. While the satisficing of more complex tag criteria is still not feasible using this technique, we forecast a number of opportunities for future directions.