21CS502- ARTIFICIAL

INTELLIGENCE UNIT 2

D.M.KALAI SELVI
ASSISTANT PROFESSOR
R.M.D ENGINEERING COLLEGE
 UNIT 2 PROBLEM SOLVING
• Heuristic search strategies- heuristic functions- Game Playing- Mini-max
Algorithm – Optimal decisions in games Alpha-beta search- Monte-Carlo
search for Games - Constraint satisfaction problems- Constraint
propagation Backtracking search for CSP- Local search for CSP -
Structure of CSP
 MEMORY BOUNDED HEURISTIC
SEARCH
• The simplest way to reduce memory requirements for A∗ is iterative-
deepening A∗ (IDA∗) algorithm
• The main difference between IDA∗ and standard iterative deepening is
that the cutoff used is the f -cost (g + h) rather than the depth; at each
iteration, the cutoff value is the smallest f -cost of any node that exceeded
the cutoff on the previous iteration
MEMORY BOUNDED ALGORITHMS
• RECURSIVE BEST FIRST SEARCH
• MA *
PERFORMANCE EVAULATION-RBFS
• RBFS is an optimal algorithm if the heuristic function h(n) is admissible.
Its space complexity is linear in the depth of the deepest optimal solution
• But its time complexity is rather difficult to characterize: it depends both
on the accuracy of the heuristic function and on how often the best path
changes as nodes are expanded.
 DIFFERENCE BETWEEN RBFS AND
IDA*
IDA* RBFS

Between iterations, IDA∗ retains RBFS retains more information in memory,but it

only a single number: the current f -cost limit uses only linear space: even if more memory were
available, RBFS has no way to make use of it.
 DIFFERENCE BETWEEN RBFS AND
IDA*
• IDA∗ and RBFS suffer from using too little memory.
• Because they forget most of what they have done, both algorithms may
end up re-expanding the same states many times over. Furthermore, they
suffer the potentially exponential increase in complexity associated with
redundant paths in graphs
MEMORY – BOUNDED A* ALGORITHM

In order to use full available memory two algorithms were devised

• Memory bounded A* algorithm
• Simplified A* algorithm
SIMPLIFIED MEMORY A * ALGORITHM
• SMA∗ proceeds just like A∗, expanding the best leaf until memory is full.
• At this point, it cannot add a new node to the search tree without dropping an old one.
• SMA∗ always drops the worst leaf node—the one with the highest f -value.
• Like RBFS, SMA∗ then backs up the value of the forgotten node to its parent. In this
way, the ancestor of a forgotten subtree knows the quality of the best path in that
subtree.
• SMA∗ regenerates the subtree only when all other paths have been shown to look
worse than the path it has forgotten.
SIMPLIFIED MEMORY A * ALGORITHM

• To avoid selecting the same node for deletion and expansion, SMA∗
expands the newest best leaf and deletes the oldest worst leaf.
• If the leaf is not a goal node, then even if it is on an optimal solution path,
that solution is not reachable with the available memory. Therefore, the
node can be discarded exactly as if it had no successors.
 PERFORMANCE EVALUATION
• SMA∗ is complete if there is any reachable solution—that is, if d, the depth of the
shallowest goal node, is less than the memory size (expressed in nodes).
• It is optimal if any optimal solution is reachable; otherwise, it returns the best
reachable solution.
• ADVANTAGE
• SMA∗ is a fairly robust choice for finding optimal solutions, particularly when the
state space is a graph, step costs are not uniform, and node generation is expensive
compared to the overhead of maintaining the frontier and the explored set.
 META LEVEL STATE SPACE
• Each state in a metalevel state space captures the internal (computational)
state of a program that is searching in an object-level state space such as
Romania.
• OBJECT-LEVEL STATE SPACE state of the A∗ algorithm consists of the
current search tree. Each action in the metalevel state space is a
computation step that alters the internal state; for example, each
computation stepin A∗ expands a leaf node and adds its successors to the
tree.
 HEURISTIC FUNCTIONS
• A heuristic function or simply a
heuristic is a function that ranks
alternatives in various search
algorithms at each branching step
basing on an available information
in order to make a decision which
branch is to be followed during a
search.
 HEURISTIC FUNCTION
• The 8-puzzle is an example of Heuristic search problem.
• The object of the puzzle is to slide the tiles horizontally or vertically into the empty space until the
configuration matches the goal configuration
• The average cost for a randomly generated 8-puzzle instance is about 22 steps.
• The branching factor is about 3.(When the empty tile is in the middle, there are four possible moves; when
it is in the corner there are two; and when it is along an edge t here are three).
• This means that an exhaustive search to depth 22 would look at about 322 approximately =3.1 X 1010
states.
• By keeping track of repeated states, we could cut this down by a factor of about 170, 000, because there are
only 9!/2 = 181,440 distinct states that are reachable.
• This is a manageable number, but the corresponding number for the 15-puzzle is roughly 10^13.
 HEURISTIC FUNCTION
• If we want to find the shortest solutions by using A*,we need a heuristic function that never overestimates the
number of steps to the goal.
• The two commonly used heuristic functions for the 15-puzzle are :
• (1) h1 = the number of misplaced tiles.
• In the above figure all of the eight tiles are out of position, so the start state would have
• h1 = 8. h1 is an admissible heuristic.
• (2) h2 = the sum of the distances of the tiles from their goal positions. This is called the city block distance or
Manhattan distance.h2 is admissible ,because all any move can do is move one tile one step closer to the goal.
• Tiles 1 to 8 in start state give a Manhattan distance of h2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18.
• Neither of these overestimates the true solution cost, which is 26
 THE EFFECT OF HEURISTIC
ACCURACY ON PERFORMANCE
• One way to characterize the quality of a heuristic is the effective branching factor b*.
• If the total number of nodes generated by A* for a particular problem is N,and the
solution depth is d,then b* is the branching factor that a uniform tree of depth d would
have to have in order to contain N+1 nodes. Thus,
• N + 1 = 1 + b* + (b*)2+…+(b*)d
• For example, if A∗ finds a solution at depth 5 using 52 nodes, then the effective
branching factor is 1.92.
• A well-designed heuristic would have a value of b∗ close to 1, allowing fairly large
problems to be solved at reasonable computational cost.
 HEURISTIC FUNCTIONS
• To test the heuristic functions h1 and h2, we generated 1200 random problems
with solution lengths from 2 to 24 (100 for each even number) and solved them
with iterative deepening search and with A∗ tree search using both h1 and h2
• The results suggest that h2 is better than h1, and is far better than using
iterative deepening search. Even for small problems with d = 12, A ∗ with h2 is
50,000 times more efficient than uninformed iterative deepening search.
• h2 is always better than h1. for any node n, h2(n) ≥ h1(n).We thus say that h2
dominates h1
 HEURISTIC FUNCTIONS
• Generating admissible heuristics from relaxed problems
• A problem with fewer restrictions on the actions is called a relaxed
problem.
• The state-space graph of the relaxed problem is a supergraph
ofRELAXED PROBLEM the original state space because the removal of
restrictions creates added edges in the graph.
• the cost of an optimal solution to a relaxed problem is an admissible
heuristic for the original problem
Generating admissible heuristics from
subproblems: Pattern databases
 Generating admissible heuristics from
subproblems: Pattern databases
• Admissible heuristics can also be derived from the solution cost of a subproblem of a given
SUBPROBLEM.
• the cost of the optimal solution of this subproblem is a lower bound on the cost of the complete
problem
• The idea behind pattern databases is to store these exact solution costs for every possible
subproblem.
• Then we compute an admissible heuristic h DB for each complete state encountered during a
search simply by looking up the corresponding subproblem configuration in the database.
• It is easy to see that the sum of the two costs is still a lower bound on the cost of solving the
entire problem. This is the idea behind disjoint pattern databases.
 Learning heuristics from experience
• “Experience” here means solving lots of 8-puzzles, for instance. Each
optimal solution to an 8-puzzle problem provides examples from which h(n)
can be learned. Each example consists of a state from the solution path and
the actual cost of the solution from that point.
• Inductive learning methods work best when supplied with features of a state
that are FEATURE relevant to predicting the state’s value, rather than with
just the raw state description. Forexample, the feature “number of misplaced
tiles” might be helpful in predicting the actual distance of a state from the
goal.
 GAMES
• Game playing is an abstract and pure form of competition that seems to
require intelligence
• It is easy to represent states and actions
• To implement game playing little knowledge is required
• Game playing research has contributed ideas on how to make the best use
of time to reach good decisions
 Games
• We first consider games with two players, whom we call MAX and MIN. MAX moves
first, and then they take turns moving until the game is over. At the end of the game, points
are awarded to the winning player and penalties are given to the loser. A game can be
formally defined as a kind of search problem with the following elements:
• • S0: The initial state, which specifies how the game is set up at the start.
• • PLAYER(s): Defines which player has the move in a state.
• • ACTIONS(s): Returns the set of legal moves in a state.
• • RESULT (s, a): The transition model, which defines the result of a move.
• • TERMINAL -T EST (s): A terminal test, which is true when the game is over and false
otherwise. States where the game has ended are called terminal states.
 Games
• U TILITY(s, p): A utility function (also called an objective function or payoff
function), defines the final numeric value for a game that ends in terminal state
s for a player p. In chess, the outcome is a win, loss, or draw, with values +1, 0,
or 1/2 .
• Chess is zero-sum because every game has payoff of either 0 + 1, 1 + 0 or 1/2 +
1/2 .
• The initial state, ACTIONS function, and RESULT function define the game
tree for the game—a tree where the nodes are game states and the edges are
moves
 Tic tac game
• From the initial state, MAX has nine possible moves. Play alternates
between MAX ’s placing an X and MIN ’s placing an O
 Optimal Decisions In Games
• In adversarial search, MIN has something to say about it. MAX therefore
must find a contingent strategy, which specifies MAX’s move in the initial
state, then MAX’s moves in the states resulting from every possible response
by MIN, then MAX’s moves in the states resulting from every possible
response by MIN to those moves, and so on.
• This is exactly analogous to the AND–OR search algorithm with MAX
playing the role of OR and MIN equivalent to AND. Roughly speaking, an
optimal strategy leads to outcomes at least as good as any other strategy
when one is play ing an infallible opponent.
 Optimal decisions in Games
We begin by showing how to find this
optimal strategy. Given a game tree,
the optimal strategy can be determined
from the mini max value of each node,
which we write as MINIMAX(n). The
minimax value of a node is the utility
(for MAX) of being in the
corresponding state, assuming that
both players play optimally from there
to the end of the game.
 Working Of Min-max Algorithm
• Working of Min-Max Algorithm:
• The working of the minimax algorithm can be easily described using an example. Below we
have taken an example of game-tree which is representing the two-player game.
• In this example, there are two players one is called Maximizer and other is called Minimizer.
• Maximizer will try to get the Maximum possible score, and Minimizer will try to get the
minimum possible score.
• This algorithm applies DFS, so in this game-tree, we have to go all the way through the leaves to
reach the terminal nodes.
• At the terminal node, the terminal values are given so we will compare those value and backtrack
the tree until the initial state occurs.
 Working of Min – Max Algorithm
• Step-1: In the first step, the algorithm
generates the entire game-tree and apply
the utility function to get the utility
values for the terminal states. In the
below tree diagram, let's take A is the
initial state of the tree. Suppose
maximizer takes first turn which has
worst-case initial value =- infinity, and
minimizer will take next turn which has
worst-case initial value = +infinity.
 Working of Min- Max Algorithm
• step 2: Now, first we find the utilities value for
the Maximizer, its initial value is -∞, so we will
compare each value in terminal state with initial
value of Maximizer and determines the higher
nodes values. It will find the maximum among
the all.
• 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
 Working of Min- Max Algorithm
• Step 3: In the next step, it's a turn for
minimizer, so it will compare all
nodes value with +∞, and will find
the 3rd layer node values.
• For node B= min(4,6) = 4
• For node C= min (-3, 7) = -3
 Working of Min- Max Algorithm
• Step 4: Now it's a turn for Maximizer,
and it will again choose the maximum
of all nodes value and find the
maximum value for the root node. In
this game tree, there are only 4 layers,
hence we reach immediately to the
root node, but in real games, there will
be more than 4 layers.
• For node A max(4, -3)= 4
 Performance Evaluation
• Complete- Min-Max algorithm is Complete. It will definitely find a solution (if
exist), in the finite search tree.
• Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.
• Time complexity- As it performs DFS for the game-tree, so the time complexity
of Min-Max algorithm is O(bm), where b is branching factor of the game-tree, and
m is the maximum depth of the tree.
• Space Complexity- Space complexity of Mini-max algorithm is also similar to
DFS which is O(bm).