Programming Fundamentals
Lecture 09 – Introduction to Artificial
Intelligence
Edirlei Soares de Lima
<edirlei.lima@universidadeeuropeia.pt>
What is Artificial Intelligence?
•
Artificial intelligence is about making computers able to
perform the thinking tasks that humans and animals are
capable of.
o Computers are very good at:
arithmetic, sorting, searching, play
some board games better than
humans, ...
o Computers are not very good at:
recognizing familiar faces, speaking
our own language, deciding what to
do next, being creative, ...
What is Artificial Intelligence?
•
•
AI researchers are motivated by:
–
–
–
Philosophy: understanding the nature of thought and the nature of
intelligence and building software to model how thinking might work.
Psychology: understanding the mechanics of the human brain and
mental processes.
Engineering: building algorithms to perform human-like tasks.
Academic AI vs Game AI:
–
Academic AI: solve problems optimally, less emphasis on hardware or
time limitations;
–
Game AI: entertain player, have to work with limited time and
hardware resources.
Complexity Fallacy
•
•
It is a common mistake to think that complex AI equals better
character behavior.
When simple things look good: Pac-Man
–
Semi-randomly decisions at junctions;
–
Player comments:
•
•
“To give the game some tension, some clever AI was programmed into the game.
The ghosts would group up, attack the player, then disperse. Each ghost had its own
AI.”
“The four of them are programmed to set a trap, with Blinky leading the player into
an ambush where the other three lie in wait.”
Complexity Fallacy
•
•
It is a common mistake to think that complex AI equals better
character behavior.
When complex things look bad: Black and White [2001]
–
Neural Networks and Decision Trees allowed creatures to learn.
–
When many people first play the game, they often end up
inadvertently teaching the creature bad habits, and it ends up being
unable to carry out even the most basic actions.
Perception Window
•
Most players will only come across some characters and
enemies for a short time, which might not be enough for the
player to understand the AI.
–
Make sure that a character’s AI matches its purpose in the game and
the attention it will get from the player.
–
A change in behavior is far more noticeable than the behavior itself.
Illusion of Intelligence
•
•
“If it looks like a fish and smells like a fish, it’s probably a fish.”
–
if the player believes an agent is intelligent, then it is intelligent.
For game AI the nature of the human mind is not the key
point.
–
The AI characters must look right and demonstrate intelligent
behavior.
•
Sometimes, simple solutions are enough to create a good
illusion of intelligence.
–
Halo [2001] – increasing the number of hit points required to kill
enemies made testers thought the AI was very intelligent.
Illusion of Intelligence
•
•
Player’s perception of intelligence can be enhanced by
providing visual and/or auditory clues about what the agent is
“thinking”.
Animation is an excellent way to create a good illusion of
intelligence.
–
The Sims [2000] – although it uses a complex emotional model for
characters, most part the characters’ behaviors is communicated with
animations.
–
Triggering animations at the right moment is the key point.
Illusion of Intelligence
•
•
The goal of game developers is to design agents that provide
the illusion of intelligence, nothing more.
Game developers rarely create great new algorithms and then
ask themselves, “So what can I do with this?”
–
Instead, they start with a design for a character and apply the most
relevant tool to get the result.
•
Be careful to never break the illusion of intelligence:
–
Running into walls, getting stuck in corners, not reacting to obvious
stimulus, seeing through walls, hearing a pin drop at 500 meters, …
Game AI – Model
Most Common Techniques
•
•
•
•
•
•
•
•
Pathfinding
Steering behaviours
Finite state machines
Automated planning
Behaviour trees
Randomness
Sensor systems
Machine learning
Randomness in Games
•
Game programmers have a special relationship with random
numbers. They can be used for several tasks:
–
–
–
–
–
–
–
–
–
–
Damage calculation;
Critical hits probability;
Item drop probability;
Reward probability;
Enemy stats;
Spawning enemies and items;
Shooting spread zones;
Decision making;
decision = love.math.random(min, max)
Procedural content generation;
…
Randomness and Probability
•
Although most programming languages include functions to
generate pseudo-random numbers, there are some situations
where some control over the random numbers is extremely
important.
–
–
Gaussian Randomness: normal distribution of random numbers.
Filtered Randomness: manipulation of random numbers so they
appear more random to players over short time frames.
–
Perlin Noise: consecutive random numbers that are related to each
other.
Gaussian Randomness
•
Normal distributions (also known as Gaussian distributions)
are all around us, hiding in the statistics of everyday life.
Height of Trees
Height of People
Gaussian Randomness
•
Normal distributions (also known as Gaussian distributions)
are all around us, hiding in the statistics of everyday life.
Speed of Runners in a Marathon
Speed of Cars on a Highway
Gaussian Randomness
•
•
There is randomness in previous examples, but they are not
uniformly random.
Example:
–
The chance of a man growing to be 170 cm tall is not the same as the
chance of him growing to a final height of 150 cm tall or 210 cm tall.
–
We see a normal distribution with the height of men centered around
1
70 cm.
Gaussian Randomness
•
Normal Distribution vs. Uniform Distribution:
Normal Distribution
Uniform Distribution
Gaussian Randomness
•
How Gaussian randomness can be generated?
–
Löve function to generate Gaussian random numbers:
function love.draw()
for x = 0, 300, 1 do
love.graphics.circle("fill", love.math.randomNormal(80, 400),
love.math.randomNormal(80, 300), 3)
end
end
Exercise 1
1
) Create a random population of 50 characters whose
height follow a normal distribution.
–
You must store the information of the characters in a array.
–
The characters can be visually represented as rectangles.
Finite State Machines
•
Usually, game characters have a limited set of possible
behaviors. They carry on doing the same thing until some
event or influence makes them change.
–
Example: a guard will stand at its post until it notices the player, then it
will switch into attack mode, taking cover and firing.
•
•
State machines are the technique most often used for this
kind of decision making process in games.
What is a state machine?
Finite State Machines
•
•
Actions or behaviors are associated
with each state.
Each transition leads from one state
to another, and each has a set of
associated conditions.
•
•
When the conditions of a transition
are met, then the character changes
state to the transition’s target state.
Each character is controlled by one
state machine and they have a
current state.
Hard-Coded Finite State Machines
local PATROL, DEFEND, SLEEP = 1, 2, 3
local state = PATROL
function UpdateState()
if state == PATROL then
if canSeePlayer() then
state = DEFEND
if tired() then
state = SLEEP
end
end
elseif state == DEFEND then
if not canSeePlayer() then
state = PATROL
end
elseif state == SLEEP then
if not tired() then
state = PATROL
end
end
end
Exercise 2
2
) Implement a finite state machine to control an NPC based on
the following diagram:
[
can see the player]
Patrol
Chase
[
can’t see the player]
Attack
Pathfinding
•
Game characters usually need to move around their level.
•
While simple movements can be manually defined by game
developers (patrol routes or wander regions), more complex
movements must be computed during the game.
Pathfinding
•
Finding a path seems obvious and natural in real life. But how
a computer controlled character can do that?
–
The computer needs to find the “best” path and do it in real-time.
Search Problem
•
•
Pathfinding is a search problem: find a sequence of actions
from an initial state to an goal state.
Problem definition:
–
–
–
–
–
Initial state
Goal state
State space
Set of actions
Cost functions
Example of Search Problem
•
Route-finding:
–
–
–
–
State space: map;
Initial state: current city;
Goal state: destination city;
Set of actions: go from one city to another (only possible if there is a
path between the cities);
–
Action cost: distance between the cities;
General Pathfinding Problems
•
State space: waypoint graphs or
tiled-based maps;
A
•
•
•
•
Initial state: current location (A);
Goal state: destination location (B);
Set of actions: movements;
B
Action cost: distance or terrain
difficulty;
Navigation Graph
•
Pathfinding algorithms can’t work directly on the level
geometry. They rely on a simplified version of the level,
usually represented in the form of a graph.
General Graph Structure
Edge
•
G = (V, E)
–
–
–
G: graph;
V: set of vertices;
E: set of edges;
Vertex
General Graph Structure
•
Weighted graph: directed on undirected graph in which a
number (the weight) is assigned to each edge.
Navigation Graph
•
Tiled-based maps can also be seen as graphs:
A
A
B
B
memory data:
0
0
1
1
0 0 0 1 1 1
0 0 0 1 1 1
0 0 1 0 0 1
1 0 0 0 0 0
Pathfinding
•
•
With the navigation graph in hands, how can we find the best
path to go from one point to another?
–
Graph search algorithms!
There are many graph search algorithms:
–
–
–
–
–
Breadth-first search (BFS)
Depth-first search (DFS)
Dijkstra algorithm
A* algorithm
…
Pathfinding / A* Algorithm – Example