Rajalakshmi Engineering College

An Autonomous Institution
Chennai-602105
PRINCIPLES OF ARTIFICIAL INTELLIGENCE
(AI19341)

Department of
CSE
 SYLLABUS
UNIT-III Constraint satisfaction problems and Game Theory

Local search for constraint satisfaction problems. Adversarial

search, Games, optimal decisions & strategies in games, the
minimax search procedure, alpha-beta pruning, additional
refinements, iterative deepening.

Department of
CSE
•
Constraint satisfaction problems
Constraint satisfaction problems or CSPs are mathematical problems where one must find states
or objects that satisfy a number of constraints or criteria. A constraint is a restriction of the feasible
solutions in an optimization problem.
• A constraint satisfaction problem consists of three components; X,D, and C:
– X is a set of variables, {X1, . . . ,Xn}.
– D is a set of domains, {D1, . . . ,Dn}, one for each variable.
– C is a set of constraints that specify allowable combinations of values.
• Each constraint Ci limits the values that variables can take, e.g., X1 ≠ X2
• Each constraint Ci is a pair <scope, relation>
– Scope = Tuple of variables that participate in the constraint.
– Relation = List of allowed combinations of variable values.
– May be an explicit list of allowed combinations.
– May be an abstract relation allowing membership testing and listing.

Department of
CSE
 State –space search problem as CSP
Many problems can be stated as constraints satisfaction problems. We can define
initial and final states as follows-
Initial state - contains the constraints that are originally given in the problem
description.
Goal State - any state that has been constrained "enough," where "enough" must be
defined for each problem. Example: Crypt arithmetic, graph coloring.
We can give an incremental formulation as a standard search problem as follows:
Initial state: the empty assignment {},in which all variables are unassigned
Successor function: a value can be assigned to any unassigned variable ,provided that
it does not conflict with previously assigned variables.
Goal test: the current assignment is complete.
Path cost: a constant cost 1 for every step
Department of
CSE
 Assignment
• To solve a CSP, we need to define a state space and the notion of a
solution. Each state in a CSP is defined by an assignment of values
to some or all of the variables, {Xi = vi, Xj = vj , . . .}.
• An assignment that does not violate any constraints is called a
consistent or legal assignment.
• A complete assignment is one in which every variable is assigned,
and a solution to a CSP is a consistent, complete assignment.
• A partial assignment is one that assigns values to only some of the
variables.

Department of
CSE
 CSP example: map coloring
• Variables: WA, NT, Q, NSW, V,
SA, T
• Domains: Di={red ,green ,blue}
• Constraints: adjacent regions
must have different colors.
• C = {SA ≠ WA,SA ≠ NT,SA ≠ Q,SA
≠ NSW,SA ≠ V, WA ≠ NT,NT ≠
Q,Q ≠ NSW,NSW ≠ V } .

Department of
CSE
Department of
CSE
 CSP example: map coloring

• Solutions are assignments satisfying all constraints, e.g.

{WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green}

Department of
CSE
 Constraint graphs
• Constraint graph:

• nodes are variables

• arcs are binary constraints

• Graph can be used to simplify the search

e.g. Tasmania is an independent subproblem

Department of
CSE
 Varieties of constraints
• Unary constraints involve a single variable.
– e.g. SA  green

• Binary constraints involve pairs of variables.

– e.g. SA  WA

• Higher-order constraints involve 3 or more variables.

– Professors A, B, and C cannot be on a committee together
– Can always be represented by multiple binary constraints

• Preference (soft constraints)

– e.g. red is better than green often can be represented by a cost for each variable assignment
– combination of optimization with CSPs
Department of
CSE
 Sudoku as a Constraint Satisfaction Problem (CSP)
• Variables: 81 variables
– A1, A2, A3, …, I7, I8, I9
– Letters index rows, top to bottom
– Digits index columns, left to right
• Domains: The nine positive digits
– A1  {1, 2, 3, 4, 5, 6, 7, 8, 9} 1 2 3 4 5 6 7 8
9
A
– Etc. B
C
• Constraints: 27 Alldiff constraints D
– Alldiff(A1, A2, A3, A4, A5, A6, A7, A8, A9) E
F
– Etc. G
H
• [Why constraint satisfaction?] I

Department of
CSE
 Cryptarithmetic Problem
Rules for Solving Cryptarithmetic Problems
• Each Letter, Symbol represents only one digit throughout the
problem.
• Numbers must not begin with zero i.e. 0567 (wrong) 567 (correct).
• Aim is to find the value of each letter in the Cryptarithmetic problems
• The numerical base, unless specifically stated, is 10.
• After replacing letters with their digits, the resulting arithmetic
operations must be correct.
• Carry over can only be 1 in Cryptarithmetic problems

Department of
CSE
CSP Example: Cryptharithmetic puzzle

Department of
CSE
EAT + THAT = APPLE

• 3 digit number (EAT) + 4 digit number(THAT) = 5 digit number(APPLE)

If so, then A can be 1 and p can be 0.
Again here T is yielding a two-digit number(10).
So there must be a carry 1 and T = 9.
• Now the expression becomes
E19
9H19
-------------------
100LE
• Now it is clear that E = 8 and L = 3
• So, A + T + L = 1 + 9 + 3 =13

Department of
CSE
The puzzle SEND + MORE = MONEY, after solving, will appear like
this

.
Ans. The heuristics and production rules are specific to the following example:
Heuristics Rules
1. If the sum of two “n” digit operands yields an “n+1” digit result then the “n+1”th digit has
to be one.
2. Sum of two digits may or may not generate a carry.
3. Whatever might be the operands the carry can be either 0 or 1.
4. No two distinct alphabets can have the same numeric code.
5. Whenever more than 1 solution appears to be existing, the choice is governed by the fact
that no two alphabets can have the same number code.

Department of
CSE
 C4 C3 C2 C1 X= {S,E,N,D,M,O,R,Y}
S E N D D+ E= Y +10.C1
+ MO R E C1+N+R=E+10.C2
-------------------- C2+E+O=N+10.C3
M O N E Y C3+S+M=O+10.C4
C4=M=1
• M =1 , so S will be 8 or 9 depends on c3.
• Say S=9 ,then C3=0, O =0, C2=1(since E≠N), E+1=N
• C1+N+R=E+10.C2
Þ C1+E+1+R=E+10
Þ C1 +R=9 (Since S=9, so C1 must be 1 and R=8)
Department of
CSE
• S= 9 ,E= , N= , D= , M= 1 , O= 0 , R= 8 ,Y=
• D+ E should give carry bit.
Þ Y can’t be equal to 0 or 1,so D+E >= 12.
• Now D ≠ 9/8, say D =7, so to get the value of Y, E should be
either 5 or 6.
• Say E=6 then 7+6=13, so Y=3 and N=7 (not possible, because
D=7), so the partial assignment is inconsistent.
• Now say E=5, then 7+5 =12, so Y=2 and N=6.
• S= 9 ,E= 5 , N=6 , D=7 , M= 1 , O= 0 , R= 8 ,Y=2
• S E N D + M O R E = M O N E Y.
•Department
9 5 6 of7 + 1 0 8 5= 1 0 6 5 2
CSE
C3 C2 C1

TWO O + O = R + 10.C1
TWO C1 +W +W =U +10.C2
----------- C2 +T +T =O +10.C3
F O U R C3= F =1
• If we will add one number with itself we will get even number.
• T>=5,so that we can get c3=1
• O can be 0/2/4/6/8
• Say O=0,then R=0 (not possible)
• Then say O=2,then R=4 and T=6,then C2=0 ,then W<5,but
W≠0,1,2,3,4, because O=2,F=1,T=6; so this assignment is
inconsistent.
Department of
CSE
C3 C2 C1

TWO O + O = R + 10.C1
TWO C1 +W +W =U +10.C2
----------- C2 +T +T =O +10.C3
F O U R C3= F =1
Say O=4,then R=8, T=7, C1=0,now W should be less than 5.
W can’t be 0,1,2. Let W=3,then U=6.
So we can get complete assignment:
F=1 , O=4,U=6,R=8, T=7,W=3.
7 4 3 + 7 4 3 = 1 4 8 6.
Department of
CSE
 CROSS + ROADS =DANGER
Constraints:
CROSS
Alldiff( A, C,D,E,G,N,O,R,S)
+R O A D S
S+ S= R + 10. C1
--------------- C1+S +D=E +10.C2
D A N G ER C2+O+A=G +10.C3
C3+R+O=N +10.C4
C4 +C +R =A +10.C5
C5= D=1

Department of
CSE
 A=5 , C=9 , D=1 ,E=4 ,G= 7,N=8 ,O= 2,R=6 ,S= 3, C1=0 ,C2= 0 ,C3= , C4=0,C5=1

S+ S= R + 10. C1
R should be an even number.
R may have 0,2,4,6,8
R can’t be 0 , 2
Let R=6, then S=3 ,C1=0 , D=1
THEN E=4 and C2=0.
Since R=6, we have to assign C>= 5 , so that we can get a carry bit, C5=1.
Let C=9, then A will be 5 by considering C4=0.
Now since C4=0 ,so O < 4. O≠ 1, 3,4 so O=2.
Then N=8 and G=7.

Department of
CSE
 9 6 2 3 3
6 2 5 13
CROSS
------------------ +ROADS
---------------
1 5 8 7 4 6 DANGER

Other Solutions:
59488 + 64218 = 123706
90733 + 67513 = 158246
92344 + 83714 = 176058

Department of
CSE
 CONSTRAINT PROPAGATION: INFERENCE IN CSPS
• In CSPs an algorithm can search (choose a new variable assignment
from several possibilities) or do a specific type of inference called
constraint propagation.
• Constraint propagation uses the constraints to reduce the number
of legal values for a variable, which can reduce the legal values for
another variable, and so on.
• Constraint propagation may be intertwined with search, or it may be
done as a preprocessing step before the search starts. Sometimes
this preprocessing can solve the whole problem, so no search is
required at all.
Department of
CSE
 Local consistency
• If we treat each variable as a node in a graph and each
binary constraint as an arc, then the process of
enforcing local consistency in each part of the graph
causes inconsistent values to be eliminated throughout
the graph. There are different types of local
consistency, which we now cover in turn.

Department of
CSE
 Node-consistent
• A single variable (corresponding to a node in the CSP
network) is node-consistent if all the values in the variable’s
domain satisfy the variable’s unary constraints.
• For example, in the variant of the Australia map-coloring
problem where South Australians dislike green, the variable
SA starts with domain {red , green, blue}, and we can make it
node consistent by eliminating green, leaving SA with the
reduced domain {red , blue}.
• We say that a network is node-consistent if every variable in
the network is node-consistent.
Department of
CSE
 Arc-consistent
• A variable in a CSP is arc-consistent if every value in its domain satisfies
the variable’s binary constraints. More formally, Xi is arc-consistent with
respect to another variable Xj if for every value in the current domain Di
there is some value in the domain Dj that satisfies the binary constraint
on the arc (Xi, Xj).
• A network is arc-consistent if every variable is arc-consistent with every
other variable. For example, consider the constraint Y = X^2 where the
domain of both X and Y is the set of digits. We can write this constraint
explicitly as <(X, Y ), {(0, 0), (1, 1), (2, 4), (3, 9))}> .
• To make X arc consistent with respect to Y, we reduce X’s domain to {0, 1,
2, 3}. If we also make Y arc-consistent with respect to X, then Y ’s domain
becomes {0, 1, 4, 9} and the whole CSP is arc-consistent.
Department of
CSE
Department of
CSE
 AC-3 Algorithm
• The arc-consistency algorithm AC-3.
• After applying AC-3, either every arc is arc-consistent, or
some variable has an empty domain, indicating that the
CSP cannot be solved.
• The name “AC-3” was used by the algorithm’s inventor
(Mackworth, 1977) because it’s the third version
developed in the paper.

Department of
CSE
• To make every variable arc-consistent, the AC-3 algorithm maintains a queue of arcs to
consider. (Actually, the order of consideration is not important, so the data structure
is really a set, but tradition calls it a queue.)
• Initially, the queue contains all the arcs in the CSP. AC-3 then pops off an arbitrary arc
(Xi,Xj) from the queue and makes Xi arc-consistent with respect to Xj . If this leaves Di
unchanged, the algorithm just moves on to the next arc. But if this revises Di (makes
the domain smaller), then we add to the queue all arcs (Xk,Xi) where Xk is a neighbor
of Xi.
• We need to do that because the change in Di might enable further reductions in the
domains of Dk, even if we have previously considered Xk. If Di is revised down to
nothing, then we know the whole CSP has no consistent solution, and AC-3 can
immediately return to failure.
• Otherwise, we keep checking, trying to remove values from the domains of variables
until no more arcs are in the queue. At that point, we are left with a CSP that is
equivalent to the original CSP—they both have the same solutions—but the arc-
consistent CSP will in most cases be faster to search because its variables have smaller
domains.
Department of
CSE
 • Set of Arcs=
{(WA,NT),(WA,SA),(NT,Q),(NT,SA),(SA,Q),
(SA,NSW),(SA,V),(Q,NSW),(NSW,V)}
• Let’s start with WA, then its domain ={R,G,B}
• Let WA=R, then NT’s domain will reduce to
{G,B}
• Say NT=B, then SA’s domain will have {G}.
• So, SA=G
• Now the other assignments will be
• Q=R ,NSW=B, V=R, T=G
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
 Path consistency
• A two-variable set {Xi,Xj} is path-consistent with respect to a third variable Xm if, for
every assignment {Xi = a,Xj = b} consistent with the constraints on {Xi,Xj}, there is an
assignment to Xm that satisfies the constraints on {Xi,Xm} and {Xm,Xj}. This is called
path consistency because one can think of it as looking at a path from Xi to Xj with Xm
in the middle.
• Let’s see how path consistency fares in coloring the Australia map with two colors. We
will make the set {WA,SA} path consistent with respect to NT. We start by enumerating
the consistent assignments to the set. In this case, there are only two: {WA = red ,SA =
blue} and {WA = blue,SA = red}. We can see that with both of these assignments NT can
be neither red nor blue (because it would conflict with either WA or SA).
• Because there is no valid choice for NT, we eliminate both assignments, and we end up
with no valid assignments for {WA,SA}. Therefore, we know that there can be no
solution to this problem.

Department of
CSE
 K-CONSISTENCY
• A CSP is k-consistent if, for any set of k − 1 variable and for
any consistent assignment to those variables, a consistent
value can always be assigned to any kth variable.
• 1-consistency says that, given the empty set, we can make
any set of one variable consistent: this is what we called
node consistency.
• 2-consistency is the same as arc consistency.
• For binary constraint networks, 3-consistency is the same
as path consistency.
Department of
CSE
 Backtracking search
• Depth-first search in the context of CSP is also called
“backtracking”
• Chooses values for one variable at a time and
backtracks when a variable has no legal values left to
assign.
• We have a standard representation. No need for a
domain-specific initial state, successor function, or goal
test.

Department of
CSE
Department of
CSE
 Improving CSP efficiency
• Previous improvements on uninformed search
 introduce heuristics
• Instead, we can add some sophistication to the unspecified
functions by using them to address the following questions:
1. Which variable should be assigned next (SELECT-UNASSIGNED-VARIABLE),
and in what order should its values be tried (ORDER-DOMAIN-VALUES)?
2. What inferences should be performed at each step in the search
(INFERENCE)?
3. When the search arrives at an assignment that violates a constraint, can
the search avoid repeating this failure?

Department of
CSE
 Variable and value ordering
• The backtracking algorithm contains the line
var ←SELECT-UNASSIGNED-VARIABLE(csp) .
• The simplest strategy for SELECT-UNASSIGNED-VARIABLE is to choose the next
unassigned variable in order, {X1,X2, . . .}. This static variable ordering seldom results in
the most efficient search.
• For example, after the assignments for WA=red and NT =green, there is only one
possible value for SA, so it makes sense to assign SA=blue next rather than assigning Q. In
fact after SA is assigned, the choices for Q, NSW, and V are all forced.
• This intuitive idea—choosing the variable with the fewest “legal” values—is called the
minimum-remaining-values (MRV) heuristic.
• It also has been called the “most constrained variable” or “fail-first” heuristic, the latter
because it picks a variable that is most likely to cause a failure soon, thereby pruning the
search tree.

Department of
CSE
 Variable and value ordering
• The MRV heuristic doesn’t help at all in choosing the
first region to color in Australia, because initially, every
region has three legal colors.
• In this case, the degree heuristic comes in handy. It
attempts to reduce the branching factor on future
choices by selecting the variable that is involved in the
largest number of constraints on other unassigned
variables.
• In Map coloring problem, SA is the variable with the
highest degree, 5; the other variables have degrees 2
or 3, except for T, which has degree 0.
• In fact, once SA is chosen, applying the degree
heuristic solves the problem without any false steps—
you can choose any consistent color at each choice
point and still arrive at a solution with no backtracking.
• The minimum-remaining values heuristic is usually a
more powerful guide, but the degree heuristic can be
useful as a tie-breaker.
Department of
CSE
 • Once a variable has been selected, the algorithm must
Variable and value decide on the order in which to examine its values.

ordering • For this, the least-constraining-value heuristic can be

effective in some cases. It prefers the value that rules
out the fewest choices for the neighboring variables in
the constraint graph.
• For example, suppose that in we have generated the
partial assignment with WA=red and NT =green and
that our next choice is for Q. Blue would be a bad
choice because it eliminates the last legal value left for
Q’s neighbor, SA. The least-constraining-value
heuristic, therefore, prefers red to blue.
• In general, the heuristic is trying to leave the
maximum flexibility for subsequent variable
assignments.

Department of
CSE
 CSP example: map coloring

• Solutions are assignments satisfying all constraints, e.g.

{WA=red,NT=green,Q=red,NSW=green,V=red,SA=blue,T=green}

Department of
CSE
 Forward checking (INFERENCE)

• Can we detect inevitable failure early?

– And avoid it later?
• Forward checking idea: keep track of remaining legal values
for unassigned variables.
• Terminate search when any variable has no legal values.
Department of
CSE
 Forward checking

• Assign {WA=red}
• Effects on other variables connected by constraints to WA
– NT can no longer be red
– SA can no longer be red
• Note: this example is not using MRV; if it were, we would choose NT or SA next. But, we
will choose Q next. This example is from the text. It shows the example here, then talks
through what would happen if we had used MRV.
Department of
CSE
 Forward checking

• Assign {Q=green}
• Effects on other variables connected by constraints with
WA
– NT can no longer be green
– NSW can no longer be green
– SA can noDepartment
longer beofgreen
CSE
 Forward checking

• Assign {V=blue}
• Effects on other variables connected by constraints with WA
– NSW can no longer be blue
– SA is empty
• Forward Checking has detected that partial assignment is inconsistent with the constraints and
backtracking can occur.

Department of
CSE
 Intelligent backtracking: Looking backward
• The BACKTRACKING-SEARCH algorithm has a very simple
policy for what to do when a branch of the search fails:
– back up to the preceding variable and try a different value for it.
This is called chronological backtracking because the most recent
decision point is revisited.

Department of
CSE
 Intelligent backtracking: Looking backward
• Consider what happens when we apply simple backtracking with a fixed
variable ordering Q, NSW, V , T, SA, WA, NT. Suppose we have generated
the partial assignment {Q=red,NSW =green, V =blue, T =red}. When we
try the next variable, SA, we see that every value violates a constraint.
We back up to T and try a new color for it, but it won’t help.
• A more intelligent approach to backtracking is to backtrack to a variable
that might fix the problem—a variable that was responsible for making
one of the possible values of SA impossible. To do this, we will keep
track of a set of assignments that are in conflict with some value for SA.
The set (in this case {Q=red ,NSW =green, V =blue, }), is called the
conflict set for SA.
Department of
CSE
 Intelligent backtracking: Looking backward
• The backjumping method backtracks to the most recent
assignment in the conflict set; in this case, backjumping
would jump over Tasmania and try a new value for V . This
method is easily implemented by a modification to
BACKTRACK such that it accumulates the conflict set while
checking for a legal value to assign. If no legal value is found,
the algorithm should return the most recent element of the
conflict set along with the failure indicator.

Department of
CSE
 Local search for CSPs
• Local search algorithms turn out to be effective in solving
many CSPs. They use a complete-state formulation: the
initial state assigns a value to every variable, and the search
changes the value of one variable at a time.
• In choosing a new value for a variable, the most obvious
heuristic is to select the value that results in the minimum
number of conflicts with other variables—the min-conflicts
heuristic.

Department of
CSE
Department of
CSE
Department of
CSE
•
Local search for CSPs
Use complete-state representation
– Initial state = all variables assigned values
– Successor states = change a value
• For CSPs
– allow states with unsatisfied constraints (unlike backtracking)
– operators reassign variable values
– hill-climbing with n-queens is an example (we saw in earlier notes)
• Variable selection: randomly select any conflicted variable
• Value selection: min-conflicts heuristic
– Select new value that results in a minimum number of conflicts with the other
variables

Department of
CSE
 Advantages of local search

• Local search can be particularly useful in an online setting

– Airline schedule example
• E.g., mechanical problems require that a plane is taken out of service
• Can locally search for another “close” solution in state-space
• Much better (and faster) in practice than finding an entirely new schedule
• The runtime of min-conflicts is roughly independent of problem size for the 8-queens
(observation in the 1990’s that gave rise to much research).
– Can solve the millions-queen problem in roughly 50 steps.
– Why?
• n-queens is easy for local search because of the relatively high density of
solutions in state-space

Department of
CSE
 Summary
• CSPs
– special kind of problem: states defined by values of a fixed set of
variables, goal test defined by constraints on variable values
• Backtracking=depth-first search with one variable assigned per
level
• Heuristics
– Variable ordering and value selection heuristics help significantly
• Constraint propagation does additional work to constrain values
and detect inconsistencies
– Works effectively when combined with heuristics
• Iterative min-conflicts is often effective in practice.
Department of
CSE
 Game Theory?
• 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.
• In AI, the most common games are of a rather specialized kind—what game
theorists call deterministic, turn-taking, two-player, zero-sum games of perfect
information (such as chess).
• In our terminology, this means deterministic, fully observable environments in
which two agents act alternately and in which the utility values at the end of the
game are always equal and opposite.
• For example, if one player wins a game of chess, and the other player necessarily
loses. It is this opposition between the agents’ utility functions that make the
situation adversarial.
Department of
CSE
 Why Game Theory?
For AI researchers, the abstract nature of games makes them an appealing subject for
study.
• The state of a game is easy to represent, and agents are usually restricted to a small
number of actions whose outcomes are defined by precise rules.
• They provide a structured task in which it is very easy to measure success or failure.
• They do not require large amounts of knowledge. They are thought to be solvable by
a straightforward search from the starting state to a winning position.
• For example, chess has an average branching factor of about 35, and games often go
to 50 moves by each player, so the search tree has about or nodes
(although the search graph has “only” about (10) ^40 distinct nodes).
( 35 ) 100

• Games, like the real world, therefore require the ability to make some decisions even
when calculating the optimal decision is infeasible.
Department of
CSE
 Two-Player Game
• We first consider games with two players, MAX and MIN. MAX moves first, and then they take turns
moving until the game is over.
• A game can be formally defined as a kind of search problem with the following elements:
– S0: The initial state, which specifies how the game is set up at the start.
– PLAYER(s): Defines which player has the move in a state.
– ACTIONS(s): Returns the set of legal moves in a state.
– RESULT(s, a): The transition model, which defines the result of a move.
– TERMINAL-TEST(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), defines
the final numeric value for a game that ends in terminal state s for a player p. In chess, the
outcome is a win, loss, or draw, with values +1, 0.

Department of
CSE
 Game Tree
• The initial state, ACTIONS function, and RESULT function define the game tree for the
game—a tree where the nodes are game states and the edges are moves.
• Consider the figure of a (partial) game tree for the game of tic-tac-toe. The top node is
the initial state, and MAX moves first, placing an X in an empty square. We show part of
the tree, giving alternating moves by MIN (O) and MAX (X) until we eventually reach
terminal states, which can be assigned utilities according to the rules of the game.
• For tic-tac-toe the game tree is relatively small—fewer than 9! = 362, 880 terminal nodes.
But for chess there are over (10) ^40 nodes, so the game tree is best thought of as a
theoretical construct that we cannot realize in the physical world.
• But regardless of the size of the game tree, it is MAX’s job to search for a good move. We
use the term search tree for a tree that is superimposed on the full game tree and
examines enough nodes to allow a player to determine what move to make.

Department of
CSE
Department of
CSE
 A Two-ply Game Tree

Department of
CSE
 A Two-ply Game Tree
• The possible moves for MAX at the root node are labeled a1, a2, and a3. The possible
replies to a1 for MIN are b1, b2, b3, and so on. This particular game ends after one move
each by MAX and MIN. The utilities of PLY the terminal states in this game range from 2
to 14.
• Given a game tree, the optimal strategy can be determined from the minimax value of
each node, which we write as MINIMAX(n). The minimax value of a node 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. Obviously, the minimax value of a terminal state is
just its utility.
• MAX prefers to move to a state of maximum value, whereas MIN prefers a state of
minimum value.

Department of
CSE
• The terminal nodes on the bottom
level get their utility values from the
game’s UTILITY function. The first MIN
node, labeled B, has three successor
states with values 3, 12, and 8, so its
minimax value is 3. Similarly, the other
two MIN nodes have minimax value 2.
The root node is a MAX node; its
successor states have minimax values 3,
2, and 2; so it has a minimax value of 3.
• The minimax decision at the root:
action a1 is the optimal choice for
MAX because it leads to the state
with the highest minimax value.
Department of
CSE
 The minimax algorithm

Department of
CSE
 The minimax algorithm
• The minimax algorithm (Figure 5.3) 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.
• For example, in Figure 5.2, the algorithm first recurses down to the three bottoms left nodes and uses the
UTILITY function on them to discover that their values are 3, 12, and 8, respectively. Then it takes the
minimum of these values, 3, and returns it as the backup value of node B. A similar process gives the
backed-up values of 2 for C and 2 for D. Finally, we take the maximum of 3, 2, and 2 to get the backed-up
value of 3 for the root node.
• The minimax algorithm performs a complete depth-first exploration of the game tree. If the maximum
depth of the tree is m and there are b legal moves at each point, then the time complexity of the minimax
algorithm is O(b^m). The space complexity is O(bm) for an algorithm that generates all actions at once or
O(m) for an algorithm that generates actions one at a time.
• This algorithm serves as the basis for the mathematical analysis of games and for more practical
algorithms.

Department of
CSE
 Three-player Game

Department of
CSE
 ALPHA–BETA PRUNING
• The problem with minimax search is that the number of game states
it has to examine is exponential in the depth of the tree.
Unfortunately, we can’t eliminate the exponent, but it turns out we
can effectively cut it in half. The trick is that it is possible to compute
the correct minimax decision without looking at every node in the
game tree. That is, we can borrow the idea of pruning to eliminate
large parts of the tree from consideration.
• The particular technique we examine is called alpha-beta pruning.
When applied to a standard minimax tree, it returns the same move
as minimax would, but prunes away branches that cannot possibly
influence the final decision.
Department of
CSE
Department of
CSE
• Alpha–beta pruning can be applied to trees of any depth, and it is often possible
to prune entire subtrees rather than just leaves.
• Minimax search is depth-first, so at any one time, we just have to consider the
nodes along a single path in the tree.
• Alpha–beta pruning gets its name from the following two parameters that
describe bounds on the backed-up values that appear anywhere along the path:
– α = the value of the best (i.e., highest-value) choice we have found so far at any choice
point along the path for MAX.
– β = the value of the best (i.e., lowest-value) choice we have found so far at any choice
point along the path for MIN.
• Alpha–beta search updates the values of α and β as it goes along and prunes the
remaining branches at a node (i.e., terminates the recursive call) as soon as the
value of the current node is known to be worse than the current α or β value for
MAX or MIN, respectively.

Department of
CSE
Department of
CSE
Department of
CSE
Department of 2<3, min(3,2)
CSE
 14>3
Department of
CSE
Department of
CSE
1. Apply alpha-beta pruning for the given game-tree

Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
2. Apply alpha-beta pruning for the given game-tree

Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE
Department of
CSE