AN INTRODUCTION OF AI & SEARCHING TECHIQUES

Prepared By- Dr Shikha Pandey
1
Bhilai Institute of Technology, Durg
DEPARTMENT OF COMPUTER SCIENCE &
ENGINEERING
Artificial Intelligence
UNIT I: Overview & Search Techniques

Syllabus :- UNIT 1
• Introduction to AI
• Well Defined Problem representation and solving
• State space search
• Blind search: Depth first search, Breadth first search
• Informed search: Heuristic function, Hill
climbing search, Best first search, A* & AO*Search
• Game tree, Evaluation function, Mini-Max search,
Alpha-beta pruning.
Prepared By- Dr Shikha Pandey 2

What is Artificial intelligence?
• It is the science and engineering of
making intelligent machines, especially
intelligent computer programs. It is related
to the similar task of using computers to
understand human intelligence.
• ―Intelligence implies that a machine must
be able to adapt to new situations‖

– Ability to learn
– Ability to think abstractly
– To solve problems
– To percieve relationship
– To adjust to one’s environment
– To profit by experience

Definition of AI
• ―John McCarthy ― gives in 1956 ―Developing computer
programs to solve complex problems by applications of
processes that are analogous to human reasoning
processes
• ―Ai is the branch of computer science that is concerned
with the automation of intelligent behavior.‖
• AI is the study of how to make computers do things
which, at the moment, people do better.

• the intelligent is behavior , when we call this man
Intelligent, we mean by that (he have the ability to Think,
understand, learn and make decision) so if we a
combine this word with system to become (Intelligent
System(IS))we mean by that , the system able to (Think,
understand, learn and make decision) in other word :

AI Tree
Fruits: Applications
Branches: Expert Systems, Natural
Language processing, Speech
Understanding, Robotics and Sensory
Systems, Computer Vision, Neural
Computing, Fuzzy Logic, GA
Roots: Psychology, Philosophy,
Electrical Engg, Management Science,
Computer science, Linguistics

Difference between AI & conventional S/W
Features AI programs Conventional
s/w
Processing type Symbolic type Numeric
Technique used Heuristic search Algorithm search
Solutions steps Indefinite definite
Answers sought Satisfactory Optimal
Knowledge Imprecise Precise
Modification Frequent Rare
Involves Large knowledge Large DB
Process Inferential repetitive

Areas of Artificial Intelligence
• . Perception
– Machine vision
– Speech understanding
– Touch ( tactile or haptic) sensation
• Robotics
• Natural Language Processing
– Natural Language Understanding
– Speech Understanding
– Language Generation
– Machine Translation
• Planning
• Expert Systems
• Machine Learning
• Theorem Proving
• Symbolic Mathematics
• Game Playing

Advantages of Artificial Intelligence
• High Accuracy with less errors: AI machines or systems are prone to less errors
and high accuracy as it takes decisions as per pre-experience or information.
• High-Speed: AI systems can be of very high-speed and fast-decision making,
because of that AI systems can beat a chess champion in the Chess game.
• High reliability: AI machines are highly reliable and can perform the same action
multiple times with high accuracy.
• Useful for risky areas: AI machines can be helpful in situations such as defusing a
bomb, exploring the ocean floor, where to employ a human can be risky.
• Digital Assistant: AI can be very useful to provide digital assistant to the users such
as AI technology is currently used by various E-commerce websites to show the
products as per customer requirement.
• Useful as a public utility: AI can be very useful for public utilities such as a self-
driving car which can make our journey safer and hassle-free, facial recognition for
security purpose, Natural language processing to communicate with the human in
human-language, etc.
•

Disadvantages of Artificial Intelligence
• High Cost: The hardware and software requirement of AI is very
costly as it requires lots of maintenance to meet current world
requirements.
• Can't think out of the box: Even we are making smarter machines
with AI, but still they cannot work out of the box, as the robot will
only do that work for which they are trained, or programmed.
• No feelings and emotions: AI machines can be an outstanding
performer, but still it does not have the feeling so it cannot make any
kind of emotional attachment with human, and may sometime be
harmful for users if the proper care is not taken.
• Increase dependency on machines: With the increment of
technology, people are getting more dependent on devices and
hence they are losing their mental capabilities.
• No Original Creativity: As humans are so creative and can imagine
some new ideas but still AI machines cannot beat this power of
human intelligence and cannot be creative and imaginative.
• Prepared By- Dr Shikha Pandey 13

Difference Between Rational and Irrational/Non-rational
Reasoning/Thinking
Rational Irrational/Non-rational
•Rational thinking can be defined as a
thinking process which is based on
reason and logic.
• It can be defined as a thinking
process where the individual
completely disregards reason and
logic in favour of emotion.
• based on Power of Emotions:
• Rational thinking is driven by
experience and facts.
• Rational thinking allows the person to
succeed.
•Based on power of brain
• Irrational thinking is driven by
emotion.
• Irrational thinking works as a barrier
which hinders the success of the
individual.

How problems can be represented in AI
• Before a solution can be found the prime
condition is that the problem must be very
precisely defined.
• So to build a system to solve a particular
problem, we need to do four things.

How problems can be represented in AI
1. Define the problem precisely. like what is
initial situation, what will be the final,
acceptable solutions.
2. Analyze the problem. various possible
techniques for solving the problem.
3. Isolate and represent the task knowledge
that is necessary to solve the problem.
4. Choose the best problem solving
technique and apply it

The most common methods of problem
representation in AI
State space representation
―A set of all possible states for a given
problem is known as the state space of the
problem.‖
or
―A state space represents a problem in
terms of states and operators that change
states.‖

A problem space consists of
1. Precondition/An initial state
2. Post condition/Final states
3. Actions
4. Total Cost

State Space Search: Summary
1. Define a state space that contains all the
possible configurations of the relevant
objects.
2. Specify the initial states.
3. Specify the goal states.
4. Specify a set of rules:
- What are unstated assumptions?
- How general should the rules be?
- How much knowledge for solutions should be in the
rules? Prepared By- Dr Shikha Pandey 20

For example
If one wants to make a cup of coffee.
What one have to do:
analyze the problem
check necessary ingredients are available or not.
if they are available.

Water jug problem?
• States– amount of water in both jugs.
• Actions—Empty large/small, pour from large/small
• Goal—specified amount of water in both jug
• Path cost—total no of actions applied

State Space Search: Playing
Chess
• State space is a set of legal positions.
• Starting at the initial state.
• Using the set of rules to move from one
state to another.
• Attempting to end up in a goal state.

State Space Search: Water Jug Problem
―You are given two jugs, a 4-litre one and a 3-litre
one. Neither has any measuring markers on it.
There is a pump that can be used to fill the jugs
with water. How can you get exactly 2 litres of
water into 4-litre jug.‖

State Space Search: Water Jug
Problem
• State: (x, y)
x = 0, 1, 2, 3, or 4 y = 0, 1, 2, 3
• Start state: (0, 0).
• Goal state: (2, n) for any n.
• Attempting to end up in a goal state.

Problem
1. (x, y)  (4, y)
if x  4
2. (x, y)  (x, 3)
if y  3
3. (x, y)  (x - d, y)
if x  0
4. (x, y)  (x, y - d)
if y  0

Problem
5. (x, y)  (0, y)
if x  0
6. (x, y)  (x, 0)
if y  0
7. (x, y)  (4, y - (4 - x))
if x  y  4, y  0
8. (x, y)  (x - (3 - y), 3)
if x  y  3, x  0

Problem
9. (x, y)  (x  y, 0)
if x  y  4, y  0
10. (x, y)  (0, x  y)
if x  y  3, x  0
11. (0, 2)  (2, 0)
12. (2, y)  (0, y)

Problem
1. current state = (0, 0)
2. Loop until reaching the goal state (2, 0)
- Apply a rule whose left side matches the current state
- Set the new current state to be the resulting state
(0, 0)
(0, 3)
(3, 0)
(3, 3)
(4, 2) Prepared By- Dr Shikha Pandey 30

Problem
The role of the condition in the left side of
a rule
 restrict the application of the rule
 more efficient
1. (x, y)  (4, y)
if x  4
2. (x, y)  (x, 3)
if y  3 Prepared By- Dr Shikha Pandey 31

Find a driving route from city A to city B
• States– location specified by city .
• Actions– driving along the roads between cities
• Goal— city B
• Path cost—total distance or expected travel time.

• Example: Consider a 4-puzzle
problem, where in a 4-cell board
there are 3 cells filled with digits
and 1 blank cell. The initial state of
the game represents a particular
orientation of the digits in the cells
and the final state to be achieved
is another orientation supplied to
the game player. The problem of
the game is to reach from the
given initial state to the goal (final)
state, if possible, with a minimum
of moves. Let the initial and the
final state be as shown in figures
1(a) and (b) respectively.
We now define two operations, blank-up
(BU) / blank-down (BD) and blank-left (BL)
/ blank-right (BR), and the state-space
(tree) for the problem is presented below
using these operators. The algorithm for
the above kind of problems is
straightforward. It consists of three steps,
described by steps 1, 2(a) and 2(b) below.

Pegs and Disks problem
• Consider the following problem. We have
3 pegs and 3 disks.
• Operators: one may move the topmost
disk on any needle to the topmost position
to any other needle
• In the goal state all the pegs are in the
needle B as shown in the figure below.

Initial State/Goal state

• Now we will describe a sequence of actions that
can be applied on the initial state.
• Step 1: Move A → C
• Step 2: Move A → B
• Step 3: Move A → C
• Step 4: Move B→ A
• Step 5: Move C → B
• Step 6: Move A → B
• Step 7: Move C→ B

8 queens problem
• The problem is to place 8 queens on a
chessboard so that no two queens are in
the same row, column or diagonal

Problem space?

4- queens problem
X
X
X
X

N queens problem formulation
• States: Any arrangement of 0 to 8 queens
on the board
• Initial state: 0 queens on the board
• Successor function: Add a queen in any
square
• Goal test: 8 queens on the board, none are
attacked

One solution

8 puzzle problem

Missionaries & Cannibals Problem
• Missionaries & Cannibals problem: 3 missionaries & 3
cannibals are on one side of the river. 1 boat carries 2.
Missionaries must never be outnumbered by cannibals. Give a
plan for all to cross the river. State: <M, C, B>
• M: no of missionaries on the left bank
• C: no of cannibals on the left bank
• B: position of the boat: L or R
• Initial state: <3, 3, L>
• Goal state: <0, 0, R>
• Operators: <M,C> ► M: No of missionaries on the boat
• ► C: No of cannibals on the boat
• Valid operators: <1,0> <2,0>, <1,1>, <0,1> <0,2>

Homework
Assignment:
1: Explain the history of AI
2: Analyse each of them and solve using AI
problem solving techniques
(a) Missionaries and cannibals
(b) 8-puzzle

What is a Production System?
• A PS is a computer program typically
used to provide some form of AI, which
consists a set of rules about behavior.
• A PS provides the mechanism necessary
to execute productions in order to achieve
some goal for the system.
• Used as the basis for many rule-based
expert systems

What is a Production System?
• A production system consists of four
basic components:
1. A set of rules of the form Ci ® Ai or
C1, C2, … Cn => A1 A2 …Am
Left hand side (LHS) Right hand side (RHS)
Conditions/antecedents Conclusion/consequence
where Ci is the condition part and Ai is the action
part.

1. The condition determines when a given rule is applied, and the
action determines what happens when it is applied.
2. knowledge databases/ working memory that contain whatever
information is relevant for the given problem & also maintains data
about current state or knowledge. Some parts of the database may
be permanent, while others may temporary and only exist during the
solution of the current problem. The information in the databases
may be structured in any appropriate manner.
3. A control strategy that determines the order in which the rules are
applied to the database, and provides a way of resolving any
conflicts that can arise when several rules match at once.
4. A rule applier which is the computational system that implements
the control strategy and applies the rules.

Production rule for water jug problem
1. (x, y)  (4, y), If x < 4 fill the 4-gallon jug.
2. (x, y)  (x,3), If y < 3 fill the 3-gallon jug.
3. (x, y)  (x- d , y), If x > 0 pour some water out of the 4-gallon jug
4. (x, y)  (x, y - d), If y > 0 pour some water out of the 4-gallon jug
5. (x, y)  (0, y) If x > 0 empty the 4-gallon jug.
6. (x, y)  (x, 0), If y > 0 empty the 3-gallon jug.
7. (x, y)  (4, y – (4 – x) ), if x + y >= 4 & y > 0 pour water from the
3-gallon jug into the 4-gallon jug
until the 4-gallon jug is full.
8. (x, y)  (x – (3 – y), 3 ), if x + y >= 4 & y > 0 pour water from the
4-gallon jug into the 3-gallon jug until
the 3-gallon jug is full.

Production rule for water jug problem
9. (x, y)  (x + y, 0 ), if x + y <= 4 & y > 0 pour all the
water from the 3-gallon jug
into the 4-gallon jug.
10. (x, y)  (0, x + y), if x + y <= 3 & x > 0 pour all the
water from the 4-gallon
jug into the 3-gallon jug.
11. (0, 2)  (2, 0), pour 2-g from 3-g to 4-g
12. (2, y)  (0, y)

One solution of water jug problem
Rule applied 4-Gallon 3-Gallon
Initial state 0 0
Rule 2 0 3
Rule 9 3 0
Rule 2 3 3
Rule 7 4 2
Rule 5 or 12 0 2
Rule 9 or 11 2 0

Problem of Conflict Resolution
• When there are more then one rule that
can be fired in a situation and the rule
interpreter can not be decide which is to
be fired, what is the order of triggering and
whether to apply it .

Some Resolution Strategies
• Perform the first. the system chooses the first rule that
matches.
• Sequencing techniques. adopt the rules in the
sequence they are.
• Perform the most specific. if there are two matching
rules and one rule is more specific than the other, activate the most
specific.
• Most recent policy. chooses newly added rule.

• Search  process of locating a solution to a
problem by any method in a search tree or
search space until a goal node is found.
• Search Space  A set of possible permutation
that can be examined by any search method in
order to find solution.
• Search Tree  A tree that is used to represent a
search problem and is examined by search
method to search for a solution.

To do a search process the following are
needed :--
The initial state description.
A set of legal operators.
The final or goal state.

Search Tree – Terminology
• Root Node: The node from which the search starts.
• Leaf Node: A node in the search tree having no children.
• Ancestor/Descendant: X is an ancestor of Y is either X is Y’s parent
or X is an ancestor of the parent of Y. If S is an ancestor of Y, Y is
said to be a descendant of X.
• Branching factor: the maximum number of children of a non-leaf
node in the search tree
• Path: A path in the search tree is a complete path if it begins with
the start node and ends with a goal node. Otherwise it is a partial
path.
• We also need to introduce some data structures that will be used in
the search algorithms.

Evaluating Search strategies
• We will look at various search strategies
and evaluate their problem solving
performance. What are the characteristics
of the different search algorithms and what
is their efficiency? We will look at the
following three factors to measure this.

Search Strategy Evaluation
1. Completeness: We will say a search method is ―complete‖
if it has both the following properties:
if a goal exists then the search will always find it
if no goal exists then the search will eventually finish and be able
to say that no goal exists
2. Time complexity: how long does it take?( number of nodes
expanded)
3. Space complexity: how much memory is needed?
4. Optimality: is a high-quality solution found? Does the solution have
low cost or the minimal cost? What is the search cost associated
with the time and memory required to find a solution?

Types of Search
• Uninformed or blind or Brute force search
or Exhaustive Search
– No information about the number of steps
– No information about the path cost
– blind search or uninformed search that does
not use any extra information about the
problem domain.
• Informed or heuristic search
– Information about possible path costs or
number of steps is used

Uninformed Search
Breadth-first search
• Root node is expanded
first
• All nodes at depth d in the
search tree are expanded
before the nodes at depth
d+1
• Implemented by putting all
the newly generated
nodes at the end of the
queue
s
1 2
3 4
7 8 9 10 11 12 13 14
5 6

Breadth first search queues
Loopno nodes expanded
0 [s] 
1 [1 2] [s]
2 [2 3 4] [1 s]
3 [3 4 5 6] [2 1 s]
4 [4 5 6 7 8] [3 2 1 s]
5 [5 6 7 8 9 10] [4 3 2 1 s]
6 [6 7 8 9 10 11 12] [5 4 3 2 1 s]
: : :

Algorithm of BFS
Step 1: put the initial node on a list S.
Step 2 : if ( S is empty) or (S = goal) terminate
search.
Step 3 : remove the first node from S. call this
node a.
Step 4 : if (a = goal) terminate search with
success.
Step 5 :Else if node a has successor, generate all
of them and add them at the tail of S.
Step 6 : go to to step 2.

A
C D E F
B
G H I J K L M N O P
Q R S T U V W X Y Z
The example node set
Initial state
Goal state
A
L
Press space to see a BFS of the example node set

A
C D E F
B
G H I J K L
Q R S T U
A
B C D
We begin with our initial state: the node
labeled A. Press space to continue
This node is then expanded to reveal
further (unexpanded) nodes. Press space
Node A is removed from the queue. Each
revealed node is added to the END of the
queue. Press space to continue the search.
The search then moves to the first node
in the queue. Press space to continue.
Node B is expanded then removed from the
queue. The revealed nodes are added to the
END of the queue. Press space.
Size of Queue: 0
Nodes expanded: 0 Current Action: Current level: n/a
Queue: Empty
Queue: A
Size of Queue: 1
Nodes expanded: 1
Queue: B, C, D, E, F
Press space to begin the search
Size of Queue: 5
Current level: 0
Current Action: Expanding
Queue: C, D, E, F, G, H
Size of Queue: 6
Nodes expanded: 2 Current level: 1
We then backtrack to expand node C,
and the process continues. Press space
Current Action: Backtracking Current level: 0
Current level: 1
Queue: D, E, F, G, H, I, J
Size of Queue: 7
Nodes expanded: 3 Current Action: Expanding
Current level: 1
Queue: E, F, G, H, I, J, K, L
Size of Queue: 8
Nodes expanded: 4 Current Action: Expanding
Current level: 1
N
M
Queue: F, G, H, I, J, K, L, M, N
Size of Queue: 9
Nodes expanded: 5
E
Current Action: Expanding Current level: 1
O P
Queue: G, H, I, J, K, L, M, N, O, P
Size of Queue: 10
Nodes expanded: 6
F
Current level: 1
Current level: 2
Queue: H, I, J, K, L, M, N, O, P, Q
Nodes expanded: 7
G
Queue: I, J, K, L, M, N, O, P, Q, R
Nodes expanded: 8
H
Current level: 1
Current level: 0
Current level: 1
Current level: 2
Queue: J, K, L, M, N, O, P, Q, R, S
Nodes expanded: 9
I
Current level: 2
Queue: K, L, M, N, O, P, Q, R, S, T
Nodes expanded: 10
J
Current level: 0
Current level: 1
Current level: 2
Queue: L, M, N, O, P, Q, R, S, T, U
Nodes expanded: 11
K
L
L
L
L
Node L is located and the search returns
a solution. Press space to end.
FINISHED SEARCH
Queue: Empty
Size of Queue: 0
Current level: 2
BREADTH-FIRST SEARCH PATTERN
L
Press space to continue the search

Time Complexity :
1 + b + b2 + b3 +…+……bd.
Hence Time complexity = O (bd)
Space Complexity :
1 + b + b2 + b3 +…+……bd.

Uninformed Search
Breadth-first search
• Breadth-first search merits
– Complete: If there is a solution, it will be found
– Optimal: Finds the nearest goal state
• Breadth-first search problem:
• Time complexity
• Memory intensive
• Remembers all unwanted nodes

show how breadth first search works on this graph.

• Breadth first search is:
• Complete. : The algorithm is optimal (i.e., admissible) if all
operators have the same cost. Otherwise, breadth first search finds
a solution with the shortest path length.
• The algorithm has exponential time and space complexity. Suppose
the search tree can be modeled as a b-ary tree as shown in Figure
3. Then the time and space complexity of the algorithm is O(bd)
where d is the depth of the solution and b is the branching factor
(i.e., number of children) at each node.
• A complete search tree of depth d where each non-leaf node has b
children, has a total of 1 + b + b2 + ... + bd = (b(d+1) - 1)/(b-1) nodes

Uninformed Search
Depth-first search
• Always expands one of
the node at the deepest
level of the tree
• Only returns when the
search hits a dead end
• Implemented by putting
the newly generated
nodes at the front of the
queue
s
1 2
3 4
5 6 7 8 11 12 13 14
9 10

Depth first search queues
Loopno nodes expanded
0 [s] 
1 [1 2] [s]
2 [3 4 2] [1 s]
3 [5 6 4 2] [3 1 s]
4 [6 4 2] [5 3 1 s]
5 [4 2] [6 5 3 1 s]
6 [7 8 2] [4 6 5 3 1 s]
: : :

Algorithm of DFS
Step 1: put the initial node on a list S.
Step 2 : if ( S is empty) or (S = goal) terminate
search.
Step 3 : remove the first node from S. call this
node a.
Step 4 : if (a = goal) terminate search with
success.
Step 5 :Else if node a has successor, generate all
of them and add them at the beginning of
S.
Step 6 : go to to step 2.

Time Complexity :
1 + b + b2 + b3 +…+……bd.
Space Complexity :
Hence Time complexity = O (d)

Uninformed Search
Depth-first search
• Depth-first search merits
– Modest memory requirements: only the
current path from the root to the leaf node
needs to be stored.
– Time complexity
• With many solutions, depth-first search is often
faster than breadth-first search, but the worst
case is still O (bm)

―It is defined as a method that provide a
better guess about the correct choice to
make at any junction that would be
achieved by random guessing.‖ OR
―It is defined as a method or as a rule or as
a trick. it is a piece of information that is
used to make search or another problem
solving method, more effective and more
efficient.‖

A heuristic is a method that
• Might not always find the best solution.
• But is guaranteed to find a good solution in
reasonable time.
• Heuristics are approximation used to minimize
the search process
• Useful in solving tough problems which
-- could not be solved any other way.
-- solutions take an infinite time or very long
time to compute.

• Heuristic function : a function that estimate
the value of a state, It is an approximation
used to minimize the search process .
• Heuristic Knowledge : knowledge of
approaches that are likely to work or of
properties that are likely to be true (but not
guaranteed).

Example of Heuristic Function
• A heuristic function at a node n is an estimate of the
optimum cost from the current node to a goal. It is
denoted by h(n).
h(n) = estimated cost of the cheapest path from node n to a
goal node
Example 1: We want a path from Kolkata to Guwahati
• Heuristic for Guwahati may be straight-line distance
between Kolkata and Guwahati
• h(Kolkata) = euclideanDistance(Kolkata, Guwahati)
Example 2: 8-puzzle: Misplaced Tiles Heuristics is the
number of tiles out of place.

• The first picture shows the current state n, and the
second picture the goal state.
• h(n) = 5
• because the tiles 2, 8, 1, 6 and 7 are out of place.
• Manhattan Distance Heuristic: Another heuristic for 8-
puzzle is the Manhattan distance heuristic. This heuristic
sums the distance that the tiles are out of place. The
distance of a tile is measured by the sum of the
differences in the x-positions and the y-positions.
• For the above example, using the Manhattan distance
heuristic,
• h(n) = 1 + 1 + 0 + 0 + 0 + 1 + 1 + 1 + 1 = 6

Hill Climbing Algorithm
• Hill climbing is a graph search algorithm where the current path is extended
with a successor node which is closer to the solution than the end of the
current path.
• In simple hill climbing, the first closer node is chosen whereas in steepest
ascent hill climbing all successors are compared and the closest to the
solution is chosen.
• Both forms fail if there is no closer node. This may happen if there are local
maxima in the search space which are not solutions. Steepest ascent hill
climbing is similar to best first search but the latter tries all possible
extensions of the current path in order whereas steepest ascent only tries
one.
• Hill climbing is sometimes called greedy local search because it grabs a
good neighbor state without thinking ahead about where to go next.
• Hill climbing often makes very rapid progress towards a solution, because it
is usually quite easy to improve a bad state. Unfortunately, hill climbing
often gets stuck for the following reasons:

1. Local Maxima:
A local maximum is a peak that is higher than each of its
neighboring states, but lower than the global maximum.
Hill-climbing algorithms that reach the vicinity of a local
maximum will be drawn upwards towards the peak, but
will then be stuck with nowhere else to go.
2. Ridges:
Ridges result in a sequence of local maxima that is very
difficult for greedy algorithms to navigate.

3. Plateaux:
A plateau is an area of the state space landscape where the evaluation
function is flat. It can be a flat local maximum, from which no uphill
exit exists, or from which it is possible to make progress.
Hill climbing operate on complete-state formulations, keeping only a
small number of nodes in memory
Hill climbing is used widely in artificial intelligence fields, for reaching a
goal state from a starting node. Choice of next node/ starting node
can be varied to give a list of related algorithms.
The problem with hill climbing is that it may find only local maxima.
Unless the heuristic is good / smooth, it doesn’t reach global
maxima.

Best first search
• A combination of DFS & BFS.
• DFS is good because a solution can be
found without computing all nodes and
BFS is good because it doesn’t get
trapped in dead ends.
• The best first search allows us to switch
between paths going the benefit of both
approaches.

How it works
• The algorithm maintains two list, one containing
a list of candidate yet to explore -- OPEN
• One containing a list of visited node – CLOSED
• Since all unvisited successor nodes of every
visited node are included in the OPEN list.
• It takes the advantage s of both DFS and
BrFS.—faster.

S
A
B
C
D
E
F
G
H
I
J
K
L
M
3
6
5
9
8
12
14
7
5
6
1
Q
2

Ste
p
Node
being
expan
ded
Children Available
Node
Node
chosen
1 S (A:3)(B:6)(c:5) (A:3)(B:6)(c:5) (A;3)
2 A (D:9)(E:8) (B:6)(c:5) (D:9)(E:8) (C:5)
3 C (H:7) (B:6) (D:9) (E:8) (H:7) (B:6)
4 B (E:12) (G:14) (E:12) (G:14) (D:9) (E:8) (H:7) (H:7)
5 H (I;5) (J:6) (E:12) (G:14) (D:9) (E:8) (I;5)
(J:6)
(I:5)
6 I K L M All L

A * algorithm
• This algorithm was given by hart Nilsson &
Rafael in 1968.
• A* is a best first search algorithm with
f(n) = g(n) + h(n)
Where
g(n) = sum of edge costs from start to n
h(n) = estimate of lowest cost path from n to goal
• f(n) = actual distanance so far + estimated
distance remaining

ANIMATION OF A*.
A
O
Z
F
N
I
V
H
Eforie
U
G
P
S
D
C
R
M
T
L
87
92
142
86
98
86
211
101
90
99
71
75
140
118
111
70
75
120
138
146
97
80
140
B
99+178=277
80+193=273
140+366=506
177+98=275
226+160=386(R)
310+0=310 (F)
Optimal route is (80+97+101) = 278 miles
1.S
278+0=278 (R,P)
2.R 3.P 4.F 5.B 278 GOAL!!
Fringe in RED
Visited in BLUE
Nodes Expanded
0+253=253
Annotations:
“g+h=f”
could use 211?
315+160=475(R)

A* SEARCH TREE
Press space to begin the search
140
80
99
In terms of a search tree we could represent this as follows ....
5
The goal state is achieved.
In relation to path cost, A* has found
the optimal route with 5 expansions.
Press space to end.
S.
0+253
=253
P
177+98
=275
A
140+366
=506
F
99+178
=277
R
80+193
=273
B
310+0
=310
Maths:
“g + h = f”
2 3
4
1
B
278+0
=278
C
226+160
=386
C
315+160
=475
138
101
211
146
97

Memory Usage of A*
• We store the tree in order to
– to return the route
– avoid repeated states
• Takes a lot of memory
• But scanning a tree is better with DFS

Constraint Satisfaction

What is a constraint problem?
• A constraint problem is a task where you have
to
– Arrange objects
– Schedule tasks
– Assign values
– …
– subject to a number of constraints

Example of constraint problems
S E N D
M O R E
M O N E Y
+
Each letter stands for a different
digit. Assign digits to the letters so
that the sum is correct.
Cryptarithmetic problems:
Constraint: when the values are assigned, the sum
must add up correctly.

SOLUTIONS
SEND
+ MORE
MONEY
9 5 6 7
+ 1 0 8 5
1 0 6 5 2

Some easy examples
• AS + A = MOM
• I + DID = TOO
• A + FAT = ASS
• SO + SO = TOO
• US + AS = ALL
• ED + DI = DID
• DI + IS = ILL

U S
+ A S
A L L
8 5
+ 1 5
1 0 0

1. CROSS
+ ROADS
DANGER
2.
TWO
+ TWO
FOUR

Another example
The 8 Queens puzzle
Place 8 queens on a chessboard
so that no two queens are
attacking one another.
Constraints: no two queens must be on the same row, the same
column, or the same diagonal

Example: Map-Coloring Problem
- Variables: WA, NT, Q, NSW, V, SA, T
- Domains: Di= {red, green, blue}
- Constraints: neighboring regions must have different colors
4

Example: Map-Coloring Problem
• Solutions: assignments satisfying all constraints, e.g.,
{WA=red, NT=green, Q=red, NSW=green, V=red, SA=blue, T=green}
5

A more practical example
• Timetabling/scheduling
– Assign classes to rooms so that
• Students aren’t required to be in two different rooms at the same
time
• Similarly for lecturers
• Two classes aren’t booked into the same room at the same time
• Rooms are sufficiently large to hold classes assigned to them
• Labs have enough computers for the classes assigned to them
• …

Formal definition of a constraint problem
• A constraint problem consists of
– A set of variables x1, x2,… xn
– For each variable xi a finite set Di of its possible
values (its domain)
– A set of constraints restricting the values that the
variables can take
• Goal: find an assignment of values to the
variables which satisfies all the constraints

Summary
• Constraint problem-solving can be applied to
a wide variety of real-world problems
• Formally, a constraint problem consists of
– A set of variables and their domains
– A set of constraints
• The goal
– Find a valid set of values
– Find all sets of values
– Find the best set of values
• The method
– Combine search and constraint propagation

Games and AI
• Games were one of the first tasks undertaken
by researchers in AI field
• A. Turing wrote chess playing program in 1950's
• Why research on games continues?
➢ Long-standing fascination for games
➢ Some difficult games remain to be won by computers

Game Trees
● Formal Description of Game :
• Initial State
• Successor function
• Terminal State
• Utility function
● Games are represented by game trees in which
● Each node represents a position
● Each link represents a legal move
● Leaf nodes are final positions(Win,Loss or Draw)
● The aim is to reach the goal node from the root node.

Types of Games
• Two player vs. Multiplayer
Tic-Tac-Toe vs. Bridge
• Zero-sum vs. General-sum
Chekers vs. Auction
• Perfect information vs. Imperfect information
Othello vs. Bridge
• Deterministic vs. Chance
Chess vs. Backgammon

Search Procedures
● Generate using simple legal-move generator will result
in very large testing space for the tester.
● So use plausible move generator.
● Now test procedure can spend more time evaluating
each of the moves, so more reliable results.

Search Procedures
● In order to choose the best move, the resulting board
position must be compared to discover which is most
advantageous -
● Use Static Evaluation Function (Utility
Function)
● It estimates how likely the particular state can
eventually lead to a win.

Minimax Search Procedure
● Depth-limited.
● Use plausible move generator to generate set of
possible successor positions.
● Apply static evaluation function to those positions &
choose the best one.
● Back up that value to the starting point.

Minimax Example
Min
4 7 9 6 9 8 8 5 6 7 5 2 3 2 5 4 9 3

Max
Max
Min
Min
7 9 6 9 8 8 5 6 7 5 2 3 2 5 4 9 3
7 6 2 6 3 4 5 1 2 5 4 1 2 6 3 4 3
Minimax Example

Max
Max
Min
Min
7 9 6 9 8 8 5 6 7 5 2 3 2 5 4 9 3
7 6 2 6 3 4 5 1 2 5 4 1 2 6 3 4 3
7 6 5 5 6 4
Minimax Example

Max
Max
Min
Min
7 9 6 9 8 8 5 6 7 5 2 3 2 5 4 9 3
7 6 2 6 3 4 5 1 2 5 4 1 2 6 3 4 3
7 6 5 5 6 4
5 3 4
Minimax Example

Max
Max
Min
Min
4 7 9 6 9 8 8 5 6 7 5 2 3 2 5 4 9 3
4 7 6 2 6 3 4 5 1 2 5 4 1 2 6 3 4 3
7 6 5 5 6 4
5 3 4
5
Minimax Example

Max
Max
Min
Min
7 9 6 9 8 8 5 6 7 5 2 3 2 5 4 9 3
7 6 2 6 3 4 5 1 2 5 4 1 2 6 3 4 3
7 6 5 5 6 4
5 3 4
5
Minimax Example

Adding Alpha-Beta Cutoffs
● Requires maintanence of 2 threshold values -
● Alpha – lower bound on the value that a
maximized node may be assigned.
● Beta – upper bound on the value that a
minimizing node may be assigned.

● Search at the minimizing level can be terminated when
a value less than alpha is discovered.
● Search at the maximizing level can be terminated
when a value greater than beta is discovered.
● At maximizing levels, only beta is used to determine
whether to cut-off the search & similarly for minimizing
levels.
Adding Alpha-Beta Cutoffs

Alpha-beta pruning
• Alpha-beta pruning is a technique used in
artificial intelligence (AI) to reduce the number of
nodes that need to be evaluated in a search
tree. It is commonly applied in game-playing
algorithms, particularly in adversarial search
scenarios like chess or checkers.
• Alpha-beta pruning significantly reduces the
number of nodes that need to be evaluated,
making it much more efficient than a simple
minimax search, especially in large game trees.

The two-parameter can be defined as:
1. 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 -∞.
2. Beta: The best (lowest-value) choice we have found so
far at any point along the path of Minimizer. The initial
value of beta is +∞.
• The Alpha-beta pruning to a standard minimax algorithm
returns the same move as the standard algorithm does,
but it removes all the nodes which are not really affecting
the final decision but making algorithm slow. Hence by
pruning these nodes, it makes the algorithm fast.
• The main condition which required for alpha-beta
pruning is: α>=β Prepared By- Dr Shikha Pandey 126

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.

AN INTRODUCTION OF AI & SEARCHING TECHIQUES

Recommended

Recommended

More Related Content

Similar to AN INTRODUCTION OF AI & SEARCHING TECHIQUES

Similar to AN INTRODUCTION OF AI & SEARCHING TECHIQUES (20)

Recently uploaded

Recently uploaded (20)

AN INTRODUCTION OF AI & SEARCHING TECHIQUES