Games and Adversarial Search
AIMA 5.1-5.2
CMPSC 442
Week 4, Meeting 11, Two Segments
Outline
1. Games as Search
2. Adversarial Search: Minimax
Outline, Wk 4, Mtg 11 2
Games and Adversarial Search
AIMA 5.1-5.3
CMPSC 442
Week 4, Meeting 11, Segment 1 of 2: Games as Search
Games as Search
● Carryover from previous material on search
○ States (aka positions)
○ Actions (aka moves)
○ Transition model
○ Evaluation function to apply to states (of a game)
○ Goal test (aka terminal test, is the game over)
● New material specific to games
○ There is an opponent to keep track of
○ The search tree includes the adversary’s possible moves with alternating
plies (levels) for the player and opponent
○ A utility function (or payoff function) of the payoff in points to each player
4Games as Search
Key Properties of the Sample Games used here
● Deterministic
● Two-player
● Turn-taking
● Perfect information
● Zero-sum: one player’s losses = the other player’s gains, and vice
versa
Simple games: Tic-Tac-Toe, Othello, Connect Four, Gobblet, Quarto, . . .
Complex games: Checkers, Chess, Go
5Games as Search
Game Search, for Two-Player, Zero-Sum Games
● Two players: MAX and MIN
● MAX moves first
● MAX and MIN take turns until the game is over
● Winner gets reward, loser gets penalty
6Games as Search
Formalizing a Game as Search
● Initial state S
0
:
How the game is set up at the start
● To-Move(s): The player whose turn it is to move in state s
● Actions(s): The set of legal moves in state s
● Result(a, s): The transition model defining the result of taking action a
in state s
● Is-Terminal(s): A Boolean to indicate when the game is finished
● Utility(s, p): Gives a numerical value to player p at the terminal state.
○ Tic-tac-toe’s utility function has three values win (+1), lose (-1) and draw (0)
in tic-tac-toe
○ Backgammon payoffs are in [0, 192]
7Games as Search
How to Play a Game by Searching
General Scheme
1. Consider all legal successors to the current state (‘board position’)
2. Evaluate each successor board position
3. Pick the move which leads to the best board position
4. After your opponent’s best move(s), repeat.
Design issues
● Representing the ‘board’ and its successor boards
● Evaluating positions
● Looking ahead (search)
8Games as Search
Evaluation of Game States
● Represent the game problem space by a tree:
○ Nodes represent board positions (states)
○ Edges represent legal moves (actions)
○ Root node is the first position in which a decision must be made
● Evaluation function f assigns real-number scores to board positions
without reference to the search path
● A terminal node represents a possible game end, labeled with its
utility (e.g. win/lose/draw, etc.)
9Games as Search
Evaluation functions for board position: f(n)
● Based on static features of that board alone
● Zero-sum assumption lets us use one function to describe goodness
for both players
○ f(n) > 0 if MAX is winning in position n
○ f(n) = 0 if position n is tied
○ f(n) < 0 if MIN is winning in position n
● Define using expert knowledge
○ Tic-tac-toe: f(n)=(# of 3 lines open for MAX)- (# open for MIN)
10Games as Search
A Partial Game Tree for Tic-Tac-Toe
11Games as Search
-1
f(n) = |potential 3-in-a-rows for Max| -
|potential 3-in-a-rows for Min|
f(n) = number of open 3-in-a-row
f(n) = 4 f(n) = 2 f(n) = 3
f(n) = 2
f(n) = 4
f(n) = 2
Games and Adversarial Search
AIMA 5.1-5.2
CMPSC 442
Week 4, Meeting 11, Segment 2 of 2: Minimax
MAX and MIN
● Max moves first: all play is computed from MAX’s vantage point
● When MAX moves, MAX attempts to MAXimize MAX’s outcome
● MAX assumes that when MIN moves, MIN attempts to MINimize MAX’s
outcome
13Minimax
Differences from Previous Search Methods
● Search goal is to make one move; playing the game has many moves
● No cost on arcs – costs derive from backed-up static evaluation
● MAX can’t be sure how MIN will respond to his moves
14Minimax
Minimax Setup
● Label the root MAX
● Alternate MAX/MIN at each next level of the tree (ply)
○ Minimax(node) is the utility of any node (for MAX)
○ Even levels represent turns for MAX
○ Odd levels represent turns for MIN
15Minimax
The Minimax Rule: “Don’t play hope chess”
Assume both players play optimally
● Max prefers next state to have maximum value
● Min prefers next state to have minimum value
16Minimax
Description of Minimax Algorithm
● Recurse down the game tree
○ Search proceeds to some depth d (number of moves to look ahead)
○ Expand to leaf nodes at depth d
● Pass the minimax values back up through the tree
○ Compute the minimax() utility function at the depth-d leaves
○ Pass value back up tree to the parent nodes
● Backed-up values
○ At a MAX node: the maximum of MAX’s descendants (the best for MAX)
○ At a MIN node: the minimum of MIN’s descendants (the best for MIN)
17Minimax
A Two-Ply Game Tree
Max’s best move at root is a
1
- why?
Min’s best response to a
1
is b
1
- why?
18Minimax
Minimax Algorithm Semi-Formally
While game not over:
1. Start with the current position as a MAX node
2. Expand the game tree a fixed number of ply (amount of look-ahead)
3. Apply the evaluation function to the leaf positions at look-ahead depth
4. Back-up the values all the way to the root
5. Pick the move assigned to MAX at the root
6. Wait for MIN to respond
19Minimax
Backing Up Values for 2-Ply Look Ahead
20Minimax
● Ply 1, Left node: Minimax(s) for MIN node whose children have utilities 2, 7
○ 2: Assume MIN picks the move to minimize MAX’s outcome
● Ply 1, Right node: Minimax(s) for MIN node whose children have utilities 1, 8
○ 1: Assume MIN picks the move to minimize MAX’s outcome
● Ply 0, Root: Minimax(s) for MAX node whose children have utilities 2, 1
○ 2: Assume MAX picks the move to maximize MAX’s outcome
Minimax
Pseudo
Code
21Minimax
Minimax Performance
Depth-first search (DFS) with fixed number of ply m as the limit.
● O(bm) time complexity
● O(bm) space complexity if algorithm computes all moves at once
● O(m) space complexity if algorithm computes moves one at a time
Performance will depend on
● The quality of the static evaluation function (expert knowledge)
● Depth of search (computing power and search algorithm)
22Minimax
Minimax is Impractical but a Useful Theoretical Tool
Chess
● Average branching factor b=35
● Average game has 80 turns (plies)
● 3580 ≈ 10123
Minimax serves as the basis for the mathematical analysis of games
23Minimax
Summary
● Games as search
○ Builds on our framework of states, actions, transition model, evaluation
function on states, and goal test
○ Adds alternating plies for MAX and MIN, and a utility function or payoff
● Minimax
○ Looks ahead to depth d, where the leaves are labeled with the payoffs
○ Backs up the MAX value of the children to a MAX node, backs up the MIN
value of the children to a MIN node
24Wk 4, Mtg 11 Summary