Transcript What is AI in Games?

Artificial Intelligence in Games
Juthawut Chantharamalee
Computer Science: SDU
1
What is AI in Games?


Techniques used in computer and video games to
produce the illusion of intelligence in the behavior
of non-player characters
A game must ‘feel’ natural
–
–
–
–
–


Obey laws of the game
Characters aware of the environment
Path finding (A*)
Decision making
Planning
Game ‘bookkeeping’, scoring
~50% of project
time building AI
2
Computer Game Types

Strategy games
– Real Time Strategy (RTS)
– Helicopter view


Role Playing Games (RPG)
Action games
– First person shooter (FPS)
– Sports games
3
Goals of Game AI

Be ‘fun’
– Reasonable challenge with natural behavior

No Cheating!
– AI has bonuses over human players such as:




Giving more damage
Having more health
Driving faster
Etc.
– Used to increase difficulty
– Draws away focus to program more human-like bots.


Run fast
Use minimal memory
4
Game AI History -1980

1960’s
– First computer games (SpaceWar)
– Board games against the computer (Chess)

1970’s
– Atari (1972)


Nolan Bushnell
Pong
– First AI implemented into games


Stored patterns
Space Invaders (1978)
– Distinct moving patterns

Galaxian (1979)
– More complex and varied enemy
movements
– 1-2% of CPU time spent on AI
5
Game AI History 1980
1980’s
– Fighting games

Karate Champ (1984)
– AI defeated a human player in chess for
the first time (1983)
– Pac-Man (1980)
6
Game AI History 1980
1990’s
– Sports games

Madden Football
– FPS and RTS games

RTS games had problems
–
–
–
–

Path finding
Decisions
Many more
Dune II: Enemy attacked in a
bee line and used cheats
RTS games did get better
– WarCraft
 First game to implement
path-finding at such a
large scale
7
Game AI History 1980
1990’s (cont.)
– Finite state machines
– Neural networks

Battlecruiser 3000AD (1996)
– Deep Blue defeats chess champ Gary Kasparov (1997)



Chess playing computer developed by IBM
Inspires AI developers
http://www.research.ibm.com/deepblue/games/game6/html/c.2.sht
ml
– Graphic cards allowing for more CPU time
– 10-35% of CPU time spent on AI
8
Game AI History 1980
2000’s
– More games using neural networks


Black & White (2001)
Collin McRae Rally 2 (2001)
– Hyperthreading

More sophisticated AI engines while simultaneously
creating a more realistic 3D environment
– Core Duo

Even more complex AI engines
9
AI in Different Game Types

FPS & RPG
– AI is in opponents, teammates, and extra
characters

RTS
– AI on all sides

Sports Games
– AI is in opponents and teammates
10
AI in FPS-type Games

Layered AI Structure
– Bottom layers = trivial

Determine paths
– Top layers = non-trivial


Reasoning and behavior
Event Driven Engine
– Action based on events
– Good Idea to use leaking
buckets to make more
flexible

Leaking Buckets
– Buckets leak contents over time
– Script with the most filled bucket gets executed
11
AI in FPS-type Games Cont.

Path-Finding
– Based on graphs describing the world

A(*)
– Most commonly used
– Guaranteed to find shortest path

Animation System
– Play appropriate sequence of animation at the chosen
speed
– Play different animation sequences for different body parts
(i.e. run and aim, and shoot and reload weapon while still
running)
– Inverted kinematics

Process of computing the pose of a human body from a set
of constraints
– i.e. An IK animation system can appropriately calculate the
parameters of arm positioning animation so that the hand can
12
grab an object located on a table or shelf
Representation of the World
in an FPS-type Game
13
AI in RTS-type Games

Path-Finding
– Handle collisions
– A(*)


Event Driven Engine
Maps Represented by a Rectangular Grid
– Module that analyzes the game map uses a goal driven
engine




Take highest rank goal and process it.
Smaller sub-goals are created as needed and are processed
until the goal has been fulfilled.
Analyzes terrain and a settlement is built based on evaluation
of the terrain
Decides when cities should be built and how reinforcements
should be placed
14
AI in RTS-type Games Cont.

Interaction between event driven and goal driven
engine example:
– A building gets blown up by an air strike
– This sparks the event based engine to give a new goal to
the goal based engine to increase air defenses
– The goal based engine responds by moving units that are
capable of air defense into position.
15
Representation of the World
in an RTS-type Game
16
AI in RPG-type Games

Little AI
– Random encounters

More common in games where fighting and
gaining levels is more important
– Scripted behavior
Often coupled with some minor AI
 Common in games depending more on their
story line than other things

– Often a combination of both
17
AI in Sports Games


Cheating
Racing games
– Segmentation




Track gets split into small sectors.
Each element gets its length calculated
Fragments used to obtain characteristics of the road in the
vehicle’s closest vicinity
In effect, the computer knows it should slow down because
it’s approaching a curve or an intersection
– Optimization



Two curves are marked on the track
First represents the optimal driving track
Second represents the track used when overtaking
opponents
– AI system must analyze terrain

Detect obstacles lying on the road
18
AI in Sports Games Cont.

Racing games (cont.)
– Strict co-operation with physics module
Physics module provides information such as
when the car is skidding
 The AI system, having received the
information that the car is skidding, should
react appropriately and try to get the
vehicle’s traction back under control

19
Popular AI Algorithms
Used In Computer Games



A(*)
Finite State Machines
Artificial Neural Networks
20
A(*) Algorithm


Goal: Find shortest path
Prerequisites
– Graph
– Method to estimate distance between points (heuristic)

Basic Method
– Try all paths?

Takes time
– Orient search towards target



Minimizes areas of the map to be examined
Uses heuristics that indicate the estimated cost of getting to
the destination
Main advantage
21
A(*) Algorithm

Algorithm
– Open list

Nodes that need to be considered as possible starts for
further extensions of the path
– Closed list

Nodes that have had all their neighbors added to the open
list
– G score



Contains the length or weight of the path from the current
node to the start node
Low lengths are better
Every node has a G score
– H score



Heuristic
Resembles G score except it represents an estimate of the
distance from the current node to the endpoint
To find shortest path, this score must underestimate the
distance
22
A(*) Algorithm

Algorithm (cont.)
– Start with an empty closed list and just
the starting point in the open list
– Every node has a G score and the node
that was used to arrive at this node
(Parent node)
23
A(*) Algorithm

Algorithm (cont.)
– Extend the path





Calculate the H scores of the nodes in the open list using a
heuristic method.
Pick the node (P) in the open list for which the sum of the G
and H scores is the lowest. Note: If the open list is empty
then no path
For every point adjacent to P not in the closed or open list,
add it to the open list. The previous nodes for these new
nodes is P, and their G score is the G score of P plus the
distance between the new node and P. If it was already in
the open list, check it’s current G score, and if the new G
score would be less than the current one update the G score
and previous node, otherwise leave it alone.
If the new point is the destination point, you have found
your path.
Move P to the closed list and start over
24
A(*) Algorithm

Example:
– Manhattan method

Calculate total # of squares moved
horizontally and vertically to reach target,
ignoring diagonal movement and obstacles.
25
A(*) Algorithm

Example (cont.):
26
A(*) Algorithm

Example (cont.): Notice: 2 squares = 54
– Can be faster to choose last one added to the open list

This biases the search in favor of squares that get found later on in
the search, when you have gotten closer to the target
27
A(*) Algorithm

Example (cont.):
28
A(*) Algorithm

Example (cont.):
29
A(*) Algorithm

Example (cont.):
30
Finite State Machines

Each object in a game can have a number of states during its
life.
– i.e. patrolling, attacking, resting, etc.

Model of behavior composed of:
– States

Stores information about the past, i.e. it reflects the input changes
from the system start to the present moment
– Transitions

Indicates a state change and is described by a condition that would
need to be fulfilled to enable the transition
– Actions

Entry action
– executed when entering the state

Exit action
– executed when exiting the state

Input action
– executed depending on present state and input conditions

Transition action
– executed when performing a certain transition
31
Finite State Machines Cont.

Advantage: Can divide
implementation of each games
object’s behavior into smaller
fragments
– Easier to debug and extend
32
Finite State Machines

State Diagram
33
Finite State Machines
Example: Pacman Ghost
34
Artificial Neural Networks

Brain
– Receives input
– Processes input
– Communicates the output

Relies on the cooperation of the individual neurons within the
network to operate
– If some neurons are not functioning, the network can still
perform its overall function

Trainable
– Learn to solve complex problems from a set of examples
– Generalizes the “acquired knowledge” to solve unforseen
problems
35
Artificial Neural Networks
36
Artificial Neural Networks

Neural Networks in Games?
– Trendy topic in the late 90’s into 00’s

Huge potential in computer games
– Collin McRae Rally 2 (2001)




Total success
The trained artificial neural network is responsible for
keeping the computer player’s car on the track while letting it
negotiate the track as quickly as possible
Input parameters: curvature of the road’s bend, distance
from the bend, type of surface, speed, or the vehicles
properties
Output: selected in a way so that the car travels and
negotiates obstacles or curves at a speed optimal for the
given conditions.
37
Artificial Neural Networks

Obstacles Limiting Neural Networks’
Application in Games
– Problems choosing appropriate input
– Neural network’s sensitivity to changes in a
game’s action logic, and the need for re-training
the network whenever such a situation occurs
– Rather complicated theory, and difficulties with
debugging in case of problems
– Time-consuming and complicated process of
training the network
38
Artificial Neural Networks

How to take advantage of an artificial neural network in a
simple game?
– Need to know what kinds of information the neural network
should provide to help solve the problem
– Choose input parameters


Choose in a way that its different combinations will let the neural
network learn to solve problems which haven’t appeared in the
example set of signals
Should represent as much information about the game world as
possible
– i.e. vectors of relative positions of the nearest obstacle or opponent, the
enemies strength, etc.
– Acquire set of input data for training

Significant effort
– Train the neural network

Mixed with simultaneous testing to make sure the game is not too
difficult, or if too easy and in need of further training
39
Artificial Neural Networks

Fuzzy logic
– Often used with neural networks
– Conversion from computer’s reasoning into
something more strongly resembling the way a
human thinks
– Usually in the form:

IF variable IS set THEN action
– i.e.


IF road IS dry THEN maintain normal speed
IF road IS wet THEN slow down
40
Conclusion

Games With No AI?
– Not possible!
– Every game with computer controlled
characters/opponents uses some sore of AI


Game AI has come a long way since the
1970s
Future looks bright
– Neural networks are the future of computer
games and a future that is not that distant
anymore
41
References
1)
2)
3)
4)
5)
Grzyb, Janusz. Artificial Intelligence in Games. Software
Developer’s Journal. June 2005.
Game Artificial Intelligence. Wikipedia Ecyclopedia.
September 7, 2006.
http://en.wikipedia.org/wiki/Game_artificial_intelligence
Petersson, Anders. Artificial Intelligence in Games.
WorldForge Newsletter. August 2001.
http://worldforge.org/project/newsletters/August2001/AI/#
SECTION00020000000000000000
Popovic, Zoran; Martin, Steven; Hertzmann, Aaron;
Grochow, Keith. Style-Based Inverse Kinematics. 2004.
http://grail.cs.washington.edu/projects/styleik/styleik.pdf
A*. The Game Programming Wiki. September 15, 2006.
http://gpwiki.org/index.php/A_star
42
The End Lesson 10
43