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.