Transcript Bbm421_–_Computer_Games_Technology__7__1x

Bbm421 – Computer Games
Technology
Fall ’12
Lecture 7
By Umut Rıza ERTÜRK
Outline
• AI
• Network
Resource
Also probably of the best resources for game
development
• AI Game Engine Programming – Brain Schwab
• Dan Witzner Hansen - Lecture Notes
What is Artificial Intelligence?
(John McCarthy, Stanford University)
•What is artificial intelligence?
It is the science and engineering of making intelligent machines, especially
intelligent computer programs. It is related to the similar task of using
computers to understand human intelligence, but AI does not have to confine
itself to methods that are biologically observable.
•Yes, but what is intelligence?
Intelligence is the computational part of the ability to achieve goals in the
world. Varying kinds and degrees of intelligence occur in people, many
animals and some machines.
•Isn't there a solid definition of intelligence that doesn't depend on relating it
to human intelligence?
Not yet. The problem is that we cannot yet characterize in general what kinds
of computational procedures we want to call intelligent. We understand some
of the mechanisms of intelligence and not others.
What’s involved in Intelligence?
• Ability to interact with the real world
–
–
–
–
to perceive, understand, and act
e.g., speech recognition and understanding and synthesis
e.g., image understanding
e.g., ability to take actions, have an effect
• Reasoning and Planning
– modeling the external world, given input
– solving new problems, planning, and making decisions
– ability to deal with unexpected problems, uncertainties
• Learning and Adaptation
– we are continuously learning and adapting
– our internal models are always being “updated”
• e.g., a baby learning to categorize and recognize animals
What is AI?
What is AI in games?
•AI is (traditionally) the control of every non-human entity in a
game?
•The other cars in a car game
•The opponents and monsters in shooter games
•Your units, your enemy’s units and your enemy in a RTS
game
•But, typically does not refer to passive things that just react to
the player and never initiate action
•That’s physics or game logic
•For example, the blocks in Tetris are not AI, nor is a flag
blowing in the wind
•It’s a somewhat arbitrary distinction
Example AI Game Scenarios
• Learning the habits and preferences of a human player
in the context of game play
• Game enemy finding the shortest route to the player
• Learning and adapting avoidance algorithms during the
game
• Game enemy adaptive collaboration with other game
enemies toward a common game objective
• Generating authentic and adaptive game dialogue and
commentary e.g sports
• Generation of game environment and levels
Perception Management
1. Perceive (Sensor information)
2. Think (Evaluate perceived data)
3. Act (execute planned action)
AI Update Step
•The sensing phase determines the
state of the world
• May be very simple - state changes
all come by message
• Or complex - figure out what is
visible, where your team is, etc
AI Module
Sensing
•The thinking phase decides what to
do given the world
• The core of AI
•The acting phase tells the animation
what to do
• Generally not that interesting (for
this course)
10
Game
Engine
Thinking
Acting
AI in the Game Loop
•AI is updated as part of the game loop, after
user input, and before rendering
•There are issues here:
•Which AI goes first?
•Does the AI run on every frame?
•Is the AI synchronized?
11
AI and Animation
•AI determines what to do and the animation does it
–AI drives animation, deciding what action the animation
system should be animating
–Scenario 1: The AI issues orders like “move from A to B”,
and it’s up to the animation system to do the rest
–Scenario 2: The AI controls everything down to the
animation clip to play
•Which scenario is best depends on the nature of the AI system
and the nature of the animation system
–Is the animation system based on move trees (motion
capture), or physics, or something else
–Does the AI look after collision avoidance? Does it do
detailed planning?
12
AI by Polling
•The AI gets called at a fixed rate
•Senses: It looks to see what has changed in the
world. For instance:
•Queries what it can see
•Checks to see if its animation has finished
running
•And then acts on it
•Why is this generally inefficient?
13
Event Driven AI
•Event driven AI does everything in response to events in the
world
–Events sent by message (basically, a function gets called
when a message arrives, just like a user interface)
•Example messages:
–A certain amount of time has passed, so update yourself
–You have heard a sound
–Someone has entered your field of view
•Note that messages can completely replace sensing, but
typically do not. Why not?
–Real system are a mix - something changes, so you do
some sensing
14
Requirements for Games AI
•They need to be fast (i.e contrary to some
academic AI approaches which are ‘optimal’ –
we will give you both)
•Games do not need optimal solutions (they
need to be fun)
•Games may need to combine several
techniques
•The goal is to design agents that provide the
illusion of intelligence
15
Goals of Game AI
•Goal driven - the AI decides what it should do, and then figures out how to
do it:
•Reactive - the AI responds immediately to changes in the world
•Knowledge intensive - the AI knows a lot about the world and how it
behaves, and embodies knowledge in its own behavior
•Characteristic - Embodies a believable, consistent character
–Fast and easy development
•Games do not need optimal solutions (they need to be fun)
•Games may need to combine several techniques
•The goal is to design agents that provide the illusion of intelligenc
•Low CPU and memory usage
•These conflict in almost every way – how?
16
AI Techniques in Games
•Basic problem: Given the state of the world, what
should I do?
•A wide range of solutions in games:
–Finite state machines, Decision trees, Rule based
systems, Neural networks, Fuzzy logic
•A wider range of solutions in the academic world:
–Complex planning systems, logic programming,
genetic algorithms, Bayes-nets
–Typically, too slow for games
17
Techniques used today
•Deterministic:
•Finite State Machines
•Decision trees
•Fuzzy State machines
•Statistical:
•Baysian Approaches
•Neural Networks
•Evolutionary algorithms/ Artificial life
18
Genetic Algorithm
•
Generate a random population of potential solutions
–
–
–
–
–
•
•
Mate (crossover) selected individuals to create offspring
Replace some individuals in the population with new offspring
Apply mutation to population and evaluate against solution objective
if solution found stop
else go to step one
Use a Binary GA or Real GA to encode problem
See Haupt and Haupt (2004), Practical Genetic Algorithms for a detailed
discussion and practical examples
Searching for Optimum Solutions
• AI systems search to find an optimum solution
to a given problem
• The optimum solution may be known by the
AI system as an objective function which is
compared with a current potential solution
• Human evaluation may take place to provide
an interactive process where each potential
solution is rated as being a worthy candidate
Example AI Game Scenarios
• Learning the habits and preferences of a human player
in the context of game play
• Game enemy finding the shortest route to the player
• Learning and adapting avoidance algorithms during the
game
• Game enemy adaptive collaboration with other game
enemies toward a common game objective
• Generating authentic and adaptive game dialogue and
commentary e.g sports
• Generation of game environment and levels
Simulated AI
•
•
•
•
•
•
Random movement
Tracking algorithms (chase / evade)
Swarming
Patterns of movement
Patterns linked to states
Random patterns of movement linked to
random states
• Probabilistic states and associated movement
Finite State Machine (FSM)
• Notion of game being in one of a finite number of
states
• Behavior and direction of game logic dependant
on current state
• Ideal properties for a robust FSM
– A reasonable number of states, each of which
represents a different goal or motive within the game
– Lots of input to the FSM, such as state of the game
environment and the other objects within the game
environment
Pathfinding
• Searching for the shortest path between two points
– Search everywhere?
– Search and record the best routes - store a heuristic (cost)
• Widely used pathfinding algorithm is the A* algorithm
– A* works by assigning a cost of moving from one position
to another in terms of finding the required point
– The A* algorithm is CPU intensive - but some versions have
been optimized to reduce computational overheads
• Good examples of A* implementation in Brackeen’s
book ‘Developing Games in Java’
Fuzzy Logic
• True / False used in traditional logic
• Fuzzy logic seeks to give an input to a fuzzy
system a fuzzy truth as to its membership of
vaguely defined collections of fuzzy states.
• Fuzzy logic allows for set membership values
to range (inclusively) between 0 and 1, and in
its linguistic form, imprecise concepts like
"slightly", "quite" and "very". Specifically, it
allows partial membership in a set.
Discrete Value Ranges
Cold
Cool
Warm
Hot
1
0
-10
0
10
20
30
0C
Fuzzy Sets Heat Value Ranges
Cold
Cool
Warm
Hot
1
0
-10
0
10
20
30
0C
Fuzzy Associated Matrix
A fuzzy associated matrix FAM is a matrix that shows the
membership grades of all the elements of a fuzzy relation.
This is a convenient way to view fuzzy relations.
Fuzzy Sets Centriod
The final stage is
defuzzification into ‘crisp’
output is value derived from
a fuzzy centroid
1
0
-10
0
10
20
30
0C
Two Measures of Complexity
•Complexity of Execution
•How fast does it run as more knowledge is added?
•How much memory is required as more knowledge is
added?
•Determines the run-time cost of the AI
•Complexity of Specification
•How hard is it to write the code?
•As more “knowledge” is added, how much more
code needs to be added?
•Determines the development cost, and risk
30
Different games need different methods
•Action Games (lead a character through a set of levels)
•Fighting Games Physical combat
•Sports Games (icehockey and football)
•Racing Games (Car, bikes, speedboats)
•Adventure games ( plots based on exploration and problem
solving)
•Role Playing games (D&D)
•Board games (Chess, checkers)
•Strategic games (i.e. military type battle scenarios)
•Simulation Games (simcity)
31
Cases
•Chess: Large search trees
•Packman: Random FSM (weighted randomness)
•Smart environments: Information is not coded
in the NPC but in their environment
32
Is AI in Games really only about the players in
the game?
•What about the surroundings?
•Interaction methods?
33
AI Timeline