Oradea
Straight−line distance
71 to Bucharest
Neamt Arad 366
87 Bucharest 0
Zerind 151
75 Craiova 160
Iasi Dobreta 242
Arad 140 Eforie 161
92 Fagaras 178
Sibiu 99 Fagaras Giurgiu 77
118
Vaslui Hirsova 151
80
Iasi 226
Rimnicu Vilcea
Timisoara Lugoj 244
142 Mehadia 241
111 211 Neamt
Lugoj 97 Pitesti 234
Oradea 380
70 98 Pitesti 98
Hirsova
Mehadia 146 101 85 Urziceni Rimnicu Vilcea 193
75 138 86 Sibiu 253
Dobreta
120
Craiova
90Bucharest Timisoara
Urziceni
Vaslui
329
80
199
Eforie
Giurgiu Zerind 374
GREEDY SEARCH AND A*
• Greedy Search
• A*
GAMES & ADVERSARIAL
SEARCH
Chapter 5
Section 1 – 4
• In which we examine the problems that arise
when we try to plan ahead in a world where
other agents are planning against us.
• Games have engaged the intellectual faculties of humans—
sometimes to an alarming degree—for as long as civilization
has existed.
• For Al researchers, the abstract nature of games makes them an
appealing subject for study.
• The state of a game is easy to represent, and agents are usually
restricted to a small number of actions whose outcomes are
defined by precise rules.
GAMES VS. SEARCH PROBLEMS
• "Unpredictable" opponent specifying a move for
every possible opponent’s reply.
• Time limits unlikely to find goal, one must
approximate
deterministic chance
perfect information chess, checkers, backgammon
go, othello monopoly
imperfect information battleships, bridge, poker, scrabble
blind tictactoe nuclear war
MAX (X)
X X X
MIN (O) X X X
X X X
XO X O X ...
MAX (X) O
XO X X O X O ...
MIN (O) X X
... ... ... ...
XO X X O X X O X ...
TERMINAL O X OO X X
O X X X
O O O
Utility −1 0 +1
How do we search this tree to find the optimal move?
Minimax value is
computed MAX 3
bottom up: A A A
1 2 3
-Leaf values are given.
-3 is the best outcome MIN 3 2 2
for MIN in this branch.
-3 is the best outcome A AA12 A A A A A A
11 13 21 22 23 31 32 33
for MAX in this game.
-We explore this tree 3 12 8 2 4 6 14 5 2
in depth-first manner.
USEFUL DEFINITION
• Pruning: ignore portions of the search tree that make no
difference to the final choice.
• Heuristic Evaluation Function: allow to approximate the
true utility of a state without doing a complete search.
• Do we need to expand all nodes?
• No: We can do better by pruning branches that will not lead
to success.
Α-Β PRUNING EXAMPLE
MAX knows that it can at least
get “3” by playing this branch
MIN will choose “3”, because it minimizes the
utility (which is good for MIN)
Α-Β PRUNING EXAMPLE
MAX knows that the new branch
will never be better than 2 for him.
He can ignore it.
MIN can certainly do as good as
2, but maybe better (= smaller)
Α-Β PRUNING EXAMPLE
MIN will do at least as good as 14 in this branch
(which is very good for MAX!) so MAX will want
to explore this branch more.
Α-Β PRUNING EXAMPLE
MIN will do at least as good as 5 in this branch
(which is still good for MAX) so MAX will want
to explore this branch more.
Α-Β PRUNING EXAMPLE
Bummer (for MAX): MIN will be able
to play this last branch and get 2. This
is worse than 3, so MAX will play 3.
MAX
MIN
..
..
..
MAX
MIN
V
PROPERTIES OF
• Pruning does not affect final result (it is exact).
• Good move ordering improves effectiveness of pruning
(see last branch in example)
• With "perfect ordering," time complexity = O(bm/2)
doubles depth of search
PRACTICAL IMPLEMENTATION
How do we make this practical?
Standard approach:
• cutoff test: (where do we stop descending the tree)
• depth limit
• better: iterative deepening
• cutoff only when no big changes are expected to occur next (quiescence search).
• evaluation function
• When the search is cut off, we evaluate the current state
by estimating its utility. This estimate if captured by the
evaluation function.
EVALUATION FUNCTIONS
• For chess, typically linear weighted sum of features
Eval(s) = w1 f1(s) + w2 f2(s) + … + wn fn(s)
• e.g., w1 = 9 with
f1(s) = (number of white queens) – (number of black
queens), etc.
AI IN GAMES
Types of AI in games
Heuristics
• Common Heuristics
– Most Constrained
– Do the most difficult thing first
– Try the most promising thing first
Algorithms
Roles or functions played in AI-based games:
Path following Decision making
Collision avoidance Tactical analysis
Finding paths Terrain analysis
World Representations Coordinating action
Movement planning
Learning
Search Tree in Games?
Game playing systems rely heavily on the
search techniques
It combines the search technique with a
number of heuristics & detailed database of
knowledge about the game
This chapter will describe the Minimax and
Alpha-Beta concepts of searching Game trees
BOARD GAMES
Best AI agents for Chess, Backgammon and
Reversi employ dedicated hardware, algorithms
and optimizations.
Basic underlying algorithms are common across
games.
Most popular AI for board games is minimax family.
Recently Memory-enhanced test driver (MTD)
algorithms are gaining favor.
GAME PLAYING
A second player (or more) is an adversary
Examples: chess, checkers, go, tic-tac-toe, connect
four, backgammon, bridge, poker
Adversarial search.
Players take turns or alternate play
Unpredictable opponent.
Solution specifies a move for every possible opponent
move.
Turn time limits
How might they affect the search process?
TYPES OF GAMES
deterministic chance
chess, checkers,
perfect connect four, backgammon
information othello
imperfect bridge, poker,
information scrabble
EXAMPLE GAME: NIM
Deterministic, Opposite Turns
Two players
One pile of tokens in the middle of the table.
At each move, the player divides a pile into
two non-empty piles of different sizes.
Player who cannot move looses the game.
EXAMPLE GAME: NIM
Assume a pile of seven tokens. min
7
Max attempts to
maximize the 6-1 5-2 4-3 max
advantage and win.
5-1-1 4-2-1 3-2-2 3-3-1 min
Min always tries to
move to a state that is
the worst for Max.
4-1-1-1 3-2-1-1 2-2-2-1 max
3-1-1-1-1 2-2-1-1-1 min
2-1-1-1-1-1 max
PERFECT DECISION, TWO PERSON GAMES
Two players
MAX and MIN
MAX moves first; alternate turns thereafter.
Formal definition of game
Initial State
Successor Function
Terminal Test
Utility Function
No one player has full control, must develop a
strategy.
MINIMAX ALGORITHM: BASICS
3 MAX
3 0 2 MIN
3 9 0 7 2 6 MAX
MIN
2 3 5 9 0 7 4 2 1 5 6
Process of Backing up: minimax decision
Assumption: Both players are knowledgeable and play
the best possible move
MINIMAX ALGORITHM
• Generate game tree to all terminal states.
• Apply utility function to each terminal state.
• Propagate utility of terminal states up one level.
• MAX’s turn: MAX tries to maximize utility value.
• MIN’s turn: MIN minimizes utility value.
• Continue backing-up values toward root, one
layer at a time.
• At root node, MAX chooses the value with
highest utility.
MINIMAX SEARCH
• What is the time complexity of the minimax
algorithm?
• Minimax decision: maximizes utility for a player
assuming that the opponent will play perfectly
and minimize its utility.
– m – looking ahead m moves in game tree
– Search can be done in a depth first manner
• i.e. traverse down a path till terminal node reached, then
back up value using minimax decision function.
PARTIAL SEARCH
What were our concerns with the other
search algorithms we have discussed?
How do those concerns apply to games?
•Full game tree may be too large to generate.
EXAMPLE: PARTIAL SEARCH FOR TIC-TAC-TOE
Generate tree to intermediate depth.
Calculate utility/evaluation function for leaf
nodes.
Back up values to the root node so MAX
player can make a decision.
EXAMPLE: PARTIAL SEARCH FOR TIC-TAC-TOE
Position p:
win for Max, u(p) =
loss for MAX, u(p) =–
otherwise, u(p) = (# of
complete rows, cols, &
diags still open for MAX) –
(# of complete rows, cols,
and diags still open for MIN)
TIC-TAC-TOE: 2ND MOVE
MAX PLAYER: 3RD MOVE
MAX PLAYER: 3RD MOVE
Search starts
depth first
Back up value
immediately
Do not
need to
generate
MIN these
nodes!
The alpha-beta pruning Why?
procedure Node A generated
COMPLEX GAMES
What happens if Minimax is applied to large
complex games?
– What happens to the search space?
Example, chess:
decent amateur program 1000 moves /second
150 seconds /move (tournament play)
Look at approx. 150,000 moves
Chess branching factor of 35
generating trees that are 3-4 ply,
Resultant play – pure amateur
Can we make search process more intelligent, and
explore more promising parts of tree in greater
depth?
ALPHA-BETA PRUNING
Definitions
value – lower bound on MAX node
value – upper bound on MIN node
Observations
value on MAX nodes never decrease
values on MIN nodes never increase
Application
Search is discontinued below any MIN node with min-
value v : cut off
Search is discontinued below any MAX node with
max-value v : cut off
ALPHA-BETA SEARCH EXAMPLE
a MAX
b c MIN
d e f g MAX
MIN
1 2 3 4 5 7 1 0 2 6 1 5
ALPHA-BETA SEARCH ALGORITHM
Computing and
value of MAX node = current largest final
backed-up value of its successors.
value of MIN node = current smallest final
backed-up value of its successors.
ALPHA-BETA SEARCH ALGORITHM
Start with AB(n; -, +)
Alpha-Beta-
Search(state) returns
an action
v = MAX-VALUE(state,-
∞, +∞)
MAX-VALUE(state, , ) return the action
MIN-VALUE(state, , ) in
if TERMINAL-TEST(state) then SUCCESSORS(state) then
if TERMINAL-TEST(state)
return UTILITY(state) with value
return v
UTILITY(state)
v = -∞ v = +∞
for a, s in SUCCESSORS(state) do for a, s in SUCCESSORS(state) do
v = MAX(v, MIN-VALUE(s, v = MIN(v, MAX-VALUE(s,
)) ))
if v >= then return v if v <= then return v
= MAX(, v) = MIN(, v)
return v (a utility value) return v (a utility value)
ALPHA-BETA SEARCH PERFORMANCE
Uses depth-first search procedure
Search effectiveness depends on node
ordering
Worst case occurs if worst moves generated first
Best case occurs if best moves generated first:
min value first for MIN nodes, and max value
first for MAX nodes.
(Is this always possible?)
ALPHA-BETA SEARCH
PERFORMANCE
Search tree of depth d, b moves per node
– bd tip nodes: Minimax search - O(bd)
– Best case:
• look at only O(bd/2) tip nodes
• Effective branching factor reduces to b so can double the
depth of the search.
– Average case:
3d
• Number of nodes examined: O(b 4
) Pruning does not
• Search depth increase 4/3
affect final result
GAMES WITH CHANCE
Example, Games with dice
– Backgammon: white can decide what his/her
legal moves are, but can’t determine black’s
because that depends on what black rolls.
Game tree must include chance nodes.
How to pick best move?
– Cannot apply minimax directly.
GAMES WITH CHANCE
For each possible move, compute
an average or expected value.
Expectiminimax(n) UTILITY (n) if n is a terminal
max Expectiminimax(s) state if n is a Max
sSuccessors ( n )
min Expectiminimax(s)
sSuccessors ( n )
node
if n is a Min node
sSuccessors(n)
P(s)*Expectiminimax(s) if n is a chance node
Complexity – O(bmnm) where n is the number of distinct
values (e.g. dice rolls)
EXPECT MAX EXAMPLE
AI GAMES - MODEL
AI is given processor time
Execution Management
AI receives
Group
information AI
Strategy Content Creation
Character
Scripting
AI
Decision Making AI has implications
for Related
technologies
Movement
Animation Physics
AI is turned into on-screen
action
AI GAMES – SCHEMATIC DIAGRAM
Content Main Game Engine AI Engine
Construction
AI specific AI data is used to Behavior
tools construct characters database
Modeling
World
package
Interface
Level Loader
World interface
Extracts relevant
Game data
Level design AI
tool behavior
Game engine
Calls AI each manager
frame
Per-frame AI receives data
processing from the game and
Results of AI from its
Are written back internal information
To game data
Package level
data
EXERCISES ON
MINIMAX & ALPHA-BETA
EXERCISE MINIMAX
MAX
MIN
MAX
MIN
1 2 3 4 0 5 4 2 1 6 3
EXERCISE FOR ALPHA-BETA SEARCH
a MAX
b c MIN
d e f g MAX
h i j k l m n MIN
MAX
5 7 2 0 1 2
5 4 2 4 3 0 2 8