Unit-1 Merged

Introduction To Artificial Intelligence CAI
INTRODUCTION
What Is AI? A Branch Of Computer Science That Uses Computational Models To Perform
Tasks That Previously Required Human Intelligence.
(Or)
AI Is The Study Of Making Computers Do Things That At The Moment People Do Better.
History Of AI
 1950-1956 - Alan Turning published his work “Computer Machinery and Intelligence”
which eventually became the turning test, which experts used to measure computer
intelligence
 1955 - John Mc Carthy Coined The AI Term and is also known as the father of AI
 1958 - John Mccarthy Created LISP
 1980 - John Searle AI Term Minda, Brains And Programs
 1994 - Raj Reddy. The first winner to get a turning award and also known as the father
of Indian AI
 1943 - Warren Mcculloch And Western Pitts Created A Model Of Artificial Neurons
 1951 - Marvin Minsky And Dear Edmonds Built The First Neural Computer Which
Is Called SNARC
 Prolog - Programming In Logic
 LISP→LIST Processing
 Prolog Is Used In Creating Artificial Intelligence It Relies On The User To Specify The
Rules And Facts About A Situation Along With The End Goal Otherwise Known As A
Query.
 1958 - LISP Programming Language – John Mc Carthy
→ Advice Taker Program
→ Published Is A Program With Common Sense
 1961 - Allen Newell And Herbert
↳ GPS (General Problem Solves)
↳ Imitate Human Problem-Solving Protocols
 1963 - Mccarthy Used J. A. Robinson's
↳ Discovery Of Resolution Method.
↳ Re Construct The " Advice Taker " Programs
1
 Example:- 1965 - Weizenbaum's

↳ ELIZA Program (Weak Method).
↳ Borrowing And Manipulating The Sentences Given By A Human
↳ Doesn't Have Complex Domain Knowledge.
 1969 - Dendral Program Created By Buchanan
↳ Used Doman Knowledge.
 1970's - MYCIN - Blood Infections.

↳ With Uncertain (Or) Incomplete Information
 1972 - Prolog Was Introduced For Calculus, Semantic Networks, Frames, And Objects
The More Efficient Version Was Introduced In 1979.
Intelligent Systems:
To design intelligent systems, it is important to categorize them into four categories (Luger and
Stubberfield 1993), (Russell and Norvig, 2003)
1. Systems that think like humans
2. Systems that think rationally
3. Systems that behave like humans
4. Systems that behave rationally
1. Systems that think like humans - Acting humanly: The Turing Test approach
The Turing Test, proposed by Alan Turing (1950), was designed to provide a satisfactory
operational definition of intelligence.
The computer would need to possess the following capabilities:
 Natural language processing to enable it to communicate successfully in English;
 Knowledge representation to store what it knows or hears;
 Automated reasoning to use the stored information to answer questions and draw new
conclusions;
 Machine learning to adapt to new circumstances and to detect and extrapolate patterns.
2. Systems that think rationally - Thinking humanly: The cognitive modeling approach
 If we are going to say that a given program thinks like a human, we must have some
way of determining how humans think.
2
 We need to get inside the actual workings of human minds.
 There are three ways to do this: through introspection—trying to catch our own
thoughts as they go by; through psychological experiments—observing a person in
action; and through brain imaging—observing the brain in action.
 Once we have a sufficiently precise theory of the mind, it becomes possible to express
the theory as a computer program.
 If the program’s input-output behavior matches corresponding human behavior, that is

evidence that some of the program’s mechanisms could also be operating in humans
3. Systems that behave like humans

 Logicians in the 19th century developed a precise notation for statements about all kinds
of objects in the world and the relations among them.
 By 1965, programs existed that could, in principle, solve any solvable problem
described in logical notation. The so-called logicist tradition within artificial
intelligence hopes to build on such programs to create intelligent systems.
4. Systems that behave rationally – The rational agent approach
 An agent is just something that acts. Of course, all computer programs do something,
but computer agents are expected to do more: operate autonomously, perceive their
environment, persist over a prolonged time period, adapt to change, and create and
pursue goals.
 A rational agent is one that acts so as to achieve the best outcome or, when there is
uncertainty, the best-expected outcome.
The Foundations of Artificial Intelligence

Foundations of AI are in various fields such as
1) Philosophy
2) Mathematics
3) Economics
4) Neuroscience
5) Psychology
3
6) Computer engineering
7) Linguistics
1) Philosophy
 The AI point of view is that philosophical theories are useful to include human-level
artificial systems and provide a basis for designing systems with beliefs, do reasoning,
and planning.
 A key problem for both AI and philosophy is understanding common sense knowledge
and abilities.
2) Mathematics
 Fundamental ideas of AI required a level of mathematical formalization in three areas:
logic, computation, and probability.
 AI systems use formal logical methods and Boolean logic, analysis of limits to what
can be computed, probability theory, uncertainty that forms the basis for most modern
approaches to AI, fuzzy logic, etc.,
 Mathematical concepts give the real solution of hypothetical or virtual problems.
 It is about structure, developing principles that remain true even if you make any
alteration in the components.
3) Economy
 In financial economics, there is a wide use of AI in making decisions about trading in
financial securities like stocks based on a prediction of their prices.
 It can increase efficiency and improve the decision-making process by analyzing large
amounts of data.
 AI deployment can increase overall productivity and create new products, leading to
job creation and economic growth.
4) Neuroscience
 Neuroscience studies are characterized for recording high dimensional and complex
brain data, making the data analysis computationally expensive and time-consuming.
 Neuroscience takes advantage of AI techniques and the increasing processing power

in modern computers, which helped improve the understanding of brain behavior.
4
5) Psychology
 Since psychology is the study of the human brain and its nature, and AI is the branch
that deals with the intelligence in machines, so for understand the intelligence of a
machine we must compare it with human intelligence.
 Artificial intelligence (AI), sometimes known as machine intelligence, refers to the

ability of computers to perform human-like including learning, problem-solving,
perception, decision-making, and speech and language.
 AI is closely linked to human psychology.
6) Computer engineering
 Artificial intelligence is the simulation of human intelligence processes by machines,
especially computer systems.
 Specific applications of AI include expert systems, natural language processing, and

speech recognition.
 An Artificial Intelligence engineer works with different algorithms, neural networks,

and other tools to advance the field of artificial intelligence.
7) Linguistics
 AI aims at simulating human intelligence by computer. Language is one of the primary
expressions of human intelligence.
 Natural Language Processing (NLP) is used to refer to all processes related to the
analysis of texts in natural language - imitation of a human language by a machine.
 By tradition, the term Computational Linguistics refers to written language, whereas

Speech Technology is used for the analysis and synthesis of spoken language.
AI problems:-
1. Learning And Adaptation
AI systems should be capable of decerning from data (or) experience and adapting their
behavior accordingly. this enables them to improve performance over time and handle new
situations More efficiency.
5
2. Complexity
AI problems often involve dealing with complex Systems (or) large amounts of Death. AI
systems must be able to handle this complexity efficiently to produce Meaningful results.
3. Uncertainty
AI systems frequently operate in an environment where outcomes are uncertain (or) incomplete
information is available. They must be equipped to make decisions (or) predictions under Such
Conditions.
4. Dynamism:
Environments in which AI Systems Operate Can Change Over time. these changes may occur
unpredictably (or) according to specific rules, requiring AI Systems, to Continually adjust thin
Strategies (or) Models.
5. Interactivity:-
Many AI applications Involve interaction with users(or) other agents. Effective AI Systems
should be able to perceive, interpret & respond to these Interactions in a Meaningful way.
6. Context-dependent:-
The Behaviour (or) performance of AI systems may depend on the Contest on which they
operate understanding and appropriately responding to different contexts is essential for
achieving desired outcomes.
7. Multi-disciplinary:-
AI problems often require knowledge and techniques from multiple disciplines, including
Computer Science, mathematics, statistics, psychology, and more. Integrating insights from
these diverse fields & is necessary for developing effective Al Solutions.
8. Goal-oriented Design:-
AI systems are typically designed to achieve specific objectives (or ) goals. Designing AI
systems with clear objectives in mind helps guide the development processes and ensure that
the. Systems are focused on achieving meaningful outcomes.
These characteristics Collective Collectively shape the Challenges and opportunities involved
in developing and deploying AI Systems across various domains and applications.
6
Agents and Environments
 An agent is something that perceives and acts in an environment.

 It can also be described as a software entity that conducts operations in the place of
users or programs after sensing the environment.
 An environment is the surroundings of the agent.
 The agent takes input from the environment through sensors and delivers the output to
the environment through actuators.
 The following are the examples of agents:
1) Human-Agent: A human agent has eyes, ears, and other organs that work for sensors, and
the hand, legs, and vocal tract work for actuators.
2) Robotic Agent: A robotic agent can have cameras, an infrared range finder, NLP for sensors,
and various motors for actuators.
3) Software Agent: Software agents can have keystrokes, file contents as sensory input act on
those inputs, and display output on the screen.
 A sensor is a device that detects and responds to some type of input from the physical
environment. The output is generally a signal that is converted to a human-readable
display at the sensor location or transmitted electronically over a network for reading
or further processing.
 The following are examples of sensors.
7
1) Temperature Sensor.
2) Proximity Sensor.
3) Accelerometer.
4) IR Sensor (Infrared Sensor)
5) Pressure Sensor.
6) Light Sensor.
7) Ultrasonic Sensor.
8) Smoke sensor
9) Alcohol Sensor.
 An actuator is a device that converts electrical signals into physical events or

characteristics.
 The following are the examples of actuators.
1) Electric motors
2) Stepper motors
3) Jackscrews
 The agent function for an agent specifies the action taken by the agent in response to
any percept sequence.
 The performance measure evaluates the behavior of the agent in an environment.
 A rational agent acts so as to maximize the expected value of the performance measure,
given the percept sequence it has seen so far.
 The agent program implements the agent function.
 There exists a variety of basic agent-program designs reflecting the kind of information
made explicit and used in the decision process.
 The designs vary in efficiency, compactness, and flexibility.
 The appropriate design of the agent program depends on the nature of the environment.
8
 EXAMPLE:-
 The Vacuum Cleaner Worlds-
 This particular world has two locations Square A and Square B.
 the vacuum agent perceives which Square it is in and whether there is dirt in the Square
 It Can Choose to Move left, Move right, Suck up the dirt , or Do nothing.

A A B
The agent work:- if the Current Square is dirty, then Suck otherwise move to the Other Square.
Percept Square Action
[A, clean] Right
[A, Dirty] Suck
[B, Clean] Left
[A, clean] [A, dirty] Suck
Right
[A, Clean], [A, clean] [A, Clean]
Right
[A, Clean], [A, clean] [A, Clean]
Good Behavior: The Concept of Rationality

 A rational agent is one that does the right thing—conceptually speaking, every entry
in the Table for the agent function is filled out correctly. Obviously, doing the right
thing is better
9
 than doing the wrong thing.

 An agent is something that perceives and acts in an environment.
 It can also be described as a software entity that conducts operations in the place of
users or programs after sensing the environment.
 An environment is the surroundings of the agent.
 A task environment specification includes the performance measure, the external

environment, the actuators, and the sensors.
 In designing an agent, the first step must always be to specify the complete task
environment.
Rationality
 Rationality depends on four things:
1) The performance measure that defines the criterion of success.
2) The agent’s prior knowledge of the environment.
3) The actions that the agent can perform.
4) The agent’s percept sequence to date.

 This leads to a definition of a rational agent
Omniscience, learning, and autonomy
 An omniscient (perfect) agent knows the actual outcome of its actions and can act
accordingly; but perfection is impossible in reality.
 Rationality is NOT the same as perfection. Rationality maximizes expected

performance, while perfection maximizes actual performance.
 A rational agent not only to gather information but also to learn as much as possible
from what it perceives.
 The agent’s initial configuration could reflect some prior knowledge of the
environment, but as the agent gains experience this may be modified and augmented.
 A rational agent should be autonomous—it should learn.
10
 After sufficient experience of its environment, the behavior of a rational agent can
become effectively independent of its prior knowledge.
 Hence, the incorporation of learning allows one to design a single rational agent that
will succeed in a vast variety of environments.
The Nature of the Environment

 Specifying the task environment
 A task environment specification includes the performance measure, the external
environment, the actuators, and the sensors.
 We group all these under the heading of the task environment, called PEAS
(Performance, Environment, Actuators, Sensors).
 In designing an agent, the first step must always be to specify the complete task
environment.

 An actuator is a device that converts electrical signals into physical events or
characteristics.
 A sensor is a device that detects and responds to some type of input from the physical
environment. The output is generally a signal that is converted to a human-readable
display at the sensor location or transmitted electronically over a network for reading
or further processing.
 Software agents can have keystrokes, file contents as sensory input act on those inputs,
and display output on the screen.
PEAS for an automated taxi driver

 Performance measure: Safe, fast, legal, comfortable trip, maximize profits •
 Environment: Roads, other traffic, pedestrians, customers •
 Actuators: Steering wheel, accelerator, brake, signal, horn •
 Sensors: Cameras, sonar, speedometer, GPS, odometer, engine sensors, keyboard
11
Properties of Task Environment

Fully observable vs partially observable:
 If an agent’s sensors give access to the complete state of the environment at each point
in time, then we say that the task environment is fully observable. If the agent has no
sensors at all then the environment is unobservable.
Single-agent vs. multiagent:
 If only one agent is involved in an environment, and operating by itself then such an
environment is called a single-agent environment. However, if multiple agents are
operating in an environment, then such an environment is called a multi-agent
environment.
 For example, the vacuum cleaning environment is single-agent while chess is a two-
agent environment.
Deterministic vs. stochastic:
 If the next state of the environment is completely determined by the current state and
the action executed by the agent, then we say the environment is deterministic;
otherwise, it is stochastic. A stochastic environment is random in nature and cannot be
determined completely by an agent.
Episodic vs. sequential:
 In an episodic task environment, the agent’s experience is divided into atomic episodes.
In each episode, the agent receives a percept and then performs a single action. The
next episode does not depend on the actions taken in previous episodes. Many
classification tasks are episodic.
 In sequential environments, the current decision could affect all future decisions. For
example, the Chess game is sequential. In this case, short-term actions can have long-
term consequences. 
 Episodic environments are much simpler than sequential environments because the
agent does not need to think ahead.
Discrete vs. continuous:
 An environment is said to be discrete if there are a finite number of actions that can be
performed within it. Continuous AI environments depend on unknown and rapidly
changing data sources. Vision systems in drones or self-driving cars operate on
continuous AI environments.
12
Known vs. unknown:

 In a known environment, the outcomes for all actions are given. If the environment is
unknown, the agent has to learn how it works in order to make good decisions.
The Structure of Agents
 The task of AI is to design an agent program that implements the agent function. The
structure of an intelligent agent is a combination of architecture and agent program. It can
be viewed as:
 Agent = Architecture + Agent program
 The following are the main three terms involved in the structure of an AI agent:
1) Architecture: Architecture is machinery that an AI agent executes on.
2) Agent Function: The agent function is used to map a percept to an action.
3) Agent program: An agent program is an implementation of an agent function.

An agent program executes on the physical architecture to produce function.
 There are four kinds of agent programs.
1) Simple reflex agents
2) Model-based reflex agents
3) Goal-based agents
4) Utility-based agents
1. Simple reflex agents
 The simplest kind of agent is the simple reflex agent. These agents select actions on the
basis of the current percept, ignoring the rest of the percept history.
 It acts according to a rule whose condition matches the current state, as defined by the
percept. The following is the schematic diagram for a simple reflex agent.
13
The following is the simple reflex agent function.
function SIMPLE-REFLEX-AGENT(percept ) returns an action

persistent: rules, a set of condition–action rules
state←INTERPRET-INPUT(percept )
rule←RULE-MATCH(state, rules)
action ←rule.ACTION
return action
 The INTERPRET-INPUT function generates an abstracted description of the current

state from the percept, and the RULE-MATCH function returns the first rule in the set
of rules that matches the given state description.
 The agent will work only if the correct decision can be made on the basis of only the
current percept—that is, only if the environment is fully observable.
2. Model-based reflex agents

 The most effective way to handle partial observability is for the agent to keep track of
the part of the world it can’t see now.
 That is, the agent should maintain some sort of internal state that depends on the percept
history and thereby reflects at least some of the unobserved aspects of the current state.
 The following is the schematic diagram for the Model-based reflex agent.
14
 The following is the model-based reflex agent function.
function MODEL-BASED-REFLEX-AGENT(percept ) returns an action 

persistent: state, the agent’s current conception of the world state model , a
description of how the next state depends on current state and action rules, a set of
condition–action rules
action, the most recent action, initially none
state←UPDATE-STATE(state, action, percept ,model )
rule←RULE-MATCH(state, rules)
action ←rule.ACTION
return action
3. Goal-based agents
Goal-based agents expand the capabilities of the model-based agent by having the "goal"
information. They choose an action, so that they can achieve the goal.
These agents may have to consider a long sequence of possible actions before deciding whether
the goal is achieved or not.
The following is the schematic diagram of the goal-based agent.
15
PROBLEM-SOLVING AGENTS
PROBLEM-SOLVING APPROACH IN ARTIFICIAL INTELLIGENCE PROBLEMS

The reflex agents are known as the simplest agents because they directly map states into
actions. Unfortunately, these agents fail to operate in an environment where the mapping is too
large to store and learn. Goal-based agent, on the other hand, considers future actions and the
desired outcomes.
Here, we will discuss one type of goal-based agent known as a problem-solving agent, which
uses atomic representation with no internal states visible to the problem-solving algorithms.
Problem-solving agent
The problem-solving agent performs precisely by defining problems and their several
solutions.
 According to psychology, “problem-solving refers to a state where we wish to reach a
definite goal from a present state or condition.”
 According to computer science, problem-solving is a part of artificial intelligence

which encompasses several techniques such as algorithms, and heuristics to solve a
problem.
Therefore, a problem-solving agent is a goal-driven agent and focuses on satisfying the goal.
16
PROBLEM DEFINITION
To build a system to solve a particular problem, we need to do four things:
(i) Define the problem precisely. This definition must include specification of the initial
situations and also final situations that constitute (i.e.) acceptable solutions to the problem.
(ii) Analyze the problem (i.e.) important features that have an immense (i.e.) huge impact on
the appropriateness of various techniques for solving the problems.
(iii) Isolate and represent the knowledge to solve the problem.
(iv) Choose the best problem–solving techniques and apply them to the particular
problem.
Steps performed by Problem-solving agent

Goal Formulation: It is the first and simplest step in problem-solving. It organizes the
steps/sequence required to formulate one goal out of multiple goals as well as actions to achieve
that goal. Goal formulation is based on the current situation and the agent’s performance
measure (discussed below).
Problem Formulation: It is the most important step of problem-solving which decides what
actions should be taken to achieve the formulated goal. There are following five components
involved in problem formulation:
i. Initial State: It is the starting state or initial step of the agent towards its goal.
ii. Actions: It is the description of the possible actions available to the agent.
iii. Transition Model: It describes what each action does.
iv. Goal Test: It determines if the given state is a goal state.
v. Path cost: It assigns a numeric cost to each path that follows the goal. The problem-
solving agent selects a cost function, which reflects its performance measure.
Remember, an optimal solution has the lowest path cost among all the solutions.
Note: Initial state, actions, and transition model together define the state-space of the
problem implicitly. The space of a problem is a set of all states which can be reached from the
initial state followed by any sequence of actions. The state space forms a directed map or graph
where nodes are the states, links between the nodes are actions, and the path is a sequence of
states connected by the sequence of actions.
 Search: It identifies all the best possible sequences of actions to reach the goal state
from the current state. It takes a problem as an input and returns a solution as its output.
17
 Solution: It finds the best algorithm out of various algorithms, which may be proven
as the best optimal solution.
 Execution: It executes the best optimal solution from the searching algorithms to reach
the goal state from the current state.
Example Problems
There are two types of problem approaches:
 Toy Problem: It is a concise and exact description of the problem that is used by the
researchers to compare the performance of algorithms.
 Real-world Problem: It is real-world-based problems that require solutions. Unlike a
toy problem, it does not depend on descriptions, but we can have a general formulation
of the problem.
Some Toy Problems
 8 Puzzle Problem: Here, we have a 3×3 matrix with movable tiles numbered from 1
to 8 with a blank space. The tile adjacent to the blank space can slide into that space.
The objective is to reach a specified goal state similar to the goal state, as shown in the
below figure.
 In the figure, our task is to convert the current state into goal state by sliding digits into
the blank space.
In the above figure, our task is to convert the current(Start) state into the goal state by
sliding digits into the blank space.
18
The problem formulation is as follows:

 States: It describes the location of each numbered tile and the blank tile.
 Initial State: We can start from any state as the initial state.
 Actions: Here, actions of the blank space are defined, i.e., either left, right, up, or
down
 Transition Model: It returns the resulting state as per the given state and actions.
 Goal test: It identifies whether we have reached the correct goal state.
 Path cost: The path cost is the number of steps in the path where the cost of each step
is 1.
 Note: The 8-puzzle problem is a type of sliding-block problem that is used for testing
new search algorithms in artificial intelligence.
 8-queens problem: This problem aims to place eight queens on a chessboard in an
order where no queen may attack another. A queen can attack other queens either
diagonally or in the same row and column.
From the following figure, we can understand the problem as well as its correct solution.
19
It is noticed from the above figure that each queen is set on the chessboard in a position where
no other queen is placed diagonally, in the same row or column. Therefore, it is the right
approach to the 8-queens problem.
For this problem, there are two main kinds of formulation:
1. Incremental formulation: It starts from an empty state where the operator augments a
queen at each step.
The following steps are involved in this formulation:
i. States: Arrangement of any 0 to 8 queens on the chessboard
ii. Initial State: An empty chessboard
iii. Actions: Add a queen to any empty box.
iv. Transition model: Returns the chessboard with the queen added in a box.
v. Goal test: Checks whether 8-queens are placed on the chessboard without any attack.
vi. Path cost: There is no need for path cost because only final states are counted.
vii. In this formulation, there is approximately a 1.8 x 1014 possible sequence to
investigate.
2. Complete-state formulation: It starts with all the 8-queens on the chessboard and moves
them around, saving from the attacks.
 The following steps are involved in this formulation
 States: Arrangement of all the 8 queens one per column with no queen attacking the
other queen.
 Actions: Move the queen to the location where it is safe from the attacks.
 This formulation is better than the incremental formulation as it reduces the state space
from 1.8 x 1014 to 2057, and it is easy to find the solutions.
Some Real-world problems

 Traveling salesperson problem(TSP): It is a touring problem where the salesman
can visit each city only once. The objective is to find the shortest tour and sell out the
stuff in each city.
 VLSI Layout problem: In this problem, millions of components and connections are
positioned on a chip in order to minimize the area, circuit delays, and stray capacitances,
and maximize the manufacturing yield.
20
The layout problem is split into two parts:

 Cell layout: Here, the primitive components of the circuit are grouped into cells, each
performing its specific function. Each cell has a fixed shape and size. The task is to
place the cells on the chip without overlapping each other.
 Channel routing: It finds a specific route for each wire through the gaps between the
cells.
 Protein Design: The objective is to find a sequence of amino acids that will fold into a
3D protein that has the property to cure some diseases.
21
22
Explanation: The following steps are taken:

1. Fill the 5-gallon jug completely.
2. Transfer 3 gallon from a 5-gallon jug to a 3-gallon jug.
3. Empty the 3-gallon capacity jug.
4. Transfer the remaining 2 gallon from a 5-gallon jug to a 3-gallon jug.
5. Now, fill the 5-gallon jug fully.
6. Pour 1 gallon from a 5-gallon jug into a 3-gallon jug.
7. There! We have 4 gallon in the first jug, now empty the 2nd jug.
For more clarity, check the below illustration
Searching for solutions

We have seen many problems. Now, there is a need to search for solutions to solve them. In
this section, we will understand how searching can be used by the agent to solve a problem.
For solving different kinds of problems, an agent makes use of different strategies to reach the
goal by searching for the best possible algorithms. This process of searching is known as a
search strategy
23
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.
Searching for solutions:
 Having formulated some problems, we now need to solve them. This is done by a search
through the state space.
 search techniques that use an explicit search tree that is generated by the initial state
and the successor function that together define the state space.
 In general, we may have a search graph rather than a search tree, when the same state
can be reached from multiple paths.
 The root of the search tree is a search node corresponding to the initial state. The first
step is to test whether this is a goal state. his is done by expanding the current state.
 that is, applying the successor function to the current state. thereby generating a new
set of states.
 We continue choosing, testing, and expanding until either a solution is found or there
are no more states to be expanded. The choice of which state to expand is determined
by the search strategy.
state space:
 It facilitates easy search

 By using state-space search, one can also find a path from the start state to the goal state
while solving a problem.
Search Strategy:
It is important to distinguish between the state space and the search tree. For the route-
finding problem, there are only 20 states in the state space, one for each city. But there are an
infinite number of paths in this state space, so the search tree has an infinite number of nodes.
There are many ways to represent nodes, but we will assume that a node is a data
structure with five components:
STATE: the state in the state space to which the node corresponds;
PARENT-NODE: the node in the search tree that generated this node:
ACTION: the action that was applied to the parent to generate the node:
PATH-COST: the cost, traditionally denoted by g(n), of the path from the initial state to the
node, as indicated by the parent pointers.
DEPTH: the number of steps along the path from the initial state.
It is important to remember the distinction between nodes and states. A node is a

bookkeeping data structure used to represent the search tree.
the collection of nodes that have been generated but not yet expanded collection is
called the fringe. Each element of the fringe is a leaf node, that is, a node with no successors
in the tree.
function TREE-SEARCH(problem, strategy) returns a solution, or failure initialize the search tree
using the initial state of problem
Loop Do
if there are no candidates for expansion then return failure
choose a leaf node for expansion according to strategy
if the node contains a goal state then return the corresponding solution
else expand the node and add the resulting nodes to the search tree
Measuring Problem-Solving Performance
The output of a problem-solving algorithm is either a failure or a solution. (Some algorithms

might get stuck in an infinite loop and never return an output.) We will 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?
Search Strategies
Uninformed search Informed Search

strategies (blind search) Strategies( heuristic)
b
Breadth-First Search Hill-Climbing
Depth-First Search A*
Depth-Limit Search AO*
Bi-Directional Search Memory Bound Search
UNINFORMED SEARCH STRATEGIES
This uninformed search (also called blind search). The term means that they have no additional
information about states beyond that provided in the problem definition. All they can do is
generate successors and distinguish a goal state from a nongoal state. All search strategies are
distinguished by the order in which nodes are expanded.
Breadth-first search(BFS)
 Breadth-first search is a simple strategy in which the root node is expanded first, then
all the
 successors of the root node are expanded next, then their successors, and so on.
 In general, all the nodes are expanded at a given depth in the search tree before any
nodes at the next level are expanded.
 Breadth-first search can be implemented by calling TREE-SEARCH with an empty
fringe that is a first-in-first-out (FIFO) queue, assuring that the nodes that are visited
first will be expanded first. (left-right)
 In other words, calling TREE-SEARCH(problem, FIFO-QUEUE()) re-
 results in a breadth-first search The FIFO queue puts all newly generated
successors at the end of the queue.
 which means that shallow nodes are expanded before deeper nodes.
 We can easily see that it is complete if the shallowest goal node is at some finite depth
d. breadth-first search will eventually find it after expanding all shallower nodes
(provided the branching factor b is finite).
 The shallowest goal node is not necessarily the optimal one; technically, breadth-first
search is optimal if the path cost is a non-decreasing function of the depth of the node.
(For example, when all actions have the same cost.)
 So far, the news about the breadth-first search has been good. To see why it is not always
the strategy of choice, we have to consider the amount of time and memory it takes to
complete a search.
 To do this, we consider a hypothetical state space where every state has b successors.
The root of the search tree generates b nodes at the first level, each of which generates
& more nodes, for a total of b² at the second level.
 Each of these generates & more nodes, yielding b nodes at the third level, and so on.
Now suppose that the solution is at depth d.
b+b^ 2 +b^ 3 +*+ b ^ d + (b ^ (d + 1) - b) = O(b ^ (d + 1))
d= depth of shallowest
b= node at every state
Advantages:
 BFS will provide a solution if any solution exists.

 If there is more than one solution for a given problem, then BFS will provide the
minimal solution which requires the least number of steps.
Disadvantages:
 It requires lots of memory since each level of the tree must be saved in memory to
expand to the next level.
 BFS needs lots of time if the solution is far away from the root node.
Example:
In the below tree structure, we have shown the traversing of the tree using the BFS algorithm
from the root node S to goal node K. The BFS search algorithm traverses 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: The time Complexity of the 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: The space complexity of the BFS algorithm is given by the Memory size
of the 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.
Depth-first Search
 Depth-first search is a recursive algorithm for traversing a tree or graph data

structure.
 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.
 DFS uses a stack data structure for its implementation.
 The process of the DFS algorithm is similar to the BFS algorithm.
 Last in first out LIFO.
Note: Backtracking is an algorithm technique for finding all possible solutions using recursion.
Advantage:
o DFS requires very little memory as it only needs to store a stack of the nodes on the
path from the root node to the current node.
o It takes less time to reach the goal node than the BFS algorithm (if it traverses in the
right path).
Disadvantage:
o There is the possibility that many states keep re-occurring, and there is no guarantee of
finding a solution.
o The DFS algorithm goes for deep-down searching and sometime it may go to the
infinite loop.
Example:
In the below search tree, we have shown the flow of the depth-first search, and it will follow
the order:
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 the goal node is not found.
After backtracking it will traverse node C and then G, and here it will terminate as it found the
goal node.
Completeness: The DFS search algorithm is complete within finite state space as it will
expand every node within a limited search tree.
Time Complexity: The 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: The DFS algorithm needs to store only a 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: The DFS search algorithm is non-optimal, as it may generate a large number of steps
or high cost to reach the goal node.
Informed (Heuristic) Search Algorithms
 The informed search algorithm is more useful for large search spaces.
 Heuristic (enabling someone to discover) is a function used to find the most promising
path.
 An informed search algorithm uses the idea of heuristics for searching. So it is also
called Heuristic search.
 It takes the current state as the starting state and produces the estimation of how close
a state is, to the goal state.
 The heuristic method, however, might not always give the best solution, but it
guarantees to find a good solution in a reasonable time.
 The heuristic function is represented by h(n), and it calculates the cost of an optimal
path between the pair of states. The value of the heuristic function is always positive.
 Heuristic function is given as h(n) <= h*(n)
 Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should
be less than or equal to the estimated cost.
 There are two algorithms in informed search.
o Hill climbing search Algorithm
o A* Search Algorithm
o AO* Search Algorithm
Pure Heuristic Search:
 Pure heuristic search is the simplest form of heuristic search algorithm.

 It expands nodes based on their heuristic value h(n).
 It maintains two lists, OPEN and CLOSED list.
 In the CLOSED list, it places those nodes which have already expanded and in the
OPEN list, it places nodes that have yet not been expanded.
 On each iteration, each node n with the lowest heuristic value is expanded and generates
all its successors, and n is placed in the closed list. The algorithm continues unit a goal
state is found.
Hill-Climbing search
 Hill climbing algorithm is a local search algorithm which continuously moves in

the direction of increasing elevation/value to find the peak of the mountain or the
best solution to the problem. It terminates when it reaches a peak value where no
neighbor has a higher value.
 The hill climbing algorithm is a technique that is used for optimizing

mathematical problems.
 One of the widely discussed examples of the Hill climbing algorithm is the
salesman problem in which we need to minimize the distance traveled by the
salesman or the 8 queens problem.
 It is also called greedy local search as it only looks to its good immediate
neighbor state and not beyond that.
 A node of hill climbing algorithm has two components which are state and value.
At each step the current node is replaced by the best neighbor; in this version, that means the
neighbor with the highest VALUE, but if a heuristic cost estimate h is used, we would find the
neighbor with the lowest h.
Features of Hill climbing
 Generate and test variants.
 Greedy approach.
 No backtracking.
function HILL-CLIMBING(problem) returns a state that is a local maximum
current ←MAKE-NODE(problem.INITIAL-STATE)
loop do
neighbor ←a highest-valued successor of current
if neighbor.VALUE ≤ current.VALUE then return current.STATE
current←neighbor
Different regions in the state space landscape:

 Local Maximum: Local maximum is a state which is better than its neighbor states,
but there is also another state which is higher than it.
 Global Maximum: Global maximum is the best possible state of state space landscape.
It has the highest value of objective function.
 Current state: It is a state in a landscape diagram where an agent is currently present.
Flat local maximum: It is a flat space in the landscape where all the neighbor states of
current states have the same value.
 Shoulder: It is a plateau region that has an uphill edge.
State-space Diagram for Hill Climbing:
 The state-space landscape is a graphical representation of the hill-climbing algorithm
which shows a graph between various states of the algorithm and the Objective
function/Cost.
 On the Y-axis we have taken the function which can be an objective function or cost
function, and state-space on the x-axis.
 If the function on the Y-axis is cost then, the goal of the search is to find the global
minimum and local minimum.
 If the function of the Y-axis is the Objective function, then the goal of the search is to
find the global maximum and local maximum.
Types of Hill Climbing Algorithm:

1. Simple hill Climbing:
 It only evaluates the neighbor node state at a time and selects the first one which
optimizes current cost and sets it as a current state.
 It only checks its one successor state, and if it finds better than the current state,
then move else be in the same state.
2. Steepest-Ascent hill-climbing:
 This algorithm examines all the neighboring nodes of the current state and
selects one neighbor node which is closest to the goal state.
 This algorithm consumes more time as it searches for multiple neighbors
3. Stochastic hill Climbing:
o this search algorithm selects one neighbor node at random and decides whether
to choose it as a current state or examine another state.
Problems in Hill Climbing Algorithm:
1. Local Maximum:
Local maximum is a peak state in the landscape which is better than each of its neighboring
states, but there is another state also present which is higher than the local maximum.
2. Plateau:
A plateau is the flat area of the search space in which all the neighbor states of the current state
contains the same value, because of this algorithm does not find any best direction to move. A
hill-climbing search might be lost in the plateau area.
3. Ridges:
A ridge is a special form of the local maximum. It has an area which is higher than its
surrounding areas, but it has a slope, and cannot be reached in a single move.
2. Simulated Annealing:
A hill-climbing algorithm which never makes a move towards a lower value is

guaranteed to be incomplete because it can get stuck on a local maximum. And if algorithm
applies a random walk, by moving a successor, then it may complete but not efficient.
Simulated Annealing is an algorithm that yields both efficiency and completeness.
3. Genetic algorithm:
A genetic algorithm is a stochastic hill-climbing search in which a large population of states is
maintained. New states are generated by mutation and by crossover, which combines pairs of
states from the population.
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 solves
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:
Step 1: 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 stop.
Step 3: Select the node from the OPEN list which has the smallest value of evaluation function
(g+h), if node n is the 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 the
evaluation function for n' and place it into
Open list.
Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the back
pointer which reflects the lowest g(n') value.
Step 6: Return to Step 2.
Advantages:
 A* search algorithm is the best algorithm than other search algorithms.
 A* search algorithm is optimal and complete.
 This algorithm can solve very complex problems.
Disadvantages:
 It does not always produce the shortest path as it mostly based on heuristics and
approximation.
 A* search algorithm has some complexity issues.
 The main drawback of A* is memory requirement as it keeps all generated
nodes in the memory, so it is not practical for various large-scale problems.
Example:
In this example, we will traverse the given graph using the A* algorithm. The heuristic value
of all states is given in 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 the start state.
Here we will use the OPEN and CLOSED list.
Solution:
Iteration 4 will give the final result, as
S--->A--->C--->G it provides the optimal path with cost 6.
Time Complexity: The time complexity of A* search algorithm depends on heuristic function,
and the number of nodes expanded is exponential to the depth of solution d. So the time
complexity is O(b^d), where b is the branching factor.
Space Complexity: The space complexity of A* search algorithm is O(b^d)
AO* algorithm
 Best-first search is what the AO* algorithm does.

 The AO* method divides any given difficult problem into a smaller group of problems
that are then resolved using the AND-OR graph concept.
 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.
AND - OR GRAPH
 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 .
 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.
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 solutionn 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:
AO* Algorithm – Question tree
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
AO* Algorithm (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 path f(A⇢C+D) is 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 in AI
 We already know about the divide and conquer strategy, a solution to a problem can
be obtained by decomposing it into smaller sub-problems.
 Each of these sub-problems can then be solved to get its sub-solution.
 These sub-solutions can then be recombined to get a solution as a whole. That is called
Problem Reduction.
 This method generates arcs which are called AND arcs.
 One AND arc may point to any number of successor nodes, all of which must be solved
for an arc to point to a solution.
Problem Reduction algorithm:
1. Initialize the graph to the starting node.
2. Loop until the starting node is labeled SOLVED or until its cost goes above FUTILITY:
(i) Traverse the graph, starting at the initial node and following the current best path and
accumulate the set of nodes that are on that path and have not yet been expanded.
(ii) Pick one of these unexpanded nodes and expand it. If there are no successors, assign
FUTILITY as the value of this node. Otherwise, add its successors to the graph and for each of
Example:Three disk tower of Hanoi problem.

EXAMPLE FOR AND-OR GRAPH
EXAMPLE: 1
STEP 1:
STEP 2:
.
STEP 3:
STEP4:
Game Playing
Game Playing is an important domain of artificial intelligence. Games don’t require much
knowledge; the only knowledge we need to provide is the rules, legal moves and the conditions
of winning or losing the game. Both players try to win the game. So, both of them try to make
the best move possible at each turn. Searching techniques like BFS(Breadth First Search) are
not accurate for this as the branching factor is very high, so searching will take a lot of time.
So, we need another search procedures that improve –
 Generate procedure so that only good moves are generated.
 Test procedure so that the best move can be explored first.
Game playing is a popular application of artificial intelligence that involves the development
of computer programs to play games, such as chess, checkers, or Go. The goal of game playing
in artificial intelligence is to develop algorithms that can learn how to play games and make
decisions that will lead to winning outcomes.
1. One of the earliest examples of successful game-playing AI is the chess program Deep
Blue, developed by IBM, which defeated the world champion Garry Kasparov in 1997.
Since then, AI has been applied to a wide range of games, including two-player games,
multiplayer games, and video games.
There are two main approaches to game playing in AI, rule-based systems and machine
learning-based systems.
1. Rule-based systems use a set of fixed rules to play the game.
2. Machine learning-based systems use algorithms to learn from experience and make
decisions based on that experience.
In recent years, machine learning-based systems have become increasingly popular, as they are
able to learn from experience and improve over time, making them well-suited for complex
games such as Go. For example, AlphaGo, developed by DeepMind, was the first machine
learning-based system to defeat a world champion in the game of Go.
Game playing in AI is an active area of research and has many practical applications, including
game development, education, and military training. By simulating game-playing scenarios, AI
algorithms can be used to develop more effective decision-making systems for real-world
applications.
Figure 1: Before backing-up of values
Figure 2: After backing-up of values We assume that PLAYER1 will start the game.
4 levels are generated. The value of nodes H, I, J, K, L, M, N, and O is provided by the

STATICEVALUATION function. Level 3 is the maximizing level, so all nodes of level 3 will
take maximum values of their children. Level 2 is minimizing level, so all its nodes will take
minimum values of their children. This process continues. The value of A is 23. That means A
should choose C to move to win.
Advantages of Game Playing in Artificial Intelligence:
1. Advancement of AI: the creation of new algorithms and techniques that can be applied
to other areas of AI.
2. Education and training: Game playing can be used to teach AI techniques and
algorithms to students and professionals, as well as to provide training for military and
emergency response personnel.
3. Research: provides an opportunity to study and develop new techniques for decision-
making and problem-solving.
4. Real-world applications: The techniques and algorithms developed for game playing
can be applied to real-world applications, such as robotics, autonomous systems, and
decision support systems.
Disadvantages of Game Playing in Artificial Intelligence:
1. Limited scope: 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
Adversarial search
Adversarial search is a fundamental concept in artificial intelligence, and its importance cannot
be overstated. It plays a pivotal role in two major domains:
1. Game-Playing: Adversarial search is a cornerstone in game-playing AI.

Whether it's chess, checkers, Go, or more modern video games, AI agents use
adversarial search to evaluate and select the best moves in a competitive
environment.
2. Decision-Making: Beyond the realm of games, adversarial search is applicable
in various decision-making processes. It's used in situations where multiple
agents have conflicting goals and must strategize to reach the best possible
outcome.
This concept can be extended to economics, robotics, and even military strategy,
where intelligent agents must plan and make decisions while considering the
actions and objectives of adversaries. Adversarial search empowers AI to
navigate complex, uncertain, and often adversarial environments effectively.
Define Adversarial Search in Artificial Intelligence
 Adversarial search in artificial intelligence is a problem-solving technique that focuses

on making decisions in competitive or adversarial scenarios.
 It is employed to find optimal strategies when multiple agents, often referred to as
players, have opposing or conflicting objectives.
 The adversarial search aims to determine the best course of action for a given player,
considering the possible moves and counter-moves of the opponent(s).
Role of Adversarial Search in AI:
1. Game-Playing
2. Decision-Making
Competitive Scenarios with Conflicting Goals:
Adversarial search is most relevant in competitive scenarios where multiple agents have
conflicting goals. In these scenarios:
 Each agent strives to maximize their own utility or minimize their own loss.
 The actions of one agent directly influence the outcomes and goals of other agents.
 The agents may have incomplete information about each other's strategies, leading to
strategic uncertainty.
The Concept of Game Trees:
They are graphical structures that depict the possible moves and counter-moves of each player
in a sequential manner. In a game tree:
 Each node represents a state of the game.
 Edges emanating from a node represent possible moves that a player can make.
 The tree branches out to represent various game states that result from different player
decisions.
By traversing and evaluating this tree, AI systems can systematically explore different game
scenarios, assess the consequences of different moves, and ultimately identify the optimal
strategy.
Mini-Max Algorithm in Artificial Intelligence
 Mini-max algorithm is a recursive or backtracking algorithm that is used in

decision-making and game theory. It provides an optimal move for the player
assuming that the opponent is also playing optimally.
 Mini-Max algorithm uses recursion to search through the game tree.
 The Min-Max algorithm is mostly used for game playing in AI. Such as Chess,
Checkers, tic-tac-toe, go, and various tow-players game. This Algorithm computes
the minimax decision for the current state.
 In this algorithm two players play the game, one is called MAX and the other is
called MIN.
 Both the players fight it as the opponent player gets the minimum benefit while they
get the maximum benefit.
 Both Players of the game are opponents of each other, where MAX will select the
maximized value and MIN will select the minimized value.
 The minimax algorithm performs a depth-first search algorithm for the exploration
of the complete game tree.
 The minimax algorithm proceeds down to the terminal node of the tree, then
backtracks the tree as the recursion.
Working of Min-Max Algorithm:
 The working of the minimax algorithm can be easily described using an example.
Below we have taken an example of game-tree which represents the two-player
game.
 In this example, there are two players one is called Maximizer and the other is called
Minimizer.
 The maximizer will try to get the Maximum possible score, and the Minimizer will
try to get the minimum possible score.
 This algorithm applies DFS, so in this game-tree, we have to go all the way through
the leaves to reach the terminal nodes.
 At the terminal node, the terminal values are given so we will compare those value
and backtrack the tree until the initial state occurs. The following are the main steps
involved in solving the two-player game tree:
Step-1: Suppose the maximizer takes the first turn which has the worst-case initial value =-
infinity, and the minimizer will take the next turn which has the worst-case initial value =
+infinity.
Step 2: initial value of the Maximizer and determine the higher nodes values. It will find the
maximum among the all.
Step 3: In the next step, it's a turn for the minimizer, so it will compare all node values
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 node's value
and find the maximum value for the root node
 For node A max(4, -3)= 4

That was the complete workflow of the minimax two-player game.
Properties of Mini-Max algorithm:
 Complete- The Min-Max algorithm is Complete. It will find a solution (if exists),
in the finite search tree.
 Optimal- The Min-Max algorithm is optimal if both opponents are playing
optimally.
 Time complexity- As it performs DFS for the game tree, the time complexity of
the Min-Max algorithm is O(bm), where b is the branching factor of the game tree,
and m is the maximum depth of the tree.
 Space Complexity- The space complexity of the Mini-max algorithm is also
similar to DFS which is O(bm).
Alpha-Beta Pruning
 Alpha-beta pruning is a modified version of the minimax algorithm. It is an

optimization technique for the minimax algorithm.
 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 parameters Alpha and beta for future expansion, so it
is called alpha-beta pruning. It is also called as Alpha-Beta Algorithm.
 Alpha-beta pruning can be applied at any depth of a tree, and sometimes it not only
prunes the tree leaves but also the entire sub-tree.
The two-parameter can be defined as:
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 -∞.
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 +∞.
Condition for Alpha-beta pruning:
The main condition required for alpha-beta pruning are:
1. α>=β
Key points about alpha-beta pruning:
 The Max player will only update the value of alpha.

 The Min player will only update the value of beta.
 While backtracking the tree, the node values will be passed to upper nodes instead
of values of alpha and beta.
 We will only pass the alpha, and beta values to the child nodes.
Working of Alpha-Beta Pruning:
Let's take an example of a two-player search tree to understand the workings of Alpha-beta
pruning
Step 1: At the first step the, Max player will start first move from node A where α= -∞ and β=
+∞, these values of alpha and beta are passed down to node B where again α= -∞ and β= +∞,
and Node B passes the same value to its child D.
Step 2:
Step 3:
Step 4:
Step 5:
Final output:
Rules to find good ordering:
Following are some rules to find good ordering in alpha-beta pruning:
 Occur the best move from the shallowest node.

 Order the nodes in the tree such that the best nodes are checked first.
 Use domain knowledge while finding the best move. Ex: for Chess, try order:
captures first, then threats, then forward moves, backward moves.
 We can bookkeep the states, as there is a possibility that states may repeat.
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 moves to the states resulting in
every possible response by MIN. Then MAX’s moves in the states result from every
possible response by MIN to those moves, and so on.
 simple recursive computation of the minimax values of each successor state.

As the recursion unwinds
 it progresses 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).
 the space complexity is O(bm), while for an algorithm that generates actions
one at a time, the space complexity is O(m)
Evaluation Function
An evaluation function, also known as a heuristic evaluation function or static evaluation

function, is a function used by game-playing computer programs to estimate the value or
goodness of a position (usually at a leaf or terminal node) in a game tree.
 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 the 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 turns or a low value for the board if the minimizer
turns.
 For this scenario let us consider X as the maximizer and O as the minimizer.
Let us build our evaluation function:
 function for the game Tic-Tac-Toe is discussed.
For this scenario let us consider X as the maximizer and O as the minimizer.
Let us build our evaluation function :
 If O wins on the board we give it a negative value of -10.

 If X wins on the board we give it a positive value of +10.
 If no one has won or the game results in a draw then we give a value of +0.
TimeComplexity: O(max(row,col))
Auxiliary Space: O(1)
UNIT - III
Representation of Knowledge: Knowledge representation issues, predicate logic- logic programming,

semantic nets- frames and inheritance, constraint propagation, representing knowledge using rules,
and rules-based deduction systems. Reasoning under uncertainty, review of probability, Bayes’
probabilistic interferences, and dempstershafer theory.
Knowledge Representation Issues:

The process of encoding information in a way that an AI system can comprehend and use is
known as knowledge representation in AI. It entails converting information and ideas from the
real world into a form that computers can use, analyze, and make conclusions from. Thanks to
this representation, AI systems may imitate human cognitive functions including problem-
solving, decision-making, and language comprehension.
Types of Knowledge in AI
1. Declarative Knowledge:
 Declarative knowledge is the ability to understand something.
 It contains ideas, facts, and objects.
 Declarative sentences are used to express descriptive knowledge, which is also known
as descriptive knowledge.
 It is less complicated than procedural programming
 Games are modeled as a Search problem and a heuristic evaluation function, which
are the two primary variables that aid in the modeling and solving of games in AI.
2. Procedural Knowledge:
 It's sometimes referred to as "imperative knowledge."
 Procedure knowledge is a form of knowledge that entails knowing how to do
something.
 It can be used to complete any assignment.
 It has rules, plans, procedures, and agendas, among other things.
 The use of procedural knowledge is contingent on the job at hand.
3. Meta-knowledge:
Meta-knowledge is information about other sorts of knowledge.
4. Heuristic understanding:
 Heuristic knowledge is the sum of the knowledge of a group of specialists in a certain
field or subject.
 Heuristic knowledge refers to rules of thumb that are based on prior experiences, and
awareness of methodologies, and are likely to work but not guarantee
5. Structural knowledge:
 Basic problem-solving knowledge is structural knowledge.
 It describes the connections between distinct concepts such as kind, part of, and
grouping.
 It is a term that describes the relationship between two or more concepts or objects.
AI knowledge cycle:
To show intelligent behavior, an artificial intelligence system must have the following
components:
 Perception
 Learning
 Knowledge Representation and Reasoning
 Planning
 Execution
 Perception is a component of an AI system that allows it to gather information from

its surroundings. It can be in the form of visual, aural, or other sensory input.
 The main components of the entire cycle are knowledge representation and reasoning.
 These two components are independent of one another, but they are also linked.
 Analysis of knowledge representation and reasoning is required for planning and
implementation.
Challenges in representing knowledge
 Scalability
 Information that is Uncertain or Incomplete
 Knowledge Fusion and Integration
 Explainability & Interpretability
predicate logic
First-order logic (FOL), also known as predicate logic or first-order predicate calculus, is a
powerful framework used in various fields such as mathematics, philosophy, linguistics, and
computer science. In artificial intelligence (AI), FOL plays a crucial role in knowledge
representation, automated reasoning, and natural language processing.
The key components of FOL include constants, variables, predicates, functions, quantifiers,
and logical connectives.
1. Constants: Constants represent specific objects within the domain of discourse. For
example, in a given domain, Alice, 2, and NewYork could be constants.
2. Variables: Variables stand for unspecified objects in the domain. Commonly used
symbols for variables include x, y, and z.
3. Predicates: Predicates are functions that return true or false, representing properties
of objects or relationships between them. For example, Likes(Alice, Bob) indicates
that Alice likes Bob, and GreaterThan(x, 2) means that x is greater than 2.
4. Functions: Functions map objects to other objects. For instance, MotherOf(x) might
denote the mother of x.
5. Quantifiers: Quantifiers specify the scope of variables. The two main quantifiers are:
 Universal Quantifier (∀): Indicates that a predicate applies to all elements in
the domain.
o For example, ∀x (Person(x) → Mortal(x)) means “All persons are
mortal.”
 Existential Quantifier (∃): Indicates that there is at least one element in the
domain for which the predicate holds.
o For example, ∃x (Person(x) ∧ Likes(x, IceCream)) means “There
exists a person who likes ice cream.”
6. Logical Connectives:
Example: Using First-Order Logic for Reasoning

To illustrate the use of FOL in reasoning, consider the following knowledge base:
1. ∀x (Cat(x) → Mammal(x)) (All cats are mammals)
2. ∀x (Mammal(x) → Animal(x)) (All mammals are animals)
3. Cat(Tom) (Tom is a cat)
From these statements, we can infer:
1. Mammal(Tom) (Since Tom is a cat, and all cats are mammals)
2. Animal(Tom) (Since Tom is a mammal, and all mammals are animals)
Applications of First-Order Logic in AI
1. Knowledge Representation
2. Automated Theorem Proving
3. Natural Language Processing (NLP)
4. Expert Systems
5. Semantic Web
Example for FOL:-
Marcus was a man.
Marcus was a Pompeian.
All Pompeians were Romans.
Caesar was a ruler.
All Romans were either loyal to Caesar or hated him.
Everyone is loyal to someone.
People only try to assassinate rulers they are not loyal to.
Marcus tried to assassinate Caesar.
All men are people
Semantic Nets- Frames And Inheritance
Semantic Network:
 Formalism for representing information about objects, people, concepts
 and specific relationships between them.
 The syntax of the semantic net is simple. It is a network of labeled nodes and links.
– It’s a directed graph with nodes corresponding to concepts, facts,
objects, etc., and
– arcs showing a relation or association between two concepts
 The commonly used links in the semantic net are of the following types.
 – is _a subclass of entity (e.g., child hospital is a subclass of hospital)
 – inst particular instance of a class (e.g., India is an instance of country)
 prop property link (e.g., property of dog is ‘bark)
Representation of Knowledge in Sem Net
“Every human, animal and bird is living thing who breathes and eat. All birds
can fly. All man and woman are humans who have two legs. Cat is an animal
and has a fur. All animals have skin and can move. Giraffe is an animal who is
tall and has long legs. Parrot is a bird and is green in color”.
Representation in Predicate Logic:-

Inheritance
 The inheritance mechanism allows knowledge to be stored at the highest
possible level of abstraction which reduces the size of knowledge base.
– It facilitates the inferencing of information associated with semantic
nets.
– It is a natural tool for representing taxonomically structured information
and ensures that all the members and sub-concepts of a concept share
common properties.
– It also helps us to maintain the consistency of the knowledge base by
adding new concepts and members of existing ones.
 Properties attached to a particular object (class) are to be inherited by all
subclasses and members of that class.
Property Inheritance Algorithm
Input: Object, and property to be found from Semantic Net;
Output: Yes, if the object has the desired property else return false;
Procedure: Find an object in the semantic net; Found = false;
While {(object ≠ root) OR Found }

DO
{
If there is a property attribute attached to an object then
{ Found = true; Report ‘Yes’}
Else
object=inst(object, class) OR isa(object,class)
};
If Found = False then report ‘No’; Stop
Isa facts Instance facts Property facts
isa(living_thing,nil). inst(john,man). prop(breathe,living_thing).
isa(human,living_thing). inst(giraffe,animal).
prop(eat,living_thing).
isa(animals,living_thing). inst(parrot, bird)
prop(two_legs,human).
isa(birds,living_thing).
prop(skin,animal).
isa(man,human).
prop(move,animal).
isa(woman,human).
prop(fur, bird).
isa(cat, animal).
prop(tall,giraffe).
prop(long_legs,giraffe).
prop(tall,animal).
prop(green, parrot).
Knowledge Representation using Frames

● Frames are a more structured form of packaging knowledge,
– used for representing objects, concepts, etc.
● Frames are organized into hierarchies or networks of frames.
● Lower-level frames can inherit information from upper-level frames in the network.
● Nodes are connected using links viz., –
– ako / subc (links two class frames, one of which is a subclass of the other e.g.,
science_faculty class is ako of faculty class),
– is_a / inst ( connects a particular instance of a class frame e.g., Renuka is_a
science_faculty)
– a_part_of (connects two class frames one of which is contained in another e.g., faculty
class is_part_of department class).
Property link of semantic net is replaced by SLOT fields.
● A frame may have any number of slots needed for describing the object. e.g.,
– faculty frame may have a name, age, address, qualification, etc as slot names.
● Each frame includes two basic elements: slots and facets.
– Each slot may contain one or more facets (called fillers) which may take many
forms such as
– value (value of the slot),

– default (default value of the slot),
– range (indicates the range of integer or enumerated values, a slot can have),
– demons (procedural attachments such as if_needed, if_deleted, if_added etc.) and
– other (may contain rules, other frames, semantic net, or any type of other information).
Description of frame work

Description of Frames
• Each frame represents either a class or an instance.
• Class frame represents a general concept whereas instance frame represents a specific
occurrence of the class instance.
• Class frames generally have default values that can be redefined at lower levels.
• If the class frame has an actual value facet then decedent frames can not modify that
value.
• Value remains unchanged for subclasses and instances.
Inheritance in Frames
• Suppose we want to know the nationality or phone of an instance-frame frame13 of
Renuka.
• This information is not given in this frame.
• Search will start from frame13 in an upward direction till we get our answer or have
reached the root frame.
• The first argument is the frame's name and the second argument is a list of slot - facet
pairs.
Constraint propagation
Constraint propagation is a fundamental concept in constraint satisfaction problems
(CSPs). A CSP involves variables that must be assigned values from a given domain while
satisfying a set of constraints. Constraint propagation aims to simplify these problems by
reducing the domains of variables, thereby making the search for solutions more efficient.
Key Concepts
Variables: Elements that need to be assigned values.
Domains: Possible values that can be assigned to the variables.
Constraints: Rules that define permissible combinations of values for the variables.
How Constraint Propagation Works

Constraint propagation works by iteratively narrowing down the domains of variables
based on the constraints. This process continues until no more values can be eliminated
from any domain. The primary goal is to reduce the search space and make it easier to find
a solution.
Steps in Constraint Propagation

Initialization: Start with the initial domains of all variables.
Propagation: Apply constraints to reduce the domains of variables.
Iteration: Repeat the propagation step until a stable state is reached, where no further
reduction is possible.
Example
Consider a simple CSP with two variables, X and Y, each with domains {1, 2, 3}, and a
constraint X ≠ Y. Constraint propagation will iteratively reduce the domains as follows:
If X is assigned 1, then Y cannot be 1, so Y's domain becomes {2, 3}.
If Y is then assigned 2, X cannot be 2, so X's domain is reduced to {1, 3}.
This process continues until a stable state is reached.
Applications of Constraint Propagation

Constraint propagation is widely used in various AI applications. Some notable areas
include:
Scheduling
In scheduling problems, tasks must be assigned to time slots without conflicts. Constraint
propagation helps by reducing the possible time slots for each task based on constraints like
availability and dependencies.
Planning
AI planning involves creating a sequence of actions to achieve a goal. Constraint
propagation simplifies the planning process by reducing the possible actions at each step,
ensuring that the resulting plan satisfies all constraints.
Resource Allocation
In resource allocation problems, resources must be assigned to tasks in a way that meets all
constraints, such as capacity limits and priority rules. Constraint propagation helps by
narrowing down the possible assignments, making the search for an optimal allocation
more efficient.
Reasoning under uncertainty

Agents may need to handle uncertainty due to partial observability, non-determinism, or a combination
of the two.
An agent may never know what state it’s in or where it will end up after a sequence of actions.
With this knowledge representation, we might write A→B, which means if A is true then B is true,
but consider a situation where we are not sure about whether A is true or not then we cannot express
this statement, this situation is called uncertainty.
Causes of uncertainty:
Following are some leading causes of uncertainty to occur in the real world.
1) Information occurred from unreliable sources.
2) Experimental Errors
3) Equipment fault
4) Temperature variation
5) Climate change.
Summarizing uncertainty
Let’s consider an example of uncertain reasoning, diagnosing a dental patient’s toothache. Let us try
to write rules for dental diagnosis using propositional logic.
Toothache ⇒ Cavity.
The problem is that this rule is wrong. Not all patients with toothaches have cavities; some
of them have gum disease, an abscess, or one of several other problems:
Toothache ⇒ Cavity ∨ GumProblem ∨ Abscess . . .
Unfortunately, to make the rule true, we have to add an almost unlimited list of
possible problems. We could try turning the rule into a causal rule:
Cavity ⇒ Toothache
The agent’s knowledge can provide only a degree of belief (a representation of the set of all possible
world states) in the relevant sentences.
Our main tool for dealing with degrees of belief is probability theory. The ontological commitments
of logic and probability theory are the same.
Probability summarizes the uncertainty that comes from our laziness and ignorance, thereby solving
the qualification problem.
Uncertainty and rational (expressible) decisions
To make choices, an agent must first have preferences between the different possible outcomes of the
various plans.
An outcome is a completely specified state.
Utility theory says that every state has a degree of usefulness, or utility, to an agent and that the agent
will prefer states with higher utility. The term utility is used here in the sense of “the quality of being
useful”.
Preferences, as expressed by utilities, are combined with probabilities in the general theory of rational
decisions called decision theory.
Decision theory = probability theory + utility theory

The fundamental idea of decision theory is that an agent is rational if and only if it chooses the action
that yields the highest expected utility, averaged over all the possible outcomes of the action. This is
called the principle of maximum expected utility (MEU).
Review Of Probability
Probabilistic reasoning is a way of knowledge representation where we apply the concept of probability
to indicate the uncertainty in knowledge.
In probabilistic reasoning, we combine probability theory with logic to handle the uncertainty.
We use probability in probabilistic reasoning because it provides a way to handle the uncertainty.
In the real world, there are lots of scenarios, where the certainty of something is not confirmed, such
as "It will rain today," "behavior of someone for some situations," or "A match between two teams or
two players." These are probable sentences for which we can assume that it will happen but are not sure
about it, so here we use probabilistic reasoning.
Need for probabilistic reasoning in AI:
When there are unpredictable outcomes.
When specifications or possibilities of predicates become too large to handle.
When an unknown error occurs during an experiment.
In probabilistic reasoning, there are two ways to solve problems with uncertain knowledge:
1) Bayes' rule
2) Bayesian Statistics
Common terms used in probabilistic reasoning:
Probability: Probability can be defined as a chance that an uncertain event will occur. It is the
numerical measure of the likelihood that an event will occur. The value of probability always remains
between 0 and 1 that represent ideal uncertainties.
0 ≤ P(A) ≤ 1, where P(A) is the probability of an event A.
P(A) = 0, indicates total uncertainty in an event A.
P(A) =1, indicates total certainty in an event A.
How we can work out the likelihood of two events occurring together given
their base and conditional probabilities?
P(a | b) = P(a b)^/ P(b)......1
P(b | a) =P(a ^b)/ P(a)......2
P(a ^b) = P(a | b)P(b) =P(b | a)P(a).........3
So in our toy example 1:
P(toothache ^ cavity) = P(toothache | cavity)P(cavity)
= P(cavity | toothache)P(toothache)
 Random variables: Variables in probability theory, their names begin with an uppercase letter.
E.g. Total; Die1.
 By convention, propositions of the form A=true are abbreviated simply as a, while A = false
is abbreviated as ¬a.
Probability distribution: When we assume a predefined ordering on the domain of a random
variable
Eg. P(Wether = sunny) = 0.6, P(Wether = rain) = 0.1, P(Weather = cloudy) = 0.29, P(Weather
= snow) = 0.01. As an abbreviation: P(Weather) = . .
Probability density function (pdfs):
Joint probability distribution: It is the notation for the distribution of multiple variables. e.g.
P(Weather, Cavity
Full joint probability distribution: The joint distribution for all of the random variables
e.g. if the variables are Cavity, Toothache, and Weather, then the full joint distribution is given
by P(Cavity, Toothache, Weather).
Bayes' theorem:
Bayes' theorem is also known as Bayes' rule, Bayes' law, or Bayesian reasoning, which
determines the probability of an event with uncertain knowledge.
In probability theory, it relates the conditional probability and marginal probabilities of two
random events.
Bayes' theorem was named after the British mathematician Thomas Bayes. The Bayesian
inference is an application of Bayes' theorem, which is fundamental to Bayesian statistics.
It is a way to calculate the value of P(B|A) with the knowledge of P(A|B).
Bayes' theorem allows updating the probability prediction of an event by observing new
information of the real world.
Example: If cancer corresponds to one's age then by using Bayes' theorem, we can determine
the probability of cancer more accurately with the help of age.
Bayes' theorem can be derived using product rule and conditional probability of event A with
known event B:
As from product rule we can write:
1. P(A ⋀ B)= P(A|B) P(B) or
Similarly, the probability of event B with known event A:
1. P(A ⋀ B)= P(B|A) P(A)
Equating right-hand side of both equations, we will get:
The above equation (a) is called Bayes' rule or Bayes' theorem. This equation is the basis of
most modern AI systems for probabilistic inference.
It shows the simple relationship between joint and conditional probabilities. Here,
P(A|B) is known as posterior
P(B|A) is called the likelihood
P(A) is called the prior probability
P(B) is called marginal probability, pure probability of evidence.
In equation (a), in general, we can write P (B) = P(A)*P(B|Ai), hence the Bayes' rule can be
written as:
Where A1, A2, A3,........, An is a set of mutually exclusive and exhaustive events.
Example-1:
Question: what is the probability that a patient has diseases meningitis with a stiff neck?
Given Data:
A doctor is aware that disease meningitis causes a patient to have a stiff neck, and it occurs
80% of the time. He is also aware of some more facts, which are given as follows:
o The Known probability that a patient has meningitis disease is 1/30,000.
o The Known probability that a patient has a stiff neck is 2%.
Let a be the proposition that patient has stiff neck and b be the proposition that patient has
meningitis. , so we can calculate the following as:
P(a|b) = 0.8
P(b) = 1/30000
P(a)= .02
Hence, we can assume that 1 patient out of 750 patients has meningitis disease with a stiff neck.
•
LOGIC CONCEPTS: First-order logic, Inference In First-Order Logic, Propositional Vs.
First-order inference, Unification & Lifts Forward Chaining, Backward Chaining, Resolution,
Learning From Observation Inductive Learning, Decision Trees, Explanation Based Learning,
Statistical Learning Methods, and Reinforcement Learning.
Inference In First-Order Logic

Inference In First-Order Logic Is Used To Deduce New Facts Or Sentences From Existing
Sentences.
Substitution is a fundamental operation performed on terms and formulas. It occurs in all
inference systems in first-order logic and in the presence of quantifiers in FOL. If we
write F[a/x], it refers to substituting a constant "a" in place of variable "x".
FOL INFERENCE RULES FOR QUANTIFIER:
O Universal Generalization (Or )Universal Instantiation
O Existential Instantiation (Or) Existential Introduction
Universal Generalization (Or )Universal Instantiation:-
we can infer any sentence obtained by substituting a ground term for the variable.
– Can Be Applied Several Times To Add New Sentences
– The New Kb Is Logically Equivalent To The Old
● Every Instantiation Of A Universally Quantified Sentence Is Entailed By
It: ∀V Α /Subst({V/G}, Α)
For Any Variable V And Ground Term G ●
E.G., ∀X King(X) ∧ Greedy(X) ⇒ Evil(X) Yields
King(John) ∧ Greedy(John) ⇒ Evil(John)
King(Richard) ∧ Greedy(Richard) ⇒ Evil(Richard)
King(F Ather(John)) ∧ Greedy(F Ather(John)) ⇒ Evil(F Ather(John))
Existential Instantiation (Or) Existential Introduction
– Can Be Applied Once To Replace The Existential Sentence
– The New Kb Is Not Equivalent To The Old – But Is Satisfiable Iff The Old Kb Was Satisfiable
For Any Sentence Α, Variable V, And Constant Symbol K That Does Not Appear Elsewhere In
The Knowledge Base: ∃ V Α /Subst({V/K}, Α)
E.G., ∃ X Crown(X) ∧ Onhead(X, John) Yields
Crown(C1) ∧ Onhead(C1, John)
Provided C1 Is A New Constant Symbol, Called A Skolem Constant
Propositional Vs. First-order inference
 Propositional Logic: Limited to simple true/false statements without the ability to
express relationships between objects. Suitable for scenarios where the complexity of
relationships is low.
 First-order logic: is more expressive and capable of representing relationships,
properties of objects, and quantification. Suitable for complex scenarios involving
multiple objects and relationships.
Propositional
Feature Logic First-Order Logic
Basic Unit Propositions Predicates, constants, variables
Limited to
Expressive, can represent
Expressiveness true/false
relationships and properties
statements
Quantifiers None Universal (∀) and Existential (∃)
Combines
Syntax propositions using Uses predicates and quantifiers
logical connectives
Semantics Truth tables Interpretation of a domain
Simple problems
Complex problems (e.g., AI
Use Cases (e.g., circuit design,
reasoning, ontology modeling)
rule-based systems)
Example P→Q ∀x∃y(Likes(x,y))∀x∃y(Likes(x,y))
Unification
 Unification is finding a substitute that makes two separate logical atomic expressions
identical. The substitution process is necessary for unification.
 It accepts two literals as input and uses substitution to make them identical.
 Example: P(x, y), and P(a, f(z)).
 P(x,y).........(i)
P(a,f(z)).........(ii)
Substitute x with a, and y with f(z) in the first expression, and it will be represented
as a/x and f(z)/y.
The first expression will be identical to the second with both replacements, and the
substitution set will be: [a/x, f(z)/y].
The following are some fundamental requirements for unification:
 Atoms or expressions with various predicate symbols can never be united.
 Both phrases must have the same number of arguments.
 If two comparable variables appear in the same expression, unification will fail.
Algorithm: Unify(Ψ1, Ψ2)
Step. 1: If Ψ1 or Ψ2 is a variable or constant, then:
a) If Ψ1 or Ψ2 are identical, then return NIL.
b) Else if Ψ1 is a variable,
a. then if Ψ1 occurs in Ψ2, then return FAIL
b. Else return { (Ψ2/ Ψ1)}.
c) Else if Ψ2 is a variable,
a. If Ψ2 occurs in Ψ1 then return FAILURE,
b. Else return {( Ψ1 / Ψ2)}.
d) Else return FAILURE.
Step.2: If the initial Predicate symbol in Ψ1 and Ψ2 are not the same, then return FAILURE.
Step. 3: IF Ψ1 and Ψ2 have a different number of arguments, then return FAILURE.
Step. 4: Set Substitution set(SUBST) to NIL.
Step. 5: For i=1 to the number of elements in Ψ1.
a) Call the Unify function with the ith element of Ψ1 and ith element of Ψ2, and put the result
into S.
b) If S = failure then returns Failure
c) If S ≠ NIL then do,
a. Apply S to the remainder of both L1 and L2.
b. SUBST= APPEND(S, SUBST).
Step 6: Return SUBST.
Lifts Forward Chaining, Backward Chaining

Facts Conversion into FOL:
o It is a crime for an American to sell weapons to hostile nations. (Let's say
p, q, and r are variables)
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p)
Step-1
Step-2
Step-3
Backward Chaining:
Backward chaining is also known as a backward deduction or backward reasoning method
when using an inference engine. A backward chaining algorithm is a form of reasoning, which
starts with the goal and works backward, chaining through rules to find known facts that
support the goal.
Properties of backward chaining:

o It is known as a top-down approach.
o Backward chaining is based on the modus ponens inference rule.
o In backward chaining, the goal is broken into sub-goals or sub-goals to prove the facts
true.
o It is called a goal-driven approach, as a list of goals decides which rules are selected
and used.
o The backward chaining algorithm is used in game theory, automated theorem proving
tools, inference engines, proof assistants, and various AI applications.
o The backward-chaining method mostly used a depth-first search strategy for proof.
Example:
American (p) ∧ weapon(q) ∧ sells (p, q, r) ∧ hostile(r) → Criminal(p) ...(1)
Step-1:
Step-2:
Step-3:
Step-4:
Step-5:
Resolution
Resolution is a theorem-proving technique that proceeds proofs by contradictions.
Resolution is used if there are various statements are given, and we need to prove a conclusion
of those statements.
Unification is a key concept in proofs by resolutions.
Resolution is a single inference rule that can efficiently operate on the conjunctive normal
form or clausal form.
a proposition formula which is always false is called a Contradictions
sa proposition formula which is always true is called a tautology
Steps for Resolution:
1. Conversion of facts into first-order logic.
2. Convert FOL statements into CNF
3. Negate the statement that needs to be proved (proof by contradiction)
4. Draw a resolution graph (unification).
Example:
1. John likes all kinds of food.
2. Apples and vegetables are food
3. Anything anyone eats and is not killed is food.
4. Anil eats peanuts and is still alive
5. Harry eats everything that Anil eats.
Prove by resolution that:
6. John likes peanuts.
Step-1: Conversion of Facts into FOL
In the first step, we will convert all the given statements into their first-order logic.
Step 2: Conversion of FOL into CNF

In First-order logic resolution, it is required to convert the FOL into CNF as CNF form makes
it easier for resolution proofs.
Advertisement
o Eliminate all implication (→) and rewrite
o ∀x ¬ food(x) V likes(John, x)
o food(Apple) Λ food(vegetables)
o ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)
o eats (Anil, Peanuts) Λ alive(Anil)
o ∀x ¬ eats(Anil, x) V eats(Harry, x)
o ∀x¬ [¬ killed(x) ] V alive(x)
o ∀x ¬ alive(x) V ¬ killed(x)
o likes(John, Peanuts).
o Move negation (¬)inwards and rewrite
o ∀x ∀y ¬ eats(x, y) V killed(x) V food(y)
o ∀x ¬ eats(Anil, x) V eats(Harry, x)
o ∀x ¬killed(x) ] V alive(x)
o ∀x ¬ alive(x) V ¬ killed(x)
o Rename variables or standardize variables
o ∀y ∀z ¬ eats(y, z) V killed(y) V food(z)
o ∀w¬ eats(Anil, w) V eats(Harry, w)
o ∀g ¬killed(g) ] V alive(g)
o ∀k ¬ alive(k) V ¬ killed(k)
o Eliminate existential instantiation quantifier by elimination.
Drop Universal quantifiers.
In this step, we will drop all universal quantifiers since all the statements are not
implicitly quantified so we don't need it.
o ¬ food(x) V likes(John, x)
o food(Apple)
o food(vegetables)
o ¬ eats(y, z) V killed(y) V food(z)
o eats (Anil, Peanuts)
o alive(Anil)
o ¬ eats(Anil, w) V eats(Harry, w)
o killed(g) V alive(g)
o ¬ alive(k) V ¬ killed(k)
Step 3: Negate the statement to be proved
In this statement, we will apply negation to the conclusion statements, which will be written as
¬likes(John, Peanuts)
Step-4: Draw Resolution graph:
Learning From Observation Inductive Learning
Decision Trees
Decision Tree is a Supervised learning technique that can be used for both classification and
Regression problems, but mostly it is preferred for solving Classification problems.
It is a tree-structured classifier, where internal nodes represent the features of a dataset,
branches represent the decision rules and each leaf node represents the outcome.
The ID3 algorithm builds decision trees using a top-down greedy search approach through
the space of possible branches with no backtracking. A greedy algorithm, as the name suggests,
always makes the choice that seems to be the best at that moment.
Steps in ID3 algorithm:
1. It begins with the original set S as the root node.
2. On each iteration of the algorithm, it iterates through the very unused attribute of the
set S and calculates the Entropy(H) and Information gain(IG) of this attribute.
3. It then selects the attribute that has the smallest Entropy or Largest Information gain.
4. The set S is then split by the selected attribute to produce a subset of the data.
5. The algorithm continues to recur on each subset, considering only attributes never
selected before.
So, to solve such problems there is a technique which is called as Attribute selection measure
or ASM.
By this measurement, we can easily select the best attribute for the nodes of the tree. There are
two popular techniques for ASM, which are:
1. Information Gain:
o Information gain is the measurement of changes in entropy after the segmentation of a
dataset based on an attribute.
o It calculates how much information a feature provides us about a class.
o A decision tree algorithm always tries to maximize the value of information gain, and
a node/attribute having the highest information gain is split first. It can be calculated
using the below formula:
o Information Gain= Entropy(S)- [(Weighted Avg) *Entropy(each feature) ]
(or)
Information Gain= Entropy(S)- [p(s/w=yes) *Entropy(s/w=yes)-p(s/w=no) *Entropy(s/w=no) ]
Note: it is applied for both weak and strong
2. Entropy: Entropy is a metric to measure the impurity in a given attribute. It specifies
randomness in data. Entropy can be calculated as:
o Entropy(s)= -P(yes)log2 P(yes)- P(no) log2 P(no)

Explanation Based Learning
Reinforcement learning
Reinforcement Learning (RL) is a branch of machine learning focused on making decisions to

maximize cumulative rewards in a given situation.
Unlike supervised learning, which relies on a training dataset with predefined answers, RL
involves learning through experience.
In RL, an agent learns to achieve a goal in an uncertain, potentially complex environment by
performing actions and receiving feedback through rewards or penalties.
Key Concepts of Reinforcement Learning
 Agent: The learner or decision-maker.
 Environment: Everything the agent interacts with.
 State: A specific situation in which the agent finds itself.
 Action: All possible moves the agent can make.
 Reward: Feedback from the environment based on the action taken.
 Policy: A strategy used by the agent to determine the next action based on the current
state.
 Reward Function: A function that provides a scalar feedback signal based on the state
and action.
 Value Function: A function that estimates the expected cumulative reward from a
given state.
 Model of the Environment: A representation of the environment that helps in planning
by predicting future states and rewards.
Example: Navigating a Maze
The problem is as follows: We have an agent and a reward, with many hurdles in between. The
agent is supposed to find the best possible path to reach the reward. The following problem
explains the problem more easily.
The above image shows the robot, diamond, and fire. The goal of the robot is to get the reward
that is the diamond and avoid the hurdles that are fired. The robot learns by trying all the
possible paths and then choosing the path that rewards him with the least hurdles. Each right
step will give the robot a reward and each wrong step will subtract the reward of the robot. The
total reward will be calculated when it reaches the final reward which is the diamond.
Main points in Reinforcement learning –

 Input: The input should be an initial state from which the model will start
 Output: There are many possible outputs as there are a variety of solutions to a
particular problem
 Training: The training is based upon the input, The model will return a state and the
user will decide to reward or punish the model based on its output.
 The model keeps continues to learn.
 The best solution is decided based on the maximum reward.
Learning: What is learning? Rote learning, learning by taking advice, learning in problem-solving, learning
from examples: Induction, explanation-based learning.
What is learning?
AI learning processes focus on processing a collection of input-output pairs for a specific function and
predicting the outputs for new inputs.
To understand the different types of AI learning models, we can use two of the main elements of human
learning processes: knowledge and feedback.
From the knowledge perspective, learning models can be classified based on the representation of input and
output data points.
In terms of feedback, AI learning models can be classified based on the interactions with the outside
environment, users, and other external factors.
AI Learning Models: Knowledge-Based Classification
AI learning models can be classified into two main types: inductive and deductive.
Inductive Learning: This type of AI learning model is based on inferring a general rule from datasets of
input-output pairs.
Deductive Learning: This type of AI learning technique starts with a series of rules and infers new rules
that are more efficient in the context of a specific AI algorithm. Explanation-Based Learning(EBL) EBL
extracts general rules from examples by “generalizing” the explanation.
AI Learning Models: Feedback-Based Classification
Unsupervised Learning: Unsupervised models focus on learning a pattern in the input data without any
external feedback. Clustering is a classic example of an unsupervised learning models.
Supervised Learning: Supervised learning models use external feedback to learning functions that map
inputs to output observations. In those models, the external environment acts as a “teacher” of the AI
algorithms.
Semi-supervised Learning: Semi-supervised learning uses a set of curated, labeled data and tries to infer
new labels/attributes on new data sets. Semi-supervised learning models are a solid middle ground between
supervised and unsupervised models.
Reinforcement Learning: Reinforcement learning models use opposite dynamics such as rewards and
punishment to “reinforce” different types of knowledge. This type of learning technique is becoming really
popular in modern AI solutions.

Unit-1 Merged

Uploaded by

Document Informationclick to expand document information

Document Informationclick to expand document information

Copyright:

Available Formats

Unit-1 Merged

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit-1 Merged

Uploaded by

Copyright:

Available Formats

Introduction To Artificial Intelligence CAI

 Example:- 1965 - Weizenbaum's

↳ Used Doman Knowledge.

 1970's - MYCIN - Blood Infections.

 Knowledge representation to store what it knows or hears;

 We need to get inside the actual workings of human minds.

 If the program’s input-output behavior matches corresponding human behavior, that is

3. Systems that behave like humans

The Foundations of Artificial Intelligence

 Mathematical concepts give the real solution of hypothetical or virtual problems.

 Neuroscience takes advantage of AI techniques and the increasing processing power

 Artificial intelligence (AI), sometimes known as machine intelligence, refers to the

 Specific applications of AI include expert systems, natural language processing, and

 An Artificial Intelligence engineer works with different algorithms, neural networks,

 By tradition, the term Computational Linguistics refers to written language, whereas

1. Learning And Adaptation

Agents and Environments

 An agent is something that perceives and acts in an environment.

4) IR Sensor (Infrared Sensor)

 An actuator is a device that converts electrical signals into physical events or

 The performance measure evaluates the behavior of the agent in an environment.

 The agent program implements the agent function.

 The designs vary in efficiency, compactness, and flexibility.

Percept Square Action

[A, clean] Right

[A, Dirty] Suck

[B, Clean] Left

[A, clean] [A, dirty] Suck

Good Behavior: The Concept of Rationality

 than doing the wrong thing.

 An environment is the surroundings of the agent.

 The performance measure evaluates the behavior of the agent in an environment.

 A task environment specification includes the performance measure, the external

2) The agent’s prior knowledge of the environment.

3) The actions that the agent can perform.

4) The agent’s percept sequence to date.

 Rationality is NOT the same as perfection. Rationality maximizes expected

 A rational agent should be autonomous—it should learn.

The Nature of the Environment

 The performance measure evaluates the behavior of the agent in an environment.

PEAS for an automated taxi driver

Properties of Task Environment

Known vs. unknown:

1) Architecture: Architecture is machinery that an AI agent executes on.

2) Agent Function: The agent function is used to map a percept to an action.

3) Agent program: An agent program is an implementation of an agent function.

 There are four kinds of agent programs.

1) Simple reflex agents

2) Model-based reflex agents

The following is the simple reflex agent function.

function SIMPLE-REFLEX-AGENT(percept ) returns an action

 The INTERPRET-INPUT function generates an abstracted description of the current

2. Model-based reflex agents

 The following is the model-based reflex agent function.

function MODEL-BASED-REFLEX-AGENT(percept ) returns an action 

The following is the schematic diagram of the goal-based agent.

PROBLEM-SOLVING APPROACH IN ARTIFICIAL INTELLIGENCE PROBLEMS