Intelligent Agents in Computer Games
Michael van Lent, John Laird, Josh Buckman, Joe Hartford, Steve Houchard, Kurt Steinkraus, Russ Tedrake
Artificial Intelligence Lab University of Michigan 1101 Beal Ave. Ann Arbor, MI 48109 vanlent@umich.edu
As computer games become more complex and consumers demand more sophisticated computer controlled opponents, game developers are required to place a greater emphasis on the artificial intelligence aspects of their games. Our experience developing intelligent air combat agents for DARPA (Laird and Jones 1998, Jones at al. 1999) has suggested a number of areas of AI research that are applicable to computer games. Research in areas such as intelligent agent architectures, knowledge representation, goal-directed behavior and knowledge reusability are all directly relevant to improving the intelligent agents in computer games. The Soar/Games project (van Lent and Laird 1999) at the University of Michigan Artificial Intelligence Lab has developed an interface between Soar (Laird, Newell, and Rosenbloom 1987) and the commercial computer games Quake II and Descent 3. Techniques from each of the research areas mentioned above have been used in developing intelligent opponents in these two games. The Soar/Games project has a number of goals from both the research and game development perspective. From the research perspective, computer games provide domains for exploring topics such as machine learning, intelligent architectures and interface design. The Soar/Games project has suggested new research problems relating to knowledge representation, agent navigation and humancomputer interaction. From a game development perspective, the main goal of the Soar/Games project is to make games more fun by making the agents in games more intelligent. If done correctly, playing with or against these AI agents will more closely capture the challenge of playing online against other people. A flexible AI architecture, such as Soar, will also make the development of intelligent agents for games easier by providing a common inference engine and reusable knowledge base that can be easily applied to many different games.
Copyright 1999, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.
Quake II and Descent 3, both popular first person perspective action games, include software hooks allowing programmers to write C code that can access the games internal data structures and agent controls. This has allowed us to extract symbolic information from the games without interpreting the image displayed on the computer screen. A common approach to building intelligent agents in computer games is to use C code and these programming hooks to control agents via a large number of nested if and switch statements. As the agents get more complex, the C code becomes difficult to debug, maintain and improve. A more constrained language that better organizes the conditional statements could be developed but we believe that language would be similar to the Soar architecture. By using the Soar architecture, we are taking advantage of the Soar groups 15 years of research into agent architectures. Soar serves as the inference engine for the intelligent agent (see figure 1). The job of the inference engine is to apply knowledge to the current situation and decide on internal and external actions. The agents current situation is represented by data structures representing the states of simulated sensors implemented in the interface and contextual information stored in Soars internal memory. Soar allows easy decomposition of the agents actions through a hierarchy of operators. Operators at the higher levels of the hierarchy explicitly represent the agents goals, while the lower level operators represent sub-steps and atomic actions used to achieve these goals. Representing goals explicitly in internal memory encourages agent developers to create goal directed agents. Soar selects and executes the operators relevant to the current situation that specify external actions, the agents moves in the game, and internal actions, such as changes to the agents internal goals. Soar constantly cycles through a perceive, think, act loop, which is called the decision cycle. 1. Perceive: Accept sensor information from the game 2. Think: Select and execute relevant knowledge 3. Act: Execute internal and external actions One of the lessons learned, as a result of the DARPA project and the Soar/Games project, is the importance of carefully designing the interface between the inference
Socket Computer Game Interface

Sensor Data Actions

Inference Engine (Soar)

Knowledge Base

Figure 1: Soar is attached to the computer game through a socket connection to an interface that is compiled into the computer game.

engine and the simulated environment. The interface extracts the necessary information from the game and encodes it into the format required by Soar. Each game requires a custom interface because the details of the interaction and the content of the knowledge extracted vary from game to game. For example, Descent 3 agents, flying in a spaceship without gravity, must have the ability to move and rotate in all six degrees of freedom. Quake II agents, running normally with gravity, require only four degrees of freedom. However, basing each interface on a common template allows much of the knowledge developed for one game to be reused in other games. The Soar/Games project uses the standard Soar knowledge representation of a hierarchy of operators each implemented by multiple production rules. The operators at the top level of the hierarchy represent the agents general goals or modes of behavior. For example, the toplevel operators in a Quake II or Descent 3 agent might include attack, explore, retreat and wander. The lower levels of the hierarchy represent successively more specific representations of the agents behavior. Sub-operators of the top-level attack operator could include different styles of attacking, such as pop-out-attack or circle-strafe, or steps followed to implement an attack, like select-attacktype and face-enemy. The operators at the bottom of the hierarchy are atomic steps and actions that implement the operators above, such as shoot, move-to-door and stopmoving. The Quake II agent currently under development consists of a five level operator hierarchy containing 57 different operators implemented with more than 400 production rules. Our hope is that many of these rules can be reused in the development of a Descent 3 agent. Because Quake II and Descent 3 are the same genre of games, they share many similarities at the strategic and tactical levels. We hope to take advantage of this by creating a game independent, genre specific knowledge base used by both games. The game portion of our demonstration consists of six workstations (200MHz or faster Pentium machines), three for the Quake II demonstration and three for Descent 3. For each game one workstation runs the game server and AI system, a second displays the ongoing game from the agents perspective and audience members can play the game against the AI agent on the third. In addition to understanding how the research has resulted in valuable concepts and how those concepts are used, the audience will also be able to evaluate the effectiveness of the

concepts by playing the games. Both games are easily understood, action oriented and visually impressive, which leads to an accessible, exciting demonstration of applied artificial intelligence research.

Acknowledgements

The authors would like to thank Outrage Entertainment Inc. for allowing us to work with Descent 3 while in development and Intel for the donation of machines.

References

Laird, J. E. and Jones, R. M. 1998. Building Advanced Autonomous AI systems for Large Scale Real Time Simulations. In Proceedings of the 1998 Computer Game Developers Conference, 365-378. Long Beach, Calif.: Miller Freeman. Laird, J. E., Newell, A. and Rosenbloom, P.S. 1987. Soar: An architecture for general intelligence. Artificial Intelligence 33:1-64. Jones, Randolph M., Laird, John E., Nielsen, Paul E., Coulter, Karen J., Kenny, Patrick. and Koss, Frank V. 1999. Automated Intelligent Pilots for Combat Flight Simulation. AI Magazine, 20(1):27-41. van Lent, M. C. and Laird, J. E. 1999. Developing an Artificial Intelligence Engine. In Proceedings of the 1999 Game Developers Conference, 577-587. San Jose, Calif.

Research in Human-level AI using Computer Games John E. Laird The goal of our research is to understand what is required for human-level artificial intelligence (AI). A key component of our methodology is developing AI systems in complex, dynamic environments that have many of the properties of the world we inhabit. Although robotics might seem an obvious choice, research in robotics requires solving many difficult problems related to low-level sensing and acting in the real world that are far removed from the cognitive aspects of intelligence. Simulated virtual environments make it possible to by-pass many of these problems, while preserving the need for intelligent real-time decision-making and interaction. Unfortunately, development of realistic virtual environments is an expensive and timeconsuming enterprise onto itself and requires expertise in many areas far a field from AI. However, computer games provide us with a source of cheap, reliable, and flexible technology for developing our own virtual environments for research. Over the last four years, we have been pursuing our research in human-level AI using a variety of computer game engines: Descent 3, Quake II, and Unreal Tournament. Outrage Entertainment, the developer of Descent 3, created an interface for us to test the viability of using a mature AI engine to control a character in the game. Descent 3 is a fun and challenging game that involves three-dimensional control of a spaceship through tunnels and caves. Although it was a useful first step, we abandoned it for Quake II in which the AI system could control more human-like characters. In Quake II, players (including AI bots) attempt to shoot each other and they can collect powerups such as health items, ammunition, and weapons. Quake II has a dynamically linked library (DLL) that allows access to Quake IIs internal data structures and controls for the computer-controlled bots. We interface our AI engine (Soar) through the DLL to control a bot that a human playes against. One attractive feature of Quake II is that there are editors available to create your own game environments. Our goal in using Quake II was to discover what was necessary to create an AI bot that played the game in much the same way a human plays the game. We designed our bots to use sensory information similar to that which is available to a human, use the controls similar to those used by a human, and use some of the tactics that humans use. For sensing, the bots can see other players and items that are not obstructed by other entities or features (such as walls) in the environment. However, it is difficult to extract spatial information about the physical environment from the game, such as walls and doors, which in the games internal data structures are just sets of polygons. The bot needs this information to avoid moving into walls and to create internal maps of its environment. To overcome this difficulty, the bots get range information to the nearest polygons to the front, back, and to both sides. The bots then build up a map as it explores the level that it later uses for moving from room to room, finding the best path to pick up a given powerup, or hiding in corners to surprise the enemy. The bot can also hear noises made by other nearby characters. For movement, the bots can move left, right, forward, and back, as well as turn, using commands that map directly onto the actions humans can make by moving their mouse and pressing keys on their keyboard. The reasoning in our bot is done by programs written in the Soar AI architecture. Programs in Soar consists of sets of rules that support knowledge-rich reactive and goal-driven behavior
through the elaboration of the situation, and the proposal, selection, and application of operators. For example, rules can elaborate the internal representation of the current situation, such as detecting that the bot is too close to a wall, or that a useful weapon is nearby. Proposal rules test the current situation, including elaborations to suggest either primitive or complex operators to perform, such as proposing to pickup a nearby powerup (weapon, health, or ammunition item). Additional rules select among proposed operators, such as preferring to pickup the best powerup if there are multiple powerups nearby. Finally, application rules generate the actions that are involved in performing the operator such as sending a motor command to move forward, or turn. Many operators that are proposed and selected cannot be applied directly, such as picking up a weapon. These are automatically converted into subgoals where further rules propose finer-grain operators to achieve the more abstract operators. Figure 2 shows a small part of the hierarchy that can arise as part of exploring a level. [Add Figure] We did some informal studies where we had humans compare the behavior of human players to variations of the bots to determine if changes in decision speed, tactics, aggressiveness, and aiming skill influence how human the bots were. The trends in the results were that bots with extremely accurate aiming or extremely fast (< 25 msec.) decision speed appeared less human than ones with less accurate aiming skills and slower (100 msec.) decision speed. We also did a qualitative analysis of the behavior and noticed that expert players attempt to anticipate the actions of their opponents. Anticipation is a form of planning similar to the lookahead search performed by AI programs that play classic games like chess and checkers; however, the challenge in a game like Quake II is that when a decision is made to perform an action (such as when to turn) is often as important as the choice of action to take. Moreover, in contrast to chess where you can see the complete board, in Quake II the there is only imperfect information about the state of each player. To simplify the process, our bot creates an internal representation of what it thinks the opponents internal state is, and then uses its own tactics to predict the opponents behavior. It continues to predict until it finds a situation in which it can get to one of the opponents destinations first and set an ambush, or there is so much uncertainty in what the opponent will do that it is not worth projecting its behavior any further. After adding anticipation, playing the bot shifts from being a purely tactical game of trying to get the best weapons and shoot the fastest, to a more strategic and intriguing game, where you are always wondering if the bot has already second guessed you and is hiding in ambush on the other side of the next door. Although action games such as Quake is the most popular game genre, there are inherent limits in the complexity of behaviors required to create compelling bots that are essentially computerized punching bags. Furthermore, these games limit the human gaming experience to violent interactions with other humans and bots. Therefore, we are currently working to develop non-violent plot-driven computer games where the AI characters have diverse and complex behavior that is driven by the interaction of their body with the environment, their goals, their knowledge of the world they inhabit, their own personal history, and their interactions with human players. This will lead to games where the human players are faced with challenges and obstacles that require meaningful interactions with the AI characters. We are building on one of the oldest genres of computer games, sometimes called interactive fiction or adventure games, which involve having the human player overcome obstacles and solve puzzles in pursuit of some

goal. [Myst, Bladerunner, Monkey Island series] One weakness of these games is that the behavior of non-player AI characters is scripted, so that the interactions with them are very stilted and not very compelling. Our challenge will be to create AI characters whose behavior are not only human-like but also leads to engaging game play. Using Unreal Tournament (UT), we are creating an adventure game where the player takes on the persona of a ghost-like energy creature trapped in a house. UT is an action game similar to Quake2 with an underlying engine that is extremely flexible. For just the cost of the game ($20), you get access to level editors for defining the environment, a scripting language (Unrealscript) for defining the physics of the world and the way objects in the world interact, and the ability to import your own objects into the game. In our game, the human players goal as the ghost is to escape the house and return home to an underground cavern. The ghost is severely limited in its ability to manipulate the environment. It can move or pick up light objects, such as a match or a piece of paper, but it cant move or manipulate heavy objects. Moreover, metal drains the ghost energy, so the ghost must avoid metal objects. These constraints force the player to entice, cajole, threaten, or frighten the AI characters into manipulating the objects in the world, which in turn forces us to develop AI characters that have enough intelligence to make these social manipulations possible and realistic. With the AI characters playing such a central role, they must have distinctive personalities in terms of their goals and reaction to the environment. For example, there will be the evil scientist who is immune to fear but is weak and easily fatigued by exertion or cold and wants to capture the ghost character, while there will also be a lost hitchhiker (we arent trying to have the most original story ever) who is easily frightened by the ghost, but is physically strong and driven by curiosity. The game will push our research to integrate the knowledge-based, goaloriented reasoning that we have concentrated in the past, with emotions, personality, and physical drives that have been used in simple, knowledge-lean agents in other systems [references to Oz, Sims]. Our hope is that we inspire others to pursue human-level AI characters and new types of games that those characters make possible. References (to be completed) Figures: I can get some screen shots of our UT game.