Artificial Intelligence for Computer Games

Craig Reynolds writes "In his recent book Artificial Intelligence for Computer Games: An Introduction , author John Funge takes us on a whirlwind tour of techniques from the literature of academic AI research and discusses their application to the nuts and bolts of game AI programming. While some of these topics are quite advanced, the text remains easily readable and grounded in what the techniques mean to real game programmers developing real game AI." Read on for Reynolds' review. Artificial Intelligence for Computer Games: An Introduction author John David Funge pages 160 publisher A K Peters rating 8 reviewer Craig Reynolds ISBN 1568812086 summary Written for game AI programmers, this book provides a practical introduction to advanced AI techniques and practices for constructing sophisticated non-player characters.

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.

Comments

Microsoft's PaperClip is the pinnacle...

[bigtallmofo]

As far as I'm concerned, the state of artificial intelligence could advance no more after the development of Microsoft Office's PaperClip helper.

That bendy little guy always knows exactly what I'm trying to do and provides timely, topical help on the subject. I mean, every time I type:

Dear :

That little artificial lifeform knows I'm getting ready to type a letter and offers to give me a hand. What a wondrous age we live in.

No thanks.

[Mononoke]

I've already been eaten by the Grue. I'd rather he not be smart enough to invite his friends to watch, point, and laugh the next time.

Better AI is a must

[Evil W1zard]

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!"

What I need...

[It doesn't come easy]

What I need is a game with AI that can evaluate my game play and tell me how to play better against my opponents, kind of like where you view your opposing team's old games to learn their patterns and weaknesses, only give me feedback in real time while I'm playing.

Re:starcraft yay

[nine-times]

Well, in a certain sense, "good" AI for games doesn't necessarily mean "harder to beat". Take a fighting game like Tekken as an example. Technically, you could just program the AI opponent to block every time you press the "attack" button, and to attack whenever you can't block. Suddenly you have "unbeatable AI", but it's not really *good* AI.

And I don't just mean "it's not technically impressive". I mean, considering the purpose of in-game AI, it's *bad* AI. Good AI generally simulates more complicated human interactions. Good AI can be tricked or distracted, and can learn so it's not so easily tricked the next time. I really like the idea of AI that will adjust to the player's skill level to always provide gameplay that is exciting and challenging, yet beatable.

In other words, I believe "good" AI in a game is not defined by being hard to beat, but by being fun to play against.

Neverwinter Nights AI Communities

[Pausanias]

Some of you might be aware that the PC/Mac/Linux Game Neverwinter Nights includes a toolset with a C-like scripting language that allows users to code the behavior of characters in a game---not just for combat, but generic interactions as well.

BioWare, the developers of the game, are known for the imaginative story lines in their Star Wars: Knights of the Old Republic and Baldur's Gate series. However, by their own admission, they never have as much time as they want to work on creature AI. In Neverwinter Nights, this shortage of time resulted in a number of unfortunate situations during game play. For example, friendly characters would waste powerful spells on pitifully weak enemies; or they would continually attempt to cast spells in close hand-to-hand combat, not realizing that this gives the close-by enemy countless opportunities to tear them into pieces, and that pulling out that dagger in their backpack might be a better idea. Especially sad were near-death enemies who would try to heal themselves with woefully inadequate healing spells (in RPG talk, down 80 hit points and casting cure minor wounds).

Luckily, the toolset allowed a number of us to code improvements to NPC behavior. I was one of them, starting the Henchman Inventory and Battle AI project, now lead by Tony K. The focus of our project was immediate improvement of game play. An even more impressive community is the Memetic AI group. These folks are putting together a full package of complex behaviors for an entire world, from peasant farmers to fearsome dragons. Impressive stuff.