AI Game Programming Wisdom 4
54 Articles, Edited by Steve Rabin, 2008.
Survey of Lowest Known Online Prices
$48.99 (30% off) Amazon.com (free shipping)
$69.99 (0% off) BarnesAndNoble.com
Section 1: General Wisdom
Abstract: This article examines the tension in game content production between the systematic reduction of specific cases to general rules on the one hand, and the deliberate construction of unique player experiences on the other. We shall see how market and design trends are pushing games towards hybrid styles that combine these two approaches, before accusing most work in game AI of remaining too closely tied to the reduction to general rules in its commitment to strongly autonomous game agents. A quick review of related themes in sociology and psychology sets us up for the last part of the article, exploring the notion of what we call a 'situationist' game AI, capable of meeting this hybrid challenge.
Abstract: Artificial personality is a powerful conceptual framework for creating compelling artificial intelligence in most type of games. It gives direction and focus to the underlying algorithms that make up all AI, encouraging a style of play which revolves around understanding and exploiting personality archetypes such as the coward, the defender, the psycho, etc. This technique was used successfully in Bicycle?Texas Hold'em from Carbonated Games in 2006, published by MSN Games.
Artificial Personality: A Personal Approach to AI
Abstract: This article describes tips and techniques for working with designers to create better AI systems and improve their utilization in-game. It covers the advantages and disadvantages of various methods for allowing designers control over AI systems, guidelines for how much to expose in scripting systems, how to organize tunable data for data driven systems, and pitfalls to avoid in implementing such systems. It also discusses how to consider designer workflow in system design and communication tips to make sure designers understand how to use these systems.
Creating Designer Tunable AI
Abstract: AI is an effective tool for analyzing gameplay. This article uses case studies of two popular casual games, Minesweeper and Sudoku, to show how small amounts of AI can illuminate what core gameplay actually is. This can be most easily applied to casual games. Writing such AI leads to new gameplay concepts. A potential two-player Minesweeper from that case study is shown. Demonstration software for both games is included.
AI as a Gameplay Analysis Tool
Abstract: This article considers the ways in which entrenched methods of game design can lead to unproductive tensions with advances in game AI technology. This issue encompasses not only methods of thinking about game design, but also styles of design documentation, and working relationships between designers and AI coders when iterating on game features. The result is not only a failure to produce useful increases in gameplay complexity. In some cases the result is actually a reduction in complexity, due to the inability of outdated design approaches to effectively control a more complex AI architecture.
Ecological Balance in AI Design
Section 2: Movement and Pathfinding
Abstract: This article describes all the techniques used to produce the squad formation movement in Company of Heroes. The squads controlled with this system have very tactical and visually interesting motion that handles obstacles and destructible environments with minimal impact on performance. A variety of techniques are described that, when used together, produce high quality squad motion.
Company of Heroes Squad Formations Explained
Abstract: This article explores the complex relationship between the forms of spatial representation employed by game agents and the forms of behavior that are easily supported by them. We shall see how most game agents typically reduce space to little more than a list of individual entities with objective spatial features existing in a task-neutral navigational representation of the global environment, and we will see how this is likely to severely limit their behavioral sophistication. This observation leads us into an extended discussion of the much richer notions of place found in the philosophical literature, before returning to practical themes with a review of place-based models in game AI. We will discuss affordance theory, smart object models, terrain analysis, influence mapping and informed environments, relating these specific approaches back to the general philosophical notions of place identified in the middle section of the article.
Turning Spaces into Places
Abstract: Many 3D games rely on some sort of navigation mesh for pathfinding. However, most methods of NavMesh generation are not suitable for run-time updates for reflecting a dynamic environment. This article proposes a novel use of line-clipping to create a system that can be dynamically updated in real time.
Dynamically Updating a Navigation Mesh via Efficient Polygon Subdivision
Abstract: This article describes a method to generate high-fidelity paths over very large terrains. The key to this approach is the Restricted Quadtree Triangulation (RQT), which provides the minimal representation of a height map given a world-space error metric. RQT is well suited to navigation meshes because it represents low-frequency terrain (flat plains, for example), with the fewest needed vertices while preserving detail in high-frequency regions. At runtime, path generation determines a preliminary course over a high-tolerance representation of the entire terrain, then refines the initial path in subsequent frames by paging low-tolerance navigation meshes for terrain chunks in the order they occur along the path. Crucial details-a narrow valley through an otherwise impassable mountain range, for example-are omitted by naive simplifications but preserved by RQT. This approach is less complex than various schemes to stitch streaming data, avoids backtracking during path refinement, and works transparently alongside other navigation mesh simplifications described in previous volumes of this series.
Intrinsic Detail in Navigation Mesh Generation
Abstract: Automatic generation of navigation meshes can increase the speed and quality of level content creation. This article presents a new empirical approach to mesh generation that relies on directly sampling the world geometry for navigability data. The algorithm is well suited to a wide range of detailed environments and results in a relatively uniform triangle mesh ideal for pathfinding use. Implementation approaches, optimizations, and extensions are also discussed.
Navigation Mesh Generation: An Empirical Approach
Abstract: Game designers are introducing more and more dynamic changes into worlds that have previously been largely entirely static. This makes for a compelling playing experience, but can be a major headache for AI programmers. If the physical world can change at any moment, how can the AI of the NPCs keep up? This paper addresses this challenge with an innovative technique for updating the key AI data structure (the navigation graph) in real-time. The technique starts with the game's raw geometry ("polygon soup") and processes this on the CPU (or even GPU!), generating or updating the navigation graph automatically.
Navigation Graph Generation in Highly Dynamic Worlds
Abstract: Pathfinding for games is a multidimensional problem. The industry is making increasing demands for solutions that are fast, use minimal pre-computation and memory, work for large and complex environments and objects of multiple sizes, etc. This article presents two search algorithms - TA* (Triangulation A*) and TRA* (Triangulation Reduction A*) - which successfully address these requirements. TA* finds paths on a Constrained Delaunay Triangulation environment representation, while TRA* works on a reduced graph calculated from this triangulation.
Fast Pathfinding Based on Triangulation Abstractions
Abstract: This article presents an automated way to create a compact and efficient navigable space mesh for an arbitrary static 3d game environment. It has been used in several commercial products and proven to provide an excellent knowledge base, allowing AI bots to navigate extremely complex 3d worlds even over vast distances.
Automatic Path Node Generation for Arbitrary 3D Environments
Abstract: This article describes a pathfinding algorithm that allows the use of Influence Maps (IM) to mark hostile and friendly regions. The algorithm allows us to find the optimal path from point A to point B very quickly while taking into consideration the different threat and safety regions in the environment. This allows units to balance the risk while traversing their path, thus allowing for more depth of gameplay.
Risk-Adverse Pathfinding Using Influence Maps
Abstract: The article discusses the subject of pathfinding in dynamic environments. It features tried and tested techniques for handling the addition, removal and most importantly modification of objects during the game. It covers how both nodes and edges can be used to store valuable information that speed up searches as well as information that is used in the actual searches. As pathfinding graphs become larger and more detailed, it is useful to catch unnecessary searches can before the actual call to the pathfinder is made. It is described how this can be done as well as how to verify existing paths.
Practical Pathfinding in Dynamic Environments
Abstract: This article describes a system to achieve high quality vehicle motion for units that move primarily by sliding along a predefined path. The system refines the paths generated by a standard smoothed A* into routes that obey the limited turning capabilities of units. A palette of possible turns to use for each corner in the original path is defined and a search technique to quickly determine the optimal turn for each corner is described. A way to avoid speed discontinuities when changing paths is also specified.
Postprocessing for High-Quality Turns
Abstract: Several different types of hierarchical pathfinding abstractions have been proposed in game-development literature, and many more are likely being used in published games. This article describes a pathfinding abstraction that is specifically designed to minimize the memory overhead of the abstraction. In addition to describing the abstraction itself, we also describe in detail how the abstraction can be used for pathfinding, including many small optimizations that are important for practical use. We measure the performance experimentally, showing a 100-fold improvement over the worst-case performance of A*.
Memory-Efficient Pathfinding Abstractions
Section 3: Architecture
Abstract: This article describes an architecture that is well suited for production or prototyping of a wide variety of games. The goal of the article is to give the reader a solid understanding of the factors to consider when designing a flexible AI architecture and focuses on the concepts and critical components necessary to successfully design an AI system that is easy to understand, build, maintain and extend. The article covers, in detail, the concepts of the architecture, decision making process, decision weighting, decision chaining, agent coordination and cooperation, as well as handling special cases.
A Flexible AI Architecture for Production and Prototyping of Games
Abstract: The vast majority of computer games developed today use either scripting or FSMs for their high-level AI architecture. While these are both powerful techniques, they are what one might think of as "procedural AI," which leaves the bulk of the decision-making in the hands of the developer. Goal-based AI is an alternative architecture that has been used in a number of successful games across multiple genres. In contrast to the techniques listed above, one might think of it as "declarative AI." Rather than telling the AI what to do, the role of the developer is to tell the AI what factors to consider when selecting an action and how to weigh them. Using this information, the AI will examine the current situation and select its actions accordingly. This paper briefly discusses the most common procedural AI architectures, followed by one popular declarative alternative, goal-based AI. Finally, we will discuss hybrid approaches where we can capture some of the best of both worlds.
Embracing Declarative AI with a Goal-Based Approach
Abstract: This paper elaborates on a previously eluded to AI design paradigm, nicknamed MARPO, that continues to produce flexible and manageable AI from first principles. It applies the rationales behind these principles to create a goal-based, hierarchical state machine that embraces the beauty of rule-based reasoning systems. Grounded in industry experience, it avoids the common pitfalls of this approach, and shows how MARPO discipline maximizes efficiency, flexibility, manageability and successfulness of the end result.
The MARPO Methodology: Planning and Orders
Abstract: A robust decision-making and control system is the best place to start with any AI engine. The behavior tree described in this article covers the major elements: implementing low-level tasks with latent execution, building a framework for managing them concurrently, assembling them in hierarchies using standard composites, and designing the system for depth-first search.
Getting Started with Decision Making and Control Systems
Abstract: In the modern role-playing game (RPG) development environment, designing and implementing a behavior system that meets the diverse needs of designers and programmers can be a challenge. The article will first identify the requirements of a desirable behavior decision system from the points of view of designers and programmers. It will then introduce a knowledge-based approach stemming from the decision tree and finite-state machine methods, which meets the requirements of a desirable decision making system. Through an actual AI example where the three methods are applied, the article will illustrate their strengths and weaknesses, hence demonstrating the value of the knowledge-based approach.
Knowledge-Based Behavior System: A Decision Tree/Finite State Machine Hybrid
Abstract: In this article we discuss an "Emotion Component" that can be used to model complex emotions, allowing you to implement more human-like behavior in game characters. The Emotion Component is set to function either as a separate unit or in conjunction with other AI processes. With this component the emotions in a game character influence its behavior and color its perception of the world. Game characters using the Emotion Component internally keep track of ("feel") a condition ("emotional state") that influences their behavior and reactions in such a way that the human player is persuaded that the character is experiencing emotions such as fear, anger, admiration, love, and greed.
The Emotion Component: Giving Characters Emotions
Abstract: The perception system described in this article presents a way to simplify AI logic and expand the capabilities of NPCs by providing prioritized information about the environment as well as tactical data. The system has been designed to enable time slicing, priority scanning, goal negotiation, short- and long-term memory, and simulation of reflex times, among other features. This system can also be scaled to reduce the performance impact of a high number of agents interacting in the world and to incorporate new complex objects with attached goals and scripts, which make it very suitable for implementing complex character behaviors in current and next-generation games.
Generic Perception System
Abstract: This article covers techniques for distributing agent processing in peer-to-peer (P2P) games. It discusses mechanisms to distribute processing to address both functional concerns (such as for streaming games) and performance concerns (distributing processing load). It also considers efficient communication mechanisms for agents running on separate machines to coordinate behavior and serialization of AI state for transferring ownership between peers.
Peer-To-Peer Distributed Agent Processing
Abstract: The proliferation of consoles with multiple cores means that games must now be threaded to run on these architectures. This changes the overall architecture for a game, but how can AI best be threaded? Options range from splitting the AI into individuals that run on different processing units to the more traditional planning system that has been functionally decomposed. Hybrid approaches such as a blackboard system are also possible and must be considered within the framework of a whole game system.
AI Architectures for Multiprocessor Machines
Abstract: Finite state machines have become the norm for game intelligence, be it to control the behavior of a non-player character or to formalize the game's rules. However, in practice they have a number of shortcomings that lead, for instance, to an explosion in the number of states or transitions. To solve many such issues, one can generalize finite state machines to statecharts, a notion introduced by David Harel in 1987. This chapter describes how statecharts overcome many of the limits of finite state machines, for instance by supporting nested states, parallel states, and continuous activities. The chapter focuses on the practical issues of building a statechart interpreter and integrating it with existing code. Two reference implementations are provided: first, a lean version in C++, ready to be added to your own game code; and second, a full-fledged demonstration in C# including a graphical statechart editor and debugger with automatic layout.
Level Up for Finite State Machines: An Interpreter for Statecharts
Abstract: This chapter describes the workflow and data structures used for scripting behaviors in the Abstract State Machine (ASM) framework. ASMs are introduced in the context of a behavior system for game agents. The focus of the paper is on how object-oriented extensions to ASM, Command Port integration of the Behavior Editor with Autodesk Maya, and a dual XML file format contribute to the usability of the behavior editor. The chapter also describes how offline manipulation of ASM definitions enabled the addition of parameters and referencing for behaviors without modifying the run-time code of the AI system.
Building a Behavior Editor for Abstract State Machines
Abstract: The Multi-axial Dynamic Threshold Fuzzy Decision Algorithm (MADTFDA) allows the designer to combine two or more constantly changing values and then compare the result to a defined numerical threshold in order to make a decision. MADTFDA is designed as a more flexible replacement for the "weighted sum" approach to combining factors. The additional flexibility is a valuable tool, allowing the designer to easily visualize the interactions of the decision inputs and enabling the programmer to create quick, robust, parameterized decision calls that accurately reflect the needs of the designer. The article covers the concept behind MADTFDA, its various uses as an AI design tool, and the use of the code that is included on the CD-ROM.
Multi-Axial Dynamic Threshold Fuzzy Decision Algorithm
Section 4: Tactics and Planning
Abstract: In an RTS game, terrain data can be precomputed and used at runtime to help the AI in its decision making. This article introduces a terrain analysis technique based on simple image processing operations which, combined with pathfinding data, produces precise information about relevant areas of the map.
RTS Terrain Analysis: An Image-Processing Approach
Abstract: As game AI complexity increases, imperative techniques such as Finite State Machines become unmanageable, inflexible, and problematical for code maintenance. Planning architectures tackle with this complexity introducing a new decision making paradigm. This article describes a new hierarchical planning technique based on STRIPS, GOAP, and HTN. It features a motivational approach together with the capability to handle parallel goal planning which favors the appearance of emergent behaviors. Advanced characteristics include, among others, partial replanning or mixing of planning and execution with the use of parameters at planning time to represent the current world state. The architecture, used in the strategy game War Leaders: Clash of Nations, allows high levels of code reusability and modularity, being easily adaptable to game design changes that commonly arise during a complete game development.
An Advanced Motivation-Driven Planning Architecture
Abstract: Goal-based AI agent architectures are a popular choice in character-driven games because of the apparent intelligence the agents display in deciding how to pursue their goals. These games often also demand coordinated behavior between the members of a group, which introduces some complexity in resolving the autonomous behavior of the individuals with the goal of the collective. This article introduces a technique for integrating military-style command hierarchies with the Goal-Oriented Action Planning (GOAP) architecture. An UnrealScript-based example of the framework is used to illustrate the concepts in practice for a squad-based first-person shooter (FPS), and practical optimizations are suggested to help the technique scale to the larger numbers of units required for real-time strategy (RTS) games.
Command Hierarchies Using Goal-Oriented Action Planning
Abstract: An efficient, easy-to-implement planner is presented based on the principles of logic programming. The planner relies on familiar IF/THEN structures and constructs plans efficiently, but it is not as expressive as other proposed planners. Many easy extensions to the planner are discussed such as inserting and removing rules dynamically, supporting continuous values, adding negations, and finding the shortest plan. Accompanying source code provides easy-to-follow implementations of the planner and the proposed extensions.
Practical Logic-Based Planning
Abstract: Sophisticated cognitive processes such as planning, learning, and opponent modeling are still the exception in modern video game AI systems. However, with the advent of multi-core computer architectures and more available memory, using more computing intensive techniques will become possible. In this paper we present the adversarial real-time planning algorithm RTSplan which is based on rapid game simulations. Starting with a set of scripted strategies RTSplan simulates determines the outcome of playing strategy pairs and uses the obtained result matrix to assign probabilities to strategies to be followed next. RTSplan is constantly replanning and therefore able to adjust to changes promptly. With an opponent modeling extension, RTSplan is able to soundly defeat individual strategies in our army deployment application. In addition, RTSplan can make use of existing AI scripts to create more challenging AI systems. Therefore it is well-suited for video games.
Simulation-Based Planning in RTS Games
Abstract: Tracking the possible location of an opponent is a potentially important game AI capability for enabling intelligent hiding from or searching for the opponent. This article provides an introduction to particle filters for this purpose. Particle filters postulate a set of specific coordinates where the opponent might be as opposed to estimating probabilities that the opponent is in particular regions of the level, as is done in the occupancy map technique. By their very nature, particle filters have a very different performance profile from occupancy maps, and thus represent an interesting alternative. We also show how adding a small amount of intelligence to the particles, transforming them to simulacra, can improve the quality of tracking.
Particle Filters and Simulacra for More Realistic Opponent Tracking
Abstract: This article provides the reader with an understanding of the fundamentals of Bayesian networks. The article will work through several examples, which show how a Bayesian network can be created to model a problem description that could be part of a video game. By the end of the article the reader will have the knowledge necessary to form and solve similar problems on their own. An implementation of our solution to the examples, which shows how beliefs are updated based on different observations, is provided on the accompanying CD-ROM.
Abstract: Before every battle comes the question - can I win this battle? Should I attack or should I run? There are a variety of ways to answer this question. This article compares several, from simple power calculations through Monte Carlo simulations, discussing the pros and cons of each and the situations where each is appropriate.
Using Bayesian Networks to Reason About Uncertainty
Section 5: Genre Specific
Abstract: An RTS game may have dozens or hundreds of individual units. This presents some interesting challenges for the AI system. One approach to managing this complexity is to make decisions on different abstraction levels. The AI for the RTS part of the game War Leaders: Clash of Nations is divided in three levels. This article is focused on the architecture developed for the lower two of these three levels, which correspond to the AI levels for units, groups, and formations. This architecture is based on the concept of a goal stack as a mechanism to drive the entire agent behavior together with orders, events, and behaviors.
A Goal Stack-Based Architecture for RTS AI
Abstract: This article extends "Autonomous Camera Control with Constraint Satisfaction Methods" written by Bourne and Sattar and published in AI Game Programming Wisdom 3. It proposes a solution to several problems we encountered during the development of a 3D platform game. One important problem we faced was the shaking of the camera position. We have studied the problem and extracted a set of mathematical conditions to ensure stability. A special set of mathematical conditions are applied to both visibility and collision constraints. The original system allows the camera to move in the entire world. Our project needed a scripted path, thus we proposed a solution to apply the constraint-based camera to limited space such as planes and splines. Speed limiting and using the solver for orientation is explored as future work.
A Versatile Constraint-Based Camera System
Abstract: With a little bit of cleverness, the GPU can be coerced into performing non-graphics related operations for you with great results. Visibility determination is one of the few components of AI that can take advantage of the massively parallel nature of new GPU hardware. Although rendering a 3D scene onto a 1D line loses a lot of information that rendering to a 2D plane may not miss, the complexity of searching a 2D texture for targets is many times larger. This technique is also simple enough such that smaller, 2D sprite based games might take advantage of it for some new gameplay ideas using searchlights, security guards, or dynamic levels used by the player to stay out of sight.
Seeing in 1D: Projecting the World onto a Line
Abstract: How quickly should an AI aim its weapon at the player? Not knowing the proper answer, developers often make up a number and hope for the best, which can often lead to complaints that the AI has unrealistic response times. Psychologists have studied human reaction time for decades. In this article, we discuss Fitts' Law, which uses the size of a target and its distance from the cursor to predict an agent's response time.
Reaction Time with Fitts?Law
Abstract: With the ever increasing physical and graphical fidelity in games, players are beginning to demand similar increases in the performance of unit AI. Unfortunately, unit AI is still most often based on simple finite state machines (FSMs) or, occasionally, rule-based systems. While these methods allow for relatively easy development and behavioral tuning, their structure imposes inherent limitations on the versatility of the units they control. In this article we propose an alternate methodology which allows units to effectively pursue multiple simultaneous goals. While our method isn't a panacea by any means, it has the potential to lead to far more flexible, "realistic" unit AI.
Enabling Actions of Opportunity with a Light-Weight Subsumption Architecture
Abstract: This article presents ideas to provide NPCs with more humanlike qualities and a greater sense of individuality in order to create more immersive game-playing experiences that capture and hold the attention and interest of players. We discuss how providing NPCs with personality, emotions, human sensing and memory can enable them to behave in a more humanlike fashion and make NPCs more distinctive. In addition, we discuss the impact that physiological stressors might have on NPCs' behavior and the different weapon handling skills of NPCs, and how these factors can contribute to making the NPCs of FTPS games more individual and humanlike.
Toward More Humanlike NPCs for First-/Third-Person Shooter Games
Abstract: Computer role-playing games often contain a complex main story-line and a series of smaller optional independent mini-stories called side-quests. Side-quests create an open world feeling, provide rewards and experience to the player for exploring optional game content, and build upon the background of the main story without affecting it. The more side-quests you add to your game, the richer the game experience will be for the player. However, more side-quests means more work generating content. This article discusses a Side-QUEst GENerator (SQUEGE) tool that will minimize the amount of time and effort needed to add side-quests to a game story. By using the patterns that exist in stories, SQUEGE intelligently provides an interesting and meaningful structure to the side-quests it produces. The result is a set of automatically generated side-quest outlines. The outlines can then be adapted, giving the game author authorial control over the side-quests generated. Finally, a programmer can use the adapted outlines to create the necessary game scripts in a straightforward manner. This process makes the creation of a large number of side-quests both easy and efficient, saving precious time and resources. The generator is easily extendable to allow for the addition of new patterns.
Stop Getting Side-Tracked by Side-Quests
Section 6: Scripting and Dialogue
Abstract: This article provides an overview of modern dialog systems. We start by presenting the issues of voice recognition, language processing, dialog management, language generation and speech synthesis. Next, we analyze two robust speech-based interactive systems, NICE and TRIPS, examining how they solved each of the issues involved in spoken dialog processing. Finally, we examine the particulars of the game domain and provide suggestions on how to approach it, with illustrations from the case studies.
Abstract: In this article we introduce a mathematical model of conflict that enhances Richardson's model of Arms Race accounting for interactive scenarios, such as the ones provided by Computer Role Playing Games. Accordingly, an HCP (Hybrid Control Process) is devised that can be combined with fuzzy rules to provide help in modeling non-linear interactive stories. The model presented here can be adopted by game AI programmers to better support the game designers' job, and to provide an interesting and unconventional type of gameplay to players. We also introduce the multi-disciplinary project Two Familes: A Tale of New Florence, which will illustrate the applications of our model.
Implementing Story-Driven Games with the Aid of Dynamical Policy Models
Abstract: This article introduces a method for largely automating NPC changes in attitude due to a player action. The method resolves the conflicting loyalties of the NPC's to produce a single number per NPC that can be used to update the NPC's feelings toward the player and drive future player-NPC interactions. The mechanics of the method are based on a constrained linear system, so it is computationally efficient, requiring only a single matrix multiplication in many applications.
Individualized NPC Attitudes with Social Networks
Abstract: Using script to empower designers with the ability to create advanced AI allows for more natural and specialized AI behaviors. This article discusses the best practices for achieving this using GameMonkey Script and gives an example of its usage in Battlestar Galactica for Xbox Live Arcade.
Abstract: This article presents the main techniques and paradigms of dialog management, with references to games, industrial applications and academic research. We cover dialog managers based on stacks, finite-state machines, frames, inference-engines and planners. For each technique, we point its strengths, applicability and issues when integrating into a broader dialog system in a game setting.
Scripting Your Way to Advanced AI
Section 7: Learning and Adaptation
Abstract: This article presents the use of an online reinforcement learning algorithm, called RETALIATE, to automatically acquire team AI in FPS domination-style games. We present the learning problem and state model from which we draw some lessons for designing AI in these game genres.
Learning Winning Policies in Team-Based First-Person Shooter Games
Abstract: Artificial intelligence behaviors in games are typically implemented using static, hand-authored scripts. Hand-authoring results in two issues. First, it leads to excessive authorial burden where the author has to craft behaviors for all the possible circumstances that might occur in the game world. Second, it results in games that are brittle to changing world dynamics. In this paper, we present our work to address these two issues by presenting techniques that a) reduce the burden of writing behaviors, and b) increase the adaptivity of those behaviors. We describe a behavior learning system that can learn behavior from human demonstrations and also automatically adapt behaviors when they are not achieving their intended purpose.
Adaptive Computer Games: Easing the Authorial Burden
Abstract: As computer graphics becomes less of a differentiator in the video game market, many developers are turning to AI and storytelling to ensure that their title stands out from the rest. To date, these have been approached as separate, incompatible tasks; AI engineers feel shackled by the constraints imposed by a story, and the story's authors fear the day that an AI character grabs their leading actor and throws him off a bridge. In this article, we attempt to set aside these differences, bringing AI engineers together with authors through a key intermediary: a player model. Following an overview of the present state of storytelling in commercial games, we present PaSSAGE (Player-Specific Stories via Automatically Generated Events), a storytelling AI that both learns and uses a player model to dynamically adapt a game's story. By combining the knowledge and expertise of authors with a learned player model, PaSSAGE automatically creates engaging and personalized stories that are adapted to appeal to each individual player.
Player Modeling for Interactive Storytelling: A Practical Approach
Abstract: Modern video games present complex environments in which their AI is expected to behave realistically, or in a "human-like" manner. One feature of human behavior is the ability to assess the desirability of the current strategic situation. This type of assessment can be modeled in game AI using a "score function." Due to the complex nature of modern strategy games, the determination of a good score function can be difficult. This difficulty arises in particular from the fact that score functions usually operate in an imperfect information environment. In this article, we show that machine learning techniques can produce a score function that gives good results despite this lack of information.
Automatically Generating Score Functions for Strategy Games
Abstract: Machine learning techniques can support AI developers in designing, tuning, and debugging tactics and strategies. In this article, we discuss how a genetic algorithm can be used to automatically discover strong strategies. We concentrate on the representation of a strategy in the form of a chromosome, the design of genetic operators to manipulate such chromosomes, the design of a fitness function, and discuss the evolutionary process itself. The techniques and their results are demonstrated in the game of Wargus.
Automatic Generation of Strategies
Abstract: Reinforcement learning (RL) is well suited to FPS bots as it is able to learn short term reactivity as well as long term planning. This article briefly introduces the basics of RL and then describes a popular RL algorithm called Sarsa. It shows how RL can be used to allow FPS bots to learn some of the behaviors that are required to play deathmatch games and presents the results of several experiments.
A Practical Guide to Reinforcement Learning in First-Person Shooters