Searching & Game Playing

Difference between Informed and Uninformed

Search in AI
Informed Search algorithms have information on the goal state which helps in more
efficient searching. This information is obtained by a function that estimates how close a
state is to the goal state. Example: Greedy Search and Graph Search.
Uninformed Search algorithms have no additional information on the goal node other
than the one provided in the problem definition. The plans to reach the goal state from the
start state differ only by the order and length of actions. Examples: Depth First Search
and Breadth-First Search.

Parameters Informed Search Uninformed Search

Known as It is also known as Heuristic Search. It is also known as Blind Search.

Using It uses knowledge for the searching It doesn’t use knowledge for the
Knowledge process. searching process.

It finds solution slow as compared

Performance It finds a solution more quickly.
to an informed search.

Completion It may or may not be complete. It is always complete.

Cost Factor Cost is low. Cost is high.

It consumes less time because of quick It consumes moderate time because

Time
searching. of slow searching.

There is a direction given about the No suggestion is given regarding the

Direction
solution. solution in it.
 It is more lengthy while
Implementation It is less lengthy while implemented.
implemented.

It is more efficient as efficiency takes It is comparatively less efficient as

into account cost and performance. incurred cost is more and the speed
Efficiency
The incurred cost is less and speed of of finding the Breadth-Firstsolution
finding solutions is quick. is slow.

Computational Computational requirements are Comparatively higher computational

requirements lessened. requirements.

Size of search Having a wide scope in terms of Solving a massive search task is
problems handling large search problems. challenging.

Greedy Search
Depth First Search (DFS)
Examples of A* Search
Breadth First Search (BFS)
Algorithms AO* Search
Branch and Bound
Hill Climbing Algorithm

Difference between BFS and DFS

S.
Parameters BFS DFS
No.
BFS stands for Breadth First
1. Stands for DFS stands for Depth First Search.
Search.
BFS(Breadth First Search) uses
DFS(Depth First Search) uses Stack
2. Data Structure Queue data structure for finding
data structure.
the shortest path.
 DFS is also a traversal approach in
BFS is a traversal approach in
which the traverse begins at the root
which we first walk through all
3. Definition node and proceeds through the nodes
nodes on the same level before
as far as possible until we reach the
moving on to the next level.
node with no unvisited nearby nodes.

BFS can be used to find a single

source shortest path in an
In DFS, we might traverse through
unweighted graph because, in
4. Technique more edges to reach a destination
BFS, we reach a vertex with a
vertex from a source.
minimum number of edges from
a source vertex.
Conceptual BFS builds the tree level byDFS builds the tree sub-tree by
5.
Difference level. sub-tree.
It works on the concept of FIFO It works on the concept of LIFO (Last
6. Approach used
(First In First Out). In First Out).
BFS is more suitable for
DFS is more suitable when there are
7. Suitable for searching vertices closer to the
solutions away from source.
given source.

DFS is more suitable for game or

Suitable for BFS considers all neighbors first
puzzle problems. We make a decision,
Decision and therefore not suitable for
8. and the then explore all paths through
Treestheirwinnin decision-making trees used in
this decision. And if this decision
g games or puzzles.
leads to win situation, we stop.

The Time complexity of BFS is

The Time complexity of DFS is also
O(V + E) when Adjacency List
O(V + E) when Adjacency List is used
Time is used and O(V^2) when
9. and O(V^2) when Adjacency Matrix is
Complexity Adjacency Matrix is used, where
used, where V stands for vertices and
V stands for vertices and E
E stands for edges.
stands for edges.
Visiting of
Here, siblings are visited beforeHere, children are visited before the
10. Siblings/
the children. siblings.
Children
 Nodes that are traversed several The visited nodes are added to the
Removal of
11. times are deleted from thestack and then removed when there are
Traversed Nodes
queue. no more nodes to visit.

In BFS there is no concept of DFS algorithm is a recursive algorithm

12. Backtracking
backtracking. that uses the idea of backtracking

BFS is used in variousDFS is used in various applications

13. Applications applications such as bipartitesuch as acyclic graphs and topological
graphs, shortest paths, etc. order etc.

14. Memory BFS requires more memory. DFS requires less memory.
BFS is optimal for finding the DFS is not optimal for finding the
15. Optimality
shortest path. shortest path.
DFS has lesser space complexity
In BFS, the space complexity is
Space because at a time it needs to store only
16. more critical as compared to
complexity a single path from the root to the leaf
time complexity.
node.
BFS is slow as compared to
17. Speed DFS is fast as compared to BFS.
DFS.
When the target is close to the When the target is far from the source,
18. When to use?
source, BFS performs better. DFS is preferable.
Hill Climbing Algorithm(Informed Search ,Heuristic
Search)
Hill Climbing is a heuristic search used for mathematical optimization problems in the
field of Artificial Intelligence.
Given a large set of inputs and a good heuristic function, it tries to find a sufficiently
good solution to the problem. This solution may not be the global optimal maximum.
● In the above definition, mathematical optimization problems imply that
hill-climbing solves the problems where we need to maximize or minimize a given
real function by choosing values from the given inputs. Example-Travelling salesman
problem where we need to minimize the distance traveled by the salesman.
● ‘Heuristic search’ means that this search algorithm may not find the optimal solution
to the problem. However, it will give a good solution in a reasonable time.
● A heuristic function is a function that will rank all the possible alternatives at any
branching step in the search algorithm based on the available information. It helps
the algorithm to select the best route out of possible routes.
Features of Hill Climbing
1. Variant of generate and test algorithm: It is a variant of generating and test
algorithm. The generate and test algorithm is as follows :
1. Generate possible solutions.
2. Test to see if this is the expected solution.
3. If the solution has been found quit else go to step 1.
Hence we call Hill climbing a variant of generating and test algorithm as it takes the
feedback from the test procedure. Then this feedback is utilized by the generator in
deciding the next move in the search space.
2. Uses the Greedy approach: At any point in state space, the search moves in that
direction only which optimizes the cost of function with the hope of finding the optimal
solution at the end.
Types of Hill Climbing

A. Simple Hill climbing:

It examines the neighboring nodes one by one and selects the first neighboring node
which optimizes the current cost as the next node.
Algorithm for Simple Hill climbing :
Step 1 : Evaluate the initial state. If it is a goal state then stop and return success.
Otherwise, make initial state as current state.
Step 2 : Loop until the solution state is found or there are no new operators present which
can be applied to the current state.
a) Select a state that has not been yet applied to the current state and apply it to produce a
new state.
b) Perform these to evaluate new state
i. If the current state is a goal state, then stop and return success.
ii. If it is better than the current state, then make it current state and proceed further.
iii. If it is not better than the current state, then continue in the loop until a solution is
found.
Step 3 : Exit.

B. Steepest-Ascent Hill climbing:

It first examines all the neighboring nodes and then selects the node closest to the
solution state as of the next node.
Algorithm for Steepest Ascent Hill climbing :
Step 1 : Evaluate the initial state. If it is a goal state then stop and return success.
Otherwise, make initial state as current state.
Step 2 : Repeat these steps until a solution is found or current state does not change
a) Select a state that has not been yet applied to the current state.
b) Initialize a new ‘best state’ equal to current state and apply it to produce a new state.
c) Perform these to evaluate new state
i. If the current state is a goal state, then stop and return success.
ii. If it is better than best state, then make it best state else continue loop with another new
state.
d) Make best state as current state and go to Step 2: (b) part.
Step 3 : Exit

C. Stochastic hill climbing:

It does not examine all the neighboring nodes before deciding which node to select. It just
selects a neighboring node at random and decides (based on the amount of improvement
in that neighbor) whether to move to that neighbor or to examine another.
Step 1: Evaluate the initial state. If it is a goal state then stop and return success.
Otherwise, make the initial state the current state.
Step 2: Repeat these steps until a solution is found or the current state does not
change.
a) Select a state that has not been yet applied to the current state.
b) Apply successor function to the current state and generate all the neighbor states.
c) Among the generated neighbor states which are better than the current state choose
a state randomly (or based on some probability function).
d) If the chosen state is the goal state, then return success, else make it the current
state and repeat step 2: b) part.
Step 3: Exit.

State Space diagram for Hill Climbing

The state-space diagram is a graphical representation of the set of states our search
algorithm can reach vs the value of our objective function(the function which we wish to
maximize).
X-axis: denotes the state space ie states or configuration our algorithm may reach.
Y-axis: denotes the values of objective function corresponding to a particular state.
The best solution will be that state space where the objective function has a maximum
value(global maximum).
 Different regions in the State Space Diagram:
1. Local maximum: It is a state which is better than its neighboring state however
there exists a state which is better than it(global maximum). This state is better
because here the value of the objective function is higher than its neighbors.
2. Global maximum: It is the best possible state in the state space diagram. This is
because, at this stage, the objective function has the highest value.
3. Plateau/flat local maximum: It is a flat region of state space where neighboring
states have the same value.
4. Ridge: It is a region that is higher than its neighbors but itself has a slope. It is a
special kind of local maximum.
5. Current state: The region of state space diagram where we are currently present
during the search.
6. Shoulder: It is a plateau that has an uphill edge.
Problems in different regions in Hill climbing
Hill climbing cannot reach the optimal/best state(global maximum) if it enters any of the
following regions :
1. Local maximum: At a local maximum all neighboring states have a value that is
worse than the current state. Since hill-climbing uses a greedy approach, it will not
 move to the worse state and terminate itself. The process will end even though a
better solution may exist.
To overcome the local maximum problem: Utilize the backtracking technique.
Maintain a list of visited states. If the search reaches an undesirable state, it can
backtrack to the previous configuration and explore a new path.
2. Plateau: On the plateau, all neighbors have the same value. Hence, it is not possible
to select the best direction.
To overcome plateaus: Make a big jump. Randomly select a state far away from
the current state. Chances are that we will land in a non-plateau region.
3. Ridge: Any point on a ridge can look like a peak because movement in all possible
directions is downward. Hence the algorithm stops when it reaches this state.
To overcome Ridge: In this kind of obstacle, use two or more rules before testing. It
implies moving in several directions at once.

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 UCS(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 UCS 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.
Algorithm of A* search:
Step1: Place the starting node in the OPEN list.
Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and stops.
Step 3: Select the node from the OPEN list which has the smallest value of evaluation function
(g+h), if node n is goal node then return success and stop, otherwise
Step 4: Expand node n and generate all of its successors, and put n into the closed list. For each
successor n', check whether n' is already in the OPEN or CLOSED list, if not then compute
evaluation function for n' and place into Open list.
Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the back
pointer which reflects the lowest g(n') value.
Step 6: Return to Step 2.

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.

Example:
In this example, we will traverse the given graph using the A* algorithm. The heuristic value of
all states is given in the below table so we will calculate the f(n) of each state using the formula
f(n)= g(n) + h(n), where g(n) is the cost to reach any node from start state.
Here we will use OPEN and CLOSED list.

Solution:

Initialization: {(S, 5)}

Iteration1: {(S--> A, 4), (S-->G, 10)}

Iteration2: {(S--> A-->C, 4), (S--> A-->B, 7), (S-->G, 10)}

Iteration3: {(S--> A-->C--->G, 6), (S--> A-->C--->D, 11), (S--> A-->B, 7), (S-->G, 10)}

Iteration 4 will give the final result, as S--->A--->C--->G it provides the optimal path with cost
6.

Points to remember:
● A* algorithm returns the path which occurred first, and it does not search for all
remaining paths.
● The efficiency of A* algorithm depends on the quality of heuristic.
● A* algorithm expands all nodes which satisfy the condition f(n)

Complete: A* algorithm is complete as long as:

● Branching factor is finite.

● Cost at every action is fixed.

Optimal: A* search algorithm is optimal if it follows below two conditions:

● Admissible: the first condition requires for optimality is that h(n) should be an
admissible heuristic for A* tree search. An admissible heuristic is optimistic in nature.

● Consistency: Second required condition is consistency for only A* graph-search.

If the heuristic function is admissible, then A* tree search will always find the least cost path.
Time Complexity: The time complexity of A* search algorithm depends on heuristic function,
and the number of nodes expanded is exponential to the depth of solution d. So the time
complexity is O(b^d), where b is the branching factor.

Space Complexity: The space complexity of A* search algorithm is O(b^d)

AO* Algorithm(Problem Reduction Technique using

AND-OR graph)
AO* Algorithm basically based on problem decompositon (Breakdown problem into small
pieces)

When a problem can be divided into a set of sub problems, where each sub problem can be
solved separately and a combination of these will be a solution, AND-OR graphs or AND - OR
trees are used for representing the solution.

The decomposition of the problem or problem reduction generates AND arcs.

AND-OR Graph

The figure shows an AND-OR graph

1. To pass any exam, we have two options, either cheating or hard work.
2. In this graph we are given two choices, first do cheating or (The red line) work hard
and (The arc) pass.
3. When we have more than one choice and we have to pick one, we apply OR
condition to choose one.(That's what we did here).
4. Basically the ARC here denote AND condition.
5. Here we have replicated the arc between the work hard and the pass because by doing
the hard work possibility of passing an exam is more than cheating.

A* Vs AO*
 1. Both are part of informed search technique and use heuristic values to solve the
problem.
2. The solution is guaranteed in both algorithm.
3. A* always gives an optimal solution (shortest path with low cost) But It is not
guaranteed to that AO* always provide an optimal solutions.
4. Reason: Because AO* does not explore all the solution path once it got solution.

How AO* works

Let's try to understand it with the following diagram

The algorithm always moves towards a lower cost value.

Basically, We will calculate the cost function here (F(n)= G (n) + H (n))

H: heuristic/ estimated value of the nodes. and G: actual cost or edge value (here unit value).

Here we have taken the edges value 1 , meaning we have to focus solely on the heuristic value.

1. The Purple color values are edge values (here all are same that is one).
2. The Red color values are Heuristic values for nodes.
3. The Green color values are New Heuristic values for nodes.

Procedure:

1. In the above diagram we have two ways from A to D or A to B-C (because of and
condition). calculate cost to select a path
 2. F(A-D)= 1+10 = 11 and F(A-BC) = 1 + 1 + 6 +12 = 20
3. As we can see F(A-D) is less than F(A-BC) then the algorithm choose the path
F(A-D).
4. Form D we have one choice that is F-E.
5. F(A-D-FE) = 1+1+ 4 +4 =10
6. Basically 10 is the cost of reaching FE from D. And Heuristic value of node D also
denote the cost of reaching FE from D. So, the new Heuristic value of D is 10.
7. And the Cost from A-D remain same that is 11.

Suppose we have searched this path and we have got the Goal State, then we will never explore
the other path. (this is what AO* says but here we are going to explore other path as well to see
what happen)

Let's Explore the other path:

1. In the above diagram we have two ways from A to D or A to B-C (because of and
condition). calculate cost to select a path
2. F(A-D)= 1+10 = 11 and F(A-BC) = 1 + 1 + 6 +12 = 20
3. As we know the cost is more of F(A-BC) but let's take a look
4. Now from B we have two path G and H , let's calculate the cost
5. F(B-G)= 5+1 =6 and F(B-H)= 7 + 1 = 8
6. So, cost from F(B-H) is more than F(B-G) we will take the path B-G.
7. The Heuristic value from G to I is 1 but let's calculate the cost form G to I.
8. F(G-I) = 1 +1 = 2. which is less than Heuristic value 5. So, the new Heuristic value
form G to I is 2.
9. If it is a new value, then the cost from G to B must also have changed. Let's see the
new cost form (B to G)
10. F(B-G)= 1+2 =3 . Mean the New Heuristic value of B is 3.
11. But A is associated with both B and C .
12. As we can see from the diagram C only have one choice or one node to explore that
is J. The Heuristic value of C is 12.
13. Cost form C to J= F(C-J) = 1+1= 2 Which is less than Heuristic value
14. Now the New Heuristic value of C is 2.
15. And the New Cost from A- BC that is F(A-BC) = 1+1+2+3 = 7 which is less than
F(A-D)=11.
16. In this case Choosing path A-BC is more cost effective and good than that of A-D.

But this will only happen when the algorithm explores this path as well. But according to the
algorithm, algorithm will not accelerate this path (here we have just did it to see how the
other path can also be correct).
But it is not the case in all the cases that it will happen in some cases that the algorithm will get
optimal solution.

Adversial Search in Artificial Intelligence

AI Adversarial search: Adversarial search is a game-playing technique where the agents are
surrounded by a competitive environment.
A conflicting goal is given to the agents (multiagent). These agents compete with one another
and try to defeat one another in order to win the game. Such conflicting goals give rise to the
adversarial search.
Here, game-playing means discussing those games where human intelligence and logic factor is
used, excluding other factors such as luck factor. Tic-tac-toe, chess, checkers, etc., are such type
of games where no luck factor works, only mind works.

Mathematically, this search is based on the concept of ‘Game Theory.’ According to game
theory, a game is played between two players. To complete the game, one has to win the game
and the other looses automatically.’
Techniques required to get the best optimal solution
There is always a need to choose those algorithms which provide the best optimal
solution in a limited time. So, we use the following techniques which could fulfill our
requirements:

● Pruning: A technique which allows ignoring the unwanted portions of a search

tree which make no difference in its final result.
● Heuristic Evaluation Function: It allows to approximate the cost value at each
level of the search tree, before reaching the goal node.

Elements of Game Playing search

To play a game, we use a game tree to know all the possible choices and to pick the best
one out. There are following elements of a game-playing:

● S0: It is the initial state from where a game begins.

● PLAYER (s): It defines which player is having the current turn to make a move in
the state.
● ACTIONS (s): It defines the set of legal moves to be used in a state.
● RESULT (s, a): It is a transition model which defines the result of a move.
● TERMINAL-TEST (s): It defines that the game has ended and returns true.
 ● UTILITY (s,p): It defines the final value with which the game has ended. This
function is also known as Objective function or Payoff function. The price
which the winner will get i.e.
● (-1): If the PLAYER loses.
● (+1): If the PLAYER wins.
● (0): If there is a draw between the PLAYERS.

For example, in chess, tic-tac-toe, we have two or three possible outcomes. Either to win,
to lose, or to draw the match with values +1,-1 or 0.
Let’s understand the working of the elements with the help of a game tree designed for
tic-tac-toe. Here, the node represents the game state and edges represent the moves taken
by the players.

A game-tree for tic-tac-toe

● INITIAL STATE (S0): The top node in the game-tree represents the initial state
in the tree and shows all the possible choice to pick out one.
 ● 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.
● ACTIONS (s): Both the players can make moves in the empty boxes chance by
chance.
● RESULT (s, a): The moves made by MIN and MAX will decide the outcome of
the game.
● TERMINAL-TEST(s): When all the empty boxes will be filled, it will be the
terminating state of the game.
● UTILITY: At the end, we will get to know who wins: MAX or MIN, and
accordingly, the price will be given to them.

Types of algorithms in Adversarial search

In a normal search, we follow a sequence of actions to reach the goal or to finish the
game optimally. But in an adversarial search, the result depends on the players which will
decide the result of the game. It is also obvious that the solution for the goal state will be
an optimal solution because the player will try to win the game with the shortest path and
under limited time.
There are following types of adversarial search:

● Minmax Algorithm
● Alpha-beta Pruning.

Mini-Max(MINMAX) Algorithm in Artificial

Intelligence
● 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.

● Mini-Max algorithm uses recursion to search through the game-tree.

● Min-Max algorithm is mostly used for game playing in AI. Such as Chess, Checkers,
tic-tac-toe, go, and various tow-players game. This Algorithm computes the minimax
decision for the current state.
● In this algorithm two players play the game, one is called MAX and other is called MIN.
 ● Both the players fight it as the opponent player gets the minimum benefit while they get
the maximum benefit.
● Both Players of the game are opponent 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 for the exploration of 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.

Working of Min-Max Algorithm:

● 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.
● 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.
● This algorithm applies DFS, so in this game-tree, we have to go all the way through the
leaves to reach the terminal nodes.
● At the terminal node, the terminal values are given so we will compare those value 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 first step, the algorithm generates the entire game-tree and apply the utility
function to get the utility values for the terminal states. In the below 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, its initial value is -∞, so we will
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.

● 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

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.

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

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

● For node A max(4, -3)= 4

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

Properties of Mini-Max algorithm:

● Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in
the finite search tree.

● Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.

● 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.
 ● 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 which we have discussed in the next topic.

Alpha-Beta Pruning
● Alpha-beta pruning is a modified version of the minimax algorithm. It is an optimization
technique for the minimax algorithm.

● As we have seen in the minimax search algorithm that the number of game states it has to
examine are exponential in depth of the tree. Since we cannot eliminate the exponent, but
we can cut it to half. Hence there is a technique by which without checking each node of
the game tree we can compute the correct minimax decision, and this technique is called
pruning. This involves two threshold parameter Alpha and beta for future expansion, so
it is called alpha-beta pruning. It is also called as Alpha-Beta Algorithm.

● Alpha-beta pruning can be applied at any depth of a tree, and sometimes it not only prune
the tree leaves but also entire sub-tree.

● The two-parameter can be defined as:

a. Alpha: The best (highest-value) choice we have found so far at any point along
the path of Maximizer. The initial value of alpha is -∞.

b. Beta: The best (lowest-value) choice we have found so far at any point along the
path of Minimizer. The initial value of beta is +∞.

● The Alpha-beta pruning to a standard minimax algorithm returns the same move as the
standard algorithm does, but it removes all the nodes which are not really affecting the
final decision but making algorithm slow. Hence by pruning these nodes, it makes the
algorithm fast.
The main condition which required for alpha-beta pruning is:

1. α>=β

Working of Alpha-Beta Pruning:

Let's take an example of two-player search tree to understand the working of Alpha-beta pruning

Step 1: At the first step the, Max player will start first move from node A where α= -∞ and β=
+∞, these value of alpha and beta passed down to node B where again α= -∞ and β= +∞, and
Node 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 algorithm backtrack to node B, where the value of β will change as this is a turn of
Min, 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.
Step 5: At next step, algorithm again backtrack the tree, from node B to node A. At node A, the
value of alpha will be changed the maximum available value is 3 as max (-∞, 3)= 3, and β= +∞,
these two values now passes to right successor of A which is Node C.

At node C, α=3 and β= +∞, and the same values will be passed on to node F.

Step 6: At node F, again the value of α will be compared with left child which is 0, and
max(3,0)= 3, and then compared with right child which is 1, and max(3,1)= 3 still α remains 3,
but the node value of F will become 1.

Step 7: Node F returns the node value 1 to node C, at C α= 3 and β= +∞, here the value of beta
will be changed, it will compare with 1 so min (∞, 1) = 1. Now at C, α=3 and β= 1, and again it
satisfies the condition α>=β, so the next child of C which is G will be pruned, and the algorithm
will not compute the entire sub-tree G.
Step 8: C now returns the value of 1 to A here the best value for A is max (3, 1) = 3. Following
is the final game tree which is the showing the nodes which are computed and nodes which has
never been computed. Hence the optimal value for the maximizer is 3 for this example.
Move Ordering in Alpha-Beta pruning:
The effectiveness of alpha-beta pruning is highly dependent on the order in which each node is
examined. Move order is an important aspect of alpha-beta pruning.

It can be of two types:

● Worst ordering: In some cases, alpha-beta pruning algorithm does not prune any of the
leaves of the tree, and works exactly as minimax algorithm. In this case, it also consumes
more time because of alpha-beta factors, such a move of pruning is called worst ordering.
In this case, the best move occurs on the right side of the tree. The time complexity for
such an order is O(bm).
● Ideal ordering: The ideal ordering for alpha-beta pruning occurs when lots of pruning
happens in the tree, and best moves occur at the left side of the tree. We apply DFS hence
it first search left of the tree and go deep twice as minimax algorithm in the same amount
of time. Complexity in ideal ordering is O(bm/2).