CSE 412: Artificial Intelligence

Topic – 5: Game Playing

Department of CSE
Daffodil International University
 Topic Contents
● Case Studies: Playing Grandmaster Chess

● Game Playing as Search

● Optimal Decisions in Games

● Greedy search algorithm
● Minimax algorithm

● Alpha-Beta Pruning
 Case Studies: Playing
Grandmaster Chess
● The real success of AI in game-playing was achieved much later
after many years’ effort.
● It has been shown that this search based approach works
extremely well.
● In 1996 IBM Deep Blue beat Gary Kasparov for the first time. and
in 1997 an upgraded version won an entire match against the
same opponent.

3
 Case Studies: Playing
Grandmaster Chess…
Kasparov vs. Deep Blue, May 1997
● 6 game full-regulation match sponsored by ACM
● Kasparov lost the match 1 wins to 2 wins and 3 tie
● This was a historic achievement for computer chess
being the first time a computer became
the best chess player on the planet.
● Note that Deep Blue plays by “brute force” (i.e. raw power
from computer speed and memory). It uses relatively
little that is similar to human intuition and cleverness.

4
 Game Playing and AI
● Why would game playing be a good problem for AI
research?
– game playing is non-trivial
●players need “human-like” intelligence
●games can be very complex (e.g. chess, go)
●requires decision making within limited time
– game playing can be usefully viewed as a search problem
in a space defined by a fixed set of rules
●Nodes are either white or black corresponding to reflect the
adversaries’ turns.
●The tree of possible moves can be searched for favourable positions.

5
 Game Playing and AI…
● Why would game playing be a good problem for AI
research?
– games often are:
●well-defined and repeatable
●easy to represent
●fully observable and limited environments
– can directly compare humans and computers

6
 Game Playing as Search
●Consider two-player, turn-taking, board games
– e.g., tic-tac-toe, checkers, chess

●Representing these as search problem:

– states: board configurations
– edges: legal moves
– initial state: start board configuration
– goal state: winning/terminal board configuration

7
 Game Playing as Search:
Game Tree
●What's the new aspect
to the search problem?
…
There’s an opponent X X X
that we cannot control!
X

…
XO X O X X
O
O

…
XX X
X X

O X
X O XO

How can this be handled?

8
 Game Playing as Search:
Complexity
● Assume the opponent’s moves can be
predicted given the computer's moves.

● How complex would search be in this case?

d
– worst case: O(b ) ; b is branching factor, d is depth
– Tic-Tac-Toe: ~5 legal moves, 9 moves max game
9
●5 = 1,953,125 states
– Chess: ~35 legal moves, ~100 moves per game
100 154 40
●35 ~10 states, but only ~10 legal states

● Common games produce enormous search trees.

9
 Greedy Search Game Playing

● A utility function maps each terminal state of the

board to a numeric value corresponding to the
value of that state to the computer.

– positive for winning, > + means better for computer

– negative for losing, > - means better for opponent
– zero for a draw
– typical values (lost to win):
●-infinity to +infinity
●-1.0 to +1.0

10
11
 Greedy Search Game Playing
●Expand each branch to the terminal states
●Evaluate the utility of each terminal state
●Choose the move that results in the board
configuration with the maximum value
A
A
9 computer's
possible moves
B
B C
C D
D E
E
-5 9 2 3
opponent's
possible moves
F
F G
G H
H II J
J K
K L
L2 M
M N
N O
O
-7 -5 3 9 -6 0 1 3 2
board evaluation from computer's perspective terminal states

12
 Greedy Search Game Playing
●Assuming a reasonable search space,
what's the problem with greedy search?
It ignores what the opponent might do!
e.g. Computer chooses C. Opponent
chooses J and defeats computer.
A
9 computer's
possible moves
B C D E
-5 9 2 3
opponent's
possible moves
F G H I J K L M N O
-7 -5 3 9 -6 0 2 1 3 2
board evaluation from computer's perspective terminal states

13
 Minimax: Idea

●Assuming the worst (i.e. opponent plays

optimally):
given there are two plays till the terminal states
– If high utility numbers favor the computer
● Computer should choose which moves?
maximizing moves
– If low utility numbers favor the opponent
● Smart opponent chooses which moves?
minimizing moves

14
 Minimax: Idea
●The computer assumes after it moves the
opponent will choose the minimizing move.
● It chooses its best move considering
both its move and opponent’s best move.
AA
1 computer's
possible moves
B
B C
C D
D E
E
-7 -6 0 1
opponent's
possible moves
F G H I J K L M N O
-7 -5 3 9 -6 0 2 1 3 2
board evaluation from computer's perspective terminal states

15
 Minimax: Passing Values up
Game Tree
●Explore the game tree to the terminal states
●Evaluate the utility of the terminal states
●Computer chooses the move to put the board
in the best configuration for it assuming
the opponent makes best moves on her turns:
– start at the leaves
– assign value to the parent node as follows
● use minimum of children when opponent’s moves
● use maximum of children when computer's moves

16
 Deeper Game Trees
●Minimax can be generalized for > 2 moves
●Values backed up in minimax way
A
A
3 computer max
B
B C
C D E
E
-5 3 0 -7
opponent
F G H I J K L M min
F
4 -5 3 8 J
9 K
5 2 M
-7
computer
N O P Q R S T U V max
4 O
-5 9 -6 0 3 5 -7 -9
opponent
W X min terminal states
-3 -5

17
 Minimax: Direct Algorithm

For each move by the computer:

● Perform depth-first search to a terminal state
● Evaluate each terminal state
● Propagate upwards the minimax values
if opponent's move minimum value of children backed up
if computer's move maximum value of children backed up
● choose move with the maximum of minimax values of children

Note:
● minimax values gradually propagate upwards as DFS proceeds: i.e., minimax
values propagate up
in “left-to-right” fashion
● minimax values for sub-tree backed up “as we go”,
so only O(bd) nodes need to be kept in memory at any time

18
 Minimax: Algorithm Complexity
Assume all terminal states are at depth d
●Space complexity?
depth-first search, so O(bd)
●Time complexity?
d
given branching factor b, so O(b )
●Time complexity is a major problem!
Computer typically only has a
finite amount of time to make a move.

19
 Minimax: Algorithm Complexity
● Direct minimax algorithm is impractical in practice
– instead do depth-limited search to ply (depth) m

● What’s the problem for stopping at any ply?

– evaluation defined only for terminal states
– we need to know the value of non-terminal states

● Static board evaluator (SBE) function uses heuristics

to estimate the value of non-terminal states.
● It was first proposed by Shannon in his paper,
Programming a computer for playing chess, in 1950.

20
 Minimax:
Static Board Evaluator (SBE)
● A static board evaluation function estimates how
good a board configuration is for the computer.
– it reflects the computer’s chances of winning from that
state
– it must be easy to calculate from the board configuration
● For Example, Chess:
SBE = α * materialBalance + β * centerControl + γ * …
material balance = Value of white pieces - Value of black pieces
(pawn = 1, rook = 5, queen = 9, etc).

21
 Minimax:
Static Board Evaluator (SBE)
● How to design good static board evaluator functions?
● First, the evaluation function should order the
terminal states in the same way as the true utility
function; otherwise, an agent using it might select
suboptimal moves even if it can see ahead all the way
to the end of the game.
● Second, the computation must not take too long!
● Third, for nonterminal states, the evaluation function
should be strongly correlated with the actual chances
of winning.
22
 Minimax:
Static Board Evaluator (SBE)
● Evaluation function is a heuristic function, and it is where the
domain experts’ knowledge resides.
● Example of an evaluation function for Tic-Tac-Toe:
f(n) = [# of 3-lengths open for me] - [# of 3-lengths open for you],
where a 3-length is a complete row, column, or diagonal.
● Alan Turing’s function for chess
– f(n) = w(n)/b(n), where w(n) = sum of the point value of white’s pieces and
b(n) is sum for black.
● Most evaluation functions are specified as a weighted sum of
position features:
f(n) = w1*feat1(n) + w2*feat2(n) + ... + wn*featk(n)
● Example features for chess are piece count, piece placement,
squares controlled, etc.
● Deep Blue has about 6,000 features in its evaluation function.
 Minimax: Algorithm with SBE

int minimax (Node s, int depth, int limit) {

if (isTerminal(s) || depth == limit) //base case
return(staticEvaluation(s));
else {
Vector v = new Vector();
//do minimax on successors of s and save their values
while ([Link]())
[Link](minimax([Link](),
depth+1, limit));
if (isComputersTurn(s))
return maxOf(v); //computer's move returns max of kids
else
return minOf(v); //opponent's move returns min of kids
}
}

24
 Minimax: Algorithm with SBE

●The same as direct minimax, except

– only goes to depth m
– estimates non-terminal states using SBE function
●How would this algorithm perform at chess?
– if could look ahead ~4 pairs of moves (i.e. 8 ply)
would be consistently beaten by average players
– if could look ahead ~8 pairs as done in typical
pc, is as good as human master

25
 Recap
●Can't minimax search to the end of the
game.
– if could, then choosing move is easy
●SBE isn't perfect at estimating.
– if it was, just choose best move without
searching

26
 Alpha-Beta Pruning Idea
● Some of the branches of the game tree won't be
taken if playing against a smart opponent.
● Use pruning to ignore those branches.
● While doing DFS of game tree, keep track of:
– alpha at maximizing levels (computer’s move)
●highest SBE value seen so far (initialize to -infinity)
●is lower bound on state's evaluation
– beta at minimizing levels (opponent’s move)
●lowest SBE value seen so far (initialize to +infinity)
●is higher bound on state's evaluation

27
 Alpha-Beta Pruning Idea
●Beta cutoff pruning occurs when maximizing
if child’s alpha ≥ parent's beta
Why stop expanding children?
opponent won't allow computer to take this move

●Alpha cutoff pruning occurs when minimizing

if parent's alpha ≥ child’s beta
Why stop expanding children?
computer has a better move than this

28
 Alpha-Beta Search Example
minimax(A,0,4) alpha initialized to -infinity

Expand A? Yes since there are successors, no cutoff test for root

A Call
max A
α=- Stack

B C D E
0

F G H I J K L M
-5 3 8 2

N O P Q R S T U V
4 9 -6 0 3 5 -7 -9

W X A
-3 -5

29
 Alpha-Beta Search Example
minimax(B,1,4) beta initialized to +infinity

Expand B? Yes since A’s alpha >= B’s beta is false, no alpha cutoff

A Call
max α=- Stack
BB C D E
β=+ 0
min

F G H I J K L M
-5 3 8 2

N O P Q R S T U V
4 9 -6 0 3 5 -7 -9
B
W X A
-3 -5

30
 Alpha-Beta Search Example
minimax(F,2,4) alpha initialized to -infinity

Expand F? Yes since F’s alpha >= B’s beta is false, no beta cutoff

A Call
max α=- Stack
B C D E
β=+ 0
min
FF G H I J K L M
α=- -5 3 8 2
max
N O P Q R S T U V F
4 9 -6 0 3 5 -7 -9
B
W X A
-3 -5

31
 Alpha-Beta Search Example
minimax(N,3,4) evaluate and return SBE value

A Call
max α=- Stack
B C D E
β=+ 0
min
F G H I J K L M
α=- -5 3 8 2
max
N
N O P Q R S T U V F
4 9 -6 0 3 5 -7 -9
B
W X green: terminal state A
-3 -5

32
 Alpha-Beta Search Example
back to alpha = 4, since 4 >= -infinity (maximizing)
minimax(F,2,4)
Keep expanding F? Yes since F’s alpha >= B’s beta is false, no beta cutoff

A Call
max α=- Stack
B C D E
β=+ 0
min
F G H I J K L M
α=4
α=- -5 3 8 2
max
N O P Q R S T U V F
4 9 -6 0 3 5 -7 -9
B
W X A
-3 -5

33
 Alpha-Beta Search Example
minimax(O,3,4) beta initialized to +infinity

Expand O? Yes since F’s alpha >= O’s beta is false, no alpha cutoff

A Call
max α=- Stack
B C D E
β=+ 0
min
F G H I J K L M
α=4 -5 3 8 2
max
O
N OO P Q R S T U V F
4 β=+ 9 -6 0 3 5 -7 -9
B
min
W X A
-3 -5

34
 Alpha-Beta Search Example
minimax(W,4,4) evaluate and return SBE value

A Call
max α=- Stack
B C D E
β=+ 0
min
F G H I J K L M
α=4 -5 3 8 2 W
max
O
N O P Q R S T U V F
4 β=+ 9 -6 0 3 5 -7 -9
B
min
W X blue: non-terminal state (depth limit) A
-3 -5

35
 Alpha-Beta Search Example
back to beta = -3, since -3 <= +infinity (minimizing)
minimax(O,3,4)
Keep expanding O? No since F’s alpha >= O’s beta is true: alpha cutoff

A Call
max α=- Stack
B C D E
β=+ 0
min
F G H I J K L M
α=4 -5 3 8 2
max
O
N O P Q R S T U V F
4 β=-3
β=+ 9 -6 0 3 5 -7 -9
B
min
W X A
-3 -5

36
 Alpha-Beta Search Example
● Why?
Smart opponent will choose W or worse, thus O's upper bound is –3.
Computer already has better move at N.

A Call
max α=- Stack
B C D E
β=+ 0
min
F G H I J K L M
α=4 -5 3 8 2
max
O
N O P Q R S T U V F
4 β=-3 9 -6 0 3 5 -7 -9
B
min
W X red: pruned state A
-3 -5

37
 Alpha-Beta Search Example
back to alpha doesn’t change, since -3 < 4 (maximizing)
minimax(F,2,4)
Keep expanding F? No since no more successors for F

A Call
max α=- Stack
B C D E
β=+ 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V F
4 β=-3 9 -6 0 3 5 -7 -9
B
min
W X A
-3 -5

38
 Alpha-Beta Search Example
back to beta = 4, since 4 <= +infinity (minimizing)
minimax(B,1,4)
Keep expanding B? Yes since A’s alpha >= B’s beta is false, no alpha cutoff

A Call
max α=- Stack
B C D E
β=+
β=4 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
B
min
W X A
-3 -5

39
 Alpha-Beta Search Example
minimax(G,2,4) evaluate and return SBE value

A Call
max α=- Stack
B C D E
β=4 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V G
4 β=-3 9 -6 0 3 5 -7 -9
B
min
W X green: terminal state A
-3 -5

40
 Alpha-Beta Search Example
back to beta = -5, since -5 <= 4 (minimizing)
minimax(B,1,4)
Keep expanding B? No since no more successors for B

A Call
max α=- Stack
B C D E
β=-5
β=4 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
B
min
W X A
-3 -5

41
 Alpha-Beta Search Example
back to alpha = -5, since -5 >= -infinity (maximizing)
minimax(A,0,4)
Keep expanding A? Yes since there are more successors, no cutoff test

A Call
max α=-5
α= Stack
B C D E
β=-5 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
min
W X A
-3 -5

42
 Alpha-Beta Search Example
minimax(C,1,4) beta initialized to +infinity

Expand C? Yes since A’s alpha >= C’s beta is false, no alpha cutoff

A Call
max α=-5
α= Stack
B C
C D E
β=-5 β=+ 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X A
-3 -5

43
 Alpha-Beta Search Example
minimax(H,2,4) evaluate and return SBE value

A Call
max α=-5
α= Stack
B C D E
β=-5 β=+ 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V H
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X green: terminal state A
-3 -5

44
 Alpha-Beta Search Example
back to beta = 3, since 3 <= +infinity (minimizing)
minimax(C,1,4)
Keep expanding C? Yes since A’s alpha >= C’s beta is false, no alpha cutoff

A Call
max α=-5
α= Stack
B C D E
β=-5 β=+
β=3 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X A
-3 -5

45
 Alpha-Beta Search Example
minimax(I,2,4) evaluate and return SBE value

A Call
max α=-5
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V I
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X green: terminal state A
-3 -5

46
 Alpha-Beta Search Example
back to beta doesn’t change, since 8 > 3 (minimizing)
minimax(C,1,4)
Keep expanding C? Yes since A’s alpha >= C’s beta is false, no alpha cutoff

A Call
max α=-5
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X A
-3 -5

47
 Alpha-Beta Search Example
minimax(J,2,4) alpha initialized to -infinity

Expand J? Yes since J’s alpha >= C’s beta is false, no beta cutoff

A Call
max α=-5
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J
J K L M
α=4 -5 3 8 α=- 2
max
N O P Q R S T U V J
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X A
-3 -5

48
 Alpha-Beta Search Example
minimax(P,3,4) evaluate and return SBE value

A Call
max α=-5
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 α=- 2
max
P
N O P Q R S T U V J
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X green: terminal state A
-3 -5

49
 Alpha-Beta Search Example
back to alpha = 9, since 9 >= -infinity (maximizing)
minimax(J,2,4)
Keep expanding J? No since J’s alpha >= C’s beta is true: beta cutoff

A Call
max α=-5
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 α=9
α=- 2
max
N O P Q R S T U V J
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X red: pruned states A
-3 -5

50
 Alpha-Beta Search Example
● Why?
Computer will choose P or better, thus J's lower bound is 9.
Smart opponent won’t let computer take move to J
(since opponent already has better move at H).

A Call
max α=-5
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 α=9 2
max
N O P Q R S T U V J
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X red: pruned states A
-3 -5

51
 Alpha-Beta Search Example
back to beta doesn’t change, since 9 > 3 (minimizing)
minimax(C,1,4)
Keep expanding C? No since no more successors for C

A Call
max α=-5
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 α=9 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
C
min
W X A
-3 -5

52
 Alpha-Beta Search Example
back to alpha = 3, since 3 >= -5 (maximizing)
minimax(A,0,4)
Keep expanding A? Yes since there are more successors, no cutoff test

A Call
max α=-5
α=3 Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 α=9 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
min
W X A
-3 -5

53
 Alpha-Beta Search Example
minimax(D,1,4) evaluate and return SBE value

A Call
max α=3
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 α=9 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
D
min
W X green: terminal state A
-3 -5

54
 Alpha-Beta Search Example
back to alpha doesn’t change, since 0 < 3 (maximizing)
minimax(A,0,4)
Keep expanding A? Yes since there are more successors, no cutoff test

A Call
max α=3
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 α=9 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
min
W X A
-3 -5

55
 Alpha-Beta Search Example
● How does the algorithm finish searching the tree?

A Call
max α=3
α= Stack
B C D E
β=-5 β=3 0
min
F G H I J K L M
α=4 -5 3 8 α=9 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
min
W X A
-3 -5

56
 Alpha-Beta Search Example
Stop Expanding E since A's alpha >= E's beta is true: alpha cutoff
● Why?
Smart opponent will choose L or worse, thus E's upper bound is 2.
Computer already has better move at C.
A Call
max α=3
α= Stack
B C D E
β=-5 β=3 0 β=2
min
F G H I J K L M
α=4 -5 3 8 α=9 α=5 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
min
W X A
-3 -5

57
 Alpha-Beta Search Example
Result: Computer chooses move to C.

A Call
max α=3
α= Stack
B C D E
β=-5 β=3 0 β=2
min
F G H I J K L M
α=4 -5 3 8 α=9 α=5 2
max
N O P Q R S T U V
4 β=-3 9 -6 0 3 5 -7 -9
min
W X green: terminal states, red: pruned states A
-3 -5 blue: non-terminal state (depth limit)

58
 Alpha-Beta Effectiveness
● Effectiveness depends on the order
in which successors are examined.

● What ordering gives more effective pruning?

More effective if best successors are examined first.

● Best Case: each player’s best move is left-most

● Worst Case: ordered so that no pruning occurs
– no improvement over exhaustive search

● In practice, performance is closer

to best case rather than worst case.
59
 Alpha-Beta Effectiveness
If opponent’s best move where first
more pruning would result:

A A
α=3 α=3
E E
β=2 β=2

K L M L K M
α=5 2 2

S T U V S T U V
3 5 -7 -9 3 5 -7 -9

60
 Alpha-Beta Effectiveness
(d/2) d
● In practice often get O(b ) rather than O(b )
– same as having a branching factor of sqrt(b)
d (d/2)
recall (sqrt(b)) = b

● For Example: chess

– goes from b ~ 35 to b ~ 6
– permits much deeper search for the same time
– makes computer chess competitive with humans

61
62
Other Issues: The Horizon Effect
● Sometimes disaster lurks just
beyond search depth
– e.g. computer captures queen,
but a few moves later the opponent checkmates

● The computer has a limited horizon, it cannot

see that this significant event could happen

● How do you avoid catastrophic losses

due to “short-sightedness”?
– quiescence search
– secondary search

63
Other Issues: The Horizon Effect
●Quiescence Search
–when SBE value frequently changing,
look deeper than limit
–looking for point when game quiets down

●Secondary Search
–find best move looking to depth d
–look k steps beyond to verify that it still looks
good
–if it doesn't, repeat step 2 for next best move
64
THANKS…