Syllabus

References
• Stuart Russel and Peter Norvig, Artificial Intelligence: A Modern
Approach, 4th edition, Pearson Education, 2021
• Elaine Rich, Kavin Knight, Shivshankar Nair, Artificial intelligence, 3rd
edition, Tata McGraw Hill, 2019
 Searching is the process in which a machine/AI finds the sequence of various steps
required to solve the given problem. It is of two major types-informed and
uninformed.

 An uninformed search is a searching technique that has no additional information

about the distance from the current state to the goal.

 Informed Search is another technique that has additional information about the
estimate distance from the current state to the goal.

4
Informed Search Vs Uninformed Search

5
Blind or Uniformed Search
 Searching without information.
 Do not have additional information about
states beyond the problem definition.
 Total search space is looked for a solution.
 No information is used to determine the
preference of one child over another.
 Examples: Breadth First Search(BFS),
Depth First Search(DFS)

Heuristic or Informed Search

 Searching with information.
 Some information about problem
space (heuristic) is used to
compute preferences among the
children for exploration and
expansion.
 Introduction
• Breadth-First Search algorithm is a graph traversing technique,
where you select a random initial node (source or root node) and start
traversing the graph layer-wise in such a way that all the nodes and
their respective children nodes are visited and explored.

• Depth-first search (DFS) is an algorithm for traversing or searching tree or

graph data structures.
• The algorithm starts at the root node (selecting some arbitrary node as the
root node in the case of a graph) and explores as far as possible along each
branch before backtracking.
• It uses last in- first-out strategy and hence it is implemented using a stack.

8
 Breadth-First Search(BFS)
• It is the most simple form of blind search. In this technique the root node is
expanded first, then all of its successors are expanded and then their successors
and so on….
• It Explores all the nodes at given depth before proceeding to the next level.
• It means that all immediate children of nodes are explored before any of the
children’s children are considered.
• It uses queue for implementation

9
 Breadth-First Search(BFS)
Algorithm:
i) Enter starting nodes on queue
ii) If queue is empty, then return fail and stop
iii) If first element on queue is GOAL node, then return success and stop
ELSE
iv) Remove and expand first element from queue and place children at end of
queue
v) Goto stop (ii)

10
This is Travelling
path

11
Let us now discuss the advantages and disadvantages of BFS-

Advantages of BFS
BFS has some advantages and are given below-
1. BFS will never get trapped exploring a blind alley
2. It is guaranteed to find a solution if one exists.

Disadvantages of BFS
BFS has certain disadvantages also. They are given below
1. Time complexity and space complexity are both i.e exponential type. This is a very big hurdle.
2. All nodes are to be generated in bfs. So even unwanted nodes are to be remembered (stored in
queue) which is of no practical use of the search.

12
Find the shortest path using BFS algorithm

13
14
15
16
 Breadth First Search

Goal

 BFS stands for Breadth First Search is a vertex based technique for finding a shortest path
in graph.
 It uses a Queue data structure which follows first in first out. In BFS, one vertex is selected
at a time when it is visited and marked then its adjacent are visited and stored in the queue.

 It is slower than DFS.

17
 Depth First Search (DFS)
• DFS begins by expanding the initial node ,generate all successors of the
initial node and test them.
• DFS is characterized by the expansion of the most recently generated or
deepest node first.
• DFS needs to store the path from the root to the leaf node as well as the
unexpanded nodes.
• It is neither complete nor optimal. If DFS goes down an infinite branch
(depth cut-off point) will not end till a goal state is found.
• If d is set too shallow, goal may be missed.
• If d is set too deep then extra computation may be performed.

18
• Starts from root node and follows each path to its greatest depth node before
moving to the next path.

• It is implemented using STACK (LIFO)

ALGORITHM:
i) Enter root node on stack
ii) Do until stack is not empty
a) Remove node
1) If node is Goal then stop
2) Push all children in stack.

19
DFS has two shortcomings:
It may miss the optimal path. DFS may expand
more nodes than necessary
DFS may never end! It may get stuck at
expanding the nodes that can’t lead to a target
node even if we use the graph-search version
of the algorithm
This is Travelling
path 21
This is Travelling
path

22
Advantages of DFS
DFS has some advantages. They are given below-
1. Memory requirements in dfs are less as only nodes on the current path
are stored.

2. Less time to reach goal node if traversal in right path.

Disadvantages of DFS
1. No guarantee of finding solutions.
2. This type of search can go on and on, deeper and deeper into the search and thus, we can get
lost. This is referred to as blind alley.

23
• In depth-first search, we start with the root node and completely explore the
descendants of a node before exploring its siblings (and siblings are explored
in a left-to right fas hion).
What is the
problem with DFS
Algorithm

Depth-first traversal: A -> B -> D -> E -> C -> F -> G

• The problem with depth-first search is that we may get lost in an infinite
branch, while there could be another short branch leading to a solution. Such
problems can be overcome by using breadth-first search, where we explore
(right-hand) siblings before children.
Breadth-first traversal: A -> B -> C -> D -> E -> F -> G
24
DFS Algorithm:

25
Find the shortest path using DFS algorithm

26
27
28
 Depth First Search

 DFS stands for Depth First Search is a edge based technique.

 It uses the Stack data structure, performs two stages, first visited vertices are pushed
into stack and second if there is no vertices then visited vertices are popped.

29
[Link] Breadth First Search (BFS) Depth First Search (DFS)
1 BFS stands for Breadth First Search. DFS stands for Depth First Search.

2 BFS (Breadth First Search) uses Queue data DFS (Depth First Search) uses Stack data
structure for finding the shortest path. structure.

3 BFS can be used to find single source In DFS, we might traverse through more edges
shortest path in an unweighted graph, to reach a destination vertex from a source.
because in BFS, we reach a vertex with
minimum number of edges from a source
vertex.
4 BFS is more suitable for searching vertices DFS is more suitable when there are solutions
which are closer to the given source. away from source.

5 BFS considers all neighbours first and DFS is more suitable for game or puzzle
therefore not suitable for decision making problems. We make a decision, then explore all
trees used in games or puzzles. paths through this decision. And if this decision
leads to win situation, we stop
30
Consider the graph shown below, starting from node A to goal node G.
Perform step-wise analysis of the DFS and BFS algorithm. Consider traversal
from left side.
Consider the graph shown below, starting from node A to goal node G.
Perform step-wise analysis of the DFS and BFS algorithm. Consider traversal
from left side.
Uniform Cost Search algorithm
 It is used for traversing a weighted tree or graph
 It comes into play when a different cost is available for each edge.
The goal of the uniform cost search algorithm is to find a path to the goal node
which has the lowest cumulative cost.
 It expands nodes according to their path costs from the root
 It can be used to solve any graph/tree where the optimal cost is in demand.
 A UCS algorithm is implemented by the priority queue
 It gives maximum priority to the lowest cumulative cost
 It is equivalent to BFS if the path cost of all edges is the same.
Advantage:
It is optimal because at every state the path with the least cost is chosen.
Disadvantage:
It does not care about the number of steps involved in searching and is only concerned about the path
cost.
Algorithm Steps
Searching with cost:
Solution:
This algorithm assumes that all operators have a cost
1. Initialize: Set OPEN ={s} , CLOSED={} ,c{s}=0
2. Fail : if OPEN={} , Terminate with failure
3. Select: Select a minimum cost state n,
From OPEN and save that n in CLOSED
4. Terminate: If N is Goal, terminate with success
5. Expand: Generate the successor of n
For each successor m:
If m is not [ OPEN and CLOSED]
Set c(m)= c(n)+c(n,m)
and insert m in OPEN
If m is in [OPEN and CLOSED]
Set c(m)= min{ c[m],c[n]+c[n,m]}
If c[m] has decreased and m is in CLOSED, MOVE it to
OPEN.
6. Go to step 2
Find the path using Uniform Cost Search algorithm
 How Greedy Best-First Search Works?
• Greedy Best-First Search works by evaluating the cost of each possible
path and then expanding the path with the lowest cost. This process is
repeated until the goal is reached.
• The algorithm uses a heuristic function to determine which path is the
most promising.
• The heuristic function takes into account the cost of the current path
and the estimated cost of the remaining paths.
• If the cost of the current path is lower than the estimated cost of the
remaining paths, then the current path is chosen. This process is
repeated until the goal is reached.
Unlocking Efficiency: How the Greedy Best First Search Algorithm Works
 Advantages of Greedy Best-First Search:
1. Simple and Easy to Implement: Greedy Best-First Search is a relatively
straightforward algorithm, making it easy to implement.
2. Fast and Efficient: Greedy Best-First Search is a very fast algorithm, making
it ideal for applications where speed is essential.
3. Low Memory Requirements: Greedy Best-First Search requires only a small
amount of memory, making it suitable for applications with limited
memory.
4. Flexible: Greedy Best-First Search can be adapted to different types of
problems and can be easily extended to more complex problems.
5. Efficiency: If the heuristic function used in Greedy Best-First Search is good
to estimate, how close a node is to the solution, this algorithm can be a
very efficient and find a solution quickly, even in large search spaces.
Disadvantages of Greedy Best-First Search:
• Inaccurate Results: Greedy Best-First Search is not always guaranteed to find
the optimal solution, as it is only concerned with finding the most promising
path.
• Local Optima: Greedy Best-First Search can get stuck in local optima, meaning
that the path chosen may not be the best possible path.
• Heuristic Function: Greedy Best-First Search requires a heuristic function in
order to work, which adds complexity to the algorithm.
• Lack of Completeness: Greedy Best-First Search is not a complete algorithm,
meaning it may not always find a solution if one is exists. This can happen if
the algorithm gets stuck in a cycle or if the search space is a too much
complex.
Greedy Best-First Search example
• Consider the below search problem , Find the path using greedy
best-first search. At each iteration, each node is expanded using
evaluation function f(n)=h(n) , which is given in the below table.
• In this search example, we are using two lists which
are OPEN and CLOSED Lists. Following are the iteration for traversing
Expand the nodes of S and put in the CLOSED
list

Initialization: Open [A, B], Closed [S]

Iteration 1: Open [A], Closed [S, B]
Iteration 2: Open [E, F, A], Closed [S, B]
: Open [E, A], Closed [S, B, F]
Iteration 3: Open [I, G, E, A], Closed [S, B, F]
: Open [I, E, A], Closed [S, B, F, G]
Hence the final solution path will be:
S----> B----->F----> G
 A* Search Algorithm
(Unleashing the Power of A* Search Algorithm: Finding the Optimal Path with Ease)
 A* search algorithm
• A* search is the most commonly known form of best-first search. It uses
heuristic function h(n), and cost to reach the node n from the start state g(n).
It has combined features of Uniform cost search and greedy best-first search,
by which it solve the problem efficiently.
• A* search algorithm finds the shortest path through the search space using
the heuristic function. This search algorithm expands less search tree and
provides optimal result faster. A* algorithm is similar to Uniform cost search
except that it uses g(n)+h(n) instead of g(n).
• In A* search algorithm, we use search heuristic as well as the cost to reach the
node. Hence we can combine both costs as following, and this sum is called as
a fitness number.
Eight Puzzle Problem
using A* search Algorithm
70
71
72
73
Solve by using A*
search algorithm
 Advantages and Disadvantages of A* Search
Advantages:
• A* search algorithm is the best algorithm than other search algorithms.
• A* search algorithm is optimal and complete.
• This algorithm can solve very complex problems.
Disadvantages:
• It does not always produce the shortest path as it mostly based on heuristics
and approximation.
• A* search algorithm has some complexity issues.
• The main drawback of A* is memory requirement as it keeps all generated
nodes in the memory, so it is not practical for various large-scale problems.
When A* is admissible
A* is admissible if the heuristic never overestimates the true cost to reach the
goal.
Admissible Heuristic Condition :

Where:
h(n) = heuristic estimate
h*(n) = actual minimum cost from n to goal

The heuristic must be optimistic➡ It can underestimate, but it must never

overestimate

Examples of admissible heuristics:

• Manhattan distance in grid pathfinding (no diagonal moves)
• Euclidean distance when movement is allowed in any direction
 Hill Climbing Algorithm
• The Hill climbing algorithm is a local search algorithm that continuously
moves in the direction of increasing elevation/value to find the peak of the
mountain or the best solution to the problem. It terminates when it reaches
a peak value where no neighbor has a higher value.
• The hill climbing algorithm is a technique that is used for optimizing
mathematical problems.
• One of the widely discussed examples of the Hill climbing algorithm is the
travel salesman problem in which we need to minimize the distance traveled
by the salesman.
• It is also called greedy local search as it only looks to its good immediate
neighbor state and not beyond that.
• A node of a hill climbing algorithm has two components which are state and
value.
 State-space Diagram for Hill Climbing:
• The state-space landscape is a graphical
representation of the hill-climbing algorithm
which shows a graph between various states of
the algorithm and Objective function/Cost.
• On the Y-axis we have taken the function which
can be an objective function or cost function,
and state-space on the x-axis.
• If the function on the Y-axis is cost then, the
goal of search is to find the global minimum
and local minimum.
• If the function of the Y-axis is the Objective
function, then the goal of the search is to find
the global maximum and local maximum.
Different regions in the state space landscape:
 Local Maximum: Local maximum is a state which is better than its neighbor
states, but there is also another state which is higher than it.

 Global Maximum: Global maximum is the best possible state of state space
landscape. It has the highest value of the objective function.

 Current state: It is a state in a landscape diagram where an agent is currently

present.

 Flat local maximum: It is a flat space in the landscape where all the neighbor
states of current states have the same value.
Problems in Hill Climbing Algorithm:
1. Local Maximum: A local maximum is a peak state in the landscape that is
better than each of its neighboring states, but there is another state also
present which is higher than the local maximum.

Solution: The backtracking technique can be a solution of the local maximum

in state space landscape. Create a list of the promising paths so that the
algorithm can backtrack the search space and explore other paths as well.
2. Plateau: A plateau is the flat area of the search space in which all the
neighbor states of the current state contains the same value, because of this
algorithm does not find any best direction to move. A hill-climbing search
might be lost in the plateau area.

Solution: The solution for the plateau is to take big steps or very little steps
while searching, to solve the problem. Randomly select a state which is far
away from the current state so it is possible that the algorithm could find
non-plateau region.
3. Ridges: A ridge is a special form of the local maximum. It has an area that
is higher than its surrounding areas, but itself has a slope, and cannot be
reached in a single move.

Solution: With the use of bidirectional search, or by moving in different

directions, we can improve this problem.
Process of Hill Climbing algorithm
• Define the current state as an initial state
• Loop until the goal state is achieved or no more operators can be
applied on the current state:–
o Apply an operation to current state and get a new state
o Compare the new state with the goal
o Quit if the goal state is achieved
o Evaluate new state with heuristic function and compare it with
the current state
o If the newer state is closer to the goal compared to the current
state, update the current state
Solution
 Genetic Algorithms(GAs)
• Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger
part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural
selection and genetics.
• These are intelligent exploitation of random searches provided with historical data to
direct the search into the region of better performance in solution space. They are
commonly used to generate high-quality solutions for optimization problems and search
problems.
• Genetic algorithms simulate the process of natural selection which means those species
that can adapt to changes in their environment can survive and reproduce and go to the
next generation.
• In simple words, they simulate “survival of the fittest” among individuals of consecutive
generations to solve a problem. Each generation consists of a population of
individuals and each individual represents a point in search space and possible solution.
Each individual is represented as a string of character/integer/float/bits. This string is
analogous to the Chromosome.
Foundation of Genetic Algorithms
• Genetic algorithms are based on an analogy with the genetic structure and behavior
of chromosomes of the population. Following is the foundation of GAs based on this
analogy -
1. Individuals in the population compete for resources and mate
2. Those individuals who are successful (fittest) then mate to create more offspring
than others
3. Genes from the “fittest” parent propagate throughout the generation, that is
sometimes parents create offspring which is better than either parent.
4. Thus each successive generation is more suited for their environment.
Fitness Score
• A Fitness Score is given to each individual which shows the ability of an
individual to “compete”. The individual having optimal fitness score (or near
optimal) are sought.
• The GAs maintains the population of n individuals (chromosome/solutions) along
with their fitness [Link] individuals having better fitness scores are given
more chance to reproduce than others.
• The individuals with better fitness scores are selected who mate and
produce better offspring by combining chromosomes of parents. The population
size is static so the room has to be created for new arrivals.
• So, some individuals die and get replaced by new arrivals eventually creating
new generation when all the mating opportunity of the old population is
exhausted. It is hoped that over successive generations better solutions will arrive
while least fit die.
Fitness Score
• Each new generation has on average more “better genes” than the
individual (solution) of previous generations. Thus each new
generations have better “partial solutions” than previous
generations.
• Once the offspring produced having no significant difference from
offspring produced by previous populations, the population is
converged. The algorithm is said to be converged to a set of
solutions for the problem.
 Search space
• The population of individuals are maintained within search space. Each
individual represents a solution in search space for given problem. Each
individual is coded as a finite length vector (analogous to chromosome) of
components. These variable components are analogous to Genes. Thus a
chromosome (individual) is composed of several genes (variable
components).
Operators of Genetic Algorithms
Crossover Operator:
• Crossover is a genetic operator used to combine the genetic information of two
parent solutions to produce one or more new offspring.
• It mimics biological reproduction where two parents exchange parts of their genetic
material.
• The goal of crossover is to mix good features of parents and create potentially better
solutions.
• This represents mating between individuals. Two individuals are selected using
selection operator and crossover sites are chosen randomly. Then the genes at these
crossover sites are exchanged thus creating a completely new individual (offspring).
For example -
Types of Crossover
1. Single-Point Crossover
• A crossover point is selected on the parent chromosomes, and the segments after that
point are swapped.

2. Two-Point Crossover
• Two points are selected, and the middle portion between the points is exchanged.

3. Multi-Point Crossover
• More than two points are chosen, and segments are alternated between parents.

4. Uniform Crossover
• Each gene is chosen randomly from either parent with equal probability.
Operators of Genetic Algorithms
Mutation Operator:
• Mutation is a genetic operator that introduces random changes in the offspring’s
genes.
• It mimics natural biological mutation and helps maintain diversity in the population.
• The purpose of mutation is to avoid premature convergence and ensure the
algorithm explores new areas of the search space.
• The key idea is to insert random genes in offspring to maintain the diversity in the
population to avoid premature convergence. (one bit flipped)
For example
Types of Mutation
1. Bit-Flip Mutation
• A random bit (0 or 1) is flipped.

2. Swap Mutation
• Two positions in the chromosome are swapped.
• Used in permutation-based problems.

3. Inversion Mutation

• A segment of the chromosome is selected and reversed.

Example:
[1 2 | 3 4 5 | 6] → [1 2 | 5 4 3 | 6]
Adversarial search algorithm
• Adversarial search is a search technique used in environments where multiple agents
(players) compete against each other, and each player's action affects the other’s
outcome.
• It is commonly used in game-playing AI, such as chess, tic-tac-toe, checkers, Go, and
other competitive games.

Adversarial search is used when the environment is:

• Multi-agent
• Competitive (agents have conflicting goals)
• Deterministic or non-deterministic
• Zero-sum (one player’s gain is another’s loss)
• The goal of adversarial search is to select the best action by assuming that the
opponent will also act optimally to defeat you.
 Minimax Algorithm
Minimax is a kind of backtracking algorithm that is used in decision making
and game theory to find the optimal move for a player assuming that your
opponent also plays optimally.
It is widely used in two player turn-based games such as Tic-Tac-Toe, Chess
etc.

In Minimax the two players are called maximizer and minimizer.
The maximizer tries to get the highest score possible while
the minimizer tries to do the opposite and get the lowest score possible.
102
 Minimax Algorithm
 In this algorithm two players play the game, one is called MAX and the other is
called MIN. Both the players fight it as the opponent player gets the minimum
benefit while they get the maximum benefit.
 Both game players are opponents of each other, where MAX will select the
maximized value and MIN will select the minimized value.
 The minimax algorithm performs a depth-first search algorithm to explore the
complete game tree.
 The minimax algorithm proceeds all the way down to the terminal node of the tree,
then backtrack the tree as the recursion.
103
Step 1:
• In the below tree diagram, let's take A as the initial state of the tree.
• Suppose the maximizer takes the first turn which has a worst-case initial
value as -∞, and
• the minimizer will take the next turn which has a worst-case initial value as
+ ∞.
104
Step 2:
Now, first, we find the utility value for the Maximizer, its initial value
is -∞.
• so we will compare each value in the terminal state with an initial
value of the Maximizer and determines the higher nodes values.
• It will find the maximum among all.
• For node D max(-1, -∞) => max(-1,4)= 4
• For Node E max(2, -∞) => max(2, 6)= 6
• For Node F max(-3, -∞) => max(-3,-5) = -3
• For node G max(0, -∞) = max(0, 7) = 7

105
Step 3:
• In the next step, it's a turn for the minimizer, so it will compare all nodes value
with +∞ and will find the 3rd layer node values.
• For node B= min(4,6) = 4
• For node C= min (-3, 7) = -3

106
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.

107
As Homework

108
 Introduction to Alpha Beta Pruning Algorithm
 The word ‘pruning’ means cutting down branches and leaves.
Alpha-beta pruning is nothing but the pruning of useless branches in decision
trees. This alpha-beta pruning algorithm was discovered independently by
researchers in the 1900s.
Alpha-beta pruning is an optimisation technique for the minimax algorithm
which is discussed in earlier lecture.
The need for pruning came from the fact that in some cases decision trees become
very complex. In that tree, some useless branches increase the complexity of the
model.
So, to avoid this, Alpha-Beta pruning comes to play so that the computer does not
have to look at the entire tree.
These unusual nodes make the algorithm slow. Hence by removing these nodes
algorithm becomes fast.
10
9
 Key points in Alpha-beta Pruning
o Alpha: Alpha is the best choice or the highest value that we have found at any
instance along the path of Maximizer. The initial value for alpha is – ∞.
o Beta: Beta is the best choice or the lowest value that we have found at any instance
along the path of Minimizer. The initial value for beta is + ∞.
o The condition for Alpha-beta Pruning is that α >= β.

o Each node has to keep track of its alpha and beta values. Alpha can be updated
only when it’s MAX’s turn and, similarly, beta can be updated only when it’s
MIN’s chance.

o MAX will update only alpha values and MIN player will update only beta
values.
o The node values will be passed to upper nodes instead of values of alpha and beta
during go into reverse of tree.
o Alpha and Beta values only be passed to child nodes. 117
 Working of Alpha-beta Pruning

Step 1:
We will first start with the initial move. We will initially define the alpha and
beta values as the worst case i.e. α = -∞ and β= +∞. We will prune the node
only when alpha becomes greater than or equal to beta.

11
1
Step 2:
Since the initial value of alpha is less than beta so we didn’t prune it. Now it’s turn for
MAX. So, at node D, value of alpha will be calculated. The value of alpha at node D will
be max (2, 3). So, value of alpha at node D will be 3

11
2
 Working of Alpha-beta Pruning
Step 3:
Now the next move will be on node B and its turn for MIN now. So, at node B, the
value of alpha beta will be min (3, ∞). So, at node B values will be alpha= – ∞ and beta
will be 3.

In the next step, algorithms traverse the next successor of Node B which is node E,
and the values of α= -∞, and β= 3 will also be passed. 11
3
Step 4:
Working of Alpha-beta
Pruning
Now it’s turn for MAX. So, at node E we will look for MAX. The current value of alpha
at E is – ∞ and it will be compared with 5. So, MAX (- ∞, 5) will be 5. So, at node E,
alpha = 5, Beta = 3.

Now as we can see that alpha is greater than beta which is satisfying the pruning
condition so we can prune the right successor of node E and the algorithm will not be
traversed and the value at node E will be 5.
11
4
 Working of Alpha-beta
Step 5:
Pruning
In the next step the algorithm again comes to node A from node B. At node A alpha
will be changed to maximum value as MAX (- ∞, 3).

So now the value of alpha and beta at node A will be (3, + ∞) respectively and will be
transferred to node C. These same values will be transferred to node F.

122
 Working of Alpha-beta Pruning
Step 6:
At node F the value of alpha will be compared to the left branch which is 0. So, MAX
(0, 3) will be 3 and then compared with the right child which is 1, and MAX (3,1) = 3
still α remains 3, but the node value of F will become 1.

11
6
 Working of Alpha-beta
Step 7:
Pruning
Now node F will return the node value 1 to C and will compare to beta value at C.
Now its turn for MIN. So, MIN (+ ∞, 1) will be 1.
Now at node C, α= 3, and β= 1 and alpha is greater than beta which again satisfies
the pruning condition. So, the next successor of node C i.e. G will be pruned and
the algorithm didn’t compute the entire subtree G.

Now, C will return the node value to A and the best value of A will be MAX (1, 3) will be 3.
11
7
 Exampl
Which nodes will be pruned if you apply alpha-beta pruning algorithm
e2
The condition used by alpha beta pruning to prune
the useless branches is: alpha >= beta
• Alpha is used and updated only by the Maximizer
• It represents the maximum value found so far. The initial value
is set to -∞
• The value of alpha is passed down to children node, but the
actual node values are passed up while backtracking
• Beta is used and updated only by the Minimizer It represents
the minimum value found
• The initial value is ∞
• The value of beta is passed down to the children node, but
actual node values are used to backtrack
 We move down, depth first, until we reach the left most leaf node. Here, we have to explore both the
leaf nodes to determine the maximum value for max's turn. The maximum value is found to be 4,
which is the value that alpha is set at.
 Now, the node's value, i.e., 4 is used to back track. When we reach node B, the value of
beta is updated to become 4 as well.
Now, moving towards the next branch, we reach the leaf node with value 6. The turn is
of max, therefore, it will choose the maximum value from its children node. When we
explore 6, we realize that the value of alpha will either be 6 or greater than 6.
We do not need to explore the other child node since the value of alpha is now greater
than beta. So 2 is pruned.
B's node value becomes 4 as it is the minimizer and min(4,6) = 4. This value is
passed up and the value of alpha is changed by the maximizer to become 4 as well.
Now moving towards the next leaf node, we follow the blue path to reach 2.

We need to explore both the branches to find the maximum value for the maximizer,
which is 2. This node value is passed up and the minimizer changes beta's value to
2. Now alpha is again greater than beta so the entire right branch is pruned.
 Example 3
Which nodes will be pruned if you apply alpha-beta pruning algorithm

As
Homework

Solution:
 Example 4
Which nodes will be pruned if you apply alpha-beta pruning algorithm

As
Homework

130
 Example 5
Which nodes will be pruned if you apply alpha-beta pruning algorithm

As
Homework