Unit 2

lOMoARcPSD|45814754
Unit II Full notes - Artifical intelligence
Artificial Intelligence (Visvesvaraya Technological University)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university

Downloaded by Sriram Kuriseti ([email protected])
lOMoARcPSD|45814754
UNIT – II: Problem Solving by Search-II and Propositional Logic

Adversarial Search: Games, Optimal Decisions in Games, Alpha–Beta Pruning, Imperfect Real-Time
Decisions.
Constraint Satisfaction Problems: Defining Constraint Satisfaction Problems, Constraint Propagation,
Backtracking Search for CSPs, Local Search for CSPs, The Structure of Problems.
Propositional Logic: Knowledge-Based Agents, The Wumpus World, Logic, Propositional Logic,
Propositional Theorem Proving: Inference and proofs, Proof by resolution, Horn clauses and definite
clauses, Forward and backward chaining, Effective Propositional Model Checking, Agents Based on
Propositional Logic.
PROBLEM SOLVING BY SEARCH-II
Multiple Agent Environments:
•Search strategies - single agent that aims to find the solution which often expressed in the
form of a sequence of actions.
• More than one agent leads to game theory. (Multiple agent)
• The environment with more than one agent is termed as multi-agent environment, in which each
agent is an opponent of other agent and playing against each other.
• Each agent needs to consider the action of other agent and effect of that action on their
performance.
• Searches in which two or more players with conflicting goals are trying to explore the
same search space for the solution are called adversarial searches, often known as Games.
1. ADVERSARIAL SEARCH:
• Adversarial search is a game-playing technique where the agents are surrounded by a

competitive environment.
• A conflicting goal is given to the agents (multiagent).
• These agents compete with one another and try to defeat one another in order to win the game.
• Such conflicting goals give rise to the adversarial search.
• Here, game-playing means discussing those games where human intelligence and logic
factor is used, excluding other factors such as luck factor.
• Tic-tac-toe, chess, checkers, etc., are such type of games where no luck factor works, only
mind works.
• Mathematically, this search is based on the concept of ‘Game Theory.’ According to game
theory, a game is played between two players. To complete the game, one has to win the game
and the other looses automatically.’
Factors In Game Theory:

lOMoARcPSD|45814754
Factors associated with the game theory are:

• Pruning: A technique which allows ignoring the unwanted portions of a search tree which
make no difference in its final result.
• Heuristic Evaluation Function: It allows approximating the cost value at each level of the
search tree, before reaching the goal node.
Types of games in Al:
Types of information:
• Perfect information: A game with the perfect information is that in which agents can look into
the complete board. Agents have all the information about the game, and they can see each other
moves also. Examples are Chess, Checkers, Go, etc.
• Imperfect information: If in a game agents do not have all information about the game and not
aware with what's going on, such type of games are called the game with imperfect information,
such as tic-tac-toe, Battleship, blind, Bridge, etc.
• Deterministic games: Deterministic games are those games which follow a strict pattern and set
of rules for the games, and there is no randomness associated with them. Examples are chess,
Checkers, Go, tic-tac-toe, etc.
• Non-deterministic games: Non-deterministic are those games which have various unpredictable
events and have a factor of chance or luck. Such games are also called as stochastic games.
Example: Backgammon, Monopoly, Poker, etc.
Zero sum theory:
• Zero-sum games are adversarial search which involves pure competition.

lOMoARcPSD|45814754
• In Zero-sum game each agent's gain or loss of utility is exactly balanced by the losses or gains
of utility of another agent.
• One player of the game try to maximize one single value, while another player tries to minimize
it.
• Each move by one player in the game is called as ply.
• Chess and tic-tac-toe are examples of a Zero-sum game.
i. Zero-sum game: Embedded thinking:
• The Zero-sum game involved embedded thinking in which one agent or player is trying to figure
out:
• What to do.
• How to decide the move
• Needs to think about his opponent as well
• The opponent also thinks what to do
• Each of the players is trying to find out the response of his opponent to their actions. This
requires embedded thinking or backward reasoning to solve the game problems in AI.
Formalization of the problem:
• Initial state: It specifies how the game is set up at the start.
• Player(s): It specifies which player has moved in the state space.
• Action(s): It returns the set of legal moves in state space.
• Result(s, a): It is the transition model, which specifies the result of moves in the state space.
• Terminal-Test(s): Terminal test is true if the game is over, else it is false at any case. The state
where the game ends is called terminal states.
• Utility(s, p): A utility function gives the final numeric value for a game that ends in terminal
states s for player p. It is also called payoff function. For Chess, the outcomes are a win, loss,
or draw and its payoff values are +1, 0, ½. And for tic-tac-toe, utility values are +1, -1, and 0.
2. GAME TREE:
• A game tree is a tree where nodes of the tree are the game states and Edges of the tree are the
moves by players. Game tree involves initial state, action's function, and result Function.
Example: Tic-Tac-Toe game tree
The following figure is showing part of the game-tree for tic-tac-toe game. Following are some key
points of the game:
• There are two players MAX and MIN.
• Players have an alternate turn and start with MAX.
• MAX maximizes the result of the game tree
• MIN minimizes the result.

lOMoARcPSD|45814754
• INITIAL STATE (S0): The top node in the game-tree represents the initial state in the tree
and shows all the possible choice to pick out one.
• PLAYER (s): There are two players, MAX and MIN. MAX begins the game by picking one
best move and place X in the empty square box.
• ACTIONS (s): Both the players can make moves in the empty boxes chance by chance.
• RESULT (s, a): The moves made by MIN and MAX will decide the outcome of the game.
• TERMINAL-TEST(s): When all the empty boxes will be filled, it will be the terminating
state of the game.
• UTILITY: At the end, we will get to know who wins: MAX or MIN, and accordingly, the
price will be given to them.
Hence adversarial Search for the minimax procedure works as follows:
• It aims to find the optimal strategy for MAX to win the game.
• It follows the approach of Depth-first search.

lOMoARcPSD|45814754
• In the game tree, optimal leaf node could appear at any depth of the tree.
• Propagate the minimax values up to the tree until the terminal node discovered.
3. TYPES OF ALGORITHMS IN ADVERSARIAL SEARCH:
• Adversarial search is a game-playing technique where the agents are surrounded by a

competitive environment.
• It is also obvious that the solution for the goal state will be an optimal solution because the
player will try to win the game with the shortest path and under limited time.
• There are following types of adversarial search:
i. Min-max Algorithm
ii. Alpha-beta Pruning.
i. MIN-MAX ALGORITHM:
 In artificial intelligence, minimax is a decision-making strategy under game theory, which is
used to minimize the losing chances in a game and to maximize the winning chances.
 This strategy is also known as ‘Min-max,’ ’MM,’ or ‘Saddle point.’
 Mini-max algorithm is a recursive or backtracking algorithm which is used in decision-
making and game theory. It provides an optimal move for the player assuming that opponent
is also playing optimally.
 Mini-Max algorithm uses recursion to search through the game-tree.
Example: Chess, Checkers, tic-tac-toe
 In this algorithm two players play the game; one is called MAX and other is called MIN.
 Both the players fight it as the opponent player gets the minimum benefit while they get the
maximum benefit.
o MIN: Decrease the chances of MAX to win the game.
o MAX: Increases his chances of winning the game.
 The minimax algorithm performs a depth-first search algorithm for
the exploration of the complete game tree.
 The minimax algorithm proceeds all the way down to the terminal node
of the tree, then backtrack the tree as the recursion.
Working of MIN-MAX Algorithm:
• MINIMAX algorithm is a backtracking algorithm where it backtracks to pick the best move out
of several choices.
• MINIMAX strategy follows the DFS (Depth-first search) concept.

lOMoARcPSD|45814754
• Here, we have two players MIN and MAX, and the game is played alternatively between them,
i.e., when MAX made a move, then the next turn is of MIN.
• It means the move made by MAX is fixed and, he cannot change it.
• The same concept is followed in DFS strategy, i.e., we follow the same path and cannot change
in the middle.
• That’s why in MINIMAX algorithm, instead of BFS, we follow DFS.
• Keep on generating the game tree/ search tree till a limit d.
• Compute the move using a heuristic function.
• Propagate the values from the leaf node till the current position following the minimax strategy.
• Make the best move from the choices.
Pseudo code for Minimax Algorithm:
Step1:
• In the first step, the algorithm generates the entire game-tree and applies the utility function to
get the utility values for the terminal states.
• In the below tree diagram, let's take A is the initial state of the tree.
• Suppose maximize takes first turn which has worst-case initial value =- infinity, and minimize
will take next turn which has worst-case initial value = +infinity.
Step 2:

lOMoARcPSD|45814754
• Now, first we find the utilities value for the Maximize, its initial value is -∞, so we will compare
each value in terminal state with initial value of Maximize and determines the higher nodes
values. It will find the maximum among the all.
• For node D max(-1,- -∞) => max(-1,4)= 4
• For Node E max(2, -∞) => max(2, 6)= 6
• For Node F max(-3, -∞) => max(-3,-5) = -3
• For node G max(0, -∞) = max(0, 7) = 7
Step 3:
• In the next step, it's a turn for minimize, so it will compare all nodes value with +∞ and will
find the 3rd layer node values.
• For node B= min(4,6) = 4
• For node C= min (-3, 7) = -3
Step 4:

lOMoARcPSD|45814754
• Now it's a turn for Maximize, and it will again choose the maximum of all nodes value and find
the maximum value for the root node.
• In this game tree, there are only 4 layers, hence we reach immediately to the root node, but in
real games, there will be more than 4 layers.
• For node A max(4, -3)= 4
Practical problem 2:
Solution:
Limitations of MIN-MAX Algorithm:

lOMoARcPSD|45814754
• The main drawback of the minimax algorithm is that it gets really slow for complex games such
as Chess, go, etc.
• This type of games has a huge branching factor, and the player has lots of choices to decide.
• This limitation of the minimax algorithm can be improved from alpha-beta pruning.
ii. ALPHA –BETA PURNING:
 A modified variant of the minimax method is alpha-beta pruning. It's a way for improving the
minimax algorithm.
 As a result, there is a technique known as Pruning that allows us to compute the correct minimax
choice without having to inspect each node of the game tree.
 It's named alpha-beta pruning because it involves two threshold parameters, Alpha and beta, for
future expansion.
 Alpha-beta pruning can be done at any depth in a tree, and it can sometimes prune the entire sub-
tree as well as the tree leaves.
Conditions of Alpha-Beta Pruning:
The main condition which required for alpha-beta pruning is:
α>=β
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, beta values to the child nodes.
Pseudo code for Alpha-Beta Pruning:

function minimax(node, depth, alpha, beta, maximizingPlayer) is
if depth ==0 or node is a terminal node then
return static evaluation of node
if MaximizingPlayer then // for Maximizer Player

maxEva= -infinity
for each child of node do
eva= minimax(child, depth-1, alpha, beta, False)
maxEva= max(maxEva, eva)
alpha= max(alpha, maxEva)
if beta<=alpha

lOMoARcPSD|45814754
break
return maxEva
else // for Minimizer player

minEva= +infinity
for each child of node do
eva= minimax(child, depth-1, alpha, beta, true)
minEva= min(minEva, eva)
beta= min(beta, eva)
if beta<=alpha
break
return minEva
Working of Alpha-Beta Pruning:

Step 1:
The Max player will begin by moving from node A, where = - and = +, and passing these values
of alpha and beta to node B, where again = - and = +, and Node B passing the same value to its
offspring D.
Step 2:
 The value of will be determined as Max's turn at Node D. The value of is compared to 2, then
3, and the value of at node D will be max (2, 3) = 3, and the node value will also be 3.
Step 3:
 The algorithm now returns to node B, where the value of will change as this is a turn of Min,
now = +, and will compare with the value of the available subsequent nodes, i.e., min (, 3) = 3,
so at node B now = -, and= 3.
 In the next step, algorithm traverse the next successor of Node B which is node E, and the values
of α= -∞, and β= 3 will also be passed.

lOMoARcPSD|45814754
Step 4:
Max will take its turn at node E, changing the value of alpha. The current value of alpha will be
compared to 5, resulting in max (-, 5) = 5, and at node E= 5 and= 3, where >=, the right successor
of E will be pruned, and the algorithm will not traverse it, and the value at node E will be 5.
Step 5:
 The method now goes backwards in the tree, from node B to node A.
 The value of alpha will be modified at node A, and the highest available value will be 3 as max
(-, 3) = 3, and = +.
 These two values will now transfer to A's right successor, Node C.
 =3 and = + will be passed on to node F at node C, and the same values will be passed on to node
F.
Step 6:
 At node F, the value of will be compared with the left child, which is 0, and max(3,0)= 3, and
then with the right child, which is 1, and max(3,1)= 3 will remain the same, but the node value
of F will change to 1.

lOMoARcPSD|45814754
Step 7:
Node F returns the node value 1 to node C, at C = 3 and = +, the value of beta is modified, and
it is compared to 1, resulting in min (, 1) = 1. Now, at C, =3 and = 1, and again, it meets the
condition >=, the algorithm will prune the next child of C, which is G, and will not compute the
complete sub-tree G.
Step 8:
C now returns 1 to A, with max (3, 1) = 3 being the greatest result for A. The completed game
tree, which shows calculated and uncomputed nodes, is shown below. As a result, in this case,
the best maximize value is 3.

lOMoARcPSD|45814754
Example 2 and Solution:

lOMoARcPSD|45814754
4. IMPERFECT REAL-TIME DECISIONS:
• Moves must be made in a reasonable amount of time.

• usually it is not feasible to consider the whole game tree (even with alpha-beta)
• Programs should cut the search off at some point earlier and apply a heuristic evaluation
function to states in the search, effectively turning non terminal nodes into terminal leaves.
Alter min-max or alpha-beta in 2 ways:
1. Replace the utility function by a heuristic evaluation function EVAL, which estimates
the position’s utility.
2. Replace the terminal test by a cutoff test that decides when to apply EVAL.
Replace using heuristic evaluation function EVAL
EVALUATION FUNCTION:
• An evaluation function returns an estimate of the expected utility of the game from a given
position.
How do we design good evaluation functions?

lOMoARcPSD|45814754
1) The evaluation function should order the terminal states in the same way as the true utility
function.
2) The computation must not take too long.
3) For nonterminal states, the evaluation function should be strongly correlated with the actual
chances of winning.
Two ways to design an Evaluation Function:
i. Expected value
ii. Weighted linear function
i. Expected Value:
The evaluation function cannot know which states are which, but it can return a single value that
reflects the proportion of states with each outcome.
Where,
• EV – the expected value
• P(X) – the probability of the event
• n – the number of the repetitions of the event
Example: How many heads would you expect if you flipped a coin twice?
Solution: X = number of heads = {0, 1, 2}
p (0)=1/4,
p (1)=1/2,
p (2)=1/4
Weighted average = 0*1/4 + 1*1/2 + 2*1/4 = 1
ii. Weighted linear function: We can compute separate numerical contributions from each feature and
then combine them to find the total value.
• EV is the probability-weighted average of all possible events.

• Therefore, the general formula to find the EV for multiple events is:
Where,
• EVAL(s) – the expected value
• wi is a weight and each
• fi is a feature of the position
Example: Three coin tosses, the expected value for the number of heads is 3 x (1/2) = 1.5.

lOMoARcPSD|45814754
Cutting off search:
To modify ALPHA-BETA-SEARCH:
1) Replace the two lines that mention TERMINAL-TEST with
2) Arrange for some bookkeeping so that the current depth is incremented on each recursive call.
• The most straightforward approach: set a fixed depth limit so that CUTOFF-TEST (state,
depth) returns true for all depth greater than some fixed depth d.
• A more robust approach: apply iterative deepening.
• A forward-pruning version of alpha-beta search that uses statistic gained from prior
experience to lessen the chance that the best move will be pruned.
Search versus lookup:
• Many game programs pre-compute tables of best moves in the opening and endgame so that
they can look up a move rather than search.
Eg: BFS, DFS
• For the opening (and early moves), the program use table lookup, relying on the expertise of
human and statistic from a database of past games.
Eg: Two player games, multiple player game.
5. CONSTRAINT SATISFACTION PROBLEMS:

• A constraint satisfaction problem (or CSP) is a special kind of problem that satisfies some
additional structural properties beyond the basic requirements for problems in general.
Definition:
• State is defined by variables Xi with values from domain Di
• Goal test is a set of constraints specifying allowable combinations of values for subsets of
variables
• Solution is a complete, consistent assignment.
• In a CSP, the states are defined as,
• Finite set of variables V1, V2, …, Vn.
• Finite set of constrainsC1, C2, …, Cm.
• Non-empty domain of possible values for each variable DV1, DV2, … DVn.
• Each constraint Ci limits the values that variables can take, e.g., V1 ≠ V2
CSP EXAMPLE:
GRAPH COLORING:
• Variables: WA, NT, Q, NSW, V, SA, T
• Domains: Di={red , green , blue}
• Constraints: adjacent regions must have different colors.
• E.g. WA ≠ NT (if the language allows this)
• E.g. (WA, NT) ≠ {(red, green), (red, blue), (green, red)…}
• A state is defined as an assignment of values to some or all variables.
• Consistent assignment: assignment does not violate the constraints.
• A solution to a CSP is a complete assignment that satisfies all constraints.

lOMoARcPSD|45814754
Solution:
• {WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=green}
• Simple example of a formal representation language

CSP benefits
• Standard representation language
• Generic goal and successor functions
• Useful general-purpose algorithms with more power than standard search algorithms, including
generic heuristics.
Applications:
• Time table problems (exam/teaching schedules)
• Assignment problems (who teaches what)
Varieties of CSP’s:
i. Discrete variables
• Finite domains of size d ⇒O (dn) complete assignments.
Eg: a Boolean CSP, NP-Complete problem
• Infinite domains (integers, strings, etc.)
Eg: job scheduling, variables are start/end days for each job
• Need a constraint language
Eg: StartJob1 +5 ≤ StartJob3.
• Linear constraints solvable, nonlinear undecidable.
ii. Continuous variables
• Linear constraints solvable in poly time by linear programming methods (deal
with in the field of operations research).
iii. Our focus: discrete variables and finite domains
iv. Unary constraints involve a single variable.
E.g. SA ≠ green
v. Binary constraints involve pairs of variables.
E.g. SA ≠ WA
vi. Global constraints involve an arbitrary number of variables.
Eg: Crypth-arithmetic column constraints.

lOMoARcPSD|45814754
• Preference (soft constraints) e.g. red is better than green often represent able by a
cost for each variable assignment; not considered here.
REAL WORLD CSP’s:
• Assignment problems
• E.g., who teaches what class
• Timetable problems
• E.g., which class is offered when and where?
• Transportation scheduling
• Factory scheduling
CSP as a standard search problem:
Incremental formulation:
• States: Variables and values assigned so far
• Initial state: The empty assignment
• Action: Choose any unassigned variable and assign to it a value that does not violate
any constraints
• Fail if no legal assignments
• Goal test: The current assignment is complete and satisfies all constraints.
• Same formulation for all CSPs!!!
• Solution is found at depth n (n variables).
• What search method would you choose?
• How can we reduce the branching factor?
Commutative:
• CSPs are commutative.
• The order of any given set of actions has no effect on the outcome.
• Example: choose colors for Australian territories one at a time
• [WA=red then NT=green] same as [NT=green then WA=red]
• All CSP search algorithms consider a single variable assignment at a time ⇒
there are dn leaves.
CRYPTARITHMETIC PROBLEM
• Cryptarithmetic Problem is a type of constraint satisfaction problem where the game is about
digits and its unique replacement either with alphabets or other symbols.
• In cryptarithmetic problem, the digits (0-9) get substituted by some possible alphabets or
symbols.
• The task in cryptarithmetic problem is to substitute each digit with an alphabet to get the result
arithmetically correct.
• We can perform all the arithmetic operations on a given cryptarithmetic problem.
Constraints for cryptarithmetic problem:
• Unique digit to be replaced with a unique alphabet (no repeated digits).
• The result should satisfy the predefined arithmetic rules, i.e., 2+2 =4
• Digits should be from 0-9 only.
• In addition operation only one carry forward.
• The problem can be solved from both sides, i.e., lefthand side (L.H.S), or right-hand side
(R.H.S)

lOMoARcPSD|45814754
Example 1: Given a cryptarithmetic problem, i.e., S E N D + M O R E = M O N E Y.
Step 1: Starting from the left hand side (L.H.S) , the terms are S and M. Assign a digit which could
give a satisfactory result. Let’s assign S->9 and M->1.
Hence, we get a satisfactory result by adding up the terms and got an assignment for O as O->0 as
well.
Step 2: Now, move ahead to the next terms E and O to get N as its output.
• Adding E and O, which means 5+0=0, which is not possible because we cannot assign the
same digit to two letters.
• Add carry 1 to the value E to change the value of alphabet.

lOMoARcPSD|45814754
Step 3: Further, adding the next two terms N and R we get,
But, we have already assigned E->5. Not possible with 5 to E. Again, after solving the whole
problem, we will get a carryover on this term, so our answer will be satisfied.
Step 4: Again, on adding the last two terms, i.e., the rightmost terms D and E, we get Y as its result.
Keeping all the constraints in mind, the final resultant is as follows:
Alphabets Values
S 9
E 5
N 6
D 7
M 1
O 0
R 8
Y 2

lOMoARcPSD|45814754
Example 2:
Example 3:
6. CONSTRATIN PROPAGATION:
 In local state-spaces, the choice is only one, i.e., to search for a solution. But in CSP, we have two
choices either:
 We can search for a solution or
 We can perform a special type of inference called constraint propagation.
 Constraint propagation is a special type of inference which helps in reducing the legal number of
values for the variables.
 The idea behind constraint propagation is local consistency.
 In local consistency, variables are treated as nodes, and each binary constraint is treated as an arc in
the given problem.
There are following local consistencies which are discussed below:
1. Node Consistency: A single variable is said to be node consistent if all the values in the
variable’s domain satisfy the unary constraints on the variables.

lOMoARcPSD|45814754
2. Arc Consistency: A variable is arc consistent if every value in its domain satisfies the binary
constraints of the variables.
3. Path Consistency: When the evaluation of a set of two variables with respect to a third variable
can be extended over another variable, satisfying all the binary constraints. It is similar to arc
consistency.
4. k-consistency: This type of consistency is used to define the notion of stronger forms of
propagation. Here, we examine the k-consistency of the variables.
7. BACKTRACKING CSP’s:
• In CSP’s, variable assignments are commutative
For example:
[WA = red then NT = green]
Is the same as?
[NT =green then WA = red]
• We only need to consider assignments to a single variable at each level (i.e., we fix the order
of assignments)
• Depth-first search for CSPs with single-variable assignments is called backtracking search.
Pseudocode for Backtracking:

lOMoARcPSD|45814754
Example:
Problem in ordering:
• Ordering
– How should we order variables for assignment?
– How should we order values from the domains?
Need Improving Backtracking Efficiency Ordering
Improving Backtracking Efficiency Ordering:
• Ordering
– How should we order variables for assignment? –
– How should we order values from the domains?
Filtering: Can we detect inevitable failures early?

lOMoARcPSD|45814754
Early detection in failure:
Forward Checking:
• Forward checking Keep track of remaining legal values for unassigned variables.
• Terminate search when any variable has no legal values.
Arc Consistency:

lOMoARcPSD|45814754
8. PROBLEM STRUCTURE:
• Tasmania and the mainland are separate structures. We can solve them independently and then
combine their solutions.
• More generally, we can decompose the CSP into separate connected components (sub-problems
of the CSP).
• Then the solution is the union of the sub- problem solutions. This can be much more efficient
than solving the entire CSP as one problem.
Algorithm for tree structure CSP’s:

• Choose one variable as root, order variables from root to leaves such that every node's parent
precedes it in the ordering.
• Backward removal phase: check arc consistency starting from the rightmost node and going
backwards.
• Forward assignment phase: select an element from the domain of each variable going left to
right. We are guaranteed that there will be a valid assignment because each arc is arc consistent.

lOMoARcPSD|45814754
9. LOCAL SEARCH FOR CSP’S:

• Improve what you have until you can’t make it better.
• Generally much faster and more memory efficient than back-tracking search (but not
necessarily complete).
• Start with an initial assignment of variables to values.
• Allow states with unsatisfied constraints.
• Attempt to improve states by reassigning variable values.
Hill-climbing search:
• In each iteration, randomly select any conflicted variable and choose value that violates the
fewest constraints.
• I.e., attempt to greedily minimize total number of violated constraints h = number of conflicts.
• Problem: local minima h = 1.
Hill climbing state space diagram:

lOMoARcPSD|45814754
10. KNOWLEDGE BASED AGENT:
 An intelligent agent needs knowledge about the real world for taking decisions and reasoning to act
efficiently.
 Knowledge-based agents are those agents who have the capability of maintaining an internal state of
knowledge, reason over that knowledge, update their knowledge after observations and take
actions. These agents can represent the world with some formal representation and act
intelligently.
 Knowledge-based agents are composed of two main parts:
i. Knowledge-base
ii. Inference system.
i. Knowledge base:
 Knowledge-base is a central component of a knowledge-based agent, it is also known as KB.
 It is a collection of sentences (here 'sentence' is a technical term and it is not identical to sentence
in English).
 These sentences are expressed in a language which is called a knowledge representation
language. The Knowledge-base of KBA stores fact about the world.
 Why use a knowledge base? Knowledge-base is required for updating knowledge for an agent
to learn with experiences and take action as per the knowledge.
ii. Inference system
 Inference means deriving new sentences from old. Inference system allows us to add a new
sentence to the knowledge base.
 A sentence is a proposition about the world. Inference system applies logical rules to the KB to
deduce new information.
 Inference system generates new facts so that an agent can update the KB.
 An inference system works mainly in two rules which are given as:
o Forward chaining
o Backward chaining
a. Architecture of knowledge-based agent:

 The above diagram is representing a generalized architecture for a knowledge-based agent. The
knowledge-based agent (KBA) take input from the environment by perceiving the environment.
 The input is taken by the inference engine of the agent and which also communicate with KB to decide
as per the knowledge store in KB.
 The learning element of KBA regularly updates the KB by learning new knowledge.

lOMoARcPSD|45814754
b. Operations Performed by KBA:
Following are three operations which are performed by KBA in order to show the intelligent behavior:
1. TELL: This operation tells the knowledge base what it perceives from the environment.
2. ASK: This operation asks the knowledge base what action it should perform.
3. Perform: It performs the selected action.
A generic knowledge-based agent:
Following is the structure outline of a generic knowledge-based agents program:

function KB-AGENT (percept):
persistent: KB, a knowledge base
t, a counter, initially 0, indicating time
TELL (KB, MAKE-PERCEPT-SENTENCE (percept, t))
Action = ASK (KB, MAKE-ACTION-QUERY (t))
TELL (KB, MAKE-ACTION-SENTENCE (action, t))
t=t+1
return action
 The knowledge-based agent takes percept as input and returns an action as output.
 The agent maintains the knowledge base, KB, and it initially has some background knowledge of the
real world.
 It also has a counter to indicate the time for the whole process, and this counter is initialized with zero.
Each time when the function is called, it performs its three operations:
 Firstly it TELLs the KB what it perceives.
 Secondly, it asks KB what action it should take

lOMoARcPSD|45814754
 Third agent program TELLS the KB that which action was chosen.
 The MAKE-PERCEPT-SENTENCE generates a sentence as setting that the agent perceived the given
percept at the given time.
 The MAKE-ACTION-QUERY generates a sentence to ask which action should be done at the current
time.
 MAKE-ACTION-SENTENCE generates a sentence which asserts that the chosen action was
executed.
c. Levels of knowledge-based agent:

A knowledge-based agent can be viewed at different levels which are given below:
1. Knowledge level
2. Logical Level
3. Implementation level
1. Knowledge level
 Knowledge level is the first level of knowledge-based agent, and in this level, we need to specify
what the agent knows, and what the agent goals are.
 With these specifications, we can fix its behavior.
 For example, suppose an automated taxi agent needs to go from a station A to station B, and he
knows the way from A to B, so this comes at the knowledge level.
2. Logical level:
 At this level, we understand that how the knowledge representation of knowledge is stored.
 At this level, sentences are encoded into different logics. At the logical level, an encoding of
knowledge into logical sentences occurs.
 At the logical level we can expect to the automated taxi agent to reach to the destination B.
3. Implementation level:
 This is the physical representation of logic and knowledge.
 At the implementation level agent perform actions as per logical and knowledge level.
 At this level, an automated taxi agent actually implement his knowledge and logic so that he can
reach to the destination.
d. Approaches to designing a knowledge-based agent:
There are mainly two approaches to build a knowledge-based agent:

1. Declarative approach: We can create a knowledge-based agent by initializing with an empty
knowledge base and telling the agent all the sentences with which we want to start with. This approach
is called Declarative approach.

lOMoARcPSD|45814754
2. Procedural approach: In the procedural approach, we directly encode desired behavior as a program
code. Which means we just need to write a program that already encodes the desired behavior or agent.
11. KNOWLEDGE REPRESENTATION:
The kind of knowledge which needs to be represented in AI systems:

 Object: All the facts about objects in our world domain. E.g., Guitars contains strings, trumpets are
brass instruments.
 Events: Events are the actions which occur in our world.
 Performance: It describe behavior which involves knowledge about how to do things.
 Meta-knowledge: It is knowledge about what we know.
 Facts: Facts are the truths about the real world and what we represent.
 Knowledge-Base: The central component of the knowledge-based agents is the knowledge base. It
is represented as KB. The Knowledgebase is a group of the Sentences (Here, sentences are used as
a technical term and not identical with the English language).
What is meant by knowledge?

Knowledge is awareness or familiarity gained by experiences of facts, data, and situations.
TYPES OF KNOWLEDGE:
1. Declarative Knowledge:
 Declarative knowledge is to know about something.
 It includes concepts, facts, and objects.
 It is also called descriptive knowledge and expressed in declarative sentences.
 It is simpler than procedural language.
2. Procedural Knowledge
 It is also known as imperative knowledge.
 Procedural knowledge is a type of knowledge which is responsible for knowing how to do
something.
 It can be directly applied to any task.
 It includes rules, strategies, procedures, agendas, etc.
 Procedural knowledge depends on the task on which it can be applied.
3. Meta-knowledge:
 Knowledge about the other types of knowledge is called Meta-knowledge.
4. Heuristic knowledge:
 Heuristic knowledge is representing knowledge of some experts in a filed or subject.

lOMoARcPSD|45814754
 Heuristic knowledge is rules of thumb based on previous experiences, awareness of approaches, and
which are good to work but not guaranteed.
5. Structural knowledge:
 Structural knowledge is basic knowledge to problem-solving.

 It describes relationships between various concepts such as kind of, part of, and grouping of
something.
 It describes the relationship that exists between concepts or objects.
APPROACH TO KNOWLEDGE REPRESENTATION:
There are mainly four approaches to knowledge representation, which are given below:
1. Simple relational knowledge:
 It is the simplest way of storing facts which uses the relational method, and each fact about a set of
the object is set out systematically in columns.
 This approach of knowledge representation is famous in database systems where the relationship
between different entities is represented.
 This approach has little opportunity for inference.
Example: The following is the simple relational knowledge representation.
2. Inheritable knowledge:
 In the inheritable knowledge approach, all data must be stored into a hierarchy of classes.
 All classes should be arranged in a generalized form or a hierarchal manner.
 In this approach, we apply inheritance property.
 Elements inherit values from other members of a class.
 This approach contains inheritable knowledge which shows a relation between instance and class, and
it is called instance relation.
 Every individual frame can represent the collection of attributes and its value.

lOMoARcPSD|45814754
 In this approach, objects and values are represented in Boxed nodes.

 We use Arrows which point from objects to their values.
Example:
3. Inferential knowledge:
 Inferential knowledge approach represents knowledge in the form of formal logics.
 This approach can be used to derive more facts.
 It guaranteed correctness.
Example: Let's suppose there are two statements:
a. Marcus is a man
b. All men are mortal
Then it can be represented as:
man(Marcus)
∀x = man (x) ----------> mortal (x)s
4. Procedural knowledge:
 Procedural knowledge approach uses small programs and codes which describes how to do specific
things, and how to proceed.
 In this approach, one important rule is used which is If-Then rule.
 In this knowledge, we can use various coding languages such as LISP language and Prolog language.
 We can easily represent heuristic or domain-specific knowledge using this approach.
 But it is not necessary that we can represent all cases in this approach.

lOMoARcPSD|45814754
12. TECHNIQUES OF KNOWLEDGE REPRESENTATION:
There are mainly four ways of knowledge representation which are given as follows:
1. Logical Representation
2. Semantic Network Representation
3. Frame Representation
4. Production Rules
1. Logical Representation
 Logical representation is a language with some concrete rules which deals with propositions and has no
ambiguity in representation.
 Logical representation means drawing a conclusion based on various conditions. This representation
lays down some important communication rules.
 It consists of precisely defined syntax and semantics which supports the sound inference. Each sentence
can be translated into logics using syntax and semantics.
i. Syntax:
 Syntaxes are the rules which decide how we can construct legal sentences in the logic.
 It determines which symbol we can use in knowledge representation.
 How to write those symbols.
ii. Semantics:
 Semantics are the rules by which we can interpret the sentence in the logic.
 Semantic also involves assigning a meaning to each sentence.

lOMoARcPSD|45814754
Logical representation can be categorized into mainly two logics:

a. Propositional Logics
b. Predicate logics
Advantages of logical representation:

1. Logical representation enables us to do logical reasoning.
2. Logical representation is the basis for the programming languages.
Disadvantages of logical Representation:

1. Logical representations have some restrictions and are challenging to work with.
2. Logical representation technique may not be very natural, and inference may not be so efficient.
2. Semantic Network Representation

 Semantic networks are alternative of predicate logic for knowledge representation.
 In Semantic networks, we can represent our knowledge in the form of graphical networks.
 This network consists of nodes representing objects and arcs which describe the relationship between
those objects.
 Semantic networks can categorize the object in different forms and can also link those objects.
 Semantic networks are easy to understand and can be easily extended.
This representation consist of mainly two types of relations:
a. IS-A relation (Inheritance)
b. Kind-of-relation
Example: Following are some statements which we need to represent in the form of nodes and arcs.
Statements:
a. Jerry is a cat.
b. Jerry is a mammal
c. Jerry is owned by Priya.
d. Jerry is brown colored.
e. All Mammals are animal.

lOMoARcPSD|45814754
In the above diagram, we have represented the different type of knowledge in the form of nodes and arcs.
Each object is connected with another object by some relation.
Advantages of Semantic network:

1. Semantic networks are a natural representation of knowledge.
2. Semantic networks convey meaning in a transparent manner.
3. These networks are simple and easily understandable.
Disadvantage in Semantic representation:

1. Semantic networks take more computational time at runtime as we need to traverse the complete network
tree to answer some questions. It might be possible in the worst case scenario that after traversing the
entire tree, we find that the solution does not exist in this network.
2. Semantic networks try to model human-like memory (Which has 1015 neurons and links) to store the
information, but in practice, it is not possible to build such a vast semantic network.
3. These types of representations are inadequate as they do not have any equivalent quantifier, e.g., for all,
for some, none, etc.
4. Semantic networks do not have any standard definition for the link names.
5. These networks are not intelligent and depend on the creator of the system.
3. Frame Representation
 A frame is a record like structure which consists of a collection of attributes and its values to describe
an entity in the world.
 Frames are the AI data structure which divides knowledge into substructures by representing stereotypes
situations.

lOMoARcPSD|45814754
 It consists of a collection of slots and slot values.

 These slots may be of any type and sizes.
 Slots have names and values which are called facets.
 Facets: The various aspects of a slot is known as Facets.
 Facets are features of frames which enable us to put constraints on the frames. Example: IF-NEEDED
facts are called when data of any particular slot is needed.
 A frame may consist of any number of slots, and a slot may include any number of facets and facets
may have any number of values.
 A frame is also known as slot-filter knowledge representation in artificial intelligence.
Example: 1
Let's take an example of a frame for a book
Slots Filters
Title Artificial Intelligence
Genre Computer Science
Author Peter Norvig
Edition Third Edition
Year 1996
Page 1152
Advantages of frame representation:

1. The frame knowledge representation makes the programming easier by grouping the related data.
2. The frame representation is comparably flexible and used by many applications in AI.
3. It is very easy to add slots for new attribute and relations.
4. It is easy to include default data and to search for missing values.
5. Frame representation is easy to understand and visualize.

lOMoARcPSD|45814754
Disadvantages of frame representation:

1. In frame system inference mechanism is not be easily processed.
2. Inference mechanism cannot be smoothly proceeded by frame representation.
3. Frame representation has a much generalized approach.
4. Production Rules
 Production rules system consist of (condition, action) pairs which mean, "If condition then action". It
has mainly three parts:
1. The set of production rules

2. Working Memory
3. The recognize-act-cycle
 In production rules agent checks for the condition and if the condition exists then production rule fires
and corresponding action is carried out. The condition part of the rule determines which rule may be
applied to a problem. And the action part carries out the associated problem-solving steps. This complete
process is called a recognize-act cycle.
 The working memory contains the description of the current state of problems-solving and rule can
write knowledge to the working memory. This knowledge match and may fire other rules.
 If there is a new situation (state) generates, then multiple production rules will be fired together, this is
called conflict set. In this situation, the agent needs to select a rule from these sets, and it is called a
conflict resolution.
Example:
o IF (at bus stop AND bus arrives) THEN action (get into the bus)
o IF (on the bus AND paid AND empty seat) THEN action (sit down).
o IF (on bus AND unpaid) THEN action (pay charges).
o IF (bus arrives at destination) THEN action (get down from the bus).
Advantages of Production rule:

1. The production rules are expressed in natural language.
2. The production rules are highly modular, so we can easily remove, add or modify an individual rule.
Disadvantages of Production rule:

1. Production rule system does not exhibit any learning capabilities, as it does not store the result of the
problem for the future uses.

lOMoARcPSD|45814754
2. During the execution of the program, many rules may be active hence rule-based production systems
are inefficient.
13. PROPOSITIONAL LOGIC
 Propositional logic (PL) is the simplest form of logic where all the statements are made by propositions.
 A proposition is a declarative statement which is either true or false.
 It is a technique of knowledge representation in logical and mathematical form.
Example:
a) It is Sunday.
b) The Sun rises from West (False proposition)
c) 3+3= 7(False proposition)
d) 5 is a prime number.
Following are some basic facts about propositional logic:
 Propositional logic is also called Boolean logic as it works on 0 and 1.

 In propositional logic, we use symbolic variables to represent the logic, and we can use any symbol for
a representing a proposition, such A, B, C, P, Q, R, etc.
 Propositions can be either true or false, but it cannot be both.
 Propositional logic consists of an object, relations or function, and logical connectives.
 These connectives are also called logical operators.
 The propositions and connectives are the basic elements of the propositional logic.
 Connectives can be said as a logical operator which connects two sentences.
 A proposition formula which is always true is called tautology, and it is also called a valid sentence.
 A proposition formula which is always false is called Contradiction.
 A proposition formula which has both true and false values is called
 Statements which are questions, commands, or opinions are not propositions such as "Where is Rohini",
"How are you", "What is your name", are not propositions.
i. Syntax of propositional logic:
 The syntax of propositional logic defines the allowable sentences for the knowledge representation.
There are two types of Propositions:
a. Atomic Propositions
b. Compound propositions

lOMoARcPSD|45814754
 Atomic Proposition: Atomic propositions are the simple propositions. It consists of a single proposition
symbol. These are the sentences which must be either true or false.
Example:
a) 2+2 is 4, it is an atomic proposition as it is a true fact.
b) "The Sun is cold" is also a proposition as it is a false fact.
 Compound proposition: Compound propositions are constructed by combining simpler or atomic
propositions, using parenthesis and logical connectives.
Example:
a) "It is raining today, and street is wet."
b) "Ankit is a doctor, and his clinic is in Mumbai."
ii. Logical Connectives:
 Logical connectives are used to connect two simpler propositions or representing a sentence logically.
We can create compound propositions with the help of logical connectives.
 There are mainly five connectives, which are given as follows:

lOMoARcPSD|45814754
Following is the summarized table for Propositional Logic Connectives:
a. Truth Table:
In propositional logic, we need to know the truth values of propositions in all possible scenarios. We can
combine all the possible combination with logical connectives, and the representation of these combinations in
a tabular format is called Truth table. Following are the truth table for all logical connectives:

lOMoARcPSD|45814754
1) Truth table with three propositions:
We can build a proposition composing three propositions P, Q, and R. This truth table is made-up of 8n Tuples
as we have taken three proposition symbols.
2) Precedence of connectives:
Just like arithmetic operators, there is a precedence order for propositional connectors or logical operators. This
order should be followed while evaluating a propositional problem. Following is the list of the precedence order
for operators:
Precedence Operators
First Precedence Parenthesis
Second Precedence Negation
Third Precedence Conjunction(AND)
Fourth Precedence Disjunction(OR)
Fifth Precedence Implication
Six Precedence Biconditional

lOMoARcPSD|45814754
iii. Logical equivalence:
 Logical equivalence is one of the features of propositional logic.

 Two propositions are said to be logically equivalent if and only if the columns in the truth table are
identical to each other.
 Let's take two propositions A and B, so for logical equivalence, we can write it as A⇔B. In below truth
table we can see that column for ¬A∨ B and A→B, are identical hence A is Equivalent to B.
iv. Properties of Operators:

o Commutativity:
o P∧ Q= Q ∧ P, or
o P ∨ Q = Q ∨ P.
o Associativity:
o (P ∧ Q) ∧ R= P ∧ (Q ∧ R),
o (P ∨ Q) ∨ R= P ∨ (Q ∨ R)
o Identity element:
o P ∧ True = P,
o P ∨ True= True.
o Distributive:
o P∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
o P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
o DE Morgan's Law:
o ¬ (P ∧ Q) = (¬P) ∨ (¬Q)
o ¬ (P ∨ Q) = (¬ P) ∧ (¬Q).
o Double-negation elimination:
o ¬ (¬P) = P.
v. Limitations of Propositional logic:

 We cannot represent relations like ALL, some, or none with propositional logic.
Example:

lOMoARcPSD|45814754
a. All the girls are intelligent.

b. Some apples are sweet.
 Propositional logic has limited expressive power.

 In propositional logic, we cannot describe statements in terms of their properties or logical relationships.
14.RULES OF INFERENCE
i. Inference:
 In artificial intelligence, we need intelligent computers which can create new logic from old logic or by
evidence, so generating the conclusions from evidence and facts is termed as Inference.
ii. Inference rules and Proof’s:
 Inference rules are the templates for generating valid arguments. Inference rules are applied to derive
proofs in artificial intelligence, and the proof is a sequence of the conclusion that leads to the desired
goal.
 In inference rules, the implication among all the connectives plays an important role. Following are
some terminologies related to inference rules:
 Implication: It is one of the logical connectives which can be represented as P → Q. It is a Boolean

expression.
 Converse: The converse of implication, which means the right-hand side proposition goes to the left-
hand side and vice-versa. It can be written as Q → P.
 Contrapositive: The negation of converse is termed as contrapositive, and it can be represented as ¬ Q
→ ¬ P.
 Inverse: The negation of implication is called inverse. It can be represented as ¬ P → ¬ Q.
From the above term some of the compound statements are equivalent to each other, which we can prove using
truth table:
Hence from the above truth table, we can prove that P → Q is equivalent to ¬ Q → ¬ P, and Q→ P is
equivalent to ¬ P → ¬ Q.

lOMoARcPSD|45814754
Types of Inference rules:
1. Modus Ponens:
The Modus Ponens rule is one of the most important rules of inference, and it states that if P and P → Q is
true, then we can infer that Q will be true. It can be represented as:
Example:
Statement-1: "If I am sleepy then I go to bed" ==> P→ Q

Statement-2: "I am sleepy" ==> P
Conclusion: "I go to bed." ==> Q.
Hence, we can say that, if P→ Q is true and P is true then Q will be true.
Proof by Truth table:
2. Modus Tollens:
The Modus Tollens rule state that if P→ Q is true and ¬ Q is true, then ¬ P will also true. It can be
represented as:
Statement-1: "If I am sleepy then I go to bed" ==> P→ Q

Statement-2: "I do not go to the bed."==> ~Q
Statement-3: Which infers that "I am not sleepy" => ~P
Proof by Truth table:

lOMoARcPSD|45814754
3. Hypothetical Syllogism:
The Hypothetical Syllogism rule state that if P→R is true whenever P→Q is true, and Q→R is true. It can be
represented as the following notation:
Example:
Statement-1: If you have my home key then you can unlock my home. P→Q
Statement-2: If you can unlock my home then you can take my money. Q→R
Conclusion: If you have my home key then you can take my money. P→R
Proof by truth table:
4. Disjunctive Syllogism:
The Disjunctive syllogism rule state that if P∨Q is true, and ¬P is true, then Q will be true. It can be represented
as:
Example:
Proof by truth-table:

lOMoARcPSD|45814754
5. Addition:
The Addition rule is one the common inference rule, and it states that If P is true, then P∨Q will be true.
Example:
Proof by Truth-Table:
6. Simplification:
The simplification rule state that if P∧ Q is true, then Q or P will also be true. It can be represented as:
7. Resolution:
The Resolution rule state that if P∨Q and ¬ P∧R is true, then Q∨R will also be true. It can be represented as

lOMoARcPSD|45814754
15.PROOF BY RESOLUTION:
 Resolution is a theorem proving technique that proceeds by building refutation proofs, i.e., proofs by
contradictions. It was invented by a Mathematician John Alan Robinson in the year 1965.
 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
which can efficiently operate on the conjunctive normal form or clausal form.
 Clause: Disjunction of literals (an atomic sentence) is called a clause. It is also known as a unit clause.
 Conjunctive Normal Form: A sentence represented as a conjunction of clauses is said to be conjunctive
normal form or CNF.
THE RESOLUTION INFERENCE RULE
 The resolution rule for first-order logic is simply a lifted version of the propositional rule. Resolution
can resolve two clauses if they contain complementary literals, which are assumed to be standardized
apart so that they share no variables.
Where li and mj are complementary literals.
This rule is also called the binary resolution rule because it only resolves exactly two literals.
Example:
We can resolve two clauses which are given below:
[Animal (g(x) V Loves (f(x), x)] and [￢ Loves (a, b) V ￢Kills (a, b)]

lOMoARcPSD|45814754
Where two complimentary literals are: Loves (f(x), x) and ￢ Loves (a, b)
These literals can be unified with unifier θ= [a/f(x), and b/x] , and it will generate a resolvent clause:
[Animal (g(x) V ￢ Kills (f(x), x)].
Steps for Resolution:

1. Conversion of facts into first-order logic.
2. Convert FOL statements into CNF
3. Negate the statement which needs to prove (proof by contradiction)
4. Draw resolution graph (unification).
To better understand all the above steps, we will take an example in which we will apply resolution.
Example:
Step-1: Conversion of Facts into FOL
 In the first step we will convert all the given statements into its first order logic.

lOMoARcPSD|45814754
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 easier for
resolution proofs.
 Eliminate all implication (→) and rewrite

a. ∀x ¬ food(x) V likes(John, x)
b. food(Apple) Λ food(vegetables)
c. ∀x ∀y ¬ [eats(x, y) Λ ¬ killed(x)] V food(y)
d. eats (Anil, Peanuts) Λ alive(Anil)
e. ∀x ¬ eats(Anil, x) V eats(Harry, x)
f. ∀x¬ [¬ killed(x) ] V alive(x)
g. ∀x ¬ alive(x) V ¬ killed(x)
h. likes(John, Peanuts).
 Move negation (¬)inwards and rewrite
. ∀x ¬ food(x) V likes(John, x)
a. food(Apple) Λ food(vegetables)
b. ∀x ∀y ¬ eats(x, y) V killed(x) V food(y)
c. eats (Anil, Peanuts) Λ alive(Anil)
d. ∀x ¬ eats(Anil, x) V eats(Harry, x)
e. ∀x ¬killed(x) ] V alive(x)
f. ∀x ¬ alive(x) V ¬ killed(x)
g. likes(John, Peanuts).
 Rename variables or standardize variables
. ∀x ¬ food(x) V likes(John, x)
a. food(Apple) Λ food(vegetables)
b. ∀y ∀z ¬ eats(y, z) V killed(y) V food(z)
c. eats (Anil, Peanuts) Λ alive(Anil)
d. ∀w¬ eats(Anil, w) V eats(Harry, w)
e. ∀g ¬killed(g) ] V alive(g)
f. ∀k ¬ alive(k) V ¬ killed(k)
g. Likes (John, Peanuts).

lOMoARcPSD|45814754
 Eliminate existential instantiation quantifier by elimination: In this step, we will eliminate

existential quantifier ∃, and this process is known as Skolemization. But in this example problem since
there is no existential quantifier so all the statements will remain same in this step.
 Drop Universal Qualifier: In this step we will drop all universal quantifier since all the statements are not
implicitly quantified so we don't need it.
a. ¬ food(x) V likes(John, x)
b. food(Apple)
c. food(vegetables)
d. ¬ eats(y, z) V killed(y) V food(z)
e. eats (Anil, Peanuts)
f. alive(Anil)
g. ¬ eats(Anil, w) V eats(Harry, w)
h. killed(g) V alive(g)
i. ¬ alive(k) V ¬ killed(k)
j. Likes (John, Peanuts).
 Distribute conjunction ∧ over disjunction ¬: This step will not make any change in this problem.
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:
 Now in this step, we will solve the problem by resolution tree using substitution. For the above problem,
it will be given as follows:
Hence the negation of the conclusion has been proved as a complete contradiction with the given set of
statements.

lOMoARcPSD|45814754
16.FORWARD AND BACKWARD CHAINING:
a. Inference engine:
 The inference engine is the component of the intelligent system in artificial intelligence, which applies
logical rules to the knowledge base to infer new information from known facts.
 The first inference engine was part of the expert system. Inference engine commonly proceeds in two
modes, which are:
a. Forward chaining
b. Backward chaining
HORN CLAUSE AND DEFINITE CLAUSE:
 Horn clause and definite clause are the forms of sentences, which enables knowledge base to use a more
restricted and efficient inference algorithm.
 Logical inference algorithms use forward and backward chaining approaches, which require KB in the
form of the first-order definite clause.
 Definite clause: A clause which is a disjunction of literals with exactly one positive literal is known
as a definite clause or strict horn clause.
 Horn clause: A clause which is a disjunction of literals with at most one positive literal is known as
horn clause. Hence all the definite clauses are horn clauses.
Example: (¬ p V ¬ q V k). It has only one positive literal k.
o It is equivalent to p ∧ q → k.
FORWARD CHAINING:
 Forward chaining is also known as a forward deduction or forward reasoning method when using an
inference engine.
 Forward chaining is a form of reasoning which start with atomic sentences in the knowledge base and
applies inference rules (Modus Ponens) in the forward direction to extract more data until a goal is
reached.
 The Forward-chaining algorithm starts from known facts, triggers all rules whose premises are satisfied,
and add their conclusion to the known facts. This process repeats until the problem is solved.
Properties of Forward-Chaining:
 It is a down-up approach, as it moves from bottom to top.

lOMoARcPSD|45814754
 It is a process of making a conclusion based on known facts or data, by starting from the initial state and
reaches the goal state.
 Forward-chaining approach is also called as data-driven as we reach to the goal using available data.
 Forward -chaining approach is commonly used in the expert system, such as CLIPS, business, and
production rule systems.
Consider the following famous example which we will use in both approaches:
Example:
 "As per the law, it is a crime for an American to sell weapons to hostile nations. Country A, an
enemy of America, has some missiles, and all the missiles were sold to it by Robert, who is an
American citizen."
Prove that "Robert is criminal."
 To solve the above problem, first, we will convert all the above facts into first-order definite clauses,
and then we will use a forward-chaining algorithm to reach the goal.
Facts Conversion into FOL:

lOMoARcPSD|45814754
Forward chaining proof:
Step-1:
 In the first step we will start with the known facts and will choose the sentences which do not have
implications, such as: American (Robert), Enemy (A, America), Owns (A, T1), and Missile (T1).
All these facts will be represented as below.
Step-2:
 At the second step, we will see those facts which infer from available facts and with satisfied premises.
 Rule-(1) does not satisfy premises, so it will not be added in the first iteration.
 Rule-(2) and (3) are already added.
 Rule-(4) satisfy with the substitution {p/T1}, so Sells (Robert, T1, A) is added, which infers from the
conjunction of Rule (2) and (3).
 Rule-(6) is satisfied with the substitution (p/A), so Hostile (A) is added and which infers from Rule-(7).
Step-3:
 At step-3, as we can check Rule-(1) is satisfied with the substitution {p/Robert, q/T1, r/A}, so we can
add Criminal (Robert) which infers all the available facts. And hence we reached our goal statement.
Hence it is proved that Robert is Criminal using forward chaining approach.

lOMoARcPSD|45814754
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:
 It is known as a top-down approach.

 Backward-chaining is based on modus ponens inference rule.
 In backward chaining, the goal is broken into sub-goal or sub-goals to prove the facts true.
 It is called a goal-driven approach, as a list of goals decides which rules are selected and used.
 Backward -chaining algorithm is used in game theory, automated theorem proving tools, inference
engines, proof assistants, and various AI applications.
 The backward-chaining method mostly used a depth-first search strategy for proof.
Example:
 In backward-chaining, we will use the same above example, and will rewrite all the rules.
Backward-Chaining proof:
 In Backward chaining, we will start with our goal predicate, which is Criminal (Robert), and then infer
further rules.

lOMoARcPSD|45814754
Step-1:
 At the first step, we will take the goal fact. And from the goal fact, we will infer other facts, and at last,
we will prove those facts true. So our goal fact is "Robert is Criminal," so following is the predicate of
it.
Step-2:
 At the second step, we will infer other facts form goal fact which satisfies the rules. So as we can see in
Rule-1, the goal predicate Criminal (Robert) is present with substitution {Robert/P}. So we will add all
the conjunctive facts below the first level and will replace p with Robert.
Here we can see American (Robert) is a fact, so it is proved here.
 Step-3: At step-3, we will extract further fact Missile(q) which infer from Weapon(q), as it satisfies
Rule-(5). Weapon (q) is also true with the substitution of a constant T1 at q.
Step-4:
 At step-4, we can infer facts Missile (T1) and Owns (A, T1) form Sells(Robert, T1, r) which satisfies
the Rule- 4, with the substitution of A in place of r. So these two statements are proved here.

lOMoARcPSD|45814754
Step-5:
 At step-5, we can infer the fact Enemy (A, America) from Hostile (A) which satisfies Rule- 6. And
hence all the statements are proved true using backward chaining.
17.THE WUMPUS WORLD IN ARTIFICIAL INTELLIGENCE

Wumpus world:
 The Wumpus world is a simple world example to illustrate the worth of a knowledge-based agent and
to represent knowledge representation. It was inspired by a video game Hunt the Wumpus by Gregory
Yob in 1973.
 The Wumpus world is a cave which has 4/4 rooms connected with passageways. So there are total 16
rooms which are connected with each other.
 We have a knowledge-based agent who will go forward in this world.

lOMoARcPSD|45814754
 The cave has a room with a beast which is called Wumpus, who eats anyone who enters the room.
 The Wumpus can be shot by the agent, but the agent has a single arrow.
 In the Wumpus world, there are some Pits rooms which are bottomless, and if agent falls in Pits, then
he will be stuck there forever.
 The exciting thing with this cave is that in one room there is a possibility of finding a heap of gold. So
the agent goal is to find the gold and climb out the cave without fallen into Pits or eaten by Wumpus.
 The agent will get a reward if he comes out with gold, and he will get a penalty if eaten by Wumpus or
falls in the pit.
 Following is a sample diagram for representing the Wumpus world. It is showing some rooms with Pits,
one room with Wumpus and one agent at (1, 1) square location of the world.
There are also some components which can help the agent to navigate the cave. These components are
given as follows:
a. The rooms adjacent to the Wumpus room are smelly, so that it would have some stench.
b.The room adjacent to PITs has a breeze, so if the agent reaches near to PIT, then he will perceive the breeze.
c. There will be glitter in the room if and only if the room has gold.
d.The Wumpus can be killed by the agent if the agent is facing to it, and Wumpus will emit a horrible scream
which can be heard anywhere in the cave.

lOMoARcPSD|45814754
PEAS description of Wumpus world:
To explain the Wumpus world we have given PEAS description as below:
i. Performance measure:
 +1000 reward points if the agent comes out of the cave with the gold.
 -1000 points penalty for being eaten by the Wumpus or falling into the pit.
 -1 for each action, and -10 for using an arrow.
 The game ends if either agent dies or came out of the cave.
ii. Environment:
 A 4*4 grid of rooms.
 The agent initially in room square [1, 1], facing toward the right.
 Location of Wumpus and gold are chosen randomly except the first square [1,1].
 Each square of the cave can be a pit with probability 0.2 except the first square.
iii. Actuators:
 Left turn,
 Right turn
 Move forward
 Grab
 Release
 Shoot.
iv. Sensors:
 The agent will perceive the stench if he is in the room adjacent to the Wumpus. (Not diagonally).
 The agent will perceive breeze if he is in the room directly adjacent to the Pit.
 The agent will perceive the glitter in the room where the gold is present.
 The agent will perceive the bump if he walks into a wall.
 When the Wumpus is shot, it emits a horrible scream which can be perceived anywhere in the cave.
 These percepts can be represented as five element list, in which we will have different indicators for
each sensor.
 Example if agent perceives stench, breeze, but no glitter, no bump, and no scream then it can be
representedas:
[Stench, Breeze, None, None, None].

lOMoARcPSD|45814754
v. The Wumpus world Properties:

 Partially observable: The Wumpus world is partially observable because the agent can only
perceive the close environment such as an adjacent room.
 Deterministic: It is deterministic, as the result and outcome of the world are already known.
 Sequential: The order is important, so it is sequential.
 Static: It is static as Wumpus and Pits are not moving.
 Discrete: The environment is discrete.
 One agent: The environment is a single agent as we have one agent only and Wumpus is not
considered as an agent.
Exploring the Wumpus world:

Now we will explore the Wumpus world and will determine how the agent will find its goal by applying logical
reasoning.
i. Agent's First step:
 Initially, the agent is in the first room or on the square [1, 1], and we already know that this room is safe
for the agent, so to represent on the below diagram (a) that room is safe we will add symbol OK. Symbol
A is used to represent agent, symbol B for the breeze, G for Glitter or gold, V for the visited room, P for
pits, W for Wumpus.
At Room [1, 1] agent does not feel any breeze or any Stench which means the adjacent squares are also OK.
ii. Agent's second Step:

 Now agent needs to move forward, so it will either move to [1, 2], or [2,1].

lOMoARcPSD|45814754
 Let's suppose agent moves to the room [2, 1], at this room agent perceives some breeze which means
Pit is around this room.
 The pit can be in [3, 1], or [2,2], so we will add symbol P? to say that, is this Pit room?
 Now agent will stop and think and will not make any harmful move.
 The agent will go back to the [1, 1] room. The room [1,1], and [2,1] are visited by the agent, so we will
use symbol V to represent the visited squares.
iii. Agent's third step:
 At the third step, now agent will move to the room [1,2] which is OK. In the room [1,2] agent perceives
a stench which means there must be a Wumpus nearby.
 But Wumpus cannot be in the room [1,1] as by rules of the game, and also not in [2,2] (Agent had not
detected any stench when he was at [2,1]).
 Therefore agent infers that Wumpus is in the room [1,3], and in current state, there is no breeze which
means in [2,2] there is no Pit and no Wumpus. So it is safe, and we will mark it OK, and the agent moves
further in [2,2].
iv. Agent's fourth step:
 At room [2,2], here no stench and no breezes present so let's suppose agent decides to move to [2,3].
 At room [2,3] agent perceives glitter, so it should grab the gold and climb out of the cave.

lOMoARcPSD|45814754
18. AGENT BASED ON PROPOSITIONAL LOGIC:
 The agent starts visiting from first square [1, 1], and we already know that this room is safe for the agent.
To build a knowledge base for Wumpus world, we will use some rules and atomic propositions.
 We need symbol [i, j] for each location in the Wumpus world, where i is for the location of rows, and j
for column location.
i. Atomic proposition variable for Wumpus world:

 Let Pi,j be true if there is a Pit in the room [i, j].
 Let Bi,j be true if agent perceives breeze in [i, j], (dead or alive).
 Let Wi,j be true if there is Wumpus in the square[i, j].
 Let Si,j be true if agent perceives stench in the square [i, j].
 Let Vi,j be true if that square[i, j] is visited.
 Let Gi,j be true if there is gold (and glitter) in the square [i, j].
 Let OKi,j be true if the room is safe.
Some Propositional Rules for the Wumpus world:

lOMoARcPSD|45814754
Representation of Knowledgebase for Wumpus world:
Following is the Simple KB for Wumpus world when an agent moves from room [1, 1], to room [2,1]:
 Here in the first row, we have mentioned propositional variables for room[1,1], which is showing that
room does not have Wumpus (¬ W11), no stench (¬S11), no Pit(¬P11), no breeze(¬B11), no gold (¬G11),
visited (V11), and the room is Safe(OK11).
 In the second row, we have mentioned propositional variables for room [1,2], which is showing that
there is no Wumpus, stench and breeze are unknown as an agent has not visited room [1,2], no Pit, not
visited yet, and the room is safe.
 In the third row we have mentioned propositional variable for room [2,1], which is showing that there
is no Wumpus(¬ W21), no stench (¬S21), no Pit (¬P21), Perceives breeze(B21), no glitter(¬G21), visited
(V21), and room is safe (OK21).
Prove that Wumpus is in the room (1, 3).
 We can prove that Wumpus is in the room (1, 3) using propositional rules which we have derived for
the Wumpus world and using inference rule.
1. Apply Modus Ponens with ¬S11 and R1:
 We will firstly apply MP rule with R1 which is ¬S11 → ¬ W11 ^ ¬ W12 ^ ¬ W21, and ¬S11 which will
give the output ¬ W11 ^ W12 ^ W12.
2. Apply And-Elimination Rule:

 After applying And-elimination rule to ¬ W11 ∧ ¬ W12 ∧ ¬ W21, we will get three statements:
¬ W11, ¬ W12, and ¬W21.
3. Apply Modus Ponens to ¬S21, and R2:

lOMoARcPSD|45814754
 Now we will apply Modus Ponens to ¬S21 and R2 which is ¬S21 → ¬ W21 ∧¬ W22 ∧ ¬ W31, which will
give the Output as ¬ W21 ∧ ¬ W22 ∧¬ W31
4. Apply And -Elimination rule:

 Now again apply And-elimination rule to ¬ W21 ∧ ¬ W22 ∧¬ W31, We will get three statements:
¬ W21, ¬ W22, and ¬ W31.
5. Apply MP to S12 and R4:
 Apply Modus Ponens to S12 and R4 which is S12 → W13 ∨. W12 ∨. W22 ∨.W11, we will get the output
as W13∨ W12 ∨ W22 ∨.W11.
6. Apply Unit resolution on W13 ∨ W12 ∨ W22 ∨W11 and ¬ W11 :

 After applying Unit resolution formula on W13 ∨ W12 ∨ W22 ∨W11 and ¬ W11 we will get W13 ∨ W12 ∨
W22.
7. Apply Unit resolution on W13 ∨ W12 ∨ W22 and ¬ W22 :

 After applying Unit resolution on W13 ∨ W12 ∨ W22, and ¬W22, we will get W13 ∨ W12 as output.

lOMoARcPSD|45814754
8. Apply Unit Resolution on W13 ∨ W12 and ¬ W12 :

 After Applying Unit resolution on W13 ∨ W12 and ¬ W12, we will get W13 as an output, hence it is
proved that the Wumpus is in the room [1, 3].

Unit 2

Uploaded by

Copyright:

Available Formats

Unit 2

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 2

Uploaded by

Copyright:

Available Formats

lOMoARcPSD|45814754

Unit II Full notes - Artifical intelligence

Artificial Intelligence (Visvesvaraya Technological University)

Scan to open on Studocu

Studocu is not sponsored or endorsed by any college or university

UNIT – II: Problem Solving by Search-II and Propositional Logic

Multiple Agent Environments:

• Adversarial search is a game-playing technique where the agents are surrounded by a

Factors In Game Theory:

Downloaded by Sriram Kuriseti ([email protected])

Factors associated with the game theory are:

Types of games in Al:

• Zero-sum games are adversarial search which involves pure competition.

Downloaded by Sriram Kuriseti ([email protected])

Formalization of the problem:

• Initial state: It specifies how the game is set up at the start.

• Player(s): It specifies which player has moved in the state space.

• Action(s): It returns the set of legal moves in state space.

Example: Tic-Tac-Toe game tree

• There are two players MAX and MIN.

• Players have an alternate turn and start with MAX.

• MAX maximizes the result of the game tree

• MIN minimizes the result.

Downloaded by Sriram Kuriseti ([email protected])

Hence adversarial Search for the minimax procedure works as follows:

• It follows the approach of Depth-first search.

Downloaded by Sriram Kuriseti ([email protected])

3. TYPES OF ALGORITHMS IN ADVERSARIAL SEARCH:

• Adversarial search is a game-playing technique where the agents are surrounded by a

Working of MIN-MAX Algorithm:

Downloaded by Sriram Kuriseti ([email protected])

Pseudo code for Minimax Algorithm:

Downloaded by Sriram Kuriseti ([email protected])

Downloaded by Sriram Kuriseti ([email protected])

Limitations of MIN-MAX Algorithm:

Downloaded by Sriram Kuriseti ([email protected])

Conditions of Alpha-Beta Pruning:

The main condition which required for alpha-beta pruning is:

Key points about Alpha-Beta Pruning:

 The Max player will only update the value of alpha.

Pseudo code for Alpha-Beta Pruning:

if MaximizingPlayer then // for Maximizer Player

Downloaded by Sriram Kuriseti ([email protected])

else // for Minimizer player

Working of Alpha-Beta Pruning:

Downloaded by Sriram Kuriseti ([email protected])

Downloaded by Sriram Kuriseti ([email protected])

Downloaded by Sriram Kuriseti ([email protected])

Example 2 and Solution:

Example 3 and Solution:

Downloaded by Sriram Kuriseti ([email protected])

Example 4 and Solution:

4. IMPERFECT REAL-TIME DECISIONS:

• Moves must be made in a reasonable amount of time.

Replace using heuristic evaluation function EVAL

Downloaded by Sriram Kuriseti ([email protected])

• EV is the probability-weighted average of all possible events.

Downloaded by Sriram Kuriseti ([email protected])

Cutting off search: