UNIT - II Searching

Searching for solutions, uniformed search strategies – Breadth first search, depth first Search.
Search with partial information (Heuristic search) Hill climbing, A* ,AO* Algorithms, Problem
reduction, Game Playing - Adversial search, Games, mini-max algorithm, optimal decisions in
multiplayer games, Problem in Game playing, Alpha-Beta pruning, Evaluation functions.

Search: Searching is a step by step procedure to solve a search-problem in a given search space.
A search problem can have three main factors:
a. Search Space: Search space represents a set of possible solutions, which a system
may have.
b. Start State: It is a state from where agent begins the search.
c. Goal test: It is a function which observe the current state and returns whether the
goal state is achieved or not.
Search tree: A tree representation of search problem is called Search tree. The root of the search
tree is the root node which is corresponding to the initial state.
Actions: It gives the description of all the available actions to the agent.
Transition model: A description of what each action do, can be represented as a transition
model.
Path Cost: It is a function which assigns a numeric cost to each path.
Solution: It is an action sequence which leads from the start node to the goal node.
Optimal Solution: If a solution has the lowest cost among all solutions.

Properties of Search Algorithms:

Following are the four essential properties of search algorithms to compare the efficiency of
these algorithms:
Completeness: A search algorithm is said to be complete if it guarantees to return a solution if at
least any solution exists for any random input.
Optimality: If a solution found for an algorithm is guaranteed to be the best solution (lowest
path cost) among all other solutions, then such a solution for is said to be an optimal solution.
Time Complexity: Time complexity is a measure of time for an algorithm to complete its task.
Space Complexity: It is the maximum storage space required at any point during the search, as
the complexity of the problem.

(i) Infrastructure for search algorithms:

▪ Search algorithms require a data structure to keep track of the search tree that is being
constructed.
▪ For each node n of the tree, we have a structure that contains four components:
• [Link]: the state in the state space to which the node corresponds;
• [Link]: the node in the search tree that generated this node;
• [Link]: the action that was applied to the parent to generate the node;
• [Link]-COST: the cost, traditionally denoted by g(n), of the path from the initial state to the
node, as indicated by the parent pointers.
➢ Queue :
▪ Now that we have nodes, we need somewhere to put them.
▪ The frontier needs to be stored in such a way that the search algorithm can easily choose the
next node to expand according to its preferred strategy.
▪ The appropriate data structure for this is a queue.
▪ The operations on a queue are as follows:
• EMPTY?(queue) returns true only if there are no more elements in the queue.
• POP(queue) removes the first element of the queue and returns it.
• INSERT(element, queue) inserts an element and returns the resulting queue.
▪ Queues are characterized by the order in which they store the inserted nodes.

▪ Three common variants are

▪ The first-in, first-out or FIFO queue, which pops the oldest element of the queue;
▪ LIFO QUEUE the last-in, first-out or LIFO queue (also known as a stack), which pops the
newest element
▪ PRIORITY QUEUE of the queue; and the priority queue, which pops the element of the queue
with the highest priority according to some ordering function.
(ii)Measuring problem-solving performance:
▪ Before we get into the design of specific search algorithms, we need to consider the criteria that
might be used to choose among them.

▪ We can evaluate an algorithm’s performance in four ways:

→ Completeness: Is the algorithm guaranteed to find a solution when there is one?
→ Optimality: Does the strategy find the optimal solution,
→ Time complexity: How long does it take to find a solution?
→ Space complexity: How much memory is needed to perform the search?

Types of search algorithms

 1. Breadth-first Search:
o Breadth-first search is the most common search strategy for traversing a tree or graph.
This algorithm searches breadthwise in a tree or graph, so it is called breadth-first search.
o BFS algorithm starts searching from the root node of the tree and expands all successor
node at the current level before moving to nodes of next level.
o The breadth-first search algorithm is an example of a general-graph search algorithm.
o Breadth-first search implemented using FIFO queue data structure.

Advantages:
o BFS will provide a solution if any solution exists.
o If there are more than one solutions for a given problem, then BFS will provide the
minimal solution which requires the least number of steps.
o It also helps in finding the shortest path in goal state, since it needs all nodes at the same
hierarchical level before making a move to nodes at lower levels.
o It is also very easy to comprehend with the help of this we can assign the higher rank
among path types.

Disadvantages:
o It requires lots of memory since each level of the tree must be saved into memory to
expand the next level.
o BFS needs lots of time if the solution is far away from the root node.
o It can be very inefficient approach for searching through deeply layered spaces, as it
needs to thoroughly explore all nodes at each level before moving on to the next

Example:
In the below tree structure, we have shown the traversing of the tree using BFS algorithm from
the root node S to goal node K. BFS search algorithm traverse in layers, so it will follow the path
which is shown by the dotted arrow, and the traversed path will be:
1. S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
Time Complexity: Time Complexity of BFS algorithm can be obtained by the number of nodes
traversed in BFS until the shallowest Node. Where the d= depth of shallowest solution and b is a
node at every state.
T (b) = 1+b2+b3+.......+ bd= O (bd)
Space Complexity: Space complexity of BFS algorithm is given by the Memory size of frontier
which is O(bd).
Completeness: BFS is complete, which means if the shallowest goal node is at some finite
depth, then BFS will find a solution.
Optimality: BFS is optimal if path cost is a non-decreasing function of the depth of the node.

2. Depth-first Search
o Depth-first search isa recursive algorithm for traversing a tree or graph data structure.
o It is called the depth-first search because it starts from the root node and follows each
path to its greatest depth node before moving to the next path.
o DFS uses a stack data structure for its implementation.
o The process of the DFS algorithm is similar to the BFS algorithm.
Advantage:
o DFS requires very less memory as it only needs to store a stack of the nodes on the path
from root node to the current node.
o It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right
path).
o With the help of this we can stores the route which is being tracked in memory to save
time as it only needs to keep one at a particular time.
Disadvantage:
o There is the possibility that many states keep re-occurring, and there is no guarantee of
finding the solution.
o DFS algorithm goes for deep down searching and sometime it may go to the infinite loop.
 o The depth-first search (DFS) algorithm does not always find the shorte¬st path to a
solution.
Example:
In the below search tree, we have shown the flow of depth-first search, and it will follow the
order as:
Root node--->Left node ----> right node.
It will start searching from root node S, and traverse A, then B, then D and E, after traversing E,
it will backtrack the tree as E has no other successor and still goal node is not found. After
backtracking it will traverse node C and then G, and here it will terminate as it found goal node.

Completeness: DFS search algorithm is complete within finite state space as it will expand
every node within a limited search tree.
Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the
algorithm. It is given by:
T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
Where, m= maximum depth of any node and this can be much larger than d (Shallowest
solution depth)
Space Complexity: DFS algorithm needs to store only single path from the root node, hence
space complexity of DFS is equivalent to the size of the fringe set, which is O(bm).
Optimal: DFS search algorithm is non-optimal, as it may generate a large number of steps or
high cost to reach to the goal node.

Heuristic Search Techniques in AI

These techniques are essential for tasks that involve finding the best path from a starting point
to a goal state, such as in navigation systems, game playing, and optimization problems. This
article delves into what heuristic search is, its significance, and the various techniques
employed in AI.
Understanding Heuristic Search
Heuristics operates on the search space of a problem to find the best or closest-to-optimal
solution via the use of systematic algorithms. In contrast to a brute-force approach, which
checks all possible solutions exhaustively, a heuristic search method uses heuristic information
to define a route that seems more plausible than the rest. Heuristics, in this case, refer to a set
of criteria or rules of thumb that offer an estimate of a firm’s profitability. Utilizing heuristic
guiding, the algorithms determine the balance between exploration and exploitation, and thus
they can successfully tackle demanding issues. Therefore, they enable an efficient solution
finding process.

Components of Heuristic Search

Heuristic search algorithms typically comprise several essential components:

1. State Space: This implies that the totality of all possible states or settings, which is
considered to be the solution for the given problem.
2. Initial State: The instance in the search tree of the highest level with no null values, serving
as the initial state of the problem at hand.
3. Goal Test: The exploration phase ensures whether the present state is a terminal or
consenting state in which the problem is solved.
4. Successor Function: This create a situation where individual states supplant the current state
which represent the possible moves or solutions in the problem space.
5. Heuristic Function: The function of a heuristic is to estimate the value or distance from a
given state to the target state. It helps to focus the process on regions or states that has
prospect of achieving the goal.

Hill Climbing
Hill Climbing can be useful in a variety of optimization problems, such as scheduling, route
planning, and resource allocation. However, it has some limitations, such as the tendency to
get stuck in local maxima and the lack of diversity in the search space. Therefore, it is often
combined with other optimization techniques, such as genetic algorithms or simulated
annealing, to overcome these limitations and improve the search results.

Advantages of Hill Climbing algorithm:

1. Hill Climbing is a simple and intuitive algorithm that is easy to understand and implement.
2. It can be used in a wide variety of optimization problems, including those with a large
search space and complex constraints.
3. Hill Climbing is often very efficient in finding local optima, making it a good choice for
problems where a good solution is needed quickly.
4. The algorithm can be easily modified and extended to include additional heuristics or
constraints.

Disadvantages of Hill Climbing algorithm:

1. Hill Climbing can get stuck in local optima, meaning that it may not find the global
optimum of the problem.
2. The algorithm is sensitive to the choice of initial solution, and a poor initial solution may
result in a poor final solution.
3. Hill Climbing does not explore the search space very thoroughly, which can limit its ability
to find better solutions.
4. It may be less effective than other optimization algorithms, such as genetic algorithms or
simulated annealing, for certain types of problems.
 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.

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 a state space where the objective function has a maximum
value(global maximum).

Different regions in the State Space Diagram:

 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.
 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.
 Plateau/flat local maximum: It is a flat region of state space where neighboring states
have the same value.
 Ridge: It is a region that is higher than its neighbors but itself has a slope. It is a special
kind of local maximum.
 Current state: The region of the state space diagram where we are currently present during
the search.
 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 :
 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.
 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.
 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.

Types of Hill Climbing

1. 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.
2. 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.
3. 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.
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 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:
o A* search algorithm is the best algorithm than other search algorithms.
o A* search algorithm is optimal and complete.
o This algorithm can solve very complex problems.

Disadvantages:
o It does not always produce the shortest path as it mostly based on heuristics and
approximation.
o A* search algorithm has some complexity issues.
o 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:
o A* algorithm returns the path which occurred first, and it does not search for all
remaining paths.
o The efficiency of A* algorithm depends on the quality of heuristic.
o A* algorithm expands all nodes which satisfy the condition f(n)<="" li="">
Complete: A* algorithm is complete as long as:
o Branching factor is finite.
o Cost at every action is fixed.
Optimal: A* search algorithm is optimal if it follows below two conditions:
o 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.
o 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* Algorithms
The AO* method divides any given difficult problem into a smaller group of problems that
are then resolved using the AND-OR graph concept. AND OR graphs are specialized graphs
that are used in problems that can be divided into smaller problems. The AND side of the
graph represents a set of tasks that must be completed to achieve the main goal, while the OR
side of the graph represents different methods for accomplishing the same main goal.

In the above figure, the buying of a car may be broken down into smaller problems or tasks
that can be accomplished to achieve the main goal in the above figure, which is an example of
a simple AND-OR graph. The other task is to either steal a car that will help us accomplish the
main goal or use your own money to purchase a car that will accomplish the main goal. The
AND symbol is used to indicate the AND part of the graphs, which refers to the need that all
subproblems containing the AND to be resolved before the preceding node or issue may be
finished.
The start state and the target state are already known in the knowledge-based search strategy
known as the AO* algorithm, and the best path is identified by heuristics. The informed
search technique considerably reduces the algorithm’s time complexity. The AO* algorithm is
far more effective in searching AND-OR trees than the A* algorithm.

Working of AO* algorithm:

The evaluation function in AO* looks like this:
f(n) = g(n) + h(n)
f(n) = Actual cost + Estimated cost
here,
f(n) = The actual cost of traversal.
g(n) = the cost from the initial node to the current node.
h(n) = estimated cost from the current node to the goal state.

Difference between the A* Algorithm and AO* algorithm

 A* algorithm and AO* algorithm both works on the best first search.
 They are both informed search and works on given heuristics values.
 A* always gives the optimal solution but AO* doesn’t guarantee to give the optimal
solution.
 Once AO* got a solution doesn’t explore all possible paths but A* explores all paths.
 When compared to the A* algorithm, the AO* algorithm uses less memory.
 opposite to the A* algorithm, the AO* algorithm cannot go into an endless loop.
Example:

Here in the above example below the Node which is given is the heuristic value i.e h(n). Edge
length is considered as 1.

Step 1

With help of f(n) = g(n) + h(n) evaluation function,

Start from node A,

f(A⇢B) = g(B) + h(B)
=1 + 5 ……here g(n)=1 is taken by default for path cost
=6

f(A⇢C+D) = g(c) + h(c) + g(d) + h(d)

=1+2+1+4 ……here we have added C & D because they are in AND
=8
So, by calculation A⇢B path is chosen which is the minimum path, i.e f(A⇢B)

Step 2
According to the answer of step 1, explore node B
Here the value of E & F are calculated as follows,

f(B⇢E) = g(e) + h(e)

f(B⇢E) = 1 + 7
=8

f(B⇢f) = g(f) + h(f)

f(B⇢f) = 1 + 9
= 10
So, by above calculation B⇢E path is chosen which is minimum path, i.e f(B⇢E)
because B's heuristic value is different from its actual value The heuristic is
updated and the minimum cost path is selected. The minimum value in our situation is 8.
Therefore, the heuristic for A must be updated due to the change in B's heuristic.
So we need to calculate it again.

f(A⇢B) = g(B) + updated h(B)

=1+8
=9
We have Updated all values in the above tree.

Step 3

By comparing f(A⇢B) & f(A⇢C+D)

f(A⇢C+D) is shown to be smaller. i.e 8 < 9
Now explore f(A⇢C+D)
So, the current node is C

f(C⇢G) = g(g) + h(g)

f(C⇢G) = 1 + 3
=4

f(C⇢H+I) = g(h) + h(h) + g(i) + h(i)

f(C⇢H+I) = 1 + 0 + 1 + 0 ……here we have added H & I because they are in AND
=2

f(C⇢H+I) is selected as the path with the lowest cost and the heuristic is also left unchanged
because it matches the actual cost. Paths H & I are solved because the heuristic for those paths
is 0,
but Path A⇢D needs to be calculated because it has an AND.

f(D⇢J) = g(j) + h(j)

f(D⇢J) = 1 + 0
=1
the heuristic of node D needs to be updated to 1.

f(A⇢C+D) = g(c) + h(c) + g(d) + h(d)

=1+2+1+1
=5

as we can see that path f(A⇢C+D) is get solved and this tree has become a solved tree now.
In simple words, the main flow of this algorithm is that we have to find firstly level 1st
heuristic
value and then level 2nd and after that update the values with going upward means towards
the root node.
In the above tree diagram, we have updated all the values.

PROBLEM REDUCTION
Problem reduction is a key method in artificial intelligence (AI) that helps solve complex issues.
It works by breaking down big problems into smaller, more manageable parts. This approach
makes it easier for AI systems to find solutions.

Why Use Problem Reduction?

1. Simplifies complex tasks: By splitting a big problem into smaller pieces, AI can tackle each
part separately.
2. Saves time and resources: Solving smaller problems often requires less computing power and
time.
3. Improves accuracy: Working on simpler tasks can lead to more precise results.
4. Helps in decision-making: Breaking down problems helps AI make better choices step by
step.

Common Problem Reduction Techniques

1. Divide and Conquer This method splits a problem into two or more sub-problems. The AI
solves each sub-problem and then combines the results to solve the original problem.
Example: Sorting a large list of numbers can be done by dividing the list, sorting smaller parts,
and then merging them.
2. Means-Ends Analysis This technique looks at the difference between the current state and the
goal state. It then tries to reduce this difference step by step.
Example: In a puzzle game, AI can compare the current board setup with the desired end result
and make moves to get closer to the goal.
3. Problem Abstraction This approach removes unnecessary details from a problem, focusing
only on the most important parts.
Example: When planning a route, AI might ignore small side streets and focus only on main roads
to find the best path quickly.
4. Subgoal Decomposition This method breaks down a main goal into smaller, easier-to-achieve
subgoals.
Example: To clean a room, AI might set subgoals like “pick up toys,” “dust surfaces,” and
“vacuum floor.”

Benefits of Problem Reduction in AI

1. Faster problem-solving
2. Better handling of complex issues
3. More efficient use of resources
4. Improved AI learning and adaptation

Example Towers Of Hanoi

Follow the steps below to solve the problem:

 Create a function towerOfHanoi where pass the N (current number of
disk), from_rod, to_rod, aux_rod.
 Make a function call for N – 1 th disk.
 Then print the current the disk along with from_rod and to_rod
 Again make a function call for N – 1 th disk.

Game Playing-Adversial search

Adversarial search is a search, where we examine the problem which arises when we try to plan
ahead of the world and other agents are planning against us.
Types of Games in AI:
o 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.
o Imperfect information: If in a 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, such as tic-tac-toe, Battleship, blind, Bridge, etc.
o 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.
o Non-deterministic games: Non-deterministic are those games which have various
unpredictable events and has 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.
Zero-Sum Game
o Zero-sum games are adversarial search which involves pure competition.
o In Zero-sum game each agent's gain or loss of utility is exactly balanced by the losses or
gains of utility of another agent.
o One player of the game try to maximize one single value, while other player tries to
minimize it.
o Each move by one player in the game is called as ply.
o Chess and tic-tac-toe are examples of a Zero-sum game.
Zero-sum game: Embedded thinking
The Zero-sum game involved embedded thinking in which one agent or player is trying to figure
out:
o What to do.
o How to decide the move
o Needs to think about his opponent as well
o The opponent also thinks what to do
Each of the players is trying to find out the response of his opponent to their actions. This
requires embedded thinking or backward reasoning to solve the game problems in AI.
Formalization of the problem:
A game can be defined as a type of search in AI which can be formalized of the following
elements:
o Initial state: It specifies how the game is set up at the start.
o Player(s): It specifies which player has moved in the state space.
o Action(s): It returns the set of legal moves in state space.
o Result(s, a): It is the transition model, which specifies the result of moves in the state
space.
 o 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.
o 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.
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:
o There are two players MAX and MIN.
o Players have an alternate turn and start with MAX.
o MAX maximizes the result of the game tree
o MIN minimizes the result.

Example Explanation:
o From the initial state, MAX has 9 possible moves as he starts first. MAX place x and
MIN place o, and both player plays alternatively until we reach a leaf node where one
player has three in a row or all squares are filled.
o Both players will compute each node, minimax, the minimax value which is the best
achievable utility against an optimal adversary.
o Suppose both the players are well aware of the tic-tac-toe and playing the best play. Each
player is doing his best to prevent another one from winning. MIN is acting against Max
in the game.
 o So in the game tree, we have a layer of Max, a layer of MIN, and each layer is called
as Ply. Max place x, then MIN puts o to prevent Max from winning, and this game
continues until the terminal node.
o In this either MIN wins, MAX wins, or it's a draw. This game-tree is the whole search
space of possibilities that MIN and MAX are playing tic-tac-toe and taking turns
alternately.

Hence adversarial Search for the minimax procedure works as follows:

o It aims to find the optimal strategy for MAX to win the game.
o It follows the approach of Depth-first search.
o In the game tree, optimal leaf node could appear at any depth of the tree.
o Propagate the minimax values up to the tree until the terminal node discovered.
In a given game tree, the optimal strategy can be determined from the minimax value of each
node, which can be written as MINIMAX(n). MAX prefer to move to a state of maximum value
and MIN prefer to move to a state of minimum value then:

Mini-Max 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 Mini-Max algorithm uses recursion to search through the game-tree.
o 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.
o In this algorithm two players play the game, one is called MAX and other is called MIN.
o Both the players fight it as the opponent player gets the minimum benefit while they get
the maximum benefit.
o Both Players of the game are opponent of each other, where MAX will select the
maximized value and MIN will select the minimized value.
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.

Initial call:
Minimax(node, 3, true)
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.
o 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 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.
o For node D max(-1,- -∞) => max(-1,4)= 4
o For Node E max(2, -∞) => max(2, 6)= 6
o For Node F max(-3, -∞) => max(-3,-5) = -3
o 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.
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:

o 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.
Optimal Decision Making in Multiplayer Games
The optimal solution becomes a contingent strategy when specifies MAX(the player on our
side)’s move in the initial state, then Max move to the states resulting for every possible
response by MIN. Then MAX’s moves in the states resulting from every possible response by
MIN to those moves, and so on.

From the current state, the minimax method in the Figure above computes the minimax
choice. It implements the defining equations directly using a simple recursive computation of
the minimax values of each successor state. As the recursion unwinds, it progresses all the way
down to the tree’s leaves, where the minimax values are then backed up through the tree. In the
figure below, for example, the algorithm recurses down to the three bottom-left nodes and uses
the UTILITY function to determine that their values are 3, 12, and 8, respectively. Then it
takes the smallest of these values, 3 in this case, and returns it as node B’s backed-up value.
The backed-up values of 2 for C and 2 for D are obtained using a similar approach. Finally, we
add the maximum of 3, 2, and 2 to get the root node’s backed-up value of 3.

The minimax algorithm explores the game tree from top to bottom in depth-first. The temporal
complexity of the minimax method is O if the maximum depth of the tree is m and there are b
legal moves at each point (bm). For an algorithm that creates all actions at once, the space
complexity is O(bm), while for an algorithm that generates actions one at a time, the space
complexity is O(m) The time cost is obviously impractical for real games, but this technique
serves as a foundation for game mathematics analysis and more practical algorithms.

Disadvantages of Game Playing in Artificial Intelligence:

1. Limited scope: The techniques and algorithms developed for game playing may not be
well-suited for other types of applications and may need to be adapted or modified for
different domains.
2. Computational cost: Game playing can be computationally expensive, especially for
complex games such as chess or Go, and may require powerful computers to achieve real-
time performance.
Alpha-Beta Pruning
o Alpha-beta pruning is a modified version of the minimax algorithm. It is an optimization
technique for the minimax algorithm.
o 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.
o 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.
o 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.

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 computed. Hence the optimal value for the maximizer is 3 for this example.
Evaluation functions.
Each leaf node had a value associated with it. We had stored this value in an array. But in the
real world when we are creating a program to play Tic-Tac-Toe, Chess, Backgammon, etc. we
need to implement a function that calculates the value of the board depending on the placement
of pieces on the board. This function is often known as Evaluation Function. It is sometimes
also called a Heuristic Function.

The evaluation function is unique for every type of game. In this post, the evaluation function
for the game Tic-Tac-Toe is discussed. The basic idea behind the evaluation function is to give
a high value for a board if the maximizer turn or a low value for the board if
the minimizer turn.

For this scenario let us consider X as the maximizer and O as the minimizer.
Let us build our evaluation function :
 If X wins on the board we give it a positive value of +10.

 If O wins on the board we give it a negative value of -10.

 If no one has won or the game results in a draw then we give a value of +0.

We could have chosen any positive/negative. For the sake of simplicity, we chose 10 and shall
use lowercase ‘x’ and lowercase ‘o’ to represent the players and an underscore ‘_’ to represent
a blank space on the board.
If we represent our board as a 3×3 2D character matrix, like char board[3][3]; then we have to
check each row, each column, and the diagonals to check if either of the players has gotten 3 in
a row.
# Python3 program to compute evaluation
# function for Tic Tac Toe Game.

# Returns a value based on who is winning

# b[3][3] is the Tic-Tac-Toe board
def evaluate(b):

# Checking for Rows for X or O victory.

for row in range(0, 3):

if b[row][0] == b[row][1] and b[row][1] == b[row][2]:

if b[row][0] == 'x':
return 10
else if b[row][0] == 'o':
return -10

# Checking for Columns for X or O victory.

for col in range(0, 3):

if b[0][col] == b[1][col] and b[1][col] == b[2][col]:

if b[0][col]=='x':
return 10
else if b[0][col] == 'o':
return -10

# Checking for Diagonals for X or O victory.

if b[0][0] == b[1][1] and b[1][1] == b[2][2]:

if b[0][0] == 'x':
return 10
else if b[0][0] == 'o':
return -10

if b[0][2] == b[1][1] and b[1][1] == b[2][0]:

if b[0][2] == 'x':
return 10
else if b[0][2] == 'o':
return -10
 # Else if none of them have won then return 0
return 0

# Driver code
if __name__ == "__main__":

board = [['x', '_', 'o'],

['_', 'x', 'o'],
['_', '_', 'x']]

value = evaluate(board)
print("The value of this board is", value)

Output
The value of this board is 10

Time Complexity: O(max(row,col))

Auxiliary Space: O(1)