Thursdays at AiGameDev.com is dedicated to the theory behind game AI. Since the Lyon GDC 2007 has just finished, what better opportunity than to go through some of the research sessions relating to artificial intelligence. I’ll start off with the sessions I attended while I gather more details about the others…
Photo 1: Just outside the GDC hall.
Automatic Behavior Synchronization
Fabrice Lamarche, Assistant Professor at Rennes 1 University, talked about a topic with such a long title that the organizers had to trim down to fit it into the timetable: Automatic Behavior Synchronisation — From Parallel State Machines to Task Modelling. There were few English speakers in the room, and they didn’t seem to mind, so Fabrice did his talk in French.
His system is based on the following ideas:
You build your finite state machines for behaviors separately, only dealing with the resources they need and working for how long.
You specify how the behavior should operate when resources are lost, and how they should get re-aquired.
A compiler transforms the separate FSMs in such a way to prevent deadlocks.
Specialized operators (like a sequence) to combine behaviors together in order to maintain a coherent usage of resources.
A runtime interpreter calculates out which transitions each behavior should take (using a weighted within [-1.0, +1.0]) when there are clashes over resources.
All the technology he described is available in a framework called HPTS++. The code is made up of a compiler and a runtime interpreter, all of which he told me are about 6,000-8,000 lines of code. He sends it out on request but apparently if you want to use it commercially you’ll need to negotiate some kind of license.
That said, the information necessary to re-implement everything is available in the following paper:
Automatic Orchestration of Behaviors Through the Management of Resources and Priority Levels F. Lamarche et S. Donikian. Proceedings of Autonomous Agents and Multi-Agent Systems, 2002. Download (PDF, 265 Kb)
I came out of the talk thinking two thing:
It’s amazing that someone has developed such an understanding of concurrent behaviors, their scheduling, and calculating the best way of doing that based on priorities.
Since a fully optimal solution isn’t required for games, what’s the best way for game developers to get the major benefits of this technology with the least amount of work?
That second question is certainly one to investigate further, but the approach I mentioned in my talk of falling back to an alternative behavior in the search tree when the resource is locked is incredibly easy to implement and also deadlock free. So I feel it’d be a good starting point to integrate some of Fabrice’s better ideas without having to spend too much time on it.
Screenshot 2: Competing behaviors while drinking coffee and reading.
You can also watch the resulting video right here (AVI, 6.1 Mb).
Playing to Train Your Video Game Avatar
Ronan Le Hy, Research Engineer at ProBayes, gave his talk on using Bayesian modeling and learning from players to create AI behaviors. He used the original Unreal Tournament deathmatch game as a basis for his research.
The approach he described works as follows:
Setting up a model using the 7 basic states (n) of a traditional deathmatch behavior, and roughly 10 sensory values (s).
Building a set of matrices, including a large n2 one and smaller ones for the sensory values separately.
These probabilities are combined together to approximate the best state to select based on the current state and the sensory values.
There are lots more cool techniques in this research, but I felt that Ronan didn’t pick the best selling point during the talk; he described it mainly as an easy way to edit behaviors using a large set of transition matrices that store probabilities. I doubt this approach helps compared to a FSM graph editor (for example), and if anything, having to work out all the possible transitions by hand is a step backwards.
However, the fascinating part of the research was how he applied Bayesian techniques to the problems of:
Inducing those large probability matrices based on observations of play.
Figuring out what state the player is in automatically based on observations
Ronan didn’t talk about this very much in his presentation, but I asked him a few questions after the talk and managed to catch up with him during coffee. Apparently, there’s absolutely no code used to help the Bayesian algorithm figure out what state the player is in; it’s done entirely using an estimation-maximization algorithm known as Baum-Welch. Since there’s no way of knowing what the player is doing, this algorithm makes it possible to estimate the model based on a hidden state (i.e. a HMM or Hidden Markov Model).
Teaching Bayesian Behaviors to Video Game Characters; Le Hy, R., Arrigoni, A., Bessière, P., Lebeltel, O. Robotics and Autonomous Systems, 2004. Download (PDF, 154 Kb)
Ronan mentioned that this approach is only guaranteed to converge to a local minimum, so you can’t be absolutely certain what a player intends. That sounds about right for games anyway, and I’d be worried if it could do any better!
Screenshot 3: Bots learning to play Unreal Tournament from players.
You can also watch a low-resolution movie (MOV, 9.2 Mb) of this research, showing the bot learning from human training.
Stay tuned for more coverage of GDC, including research sessions!