Adversarial Search (Minimax)
Deterministic,zero‐sumgames
5 Max 4 5Min
Tic‐tac‐toe, chess, go
One player maximises result and the other minimises result
Minimaxsearch:
A state‐space search tree
Players alternate turns
4 8 17
5
Compute each node’s minimax value, i.e. the best achievable utility against an optimal adversary
Implementing Minimax
function max_value (state) return its minimax value initialise ∞
for each successor of state
function min_value (state) return its minimax value initialise ∞
for each successor of state
max, _ return
min, _ return
function minimax_value (state) return its minimax value if state is a terminal state
return its utility
if state is for agent Max to take an action
return max_value(state)
if state is for agent Min to take an action
return min_value(state)
Minimax example
Max
Min
v=4
4
Minimax example
Max
v=3
Min
v=43 v=2
438267
Minimax example
Max
v=3
Min
v=3 v=2 v=17
4 3 8 2 6 7 17 1
Minimax example
Max
v=3
Min
v=3 v=2 v=1
4 3 8 2 6 7 17 1 5
Computational Complexity of Minimax
Howefficientisminimax
Tic‐Tac‐Toe Connect Four Checkers Nine men’s
10 10 10
DFS (exhaustive)
Time: , is branching factor, is maximum depth of the tree.
morris Draughts Chess Backgammon
10
Space: Examples
10 10
Chess: 35, 100 Go:250, 150
Chinese Chess
10 10
Exact solution is completely infeasible, but do we need to explore the entire tree to find the minimax value?
Game
Game‐tree complexity (appr)
Shoji Go
10 10
Game Tree Pruning
Max
v=3
Min
v=3 v=2 v=1
4 3 8 2 6 7 17 1 5
Game Tree Pruning
Max
Min
v<=4
43
Game Tree Pruning
Max
Min
v<=3
438
Game Tree Pruning
Max
v>=3
Min
v=3 v<=2
4382
Game Tree Pruning
Max
v>=3
Min
v=3 v<=2 v<=17
4382 171
Game Tree Pruning
Max
v>=3
Min
v=3 v<=2 v<=1
4382 171
Game Tree Pruning
Max
v=3
Min
v=3 v<=2 v<=1
4382 171
Alpha‐Beta Pruning
General configuration (for agent Max)
LetbethevaluethatMaxcancurrentlygetatleast.
Wearenowcomputingthemin_valueatsomenode
Whenweexplore’schildren,ifwefindthatthevalue
of will never be better than (for agent Max), then we can stop considering ’s other children.
Properties of alpha‐beta pruning
Thepruninghasnoeffectonminimaxvalueforthe
root
Goodchildorderingimproveseffectivenessofpruning
Complexity of perfect ordering: /
Fullsearchofmanygames(e.g.Chess)isstillhopeless
Alpha‐Beta quiz
Min
Quiz: Find the nodes of the following tree pruned by alpha‐beta pruning algorithm. Assuming child nodes are visited from left to right. There are four layers and you can use L‐ to denote the th node from left to right in the layer , e.g., the first node (with value 8) at the bottom layer can be denoted by L4‐1.
Max
Max
8
5 20 3
2 4 15 6