Adversarial Search
Game Playing
Dr. Mohamed K. Hussein
Outline
• Optimal decisions
• α-β pruning
Games vs. search problems
• "Unpredictable" opponent specifying a
move for every possible opponent reply
Games in AI
• In AI, “games” usually refers to
deterministic, turn-taking, two-player, zero-
sum games of perfect information
– Deterministic: next state of environment is
completely determined by current state and
action executed by the agent (not
probabilistic)
– Turn-taking: 2 agents whose actions must
alternate
– Zero-sum games: if one agent wins, the other
loses
– Perfect information: fully observable
Games in AI
• Rich tradition of creating game-playing
programs in AI
• Many similarities to search
• Most of the games studied
– have two players,
– are zero-sum: what one player wins, the other loses
– have perfect information: the entire state of the
game is known to both players at all times
• E.g., tic-tac-toe, checkers, chess, Go,
backgammon, …
– Will focus on these for now
• Recently more interest in other games
– Esp. games without perfect information; e.g., poker
• Need probability theory, game theory for such
games
Games as Search
• States:
• board configurations
• Initial state:
• the board position and which player will move
• Successor function:
• returns list of (move, state) pairs, each indicating a
legal move and the resulting state
• Terminal test:
• determines when the game is over
• Utility function:
• gives a numeric value in terminal states
• (e.g., -1, 0, +1 for loss, tie, win)
Game tree (2-player,
deterministic, turns)
Minimax Algorithm
2
2 1 2 1
2 7 1 8 2 7 1 8 2 7 1 8
This is the move 2
Static evaluator selected by minimax
value
2 1
MAX
MIN 2 7 1 8
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
max
min
max
min
© Patrick Winston
Minimax
• Perfect play for deterministic games
•
• Idea: choose move to position with highest minimax
value
= best achievable payoff against best play
•
• E.g., 2-ply game:
•
Mini-Max Properties
• Complete?
• Optimal?
– Against an optimal opponent?
– Otherwise?
• Time complexity?
• Space complexity?
Mini-Max Properties
• Complete? Yes, if tree is finite
• Optimal?
– Against an optimal opponent?
– Otherwise?
• Time complexity?
• Space complexity?
Mini-Max Properties
• Complete? Yes, if tree is finite
• Optimal?
– Against an optimal opponent? Yes
– Otherwise? No: Does at least as well, but
may not exploit opponent weakness
• Time complexity?
• Space complexity?
Mini-Max Properties
• Complete? Yes, if tree is finite
• Optimal?
– Against an optimal opponent? Yes
– Otherwise? No: Does at least as well, but
may not exploit opponent weakness
• Time complexity? O(bm)
• Space complexity? O(bm)
Minimax algorithm
Alpha-beta pruning
• We can improve on the performance of the minimax
algorithm through alpha-beta pruning
• Basic idea: “If you have an idea that is surely bad, don't
take the time to see how truly awful it is.” -- Pat Winston
MAX >=2 • We don’t need to compute
the value at this node.
MIN =2 <=1
• No matter what it is, it can’t
affect the value of the root
MAX node.
2 7 1 ?
α-β pruning example
α-β pruning example
α-β pruning example
α-β pruning example
α-β pruning example
Alpha-Beta Pruning
• Pruning = cutting off parts of the search
tree (because you realize you don’t need
to look at them)
– When we considered A* we also pruned large
parts of the search tree
• Maintain alpha = value of the best option
for player 1 along the path so far
• Beta = value of the best option for player 2
along the path so far
max
min
max
min
max
min
max
min
max
min
max
min
max
min
max
min
© Patrick Winston
max
min
max
Do we need to check
this node?
min
??
max
min
max
No - this branch is guaranteed to be
worse than what max already has
min
X
Properties of α-β
• Pruning does not affect final result
•
• Good move ordering improves effectiveness of pruning
•
• With "perfect ordering," time complexity = O(bm/2)
doubles depth of search
• A simple example of the value of reasoning about which
computations are relevant (a form of metareasoning)
•
Why is it called α-β?
• α is the value of the
best (i.e., highest-
value) choice found
so far at any choice
point along the path
for max
• If v is worse than α,
max will avoid it
• prune that branch
• Define β similarly for
min
The α-β algorithm
The α-β algorithm
Example
-which nodes can be pruned?
3 4 1 2 7 8 5 6
Answer to Example
-which nodes can be pruned?
Max
Min
Max
3 4 1 2 7 8 5 6
Answer: NONE! Because the most favorable nodes for both are
explored last (i.e., in the diagram, are on the right-hand side).
Second Example
(the exact mirror image of the first example)
-which nodes can be pruned?
6 5 8 7 2 1 3 4
Answer to Second Example
(the exact mirror image of the first example)
Max -which nodes can be pruned?
Min
Max
6 5 8 7 2 1 3 4
Answer: LOTS! Because the most favorable nodes for both are
explored first (i.e., in the diagram, are on the left-hand side).
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Example
Summary
• Games are fun to work on!
• They illustrate several important points
about AI
• perfection is unattainable must
approximate
• good idea to think about what to think about
