Module – 3 (Search in Complex environments)

Adversarial search – Games, Optimal decisions in games, The Minimax algorithm, Alpha-
Beta pruning. Constraint Satisfaction Problems – Defining CSP, Constraint Propagation-
inference in CSPs, Backtracking search for CSPs, Structure of CSP problems.

1. Write a note on adversarial search?

• In artificial intelligence, deep learning, machine learning, adversarial search is basically a
kind of search in which one can trace the movement of an enemy.
• Searches, in which two or more players with conflicting goals are trying to explore the
same search space for the solution, are called adversarial searches, often known as
Games.
• Adversarial search problems typically exist in two-player games where the players' actions
alternate.
• Examples are chess, checkers, and tic-tac-toe etc.
2) Discuss different types of Games in Al?
1. Perfect information:
 A game with the perfect information is that in which agents can look into the complete
board. Agents have all the information about the game, and they can see each other moves
also.
• Examples are Chess, Checkers, Go, etc.
2. Imperfect information:
• Game agents do not have all information about the game and not aware with what's going
on, such type of games are called the game with imperfect information.
• Examples are such as Battleship, blind, Bridge, etc.
3. Deterministic games:
• Deterministic games are those games which follow a strict pattern and set of rules for the
games and there is no randomness associated with them.
• Examples are chess, Checkers, Go, tic-tac-toe, etc.
4. Non-deterministic games:
 • Non-deterministic are those games which have various unpredictable events and have a
factor of chance or luck.
• This factor of chance or luck is introduced by either dice or cards.
• These are random, and each action response is not fixed. Such games are also called as
stochastic games.
• Example: Backgammon, Monopoly, Poker, etc.
3) Write standard formalization of a game?
• Initial state: It specifies how the game is set up at the start.
• Player(s): It specifies which player has moved in the state space.
• Action(s): It returns the set of legal moves in state space.
• Result(s, a): It is the transition model, which specifies the result of moves in the state
space.
• Terminal-Test(s): Terminal test is true if the game is over, else it is false at any case. The
state where the game ends is called terminal states.
• Utility(s, p): A utility function gives the final numeric value for a game that ends in
terminal states s for player p. It is also called payoff function. For Chess, the outcomes are
a win, loss, or draw and its payoff values are +1, 0, ½. And for tic-tac-toe, utility values are
+1, -1, and 0.
4) Write a note on Game Tree?
• A game tree is a tree where nodes of the tree are the game states and Edges of the tree are
the moves by players.
• Game tree involves initial state, actions function, and result Function.
• Example: Tic-Tac-Toe game tree:
• The following figure is showing part of the game-tree for tic-tac-toe game. Following are
some key points of the game:
 There are two players MAX and MIN.
 Players have an alternate turn and start with MAX.
 MAX maximizes the result of the game tree.
 MIN minimizes the result.
• Following are the standard formalization of a Tic-Tac-Toe game tree.
1. INITIAL STATE (Se): The top node in the game-tree represents the initial state in the tree
and shows all the possible choice to pick out one.
2. PLAYER (s): There are two players, MAX and MIN. MAX begins the game by picking
one best move and place X in the empty square box.
3. ACTIONS (s): Both the players can make moves in the empty boxes chance by chance.
4. RESULT (s, a): The moves made by MIN and MAX will decide the outcome of the game.
5. TERMINAL-TEST(s): When all the empty boxes will be filled, it will be the terminating
state of the game.
6. UTILITY: At the end, we will get to know who wins: MAX or MIN, and accordingly, the
price will be given to them. (-1): If the PLAYER loses. (+1): If the PLAYER wins. (0): If
there is a draw between the PLAYERS.
5) Discuss MiniMax Search algorithm?
o Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-
making and game theory. It provides an optimal move for the player assuming that
opponent is also playing optimally.
o The minimax algorithm performs a depth-first search algorithm for the exploration of the
complete game tree.
o The minimax algorithm proceeds all the way down to the terminal node of the tree, then
backtrack the tree as the recursion.

Working of Min-Max Algorithm

o The working of the minimax algorithm can be easily described using an example. Below
we have taken an example of game-tree which is representing the two-player game.
o In this example, there are two players one is called Maximizer and other is called
Minimizer. Maximizer will try to get the Maximum possible score, and Minimizer will try
to get the minimum possible score.
o This algorithm applies DFS, so in this game-tree, we have to go all the way through the
leaves to reach the terminal nodes.
o At the terminal node, the terminal values are given so we will compare those values and
backtrack the tree until the initial state occurs. Following are the main steps involved in
solving the two-player game tree:
Step-1: In the tree diagram, let's take A is the initial state of the tree. Suppose maximizer
takes first turn which has worst-case initial value =- infinity, and minimizer will take next turn
which has worst-case initial value = +infinity.

Step 2: Now, first we find the utilities value for the Maximizer, it compare each value in terminal
state with initial value of Maximizer and determines the higher nodes values. It will find the
maximum among the all.

o For node D max(-1,4)= 4

o For Node E max(2, 6)= 6
o For Node F max(-3,-5) = -3
o For node G max(0, 7) = 7

Step 3: In the next step, it's a turn for minimizer, so it will compare all nodes value with +∞, and
will find the 3rd layer node values.

o For node B= min(4,6) = 4

o For node C= min (-3, 7) = -3
Step 4: Now it's a turn for Maximizer, and it will again choose the maximum of all nodes value
and find the maximum value for the root node. In this game tree, there are only 4 layers,
hence we reach immediately to the root node, but in real games, there will be more than 4
layers.
o For node A max(4, -3)= 4

 That was the complete workflow of the minimax two player game.

Properties of Mini-Max algorithm:

o Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in
the finite search tree.
o Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.
o Time complexity- As it performs DFS for the game-tree, so the time complexity of Min-
Max algorithm is O(bm), where b is branching factor of the game-tree, and m is the
maximum depth of the tree.
o Space Complexity- Space complexity of Mini-max algorithm is also similar to DFS which
is O(bm).

Limitation of the minimax Algorithm:

 The main drawback of the minimax algorithm is that it gets really slow for complex games
such as Chess, go, etc.
  This type of games has a huge branching factor, and the player has lots of choices to
decide. This limitation of the minimax algorithm can be improved from alpha-beta
pruning.

6) Discuss Alpha-Beta Pruning method?

• The problem with minimax search is that the number of game states it has to examine is
exponential in the depth of the tree. To avoid this it is possible to compute the correct
minimax decision without looking at every node in the game tree by pruning
• Alpha–beta pruning can be applied to trees of any depth, and it is often possible to prune
entire sub trees rather than just leaves.
• α = 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 as soon as the value of the current node is known to be worse than the
current α or β value for MAX or MIN, respectively

Working of Alpha-Beta Pruning:

Step 1: At the first step the, Max player will start first move from node A where α= -∞ and β= +∞, these
values passed down to node B where again α= -∞ and β= +∞, and B passes the same value to its child D.
Step 2: At Node D, the value of α will be calculated as its turn for Max. The value of α is compared with
firstly 2 and then 3, and the max (2, 3) = 3 will be the value of α at node D and node value will also 3.
Step 3: Now backtrack to B, where the value of β will change. Now β= +∞, will compare with the available
subsequent nodes value, i.e. min (∞, 3) = 3, hence at node B now α= -∞, and β= 3.

In the next step, algorithm traverse the next successor of Node B which is node E, and the values of α= -∞,
and β= 3 will also be passed.
Step 4: At node E, Max will take its turn, and the value of alpha will change. The current value of alpha
will be compared with 5, so max (-∞, 5) = 5, hence at node E α= 5 and β= 3, where α>=β, so the right
successor of E will be pruned, and algorithm will not traverse it, and the value at node E will be 5.
7) Explain Constraint propagation: Inference in CSPs?
 Using the constraints to reduce the number of legal values for a variable, which in turn can
reduce the legal values for another variable, and so on is called Constraint propagation.
 Constraint propagations are of 2 types
1. Global consistency
2. Local consistency
Global consistency
• A global constraint is one involving an arbitrary number of variables (but not necessarily
all variables).
• Global constraints can be handled by special-purpose algorithms that are more efficient
than general-purpose methods.
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:
1. Node consistency
2. Arc consistency
3. Path consistency
4. K- consistency
Node consistency
• A single variable (a node in the CSP network) is node-consistent if all the values in the
variable’s domain satisfy the variable’s unary constraint.
• We say that a network is node-consistent if every variable in the network is node-
consistent.
• Eg: variant of the Australia map-coloring problem with 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}.
Arc consistency
• A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s
binary constraints.
 • 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 = X2 where the domain of both X and Y is the set
of digits.
• The constraint can be written 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}.
• To make Y arc-consistent with respect to X, then Y ’s domain becomes {0, 1, 4, 9} and the
whole CSP is arc-consistent.
3. 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 constraint on {Xi, Xj},
 there is an assignment to Xm that satisfies the constraints on {Xi, Xm} and {Xm, Xj}.
• Path consistency tightens the binary constraints by using implicit constraints that are
inferred by looking at triples of variables.
Example: 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.
5. K-consistency:
• Stronger forms of propagation can be defined with the notion of k-consistency.
• 1-consistency = node consistency;
• 2-consisency = arc consistency;
 • 3-consistency = path consistency.
• A CSP is strongly k-consistent: if it is k-consistent and is also (k - 1)-consistent, (k – 2)-
consistent, all the way down to 1-consistent.
• A CSP with n nodes and make it strongly n-consistent, we are guaranteed to find a solution
in time O(n2d).
• But algorithm for establishing n-consistency must take time exponential in n in the worse
case, also requires space that is exponential in n.
8) Explain backtrack search in CSP?
• Backtracking search is a depth-first search that chooses values for one variable at a time
and backtracks when a variable has no legal values left to assign.
• Backtracking algorithm repeatedly chooses an unassigned variable, and then tries all values
in the domain of that variable in turn, trying to find a solution.
• If an inconsistency is detected, then BACKTRACK returns failure, causing the previous
call to try another value.
• There is no need to supply BACKTRACKING-SEARCH with a domain-specific initial
state, action function, transition model, or goal test.
Backtrack algorithm
Example: 4-Queens backtracking (Refer Notebook)

8) What is a Constraint Satisfaction Problem (CSP)?

 A Constraint Satisfaction Problem is a mathematical problem where the solution must
meet a number of constraints. In a CSP, the objective is to assign values to variables such
that all the constraints are satisfied. CSPs are used extensively in artificial intelligence for
decision-making problems where resources must be managed or arranged within strict
guidelines.
Common applications of CSPs include:
 Scheduling: Assigning resources like employees or equipment while respecting time and
availability constraints.
 Planning: Organizing tasks with specific deadlines or sequences.
 Resource Allocation: Distributing resources efficiently without overuse.
Components of Constraint Satisfaction Problems
CSPs are composed of three key elements:
1. Variables: The things that need to be determined are variables. Variables in a CSP are the
objects that must have values assigned to them in order to satisfy a particular set of
constraints. Boolean, integer, and categorical variables are examples of the variables.
2. Domains: The range of potential values that a variable can have is represented by domains.
Depending on the issue, a domain may be finite or limitless. For instance, in Sudoku, the
set of numbers from 1 to 9 can serve as the domain of a variable representing a problem
cell.
3. Constraints: The guidelines that control how variables relate to one another are known as
constraints. Constraints in a CSP define the ranges of possible values for variables. Unary
constraints, binary constraints, and higher-order constraints are only a few examples of the
various sorts of constraints.
Types of Constraints
1. Unary Constraints-A unary constraint in a Constraint Satisfaction Problem (CSP) is a
constraint that limits the values that can be assigned to a single variable. For example, in
map coloring, a unary constraint could be A≠Green.
 2. Binary Constraints-In these problems, each constraint involves only two variables. For
example, in a scheduling problem, the constraint could specify that task A must be
completed before task B.
3. Higher-order constraints -Higher-order constraints in a Constraint Satisfaction Problem
(CSP) involve three or more variables: Example: In cryptarithmetic, higher-order
constraints include column constraints.
9) Discuss structure of CSP problems?
 The structure of the problem can be represented by constraint graph and is used to find
solutions quickly.

 Eg: consider the above Australia map coloring problem, its constraint graph is shown in
figure. A constraint graph is a tree when 2 variables are connected by only one path.
How to solve a tree-structure CSP
 Pick any variable to be the root of the tree.
 Choose an ordering of the variable such that each variable appears after its parent in the
tree. (topological sort)
 Any tree with n nodes has n-1 arcs, so we can make this graph directed arc-consistent in
0(n) steps, each of which must compare up to d possible domain values for 2 variables, for
a total time of 0(nd2).
 Once we have a directed arc-consistent graph, we can just march down the list of variables
and choose any remaining value.
 Since each link from a parent to its child is arc consistent, we won't have to backtrack, and
can move linearly through the variables.
 There are 2 primary ways to reduce more general constraint graphs to trees.
1. Based on removing nodes
2. Based on collapsing nodes together(Tree decomposition)
Based on removing nodes

 The first way to reduce a constraint graph to a tree involves assigning values to some
variables so that the remaining variables form a tree.
 Consider the constraint graph for Australia, shown again in Figure (a). Without South
Australia, the graph would become a tree, as in (b).
 Fortunately, we can delete South Australia by fixing a value for SA and deleting from the
domains of the other variables any values that are inconsistent with the value chosen for
SA.
  Now, any solution for the CSP after SA and its constraints are removed will be consistent
with the value chosen for SA . Therefore, we can solve the remaining tree with the
algorithm given above and thus solve the whole problem.
 The general algorithm is as follows:
1. Choose a subset S of the CSP’s variables such that the constraint graph becomes a
tree after removal of S. S is called a cycle cutset.
2. For each possible assignment to the variables in S that satisfies all constraints on S,
(a) remove from the domains of the remaining variables any values that are
inconsistent with the assignment for S, and
(b) if the remaining CSP has a solution, return it together with the assignment for S.
Tree decomposition
The second way to reduce a constraint graph to a tree is based on constructing a tree
decomposition of the constraint graph: a transformation of the original graph into a tree where
each node in the tree consists of a set of variables, as in Figure.

Tree decomposition must satisfy these three requirements:

 Every variable in the original problem appears in at least one of the tree nodes.
 If two variables are connected by a constraint in the original problem, they must appear
together (along with the constraint) in at least one of the tree nodes.
 If a variable appears in two nodes in the tree, it must appear in every node along the path
connecting those nodes.

Q) (Refer Notebook for crypt arithmetic problems)