MODULE - III

Heuristic Search Techniques in AI

Heuristic search techniques are used for problem-solving in AI systems. These techniques
help find the most efficient path from a starting point to a goal, making them essential for
applications such as navigation systems, game playing, and optimization problems.

• Heuristic search operates within the search space of a problem to find the best or
near-optimal solution using systematic algorithms.

• Unlike brute-force methods, which exhaustively evaluate all possible solutions,

heuristic search leverages heuristic information to guide the search toward more
promising paths.

heuristics refer to a set of criteria or rules of thumb that provide an estimate of the most
viable solution. By balancing exploration (searching new possibilities)
and exploitation (refining known solutions), heuristic algorithms efficiently solve complex
problems that would otherwise be computationally expensive.

The advantage of heuristic search techniques in AI is their ability to efficiently navigate large
search spaces. By prioritizing the most promising paths, heuristics significantly reduce the
number of possibilities that need to be explored. This not only accelerates the search
process but also enables AI systems to solve complex problems that would be impractical for
exact algorithms.

Components of Heuristic Search

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.

Types of Heuristic Search Techniques

1. A* Search Algorithm
A* Search Algorithm is perhaps the most well-known heuristic search algorithm. It uses a
best-first search and finds the least-cost path from a given initial node to a target node. It
has a heuristic function, often denoted as 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛) , where g(n) is the cost from
the start node to n, and h(n) is a heuristic that estimates the cost of the cheapest path
from n to the goal. A* is widely used in pathfinding and graph traversal.

2. Greedy Best-First Search

Greedy best-first search expands the node that is closest to the goal, as estimated by a
heuristic function. Unlike A*, which considers both path cost and estimated remaining
cost, greedy best-first search only prioritizes the estimated cost to the goal. While this
makes it faster, it can be less optimal, often leading to sub optimal solutions.

3. Hill Climbing

Hill climbing is a heuristic search used for mathematical optimization problems. It is a variant
of the gradient ascent method. It starts from a random initial point and iteratively moves
toward higher values (local maxima) by choosing the best neighbouring state. However, it
can get stuck in local maxima, failing to find the global optimum.

4. Simulated Annealing

Inspired by annealing in metallurgy, simulated annealing is a probabilistic technique for

finding the global optimum. Unlike hill climbing, it allows the search to accept worse
solutions temporarily to escape local optima. This probabilistic acceptance decreases over
time, allowing it to converge toward the best solution.

5. Beam Search

Beam search is a graph-based search technique that explores only a limited number of
promising nodes (a beam). The beam width, which limits the number of nodes stored in
memory, plays a crucial role in the performance and accuracy of the search.

Applications of Heuristic Search

Heuristic search techniques are widely used in various real-world scenarios, including:

• Pathfinding: Whether it's navigating a city or plotting a route in a game, heuristic

search helps find the shortest or most efficient path between two points.

• Optimization: From resource allocation to scheduling, heuristic methods help make

the most of available resources while maximizing efficiency.

• Game Playing: In strategy games like chess and Go, AI relies on heuristic search to
evaluate possible moves and plan ahead.

• Robotics: Autonomous robots use heuristic search to determine their movements,

avoid obstacles, and complete tasks efficiently.
 • Natural Language Processing (NLP): Search algorithms play a key role in language
processing tasks like parsing, semantic analysis, and text generation, helping AI
understand and generate human language.

Advantages of Heuristic Search Techniques

• Efficiency: By focusing on the most promising paths, heuristic search significantly

reduces the number of possibilities explored, saving both time and computational
resources.

• Optimality: When using admissible heuristics, certain algorithms like A* can

guarantee an optimal solution, ensuring the best possible outcome.

• Versatility: Heuristic methods are adaptable and can be applied to a wide range of
problems, from pathfinding and optimization to game AI and robotics.

Limitations of Heuristic Search Techniques

Despite their advantages, heuristic search techniques also have some limitations:

• Heuristic Quality: The effectiveness of heuristic search heavily depends on the

quality of the heuristic function. Poorly designed heuristics can lead to inefficient or
suboptimal solutions.

• Space Complexity: Some heuristic algorithms require large amounts of memory,

especially when dealing with extensive search spaces, making them less practical for
resource-limited environments.

• Domain-Specificity: Designing effective heuristics often requires domain-specific

knowledge, which can make it difficult to create general-purpose heuristic
approaches.

Greedy Best first search algorithm

Greedy Best-First Search is an AI search algorithm that attempts to find the most promising
path from a given starting point to a goal. It prioritizes paths that appear to be the most
promising, regardless of whether or not they are actually the shortest path. The algorithm
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 works by using 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.
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.

Advantages of Greedy Best-First Search:

• Simple and Easy to Implement: Greedy Best-First Search is a relatively

straightforward algorithm, making it easy to implement.

• Fast and Efficient: Greedy Best-First Search is a very fast algorithm, making it ideal for
applications where speed is essential.

• Low Memory Requirements: Greedy Best-First Search requires only a small amount
of memory, making it suitable for applications with limited memory.

• Flexible: Greedy Best-First Search can be adapted to different types of problems and
can be easily extended to more complex problems.

• 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.
Applications of Greedy Best-First Search:

• Pathfinding: Greedy Best-First Search is used to find the shortest path between two
points in a graph. It is used in many applications such as video games, robotics, and
navigation systems.

• Machine Learning: Greedy Best-First Search can be used in machine learning

algorithms to find the most promising path through a search space.

• Optimization: Greedy Best-First Search can be used to optimize the parameters of a

system in order to achieve the desired result.

• Game AI: Greedy Best-First Search can be used in game AI to evaluate potential
moves and chose the best one.

• Navigation: Greedy Best-First Search can be use to navigate to find the shortest path
between two locations.

• Natural Language Processing: Greedy Best-First Search can be use in natural

language processing tasks such as language translation or speech recognition to
generate the most likely sequence of words.

• Image Processing: Greedy Best-First Search can be use in image processing to

segment image into regions of interest.

Hill Climbing in Artificial Intelligence

Hill climbing is a heuristic search algorithm that belongs to the family of local search
methods. It is designed to solve problems where the goal is to find an optimal (or near-
optimal) solution by iteratively moving from the current state to a better neighbouring state,
according to a heuristic or evaluation function.

• It is an optimisation technique used in artificial intelligence (AI) to find solutions for a

wide variety of problems.

• It operates on the principle of incrementally improving a solution by making local

changes and evaluating their merit.

• Its simplicity, intuitive logic and adaptability to different problems make it a go-to
method.

Hill Climbing Algorithms

Hill climbing follows these steps:

1. Initial State: Start with an arbitrary or random solution (initial state).

2. Neighbouring States: Identify neighbouring states of the current solution by making

small adjustments (mutations or tweaks).
 3. Move to Neighbour: If one of the neighbouring states offers a better solution
(according to some evaluation function), move to this new state.

4. Termination: Repeat this process until no neighboring state is better than the current
one. At this point, we have reached a local maximum or minimum.

Features of Hill Climbing Algorithm

1. Variant of Generating and Testing Algorithm: Hill Climbing is a specific variant of

the generating and testing algorithms. The process involves: This iterative feedback
mechanism allows Hill Climbing to refine its search by using information from previous
evaluations to inform future moves in the search space.

• Generating possible solutions: The algorithm creates potential solutions within the
search space.

• Testing solutions: Each generated solution is evaluated to determine if it meets the

desired criteria.

• Iteration: If a satisfactory solution is found, the algorithm terminates; otherwise, it

returns to the generation step.

2. Greedy Approach: Hill Climbing algorithm uses greedy approach, meaning that at each
step, it moves in the direction that optimizes the objective function. This strategy aims to
find the optimal solution efficiently by making the best immediate choice without
considering the overall problem context.

Types of Hill Climbing in Artificial Intelligence

1. Simple Hill Climbing Algorithm: Simple Hill Climbing is a straightforward variant of hill
climbing where the algorithm evaluates each neighbouring node one by one and selects the
first node that offers an improvement over the current one.

2. Steepest-Ascent Hill Climbing: Steepest-Ascent Hill Climbing is an enhanced version of

simple hill climbing. Instead of moving to the first neighboring node that improves the state,
it evaluates all neighbours and moves to the one offering the highest improvement (steepest
ascent).

3. Stochastic Hill Climbing: Stochastic Hill Climbing introduces randomness into the search
process. Instead of evaluating all neighbours or selecting the first improvement.

Advantages of Hill Climbing Algorithm

1. Simplicity and Ease of Implementation: Hill Climbing is a simple and intuitive

algorithm that is easy to understand and implement making it accessible for
developers and researchers.
 2. Versatility: The algorithm can be applied to a wide variety of optimization problems,
including those with large search spaces and complex constraints.

3. Efficiency in Finding Local Optima: Hill Climbing is often highly efficient at finding
local optima making it a suitable choice for problems where a good solution is
required quickly.

4. Customizability: The algorithm can be easily modified or extended to incorporate

additional heuristics or constraints allowing for more tailored optimization
approaches.

Applications of Hill Climbing in AI

• Pathfinding: It is used in AI systems that need to navigate or find the shortest path
between points such as in robotics or game development.

• Optimization: It can be used for solving optimization problems where the goal is to
maximize or minimize a particular objective function such as scheduling or resource
allocation problems.

• Game AI: In certain games, AI uses hill climbing to evaluate and improve its position
relative to an opponent's.

• Machine Learning: It is sometimes used for hyperparameter tuning where the

algorithm iterates over different sets of hyperparameters to find the best
configuration for a machine learning model.

A* Search Algorithm
A* Search algorithm is one of the best and popular technique used in path-finding and graph
traversals, A* Search algorithms, unlike other traversal techniques, it has “brains”. What it
means is that it is really a smart algorithm which separates it from the other conventional
algorithms. This fact is cleared in detail in below sections.
And it is also worth mentioning that many games and web-based maps use this algorithm to
find the shortest path very efficiently (approximation).

Relation (Similarity and Differences) with other algorithms-

Dijkstra is a special case of A* Search Algorithm, where h = 0 for all nodes.

Implementation
We can use any data structure to implement open list and closed list but for best
performance, we use a set data structure of C++ STL(implemented as Red-Black Tree) and a
boolean hash table for a closed list.
The implementations are similar to Dijkstra's algorithm. If we use a Fibonacci heap to
implement the open list instead of a binary heap/self-balancing tree, then the performance
will become better (as Fibonacci heap takes O(1) average time to insert into open list and to
decrease key)
Limitations
Although being the best path finding algorithm around, A* Search Algorithm doesn’t
produce the shortest path always, as it relies heavily on heuristics / approximations to
calculate - h

Simulated Annealing

Simulated Annealing is an optimization algorithm designed to search for an optimal or near-

optimal solution in a large solution space. The name and concept are derived from the
process of annealing in metallurgy, where a material is heated and then slowly cooled to
remove defects and achieve a stable crystalline structure. In Simulated Annealing, the "heat"
corresponds to the degree of randomness in the search process, which decreases over time
(cooling schedule) to refine the solution. The method is widely used in combinatorial
optimization, where problems often have numerous local optima that standard techniques
like gradient descent might get stuck in. Simulated Annealing excels in escaping these local
minima by introducing controlled randomness in its search, allowing for a more thorough
exploration of the solution space.

How Simulated Annealing Works

The algorithm starts with an initial solution and a high "temperature," which gradually
decreases over time. Here’s a step-by-step breakdown of how the algorithm works:

• Initialization: Begin with an initial solution 𝑆𝜊 and an initial temperature 𝑇𝜊. he

temperature controls how likely the algorithm is to accept worse solutions as it
explores the search space.

• Neighbourhood Search: At each step, a new solution 𝑆 ′ is generated by making a

small change (or perturbation) to the current solution S.

• Objective Function Evaluation: The new solution S' is evaluated using the objective
function. If S' provides a better solution than S, it is accepted as the new solution.

• Acceptance Probability: If S' is worse than S, it may still be accepted with a

probability based on the temperature and the difference in objective function values.
The acceptance probability is given by:
Δ𝐸
𝑃(accept) = 𝑒 − 𝑇

• Cooling Schedule: After each iteration, the temperature is decreased according to a

predefined cooling schedule, which determines how quickly the algorithm converges.
Common cooling schedules include linear, exponential, or logarithmic cooling.
 • Termination: The algorithm continues until the system reaches a low temperature
(i.e., no more significant improvements are found), or a predetermined number of
iterations is reached.

Cooling Schedule and Its Importance

The cooling schedule plays a crucial role in the performance of Simulated Annealing. If the
temperature decreases too quickly, the algorithm might converge prematurely to a
suboptimal solution (local optimum). On the other hand, if the cooling is too slow, the
algorithm may take an excessively long time to find the optimal solution. Hence, finding the
right balance between exploration (high temperature) and exploitation (low temperature) is
essential.

Advantages of Simulated Annealing

• Ability to Escape Local Minima: One of the most significant advantages of Simulated
Annealing is its ability to escape local minima. The probabilistic acceptance of worse
solutions allows the algorithm to explore a broader solution space.

• Simple Implementation: The algorithm is relatively easy to implement and can be

adapted to a wide range of optimization problems.

• Global Optimization: Simulated Annealing can approach a global optimum,

especially when paired with a well-designed cooling schedule.

• Flexibility: The algorithm is flexible and can be applied to both continuous and
discrete optimization problems.

Applications of Simulated Annealing

• Simulated Annealing has found widespread use in various fields due to its versatility
and effectiveness in solving complex optimization problems. Some notable
applications include:

• Traveling Salesman Problem (TSP): In combinatorial optimization, SA is often used to

find near-optimal solutions for the TSP, where a salesman must visit a set of cities
and return to the origin, minimizing the total travel distance.

• VLSI Design: SA is used in the physical design of integrated circuits, optimizing the
layout of components on a chip to minimize area and delay.

• Machine Learning: In machine learning, SA can be used for hyperparameter tuning,

where the search space for hyperparameters is large and non-convex.

• Scheduling Problems: SA has been applied to job scheduling, minimizing delays and
optimizing resource allocation.
Constraint Satisfaction Problems (CSP) in Artificial Intelligence

A Constraint Satisfaction Problem is a mathematical problem where the solution must meet
a number of constraints. In CSP the objective is to assign values to variables such that all the
constraints are satisfied. Many AI applications use CSPs to solve decision-making problems
that involve managing or arranging resources under strict guidelines. Common applications
of CSPs include:

• Scheduling: It assigns resources like employees or equipment while respecting time

and availability constraints.

• Planning: Organize tasks with specific deadlines or sequences.

• Resource Allocation: Distributing resources efficiently without overuse

Components of Constraint Satisfaction Problems

CSPs are composed of three key elements:

1. Variables: These are the things we need to find values for. Each variable represents
something that needs to be decided. For example, in a Sudoku puzzle each empty cell is a
variable that needs a number. Variables can be of different types like yes/no choices
(Boolean), whole numbers (integers) or categories like colors or names.

2. Domains: This is the set of possible values that a variable can have. The domain tells us
what values we can choose for each variable. In Sudoku the domain for each cell is the
numbers 1 to 9 because each cell must contain one of these numbers. Some domains are
small and limited while others can be very large or even infinite.

3. Constraints: These are the rules that restrict how variables can be assigned values.
Constraints define which combinations of values are allowed. There are different types of
constraints:

• Unary constraints apply to a single variable like "this cell cannot be 5".

• Binary constraints involve two variables like "these two cells cannot have the same
number".

• Higher-order constraints involve three or more variables like "each row in Sudoku
must have all numbers from 1 to 9 without repetition".

Types of Constraint Satisfaction Problems

CSPs can be classified into different types based on their constraints and problem
characteristics:
 1. Binary CSPs: In these problems each constraint involves only two variables. Like in a
scheduling problem the constraint could specify that task A must be completed
before task B.

2. Non-Binary CSPs: These problems have constraints that involve more than two
variables. For instance in a seating arrangement problem a constraint could state that
three people cannot sit next to each other.

3. Hard and Soft Constraints: Hard constraints must be strictly satisfied while soft
constraints can be violated but at a certain cost. This is often used in real-world
applications where not all constraints are equally important.

Adversarial Search Algorithms in Artificial Intelligence (AI)

The Adversarial search is a well-suited approach in a competitive environment, where two or

more agents have conflicting goals. The adversarial search can be employed in two-
player zero-sum games which means what is good for one player will be the misfortune for
the other. In such a case, there is no win-win outcome. In artificial intelligence, adversarial
search plays a vital role in decision-making, particularly in competitive environments
associated with games and strategic interactions. By employing adversarial search, AI agents
can make optimal decisions while anticipating the actions of an opponent with their
opposing objectives. It aims to establish an effective decision for a player by considering the
possible moves and the counter-moves of the opponents.

The adversarial search in competitive environments can be utilized in the below scenarios
where the AI system can assist in determining the best course of action by both considering
the possible moves and counter-moves of the opponents.

• Each agent seeks to boost their utility or minimize their loss.

• One agent’s action impacts the outcomes and objectives of the other agents.

• Additionally, strategic uncertainty arises when the agents may lack sufficient
information about each other’s strategies.

Role of Adversarial Search in AI

• Game-playing: The Adversarial search finds a significant application in game-

playing scenarios, including renowned games like chess, Go, and poker.

• Decision-making: Decision-making plays a central role in adversarial search

algorithms, where the goal is to find the best possible move or strategy for a player in
a competitive environment against one or more components.
Minimax algorithm

The Minimax algorithm is claimed to be a recursive or backtracking algorithm that is

responsible for choosing the best optimal move in the conflicting environment. The Minimax
algorithm operates on a tree structure known as the game tree, which is the collection of all
the possible moves in the corresponding game states in a given game. The game tree’s leaf
node accommodates all the possible moves. The game state denotes the current board
condition. With every single move, the game state changes and the game tree gets updated
height-wise. When visualized, this game tree often resembles an inverted tree, with the root
representing the current game state and the branches representing possible moves.

This algorithm simply works by proceeding down to the tree until it reaches the leaf node
and then it backs up the minimax values through the tree as the recursion unwinds. The
prime motive of the Minimax algorithm is to maximize the chance of winning for the
maximizer. In the game tree, every node is assigned weights that influence the chances of
winning, the higher the weights, the higher the chances of winning.

Key terminologies in the Minimax algorithm

• Minimax Tree: A tree structure shows all possible moves and game states in a game,
used by Minimax to find the best move.

• MAX (Maximizer) - Maximizer seeks favourable outcomes in games by maximizing

chances of winning for themselves as players.

• MIN (Minimizer) - Minimizer reduces winning chances, making moves leading to

least favourable outcome for the Maximizer in games.

• Initial state - Starting state of game board, representing the configuration at the
beginning of the game.

• Terminal state -Terminal states are the final outcomes of a game board, resulting in
either a win, loss, or draw.

• Heuristic Evaluation Function: Function evaluates game states for maximizer,

assigning numerical values to each game state based on piece positions, material
advantage, and board control.

Optimal Decision Making in Games

Humans' intellectual capacities have been engaged by games for as long as civilization has
existed, sometimes to an alarming degree. Games are an intriguing subject for AI
researchers because of their abstract character. A game's state is simple to depict, and actors
are usually limited to a small number of actions with predetermined results. Physical games,
such as croquet and ice hockey, contain significantly more intricate descriptions, a much
wider variety of possible actions, and rather ambiguous regulations defining the legality of
activities. With the exception of robot soccer, these physical games have not piqued the AI
community's interest.

Games are usually intriguing because they are difficult to solve. Chess, for example, has an
average branching factor of around 35, and games frequently stretch to 50 moves per player,
therefore the search tree has roughly 35100 or 10154 nodes (despite the search graph
having "only" about 1040 unique nodes). As a result, games, like the real world, necessitate
the ability to make some sort of decision even when calculating the best option is
impossible.

Optimal Decision Making in Games

Let us start with games with two players, whom we'll refer to as MAX and MIN for obvious
reasons. MAX is the first to move, and then they take turns until the game is finished. At the
conclusion of the game, the victorious player receives points, while the loser receives
penalties. A game can be formalized as a type of search problem that has the following
elements:

• S0: The initial state of the game, which describes how it is set up at the start.

• Player (s): Defines which player in a state has the move.

• Actions (s): Returns a state's set of legal moves.

• Result (s, a): A transition model that defines a move's outcome.

• Terminal-Test (s): A terminal test that returns true if the game is over but false
otherwise. Terminal states are those in which the game has come to a conclusion.
Mini-Max Algorithm

Mini-Max algorithm is a decision-making algorithm used in artificial intelligence, particularly

in game theory and computer games. It is designed to minimize the possible loss in a worst-
case scenario (hence "min") and maximize the potential gain (therefore "max").

Working of Min-Max Process in AI

Min-Max algorithm involves two players: the maximizer and the minimizer, each aiming to
optimize their own outcomes.

Players Involved

Maximizing Player (Max):

• Aims to maximize their score or utility value.

• Chooses the move that leads to the highest possible utility value, assuming the
opponent will play optimally.

Minimizing Player (Min):

• Aims to minimize the maximizer's score or utility value.

• Selects the move that results in the lowest possible utility value for the maximizer,
assuming the opponent will play optimally.

The interplay between these two players is central to the Min-Max algorithm, as each player
attempts to outthink and counter the other's strategies.

Steps involved in the Mini-Max Algorithm

Step 1: Generate the Game Tree

• Objective: Create a tree structure representing all possible moves from the current
game state.

• Details: Each node represents a game state, and each edge represents a possible
move.

Step 2: Evaluate Terminal States

• Objective: Assign utility values to the terminal nodes of the game tree.

• Details: These values represent the outcome of the game (win, lose, or draw).

Step 3: Propagate Utility Values Upwards

• Objective: Starting from the terminal nodes, propagate the utility values upwards
through the tree.

• Details: For each non-terminal node:

 o If it's the maximizing player's turn, select the maximum value from the child
nodes.

o If it's the minimizing player's turn, select the minimum value from the child
nodes.

Step 4: Select Optimal Move

• Objective: At the root of the game tree, the maximizing player selects the move that
leads to the highest utility value.

Min-Max Formula

The Min-Max value of a node in the game tree is calculated using the following recursive
formulas:

1. Maximizing Player's Turn:

Max(𝑠) = max⁡𝑎∈𝐴(𝑠) Min(Result(𝑠, 𝑎))

Here:

• Max(𝑠)is the maximum value the maximizing player can achieve from state 𝑠.

• 𝐴(𝑠) is the set of all possible actions from state 𝑠.

• Result(𝑠, 𝑎) is the resulting state from taking action 𝑎 in state 𝑠.

Min(Result(𝑠, 𝑎)) is the value for the minimizing player from the resulting state.

Alpha-beta pruning

The word ‘pruning’ means cutting down branches and leaves. In Artificial Intelligence, Alpha-
beta pruning is 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 a search optimization technique that improves the performance of
the minimax algorithm. The minimax algorithm is a decision-making process commonly
used in two-player, zero-sum games like chess. In such games, one player aims to maximize
their score while the other seeks to minimize it.

How Alpha Beta Pruning Works

The key idea behind Alpha Beta Pruning is to avoid evaluating branches of the game tree
that cannot influence the final decision based on the values already discovered during the
search. It achieves this using two values: Alpha and Beta.
Alpha and Beta Values

• Alpha represents the best (highest-value) value that the maximizing player (usually
the AI) can guarantee so far. It acts as a lower bound. The initial value of alpha is −∞.

• Beta represents the best (lowest-value) value that the minimizing player (the
opponent) can guarantee so far. It acts as an upper bound. The initial value of alpha
is +∞.

The Pruning Process

• As the AI explores the tree, it keeps track of Alpha and Beta values. When exploring a
node, it compares the node's value against these values.

• If, at any point, Alpha becomes greater than or equal to Beta; it means the current
branch will not affect the final decision because the opponent will avoid this path in
favor of a better one. As a result, this branch is pruned, and the algorithm moves on
to the next branch.

• This process allows the algorithm to skip large parts of the tree, significantly reducing
the number of nodes to be evaluated.

Working of Alpha-beta Pruning

1. First, we will take care of the first move. So initially, we will define the worst case α = −∞
and β = +∞. If alpha is greater than or equal to beta, we will prune the node.

2. We didn't prune it since the initial value of alpha is less than beta. Now it's turn for MAX.
Therefore, we will calculate the value of alpha at node D. At node D, the value of alpha will
be max (2, 3) = 3.

3. Now, node B’s turn is MIN. That means that the value of alpha beta at node B will be min
(3, ∞). Therefore, alpha will be – ∞ and beta will be 3 at node B.
Symbolic AI

Symbolic AI, also known as Good Old-Fashioned Artificial Intelligence (GOFAI), is a branch of
artificial intelligence that uses symbols and symbolic reasoning to solve complex problems.
Unlike modern machine learning techniques, which rely on data and statistical models,
symbolic AI represents knowledge explicitly through symbols and rules. This approach has
been foundational in the development of AI and remains relevant in various applications
today.

Historical Context and Evolution of Symbolic AI

Symbolic AI's origins trace back to early AI pioneers like John McCarthy, Herbert Simon,
and Allen Newell. They believed that human intelligence could be modeled through logic
and symbol manipulation. Their goal was to create machines that could perform tasks
typically requiring human intelligence, such as problem-solving, decision-making, and
language understanding.

In the 1960s and 1970s, symbolic AI gave birth to early expert systems—programs designed
to simulate human expertise in specific domains like medicine, engineering, and law. These
expert systems were successful in certain narrow fields where the knowledge could be
encoded as rules and facts.

Key Concepts and Methods in Symbolic AI

Symbolic AI revolves around several core concepts and methods that enable the
manipulation of symbols to represent knowledge and facilitate problem-solving. Here are
some of the key elements:

1. Knowledge Representation

Symbolic AI uses various techniques to represent knowledge explicitly, including:

• Logic Programming: Representing knowledge as logical statements and rules, such as

Prolog

• Semantic Networks: Depicting concepts as nodes and their relationships as labeled

links

• Frames: Organizing knowledge into data structures with slots for attributes and
values

• Production Rules: Expressing knowledge as condition-action pairs, like "IF-THEN"

statements
2. Reasoning and Inference

Symbolic AI employs logical reasoning and inference mechanisms to derive new knowledge
from the represented information. Common inference techniques include:

• Deductive Reasoning: Drawing conclusions from general rules and specific facts

• Inductive Reasoning: Generalizing from specific instances to formulate general rules

• Abductive Reasoning: Inferring the most likely explanation for a set of observations

3. Problem-Solving Methods

Symbolic AI systems tackle problems using various problem-solving strategies, such as:

• Generate-and-Test: Generating potential solutions and testing them against

constraints

• Means-Ends Analysis: Identifying differences between the current state and the goal
state, then finding operators to reduce those differences

• Problem Reduction: Breaking down a problem into smaller subproblems that can be
solved independently

4. Knowledge Engineering

Developing Symbolic AI systems requires extensive knowledge engineering, which involves:

• Knowledge Acquisition: Gathering and formalizing domain knowledge from experts

• Knowledge Representation Design: Choosing appropriate representation schemes

for the problem domain

• Knowledge Base Construction: Encoding the acquired knowledge into a structured

knowledge base

Advantages of Symbolic AI

1. Transparency: Since symbolic AI is based on explicitly defined rules and symbols, it is

easy to understand how a decision was made. This transparency makes debugging
and improving the system more straightforward.

2. Flexibility in Representing Complex Knowledge: Symbolic AI excels at representing

and reasoning over structured, rule-based knowledge. It is highly effective in areas
where well-defined logic or processes are involved.

3. Interpretable: Symbolic systems are easier to interpret compared to other AI models,

such as neural networks, which are often described as "black boxes."

Challenges and Limitations

 1. Scalability: As the domain of knowledge expands, the number of symbols and rules
needed to represent it increases exponentially. Managing large-scale symbolic
systems becomes unwieldy.

2. Limited Adaptability: Symbolic AI struggles to handle unstructured data, such as

images or raw text, and is poor at learning from examples or adapting to new
situations without being reprogrammed.

3. Real-World Ambiguity: The rigid rules in symbolic AI make it difficult for systems to
deal with ambiguous, uncertain, or incomplete information. Unlike human cognition,
which can handle ambiguity and context changes, symbolic AI needs precise input to
function effectively.

4. Lack of Learning: Traditional symbolic AI lacks the ability to learn from new
experiences. While it can perform tasks based on its pre-existing rules, it cannot
modify those rules or adapt to new data without human intervention.

Propositional Logic

Propositional logic works with statements called propositions that can be true or false. These
propositions represent facts or conditions about a situation. We use symbols to represent
the propositions and logical operations to connect those propositions. It helps us understand
how different facts are related to each other in complex statements or problem. Proposition
operators like conjunction (∧), disjunction (∨), negation (¬), implication (→) and
biconditional (↔) helps combine various proposition to represent logical relations.

Example of Propositions Logic

• P: "The sky is blue." (This statement can be either true or false.)

• Q: "It is raining right now." (This can also be true or false.)

• R: "The ground is wet." (This is either true or false.)

These can be combined using logical operations to create more complex statements. For
example:

• P ∧ Q: "The sky is blue AND it is raining." (This is true only if both P and Q are true.)

• P ∨ Q: "The sky is blue OR it is raining." (This is true if at least one of P or Q is true.)

• ¬P: "It is NOT true that the sky is blue." (This is true if P is false means the sky is not
blue.)

Logical Equivalence

Two statements are logically equivalent if they always have the same truth values in every
possible situation. For example:
 • The statement "S → T" (if S then T) is equivalent to "¬S ∨ T" (not S or T). This means
"if S is true, then T must be true" is the same as "either S is false or T is true."

• The biconditional "P ↔ Q" (P if and only if Q) is equivalent to "(P → Q) ∧ (Q → P)" (P

implies Q and Q implies P).

These equivalences show that different logical expressions can have the same meaning. You
can verify them using truth tables or by simplifying the statements with logical rules.

Basic Concepts of Propositional Logic

1. Propositions

A proposition is a statement that can either be true or false. It does not matter how
complicated statement is if it can be classified as true or false then it is a proposition. For
example:

• "The sky is blue." (True)

• "It is raining." (False)

2. Logical Connectives

Logical connectives are used to combine simple propositions into more complex ones. The
main connectives are:

• AND (∧): This operation is true if both propositions are true.

Example: "It is sunny ∧ it is warm" is true only if both "It is sunny" and "It is warm"
are true.

• OR (∨): This operation is true if at least one of the propositions is true.

Example: "It is sunny ∨ it is raining" is true if either "It is sunny" or "It is raining" is
true.

• NOT (¬): This operation reverses the truth value of a proposition.

Example: "¬It is raining" is true if "It is raining" is false.

• IMPLIES (→): This operation is true if the first proposition leads to the second.
Example: "If it rains then the ground is wet" (It rains → The ground is wet) is true
unless it rains and the ground is not wet.

• IF AND ONLY IF (↔): This operation is true if both propositions are either true or
false together.
Example: "It is raining ↔ The ground is wet" is true if both "It is raining" and "The
ground is wet" are either true or both false.

Applications of Propositional Logic in AI

1. Knowledge Representation: Propositional logic is used to represent knowledge in a
structured way. It allows AI systems to store and manipulate facts about the world. For
example in expert systems knowledge is encoded as a set of propositions and logical rules.

2. Automated Reasoning: AI uses logical rules such as Modus Ponens and Modus Tollens
which help systems to find new conclusions from existing fact and to "think" logically. For
example:

• Modus Ponens: If "P → Q" and "P" are true then "Q" must be true.

• Modus Tollens: If "P → Q" and "¬Q" are true then "¬P" must be true.

3. Problem Solving and Planning: It allows AI planners to solve problems and to create
action sequences by representing goals. For example the STRIPS planning system helps
propositional logic to represent preconditions and effects of actions.

4. Decision Making: It helps to evaluate various options and find the best course of action.
Logical rules can encode decision criteria and truth tables can be used to assess the
outcomes of different choices.

5. Natural Language Processing (NLP): It is applied in NLP for tasks like semantic parsing
where natural language sentences are converted into logical representations. This helps in
understanding and reasoning about the meaning of sentences.

Syntax and Semantics of First-Order Logic in AI

The syntax of first-order logic consists of symbols and rules for constructing well-formed
formulas (WFFs), which are statements or formulas in the language of FOL. The syntax
encompasses the language constructs used to express knowledge and relationships within a
domain.

Terms in First-Order Logic

Terms represent objects or entities within the domain of discourse. In AI, terms can
correspond to real-world entities, such as objects, individuals, or abstract concepts. They
include:

• Constants: Specific entities, e.g., "John", "Apple".

• Variables: Placeholders for entities, e.g., "x", "y".

• Functions: Expressions applied to terms, e.g., "Age(John)", "Parent(x)".

Predicates in First-Order Logic

Predicates express properties, relations, or conditions that hold between objects. They
describe the state of the world or assert facts about entities within the domain. Examples
include:
 • "IsHuman(x)"

• "IsParent (x, y)"

Quantifiers in First-Order Logic

Quantifiers in first-order logic allow for the specification of statements about the entirety or
existence of objects within the domain.

• Universal quantifiers (∀): Statements that hold for all objects.

• Existential quantifiers (∃): Statements that hold for at least one object.

Connectives in First-Order Logic

Logical connectives such as conjunction (∧), disjunction (∨), implication (→), and negation
(¬) enable the composition of complex statements from simpler ones. They facilitate the
expression of logical relationships and constraints in AI knowledge representations.

Connectives in First-Order Logic

• Conjunction (∧):

o Meaning: Represents logical "and" between two propositions. The

conjunction of two propositions is true only if both propositions are true.

o Example: If P(x) represents "x is red" and Q(x) represents "x is round", then
P(x)∧Q(x) represents "x is red and round".

• Disjunction (∨):

o Meaning: Represents logical "or" between two propositions. The disjunction

of two propositions is true if at least one of the propositions is true.

o Example: If P(x) represents "x is a cat" and Q(x) represents "x is a dog", then
P(x)∨Q(x) represents "x is either a cat or a dog".

• Implication (→):

o Meaning: Represents logical "if-then" relationship between two propositions.

The implication P→Q is true if either Q is true or if P is false.

o Example: If P(x) represents "x is a mammal" and Q(x) represents "x produces
milk", then P(x)→Q(x) represents "if x is a mammal, then it produces milk".

• Negation (¬):

o Meaning: Represents logical "not" or negation of a proposition. It reverses

the truth value of the proposition.
 o Example: If P(x) represents "x is intelligent", then ¬P(x) represents "x is not
intelligent".

Well-Formed Formulas (WFFs) in First-Order Logic

Well-formed formulas (WFFs) in first-order logic (FOL) are expressions constructed according
to the syntactic rules of FOL, representing meaningful statements about the world. These
formulas serve as the building blocks for encoding knowledge and reasoning in AI systems.

Characteristics of WFF

• Syntax Compliance: WFFs adhere to the syntax rules of first-order logic, which define
how terms, predicates, quantifiers, and logical connectives can be combined to form
valid expressions.

• Symbolic Representation: WFFs consist of symbols representing terms (constants,

variables, and functions), predicates (relations), quantifiers (∀, ∃), and logical
connectives (∧, ∨, →, ¬).

• Quantifier Scope: WFFs maintain clear quantifier scope, ensuring that quantifiers
bind variables appropriately within the formula. The scope of quantifiers affects the
interpretation and meaning of the formula.

• Complexity and Nesting: WFFs can range from simple atomic formulas to complex
nested structures involving multiple quantifiers and connectives. Proper nesting and
grouping of sub formulas are essential for clarity and unambiguous interpretation.

Importance of Well-Formed Formulas

• Knowledge Representation: WFFs serve as a formal language for representing

knowledge about the world in AI systems. They enable the encoding of facts, rules,
constraints, and relationships in a structured and precise manner.

• Automated Reasoning: AI systems utilize WFFs for automated reasoning tasks such
as deduction, inference, and logical decision-making. Well-formed formulas facilitate
the application of formal logic principles to derive new information from existing
knowledge.

• Semantic Understanding: Understanding the syntax and semantics of WFFs is crucial

for natural language processing (NLP) systems to interpret and extract meaning from
textual data. Mapping natural language statements to logical representations
involves recognizing and constructing well-formed formulas.

• Problem-Solving and Planning: In AI planning and problem-solving domains, well-

formed formulas play a key role in defining the initial state, goal state, and transition
 rules of a problem. They enable the formulation of logical constraints and objectives
for automated planning algorithms.

Semantics of First-Order Logic

Semantics in first-order logic deals with the interpretation of sentences and formulas within
the framework of a mathematical model. It provides a way to assign meanings to the
symbols and structures used in first-order logic.

Key Elements of Semantics in First-Order Logic

• Variables: These represent placeholders for objects or elements within a domain.

• Constants: These represent specific elements within the domain.

• Predicates: These are expressions that can be true or false depending on the objects
they're applied to.

• Functions: These map elements from the domain to other elements in the domain.

• Quantifiers: Such as "for all" (∀) and "exists" (∃), used to express universal and
existential quantification, respectively.

Interpretation in First-Order Logic

The semantics of first-order logic involve defining what makes a formula true or false in a
given interpretation (also called a model). An interpretation consists of:

• A domain of discourse: This is the set of objects over which the variables range.

• Interpretations of constants: Each constant is mapped to an element in the domain.

• Interpretations of predicates: These are mappings that determine whether a

predicate holds true for a particular tuple of objects from the domain.

• Interpretations of functions: These mappings assign values to functions based on the

values of their arguments.

The truth of a sentence or formula in first-order logic is determined by evaluating it within a

specific interpretation. This is done recursively, where the truth of atomic formulas
(predicates applied to terms) is determined based on the interpretation of predicates and
the values of the terms.

• Universal quantification (∀) asserts that a statement holds true for all objects in the
domain.
 • Existential quantification (∃) asserts that there exists at least one object for which
the statement is true.

Atomic Formulas

An atomic formula P(t₁, t₂, ..., tₙ) is satisfied by an interpretation if the objects assigned to
the terms make the predicate P true.

Complex Formulas

The satisfaction of complex formulas is determined recursively based on the satisfaction of

their constituent parts, considering logical connectives and quantifiers. For example, a
conjunction ϕ∧ψ is satisfied if both ϕ and ψ are satisfied.

Quantifiers

• A universally quantified formula ∀xϕ(x) is satisfied if ϕ(x) is satisfied for all objects in
the domain.

• An existentially quantified formula ∃xϕ(x) is satisfied if ϕ(x) is satisfied for at least

one object in the domain.

Validity in First-Order Logic

• Definition: A formula is considered valid if it is satisfied by every interpretation,

meaning it holds true universally.

• Symbolic Notation: ⊨ϕ, meaning ϕ is valid.

Relationship between Satisfaction and Validity

• A formula is valid if and only if its negation is unsatisfiable. In other words, a formula
is valid if there is no interpretation that makes it false.

• If a formula is valid, it is satisfied by every interpretation.

• If a formula is satisfied by a specific interpretation, it does not necessarily mean it is

valid unless it holds true under all possible interpretations.

Applications of First-Order Logic in AI

First-order logic (FOL) plays a pivotal role in various AI domains by providing a structured and
formal framework for representing and reasoning about knowledge. Here are some key
applications:
1. Automated Reasoning

• Deduction: AI systems use FOL to perform logical deductions, deriving new

information from existing knowledge bases.

• Theorem Proving: FOL underpins automated theorem provers that can verify
mathematical theorems and logical assertions.

2. Knowledge Representation

• Ontology Engineering: FOL is used to create and manage ontologies that define the
relationships between different concepts within a domain.

• Expert Systems: AI systems encode domain-specific knowledge using FOL, enabling

them to make informed decisions and provide expert advice.

3. Natural Language Processing (NLP)

• Semantic Parsing: FOL helps in parsing natural language sentences into logical forms
that AI systems can process and understand.

• Information Extraction: AI systems use FOL to extract structured information from

unstructured text.

4. Planning and Problem Solving

• Automated Planning: FOL defines the initial state, goal state, and transition rules,
allowing AI systems to devise plans to achieve specific objectives.

• Constraint Satisfaction Problems (CSPs): FOL represents constraints and conditions

that AI systems must satisfy to find viable solutions to complex problems.

5. Robotics

• Perception and Action: FOL is used to represent the relationships between objects
and actions in a robot’s environment, facilitating autonomous decision-making and
navigation.

• Task Planning: Robots use FOL to plan and execute sequences of actions to
accomplish tasks

WFFs
• Syntax Compliance: Follows strict grammar rules of the chosen logic (e.g.,
propositional or first-order logic).
 • Atomic Basis: Built from simple propositions (constants, variables, predicates with
terms).

• Connective Rules: Uses logical connectives (¬, ∧, ∨, →, ⇔) to combine simpler WFFs,

requiring proper parentheses for clarity (e.g., (A ∧ B)).

• Quantifier Scope: In predicate logic, quantifiers (∀, ∃) bind variables correctly within
their defined scope (e.g., ∀x (P(x))).

• Unambiguous Interpretation (Semantics): Each WFF can be assigned a definite truth

value (true or false) under a given interpretation (model).

• Validity: A WFF is valid if it's true in every possible interpretation (e.g., A ∨ ¬A).

• Satisfiability: A WFF is satisfiable if it's true in at least one interpretation (e.g., A ∧ B).

• Logical Consequence: WFFs allow for determining if one statement logically follows
from others (inference).

How WFFs Function in AI

• Knowledge Representation: WFFs provide a precise way to encode facts and rules in
AI systems (e.g., expert systems, theorem provers).

• Reasoning & Inference: They form the basis for automated deduction, allowing AI to
derive new knowledge from existing WFFs (premises).

• Formal Systems: WFFs define the vocabulary and grammar for formal reasoning
systems, enabling computers to manipulate logical statements mechanically.

Key Characteristics

• Conjunction of Clauses: The entire formula becomes a set of clauses linked by ANDs
(implicit).

• Disjunction of Literals: Each clause contains literals (predicates or their negations)

connected by ORs.

• Implicit Universal Quantifiers: All variables are assumed to be universally quantified

(∀), so explicit quantifiers are dropped.

• No Existential Quantifiers: Existential quantifiers (∃) are eliminated through a

process called Skolemization, replacing existentially quantified variables with Skolem
functions or constants.

Why It's Used

 • Simplifies Reasoning: Converts complex logical expressions into a uniform, simpler
structure.

• Enables Resolution: It's the required input format for the resolution inference rule, a
fundamental technique for proving logical entailment.

• Prolog: The logic used in Prolog, a logic programming language, is based on Horn
clauses, a restricted form of clausal form.

Unification in AI

Unification in AI aims to develop models and systems that can handle multiple tasks across
various cognitive domains. Instead of designing specialised AI systems for narrowly defined
tasks (like chatbots for conversation or algorithms for image recognition), the goal is to
integrate these systems into a unified framework capable of functioning cohesively.

This effort mirrors the idea of general intelligence, where a single system can perceive,
reason, and act across multiple domains, much like human intelligence.

Mathematics of Unification

In mathematical terms, unification can be viewed as the process of finding a unifier for two
or more objects. In AI, unification involves generalising models to solve multiple tasks by
identifying common patterns or rules.

Formal Definition of Unification

Let 𝐸1 and 𝐸2 be two expressions (like formulas, terms, or sentences). The goal of unification
is to find a substitution 𝜃 such that:

𝐸1 𝜃 = 𝐸2 𝜃

Here:

• 𝐸1 𝜃 means applying substitution 𝜃 to 𝐸1 .

• 𝜃 is a mapping from variables to terms.

A most general unifier (MGU) is the simplest substitution that satisfies the unification.

Example of Unification in Terms

Consider two terms:

𝑓(𝑥, 𝑦) and 𝑓(𝑎, 𝑧)

We can unify these terms by finding the substitution 𝜃 = {𝑥/𝑎, 𝑦/𝑧}. After applying 𝜃, both
terms become:
 𝑓(𝑎, 𝑧)

Thus, 𝜃 = {𝑥/𝑎, 𝑦/𝑧} is the most general unifier (MGU) for these terms.

Why Unification Matters in AI

1. Improved Efficiency: Unified AI systems eliminate the redundancy of developing

separate models for different tasks, reducing computational resources and time.

2. Human-Like Intelligence: Human intelligence is not domain-specific. We seamlessly

switch between conversation, visual understanding, and logical thinking. A unified AI
system would better mimic this fluidity.

3. Scalability: Unified AI systems are more scalable as they can generalise to new tasks
and domains without requiring extensive retraining.

4. Enhanced Collaboration: Unified frameworks promote interdisciplinary research by

integrating insights from various fields like NLP, computer vision, and robotics,
leading to breakthroughs at the intersection of these disciplines.

Resolution Algorithm in Artificial Intelligence

Resolution algorithm is a rule used in Artificial Intelligence (AI) for logical reasoning. It helps
our AI system to figure out if the given statement is logically proven from a set of known
facts or not. It operates mainly on statements expressed in Conjunctive Normal Form
(CNF) and is most commonly used in Propositional Logic and First-Order Predicate Logic.

For example:

If you have a statement like "It is raining OR it is sunny," the algorithm will try to determine if
this is always true, sometimes true or never true based on the information provided.

The algorithm works by systematically combining logical statements until it either finds a
contradiction meaning the statement is false or confirms that the statement is true.

Working of Resolution Algorithm

The Resolution Algorithm works on clauses that are small logical statements connected by
"AND" or "OR." It works by:

Step 1: Convert Statement into Logical Forms

• First, input sentence is converted into a standard format called Conjunctive Normal
Form (CNF) means we break down the complex statements into simple parts
connected by "AND" and "OR."

• If the Original statement: "If it is raining then the ground is wet." then its CNF is:
"NOT(Raining) OR Wet.
Step 2: Combine Clauses Using Resolution Rule

• The core idea of the Resolution Algorithm is the resolution rule which combines two
clauses to produce a new clause.

• If you have two clauses say A OR B and NOT(A) OR C you can combine them to get B
OR C. This process eliminates one variable (A in this case) and simplifies the problem.

Step 3: Repeat Until You Find an Answer

The algorithm keeps applying the resolution rule to pairs of clauses until one of two things
happens:

• Contradiction Found : If the algorithm produces an empty clause (written as FALSE) it

means the original set of statements is inconsistent and cannot be true at the same
time.

• No Contradiction : If no empty clause is found after trying all combinations then the
statements are consistent and can coexist..

Applications of the Resolution

The Resolution Algorithm is widely used in the following AI applications:

1. Automated Theorem Proving : It helps computers to automatically prove

mathematical theorems or verify logical arguments without human intervention.

2. Knowledge Representation : In AI systems knowledge is represented as logical

statements. The Resolution Algorithm allow these systems to reason about that
knowledge effectively.

3. Problem Solving : Many real-world problems can be framed as logical puzzles. For
example scheduling tasks, diagnosing faults in systems or planning routes can all
benefit from logical reasoning using resolution.

4. Foundation for Advanced Techniques : The Resolution Algorithm forms the basis for
more advanced AI techniques such as SAT solvers which is used to solve Boolean
satisfiability problems and logic programming languages.