Transcript History and overview

Game AI
The history, development, strategies,
and challenges of intelligence in
computer games
History and overview
• Minimax
- Developed by John von Neumann in 1928
- This algorithm is used extensively in game theory
• Samuel’s learning program (1959)
- The program learns through the manipulation of
the summation of heuristics.
- If the program wins, it raises high heuristic values
and lowers low ones. If it loses, it does the opposite.
• 1960s
- Progress and success in Game AI.
- Creating a successful AI meant coming up with the
right rules for it to follow.
• 1970s-1980s
- Transition to games as entertainment
- Using search based AI to emulate entertaining
characters would be unnatural and clumsy
- Game play is based more on skill than on rules
• Early 1990s
- Increased realism becomes the primary focus of the
game industry
- A rift develops between the developers of popular
games and AI researchers
- Game AI that it remains little more than a modified
version of Pac-man.
Examples:
First Person Shooters and
Simulators (Wolfenstein 3D,
Doom, Tie-Fighter): If
alarmed, the AI will track and
attack the player. Otherwise, it
will idle.
Real Time Strategy (Warcraft,
Command and Conquer):
Build strongest unit (or group),
scout, attack. Actual AI is
stupid, map layout is used to
simulate strategy.
Late 1990s
- To add intrigue,
developers look again to AI
Examples:
First Person Shooters (Halflife,
Deus Ex, Unreal Tournament):
“Suicidal” AI is replaced by more
sophisticated AI that appears to
care about its own life. It
coordinates attacks, calls for
backup, and retreats when hurt.
Friendly AI can even be given
orders by the player.
Real Time Strategy: AI in the
broad scheme doesn’t evolve much
in RTS games. Individual unit
scripts are added in to some
games, but in the over all picture,
the AI still simply pours units at an
enemy until it is defeated. Perhaps
this is because of the foreignness
of the RTS paradigm, or maybe it
really is the best strategy. Most
successful human players abide by
this “rush” strategy.
• Present
- Broadband and online multiplayer games
- Highly immersive AI to contrast real players
Examples:
Multiplayer Games (Battlefield 1942): The AI in this game is outright
pitiful. While it excels at pathfinding, using tanks, planes, ships, and
other implements, it is simply not human-like behavior. Among other
things, the AI lacks a reasonable strategy. Instead of sending all of its
troops to the front lines, it distributes them equally throughout the map.
It often has trouble deciding whether it should shoot an enemy or
simply lie down and stand up repeatedly.
Immersive AI (Halo): Because of the plotline in this game, the
friendly AI acts largely autonomously. While the human player is the
“leader,” this only extends to the AI’s protection, not its obedience.
This is also reflected in the opponent AI. When attacking a group of
AI controlled enemies, if the leader is removed first, the remaining
force becomes less effective and less organized.
Current Approaches
• Rule based –
- A state machine accepts an input and produces an
output.
- Simple to implement and easy to test
- Finite state machines (FSM) are familiar concepts to
programmers
Good examples of the FSM approach are the early
first person shooters.
pseudo-code:
while(true){
if(see_player){
chase(player);
if(distance_to_player <
melee_distance){
attack(melee, player)
}else{
attack(ranged, player)
}}
- Complex FSMs become huge and unwieldy.
- Game play becomes predictable.
- Fuzzy state machines (FuSMs) introduce ambiguity
- History of states becomes relevant in decision
making for FuSMs
- Creates a more realistic but still simple state machine
• Extensible AI
- Possible solution to massive FSMs.
- Consists of a fully operational AI engine with a
modular rule base
- Separation of the AIs persona from the game code
allows the end user to modify AI behavior
- Effectively implemented in several modern games,
including Unreal.
- Issues about the amount of control the end user
should have
- Copyright issues
- Fail-safe issues
- ExAI is appropriate when a game is expected to be
heavily modified aftermarket
- Currently, users can only set parameters on preexisting AI behavior
• Learning and Behavior Development
- Instead of hard coding FSMs, let the AI learn as the
player progresses
- This fits modern compute games well: AI is weak
while the player is learning, and gradually strengthens.
- Mimics learning theories in modern psychology
- Accomplished through Neural Networks and Genetic
Algorithms
An example of how this works is the game Black
and White. In this game, the player takes the role
of a deity and has a trainable creature to assist.
Problems: There is no way to tell what the
creature is really learning:
“I thought it would be pretty neat to teach my creature the healing spell.
Since he is always kind and generous, he ran to a village to try out his new
spell. When there was no one there, the creature became upset. So he picked
someone up and threw them against the mountain. The ape then healed the
man and was happy.”
When a problem like this is found, even more
“training” is needed to clarify the intent of the
player.
Major Challenges
• Resources
- Realism in computer games focused on graphics
- Advanced graphics requires many CPU cycles
- Recent advances in computer hardware have
someone alleviated this issue.
• Deadlines
- Game engine must be developed before AI can be
tested
- AI programmers often have to compromise to meet
deadlines
• Over Intelligence
- Perfect AI would be easier to code
- It would lack believability and not be fun.
- Human-level AI should quit, surrender, or run awayeven fight to the end.
• Research and Development
- Lack of cohesion between AI research community
and game developers
- AI in modern computer games seems trivial to AI
researchers
• Human Level Intelligence
- Human level behavior will require AI
- We currently have only limited behavior
- Human level intelligence is really hard to create and
we still do not know how to achieve it
Applications
• Training Simulators
- Effective training often requires thousands of people
- Computer generated stand-ins can cut costs
• Virtual Environments
- Simulated worlds allows AI researchers to
concentrate on algorithms instead of sensors
- Again, computer generated robots are cheaper than
actual robots
• Human-level AI
- Every person is an expert on human-level
intelligence
- Testing of AI is easy
• Movies
- Crowd scenes
- Flocking behavior
- Realistic Movement
The future of Game AI
• Intelligent Landscape
- Sims weren’t smart at all
- Instead, surrounding objects contained instructinos
for use
- AI finds the object that makes them happy and
follows instructions
• Fuzzy AI
- Rule based AI is not sufficient to model human
intelligence
- Uncertain algorithms such as Genetic Algorithms
and Neural Networks are the future
• Immersive game space
- Instead of creating a reality, the AI borrows from the
real world
- Will a game AI be the first to pass the Turing Test?
Bibliography
Peterson, Ivars. “Silicon Champions of the Game.”
ScienceNewsOnline. August 2, 1997.
Wookcock, Steve. “Game AI: The State of the Industy” Game
Developer Magazine. August, 1999.
“AI in Gaming” Generation5.org.
http://www.generation5.org/app_game.shtml.
McCarthy, John. “Arthur Samuel: Pioneer in Machine
Learning.” Stanford Computer Science Computer History
Page.
Laird, John and Michael van Lent. “Human-level AI’s Killer
Application: Interactive Computer Games.” American
Association for Artificial Intelligence. 2000.
Laird, John. “Bridging the Gap Between Developers and
Researchers.” Game Developer Magazine. August 2000.
Johnson, Steven. “Wild Things.” Wired Magazine. Issue 10.03,
March 2002.