Although games have existed for thousands
of years, the computer has greatly expanded the types of games we can play. The
computer allows us to create and interact with completely new virtual worlds
that previously existed only in our imagination. The computer is unique in its
ability to create an almost infinite variety of challenges at many different
time scales, from epic quests that take weeks to achieve, to moment to moment
action where we know that if we play just a few more minutes, we will achieve
new powers or unlock hidden secrets. The challenges usually arise directly from
our interaction with the virtual
environment, varying from the dramatic, such as struggling to leap over a
bottomless chasm, to the mundane, such as attempting to create an unbroken line
of bricks out of an unending supply of descending blocks. However, it is not
just the challenge of a human vs. the world that enthralls us; it is also the
challenge of competing and cooperating with another intellect. From the very
first computer game, Space War!, where the player
controlled a space ship and attempted to destroy another player’s ship, the
challenge has often been human vs. human. What is unique to computer games is
that we now “have the technology” to create games where the challenge of playing
against another intellect is not restricted to playing another human. Computers
cannot only create challenging environments; they can also create challenging
artificially intelligent (AI) characters (Woodcock 2000). AI characters also allow us to create
games where the challenges stem not just from competition, but also from the
social interactions with characters in populated virtual worlds. Despite the obvious connection between
AI and computer games the AI research community has only occasionally explored
games as an application area (Agre and Chapman 1987, McCarthy
1998).
In this chapter we explore the impact of
AI on computer games. We start with an examination of the different game genres:
action, role playing, adventure, strategy, simulation, sports and racing. There
are no hard and fast lines that delineate these genres, and many games straddle
multiple genres. For example, there are strategy games (Dungeon Keeper) that
allows the human to “jump into the body” of one of their units and play as if it
is an action game. Also, there are action games where you must manage resources
and multiple units (such as Battlezone). However, the genres provide a useful
organization and different genres present the player with different
environments, different challenges, and different roles for AI to enhance the
game experience. Although each genre has its distinctive characteristics, there
are some commonalities to the roles that AI plays in these genres. The
connection between the genres and roles is shown in Figure
1.
_files/image001.gif)
_files/image002.gif)
_files/image003.gif){kind=small}
_files/image004.gif){kind=small}
_files/image005.gif){kind=small}
_files/image006.gif){kind=small}
_files/image007.gif){kind=small}
_files/image008.gif)
_files/image009.gif){kind=small}
_files/image010.gif){kind=small}
_files/image011.gif){kind=small}
_files/image012.gif){kind=small}
_files/image013.gif){kind=small}
_files/image014.gif){kind=small}
_files/image015.gif){kind=small}
The second half of
this chapter examines each of the AI roles in more detail, providing historical
background on the AI techniques used for each role. For each role, we also
examine the tension that exists between overall game play and the competence of
the AI. In many cases, multiple levels of AI are needed to challenge the range
of human players who vary from novice to expert. In order to provide a
challenging opponent for human experts, the AI may finesse some of the rules
that the human must play by. For each role we also attempt to predict how AI in
games will evolve in the future as both the power of the underlying hardware
increases and we improve our understanding of artificial
intelligence.
Game
Genres
Action
Games
“Shortly after landing on an alien
surface you learn that hundreds of your men have been reduced to just a
few. Now you must fight your way
through heavily fortified military installations, lower the city’s defenses and
shut down the enemy’s war machine.” – Quake II
Action games are one of the most popular
game genres and involve the human player controlling a character in a virtual
environment, usually running around frantically using deadly force to save the
world from the forces of evil. These games vary in the perspective that the
human has of their character, be it first person, where the human sees what the
character would see, or third-person, where the player looks over the shoulder
of the character. Popular examples include Doom, Quake (Keighley 1999), Descent,
Half-Life (Birdwell 1999), Tomb Raider, Unreal Tournament, and Halo. In pure
action games, AI is used to control the enemies, which are invariably alien
monsters or mythical creatures. Realism in graphics
has been the point of competition for these games; however, the graphics race
seems to have run its course, with better AI becoming the point of comparison.
Recent games have extended the genre so that the human player may be part of a
team, including either human or AI partners. In all cases, it is the
moment-to-moment reaction of the AI to the human that is most important so that
the AI must be tactically savvy with little emphasis on
strategy.
Role-Playing Games
“Immerse yourself in
a…world, where nations hang in the balance of your actions, dark prophecies test
your resolve, and heroic dreams can be fulfilled at last.” – Baldur’s
Gate
In role-playing games, a human can play
different types of characters, such as a warrior, a magician, or a thief. The
player pursues quests, collects and sells items, fights monsters, and enhances
the capabilities of their character (such as strength, magic, quickness, etc.),
all in an extended virtual world. Example games include Baldur's Gate, Diablo,
and the Ultima series. Recently, massively multiplayer role-playing games have
been introduced where thousands of people play and interact in the same game
world: Ultima Online, Everquest, and Asheron's Call. In all types of
role-playing games, some of AI characters play the same role of enemy as in
action games; however, role-playing games include additional characters, such as
traveling companions, shopkeepers, and villagers who increase the social aspects
of the game. These additional, supporting characters expand the requirements of
AI beyond just tactical enemies. Because of their open-ended nature, massively
multiplayer games provide an additional opportunity to use AI as a generator of
quests for human players to pursue.
Adventure Games
“Aye, ‘tis a rollicking piratey adventure
that’s sure to challenge the mind and shiver a few timbers!” – The Curse of
Adventure games, and the related genre of
interactive fiction, move even further away from action games, as they
de-emphasize armed combat and emphasize story, plot, and puzzle solving. In
these games, players must solve puzzles and interact with other characters as
they progress through an unfolding adventure that is determined in part by their
actions. Early adventure games, such as Adventure and Zork were totally text
based, but more recent games sport 3D graphics (sometimes using the graphics
engines developed for action games). Example games include the Infocom series,
King's Quest, and many games from Lucas Arts, such as Full Throttle,
Strategy Games
“Players must successfully construct and
rule their medieval empire while engaging in real-time tactical warfare over
land, sea, and air.” – Warcraft
In strategy games, the human controls
many units (usually military units, like tanks, or the ever present alien war
machines) to do battle from a god's eye view against one or more opponents.
Strategy games include reenactments of different types of battles: historical
(Close Combat, Age of Empires), alternative realities (Command and Conquer),
fictional future (Starcraft), and mythical (Warcraft, Myth). The human is faced
with problems of resource allocation, scheduling production, and organizing
defenses and attacks (
Simulation Games
“You’re in charge of
creating an entire city from the ground up – and the sky’s the limit.” – SimCity
3000
Simulation games give
the player god-like control over a simulated world. The human can modify the
environment and, to some extent, its inhabitants. The entertainment comes from
observing the effects of his or her actions on individuals, society, and the
world. SimCity is the classic example of a simulation, or god game, where the
human acts as mayor and the AI controls individual units or citizens of the
simulated city. The Sims and the game Black and White are probably the most
intriguing examples. In theses games, the player creates individual characters
(units) that have significant autonomy, with their own drives, goals, and
strategies for satisfying those goals, but where God (the human player) can come
in and stir things up both by managing the individual characters and their
environment.
Sports
“Welcome to Madden
NFL 97, the game that captures the excitement of a 30 yard touchdown pass, the
strategy of a well executed scoring drive, and the atmosphere of a crisp autumn
afternoon in the stadium.” – Madden NFL 97
Sports games cover almost every sport imaginable, from traditional
team sports such as football or baseball, to individual sports, such as Olympic
events. Many of the individual sports fall under racing games, such as car
racing, boat racing, or snowboarding, and these are covered in a separate genre
below. Team sports games have the human play a combination of coach and player
in popular sports, such as
Racing Games
“Gran Turismo 3 delivers the most
realistic racing experience. Customizable vehicles handle different due to
differences in horsepower, ride height, tire type or vehicle mass, just to name
a few variables.” – Gran Turismo 3
There are computer-racing games for
almost any vehicle or platform that a human can climb on: cars, trucks,
motorcycles, boats, planes, skates, skateboards, and snowboards. Some of the first computer games
involved racing cars, avoiding obstacles, and trying to beat a computer or human
opponent. In racing games, the computer provides a simulation of a sport from a
first or third-person perspective. The human player controls a participant in
the game who competes against other human or computer players. The AIs for a
racing game are in a class by themselves because the goal in a racing game is so
simple – stay on course and be the fastest to the finish
line.
AI
Roles
Across these genres, AI
is used in a variety of ways. One might be tempted to think that an AI should
always be constructed to model a human player as accurately as possible.
Sometimes that is appropriate, but as we review each of the roles an AI
character can play, we will see that often human-like behavior must be
sacrificed because human-like behavior is still beyond the state of the art or
because the game is more fun without it. In computer games, the real goal of the
AI character is to enhance gameplay and most of the time that entails being an
opponent that fights up until then end and then loses.
Tactical Enemies and
Partners
In action games, the main thrill is
destroying the bad guys and, except for multi-player games, the bad guys are
controlled by the computer. In early action games, the computer-controlled
enemies did little more than shoot widely and run directly at the player. The
enemies were challenging, not because of the complex tactics they used, but
because of their superior numbers. Initially, some tactical enemies overcome
their limited intelligence by “cheating”, such as having the ability to see
through walls or out of the back of their heads.
Navigation was not an issue in early
games because the enemies were placed in locations that the human player had to
traverse and the AIs could just run at the human. When navigation is required,
it is done via nodes that are placed in the world that the AIs can see, but are
invisible to the human player. The AI moves from node to node, whose placement
guarantees that the AI will not have to dynamically avoid obstacles. Usually a
level designer places the nodes by hand, although recently some games have
software that automatically generates nodes. Nodes are used for more than pure
navigation, with some nodes being marked as places for sniping or ambushing. In
addition to following nodes, the AIs also are also able to interact with the
items in their world, such as picking up weapons, ammo, or health powerups. In
some games, the AI will have complex responses to player actions, such as
picking up a grenade that has been thrown their way and throwing it back at the
human player (Return to Castle Wolfenstein). Some tactical enemies will use
cover during reloading to avoid being easy targets.
There is a continual tension between
making the enemies more realistic and maintaining the game play experience. For
most of these games, the human player fights against tens or hundreds of
opponents, and if the AI opponent had anything close to the human’s
capabilities, the game would be impossible. The AI must be challenging and then,
because of some failure or mistake, die gracefully before the onslaught of the
human player. For example, in the game Deus Ex, the enemy AI characters have
realistic models of a human’s limited field of view, and must detect the player
by “hearing” the sound of footsteps, door openings, etc. Thus, these characters
react to their environment much the way a human would. But if the AI characters
use this information to the fullest to hunt down the human, the player would be
“toast.” To keep the realism high but still allow the player to win, the AI
characters always give their position away by talking or making noise when they
hear or see a glimpse of the player, saying such witty comments as “What was
that?” or “Who goes there?” This alerts the player to the presence of the
enemies, giving the player a chance to get that all-important first shot in.
Moreover, the enemy characters always
miss on the first couple shots, which further helps the
human player beat the AI enemy.
In most actions games, there is a
multiplayer mode where it is every player – human or computer – fighting for
itself. In these cases, the computer enemies should be
as challenging as a human without obvious faults or disadvantages. It is easy to
make the computer enemies challenging by giving them superhuman reaction times
and aiming skills. Playing against these types of enemies forces the human
player to adopt tactics that don’t necessarily transfer to playing against other
humans. Our own research (Laird and van Lent 1999; Laird 2000b) has concentrated
on building enemies for Quake II that have the same strengths and weaknesses as
human players. To beat them, you have to out-think them as much as you have to
out-shoot them. Our Soar Quakebot is essentially a real-time expert system that
has multiple goals and extensive tactics and knowledge of the game. It is built
within the Soar architecture and has over 800 rules. While exploring a level, it
creates an internal model of its world and it uses that model in its tactics, to
collect nearby weapons, ammo, and health, to track down an enemy, and to set
ambushes. It also tries to anticipate the actions of human players by putting
itself in their shoes (creating an internal model of their situation garnered
from its perception of the player) and projecting what it would do if it were
the human player. This changes the game from one of always trying to just get
off the first shot, to a more strategic game of predicting the opponent’s
behavior, and at the same time, avoiding being too predictable
yourself.
Building human-level enemies for these
games requires solving many general AI problems and integrating the solutions
into coherent systems. The enemies must be autonomous. They must interact with a
complex dynamic environment, which requires reactive behavior, integrated
planning, and common sense reasoning. As they advance, they will also need
models of high-level vision that have the same strengths and weaknesses as
humans. For example, if the human were in a dark room, the AI would be cheating
if it could easily sense, identify, and locate the human. However, if the human
is backlit by a bright hall, the AI enemy should easily sense and locate the
human, but possibly not identify him. This is important for game play so that
the same tactics and behaviors that work well with humans work well with AI
enemies.
There are many other aspects of AI that
are important to building intelligent enemies. Because of the extended geography
of the environment, they must navigate, use path planning, spatial reasoning,
and temporal reasoning. As the games become more complex, the AI will need to
plan, counter-plan, and adapt to the strategies and tactics of its enemies,
using plan recognition, opponent modeling techniques, and learning. Their
responses need to be within the range of humans in terms of reaction times and
realistic movement. One can even imagine adding basic models of emotions, where
the enemies get “mad” or “frustrated” and change their behavior as a
result.
Although the emphasis in many games is
fighting against the computer, some
games provide the player with teammates that help them fight against the
overwhelming odds. Creating AI controlled partners involves many of the same
research issues as tactical enemies.
However, while enemy AIs emphasize autonomy, AI partners emphasize
effortless cooperation and coordination between the human player and the AI
partner. Current games restrict the human to using specific commands to interact
with partners, such as defend, attack, and follow me - commands much more
limited than used in human-to-human interactions. In the extreme, this brings
speech recognition, natural language processing, and even gesture recognition
into the mix of future research issues that will need to be incorporated into
computer games. The partner AI must coordinate its behavior, understand
teamwork, model the goals of the human, and adapt to his style. Creating such
partners can build on previous research in these areas, but must embed it within
the context of all of the other cognitive activities involved in playing the
game.
Support Characters
In adventure and role-playing games,
support characters fill out the game world with interesting people for the
player to interact with. Support
characters are the merchants you buy equipment from, the tavern drunks you learn
key clues from, the guard you must convince to unlock the gate, and the damsel
in distress. While they are some of the least sophisticated AI characters in
today’s computer games, they have the most promise to improve games and are the
most interesting in terms of developing human-level AI. Today’s support
characters are very limited in their interactions with the player and very scripted in their behavior. Conversations with the
player take the form of canned speeches by the support characters, usually text
with corresponding voice-overs, interspersed with decision points at which the
player can affect the direction of the conversation. Decision points present the player with
a short list of phrases from which to choose their next utterance. The behavior of support characters is
generally limited to a looping animation with a few scripted action sequences
that are triggered by the player’s actions. So, the support characters stand in one
place, continually chopping wood or drinking from their mug of ale, until the
player initiates an interaction.
During the scripted interaction the support character may gesture to
emphasize a point or even walk a short distance to hand the player an
object. Once the interaction is
over, the character returns to his or her looping behavior.
In a few games, such as in Blade Runner
(Castle 1998), the support characters have some limited autonomy and some simple
goals, but they are extremely narrow goals supported by limited sets of
behaviors. Unfortunately, most game
developers aren’t as interested in improving support characters as they are in
improving AI for the other roles.
The popularity of adventure games seems to be temporarily ebbing and,
with the advent of massively multiplayer role-playing games, human players are
filling the role of support characters in role-playing games. However, recent
advances in research on human-computer interaction, social intelligence, and
natural language interfaces may provide interesting new approaches to the AI for
support characters. This is
promising area for AI research because, if done well, they will allow the
characters in the game to interact socially with the player. One reason today’s games are so violent
is the lack of sophisticated support characters. Shooting at the player requires less
complex AI than talking to the player.
Socially intelligent support characters will help populate the games with
interesting opportunities for interaction that guide the player along various
plot lines. Each character will
have a set of goals and beliefs about the world that the player must discover
and utilize to obtain the assistance of that character. Perhaps after a long and harrowing quest
the player will discover that the princess doesn’t want to be rescued and the
final challenge is resolving her conflicts with her father, the King.
Since these characters will exist in a
virtual world and play the role of humans in that world, they provide a useful
first step in research towards human-level AI (Brooks at al 1999, Laird and van
Lent 2001). Support characters must interact with and adapt to the environment,
to human players and to other support characters. They must provide human-like responses,
including realistic movement (Hayes-Roth and Doyle 1998), personality, emotions,
natural language understanding and natural language generation. In order to do
all this, and because these support characters most directly play the role of
embodied virtual humans, they require a wide range of integrated AI
capabilities.
Strategic Opponents
The
tasks a strategic opponent performs can be divided into two categories:
allocating resources and issuing unit control commands. In the popular
real time strategy game Age of Kings, for example, resources include food, gold,
wood, and stone and are gathered from specific points on the map. Once gathered, these resources are used
to build a wide variety of units, such as militia, archers, knights, ships, and
workers, and buildings, for example barracks, farms, walls, monasteries, and
universities. Tailoring the
allocation of resources to simultaneously support cultural development, defense
and offensive is half of the strategic opponent’s job. The other half of the job is to develop
offensive and defensive strategies and command the units that have been produced
to implement those strategies.
Units can be ordered to move in a variety of formations, attack enemy
units and buildings, defend friendly units or buildings, and perform a number of
special actions. For example, monks
can convert enemy forces so they change sides. Strategy games almost always include
non-military units that are used to gather resources, build new buildings, and
repair damaged buildings. The
resource allocation and unit control tasks cannot be controlled
independently. The type of
resources gathered and how they’re spent must be guided by the needs of the
strategic opponent’s unit control strategy. Similarly, the unit control strategy
must take into account the available resources to avoid selecting a strategy
that requires unavailable resources.
Strategic
opponents are also found in team sports games. Acting as the coach of the opposing
team, the strategic opponents is again faced with the tasks of allocating
resources and issuing unit control commands. In a
In the past, most game developers resorted to static,
pre-defined strategies and “cheating” to minimize the demands on the strategic
opponent. The artificial intelligence for the strategic opponents
generally took the form of a single hard-coded strategy created by the game
designer when the game level was created.
For real-time strategy games this would be a single attack plan, usually
a mass frontal assault, executed periodically (for example every 10 minutes)
with no regard for the human player’s behavior. As with tactical
opponents, these strategic opponents were designed to allow the human to win
after a close and entertaining battle.
Often this design goal was explicitly programmed into the strategic
opponent’s behavior. If the
periodic attacks threatened to wipe out the human player the strategic opponent
would reduce the attacking force accordingly. Based on the belief that human players
would lose interest after 40 minutes of game play, at least one game company
programmed the strategic opponent to destroy most of its own forces after 35
minutes of play. These behaviors
gave the human player the perception that they had barely survived the strategic
opponent’s desperate, last-ditch attack and as a result conquered the undefended
base. In sports games, the
strategic opponent often utilized a fixed sequence of plays or would randomly
selected plays from the play library. Because most strategic opponents
relied on a fixed strategy, they were predictable and easily beaten once their
weaknesses were found.
To
implement these pre-defined strategies the strategic opponents usually cheated
in a number of ways. One form of
cheating allowed the creation of extra units or resources from nothing to
support the periodic attacks. Another form of cheating gave the strategic
opponent complete knowledge of the map and the locations of the player's forces.
This freed the strategic opponent from exploring the map and scouting the enemy
to obtain this information. In most cases, players eventually detected
that the strategic opponents were cheating, which destroyed the illusion that
they were matching wits with a military genius or famous coach.
More
recent strategic opponents have become more sophisticated. In many cases
cheating has been reduced or eliminated. As the players demand more varied
opponents, game developers have given strategic opponents a library
of
strategic plans from which to choose. In strategy games this library may
consist of a small number of hard-coded attack strategies from which the
strategic opponent selects. By selecting a strategy that corresponds to
the human player's plan, the strategic opponent can use its resources more
effectively and require fewer cheat-provided resources. In addition,
better path planning algorithms has made it much easier to include exploring and
scouting as part of the strategic opponent's behavior. Recent sports games
are going a step further by detecting patterns in the human player's behavior
and giving the strategic opponent the ability to take advantage of these
regularities. An AI who reacts to the player's behavior results in a more
challenging and entertaining strategic opponent. In addition, it reduces
the chance that the player will find and exploit weaknesses in the strategic
opponent.
In the future, strategic opponents may be able to create
new strategies specific to the opponent and situation. This will involve
integrated planning, common sense reasoning, spatial reasoning, plan
recognition, and counter-planning. One of the most important aspects of strategy
creation is the coordination of multiple types of units into a cohesive
strategy. Once a
plan is created, the strategic opponent must determine how
to best use limited resources to compose offensive and defensive forces
appropriate to implementing the plan. This resource allocation can involve
scheduling, constraint satisfaction, and temporal reasoning.
Units
In both strategy games
and team sports games, the strategic opponent implements a strategy by issuing
commands to a large number of units that make up their force. For example, in strategy games the
strategic opponent issues orders to worker units and military units. Commands to worker units specify what
type of building to build or what type of resources to gather and from which
site. Military units might be
commanded to attack an enemy unit, defend against attack, or patrol along a
specified path. In both cases some
intelligence is required on the part of the unit to carry out the strategic
opponent’s orders. The units must
be able to plan a path, follow it to a selected location and react to changes in
their local environment such as the appearance of enemy units or depletion of
resources.
In a team sports game
the strategic opponent might select a play or strategy for the entire team. That strategy defines a role and/or
approximate path for each player involved in the play. As with strategy games, the individual
units (players) must plan and follow paths and react to the opposing units. Because there is more variation between
players than between military units (at least in a strategy game context), team
sports games tend to place more of the decision-making responsibility on the
units. Returning to the football
game example, the coach specifies a general play that may have a number of
options when executed. The unit
players, especially the quarterback, must decide which of these options to
select, which receiver to throw to or which running lane to take, on the fly as
the play unfolds. As with strategic
opponents, units in sports games must conform to the user’s knowledge of the
style of the player that that unit represents.
Initially the primary
focus of artificial intelligence development for units was path planning. Tens or hundreds of units are
often active at the same time and calculating a path for each unit to its goal
around environmental obstacles is a computationally expensive procedure. Borrowing from the AI research
community, game programmers discovered that the A* search algorithm is a
powerful and efficient way to calculate these paths. To this day variations on the A*
algorithm are still the primary path planning technology used in the game
industry. A* is effective in
avoiding static obstacles but dynamic obstacles, such as other moving units,
still present a problem.
Recalculating each unit’s path every time step to avoid all the other
units is simply too expensive. As a
result, early strategy games exhibited frequent traffic jams at bottlenecks when
groups of units moved together.
This was often overcome by allowing units to pass through each other
avoiding unit collision and moving obstacles altogether. In these early strategy games units
typically ignore enemy units they discover unless explicitly ordered to attack
them. These two problems could
cause armies to get strung out due to a bottleneck and then parade past a single
enemy unit allowing it to destroy the whole army.
In more recent strategy games, units can
be given commands defining how to react to enemy units. A unit set to attack may attack and
follow any enemy it comes across until it kills or is killed. When set to defend, however, the unit
might attack the enemy unit but would not follow it. These different behavior strategies are
supported by a finite state machine that controls how the unit selects actions
to execute a command. The different
settings (attack, defend…) simply modify the transitions within that unit’s
finite state machine. Another
recent advance allows groups of units to move in formation. The player selects a group of units and
specifies a formation. The units
will then automatically organize themselves into that formation with different
types of units in appropriate places.
For example, a group of swordsmen and archers will organize themselves in
a box formation such that the archers are on the inside protected by the
swordsmen around the perimeter.
Once in formation the units will move as a group and try to avoid
breaking formation. Formation
organization and moving in formation requires some advanced path planning,
teamwork, and careful scripting on the game developer’s
part.
As strategy games and
team sports games continue to advance the units in these games will continue to
become more autonomous. The level
of unit autonomy must be carefully balanced to allow users to maintain strategic
and tactical control over their units while eliminating the tedious
micro-management of each unit. The
move towards grouping units into formations and issuing group commands is a
first step in this direction.
Future areas of research for unit-level AI include case-based reasoning,
teamwork, distributed planning and execution, and, as always, path
planning. Since there can be
hundreds of units active in a game at one time, the issues of computational and
memory overhead are particularly important for unit AI (Atkin et al.
1999).
Racing
Opponents
Opponents for racing games are some of
the most pure applications of artificial intelligence in games. The AI must
travel over a course, controlling a vehicle (which could be a car, a boat, a
plane, or even a snowboard). The most primitive and earliest opponents for
racing games followed a predefined circuit around the course at a set speed –
they were essentially the rabbit that the greyhounds/players chase around the
course. They were oblivious to the physics of the world so they could move in
ways and at speeds that were impossible for the human player to match. A simple
extension to make them appear more realistic was to vary their speeds at
predefined places around the course, such as slowing down in curves or over
rough terrain and then speeding up in straight-aways.
The next step was to have the
AI-controlled vehicles obey the same physics as the players’ vehicles, so they
would spin out or crash if they took a corner too fast and more generally have
to race following the same rules as a human player. Controlling a vehicle can be
quite complex, requiring the integration of domain-dependent planning to
determine where the vehicle should attempt to be a few seconds from now using
the appropriate tactics, real-time execution to attempt to get to that position,
and real-time reaction to
respond to the movements of other vehicles. To avoid these complexities,
the AI for racing opponents almost invariably follows a recorded trace of the
behavior of a human player. It is as if there is a line on the course that tells
the AI where to go, what speed to use, and possibly any special maneuvers that
should be performed.
Using a trace of human behavior solves
some of the problems. However, racing games inevitably involve reacting to
changes in the environment: another vehicle may be in the way and must be
avoided, a powerup (an object that gives the racer special powers, such as
enhanced speed or repairs to injuries) may appear, or the vehicle may be pushed
off onto an alternative part of the course and need to switch to a new path.
Thus, one of the complexities in using human traces is
knowing how to balance blind trace following with pursuing dynamic goals
that arise during the race. Usually there will be a set of pre-specified cues
that establish the behaviors that respond to the dynamic events and then once
those behaviors are complete, the AI returns to following the
trace.
Creating opponents whose behavior is
based on human traces also makes it easy to create a variety of opponents at
different skill levels with different styles – just record different humans with
these different characteristics (or if you are on a restricted budget, a single
human pretending to have different styles). In the limit, the behavior of
world-famous expert racers can be recorded – similar to using motion capture for
signature moves in sports games.
The different skill levels are an
important part of making a racing game fun to play. If a human player must start
out against an expert, he will be soundly beaten. Conversely, if there are only
easy opponents to race against, the human player will quickly become bored as he
gains experience. Although AI opponents with multiple skill levels is a
successful and probably the dominant approach, it does require that the human
continually choose the right level of competition – there will inevitably be
races in which the human finds himself either far behind or far ahead of the AI
competition. An alternative is to try to make every race a nail biter where the
human always has a chance to comeback and win, no matter what mistakes they made
early on. Moreover, if they have a great race, they are challenged up until the
end. To provide this, many racing games have “rubber banding”, where the AI
systems slows down if it gets too far ahead and speeds up if it gets too far
behind. Thus, the player is always in the heat of a race, and if the player has
a strong finish, he will win.
What can we expect in the future for racing AIs? Racing AIs already provide excellent competition (some even including taunts during the race) but we can speculate that many future racing games will require AIs that can race over novel or dynamic terrain, where it is infeasible to create human traces for all of the possible paths. These AIs will probably incorporate limited planning where they analyze the course in front of them and pick a path and speed based on knowledge of the terrain they must traverse, performance characteristics of their vehicle, and its predicted interaction with the race course. Such reasoning is inherently more computationally intensive than current approaches, but as both consoles and PCs continue to marshal more and more processing power, the AI will get enough computational resources to use more complex approaches.
Commentators
One of the more unusual
roles for AI in computer games is to simulate the play-by-play reporting during
a sports game by having one or more computerized commentators. The role of the
commentator is to observe the actions of the AI and the human and generate
natural language comments suitable to describe the action (Frank 1999). Although
not necessary for the competitive aspects of the game, game players seem to
enjoy having the background patter that highlights their successes and failures.
Many sports games take their commentators very seriously, using established
commentators, such as John Madden, to not only provide the play-by-play, but
also to market the games. Hours of commentary is recorded and then played at the
appropriate times during the game.
Good commentary is extremely difficult because, not only does it report
on the specific action in the game, but it relates that action to current state
of the game (where the ball is on the field, who is ahead, by how much, how much
time is left in the game…) and the teams’ goals, often with a comment on the
wisdom of the play selection. Thus, the exact same play can be a good call at
one point in the game, but be a huge mistake in another. For example, in U.S.
football, if time is running out in the game and a team is behind by four points
with the ball on the opponent’s 20 yard line, with fourth down and 8 yards to
go, the player might call a pass play in an attempt to win the game, and the
commentators should acknowledge that he is forced to do this. If the player
attempts to kick a field goal, that won’t help win the game and the player
should be chastised. However, if
time is running out in the first half (but not the game), and a team is up by
seven point, with the ball still on the opponent’s 20 yard line with fourth down
and 8 yards to go, the commentators should comment that the player is taking a
huge risk by calling a pass play, but laud the human player if he attempts a
field goal. The difficulties in
creating good commentary are further complicated by the need to avoid
repetition, which is difficult because to obtain high quality in the speech
production, all of the phrases are pre-recorded. There is nothing like hearing
the same exact phrase more than once in a game to destroy the suspension of
disbelief.
Conclusion
The focus of this chapter is the
different roles AI plays in today’s game genres. However, game developers are constantly
searching for the next innovation that will revolutionize the industry. An example of this is the recent
appearance of massively multiplayer online games, now the fastest growing game
genre. New genres and new roles in
existing genres will provide new opportunities for AI. AI story directors might construct
stories on the fly giving the player unlimited freedom in the game world. AI opponents might use fast planning
algorithms to detect weaknesses in the player’s defenses and create novel
strategies and/or tactics specifically designed to exploit those
weaknesses. Developers may teach,
rather than program, AI opponents that learn to play the game and learn to adapt
to the strengths and weaknesses of different players. Conversely, new advances in AI can open
a door to new game genres and even new game paradigms (Stern 1999). For example, speech recognition, natural
language understanding, and speech generation could lead to a new class of games
played via cellphone.
The existing roles for artificial
intelligence, as well as future roles, share a common goal of providing the
human player with an entertaining experience. Success, and profitability, requires
careful balancing of a number of factors.
The AI opponents must challenge the player while still allowing the
player to taste victory. The AI
characters must be believable with personality and a rich range of behaviors
while still fitting into a game developer’s budget and schedule. The AI enemies must be cunning and
crafty in their tactics while still reacting in factions of a second.
Fortunately for gamers, game developers
only need concern themselves with the results, or external appearance of
believability, of the AI.
Shortcuts, cheats, and other smoke and mirror techniques abound in
commercial game development. In
some cases, such as strategic opponents, the players discover the cheats. However, in most cases the players only
see the resulting behavior that makes games so entertaining. With the goal of discovering the
foundations and inner workings of intelligent behavior, AI research pays as much
attention to the realism of the process as the realism of the result. With a few exceptions, game developers
have generally found the techniques used by the research community to be too
costly in terms of processor and memory demands. However, with the power of computers
increasing almost daily and AI’s new prominence as a point of competition for
games we believe AI research will soon play a role in commercial computer games
(Laird 2000a, Takahashi 2000)
Acknowledgments
The authors are indebted
to the many students and staff who have worked on the Soar/Games project, most
notably Steve Houchard, Karen Coulter,
Mazin Assanie, Josh
Buchman, Joe
Hartford, Ben Houchard, Damion Neff, Kurt
Steinkraus, Russ Tedrake, and Amy Unger. Thanks
to Doug Church and Lars Liden for educating us on AI
and commercial computer games.
References
Agre, P.
E. and Chapman, D. 1987. Pengi: An implementation of a theory of activity, In
Proceedings of AAAI-87,
268-272, AAAI Press.
Atkin, M.
S., Westbrook, D. L., and Cohen, P. R., 1999. Capture the Flag:
Military Simulation Meets Computer Games. In Papers from the AAAI 1999 Spring
Symposium on Artificial Intelligence and Computer Games, Technical Report
SS-99-02, AAAI Press, 1-5.
Birdwell, K. 1999. The
CABAL: Valve's Design Processing for Creating Half-Life. Game Developer.
6(12):40-50.
Brooks, R. A., Breazeal. C., Marjanovic, M., Scassellati, B.,
and Williamson, M. 1999. The Cog Project: Building a Humanoid
Robot.
Castle, L. 1998. The
Making of Blade Runner, Soup to Nuts! In Proceedings of the
Computer Game Developers' Conference, Long Beach, CA,
87-97.
Frank,
Hayes-Roth, B. and
Doyle, P. 1998. Animate Characters. Autonomous Agents and Multi-Agent
Systems, 1(1):195-230.
Keighley, G. 1999. The Final
Hours of Quake III Arena: Behind Closed Doors at id Software, GameSpot, http://www.gamespot.com/features/btg-q3/index.html.
Laird, J. E.
2000a. Bridging the Gap Between Developers and Researchers. Game Developer, 7(8), p.
34.
Laird, J. E.
2000b. It Knows What You’re
Going To Do: Adding Anticipation to a Quakebot. In
Papers from the AAAI 2000 Spring Symposium on Artificial Intelligence and
Interactive Entertainment, Technical Report SS-00-02, 41-50. AAAI Press.
Laird, J. E. and van
Lent, M. 1999. Developing an Artificial Intelligence
Engine. In Proceedings of the Game Developers
Conference,
Laird, J. E. and van
Lent, M. 2001. Interactive Computer
Games: Human-level AI’s Killer Application. AI Magazine, 22 (2):
15-25.
McCarthy, J. 1998.
Partial Formalizations and the Lemmings Game,
http://www-formal.stanford.edu/jmc/ lemmings.html
Stern, A.
1999. AI
Beyond Computer Games. In Papers from the AAAI 1999 Spring Symposium
on Artificial Intelligence and Computer Games, Technical Report SS-99-02,
77-80. AAAI Press.
Takahashi, D. 2000.
Artificial Intelligence Gurus Win Tech-Game Jobs.
The Wall Street Journal,
Whatley, D. 1999. Designing Around Pitfalls of Game AI. In
Proceedings of the Game Developers Conference,
Woodcook, S. 2000. Game AI: The
State of the Industry. Game Developer, 7(8), 24-32.