August 4, 2004

AAAI Game AI Workshop Trip Report

by Michael Mateas · , 2:46 pm

As promised, here’s (finally) my trip report for the AAAI Workshop on Challenges in Game AI. The report is really a bunch of notes I took about the various talks, lightly edited to make them more readable. I didn’t quite manage to take notes for everyone’s talk, but did for most of them. After the workshop, I spent a week on the West Coast visiting a number of game companies (Will Wright’s group at Walnut Creek, the Sims 2 Maxis folk at EA headquarters, and Sony Electronic Entertainment US R&D where Craig Reynolds works) and going to my 20 year high school reunion (“Go Senators“).

Paul Kruszewski: Biographic technologies
Paul gave a post-mortem of how things have gone the last 4 years at Biographic, the AI Implant folks (AI middleware for games).

Vision: AI is next generation computer graphics. There’s been a natural movement from rendering to animation to AI. He believes that some day AI will all go into hardware, just like the rest of graphics. I disagree. The range of techniques called “AI” is so broad that it will always require something like a general purpose processor. Certainly you can implement specific AI languages in hardware (e.g. Symbolics machines implemented Lisp in hardware, over the years people have built hardware implementations of prolog), or specific techniques (e.g. at GDC there was a guy from a company that makes a path planning chip), but there’s no universal hardware support you could provide across all AI techniques, except for a general purpose CPU.

AI Implant attempts to support both the Hollywood special effects industry and the game industry.

“If it moves in an intelligent way, it’s a character. Otherwise it’s physics.” I like this. Similar to the definition of game AI I proposed in my DIGRA paper last November.

AI Implant works as a plugin for Maya, providing visual tools for authoring simple character behaviors.

AI implant is in the “characters as vehicles” tradition first described by Craig Reynolds. This paradigm works well for high-level group behavior (e.g. flocking, battle scenes with thousands of agents, the pedestrians in Grand Theft Auto), but, to my mind, is inappropriate for detailed, language heavy social behavior like we have in Façade.

For games, people really cared about pathfinding, which they didn’t provide detailed support for. They focused on supporting level editors/designers in creating characters, but programmers wanted to own that part.

Challenges:
Physics creates dynamic world.
Huge worlds. Manual methods are no longer an option.
Complex characters: integration of AI with non-linear animation, IK/FK, Ragdoll (animation + AI control)

Nathan Combs: BBN
Nathan described the tensions between declarative and imperative paradigms of behavior design. Currently most character behavior is created via scripting, which is imperative. Scripting is ingrained in the game production culture: coders write infrastructure, designers write game logic in scripting languages.

Rule-based behaviors are an example of declarative behavior design. The strength declarative approaches is that they separate the behavior logic (described directly in rules) from the detailed implementation (control flow).

Interestingly, ABL (the reactive planning language we wrote for Façade) is an imperative/declarative hybrid.

He briefly described the IGDA’s AI group discussions to define a rule-based API.

Cinematic design style (e.g. linear story, lots of cut scenes, etc.) favors imperative approaches, emergent design styles favor declarative approaches.

Duane Szafron: University of Alberta – Code generation for AI scripting
Jonathan’s group has built an editor on top of the Never Winter Nights editor that generates NWN code for you from high-level software patterns. Example patterns include: item container, barrier perimeter, damage source, guard item.

Each pattern has a wizard-like dialog box where you fill in the parameters for the pattern – the system then generates event-based NWN code for you. Under the hood there is a macro language from which NWN scripts are generated.

He gave a nice NWN demo of various generated script patterns in action.

I wonder how often designers want to do deeper modifications of the generated script, that is, directly manipulate the generated code? It seems like you wouldn’t want to make the generated code completely black-box, but would want to allow the designer to drop into the generated code if they wish.

The first version is available on the web.

Hector Munoz-Avila, Lehigh University
Strategic planning for Unreal Tournament bots.

Research questions: reactive planning, case-based adaptation and learning.
Is it possible to create a declarative language for encoding gaming strategies?

Gave an overview of HTN planning. Uses Javabots to accomplish reactivity by implementing atomic plan operators in Javabots. Javabots is a java middleware layer for communicating with UT via sockets. We’re using Javabots in the Experimental Game Lab for our connection of ABL to UT.

He’s using TMKL, an agent modeling language developed at Georgia Tech, to describe his agents.

Paul Carpenter and Ryan McAlinden, USC, ICT
Creating an adaptive opponent within a military RTS. They’re using Full Spectrum Command, a military training game. The opponent generates dynamic opposing forces plans using Graphplan, one of the first plan compilation planners developed at CMU by Blum and Ferst.

Michael Buro, University of Alberta
He issues a call for AI research in RTS games. Some current challenges in RTS AI: adversarial real-time planning, uncertainty, spatial and temporal reasoning, learning, resource management, pathfinding, opponent modeling, collaboration.

Commercial games often cheat: maximizing strength vs. maximizing sales. He’s interested in maximizing strength. In general there was an uncomfortable split at the workshop where AI designers for commercial games focused on creating “fun” AI, and often mentioned cheating, while academic AI researchers focused on “correct” game AI that finds optimal solutions (e.g. crushes the player at every opportunity). In my talk I pointed out that creating an engaging player experience is a first class AI research problem. The choice between cheating or pursuing a traditional AI research agenda is a forced choice; expressive AI is a third option.

He’s developing an open-source RTS game environment.

Elizabeth Gordon, University of Nottingham
GRUE: An Architecture for Building Game Agents
GRUE is based on Nils Nilson’s Teleo-Reactive programs, and is thus in the same class of languages as ABL (reactive planners).

Goal generators generate goals in response to current situation in the world. Authors write goal generators (rules that generate goals). GRUE selects teleo-reactive programs to accomplish goals, where a teleo-reactive program is a collection of rules for accomplishing a specific goal. Goals only appear at the top (no explicit subgoaling), though teleo-reactive programs can call subprograms. But the mechanism for pursing goals and calling subprograms is different (not uniform). One of the features that ABL inherits from Hap is that the goal pursuit mechanism is used uniformly all the way down the behavior hierarchy.

Sequencing is not supported as a primitive in the language, but you can chain rules or call sequential programs on the right-hand side of a rule.

Resource variables are used to manage body resources, similar to the resource management framework we wrote for Façade.

Elizabeth’s home page is here.

David Aha, Naval Research Labs
He’s building a middleware tool to support hooking up learning algorithms to game engines. The goal is to support DARPA challenge problems in learning. The ML community has been focusing on knowledge poor, short-lived systems. He’s interested in supporting learning work in knowledge rich, long-lived domains (e.g. games). The middleware takes five inputs describing the simulator i/o, game model, learning and performance task, reasoning system i/o, evaluation strategy and uses these descriptions to integrate the game world, reasoning system, and learning algorithm. He has DARPA money to support 10 collaborations at game and educational institutions. Current reasoning engines he’s working with include: Soar, ICARUS, DCA.

Joshua Jones, Georgia Tech
Hierarchical judgment composition in games.
Use compositional features (human-provided knowledge about how simpler environmental features combine to form more complex features), to guide learning. Instead of treating the problem as a complex function over a flat feature space, use the hierarchical composition of features to focus learning on simpler problems. Also supports knowledge transfer across situations. He has tested this approach for city placement in FreeCiv (an opensource implementation of Civilization).

Charles Madeira, University of Paris 6
Reinforcement learning for turn-based strategy games.
To address the high dimensionality of the state space, he decomposes problem by military hierarchy, abstracts the current state (doesn’t use raw game state) and bootstraps the learning process by playing against the default game AI.

Ben Geisler, Radical Entertainment
Integrating machine learning into behavior models for games. Particularly interesting in FPSs. Machine learning is useful because hardcoded behavior is boring for player and breaks suspension of disbelief, and, from a developer perspective, encoding AI for FPS agents is tedious and error prone.

Sensibly points out, as I’ve seen pointed out by game AI developers at every game AI conference I’ve been to, that the goal of game AI is to:

Note the distinction to Michael Buro’s talk above, where he said he’s interested in maximizing strength, not maximizing sales. But, focusing on AI that creates a player experience opens up a whole new AI research agenda that still has hard, first class technical problems to solve, but aimed at a different end than traditional AI.

So his goal is to find out how can we use ML to make a better gameplay experience. Humans are fun, as evidence by the popularity of multi-player FPS, so, use ML to have bots learn to play like a human by observing human play. Tried a number of different ML algorithms including: decision tree learning (ID3), naïve bayes, neural networks, neural net ensembles (both boosting and bagging), RL (connectionist Q-learning).

During the discussion, people talked about the idea of behavior capture or “go cap”, where a designer drives a character around in a world, and the system learns to act like the designer (behavioral programming by example). Some work in this area: Michael van Lent, Tozour.

Baylor Wetzel
He’s built a database, called BadAI, of problems appearing in game AI, though he doesn’t have somewhere to host it (I volunteered to host it at Tech). His talk surveyed common AI problems appearing in game titles. Some examples:

These are all problems that you can predict. They don’t require a Ph.D. to solve. They don’t require a bunch of CPU. The solution is to start documenting these stupid, simple problems, so that the solutions become well known.

Robin Hunicke, Northwestern
There was a movement that crested about 2 years ago to develop a language (examples Formal Abstract Design Tools, Design Patterns) for talking about game design and identifying and solving design problems.

At GDC 2001-2004 has participated in a series of game tuning workshops to talk about problems in game designs using the MDA (Mechanics, Design, Aesthetics) model.

It’s an artifact-centered approach: games are unlike other media (movies, books, etc.) in that they are about behavior. In this approach, you look at mechanics (algorithms, rules), how this leads to dynamics (strategies and high-level player actions available through the mechanics) and how this creates an aesthetic experience within the player. Aesthetics is captured by Marc LeBlanc’s 8 kinds of fun: e.g. challenge, narrative, fantasy, discovery, submission.

By breaking “fun” into more specific components, can start talking about how the different parts of the game design create different pleasures.

Dynamics creates aesthetics: Eg. Building, buying, designing, personalizing or customizing yield Expression.

Gave examples of how the MDA could be used to fix the boring endgame problem in Monopoly (losers slowly, painfully lose as the few winners exercise their established monopolies).

The MDA approach:

Aaron Khoo, Microsoft
Aaron gave a case-study of the AI in Mythica a cancelled MMPORPG that was being developed by Microsoft.

AI divided into internal AI, a behavior-based system, implemented in C/C++, and a scripting system, using Lua. It’s interesting that a number of games discussed at the workshop make use of Lua as a scripting language. It seems to be emerging almost as a standard in game scripting, partly becuase of a liberal license model (like, it’s free, and not GPL’d so you don’t have to share your extensions). The scripts use a stack-based interface to communicate parameters to the internal AI.

Behavior stack for NPCs: flee -> rest -> return -> use skills -> respond to alarm -> pick a fight -> move -> do nothing
Each decision cycle, system moves down the behavior stack checking conditions, and executes the first behavior that activates. Individual behaviors can be turned on and off under special conditions.

Gave an analysis of aggro systems. Aggro systems control which characters (players) the NPCs attack. NPCs attack the player the hate the most. This has strong implications for gameplay, specifically coordination between different player types (e.g. warrior (point attacks), nuker (area attacks) and healer).

Greg Alt, Surreal Software
Gave an analysis of the AI in The Suffering: Prison is Hell.
Characters have a hierarchical behavior system similar to ABL’s ABT, where behaviors are implemented as C++ classes. Goal was to create a mixture of scripted and autonomous behavior.

To handle interruptions (e.g. getting shot while you’re trying to climb a ladder), high-level demons interrupt the behavior tree, push the entire behavior tree on a stack , do the reaction, and then restore the behavior tree. Individual behaviors at different levels in the tree figure out if conditions they need have been invalidated and work to restore them.

Jeff Orkin, Monolith Productions
Described the use of real-time planning in games.
Built a C++ toolkit based on the PDDL plan description language (STRIPS-like plan language).
Reasons for using planning in games:

They optimize planning by only representing world state symbolically if there are chains of actions that could make use of that state (preconditions and effects). For other conditions, use calls to arbitrary code. They also used agent-centric representations (e.g. “the character I am attacking”) to minimize the number of symbols they represent. In fact, as pointed out by Ian Horswill, it turns out that the state they plan over grounds into a finite set of expressions, and thus could be handled very efficiently by a combinatoric circuits approach (similar to the propositional caching done by truth maintenance systems).

Curt Bererton, CMU
State estimation for games. He’s applying the particle filter technique used in the robotics community for robot localization to games. For the problem of having an NPC look for a player without cheating, maintains an evolving probability distribution over possible player locations that is updated by observations as well as evolution of the distribution based on presumed player movement.

Paul Brobst, USC
Path planning and automated terrain analysis for games. He’s doing dynamic caching for pathplanning by storing subpaths of successfully generated paths.

Christian Darken, MOVES Institute
Efficient and dynamic response to fire in FPS’s. Interested in avoiding dumb behavior where NPCs don’t make intelligent use of cover when under fire. He’s developed a sensor grid approach in which, unlike most games, the set of hiding places is not fixed and pre-specified, but rather computed dynamically making use of terrain information. He implemented his dynamic hiding place approach in America’s Army.

Joe Andrieu and Jeff Rawling, Real Time Drama
Andrew and I have been following Joe’s and Jeff’s work for a number of years. They founded the company Real Time Drama to build interactive dramas in massively multi-player games. Like our work in Façade, they’re trying to create Aristotelian interactive drama. In their approach, which is still in the design phase, they keep track of multiple potential stories and constantly present dramatic situations to test whether the player’s current motivations continue to be aligned with the protagonist’s motivations in the currently active story. When the system observes that the player’s motivations are no longer consistent with the current motivations, it escalates the dramatic situation, in order to confirm the observation, and then gracefully switches to a different story consistent with the new player motivations. Scenes are viewed as hypotheses about whether the player is capable of the dramatic value change in the scene. Early in story, scenes test aspirational hypotheses about who the player wants to be (do they want to be the scoundrel, the hero, etc.). Later in the story scenes test conformational hypotheses to see if the player is really experiencing the dramatic value change consistent with the character the system thinks they are. This is similar to what we do with beats in Façade, where we offer the player opportunities (tests) to take different actions, and use the player’s reaction to the test to change the story, though we don’t explicitly model and predict the player’s role in the story. They use the same terminology we tend to use in Façade, talking about offering the player dramatic affordances, and recognizing discourse acts the player makes in response to situations.

Borut Pfeifer, Radical
Nice discussion of how reactive agents can help create emergent gameplay. Borut is both a designer and programmer, and so can examine the relationship between technical agent implementation and game design. References Phoebe Sengers work on behavioral schizophrenia in agents, how the kind of behavioral thrashing that reactive systems are sometimes prone to can lead to behavior that looks schizophrenic to the player. Talked about how for games, agent architectures should explicitly represent what the agent wants to communicate to the player and use this knowledge to guide behavior selection.

Finnegan Southey, University of Alberta
Described semi-automated techniques for gameplay analysis. Some examples of analysis: probability of winning, are there “sweet spots” that players can exploit or impossible situations, what is the variance in outcomes, etc. He’s starting with simple scenarios, like a penalty kick in a sports game, or a squad-level battle. Main elements of approach: create abstract features to reduce dimensionality, run simulations to obtain samples, use machine learning to obtain useful summaries of samples. He’s using active learning, where intermediate learner results are used by the learner to specify queries to guide further sampling. Summaries take the form of learned rules, using standard rule-learning algorithms such as C4.5 or SLIPPER. Gave an example of discovering an exploitable sweetspot in a soccer game, where the human can reliably score penalty kicks if they kick into a certain zone. EA is going to use the tool internally to help analyze design for FIFA 2005 (next iteration of EA’s soccer game).

Robin Hunicke, Northwestern
AI for dynamic difficulty adjustment in gameplay. Described her personal research trajectory, moving from building interactive art experiences into games. First research project was to “fix” a problem with FPSs for novice players where novices keep on dying. Built a design where you have a patron, and, as long as your patron is still alive, you stay alive even if you’re getting blasted. Turned out to be incredibly boring, keeping a lousy player alive indefinitely, without the player getting any better. After discovering MDA (see her talk above) at the 2001 GDC Game Tuning Workshop, realized that by trying to fix FPSs, she’d actually broken them, destroying the challenge and tension arc that makes FPSs work. She looked at the concept of flow, where challenge and success are balanced to keep you in a state of intense focus and reward. Also looked at Will Wright’s notion of balancing cycles of positive and negative feedback (success and failure) in gameplay so as to keep the player playing. Then, returning to the FPS case, she’s built a system that predicts probabilities of success and failure for different FPS tasks, and intervenes in the world according to predicated success and failure probabilities in such a way as to keep the player in a certain zone of success and failure feedback. Reminds me of a drama manager, but instead of intervening in the world in such a way as to make a story happen (dramatic evaluation), instead intervenes so as to maintain a flow state (flow evaluation).

4 Responses to “AAAI Game AI Workshop Trip Report”


  1. Ian Wilson Says:
    August 5th, 2004 at 1:12 am

    Michael,

    Thanks for the write up, it was very interesting and informative.

    Nathan talked about what we are doing at the IGDA (to define Game AI standards) and Borut Pfeifer and Jeff Orkin are also part of that effort. This years report is here if you would like to see where we are:

    http://www.igda.org/ai/report-2004/report-2004.html

    Also with the idea of hardware AI, I feel this is the way Games will go for at least a certain sub set of AI tools often used in games such as path planning, line of sight etc. Especially as the latest “GPUs” are now open to general purpose “parallel” processing in addition to the graphics processing for which they were designed. A great site dedicated to coopting graphics GPUs is here:

    http://www.gpgpu.org/

    Robin Hunickes research ties in closely with what I am doing with defining optimal reward. The key point here is that the optimal reward zone for any individual is unique. It depends on personality, age, gender as well as current mood and skill level. It is a moving target that defines your optimal current balance of arousal, stress, anxiety, motivation and reward. The “negative” aspects of course being necessary in order for the “positive” to be, well, positive in relation.

    Anyway, again, thanks for the time and effort with the write up.

    Ian

  2. codemonkey uk from Hulver\'s site Says:
    August 12th, 2004 at 6:20 pm iCalShare Comments
    I maintain an iCal shared calender of games industry / programming conferences [view | subscribe]. I have it listed on iCalShare, in the “Tech” section. If you scroll down that page you will see that “GameDevCon” has two comments. If you click to view…

  3. wendell Says:
    January 11th, 2005 at 6:56 pm

    Hi. my name is wendell brown. I interested in being a game desinger. Can you send me more info’ on you college.

  4. michael Says:
    January 12th, 2005 at 11:14 am

    Wendell, check out Georgia Tech’s undergrad program in computational media and masters program in Information Design and Technology. The best way to get this info is to email me, not to post on the blog (I would have emailed you back and deleted this comment, but there’s no contact info for you).

Powered by WordPress