Slashdot Mirror
Artificial Intelligence for Computer Games
Funge's background includes both academic AI research and commercial development of game AI technology. This has allowed him to write a refreshingly practical book for the game AI programmer which will also expand the reader's knowledge of AI. He presents advanced AI research in a way that is meaningful to the working game AI programmer. Non-player characters (NPCs) are the focus of this book, although it touches upon techniques applicable to other kinds of AI. Funge begins with a simple NPC architecture, then goes on to consider how they act in their world, perceive and react to their surroundings, remember their past experiences, plan their actions, and learn from the past to improve their future behavior. In addition, Funge hopes his book will contribute to a "common framework and terminology" to promote better communication between practitioners interested in game AI, leading to better interoperability for their software. (Please note that John Funge is a friend and former coworker of mine. I was pleased to accept John's invitation to review his book.)
The field of Artificial Intelligence has been actively studied since the 1950s. In that half century many useful techniques have been developed and applied to a broad range of scholarly and commercial applications -- most quite serious and sometimes a bit dry. In contrast, today the most economically significant application of AI is in computer games. This commercial application motivates today's students to study AI and drives a good deal of academic AI research. Modern games have incredible graphics and their animation technology is becoming very sophisticated. As graphic animation increasingly becomes a solved problem, more and more attention is being paid to game AI. It seems likely that the next few years will see a tremendous investment in game AI technology leading to significant improvements in the state of the art.
As I read Funge's book I was struck by how oriented it was to the interests of AI programmers working on commercial games. Certainly the discussion focused on the practical rather than the theoretical. (There are many asides, footnotes and citations of the academic literature for those with an interest in pursuing the theory.) More concretely, the text is peppered with fragments of C++ code. A working programmer who visits the academic literature is often faced with the daunting task of converting prose, equations or breezy pseudo-code into something suitable for compilation. If a reader of this book does not follow a bit of the discussion, a glance at the nearby C++ code listing will usually set things straight. I have it on good authority that functioning source code for the examples in the book will appear on the www.ai4games.org website "soon."
The book is divided into seven chapters (Introduction, Acting, Perceiving, Reacting, Remembering, Searching, and Learning) plus a Preface, two appendices, an extensive Bibliography and an Index. The chapter on "Acting" introduces the simple game of tag used as an example throughout the book. It further sets the stage by describing the principal components of the game engine and the AI system. The third chapter, "Perceiving," introduces percepts -- the formal framework used to encapsulate and manipulate an NPC's awareness of its world. In many games a key concept is filtering out information which is available in the game state but should not be "known" by the NPC. Chapter 4 describes reactive controllers. Funge uses a very strict definition of reactive -- informally, it means a non-deliberative controller, but in this book the term is used to mean strictly stateless. This distinction has a practical consequence since a stateless controller can be shared among multiple NPCs. (Yet I wondered how important this was in practice. That point was not explored in any depth, and a "slightly stateful" reactive controller can be very useful.) The chapter on "Remembering" introduces memory percepts, mental state, beliefs and communication between NPCs. The sixth chapter covers "Searching" -- through trees of possible future actions, often referred to as planning. The extensive treatment of search includes both examining the host of options that are available to an NPC at each juncture, as well as reasoning about the interaction of one NPC's behavior with another, known as adversarial search. The final chapter covers "Learning." It looks at both offline learning (which happens before the game is shipped) and online learning (happening during gameplay). The first is merely an aid to game development, the latter promises NPC that can adjust to the player's skill and style of play. Online learning present many more technical challenges. In fact, my first impression on reading this section that it was less practical than the rest of the book because of the difficulties of online learning. However, from the description of this GDC 2005 lecture, it appears that Funge and his colleagues have made significant progress in this area.
I recommend Artificial Intelligence for Computer Games: An Introduction to commercial game AI programmers, as well as other game programmers and designers who wish to learn more about this area. Because of its sound academic underpinning, the book will also be of interest to students of artificial intelligence and to professionals in related areas such as agent-based simulation and training.
Reynolds is a Senior Research Scientist in the R&D group of Sony Computer Entertainment America. His interests center on modeling behavior of autonomous characters, particularly steering behaviors for agile life-like motion through their worlds. See his page on Game Research and Technology. You can purchase Artificial Intelligence for Computer Games: An Introduction from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
Because I want those crushbone orcs to think about how I might feel emotionally before they fire some magic lightning at me or club me. Or they can say "Well he's level 65 and I'm level 10, so maybe I will not chase after him today!"
News Reporters Make Tasty Polar Bear Treats!
A few years from now, we will hear : "Let me put it this way, Mr. Amer. The 9000 series is the most reliable computer ever made. No 9000 computer has ever made a mistake or distorted information. We are all, by any practical definition of the words, foolproof and incapable of error." And of course the paper clip will be saying it!
#include bier;
Is the O'Reilly book AI for Game Developers. It has lots of practical examples and ideas with code snippets that build from something a beginner can understand.
Pattern-based is easier to code as well. If you want the enemies to react to the player's abilities, just set up a rank system (like just about every score-based vertical shooter from the past 5-10 years).
Complicated game AI is overrated. If I want an intelligent opponent, I can always just play a friend over LAN or internet.
Such a thing would be great for fighting games. But A good fighting game AI would be rather difficult to simulate high level play because there are so many tiny mind games going on that aren't immedietly apparant. Being random, but being random in a logical, stratigic manner is hard enough for a human to learn to do. Having a computer teach you how to do it would likely be a harder thing to do, but it would be cool and quite possible to have a computer highlight the basics and start players down the path of mastery via AI.
The eternal struggle of good vs. evil begins within one's self.
Yes, I'd like to play against this "insane" AI script. I play SC pretty regularly against the computer (actually, 5-6 of them at once) and tend to win about 75% of the time.
But let's get one thing straight... giving the computer a free "cash flow" is not advanced AI.
I'd prefer it if the AI didn't act so predictably, that's all.
-David
As a simple example, you might play a modern-day RPG, where your character is at a Tennis match with an NPC. You might decide to throw that match, in order to have that NPC put in a good word with your boss. Traditionally, this has been scripted, like this:
In these cases, the designer explicitly considers which actions the player can take, and what their outcomes will be. What I think will happen more in the near future, will be that designers will set rules up, let the players know how their actions have affected the system, and then leave him to "game the game," as it were. The designer of the above scenario might, instead, give the player the chance to "play well" or "play poorly," independent of why the player would want to do that. The player knows the game's state, and therefore has an idea as to what he can do to alter that state.
This takes place to some extent in existing games, such as Deus Ex: IW and, especially, in The Sims 2. In the latter case, for example, a wedding party will go well if the guests are happy. The guests will be happy if their needs are met. Their needs will be met if they have X, Y, and Z. The designers did not implement a direct corrolation between X, Y, and Z and the wedding party; changes in the game's state occur because of the third or fourth-order consequences of a player's actions. In comparison, most interaction in a first-person shooter is first-order: kill the critter to get past the critter. (I love first-person shooters, but judging from the way some Slashdot posts received Doom 3, I think that an FPS that adds complexity in this manner may do well.)
My prediction here isn't a divine revelation that we'll have this newfangled style of "emergent gameplay" -- we already have it. However, I think that, come 2006, we'll have a sexy buzzword for it, and that it'll be sprawled over the covers of CGW and PCG.
_________________________________________________
Inago Rage - Fight, Fly, and Create your own 3D arenas in our first-person shooter
We're indie. We're working on our 14th game.
However, I have still to find the first good book on AI that deals with complex tasks for agent behavior. Many books cover the first few notions that are just abstractions of how we would probably be doing things, but none of them go deeper where the complexity becomes hairy, the lines become fuzzy and the amount of bookkeeping necessary to solve the problem grows exponentionally. I`m talking about dialogue models, strong and week constraint planning engines, emotion simulation, symbolic reasoning, etc.. Each of them separately in it`s simplest form has been described 100s of times, but never has one book touched on the complexity when everything should come together. Not even the commercially available API`s like Ai Implant or Spirops come close.
Well. Maybe that`s not such a bad thing. I can always start writing myself..
With great power comes great electricity bills.
I got pretty good at StarCraft: BroodWar. I could play 2 on 1 against the computer and win nearly every time. Playing three on one was pretty tough. However, a buddy and I could play 2 on 6 with regularity.
It wasn't until the last set of patches, that we couldn't beat several of our favorite maps on 2 on 6. Big Game Hunter was a great map to play, if you did it properly, you could play 2 on 6 as protos, which normally we couldn't do. Playing 2 on 6 on just about any other map was easy if you were patient and played as Terran and the primary base was at all defensible. The last set of patches made the AI very good about early pressure, and often pressure. It also improved it's ability to wave as one huge group, rather then having them with two or three of them in your base at one time. Two or three opponents in your base in the early game is doable. Five or Six was just a complete impossibility for us to deal with.
Especially if the computer wouldn't cheat (just give it extra money, or use skewed stats not available to the player). I don't mind of the computer has "infinite mice", although, anything that simulated the limitation of the number of commands that could be issued would be cool.
The other interesting thing, is that the AI got better with a faster machine. At various points, just upgrading machines without changing the game version would make things more challenging. Finally, on Big Game Hunter we pretty much proved to ourselves that Blizzard wasn't having the AI cheat in terms of picking the proper counter units. The trick to beating Big Game hunter as Protos was to build as many "Carriers" as you could. Put down as many of the Photon cannons as you could. Put down two sets of Upgrade buildings so you can do all of the upgrades in parallel. Defend your main base with proton cannons and other foot troops. When each of you has a dozen fully upgraded carriers, each of you hits a different opponent (Build shield rechargers on the edge of your base towards the side you are going to attack). You should be able to crush your opponent with relative ease. Both teams then pick a third opponent to attack crush them. Then it's just time to clean up. You should have pretty much destroyed everyones forces, go clean up the bases. However, if you used a Carrier to defend your base before you had a dozen of them, the computer would build the perfect counter unit (normally those really cheap small zerg fliers). As long as you hide the carriers in the back of your base, you'd just crush the computer. If not, they had a tendency to build too little anti-air units until it was too late. This basic strategy was figured out while we played it 3 on 5, until everyone got tired of me just essentially doing nothing for the first half of the game while they defended, followed by me beating 4 of the 5 opponents. The last patch we applied (either the 1.09 patch or the one after it if there was one), the computer waved so badly that couldn't keep enough proton cannons on the ground to defend your base.
The other thing I really wish that games makers allowed was the ability to script AI so you could essentially build your own AI scripts, so that the AI was exentisible without writting a DLL.
Kirby
What I didn't like about Half-Life:
"Easy - enemies are weak and stupid"
"Normal - enemies are strong and stupid"
"Hard - enemies are strong and smart"
What I regret, that there wasn't a setting for "enemies are weak and smart".
I hardly enjoy unloading 30 bullets from my clip into hardly moving enemy's head instead of 10. But I vastly more enjoy unloading 30 bullets at the walls around a smart, dodging enemy trying to get it and finally killing with 1-2, than shooting 10 bullets right in head and have it still live.
45 5F E1 04 22 CA 29 C4 93 3F 95 05 2B 79 2A B2
I believe advanced AI techniques like nueral nets will be the next "killer app" for MMOGs. Learning AI is not impractical for a single player stand alone game but it is not as "exciting" nor do single player system have enough computing power and "experience" to really put a nueral net through its paces.
--> Neural nets are less efective than expert systems based on inference rules. Nowdays the most intelligent engines are driven by real-time programmable expert systems, as flexible inference rules (propositional logic) are, by far, a very kind way for giving "near natural" acting-response modeling.
About your whole comment, I think that you want to argumentate a way for self learned tactics, improving the skills for rich acting and surpresive/imprevisible/autodidactic learning. But as in common life, despite how clever/intelligent you can be, you need a "well known model" to reach the optimum (see maths, physics, psicology, etc.), as you can't go too far without a base knowledge, the same way as a child learns how to become an adult.
My bet, non sense as any other, is that expert systems (propositional logic, inference) will continue on the top as new schemes are being added to its basis. Neural nets are, IMO, mostly marketting, as are just function interpolator/extrapolator (despite how complex could be your system), but often retrieved as the Holly Grial of the AI (the same goes for genetic computing... a way to get suboptimum results by being too much lazy for reading Floyd or Dijkstra).
The problem is "simulation of human" vs "solving problems".
Do you aim for immersion or competitiveness, that's the question. Competitiveness is easier than immersion, and in some games bots are just as irritating as human opponents. Do you want behaviour that is plausible for the type of world you are playing in, or behaviour optimized for winning the game. It is impossible to realize both if the game is not balanced to reward behaviour that is logical for the world the game simulates.
If the multiplayer version of the game also feels wrong, there is no amount of AI that is going to solve the problem. Contrary to what many believe, it is not the adolescents you are playing that are the problem, but the mechanics of the game. The AI programmer has an impossible task writing an entertaining AI for a fundamentally flawed world without cheating.
Some simple examples:
- In 'medieval' RTS games like AoE your enemy will never retreat or flee when outnumbered, regardless of whether he is AI or a good human player. In the real world they would. Human live is valued wrongly.
- In many 3D FPS games your enemy will jump up and down like an idiot to dodge bullets. In real life that 1) doesn't work because you can't jump high enough, and 2) you get tired pretty quickly.
- The economy: no game gets the economy right.
Video games are too unbalanced and temporary to invest time in game AI. There is nothing to learn in game AI programming that will generalize to the next project you work on. In chess, which is balanced and has been around for longer than AI, the AI is very competitive.
There are a number of competitive botclients for quake and UT servers, but bots are not generally allowed on servers unfortunately so most players don't know. I have written a specialized bot for a UT mod (unrealspeed, about 9 hours work) in the past, but most UT mods are released without any specialized bots. And even when you implement a dedicated bot, the map suppliers are too lazy to add good path nodes and test them. That just shows how little true interest in bot programming there is. It is less important than correct lighting and shadows.
I will never waste my time on something like this again because a few months later UT2003 changed the API and we decided to stop supporting the mod. To get decent AI, the game must remain the same for at least a few years.
The objective of consumer-focussed game AI is to make it fun for the player. It's actually fairly trivial to make AI that wins all the time (think: cheat.) The hard part is to make an AI that makes it difficult enough for the player to keep them interested without being so easy that it gets boring.
Another good goal is to try and surprise the player. An AI that always behaves in simple stimulus-response is no fun after a while; you learn the patterns. It's much more fun (and much more replayable) if the AI does things you don't expect, and occasionally wins doing them.
What I would like to see is ANY AI for RTS games that neither makes use of, nor loses to, the "make as many units as possible and swarm the opponent" strategy.
The problem with that is that AI is not such a direct thing as rendering graphics. AI implementations vary a lot, and depend a lot on the world's state.
In order to accelerate AI, you'd have to make a chip that would accelerate some very used part of it, and what would that be? Perhaps a chip could accelerate neural networks. The problem is that while every 3D engine ends rendering polygons not every AI is a neural network.
The computer language Prolog is very clever at figuring out solutions from complex data. It can learn new rules and information and include those in its solutions.
Has it even been used for game AI? If not, why not? If so, how did that go?