AIIDE 2008: Day 2 Live Blogging

AI IDE 2008(A reminder.  I’m editing these notes a week after the fact, just making it readable, but I’ve left the original voice in this piece and roughness intact because I feel the live-blogging depth is more useful then a concise, thoughtful analysis would be. I’m happy to answer any questions people have, though, and I encourage you to contact the original presenters as well for more thorough details.)

(links to my Day 1 conference live blog)

The AI of Spore by Eric Grundstrom (EA Maxis)

The keynote speaker this morning, Grundstrom talked about the AI tech of Spore and its player-centric and asymmetrical focus. Starting with the Cell stage, Maxis used a lot of fluid and particle simulation alongside the flocking AI to create unique movement. I believe this was Jeff Gates work, a friend of mine. Behavior was part-AI driven and part-design to make interesting differences between the creatures. The key was always AI that was player-centered personality design. They started with depth before breadth – make the first AI really compelling before you generalize it to different sorts. A funny but familiar aside – when growl music was added for when AIs attacked QA reported that the AI seemed better, even though none of the AI had actually changed. The whole Cell stage asymmetric AI, in that it’s PvE – the NPCs don’t grow like the player and have different goals.

Grundstrom then moved on to the creature game. The goal was to duplicate Diablo‘s model. The key difference with the creature game is they wanted a real range of behaviors – responding to stimuli, interrupting and resuming behaviors, and scheduling some behaviors against time. He started with the “Interaction system” – just rank each action and choose the highest one. Each action runs till it stops. It sounds very similar to the Diablo AI, actually. NPCs get invited to group actions. The big drawback was that it scaled poorly – each action needed custom code to handle interrupts and stimulus to switch to other actions. So the big takeaway – they switched to behavior trees. The win was that they can now have all actions re-evaluate every frame, so interrupts are simpler. They wished they’d done an animation state machine to sequence animations to their actions. Another lesson was to keep the NPCs passive at nests and let players seek out interaction, because the chasing gameplay is harder to do then it sounds – it just comes down to who is faster. You’d get followed forever or you’d be dead. This general role of treating NPCs different from players was important – very not-multiplayer.

On to game 3 – the tribe game. The big new play was specializing and upgrading tools. It’s an economy slider balancing game. Still autonomous agents and packs, so the needs are fairly similar to creature game. Grundstrom kept behavior trees, but wanted to do group behaviors for the tribes. Thus there’s a new join behavior and a lead behavior, and the lead behavior gives orders to the members. This was helped by a group manager – because otherwise if the lead individual was killed, the group would lose track of its goal. There was still a general design focus on player-centered PvE – pace the AI attacks for drama, warn player of impeding attacks, etc. Not much new AI so far – the stages are so broad and vague that I believe individual games have gone farther in each AI type. The organization and reuse became correspondingly more important then normal, however.

The penultimate game AI is “Civ-style” – a very different kind of challenge, more RTS then action game. There are now cities, and a communication screen to communicate with city agents. The relationships between the various agents were very complex – Civ4 style attributes that aggregate to a number, using Civ4‘s the improvement of the added player feedback. Here the AI is strategic – building, upgrading, relationships, managing attack tactics, pathing (for the first time really, beyond steering!), and citizen vignettes that give appropriate feedback to the player. They used 2 kinds of scripts for strategy – domestic and expansion scripts, but the engineers unfortunately ended up doing them all in C++. These scripts formed each tribes plan. Grundstrom forced the AI to attack their lowest relationship so as to create a better story. He also used different relationship decay rates across attributes to add more dynamism.

Behavior trees and groups were again used for the individual attack units. The units routed using A* with some optimization, focusing on the path following rather then the path creation. There were a wide variety of unit types to support: planes, ships, and vehicles. Which meant a desired facing pathing solution as well as a position solution. In the end could have used better obstacle management and environmental awareness to handle routing. Reserved destinations on the map would have helped too. Maxis used emergent formations, coming from each group picking nodes in sequence (from front to back?), and group’s members around existing picks. (In practice, this had some problems, particularly in tribe where pathing was trickier and all members had to be in place before performing.) Player/NPC Asymmetry was less in civ stage, almost even, but he did give the player a head start and super-weapons to end the stage faster. Much more going on here AI-wise then in the stages so far.

And lastly, space. Relationship management here was key, and there are is a lot of new data throughout space to manage. It’s an avatar game, lite RPG upgrading rather then strategy. Key new techs were the terraforming and ecology simulation, and NPC empires with the same conversation, trade, expansion and war needs of civ. There was a neat random name generator for all those planets, which used a similar approach to Cope’s music generator – using frequencies of letters in common names to generate whole new names. In space they went for a turn-based expansion feel, so the pacing was very deliberate and relied on externally controlled events. This included “random” disasters and raids, which create an implicit limit on empire size (although design could tie “random” rate to size). They liked the plate-spinning aspect of it. Each empire also has a random personality, which affected diplomacy and relationship changes from events. Initially each personality was a separate goal and voice, which made a lot of combinations that were less predictable. But the problem was that the writer had to write for each combination, so they settled on only 8-9 types. Overall, data management was the key issue for the project, because not all of it was in memory at once. They still focused on staying player-centered and asymmetric – transparent relationship, local simulation, and simplified ecology, no real economy at all, and different technology tree for the player.

Big conclusion was to keep it simple and stick with established practices for low risk and ease of tuning. Use player-centered illusions because they are efficient and compelling, even though you lose the emergent simulation which is so AI-dreamy. If he did it again, he would have tried a more complex AI setup while focusing on a simple interface (not clear how this is not just a radically different goal with a interface requiring more work, but I think he wished they could have done more emergence). Grundstrom points to the ecology as an example, saying they kept the model simple for the ecology – carnivores, herbivores, etc – but simulate more behind the scenes. Lastly, the PvE asymmetry was important because it was significantly easier to balance and tune and adjust the NPCs when the game design changes if it doesn’t affect the player.

Grundstrom future desires from the AI community are more living worlds – an illusion of more complex worlds that allow players to go anywhere, do anything. This requires NPCs that are interesting, change over time, and react to others and the environment. He also wants to see more believable people that reacts to a mental model – personality, memory, relationships, emotion – as well as events and behavior customizable for any game. He also points to movie stories that are really “tight” – everything matters and builds progression to overall global goals. Mentions Facade as a direction, but thinks things can be simpler – probabilistic state machines that can be tuned.

Overall, the data issues sound like the most interesting challenge, here, but unfortunately there’s little detail. Question about the LOD touches on this a bit – there was local simulation of empires. Tribe LOD did something similar – different levels of processing for each distance. I asked him about the data management afterwards and he answered the senior engine programmers were able to solve it and keep the data invisible from the AI through something like 10 substantial refactoring, using a mix of data caching, time delays, and data structure optimization. It was made trickier by the need for procedural content from the network, but they pre-streamed content packages in, and used Maxis content off the disk in a pitch.

Into the sessions!

Stochastic Plan Optimization in Real-Time Strategy Games from Andrew Trusty (I believe)

Games have huge decisions spaces, huge state spaces, non-deterministic, real time – your classical approaches don’t work directly. We could abstract the game state or abstract the decision space or add domain knowledge. Trusty’s approach is to use case-based planning for RTS micro battles – use a pre-created planning library, find a plan that is similar to the goals of the current problem, and adapt it to the situation. So, where do the plans come from? How do we find them? And how do we adapt them? He calls their approach the Darmok architecture. The idea is to get plans by observing human experts. Today he’s focusing on fixing bad plans from the experts, unintentional errors. Stochastic Plan Optimization is called for! When a plan fails, the algorithm evolutionarily reevaluate the plan and finds a better plan for the failed goals the next time. Assumption though, the entire plan space can been searched and the original plan isn’t wholly bad. Phase 1 of the search – take the original plan and alter it randomly, to get a search space. Then run each plan in-game (for hours) behind the scenes and apply a fitness to each plan. Phase 2, take the top 4 plans, and then randomize/prune/mix/in-place randomize them together. They check to make sure that there aren’t duplicating a plan here, to explore further. Then run them through the generations again, evolvingly.

First issue in tests was that the experts were just not very good at this particularly game – or situations compounded inside the gameplay that forced them to make obviously bad tradeoffs. This led to a pretty bad overall database. So how well did this algorithmic fix them? Pretty well, the expert plans turned out better. The catch? The algorithm still takes a lot of time, particularly because you are running the game every time you test and evolve your plans. He needs to reduce the search space or run the game faster. And this is for only winning local RTS battles. This needs to scale up to wars for larger plans. There’s some potential here for micro in RTSs though, which is otherwise really hard AI. Trusty needs to account for terrain more, but that could probably be done in the plan actions. There would also have to be some accounting for difficulty, like APM limits – since the optimal plan here is likely just more complex and faster actions wouldn’t be perceived as fair by most players. There’s player coaching potential too – training players to make better RTS decisions in during their play or while analyzing replays.

Constructing Complex NPC Behavior via Multi-Objective Neuroevolution with Jacob Schrum from University of Texas.

Daytime television programming for kids! Nope, couldn’t fool you, that’s not what this is. It’s making tools that discover NPC emergent behavior ahead of time and provide levers to tune emergence. Or, more directly, Schrum’s concern is that reinforcement learning and evolution don’t consider multiple objectives in their fitness function. So he applied a “Prareto optimization” approach(?), which requires exceptional performance in every objective considered. Since most objectives are in conflict, this will find a “front” along the trade-off axes where the trade-offs are most optimal. This also means the trade-offs could be optimized in different ways (the levers), by moving the optimization algorithm along the front. He uses a Non-dominated Sorting Genetic Algorithm II (K. Deb 2000) algorithm to find the points. (Catch here is you have to be able to quickly generate the possible data points, which means simulating each one as they are randomly moved as the rewards for each trade-off are varied). Schrum used neural networks to be the bots for each mutations. He started with the simplest static player strategies to evolve against and then went to more aggressive strategies. He compares his tests to the standard approach using the weighted sum from individual objectives. Results show definite improvement. In examples the single objective approach can’t find a good balance of the objectives – in one case they just run away and chase forever (because all agents are the same speed). With Schrum’s multiple objectives approach, there is better teamwork – baiting the player bot by getting the player to turn away or a charging strategy that takes advantage of the player’s facing and swing direction after getting the player gets hit from another angle. Both are valid answers, but balance the objectives along the front differently. Many of these behaviors evolved were in fact unpredicted, but successful. The research definitely creates a distinctive fixed behavior model for the NPCs that players could play and learn against, because the player trainer bot is static. Haven’t noticed this feature before – makes it much more viable in games, because predictable NPC behavior is so important. Others must be doing it too. Schrum proposes learning against humans (which would remove this benefit, so I’m not sure that’s the best step). He also wants to optimize the training and sim iterations for real time learning. The big win of the research is the emergent strategies are more apparent and more integrated across multiple conflicting goals – there’s a balanced approach rather then the oscillations that comes from using a single fitness score for multiple goals. The drawbacks are just the complexity of the training algorithm – the game would have to be really focused on this need.

Effects of Communication on the Evolution of Squad Behaviours from Darren Doherty.

Doherty’s domain is squad-based shooters, an area that needs AI for situation-based tactics. He looked at PvP players and cited communication, role definition, and skill as 3 factors of team success, and tried to build them into a bot. Using goal driven agents, he evolved a ranged combat decision making tree constrained by limited senses and memory. He minimized his evolutionary algorithm against damage taken, team damage taken, and maximizes enemy health, and then tested the bot in a squad, fighting a more capable single enemy. Unfortunately his data comparisons are just against communicated data versus uncommunicated data, and shows communications improve team performance, but only 2.5%, yikes, less then sensory improvements. I’m not sure I understand the goal of the research here. Since we can fake this pretty well with shared team knowledge, I’m not sure how valuable this is. Even setting this up on individuals alone isn’t too hard (I’ve set it up myself several times).

Implementation Walkthrough of a Homegrown “Abstract State Machine” Style System in a Commercial Sports Game from Brian Schwab of SCEA.

Schwab created a situational data-driven system for the non-technical staff on SCEA’s basketball title, similar to a scripting language, and goes into the slimy guts of the language. In the tool, any resolution of game state was important, and multi-agent coordination was key. Schwab built his AI starting with a global FSM that ran a gross game state, using a custom script, for taking care of pausing, free throws, etc. Then a perception layer (variables, condition bools that are optimized, and percepts – ramped conditions) that can be tested against in agent behavior. Then there was the agent behavior animation-selection layer – a FSM with nodes representing animation selection. Next he went into the designer’s scripting language. Each agent was defined by a set of game roles in the script that were collections of expressions and conditions using AND based logic (to keep them simple to create technically). The scripting language itself was built around situations – the general decision making using expressions, conditions, and roles. Situations weren’t just states, but nodes within a decision tree, with grouped children under parents, priority based. There were many different node types: abstract nodes to partition states, persistent states – the current head of the tree for the team, and the non-physical situation nodes which are abstract but can change variables and fire events (not clear why better then abstract nodes here). I think this was to allow multiple “threads” to run at once from one script. The roles for agents supported “inheritance” that give the scripts memory. There were several types of special roles as well: non-required, non-physical roles, and exclusion roles. This language wasn’t an abstract state machine so much as a formal method for specifying algorithms for the designers to follow. A state with a set of values and rules. It’s a data structure that models code – aka a scripting system. Designers used it for cameras, cutscenes, crowd, commentary, storylines, minigames, etc. They could switch between reactive script to interactive AI, and could filter out interrupts from other places and declare how the script was allowed to exit. For debugging, Schwab used the game’s replay buffer to get debug visual and text data, including any situations running. He supported dynamic loading and a nifty “teleport” button to setup each situation immediately for debugging. His big takeaways – don’t change your AI engine and rewrite the content in less then 2 years. Also, Usability is key – steep learning curve is no fun. There were lots of pitfalls and gotchas. There’s a lot of special case situation times added. Make sure you support syntax checking and keep GUI conventions that are useful and consistent. He has a great search bar for searching every behavior, variables, and situations. This helps organize and track the situations. It even has scoping windows to see who could interrupting each situation! These kind of usability details are very handy.

Dynamic Expansion of Behaviour Trees by Gonzalo Flórez-Puga.

Florez-Puga has been studying Damian Isla’s behavior trees in the seat next to me. Ah, it was for his presentation. He goes into the backstory of what the behavior tree is – see Damian Isla’s paper if you want the details, it’s quite good. Florez-Puga recalls that within each hierarchical state the priorities can change at runtime. And users can get parameter creep in tuning trees. Since they are used across all characters trees could get wrecked by other designers at runtime unknowingly. So he’s building tools to help designers author behavior trees. In particular, there’s a search of existing trees to help designers jump start making new states (states in the tree? He’s falling into FSM language… ah, he’s using a FSM inside each node of the behavior tree, where the behaviors are more goals). He points out the trees are similar to case-based reasoning in their reuse. Maybe we can use case-based reasoning to fill our behavior tree at run-time? (Hmmm… why couldn’t the behavior tree have those cases in it already and run the reasoning inside its initial preconditions? This seems to be research that’s strayed far from it’s stated purpose. – helping designers) Now he’s got a neat demo of a simple 3d environment where each room in a dungeon is a C++ class and contains methods as quests and byte code data as prey. He’s using this as his domain. But I’m losing where he’s going. He shows the process for his research, but I’m not clear on the benefits. He’s pointing out that you could dynamically remove and add nodes to the tree based on general game state. (But the tree evaluates that inherently within each action. Are you effectively pulling the evaluation outside of each action? Since the case needs to know the action’s parameters, I’m not sure if that’s a win, over generalizing the evaluation to data for all actions. It it’s a win, it seems pretty straightforward). Florez-Puga says this could add dynamic learning and unplanned behavior mid-game. But it still requires tweaking floats and regressive testing and QA. The big question is whether it actually makes authoring easier, unanswered.

Hierarchical Petri Nets for Story Plots Featuring Virtual Humans from Daniel Balaš

Last before lunch. Balaš wants to compare dynamic Finite State Machines to “petri nets” for controlling story agents. FSMs are formal, comprehensive, graphical, and can be made hierarchical. But they can’t run in parallelism and it’s hard to represent variables and constraints within the transitions. He displays a story as a FSM with each node as a location to travel to or an action or result that can be reached. Issue is that it’s difficult to remove nodes from the machine, and then enable new story transitions simply. Instead, petri nets are directed graphs of places and transitions. But, transitions can also be from multiple input places and output places. The key is there can be multiple ins and outs from each node that both get traveled. The petri net will pause each branch until transitions join back together in a node. Petri nets are also are non-deterministic, supporting dynamic movement between nodes. In a story, Balaš represents the agents as occupying a node (“a token”), and then creates story conditions based on the location of each token. This makes the results of each transition predictable. He modifies tokens with attributes, like color, to add query for the transitions, as well as supporting hierarchical petri nets. He built this technique into Europe2045, an educational multiplayer online game for high schoolers. He demonstrates the game’s Conflict in Darfur story branch setup in a petri net. Can we use it to control agents and specify a whole story? Yes, with some changes – petri nets can’t specify “when all agents come”, but he uses a new kind of transition to guard against this.

Balaš is still working on the testing and development of the technique within the specific game to get results.

This is a representation model for stories, but I’m not clear how this is useful – it’s an algorithmic model of things that already had to be created somewhere else. It would only help if this model’s construction is faster then other methods. Question: yes, Balaš can also extend the petri nets to account for time.

Logical Agents for Language and Action in Martin Magnusson

Unfortunately, I missed the talk over lunch. Check for his work. Magnusson is exploring a theorem proving out language as a new form of gameplay,. I’ve seen the demo video before, but haven’t played with it. He really focused on constraining the gameplay options so that the logic is more communicative and more interpretable by a machine. Worth checking the demo out. How different will this feel in practice, from something, say, like Creatures?

Recomibinable game mechanics for automated design mechanics by Mark J. Nelson

Nelson is trying to give answers to game designs using formal logic for game representation, rapid prototyping, level randomizers, etc. He’s breaking down mechanics-heavy design dynamics using MDA (mechanics-dynamics-aesthetics) into a fashion that could be formalizable. So he can sim it. For example, Nelson references Spore’s rapid prototypes – each either investigating specific mechanics or building a more complete model. The idea is interesting – theoretically designers could queries their ruleset on outcomes – max # of zerglings in 3 minutes, can 2 turrets make base impregnable, can base be overrun with [units]? The goal is to answer balancing questions and provide new information-visualization features. He’s been interviewing game designers, mainly Chaim Gingold, to learn more of what designers need. The idea here is actually blindingly simple – if mechanics are rules, why can’t we analyze them mathematically and make computer queries about their structure?

Nelson’s work focused on board games, using first-order logic. He’s writing a designer tool in a declarative logic language, supports arbitrary reasoning, but requires frame axioms and has no real natural representation of time. Event calculus provides the framework within the first-order logic for reasoning about the system dynamics. The tool he’s writing has states – fluents, events, and timepoints. Fluents can holdAt() timepoints, events happen at time points and can start or end fluents. The axioms define the semantics (rules). Fluents don’t change their values, and you don’t have to specify what isn’t effected, only proactive rules. Fluents thus become game state, events encode player input and game-world events. Game mechanics are the state-evolution rules that result from these rules and states.

Momentary realization rant: part of the problem with AI for design is AI is a procedural solution to a one-off problem. If you only need one solution, one time, making a program to find that solution is a tough sell. Outsiders (read Middleware) could provide solutions to lots of people, or you could find situations (like fine tuning) where AI is needed to respond to the simulation frequently, but one-run AI solutions just won’t be used by designers. They like thinking about it themselves the first time too much.

Last, Nelson focuses on setups that are already procedural or have tunable rules. The tool’s still “assembly-ish”. The potential is good though , particularly for game-games rather then story-games. There’s also a setup time issue – whether this sort of tool is actually useful depends on how long an idea takes to setup to test against. But there seems to be a lot of good potential uses – map balancing in starcraft, for example, or drama management testing. I think it needs more formalization and design input, but while it’s a bit vague, it’s interesting, applicable work, and I’d like to stay in touch with him. Question: How to deal with non-determinism of games, given logic is deterministic? Some models don’t require it, and logic can be modified to do some of it (say with multiple simulations). True – many times you are trying to model a particular path anyways.

Into the poster sessions!

PaSSAGE: A Demonstration of Player Modelling in Interactive Storytelling from David Thue

Thue had data to show that drama management had greater then a 75% increase in surveyed enjoyment in Neverwinter Nights if you just picked events using a calculated player archetype. I’ve never really tried to model player archetype because I thought players liked to choose and change their archetype while playing, but he’s trying it. He’s doing player modeling across 5 archetypes, mapping the encounters to these axes, and then choosing the most appropriate encounter from the results. There’s feedback within each encounter to change the player’s archetype – conversation optoins within the encounters that are pre-weighted to signal a certain desire. This give, some feedback into the model. The data is a great feather for player modeling, but I’m not sure it’s a big enough finding to be significant yet – there’s still reusing all the content lost in the encounter branches, for example.

EMPath: Integrating Experience Management into an adventure game from Anne Sullivan and Sherol Chen

Sullivan and Chen tried to do Drama Management in adventure games to see if it provides a better experience specifically for quests. Correction, they call it Experience Management rather then Drama Management because they really aren’t trying to create drama, they are just trying to guide and improve the experience. Their test game uses real event sequencing to control the experience – measuring Story Density, Information Intensity, Thought Flow, and Manipulation to manage the overall experience. There’s also a differentiation of hints and other types of changes from new events that I need to remember to ask for more detail on. The Experience Manager has a set of actions it can do – move an event, stall an event, force an event on a player – and it chooses them based on those controls to push you along it’s multi-branched story path. This is somewhat more similar to what I was doing before. They use significant plot points rather then zones to demarcate when to take Experience Manager actions. The Manager really helped remind people of things they otherwise would have missed within the plot line. Most importantly , Sullivan and Chen did surveys of players that show significant experience improvement. Really interesting, familiar work. I had more of the drama element in my attributes, and a bit more larger game plot pointing and content development, but it’s definitely down the same lines and they have some data to show for it. Hopefully this will become another good argument for doing narrative management – demonstrable experience improvement – along with the reduced content reasons that I’ve used in the past. Exciting! A good take-away from the conference, and I’ll be interested if they can show the content reduction games as well.

Direction Maps for Cooperative Pathfinding from M. Renee Jansen looked like a faster simpler way to do patrol routes using vector flow fields, although this problem doesn’t seem to come up too often. I could really see using it in crowd pathfinding tech.

Automatically-generated Convex Region Decomposition for Real-time Spatial Agent Navigation in Virtual Worlds from D. Hunter Hale should give the path-planners and maybe collision detection guys a lot of fun. Hale proposes an interesting technique for simpler and faster convex mesh filling, with the downside being the merging and reduction steps are left to the user and it works only for fixed, known convex obstacles. Basically, in 2D, the technique relies on slowly growing out the mesh starting inside user-grid defined regions. Region edges stop growing if they hit something, vertices grow along anything they hit. Wait until they stop growing, then detect adjacent empty space, and repeat these steps until all regions are full. Then combine any regions that would stay convex, remove the collinear vertices and zero length edges, and you’re done.

Whew! Two down, one more to go. Another day with tons to cover. But I learned a lot!

2 thoughts on “AIIDE 2008: Day 2 Live Blogging

  1. Pingback: Grand Text Auto » i’m an ngmofo

  2. Pingback: AIIDE Day 3: Live Blogging « Game of Design

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s