Chapter 2: Problem Solving
● Uninformed search techniques
Contents ●
●
Informed search techniques
Local search Algorithm and
optimization
● Adversarial search techniques
Adversarial Search
Adversarial search is employed to find optimal strategies when multiple agents have
opposing or conflicting objectives, e.g., while playing games.
Mathematical game theory, a branch of economics, views any multiagent
environment as a game, provided that the impact of each agent on the others is
“significant”, regardless of whether the agents are cooperative or competitive.
Game playing
Games don’t require much knowledge; the only knowledge we need to provide are
the rules, legal moves and the conditions of winning or losing the game.
Both players try to win the game. So, both of them try to make the best move
possible at each turn.
Two-Player Zero-Sum Games
Here we consider deterministic, two-player, turn-taking, perfect information (fully
observable), zero-sum games, e.g. chess.
Zero-sum = what is good for one player is just as bad for the other; there is no
“win-win” outcome.
For games, the terms move = action, position = state.
We will call our two players MAX and MIN.
At the end of the game, points are awarded to the winning player and penalties are
given to the loser.
Two-Player Zero-Sum Games
A game can be formally defined with the following elements:
S0: The initial state.
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(s, a): The transition model, which defines the result of a move.
Is-Terminal(s): A terminal test, which is true when the game is over and false otherwise. States where the
game has ended are called terminal states.
Utility(s, p): A utility function (also called an objective function or payoff function), which defines the final
numeric value to player p when the game ends in terminal state s.
State Space Graph and Game Tree
The initial state, ACTIONS function, and RESULT function define the state space
graph for the game—a graph where the vertices are game states and the edges are
moves.
We can superimpose a search tree over part of the state space graph to determine
what move to make.
We define the complete game tree as a search tree that follows every sequence of
moves all the way to a terminal state.
Game Tree for Tic-Tac-Toc
Optimal Decisions in Games
MAX wants to find a sequence of actions leading to a win, but MIN will respond
with a move that is the worst for MAX (and the best for MIN).
MAX therefore must find a contingent strategy, which specifies MAX’s move in the
initial state, then MAX’s moves in the states resulting from every possible response
by MIN, then MAX’s moves in the states resulting from every possible response by
MIN to those moves, and so on.
Given a game tree, the optimal strategy can be determined from the minimax value
of each node.
Optimal Decisions in Games
The minimax value is the utility (for MAX) of being in the corresponding state
(assuming that both players play optimally from there to the end of the game).
The minimax value of a terminal state is just its utility.
Given a choice, MAX prefers to move to a state of maximum value, whereas MIN
prefers a state of minimum value.
Example
The Minimax Search Algorithm
The minimax algorithm computes the minimax decision from the current state.
It uses a simple recursive computation of the minimax values of each successor state,
directly implementing the defining equations.
The recursion proceeds all the way down to the leaves of the tree, and then the
minimax values are backed up through the tree as the recursion unwinds.
It performs a complete depth-first exploration of the game tree.
The Minimax Search Algorithm: Example
The Minimax Search Algorithm: Example
min(3, 12, 8)
The Minimax Search Algorithm: Example
3
The Minimax Search Algorithm: Example
min(2, 4, 6)
The Minimax Search Algorithm: Example
2
The Minimax Search Algorithm: Example
min(14, 5, 2)
The Minimax Search Algorithm: Example
2
The Minimax Search Algorithm: Example
max(3, 2, 2)
The Minimax Search Algorithm: Example
3
Therefore, action a1 is the optimal choice for MAX because it
leads to the state with the highest minimax value.
The Minimax Search Algorithm
Complete? Yes, if tree is finite (chess has specific rules for this)
Optimal? Yes, against an optimal opponent.
Time complexity? O(bm)
Space complexity? O(bm) (depth-first exploration)
Alpha-Beta Pruning
Alpha-beta pruning is a modified version of the minimax algorithm.
It computes the correct minimax decision without examining every state by pruning
the parts of the tree that make no difference to the outcome.
Alpha-Beta Pruning
Alpha-beta pruning gets its name from the two extra parameters, ɑ and β that
describe bounds on the backed-up values that appear anywhere along the path:
ɑ = the value of the best choice we have found so far at any choice point along the
path for MAX. Think ɑ = “at least”
β = the value of the best choice we have found so far at any choice point along the
path for MIN. Think ɑ = “at least”
Alpha-Beta Pruning: Example
The first leaf below B has
the value 3.
Hence, B, which is a MIN
node, has a value of at
most 3.
Alpha-Beta Pruning: Example
The second leaf below B
has a value of 12; MIN
would avoid this move, so
the value of B is still at
most 3.
Alpha-Beta Pruning: Example
The third leaf below B has
a value of 8; we have seen
all B’s successor states, so
the value of B is exactly 3.
Now we can infer that the
value of the root is at least
3, because MAX has a
choice worth 3 at the root.
Alpha-Beta Pruning: Example
The first leaf below C has
the value 2. Hence, C,
which is a MIN node, has
a value of at most 2. But
we know that B is worth
3, so MAX would never
choose C. Therefore, there
is no point in looking at
the other successor states
of C.
Alpha-Beta Pruning: Example
The first leaf below D has
the value 14, so D is
worth at most 14. This is
still higher than MAX’s
best alternative (i.e., 3),
so we need to keep
exploring D’s successor
states.
Alpha-Beta Pruning: Example
The second successor of D
is worth 5, so again we
need to keep exploring.
The third successor is
worth 2, so now D is
worth exactly 2.
Alpha-Beta Pruning: Exercise
Alpha-Beta Pruning: Exercise
Properties of Alpha-Beta Pruning
Pruning does not affect final result.
Move ordering affects the effectiveness of Alpha-Beta Pruning.
With “perfect ordering,” time complexity = O(bm/2)
⇒ doubles solvable depth
