I was browsing through my Google alerts for “Game AI” and this jumped out at me. It was a review of the upcoming Ghost Recon: Future Soldier on Digital Trends (who, TBH, I hadn’t heard of until this). The only bit about the AI that I saw was the following paragraph:
The cover system is similar to many other games, but you canât use it for long. The environments are partly destructible, and hiding behind a concrete wall will only be a good idea for a few moments. The enemy AI will also do everything it can to flank you, and barring that, they will fall back to better cover.
There is a sort of meta-reason I find this exciting. First, from a gameplay standpoint, having enemies that use realistic tactics makes for a more immersive experience. Second, on the meta level is the fact that this breaks from a meme that has been plaguing the industry for a while now. Every time someone suggested that enemies couldâand actually shouldâflank the player, there was a rousing chorus of “but our players don’t want to be flanked! It’s not fun!”
“but our players don’t want to be flanked!”
This mentality had developed a sort of institutional momentum that seemed unstoppable for a while. Individuals, when asked, thought it was a good idea. Players, when blogging, used it as an example of how the AI was stupid. However, there seemed to be a faceless, nebulous design authority that people cited… “it’s not how we are supposed to do it!”
What are we supposed to do?
One of the sillier arguments I heard against having the enemy flank the player and pop him in the head is that “it makes the player mad”. I’m not arguing against the notion that the player should be mad at this… I’m arguing against the premise that “making the player mad” is altogether unacceptable.
“…it makes the playerÂ mad.”
In my lecture at GDC Austin in 2009 (“Cover Me! Promoting MMO Player Interaction Through Advanced AI” (pdf 1.6MB), I pointed out that one of the reasons that people prefer to play online games against other people is because of the dynamic, fluid nature of the combat. There is a constant ebb and flow to the encounter with a relatively tight feedback loop. The enemy does something we don’t expect and we must react to it. We do something in response that they don’t expect and now they are reacting to us. There are choices in play at all times… not just yours, but the enemy’s as well. And yes, flanking is a part of it.
It builds tension in my body that is somewhat characteristic of combat.
In online games, if I get flanked by an enemy (and popped in the head), I get mad as well… and then I go back for more. The next time through, I am a little warier of the situation. I have learned from my prior mistake and am now more careful. It builds tension in my body that, while having never been in combat, I have to assume is something that is somewhat characteristic of it. Not knowing where the next enemy is coming from is a part of the experience. Why not embrace it?
Something to fall back on…
One would assume some level of self-preservation in the mind of the enemy…
The “fall-back” mechanic is something that is well-documented through DamiÃ¡n Isla’s lectures on Halo 3. It gives a more realistic measure of “we’re winning” than simply mowing through a field of endless enemies. Especially in human-on-human combat where one would assume some level of self-preservation in the mind of the enemy, having them fall back instead of dying mindlessly is a perfect balance between the two often contradictory goals of “survival” and “achieving the goal”. It is this balance that makes the enemy feel more “alive” and even “human”.
If enemies simply fight to the death, the implication is that “they wanted to die“.
Often, if enemies simply fight to the death, the implication is that “they wanted to die”. Beating them, at that point, is like winning against your dad when you were a kid. You just knew that he was letting you win. The victory didn’t feel as good for it. In fact, many of us probably whined to our fathers, “Dad! Stop letting me win! I wanna win for real!” Believe it or not, on a subconscious level, this is making the player “mad” as well.
They want to win but you are making them choose to live instead!
By given our enemies that small implication that they are trying to survive, the player is given the message that “you are powerful… they want to win but you are making them choose to live instead!”
Here’s hoping that we can actually move beyond this odd artificial limitation on our AI.
Total War creator, The Creative Assembly, has announced the development of the latest in the line of acclaimed RTS games, Shogun 2. While the Total War franchise has a 10-year history and is fairly well-known for its AI, Â this blurb from their web site has spread through the web like an overturned ink well:
Featuring a brand new AI system inspired by the scriptures that influenced Japanese warfare, the millennia old Chinese âArt of Warâ, the Creative Assembly brings the wisdom of Master Sun Tsu to Shogun 2: Total War. Analysing this ancient text enabled the Creative Assembly to implement easy to understand yet deep strategical gameplay.
Sun Tzu‘s “The Art of War” has been a staple reference tome since he penned it (or brushed it… or whatever) in the 6th century B.C. It’s hard to find many legends that have made it for over 20 centuries. Its applications have been adapted in various ways to go beyond war to arenas such as business and politics. Suffice to say that “The Art of War” lives on as “things that just make sense”.
The problem I have here is that this seems to be more of a marketing gimmick than anything. After all, most of what Sun Tzu wrote should, in various forms, already be in game AI anyway. Â To say Sun Tzu’s ideas are unique to him and would never have been considered without his wisdom is similar to saying that no one thought that killing was a bad idea until Moses wandered down the hill with “Thou Shalt Not Kill” on a big ol’ rock. No one stood around saying, “Gee… ya think?” Likewise, Sun Tzu’s advice about “knowing your enemy” is hardly an earth-shattering revelation.
Certainly, there is plenty of game AI out there that could have benefited from a quick read of a summary of Art of War.
Certainly, there is plenty of game AI out there that could have benefited from a quick read of a summary of Art of War. Things like “staying in cover and waiting for the enemy to attack you” come to mind. Of course, in the game world, we call that “camping” (as an individual) or “turtling” (as a group). I can imagine a spirited argument as to whether a camping/turtling AI is necessarily What Our Players Wantâ¢, however. It certainly beats the old “Doom model” of “walk straight towards the enemy”.
And what about the Sun Tzu concept of letting your two enemies beat the snot out of each other before you jump in? (I believe there are translations that yielded “dog shit” rather than “snot” but the meaning is still clear.) If you are in an RTS and one enemy just sits and waits for the other one whack you around a little bit, it’s going to look broken. On the other hand, I admit to doing that in free-for-all Starcraft matches… because it is a brutal tactic!
The problem I have with their claim is that we already do use many of his concepts in game AI.
The problem I have with their claim, however, is that there are many concepts in the Art of War that we already do use in game AI. By looking at Sun Tzu’s chapter headings (or whatever he called them) we can see some of his general ideas:
For ease of reference, I pillage the following list from Wikipedia:
Laying Plans/The Calculations
Waging War/The Challenge
Attack by Stratagem/The Plan of Attack
Weak Points & Strong/Illusion and Reality
Maneuvering/Engaging The Force
Variation in Tactics/The Nine Variations
The Army on the March/Moving The Force
The Attack by Fire/Fiery Attack
The Use of Spies/The Use of Intelligence
Going into more detail on each of them, we can find many analogues to existing AI practices:
Laying Plans/The Calculations explores the five fundamental factors (and seven elements) that define a successful outcome (the Way, seasons, terrain, leadership, and management). By thinking, assessing and comparing these points you can calculate a victory, deviation from them will ensure failure. Remember that war is a very grave matter of state.
It almost seems to easy to cite planning techniques here because “plans” is in the title. I’ll go a step further then and point out that the practice of collecting information and assessing the relative merits of the selection, you can determine potential outcomes or select correct paths of action. This is a common technique in AI decision-making calculations. Even the lowly min/max procedure is, in essence simply comparing various potential paths through the state space.
Waging War/The Challenge explains how to understand the economy of war and how success requires making the winning play, which in turn, requires limiting the cost of competition and conflict.
This one speaks even more to the min/max approach. The phrase “limiting the cost of competition and conflict” expresses the inherent economic calculations that min/max is based on. That is, I need to get the most bang for my buck.
Attack by Stratagem/The Plan of Attack defines the source of strength as unity, not size, and the five ingredients that you need to succeed in any war. In order of importance attack: Strategy, Alliances, Army, lastly Cities.
Any coordinating aspects to the AI forces falls under this category. For example, the hierarchical structure of units into squads and ultimately armies is part of that “unity” aspect. Very few RTS games send units into battle as soon as they are created. They also don’t go off and do their own thing. If you have 100 units going to 100 places, you aren’t going to have the strength of 100 units working as a collection. Â This has been a staple of RTS games since their inception.
Tactical Dispositions/Positioning explains the importance of defending existing positions until you can advance them and how you must recognize opportunities, not try to create them.
Even simply including cover points in a shooter game can be thought of as “defending existing positions”.
Even simply including cover points in a shooter game can be thought of as “defending existing positions”. More importantly, individual or squad tactics that do leapfrogging, cover-to-cover, movement is something that has been addressed in various ways for a number of years. Not only in FPS games do we see this (e.g. F.E.A.R.), but even in some of the work that Chris Jurney did originally in Company of Heroes. Simply telling a squad to advance to a point didn’t mean they would continue on mindless of their peril. Even while not under fire, they would do a general cover-to-cover movement. When engaged in combat, however, there was a very obvious and concerted effort to move up only when the opportunity presented itself.
This point can be worked in reverse as well. The enemies in Halo 3, as explained by DamiÃ¡n Isla in his various lectures on the subject, defend a point until they can no longer reasonably do so and then fall back to the next defensible point. This is a similar concept to the “advance” model above.
Suffice to say, whether it be advancing opportunistically or retreating prudently, this is something that game AI is already doing.
Energy/Directing explains the use of creativity and timing in building your momentum.
This one is a little more vague simply because of the brevity of the summary on Wikipedia. However, we are all well aware of how some games have diverged from the simple and stale “aggro” models that were the norm 10-15 years ago.
Weak Points & Strong/Illusion and Reality explains how your opportunities come from the openings in the environment caused by the relative weakness of your enemy in a given area.
Identifying the disposition of the enemy screams of influence mapping…
Identifying the disposition of the enemy screams of influence mappingâsomething that we have been using in RTS games for quite some time. Even some FPS and RPG titles have begun using it. Influence maps have been around for a long time and their construction and usage are well documented in books and papers. Not only do they use the disposition of forces as suggested above, but many of them have been constructed to incorporate environmental features as Mr. Tzu (Mr. Sun?) entreats us to do.
Maneuvering/Engaging The Force explains the dangers of direct conflict and how to win those confrontations when they are forced upon you.
Again, this one is a bit vague. Not sure where to go there.
Variation in Tactics/The Nine Variations focuses on the need for flexibility in your responses. It explains how to respond to shifting circumstances successfully.
This is an issue that game AI has not dealt with well in the past. If you managed to disrupt a build order for an RTS opponent, for example, it might get confused. Also AI was not always terribly adaptive to changing circumstances. To put it in simple rock-paper-scissors terms, if you kept playing rock over and over, the AI wouldn’t catch on and play paper exclusively. In fact, it might still occasionally play scissors despite the guaranteed loss to your rock.
Lately, however, game AI has been far more adaptive to situations. The use of planners, behavior trees, and robust rule-based systems, for example, has allowed for far more flexibility than the more brittle FSMs allowed for. It is much harder to paint an AI into a corner from which it doesn’t know how to extricate itself. (Often, with the FSM architecture, the AI wouldn’t even realize it was painted into a corner at all and continue on blissfully unaware.)
The Army on the March/Moving The Force describes the different situations inf them.
[editorial comment on the above bullet point: WTF?]
I’m not sure to what the above refers, but there has been a long history of movement-based algorithms. Whether it be solo pathfinding, group movement, group formations, or local steering rules, this is an area that is constantly being polished.
The Attack by Fire/Fiery Attack explains the use of weapons generally and the use of the environment as a weapon specifically. It examines the five targets for attack, the five types of environmental attack, and the appropriate responses to such attack.
For all intents and purposes, fire was the only “special attack” that they had in 600 BC. It was their BFG, I suppose. Extrapolated out, this is merely a way of describing when and how to go beyond the typical melee and missile attacks. While not perfect, actions like spell-casting decisions in an RPG are not terribly complicated to make. Also, by tagging environmental objects, we can allow the AI to reason about their uses. One excellent example is how the agents in F.E.A.R. would toss over a couch to create a cover point. That’s using the environment to your advantage through a special (not typical) action.
The Use of Spies/The Use of Intelligence focuses on the importance of developing good information sources, specifically the five types of sources and how to manage them.
The interesting point here is that, given that our AI already has the game world at its e-fingertips, we haven’t had to accurately simulate the gathering of intelligence information. That has changed in recent years as the technology has allowed us to burn more resources on the problem. We now regularly simulate the AI piercing the Fog of War through scouts, etc. It is only a matter of time and tech before we get even more detailed in this area. Additionally, we will soon be able to model the AI’s belief of what we, the player, know of its disposition. This allows for intentional misdirection and subterfuge on the part of the AI. Now that will be fun!
Claiming to use Sun Tzu’s “Art of War” makes for good “back of the box” reading…
Anyway, the point of all of this is that, while claiming to use Sun Tzu’s “Art of War” makes for good “back of the box” reading, much of what he wrote of we as game AI programmers do already. Is there merit in reading his work to garner a new appreciation of how to think? Sure. Is it the miraculous godsend that it seems to be? Not likely.
In the mean time, marketing fluff aside, I look forward to seeing how it all plays out (so to speak) in the latest Total War installment. (Looks like I might get a peek at E3 next week anyway.)
Back in November, there was a get-together of Boston Post Mortem (billed as “games and grog, once a month”) that had a panel of local AI folks. The panelist’s names are familiar to many of us… DamiÃ¡n Isla, Jeff Orkin, and John Abercrombie. It was moderated by Christian Baekkelund whom I had the opportunity to have dinner with in Phily when I was in town for the GameX Industry Summit. Thankfully, this panel was recorded by Darius Kazemi and posted on his Vimeo site and on the Boston Post Mortem page. I embed it here for simplicity’s sake.
The first question to the panel was “what do new AI developers do wrong” or something to that effect. DamiÃ¡n set up the idea of two competing mentalities… gameplay vs. realistic behavior. He and John both supported the notion that the game is key and that creating a system just for the sake of creating it can range anywhere from waste of time to downright wrong.
…create autonomous characters and then let the designers create worlds…
The thing that caught me was Jeff’s response, though (5:48). His comment was that AI teams can’t force designers to be programmers through scripts, etc. That’s not their strength and not their job. While that’s all well and good, it was his next comment that got me cheering. He posited that it is the AI programmers job to create autonomous characters and then let the designers create worlds that let the characters do their thing in.
Obviously, it isn’t a one way street there… the designers job isn’t to show off the AI. However, I like the idea of the designers not having to worry about implementing behavior at all — just asking for it from the AI programmer and putting the result into their world. John’s echo was that it’s nice to build autonomous characters but with overrides for the designers. It isn’t totally autonomous or totally scripted. This sounds like what he told me in his Bioshock experience when I talked to him about it a few years ago.
I happen to agree that the focus needs to be on autonomy first and then specific game cases later. The reason for this is too often the part of the AI that looks “dumb” or “wrong” is when the AI isn’t being told to do anything specific. For example, how often would you see a monster or soldier just standing there? Some of the great breakthroughs in this were from places like Crytek in Far Cry, Crysis, etc. The idea of purposeful-looking idle behaviors was a great boon to believable AI.
The other advantage to creating autonomy first was really fleshed out by Jeff Orkin’s work on F.E.A.R. (Post-Play’em) No more do designers (or even AI programmers) have to worry about telling an agent exactly what it should do in a situation. By creating an autonomous character, you can simply drop them in a situation and let them figure it out on their own. This can be done with a planner like Jeff did, a utility-based reasoner, or even a very detailed behavior tree. Like John said above, all you need to remember is to provide the override hooks in the system so that a designer can break an AI out of its autonomy and specifically say “do this” as an exception rather than hand-specifying each and every action.
What’s in Our Way?
The next question was about “the biggest obstacle” for game AI moving forward. Jeff’s first answer was about authoring tools. This has been rehashed many times over. John expressed his frustration at having to start from scratch all the time (and his jealousy that DamiÃ¡n didn’t have to between Halo 2 and 3).
…to get your AI reviewed well, you need to invest in great animators.
DamiÃ¡n’s comment was amusing, however. He suggested that to get your AI reviewed well and have players say “that was good AI”, you need to invest in great animators. This somewhat reflects my comment in the 2009 AI Summit where I pointed out that AI programmers are in the middle of a pipeline with knowledge representation on one side and animation on the other. It doesn’t do any good to be able to generate 300 subtle behaviors if the art staff can only represent 30 of them.
On the other hand, he reiterated what the other guys said about authoring tools and not having to re-invent the wheel. He supports middleware for the basic tasks like A*, navmesh generation, etc. If we don’t have to spend time duplicating the simple tasks over and over, we can do far more innovation with what we have.
That’s similar to my thought process when I wrote my book, “Behavioral Mathematics for Game AI“. You won’t see a description of FSMs, A*, or most of the other common AI fare in the book. How many times has that been done already? What I wanted to focus on was how we can make AI work better through things other authors haven’t necessarily covered yet. (Ironically, it was Jeff Orkin who told me “I don’t think anyone has written a book like that. Many people need to read a book about that. Heck… I’d read a book about that!” — Thanks Jeff!)
What Makes the Shooter Shot?
The next question (11:45) was about what FPS-specific stuff they have to deal with.
When Halo 3 came out, they could afford fewer raycasts than Halo 2.
DamiÃ¡n talked about how their challenge was still perception models. They really tried to do very accurate stuff with that in Halo. He pointed out that raycasting is still the “bane” of his existence because it is so expensive still. Despite the processors being faster, geometry is far more complex. Alarming note: When Halo 3 came out, they could actually afford fewer raycasts than on Halo 2. Now that sucks! Incidentally, the struggle for efficiency in this area very much relates to DamiÃ¡n’s “blackboard” interview that I wrote about last week.
Interestingly, Jeff argued the point and suggested that cheating is perfectly OK if it supports the drama of the game. I found this to possibly be in conflict with his approach to making characters autonomous rather than scripted. Autonomy is on the “realistic” end of the spectrum and “scripted” on the other. The same can be said for realistic LOS checks compared to triggered events where the enemy automatically detects the player regardless.
John split the difference with the profound statement, “as long as the player doesn’t think you’re cheating, it’s totally OK.” Brilliant.
AI as the Focus or as a Focusing Tool
Supporting the overall design of how the game is to be experienced is just as important as the naked math and logic.
In response to a question about what DamiÃ¡n meant about “AI as a game mechanic,” he offered an interesting summation. He said that, from a design standpoint, the AI deciding when to take cover and when to charge is as important as how much a bullet took off your vitality. That is, supporting the overall design of how the game is to be experienced is just as important as the naked math and logic.
He also pointed out that the design of a game character often started out with discussions and examples of how that AI would react to situations. “The player walks into a room and does x and the enemy will do y.” Through those conversations, the “feel” of a type of character would be created and, hopefully, that is what the player’s experience of that type of character would end up being.
In my opinion, a lot of this is accomplished by being able to not only craft behaviors that are specific to a type of enemy (the easy way of differentiation) but also parameterizing personality into those agents so that they pick from common behaviors in different ways. That is, something that all enemies may do at some point or another but different types of enemies do at different times and with different sets of inputs. I went into this idea quite a bit in my lecture from the 2009 AI Summit (Breaking the Cookie-Cutter: Modeling Individual Personality, Mood, and Emotion in Characters) where I talked about incorporating personality into game agents.
The Golden Rules of AI (20:30)
Christian started things off by citing the adage, “it’s more important to not look stupid than to look smart.” No big surprise there.
The player feels good about killing someone if the kill is challenging.
John said that the AI must be “entertaining”. My only problem with this is that different people find different things entertaining. It’s kinda vague. Better to say that the AI must support the design. Both John and Jeff extended this idea by talking about providing a challenge… the player feels good about killing someone if the kill is challenging.
DamiÃ¡n sucked up to my buddy Kevin Dill a little bit my citing a quote that he made in our joint lecture at the GameX Industry Summit, The Art of Game AI: Sculpting Behavior with Data, Formulas, and Finesse. Kevin said that AI programmers must be an observer of life. I certainly agree with this notion… in fact, for years, my little tag at the end of my industry bios has said, “[Dave] continues to further his education by attending the University of Life. He has no plans to graduate any time soon.” In fact, Chapter 2 of my book is titled “Observing the World”… and Kevin was my tech editor. It should be intuitively obvious, even to the most casual observer, that Kevin stole that idea from me! DamiÃ¡n should have cited me in front of a bunch of game developers! So there!
Anyway, DamiÃ¡n’s point was not only how Kevin and I meant it — observing how people and animals do their thing, but also in being a very detailed and critical observer of your AI. There must be a discipline that scrubs out any little hiccup of animation or behavior before they pile up into a disjointed mess of little hiccups.
Jeff agreed to some extend but related something interesting from the development of F.E.A.R. — he said that most development schedules start by laying out the behavior for each type of character and then, if there is time, you go back and maybe try to get them to work together or with the environment, etc. With F.E.A.R., they started from the beginning with trying to work on the coordinated behaviors. With all the shouting and chaos going on with these guys working against you, you don’t notice the little glitches of the individuals quite as much.
DamiÃ¡n backtracked and qualified his comments… not just hunting down everything that is wrong… but rather everything that is wrong that matters.
Look but Don’t Touch
If you are fighting for your life, you don’t notice the details as much.
John brought up an interesting helpful hint. He talked about how, by turning on God mode (invulnerability), you can dispense with the fight for survival and really concentrate on how the AI is behaving. If you are fighting for your life, you don’t notice the details as much.
I have to agree. That’s why when I go to places like E3, I would rather stand back and watch other people play so I can observe what’s going on with the AI. (I always fear that demo people at E3 are going to be put off by my refusal to join in.) This is one of the problems I have when I’m playing for my Post-Play’em articles. I get so caught up in playing that I don’t look for things anymore. One solution is to have a house full of teenagers… that gives you ample time to just sit and watch someone else play games. I recommend it to anyone. (I believe John and DamiÃ¡n have started their respective processes of having teenagers… eventually.)
Emergence… for Good or Evil
If the AI can have the freedom to accidentally do something cool and fun, it also has the freedom to do something dumb or uninteresting.
In response to a question asking if AI has ever done anything unexpected, DamiÃ¡n spoke about how the sacred quest of emergence isn’t always a good thing. He said that emergent behavior must fall out of the AI having the freedom to do things. If the AI can have the freedom to accidentally do something cool and fun, it also has the freedom to do something dumb or uninteresting. Because of that, emergence has a really high cost in that it can be more of a drag on gameplay than the occasional gem it might produce.
Christian qualified the question a little more by asking if there was a time when the emergent behavior was found well before ship and the team thought it was something to encourage. He cited examples from his own experience. John talked about emergent gameplay that resulted from simple rules-based behavior in Bioshock. You could set a guy on fire, he would run to water, then you could shock the water and kill him. Was it necessary? No. Was it fun for the player to be creative this way? Sure.
To Learn or Not to Learn?
One question that was asked was about using machine learning algos. Christian started off with a gem about how you can do a lot of learning just by keeping track of some stats and not resorting to the “fancier stuff.” For example, keeping track of pitches the player throws in a baseball game doesn’t need a neural network. He then offered that machine learning can, indeed, be used for nifty things like gesture recognition.
Oh… are you using neural networks?
Jeff admitted that he hates the question that comes up when people find out he does AI in games. They often ask him, “Oh… are you using neural networks?” I think this really hits home with a lot of game AI folks. Unfortunately, even a cursory examination of the AI forums at places like GameDev.net will show that people still are in love with neural networks. (My quip is that it is because The Terminator claims to be one so it’s real sexy.) Thankfully, the AIGameDev forum is a little more sane about them although they do come up from time to time. Anyway, Jeff said he has never used them — and that he’s not even sure he understands them. While he thinks that NNs that are used in-game like in Creatures or Black & White are cool, they are more gimicky and not as useful with the ever-increasing possibility space in today’s games.
I Have a Plan
It is hard to accommodate the ever-changing goals of the human players.
Jeff acknowledged that the planner revolution that he started has graduated to hierarchical planners to do more complex things like squad interaction. However, one big caveat that he identified was when you incorporate humans into the mix alongside the squad. It is hard to accommodate the ever-changing goals of the human players.
This, of course, brought us back to the idea of conveying intent — one of the nasty little problem spaces of game AI. DamiÃ¡n explained it as a function of interpretation rather than simply one of planning. I agree that this is going to be a major issue for a long time until we can crack the communication barrier such as voice recognition and natural language processing. Until we can tell our AI squad-mates the same thing we can tell our human squad-mates and expect a similar level of understanding, we are possibly at an impasse.
Moving Forward by Standing Still
As the worlds become more complicated, we have to do so much more work just to do the same thing we did before.
Someone asked the panel what sort of things that they would like to see out of smaller, indie developers that might not be able to be made by the bigger teams. To set the stage, DamiÃ¡n responded with a Doug Church quote from the first AIIDE conference. Doug said that we have to “move forward by standing still.” As the worlds become more complicated, we have to do so much more work just to do the same thing we did before. (See DamiÃ¡n’s note about the LOS checks in Halo 2 and 3 above.) DamiÃ¡n suggested that the indie space has more opportunities to move forward with this because they aren’t expected to do massive worlds. Instead, they can focus on doing AI-based games.
This is what Matt Shaer’s interview with me in Kill Screen magazine was going after. With my Airline Traffic Manager as one of his examples, he spoke specifically about how it is the smaller, dedicated developer who is going after the deeper gameplay rather than the bigger world. I hope this is the case. We have seen a few examples so far… there are likely more to come.
Someone mentioned seeing a demo of improved LOS checks by using the GPU and asked if AI programmers should be pushing that more. John somewhat wittily suggested that AI programmers won’t be using the graphics chips until someone can find a system where a graphics chip isn’t being used at all. DamiÃ¡n was a little more direct in saying that the last people he wanted to work in conjunction with was the graphics programmers. This reminds me of a column I wrote on AIGameDev a few years back, Thou Shalt Not Covet Thy Neighbor’s Silicon. The graphics guys finally got “their space.” They aren’t letting us have any of it any time soon!
DamiÃ¡n pointed out that most advanced AI needs a lot of memory and access to the game state, etc. Those are things that the GPU isn’t really good at. About the only thing that you could do without those things is perhaps flocking. I agree that there really isn’t a lot we can do with the GPU. He did concede that if ATI wanted to do a raycasting chip (rather than borrowing time from the hated graphics guys) , that would be beautiful… but that’s about it.
Director as Designer?
Someone asked about the possibility of seeing the technology that was behind Left 4 Dead’s “AI Director” being used as a sort of game designer, instead. DamiÃ¡n pointed out that the idea of a “meta-AI” has been around for years in academic AI and that it is now really starting to get traction in the game world. I agree that the customized gameplay experience is a major turning point. I really like the idea of this as it really comes down to a lot of underlying simulation engine stuff. That’s my wheelhouse, really.
Where to Now?
They closed with some commentary on the future of game AI which I will leave to you to listen to. Suffice to say that for years, everyone has been expecting more than we have delivered. I’m not sure that is because we are slacking off of because they have vastly underestimated what we have to do as AI designers and programmers. At least, with all the attention that is being brought to it through the Game AI Conference that AIGameDev puts on, the AI Summit now being a regular feature at GDC, and other such events, we are going to be moving forward at some speed.
I was looking at my daily barrage of Google alerts on “game AI” (which tend to contain an annoying number of links to stories about Alan Iverson) and this article blurb from the Bitbag happened to catch my eye. It’s a preview of Halo Reach and seems to be a fairly thorough treatment. They talk about a lot of the different gameplay elements and how they differ from prior games in the franchise. They go into great detail about a lot of things. There was only a little bit of info about the AI, however. It said:
Bungie wants this game to feel a lot like Combat Evolved. They want Reach to be filled with open environments filled with enemies and allow you to figure out how you want to deal with the situation. There will be corridor battles like what weâve seen in past Halos, but that will be balanced with the terrain of Reach. Reach will have a full weather system as well as Bungie saying they will have â40 AI and 20 vehiclesâ on screen at a time.
I thought that was kind of interesting simply because my first reaction was “is that all?” After a moment’s reflection, I realized that the number of AI on the screen in prior Halo games – and even in other shooters – is usually along the lines of a dozen… not 2 score.
On the other hand, it a game like Assassin’s Creed (my Post-Play’em observations), there were plenty of AI on-screen. However, the majority of them were just the citizens who, for the most part, weren’t doing much beyond animation and local steering (until you engaged them for some reason). The question about Bungie’s promise above, then, is how much level of detail scaling will there be with those 40 on-screen AI characters?
Typical LOD scaling has a tiered system such as:
Directly engaged with the player
On-screen but not engaged
Off-screen but nearby
On-screen but distant
Off-screen and distant
Each of those levels (in order of decreasing AI processing demand) has a list of things that it must pay attention to or a different timer for how long to wait between updates. How much of this is Bungie tapping into with Reach, or all they all running at the same LOD?
I know that the AI guys at Bungie are pretty sharp and go out of their way to pull of nifty stuff. In fact, ex-Bungie AI lead, DamiÃ¡n Isla just did an interview with AIGameDev on blackboard architectures (my writeup) where he explained how a lot of the Halo 2 and 3 AI was streamlined to allow for better processing of many characters. I’m quite sure that much of that architecture survives in Halo Reach.
Anyway, I just thought it was interesting to see the promised numbers. It will be even more interesting to see how the marketing blurb actually plays out on the screen in the final product.
In preparation for the GDC AI Summit (and the inevitable stream of dinner conversations that will be associated with GDC), I have tried to catch up on playing some games and also getting current with papers and interviews. On the later point, Alex Champandard at AIGameDev keeps me hopping. It seems he is almost constantly interviewing industry people on the latest and greatest stuff that is happening in the game AI realm.
A few weeks back, he interviewed DamiÃ¡n Isla about blackboard architectures and knowledge representation. Seeing as I always learn something from DamiÃ¡n, I figured that interview needed to go to the top of the list. Here’s some of my notes as I listen through the interview.
Make it Bigger
DamiÃ¡n’s first point to Alex was that a major benefit of a blackboard architecture was scalability. That is, putting together a rule-based system that performs a single decision is simple… the hard part is when you have 10,000 of those rules going on at the same time.
In a similar vein, he said it was about shared computation. Many of the decisions that are made are used with the same information. Blackboards, to Damian, are an architectural feature that can decouple information gathering and storage from the decisions that are made with that information. If one part of a decision needs to know about a computed value regarding a target, that information could potentially be used by another portion of the decision engine entirely… even for a competing action. By calculating the requisite information once and storing it, the decision algorithms themselves can simply look up what they need.
This is similar to the approach that I espouse in my book. I don’t directly say it, but in a way it is implied. With my approach of compartmentalizing tiers of calculations, many of the individual layers of information that needs to be processed are done so independently of the final decision. The information needs only be collected and tabulated one time, however. The various decision models can simply look up what they need. In a multi-agent system, different agents can use much of the same information as well. While distance to a target may be personal, the threat level of a target (based on weaponry, health, cover, etc.) may be the same for all the enemies. That threat level can be calculated once and saved for everyone to use.
Back to DamiÃ¡n…
He mentioned that at the Media Lab at MIT they used blackboards for many things like logging, testing, and debugging. That is something I haven’t necessarily thought of. They also had observer systems running over a network. They shared parts of the blackboard info so that the fully running games were doing everything but thinking.
Alex reiterated that a blackboard is more of an architectural feature rather than a decision process. DamiÃ¡n confirmed that the history of blackboards involved planners but that we are now using them inside reactive systems as well.
Blackboards vs. Lots of Static Variables
At Alex’s prompting, DamiÃ¡n suggested that the blackboard is far more dynamic than having just many billions of values specified in a character.h file. In fact, he likened it much more to having one unified interface to all of your game data beyond just that of the character in question.
Do all agents need their own unique blackboard?
I like the fact that DamiÃ¡n’s initial answer was a refrain that I repeated throughout my book… “it totally depends on the game you’re making.” Unfortunately, that is a major stumbling block to answering any architectural or procedural question.
He went on to say something similar to what I mention above… that you have to mix them. There are some pieces of information that individuals track and others that are available to the group as a whole. Visibility of targets, for example, is individual. Goals for a squad, on the other hand, is something that can be shared and referenced.
Direct Query vs. Blackboard?
The most important point DamiÃ¡n made here had to do with “redundancy”. If you have a situation that you can guarantee you only need something once, then accessing it directly from a behavior is fine. If multiple behaviors might use the same data, access it once and store it on the blackboard.
The answer to avoiding the redundancy issue was “abstraction”. That’s what a blackboard represents. It gives that intermediate layer of aggregation and storage. He actually referred to it as “sub-contracting” the information gathering out to the blackboard system. The difference is that the blackboard isn’t simply passing on the request for information, it is actually storing the information as a data cache so that it doesn’t need to be re-accessed.
One very important point that he made was that there was some intelligence to the blackboard in deciding how often to ask for updates from the world. This is a huge advantage in that the process of information gathering for decisions can be one of the major bottlenecks in the AI process. LOS checks, for example, are horribly time-consuming. If your system must ask for all the LOS checks and other information every time a BT is run (or multiple times in the same BT), there can be a significant drain on the system. However, if you are able to time-slice the information gathering in the background, the only thing the BT needs to do as access what is on the blackboard at that moment.
Incidentally, this is a wonderful way of implementing threading in your games. If your information gathering can continue on its own timeline and the behaviors need only grab the information that is current on the blackboard, those two processes can be on separate threads with only the occasional lock as the blackboard is being updated with new info.
This goes back to my interview with Alex about a year ago where he asked about the scalability of the techniques I write about in my book. My point was that you don’t have to access all the information every time. By separating the two processes out with this abstraction layer as the hand-off point, it keeps the actual decision system from getting bogged down.
In order to also help facilitate this, DamiÃ¡n spoke of the way that the information gathering can be prioritized. Using LOS checks as his example, he talked about how the Halo engine would update LOS checks on active, armed, enemies every 2 or 3 frames, but update LOS checks on “interesting but not urgent” things like dead bodies every 50 frames. Sure, it is nice for the AI to react to coming around a corner and seeing the body, but we don’t need to constantly check for it.
Compare this to a BT where a node “react to dead body” would be checked along with everything else or (with a different design) only after all combat has ceased and the BT falls through the combat nodes to the “react…” one. At that point, the BT is deciding how often to check simply by its design. In the blackboard architecture, the blackboard handles the updates on what the agent knows and the BT handles if and how it reacts to the information.
Chicken or Egg?
DamiÃ¡n talked about how the KR module and the decision module does, indeed, need to be built in concert since information and decisions are mutually dependent. However, he talked about how the iterative process is inherently a “needs-based” design. That is, he only would write the KR modules necessary to feed the decisions that you are going to be using the information for. This is, of course, iterative design at its very core (and how I have always preferred to work anyway). While you might first identify a decision that needs to be coded, you need to then put much of that on hold until you have put together all of the KR implementation that will feed the decision. If you then add future decision processes that use that same blackboard, more power to you. (None of this trumps the idea that you need to plan ahead so that you don’t end up with a mish-mash of stuff.)
As mentioned before, what you put into the KR blackboard is very dependent on the game design. It goes beyond just what knowledge you are storing, however. DamiÃ¡n specifically mentioned that he tries to put as much “smarts” into the KR level as possible. This has the effect of lifting that burden from the decision process, of course.
Are There Exceptions?
Alex asked the question if there would be cases that a behavior engine (such as the BT) would directly access something in the game data rather than looking it up in the KR/blackboard level. DamiÃ¡n cautioned that while you could make the case for doing that occasionally, you would really have to have a good reason to do so. Alex’s example was LOS checks which, unfortunately, is also the wrong time to step outside of the blackboard since LOS checks are such a bottleneck. DamiÃ¡n’s emphasis was that these sorts of exceptions step outside the “smarts” of the KR system… in this case how the KR was spreading out the LOS checks to avoid spikes.
Another example was pathfinding. He said a developer might be tempted to write a behavior that kicks off its own pathfind routine. That’s generally a bad idea for the same bottleneck reasons.
More than Information
I really liked DamiÃ¡n’s exposition on one example of how Halo used more than simple LOS checks. He explained the concept of “visibility” as defined in Halo where the algorithm that fed the blackboard took into account ideas such as distance, the agent’s perceptual abilities, the amount of fog in the space at any time. This was so much more than a LOS check. All the behaviors in the BT then could use “visibility” as a decision-making criteria. I haven’t seen a copy of the Halo 3 BT, but I can imagine that there were many different nodes that used visibility as an input. It sure is nice to do all of this (including the expensive LOS checks) one time per n frames and simply store it for later use as needed. Again, this is very similar to what I espouse in my book and in utility-based reasoners in general.
Dividing up the KR
He described something interesting about how you could have a manager that assigns how many LOS checks each AI gets and then, once the AI knows how many it will get, the AI then prioritizes its potential uses and divvies them up according to its own needs. Rather than having one manager get requests of priorities from all the AIs at once, the first cut would be to simply give each of them a few (which could also involve some interesting prioritization) and then let them decide what to do with the ones they get. I thought that was a very novel way of doing things.
What Does it Look Like?
In response to a question about what does the blackboard data structure look like, DamiÃ¡n acknowledged that people think about blackboards in two different ways. One is just based on a place to scribble shared data of some sort. The other, more formal notion is based on the idea of key/value pairs. He prefers this method because you can do easy logging, etc. For more high-performance stuff (e.g. FPS) there really isn’t much of a need for key/value pairs so there may be more efficient methods such as looking up the information in a struct.
He went on to point out that the size and speed trade-off is likely one of the more important considerations. If an agent at any one time may only care about 5-10 pieces of data, why set aside a whole 500-item struct in memory? Also, key/value pairs and hash tables can’t necessarily be more expressive than a hard-coded struct. I would tend to agree with this. So much of what the data says is in what it is associated with (i.e. the other elements of the struct) and the code around it.
In Halo, they were on the hard-coded side of things because there wasn’t too much data that they needed to store and access. In general, the KR of what you need to access will tend to stabilize long before the behavior.
He also explained the typical genesis of a new KR routine. Often, it happens though refactoring after you find yourself using a particular algorithm in many locations. If this happens, it can often be abstracted into the KR layer. This is the same thing I have found in my own work.
One caveat he added was extending key/value pairs with a confidence rating in case you wanted to do more probabilistic computations. You could iterate over the information, for example, and apply decay rates. Of course, you could also do that in a hard-coded struct. I was thinking this before he said it. To me, adding the manager to deal with the semantics of key/value/confidence sets might introduce more trouble than it is worth. Why not put together a vector of structs that process the same information? To me, this goes to a point of how you can divide your KR into smaller, specifically-functional chunks.
An interesting question led to something that I feel more at home with. Someone asked about blackboards collecting the info, processing some info, and writing that info back to the blackboard to be read by the agent and/or other blackboard processors. DamiÃ¡n agreed that a modular system where multiple small reasoners could certainly be touching the same data store… not only from a read standpoint, but a write one as well. This is very intuitive to me and, in a way, is some of the things that I am doing in Airline Traffic Manager (sorry, no details at this time).
DamiÃ¡n confessed that his search demo from the 2009 AI Summit did exactly this. The process that updated the occupancy map was a module hanging off the blackboard. The blackboard itself was solely concerned with grabbing the data of what was seen and unseen. The reasoner processed this data and wrote it back to the blackboard in the form of the probabilistic mapping on those areas. The agent, of course, looked at that mapping and selected it’s next search location accordingly. (BTW, influence mapping of all kinds is a great use for this method of updating information.)
DamiÃ¡n summed up that the overall goal of the blackboard (and, in my opinion KR in general) is that of “meta-representation”. Not that data exists but what that data really means. What it means is entirely dependent on context. The blackboard simply stores these representations in a contextually significant way so that they can be accessed by agents and tools that need to use and respond to that information.
What This Means to Me
I really find this approach important – and am startled that I started using many of these concepts on my own without knowing what they were. One of the reasons that I very much support this work, however, is because it is key to something that I have unwittingly become a part of.
Utility-based architectures describe a whole decision making system that chooses actions based on individual floating-point numbers that indicate value. (At least that’s as close to an official definition I can come up with.) Utility in itself isn’t new, and you’ll no doubt remember using it as a voting or scoring system for specific problems like threat selection, target selection, etc. What’s new in 2009 for is:
1. There’s now an agreed-upon name for this architecture: utility-based, which is much more reflective of how it works. Previous names, such as “Goal-Based Architectures” that Kevin Dill used were particularly overloaded already.
2. A group of developers advocate building entire architectures around utility, and not only sprinkling these old-school scoring-systems around your AI as you need them.
The second point is probably the most controversial. That said, there are entire middleware engines, such as motivational graphs which have been effective in military training programs, and Spir.Ops’ drive-based engine applied in other virtual simulations. The discussion about applicability to games is worth another article in itself, and the debate will certainly continue into 2010!
It’s obvious to many people that I am one of the members of that “group of developers” who “advocate building entire architectures around utility”. After all, my book dealt significantly with utility modeling. I am also playing the role of the “utility zealot” in a panel at the 2010 GDC AI Summit specifically geared toward helping people decide what architecture is the best for any given job.
While utility modeling has been often used as a way of helping to sculpt and prioritize decisions in other architectures such as FSMs, BTs, or the edge weights in planners, many people (like Alex) are skeptical of building entire reasoner-based architectures out of them. What Damian explained in this interview is a major part of this solution. Much of the utility-based processing can be done in the KR/blackboard level — even through mutli-threading — to lighten the load on the decision structure. As more of the reasoning gets moved into the KR by simply prepping the numbers (such as how “visibility” represented a combination of factors), less has to happen as part of the decision structure itself.
Kevin Dill and I will be speaking more about this in our lecture at the AI Summit, Improving AI Decision Modeling Through Utility Theory. I hope to be writing more about it in the future as well. After all, according to Alex, it is one of the emerging trends of 2010!
Damian Isla of Bungie spoke at the recent Develop conference in the UK. He covered a lot of the history of Halo and some of the design decisions that were made in the franchise. Here’s a story from Gamasutra that covers a lot of good stuff.
Specifically, there’s a couple of things I want to touch on.
Halo’s designers wanted the title’s gameplay to explore mankind’s “primal games” such as hide and seek, tag, and king of the hill, and the game’s encounters were created with them in mind.
“It’s evolution that taught us these primal games,” said Isla. “They’re the ones that are played with our reptilian brains. The idea was for the AI [to] play them back with you.”
That’s kind of interesting from a design standpoint. I guarantee that no one is sitting there thinking “hey, this is like King of the Hill” but they all recognize the concept on a subconcious level.
Isla pointed out that the importance of territory in Halo’s encounter design is closely connected to the recharging shield mechanic that has appeared since the original game.
“Part of that recipe demands that at some point you have a safe zone,” he explained. “In a sense we needed to make the AI territorial. Once you have this idea, you have to think about the problem of encounter progression as the player expands their safe zone. That itself is a pretty fun process. It gives the player a sense of progress, and is extremely plannable.
This makes a heckuva lot more sense than the “arena + safe corridor + arena…” model. What Halo did was break it up theoretically rather than physically (i.e. with walls). However, there still was the knowledge that the dudes – while still in their territory – were still going to try to take pot shots at you. You could take cover and they weren’t necessarily going to come get you, but it wasn’t completely safe.
Isla made special mention of AI misperception — “the most interesting form” of good AI mistakes. If the player moves stealthily, the AI will assume the player is still sitting where the AI last knew him to be. [snip] “Each AI has an internal model of each target, and that model can be wrong,” Isla summarized. “This allows the AI to be surprised by you, and this is very fun.”
Amen, brother! This is something that I love seeing. I remember reading some of Damian’s papers in the AI Wisdom series on exactly this concept of unknown location and search. Good stuff, man!
Still, Isla stressed, enemies shouldn’t be dumb. “It’s more fun to kill an enemy that’s cunning, formidable, and tactical,” he said, pointing out that that goal is not just an AI problem but also related to convincing animation and game fiction.
Dude… have I told you I loved you? I’m so sick of the mantra of “AI shouldn’t be smart, it should be fun!” As if those two are mutually exclusive of each other.
“In Halo 2, if an AI tips over his vehicle, he walks off and forgets completely he was ever in one,” said Isla. “In Halo 3, if he tips it, he remains in its vicinity fighting until there is a point where he can right it again.”
According to Isla, the latter approach is “the way things should be going” — as he puts it, “behavior should be a very thin layer on top of a world of concepts.”
I would argue that behavior is more than a thin layer. Otherwise, I agree. Which really brings the concept of knowledge representation to the forefront. Not just world representation (e.g. geometry), but a general concept of how agents perceive and conceptualize things (i.e. psychology). Again, I’ve read some of Damian’s papers on the subject. To me, he is someone who “gets it”.
Got linked to this by Paul Tozour. Here are Damian Isla’s (Bungie) slides from his 2005 AIIDE presentation on “spatial competence” entitled “Dude, where’s my Warthog?” It includes info on a ton of the stuff he/they did in Halo 2. Included is information on pathfinding – especially with regard to how we (as people) process spatial information. It’s nice to see someone else tapping into psychology as a source for potential solutions for game AI.
Damian Isla of Bungie has uploaded his slides from his GDC presentation (which I haven’t written up my commentary on yet). He also discusses the history of the “Objectives” system that they used in Halo 3 on this blog post at Game/AI.
I will be breaking down his presentation in a few days (I’m still trying to get caught up).
I’m in the process of uploading all my GDC-related things to this page. You can actually listen to my audio of the 3 AI roundtables and read my (barely comprehensible) notes that I furiously took during each. Also, it has links to the pictures that I took during the roundtables and the AI Programmers Dinner on Friday night.
On that page, I will also be posting other AI-related tidbits such as my notes from lectures such as those by Soren Johnson’s (Civ 4), Damian Isla (Halo 3), and Peter Molyneux (Fable 2). Give me a few days to get it all straightened out, though.
Also, I sat down with John Abercrombie of 2k-Boston on Sunday morning and spoke with him about the AI that he did for Bioshock. That should be posted on Wednesday. Look for it over on Post-Play’em.
(Remember to tap the RSS feed to keep up with these additions and all other AI-related things.)
One final note about GDC… it’s always an exhilarating week… but it sure does make my head hurt!