CS 561a: Introduction to Artificial Intelligence
CS 561, Session 5
1
This time: Outline
Game playing
The minimax algorithm
Resource limitations
alpha-beta pruning
Elements of chance
CS 561, Session 5
2
What kind of games?
Abstraction: To describe a game we must capture every relevant aspect of the game. Such as:
Chess
Tic-tac-toe
…
Accessible environments: Such games are characterized by perfect information
Search: game-playing then consists of a search through possible game positions
Unpredictable opponent: introduces uncertainty thus game-playing must deal with contingency problems
CS 561, Session 5
3
Searching for the next move
Complexity: many games have a huge search space
Chess: b = 35, m=100 nodes = 35 100
if each node takes about 1 ns to explore
then each move will take about 10 50 millennia
to calculate.
Resource (e.g., time, memory) limit: optimal solution not feasible/possible, thus must approximate
Pruning: makes the search more efficient by discarding portions of the search tree that cannot improve quality result.
Evaluation functions: heuristics to evaluate utility of a state without exhaustive search.
CS 561, Session 5
4
Two-player games
A game formulated as a search problem:
Initial state: ?
Operators: ?
Terminal state: ?
Utility function: ?
CS 561, Session 5
5
Two-player games
A game formulated as a search problem:
Initial state: board position and turn
Operators: definition of legal moves
Terminal state: conditions for when game is over
Utility function: a numeric value that describes the outcome of the
game. E.g., -1, 0, 1 for loss, draw, win.
(AKA payoff function)
CS 561, Session 5
6
Game vs. search problem
CS 561, Session 5
7
Example: Tic-Tac-Toe
CS 561, Session 5
8
Type of games
CS 561, Session 5
9
Type of games
CS 561, Session 5
10
The minimax algorithm
Perfect play for deterministic environments with perfect information
Basic idea: choose move with highest minimax value
= best achievable payoff against best play
Algorithm:
Generate game tree completely
Determine utility of each terminal state
Propagate the utility values upward in the three by applying MIN and MAX operators on the nodes in the current level
At the root node use minimax decision to select the move with the max (of the min) utility value
Steps 2 and 3 in the algorithm assume that the opponent will play perfectly.
CS 561, Session 5
11
Generate Game Tree
CS 561, Session 5
12
Generate Game Tree
x
x
x
x
CS 561, Session 5
13
Generate Game Tree
x
o x
x
o
x
o
x o
CS 561, Session 5
14
Generate Game Tree
x
o x
x
o
x
o
x o
1 ply
1 move
CS 561, Session 5
15
A subtree
win
lose
draw
x
x
o
o
o
x
x
x
o
o
o
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
o
o
o
o
o
o
x
x
o
o
o
x
x
o
x
x
x
x
x
o
o
o
x
x
o
x
x
o
o
o
x
x
o
x
x
x
o
o
o
x
x
o
CS 561, Session 5
16
What is a good move?
win
lose
draw
x
x
o
o
o
x
x
x
o
o
o
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
x
x
o
o
o
x
x
o
o
o
o
o
o
x
x
o
o
o
x
x
o
x
x
x
x
x
o
o
o
x
x
o
x
x
o
o
o
x
x
o
x
x
x
o
o
o
x
x
o
CS 561, Session 5
17
Minimax
3
8
12
4
6
14
2
5
2
Minimize opponent’s chance
Maximize your chance
CS 561, Session 5
18
Minimax
3
2
3
2
8
12
4
6
14
2
5
2
MIN
Minimize opponent’s chance
Maximize your chance
CS 561, Session 5
19
Minimax
3
3
2
3
2
8
12
4
6
14
2
5
2
MAX
MIN
Minimize opponent’s chance
Maximize your chance
CS 561, Session 5
20
Minimax
3
3
2
3
2
8
12
4
6
14
2
5
2
MAX
MIN
Minimize opponent’s chance
Maximize your chance
CS 561, Session 5
21
minimax = maximum of the minimum
1st ply
2nd ply
CS 561, Session 5
22
Minimax: Recursive implementation
Complete: ?
Optimal: ?
Time complexity: ?
Space complexity: ?
CS 561, Session 5
23
Minimax: Recursive implementation
Complete: Yes, for finite state-space
Optimal: Yes
Time complexity: O(bm)
Space complexity: O(bm) (= DFS
Does not keep all nodes in memory.)
CS 561, Session 5
24
1. Move evaluation without complete search
Complete search is too complex and impractical
Evaluation function: evaluates value of state using heuristics and cuts off search
New MINIMAX:
CUTOFF-TEST: cutoff test to replace the termination condition (e.g., deadline, depth-limit, etc.)
EVAL: evaluation function to replace utility function (e.g., number of chess pieces taken)
CS 561, Session 5
25
Evaluation functions
Weighted linear evaluation function: to combine n heuristics
f = w1f1 + w2f2 + … + wnfn
E.g, w’s could be the values of pieces (1 for prawn, 3 for bishop etc.)
f’s could be the number of type of pieces on the board
CS 561, Session 5
26
Note: exact values do not matter
CS 561, Session 5
27
Minimax with cutoff: viable algorithm?
Assume we have 100 seconds, evaluate 104 nodes/s; can evaluate 106 nodes/move
CS 561, Session 5
28
2. - pruning: search cutoff
Pruning: eliminating a branch of the search tree from consideration without exhaustive examination of each node
- pruning: the basic idea is to prune portions of the search tree that cannot improve the utility value of the max or min node, by just considering the values of nodes seen so far.
Does it work? Yes, in roughly cuts the branching factor from b to b resulting in double as far look-ahead than pure minimax
CS 561, Session 5
29
Demo
http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html
CS 561, Session 5
30
- pruning: example
6
6
MAX
6
12
8
MIN
CS 561, Session 5
31
- pruning: example
6
6
MAX
6
12
8
2
2
MIN
CS 561, Session 5
32
- pruning: example
6
6
MAX
6
12
8
2
2
5
5
MIN
33
- pruning: example
6
6
MAX
6
12
8
2
2
5
5
MIN
Selected move
Interactive demo:
https://www.yosenspace.com/posts/computer-science-game-trees.html
CS 561, Session 5
34
- pruning: general principle
Player
Player
Opponent
Opponent
m
n
v
If > v then MAX will chose m so prune tree under n
Similar for for MIN
CS 561, Session 5
35
Properties of -
CS 561, Session 5
36
The - algorithm
CS 561, Session 5
37
More on the - algorithm
Same basic idea as minimax, but prune (cut away) branches of the tree that we know will not contain the solution.
We know a branch will not contain a solution once we know a better outcome has already been discovered in a previously explored branch.
CS 561, Session 5
38
Remember: Minimax: Recursive implementation
Complete: Yes, for finite state-space
Optimal: Yes
Time complexity: O(bm)
Space complexity: O(bm) (= DFS
Does not keep all nodes in memory.)
CS 561, Session 5
39
The - algorithm
CS 561, Session 5
40
More on the - algorithm
Same basic idea as minimax, but prune (cut away) branches of the tree that we know will not contain the solution.
Because minimax is depth-first, let’s consider nodes along a given path in the tree. Then, as we go along this path, we keep track of:
: Best choice so far for MAX
: Best choice so far for MIN
CS 561, Session 5
41
The - algorithm
Note: and are both
Local variables. At the
Start of the algorithm,
We initialize them to
= - and = +
CS 561, Session 5
42
More on the - algorithm
…
MAX
MIN
= -
= +
5 10 6 2 8 7
Min-Value loops
over these
In Min-Value:
= -
= 5
= -
= 5
= -
= 5
Max-Value loops
over these
Return v=5
CS 561, Session 5
43
More on the - algorithm
…
MAX
MIN
MAX
5 10 6 2 8 7
In Max-Value:
= -
= 5
= -
= 5
= -
= 5
= 5
= +
Max-Value loops
over these
Return v=5
CS 561, Session 5
44
In Min-Value:
More on the - algorithm
…
MAX
MIN
MAX
5 10 6 2 8 7
= -
= 5
= -
= 5
= -
= 5
= 5
= +
= 5
= +
End loop and return 2
Min-Value loops
over these
CS 561, Session 5
45
In Max-Value:
More on the - algorithm
…
MAX
MIN
MAX
5 10 6 2 x x
= -
= 5
= -
= 5
= -
= 5
= 5
= +
= 5
= +
= 5
= +
Max-Value loops
over these
Return v=2
CS 561, Session 5
46
Another way to understand the algorithm
For a given node N,
is the value of N to MAX
is the value of N to MIN
CS 561, Session 5
47
Example
CS 561, Session 5
48
- algorithm: slight variant (from earlier version of textbook)
Is this wrong compared to latest version of textbook?
Please always use latest version of the algorithm as in 3rd edition of textbook.
CS 561, Session 5
49
Solution
NODE TYPE ALPHA BETA SCORE
A MAX -Inf Inf
B MIN -Inf Inf
C MAX -Inf Inf
D MIN -Inf Inf
E MAX 10 10 10
D MIN -Inf 10
F MAX 11 11 11
D MIN -Inf 10 10
C MAX 10 Inf
G MIN 10 Inf
H MAX 9 9 9
G MIN 10 9 9
C MAX 10 Inf 10
B MIN -Inf 10
J MAX -Inf 10
K MIN -Inf 10
L MAX 14 14 14
K MIN -Inf 10
M MAX 15 15 15
K MIN -Inf 10 10
…
NODE TYPE ALPHA BETA SCORE
…
J MAX 10 10 10
B MIN -Inf 10 10
A MAX 10 Inf
Q MIN 10 Inf
R MAX 10 Inf
S MIN 10 Inf
T MAX 15 15 15
S MIN 10 15
U MAX 2 2 2
S MIN 10 2 2
R MAX 10 Inf
V MIN 10 Inf
W MAX 4 4 4
V MIN 10 4 4
R MAX 10 Inf 10
Q MIN 10 10 10
A MAX 10 Inf 10
CS 561, Session 5
50
State-of-the-art for deterministic games
CS 561, Session 5
51
Nondeterministic games
CS 561, Session 5
52
Algorithm for nondeterministic games
CS 561, Session 5
53
Remember: Minimax algorithm
CS 561, Session 5
54
Nondeterministic games: the element of chance
3
?
0.5
0.5
8
17
8
?
CHANCE
?
expectimax and expectimin, expected values over all possible outcomes
CS 561, Session 5
55
Nondeterministic games: the element of chance
3
5
0.5
0.5
8
17
8
5
CHANCE
4 = 0.5*3 + 0.5*5
Expectimax
Expectimin
CS 561, Session 5
56
Evaluation functions: Exact values DO matter
Order-preserving transformation do not necessarily behave the same!
CS 561, Session 5
57
State-of-the-art for nondeterministic games
CS 561, Session 5
58
Summary
CS 561, Session 5
59
Exercise: Game Playing
(a) Compute the backed-up values computed by the minimax algorithm. Show your answer by writing values at the appropriate nodes in the above tree.
(b) Compute the backed-up values computed by the alpha-beta algorithm. What nodes will not be examined by the alpha-beta pruning algorithm?
(c) What move should Max choose once the values have been backed-up all the way?
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Y
X
2
3
8
5
7
6
0
1
5
2
8
4
2
10
Max
Max
Min
Min
Consider the following game tree in which the evaluation function values are shown below each leaf node. Assume that the root node corresponds to the maximizing player. Assume the search always visits children left-to-right.
/docProps/thumbnail.jpeg