.

UNIT1
Agent: An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that
environment through actuators.
Percept: percept to refer to the agent’s perceptual inputs at any given instant
percept sequence: An agent’s percept sequence is the complete history of everything the agent has ever perceived. In
general, an agent’s choice of action at any given instant can depend on the entire percept sequence observed to date, but not
on anything it hasn’t perceived.

Agent function : agent’s behavior is described by the agent function that maps any given percept sequence to an action.
Agent program: Internally, the agent function for an artificial agent will be implemented by an
AGENT PROGRAM agent program.

Example:

1
RATIONAL AGENT : A rational agent is one that does the right thing—conceptually speaking, every entry in the table for the
agent function is filled out correctly.
Rationality
What is rational at any given time depends on four things:
• The performance measure that defines the criterion of success.
• The agent’s prior knowledge of the environment.
• The actions that the agent can perform.
• The agent’s percept sequence to date.

Specifying the task environment:

task environment, we call this the PEAS (Performance, Environment, Actuators, Sensors) description. In designing an
agent, the first step must always be to specify the task environment as fully as possible. The vacuum world was a simple
example; let us consider a more complex problem: an automated taxi driver. We should point out, before the reader becomes
alarmed, that a fully
automated taxi is currently somewhat beyond the capabilities of existing technology. Following figure summarizes the PEAS
description for the taxi’s task environment. We discuss each element in more detail in the following paragraphs.

2
First, what is the performance measure to which we would like our automated driver
to aspire? Desirable qualities include getting to the correct destination; minimizing fuel consumption
and wear and tear; minimizing the trip time or cost; minimizing violations of traffic
laws and disturbances to other drivers; maximizing safety and passenger comfort; maximizing
profits. Obviously, some of these goals conflict, so tradeoffs will be required.
Next, what is the driving environment that the taxi will face? Any taxi driver must
deal with a variety of roads, ranging from rural lanes and urban alleys to 12-lane freeways.
The roads contain other traffic, pedestrians, stray animals, road works, police cars, puddles, The taxi must also interact with
potential and actual passengers. There are also
some optional choices.
The actuators for an automated taxi include those available to a human driver: control
over the engine through the accelerator and control over steering and braking. In addition, it
will need output to a display screen or voice synthesizer to talk back to the passengers, and
perhaps some way to communicate with other vehicles, politely or otherwise.
The basic sensors for the taxi will include one or more controllable video cameras so
that it can see the road; it might augment these with infrared or sonar sensors to detect distances
to other cars and obstacles. To avoid speeding tickets, the taxi should have a speedometer,
and to control the vehicle properly, especially on curves, it should have an accelerometer.
To determine the mechanical state of the vehicle, it will need the usual array of engine, fuel,
and electrical system sensors. Like many human drivers, it might want a global positioning
system (GPS) so that it doesn’t get lost. Finally, it will need a keyboard or microphone for
the passenger to request a destination.

Following figure shows the basic PEAS elements for a number of additional agent types.

3
Properties of Task Environments
1. Fully observable (vs. partially observable): An agent's sensors give it access to the complete state of the
environment at each point in time
2. Deterministic (vs. stochastic): next state of the env. determined by current state and the agent’s action. If the
environment is deterministic except for the actions of other agents, then the environment is strategic.
3. Episodic (vs. sequential):  Agent's experience is divided into atomic "episodes" Choice of action in each episode
depends only on the episode itself
4. Static (vs. dynamic): The environment is unchanged while an agent is deliberating Semidynamic if the environment
itself doesn’t change with time but the agent's performance score does
5. Discrete (vs. continuous): A limited number of distinct, clearly defined percepts and actions.
6. Single agent (vs. multiagent): An agent operating by itself in an environment Competitive vs. cooperative.

4
 THE STRUCTURE OF AGENTS:
The job of AI is to design an agent program that implements the agent function—
the mapping from percepts to actions. We assume this program will run on some sort of
computing device with physical sensors and actuators—we call this the architecture:
agent = architecture + program .
Obviously, the program we choose has to be one that is appropriate for the architecture. If the program is going to
recommend actions like Walk, the architecture had better have legs.

Agent programs:
They take the current percept as input from the sensors and return an action to the actuators.

four basic kinds of agent programs that embody the principles underlying almost all intelligent systems:
• Simple reflex agents;
• Model-based reflex agents;
• Goal-based agents; and
• Utility-based agents.

Simple reflex agents

5
The simplest kind of agent is the simple SIMPLE REFLEX reflex agent. These agents select actions on the basis of the current
percept, ignoring the rest of the percept history. For example, the vacuum agent
is a simple reflex agent, because its decision is based only on the current location and on whether that location contains dirt.
Simple reflex behaviors occur even in more complex environments. Imagine yourself
as the driver of the automated taxi. If the car in front brakes and its brake lights come on, then
you should notice this and initiate braking. In other words, some processing is done on the
visual input to establish the condition we call “The car in front is braking.” Then, this triggers
some established connection in the agent program to the action “initiate braking.” We call
such a connection a condition–action rule,5 written as

if car-in-front-is-braking then initiate-braking.

Humans also have many such connections, some of which are learned responses (as for driving)
and some of which are innate reflexes (such as blinking when something approaches the
eye). In the course of the book, we show several different ways in which such connections
can be learned and implemented.

The agent program, which is also very simple, is shown in Figure 2.10. The INTERPRET-INPUT function generates an
abstracted description of the current state from the
percept, and the RULE-MATCH function returns the first rule in the set of rules that matches
6
the given state description. Note that the description in terms of “rules” and “matching” is
purely conceptual; actual implementations can be as simple as a collection of logic gates
implementing a Boolean circuit.
Simple reflex agents have the admirable property of being simple, but they turn out to be
of limited intelligence. The agent in Figure 2.10 will work only if the correct decision can be
made on the basis of only the current percept—that is, only if the environment is fully observable.

For example, the braking

rule given earlier assumes that the condition car-in-front-is-braking can be determined from
the current percept—a single frame of video. This works if the car in front has a centrally
mounted brake light. Unfortunately, older models have different configurations of taillights,
brake lights, and turn-signal lights, and it is not always possible to tell from a single image
whether the car is braking. A simple reflex agent driving behind such a car would either brake
continuously and unnecessarily, or, worse, never brake at all.
We can see a similar problem arising in the vacuum world. Suppose that a simple reflex
vacuum agent is deprived of its location sensor and has only a dirt sensor. Such an agent
has just two possible percepts: [Dirty] and [Clean]. It can Suck in response to [Dirty]; what
should it do in response to [Clean]? Moving Left fails (forever) if it happens to start in square
A, and moving Right fails (forever) if it happens to start in square B. Infinite loops are often
unavoidable for simple reflex agents operating in partially observable environments

Model-based reflex agents

The most effective way to handle partial observability is for the agent to keep track of the
part of the world it can’t see now. That is, the agent should maintain some sort of internal
state that depends on the percept history and thereby reflects at least some of the unobserved
aspects of the current state. For the braking problem, the internal state is not too extensive—
just the previous frame from the camera, allowing the agent to detect when two red lights at
the edge of the vehicle go on or off simultaneously. For other driving tasks such as changing
lanes, the agent needs to keep track of where the other cars are if it can’t see them all at once.
And for any driving to be possible at all, the agent needs to keep track of where its keys are

7
Goal-based agents
Knowing something about the current state of the environment is not always enough to decide
what to do. For example, at a road junction, the taxi can turn left, turn right, or go straight
on. The correct decision depends on where the taxi is trying to get to. In other words, as well
as a current state description, the GOAL agent needs some sort of goal information that describes
situations that are desirable—for example, being at the passenger’s destination. The agent
program can combine this with the model (the same information as was used in the modelbased
reflex agent) to choose actions that achieve the goal. Figure 2.13 shows the goal-based
agent’s structure.
Sometimes goal-based action selection is straightforward—for example, when goal satisfaction
results immediately from a single action. Sometimes it will be more tricky—for
example, when the agent has to consider long sequences of twists and turns in order to find a
way to achieve the goal. Although the goal-based agent appears less efficient, it is more flexible because the knowledge that
supports its decisions is represented explicitly and can be modified. If it starts to rain, the agent can update its knowledge of
how effectively its brakes will operate; this will
automatically cause all of the relevant behaviors to be altered to suit the new conditions.
For the reflex agent, on the other hand, we would have to rewrite many condition–action
8
rules. The goal-based agent’s behavior can easily be changed to go to a different destination,
simply by specifying that destination as the goal. The reflex agent’s rules for when to turn
and when to go straight will work only for a single destination; they must all be replaced to
go somewhere new.

Utility-based agents
Goals alone are not enough to generate high-quality behavior in most environments. For
example, many action sequences will get the taxi to its destination (thereby achieving the
goal) but some are quicker, safer, more reliable, or cheaper than others. Goals just provide a
crude binary distinction between “happy” and “unhappy” states. A more general performance
measure should allow a comparison of different world states according to exactly how happy
they would make the agent. Because “happy” does not sound very scientific, economists and
computer scientists use the term utility instead.
We have already seen that a performance measure assigns a score to any given sequence
of environment states, so it can easily distinguish between more and less desirable ways of
getting to the UTILITY FUNCTION taxi’s destination. An agent’s utility function is essentially an internalization
of the performance measure. If the internal utility function and the external performance
measure are in agreement, then an agent that chooses actions to maximize its utility will be
rational according to the external performance measure.

9
Uninformed search strategy:
DFS
BFS

ON

ARTIFICIAL INTELLIGENCE

10
 PREPARED BY

DR. PRASHANTA KUMAR PATRA

COLLEGE OF ENGINEERING AND TECHNOLOGY,

BHUBANESWAR

11
Problems of AI:
Intelligence does not imply perfect understanding; every intelligent being has limited perception,
memory and computation. Many points on the spectrum of intelligence versus cost are viable,
from insects to humans. AI seeks to understand the computations required from intelligent
behaviour and to produce computer systems that exhibit intelligence. Aspects of intelligence
studied by AI include perception, communicational using human languages, reasoning, planning,
learning and memory.

The following questions are to be considered before we can step forward:

1. What are the underlying assumptions about intelligence?
2. What kinds of techniques will be useful for solving AI problems?
3. At what level human intelligence can be modelled?
4. When will it be realized when an intelligent program has been built?

Branches of AI:

A list of branches of AI is given below. However some branches are surely missing, because no
one has identified them yet. Some of these may be regarded as concepts or topics rather than full
branches.

Logical AI — In general the facts of the specific situation in which it must act, and its goals are
all represented by sentences of some mathematical logical language. The program decides what
to do by inferring that certain actions are appropriate for achieving its goals.

12
Search — Artificial Intelligence programs often examine large numbers of possibilities – for
example, moves in a chess game and inferences by a theorem proving program. Discoveries are
frequently made about how to do this more efficiently in various domains.

Pattern Recognition — When a program makes observations of some kind, it is often planned
to compare what it sees with a pattern. For example, a vision program may try to match a pattern
of eyes and a nose in a scene in order to find a face. More complex patterns are like a natural
language text, a chess position or in the history of some event. These more complex patterns
require quite different methods than do the simple patterns that have been studied the most.

Representation — Usually languages of mathematical logic are used to represent the facts about
the world.

Inference — Others can be inferred from some facts. Mathematical logical deduction is
sufficient for some purposes, but new methods of non-monotonic inference have been added to
the logic since the 1970s. The simplest kind of non-monotonic reasoning is default reasoning in
which a conclusion is to be inferred by default. But the conclusion can be withdrawn if there is
evidence to the divergent. For example, when we hear of a bird, we infer that it can fly, but this
conclusion can be reversed when we hear that it is a penguin. It is the possibility that a
conclusion may have to be withdrawn that constitutes the non-monotonic character of the
reasoning. Normal logical reasoning is monotonic, in that the set of conclusions can be drawn
from a set of premises, i.e. monotonic increasing function of the premises. Circumscription is
another form of non-monotonic reasoning.

Common sense knowledge and Reasoning — This is the area in which AI is farthest from the
human level, in spite of the fact that it has been an active research area since the 1950s. While
there has been considerable progress in developing systems of non-monotonic reasoning and
theories of action, yet more new ideas are needed.

Learning from experience — There are some rules expressed in logic for learning. Programs
can only learn what facts or behaviour their formalisms can represent, and unfortunately learning
systems are almost all based on very limited abilities to represent information.

Planning — Planning starts with general facts about the world (especially facts about the effects
of actions), facts about the particular situation and a statement of a goal. From these, planning
programs generate a strategy for achieving the goal. In the most common cases, the strategy is
just a sequence of actions.

Epistemology — This is a study of the kinds of knowledge that are required for solving
problems in the world.

Ontology — Ontology is the study of the kinds of things that exist. In AI the programs and
sentences deal with various kinds of objects and we study what these kinds are and what their
basic properties are. Ontology assumed importance from the 1990s.

13
Heuristics — A heuristic is a way of trying to discover something or an idea embedded in a
program. The term is used variously in AI. Heuristic functions are used in some approaches to
search or to measure how far a node in a search tree seems to be from a goal. Heuristic
predicates that compare two nodes in a search tree to see if one is better than the other, i.e.
constitutes an advance toward the goal, and may be more useful.

Genetic programming — Genetic programming is an automated method for creating a working

computer program from a high-level problem statement of a problem. Genetic programming
starts from a high-level statement of ‘what needs to be done’ and automatically creates a
computer program to solve the problem.

Applications of AI
AI has applications in all fields of human study, such as finance and economics, environmental
engineering, chemistry, computer science, and so on. Some of the applications of AI are listed
below:
• 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

AI Technique:

Artificial Intelligence research during the last three decades has concluded that Intelligence
requires knowledge. To compensate overwhelming quality, knowledge possesses less desirable
properties.
A. It is huge.
B. It is difficult to characterize correctly.
C. It is constantly varying.
D. It differs from data by being organized in a way that corresponds to its application.
E. It is complicated.

14
An AI technique is a method that exploits knowledge that is represented so that:
• The knowledge captures generalizations that share properties, are
grouped together, rather than being allowed separate representation.

• It can be understood by people who must provide it—even though for

many programs bulk of the data comes automatically from readings.

• In many AI domains, how the people understand the same people must supply
the knowledge to a program.

• It can be easily modified to correct errors and reflect changes in real conditions.

• It can be widely used even if it is incomplete or inaccurate.

• It can be used to help overcome its own sheer bulk by helping to narrow the
range of possibilities that must be usually considered.

In order to characterize an AI technique let us consider initially OXO or tic-tac-toe and use a
series of different approaches to play the game.
The programs increase in complexity, their use of generalizations, the clarity of their
knowledge and the extensibility of their approach. In this way they move towards being
representations of AI techniques.

HEURISTIC SEARCH TECHNIQUES:

Search Algorithms
Many traditional search algorithms are used in AI applications. For complex problems, the
traditional algorithms are unable to find the solutions within some practical time and space
limits. Consequently, many special techniques are developed, using heuristic functions.
The algorithms that use heuristic functions are called heuristic algorithms.

• Heuristic algorithms are not really intelligent; they appear to be intelligent because
they achieve better performance.
• Heuristic algorithms are more efficient because they take advantage of feedback from the
data to direct the search path.
• Uninformed search algorithms or Brute-force algorithms, search through the search space
all possible candidates for the solution checking whether each candidate satisfies the
problem’s statement.
• Informed search algorithms use heuristic functions that are specific to the problem, apply
them to guide the search through the search space to try to reduce the amount of time
spent in searching.

A good heuristic will make an informed search dramatically outperform any uninformed search:
for example, the Traveling Salesman Problem (TSP), where the goal is to find is a good solution
15
instead of finding the best solution.

In such problems, the search proceeds using current information about the problem to predict
which path is closer to the goal and follow it, although it does not always guarantee to find the
best possible solution. Such techniques help in finding a solution within reasonable time and
space (memory). Some prominent intelligent search algorithms are stated below:
1. Generate and Test Search
2. Best-first Search
3. Greedy Search
4. A* Search
5. Constraint Search

There are some more algorithms. They are either improvements or combinations of these.
• Hierarchical Representation of Search Algorithms: A Hierarchical representation of most
search algorithms is illustrated below. The representation begins with two types of search:
• Uninformed Search: Also called blind, exhaustive or brute-force search, it uses no
information about the problem to guide the search and therefore may not be very
efficient.
• Informed Search: Also called heuristic or intelligent search, this uses information about the
problem to guide the search—usually guesses the distance to a goal state and is therefore
efficient, but the search may not be always possible.

16
The first requirement is that it causes motion, in a game playing program, it moves on the board
and in the water jug problem, filling water is used to fill jugs. It means the control strategies
without the motion will never lead to the solution.
The second requirement is that it is systematic, that is, it corresponds to the need for global
motion as well as for local motion. This is a clear condition that neither would it be rational to
fill a jug and empty it repeatedly, nor it would be worthwhile to move a piece round and round
on the board in a cyclic way in a game. We shall initially consider two systematic approaches for
searching. Searches can be classified by the order in which operators are tried: depth-first,
breadth-first, bounded depth-first.

17
Breadth-first search
A Search strategy, in which the highest layer of a decision tree is searched completely before
proceeding to the next layer is called Breadth-first search (BFS).
• In this strategy, no viable solutions are omitted and therefore it is guaranteed that an
optimal solution is found.
• This strategy is often not feasible when the search space is large.
Algorithm
1. Create a variable called LIST and set it to be the starting state.
2. Loop until a goal state is found or LIST is empty, Do
a. Remove the first element from the LIST and call it E. If the LIST is empty, quit.
b. For every path each rule can match the state E, Do
(i) Apply the rule to generate a new state.
(ii) If the new state is a goal state, quit and return this state.
(iii) Otherwise, add the new state to the end of LIST.

18
Advantages
1. Guaranteed to find an optimal solution (in terms of shortest number of
steps to reach the goal).
2. Can always find a goal node if one exists (complete).
Disadvantages
1. High storage requirement: exponential with tree depth.
Depth-first search
A search strategy that extends the current path as far as possible before backtracking to the last
choice point and trying the next alternative path is called Depth-first search (DFS).
• This strategy does not guarantee that the optimal solution has been found.
• In this strategy, search reaches a satisfactory solution more rapidly than breadth first,
an advantage when the search space is large.
Algorithm
Depth-first search applies operators to each newly generated state, trying to drive directly toward
the goal.
1. If the starting state is a goal state, quit and return success.
2. Otherwise, do the following until success or failure is signalled:
a. Generate a successor E to the starting state. If there are no more successors, then signal failure.
b. Call Depth-first Search with E as the starting state.
c. If success is returned signal success; otherwise, continue in the loop.
Advantages
1. Low storage requirement: linear with tree depth.
2. Easily programmed: function call stack does most of the work of maintaining state of
the search.
Disadvantages
1. May find a sub-optimal solution (one that is deeper or more costly than the best solution).
2. Incomplete: without a depth bound, may not find a solution even if one exists.
[Link] Bounded depth-first search
Depth-first search can spend much time (perhaps infinite time) exploring a very deep path that
does not contain a solution, when a shallow solution exists. An easy way to solve this problem is
to put a maximum depth bound on the search. Beyond the depth bound, a failure is generated
automatically without exploring any deeper.
Problems:
1. It’s hard to guess how deep the solution lies.
2. If the estimated depth is too deep (even by 1) the computer time used is
dramatically increased, by a factor of bextra.
3. If the estimated depth is too shallow, the search fails to find a solution; all that computer
time is wasted.

UNIT2

Heuristics
A heuristic is a method that improves the efficiency of the search process. These are like tour
guides. There are good to the level that they may neglect the points in general interesting
directions; they are bad to the level that they may neglect points of interest to particular
19
individuals. Some heuristics help in the search process without sacrificing any claims to entirety
that the process might previously had. Others may occasionally cause an excellent path to be
overlooked. By sacrificing entirety it increases efficiency. Heuristics may not find the best

20
solution every time but guarantee that they find a good solution in a reasonable time. These are
particularly useful in solving tough and complex problems, solutions of which would require
infinite time, i.e. far longer than a lifetime for the problems which are not solved in any other
way.
Heuristic search
To find a solution in proper time rather than a complete solution in unlimited time we use
heuristics. ‘A heuristic function is a function that maps from problem state descriptions to
measures of desirability, usually represented as numbers’. Heuristic search methods use
knowledge about the problem domain and choose promising operators first. These heuristic
search methods use heuristic functions to evaluate the next state towards the goal state. For
finding a solution, by using the heuristic technique, one should carry out the following steps:
1. Add domain—specific information to select what is the best path to continue searching along.
2. Define a heuristic function h(n) that estimates the ‘goodness’ of a node n.
Specifically, h(n) = estimated cost(or distance) of minimal cost path from n to a goal state.
3. The term, heuristic means ‘serving to aid discovery’ and is an estimate, based on domain
specific information that is computable from the current state description of how close we are
to a goal.
Finding a route from one city to another city is an example of a search problem in which
different search orders and the use of heuristic knowledge are easily understood.
1. State: The current city in which the traveller is located.
2. Operators: Roads linking the current city to other cities.
3. Cost Metric: The cost of taking a given road between cities.
4. Heuristic information: The search could be guided by the direction of the goal city from
the current city, or we could use airline distance as an estimate of the distance to the goal.
Heuristic search techniques
For complex problems, the traditional algorithms, presented above, are unable to find the
solution within some practical time and space limits. Consequently, many special techniques are
developed, using heuristic functions.
• Blind search is not always possible, because it requires too much time or Space (memory).

Heuristics are rules of thumb; they do not guarantee a solution to a problem.

• Heuristic Search is a weak technique but can be effective if applied correctly; it
requires domain specific information.

Characteristics of heuristic search

• Heuristics are knowledge about domain, which help search and reasoning in its domain.
• Heuristic search incorporates domain knowledge to improve efficiency over blind search.
• Heuristic is a function that, when applied to a state, returns value as estimated merit of
state, with respect to goal.
✓ Heuristics might (for reasons) underestimate or overestimate the merit of a state
with respect to goal.
✓ Heuristics that underestimate are desirable and called admissible.
• Heuristic evaluation function estimates likelihood of given state leading to goal state.
• Heuristic search function estimates cost from current state to goal, presuming function
is efficient.

21
Heuristic search compared with other search
The Heuristic search is compared with Brute force or Blind search techniques below:

Comparison of Algorithms

Brute force / Blind search Heuristic search

Can only search what it has knowledge Estimates ‘distance’ to goal state
about already through explored nodes

No knowledge about how far a node Guides search process toward goal
node from goal state
Prefers states (nodes) that lead
close to and not away from goal
state

Example: Travelling salesman

A salesman has to visit a list of cities and he must visit each city only once. There are different
routes between the cities. The problem is to find the shortest route between the cities so that the
salesman visits all the cities at once.

Suppose there are N cities, then a solution would be to take N! possible combinations to find the
shortest distance to decide the required route. This is not efficient as with N=10 there are
36,28,800 possible routes. This is an example of combinatorial explosion.

There are better methods for the solution of such problems: one is called branch and bound.
First, generate all the complete paths and find the distance of the first complete path. If the next
path is shorter, then save it and proceed this way avoiding the path when its length exceeds the
saved shortest path length, although it is better than the previous method.

Generate and Test Strategy

Generate-And-Test Algorithm
Generate-and-test search algorithm is a very simple algorithm that guarantees to find a solution if
done systematically and there exists a solution.
Algorithm: Generate-And-Test
1. Generate a possible solution.
2. Test to see if this is the expected solution.
3. If the solution has been found quit else go to step 1.
Potential solutions that need to be generated vary depending on the kinds of problems. For some
problems the possible solutions may be particular points in the problem space and for some
problems, paths from the start state.

22
Figure: Generate And Test
Generate-and-test, like depth-first search, requires that complete solutions be generated for
testing. In its most systematic form, it is only an exhaustive search of the problem space.
Solutions can also be generated randomly but solution is not guaranteed. This approach is what is
known as British Museum algorithm: finding an object in the British Museum by wandering
randomly.
Systematic Generate-And-Test
While generating complete solutions and generating random solutions are the two extremes there
exists another approach that lies in between. The approach is that the search process proceeds
systematically but some paths that unlikely to lead the solution are not considered. This
evaluation is performed by a heuristic function.
Depth-first search tree with backtracking can be used to implement systematic generate-and-test
procedure. As per this procedure, if some intermediate states are likely to appear often in the
tree, it would be better to modify that procedure to traverse a graph rather than a tree.
Generate-And-Test And Planning
Exhaustive generate-and-test is very useful for simple problems. But for complex problems even
heuristic generate-and-test is not very effective technique. But this may be made effective by
combining with other techniques in such a way that the space in which to search is restricted. An
AI program DENDRAL, for example, uses plan-Generate-and-test technique. First, the planning
process uses constraint-satisfaction techniques and creates lists of recommended and
contraindicated substructures. Then the generate-and-test procedure uses the lists generated and
required to explore only a limited set of structures. Constrained in this way, generate-and-test
proved highly effective. A major weakness of planning is that it often produces inaccurate
solutions as there is no feedback from the world. But if it is used to produce only pieces of
solutions then lack of detailed accuracy becomes unimportant.

23
Hill Climbing
Hill Climbing is heuristic search used for mathematical optimization problems in the field of
Artificial Intelligence .
Given a large set of inputs and a good heuristic function, it tries to find a sufficiently good
solution to the problem. This solution may not be the global optimal maximum.
▪ In the above definition, mathematical optimization problems implies that hill climbing
solves the problems where we need to maximize or minimize a given real function by
choosing values from the given inputs. Example-Travelling salesman problem where
we need to minimize the distance traveled by salesman.
▪ ‘Heuristic search’ means that this search algorithm may not find the optimal solution
to the problem. However, it will give a good solution in reasonable time.
▪ A heuristic function is a function that will rank all the possible alternatives at any
branching step in search algorithm based on the available information. It helps
the algorithm to select the best route out of possible routes.
Features of Hill Climbing
1. Variant of generate and test algorithm : It is a variant of generate and test algorithm. The
generate and test algorithm is as follows :

1. Generate a possible solutions.

2. Test to see if this is the expected solution.
3. If the solution has been found quit else go to step 1.
Hence we call Hill climbing as a variant of generate and test algorithm as it takes the feedback
from test procedure. Then this feedback is utilized by the generator in deciding the next move in
search space.
2. Uses the Greedy approach : At any point in state space, the search moves in that direction
only which optimizes the cost of function with the hope of finding the optimal solution at
the end.
Types of Hill Climbing

1. Simple Hill climbing : It examines the neighboring nodes one by one and selects the
first neighboring node which optimizes the current cost as next node.
Algorithm for Simple Hill climbing :
Step 1 : Evaluate the initial state. If it is a goal state then stop and return success. Otherwise,
make initial state as current state.

Step 2 : Loop until the solution state is found or there are no new operators present which can
be applied to current state.

a) Select a state that has not been yet applied to the current state and apply it to produce a
new state.
b) Perform these to evaluate new state
i. If the current state is a goal state, then stop and return success.
ii. If it is better than the current state, then make it current state and proceed further.
iii. If it is not better than the current state, then continue in the loop until a solution is found.
24
Step 3 : Exit.

25
 2. Steepest-Ascent Hill climbing : It first examines all the neighboring nodes and then
selects the node closest to the solution state as next node.

Step 1 : Evaluate the initial state. If it is goal state then exit else make the current state as
initial state

Step 2 : Repeat these steps until a solution is found or current state does not change

i. Let ‘target’ be a state such that any successor of the current state will be better than it;
ii. for each operator that applies to the current state
a. apply the new operator and create a new state
b. evaluate the new state
c. if this state is goal state then quit else compare with ‘target’
d. if this state is better than ‘target’, set this state as ‘target’
e. if target is better than current state set current state to
Target Step 3 : Exit
3. Stochastic hill climbing : It does not examine all the neighboring nodes before deciding
which node to select .It just selects a neighboring node at random, and decides (based
on the amount of improvement in that neighbor) whether to move to that neighbor or
to examine another.
State Space diagram for Hill Climbing
State space diagram is a graphical representation of the set of states our search algorithm can
reach vs the value of our objective function(the function which we wish to maximize).
X- axis : denotes the state space ie states or configuration our algorithm may reach.
Y-axis : denotes the values of objective function corresponding to to a particular state.
The best solution will be that state space where objective function has maximum value(global
maximum).

Different regions in the State Space Diagram

1. Local maximum : It is a state which is better than its neighboring state however there
exists a state which is better than it(global maximum). This state is better because
26
here value of objective function is higher than its neighbors.

27
 2. Global maximum : It is the best possible state in the state space diagram. This because
at this state, objective function has highest value.
3. Plateua/flat local maximum : It is a flat region of state space where neighboring
states have the same value.
4. Ridge : It is region which is higher than its neighbours but itself has a slope. It is a special
kind of local maximum.
5. Current state : The region of state space diagram where we are currently present
during the search.
6. Shoulder : It is a plateau that has an uphill
edge. Problems in different regions in Hill climbing
Hill climbing cannot reach the optimal/best state(global maximum) if it enters any of the
following regions :
1. Local maximum : At a local maximum all neighboring states have a values which is
worse than than the current state. Since hill climbing uses greedy approach, it will
not move to the worse state and terminate itself. The process will end even though a
better solution may exist.
To overcome local maximum problem : Utilize backtracking technique. Maintain a list of
visited states. If the search reaches an undesirable state, it can backtrack to the previous
configuration and explore a new path.
2. Plateau : On plateau all neighbors have same value . Hence, it is not possible to select
the best direction.
To overcome plateaus : Make a big jump. Randomly select a state far away from current state.
Chances are that we will land at a non-plateau region
3. Ridge : Any point on a ridge can look like peak because movement in all possible
directions is downward. Hence the algorithm stops when it reaches this state.
To overcome Ridge : In this kind of obstacle, use two or more rules before testing. It
implies moving in several directions at once.

Best First Search (Informed Search)

In BFS and DFS, when we are at a node, we can consider any of the adjacent as next
node. So both BFS and DFS blindly explore paths without considering any cost function. The
idea of Best First Search is to use an evaluation function to decide which adjacent is most
promising and then explore. Best First Search falls under the category of Heuristic Search or
Informed Search.
We use a priority queue to store costs of nodes. So the implementation is a variation of BFS, we
just need to change Queue to PriorityQueue.

Algorithm:
Best-First-Search(Grah g, Node start)
1) Create an empty
PriorityQueue PriorityQueue
pq;
2) Insert "start" in
pq. [Link](start)
3) Until PriorityQueue is empty
28
u = [Link]

29
 If u is the goal
Exit
Else
Foreach neighbor v of u
If v "Unvisited"
Mark v "Visited"
[Link](v)
Mark v "Examined"
End procedure
Let us consider below example.

We start from source "S" and search for

goal "I" using given costs and Best
First search.

pq initially contains S
We remove s from and process unvisited
neighbors of S to pq.
pq now contains {A, C, B} (C is put
before B because C has lesser cost)

We remove A from pq and process unvisited

neighbors of A to pq.
pq now contains {C, B, E, D}

30
We remove C from pq and process unvisited
neighbors of C to pq.
pq now contains {B, H, E, D}

We remove B from pq and process unvisited

neighbors of B to pq.
pq now contains {H, E, D, F, G}

We remove H from pq. Since our goal

"I" is a neighbor of H, we return.
Analysis :
▪ The worst case time complexity for Best First Search is O(n * Log n) where n is number
of nodes. In worst case, we may have to visit all nodes before we reach goal. Note that
priority queue is implemented using Min(or Max) Heap, and insert and remove
operations take O(log n) time.
▪ Performance of the algorithm depends on how well the cost or evaluation function
is designed.

A* Search Algorithm
A* is a type of search algorithm. Some problems can be solved by representing the world in the
initial state, and then for each action we can perform on the world we generate states for what the
world would be like if we did so. If you do this until the world is in the state that we specified as
a solution, then the route from the start to this goal state is the solution to your problem.

In this tutorial I will look at the use of state space search to find the shortest path between two
points (pathfinding), and also to solve a simple sliding tile puzzle (the 8-puzzle). Let's look at
some of the terms used in Artificial Intelligence when describing this state space search.

Some terminology

A node is a state that the problem's world can be in. In pathfinding a node would be just a 2d
coordinate of where we are at the present time. In the 8-puzzle it is the positions of all the tiles.
Next all the nodes are arranged in a graph where links between nodes represent valid steps in
solving the problem. These links are known as edges. In the 8-puzzle diagram the edges are
shown as blue lines. See figure 1 below.
State space search, then, is solving a problem by beginning with the start state, and then for each
node we expand all the nodes beneath it in the graph by applying all the possible moves that can
be made at each point.

Heuristics and Algorithms

At this point we introduce an important concept, the heuristic. This is like an algorithm, but with
a key difference. An algorithm is a set of steps which you can follow to solve a problem, which
31
always works for valid input. For example you could probably write an algorithm yourself for

32
multiplying two numbers together on paper. A heuristic is not guaranteed to work but is useful in
that it may solve a problem for which there is no algorithm.
We need a heuristic to help us cut down on this huge search problem. What we need is to use our
heuristic at each node to make an estimate of how far we are from the goal. In pathfinding we
know exactly how far we are, because we know how far we can move each step, and we can
calculate the exact distance to the goal.
But the 8-puzzle is more difficult. There is no known algorithm for calculating from a given
position how many moves it will take to get to the goal state. So various heuristics have been
devised. The best one that I know of is known as the Nilsson score which leads fairly directly to
the goal most of the time, as we shall see.

Cost

When looking at each node in the graph, we now have an idea of a heuristic, which can estimate
how close the state is to the goal. Another important consideration is the cost of getting to where
we are. In the case of pathfinding we often assign a movement cost to each square. The cost is
the same then the cost of each square is one. If we wanted to differentiate between terrain types
we may give higher costs to grass and mud than to newly made road. When looking at a node we
want to add up the cost of what it took to get here, and this is simply the sum of the cost of this
node and all those that are above it in the graph.

8 Puzzle
Let's look at the 8 puzzle in more detail. This is a simple sliding tile puzzle on a 3*3 grid where
one tile is missing and you can move the other tiles into the gap until you get the puzzle into the
goal position. See figure 1.

Figure 1 : The 8-Puzzle state space for a very simple example

There are 362,880 different states that the puzzle can be in, and to find a solution the search has

33
to find a route through them. From most positions of the search the number of edges (that's the

34
 blue lines) is two. That means that the number of nodes you have in each level of the search is
2^d where d is the depth. If the number of steps to solve a particular state is 18, then that�s
262,144 nodes just at that level.

The 8 puzzle game state is as simple as representing a list of the 9 squares and what's in them.
Here are two states for example; the last one is the GOAL state, at which point we've found the
solution. The first is a jumbled up example that you may start from.

Start state SPACE, A, C, H, B, D, G, F, E

Goal state A, B, C, H, SPACE, D, G, F, E
The rules that you can apply to the puzzle are also simple. If there is a blank tile above, below, to
the left or to the right of a given tile, then you can move that tile into the space. To solve the
puzzle you need to find the path from the start state, through the graph down to the goal state.

There is example code to to solve the 8-puzzle on the github site.

Pathfinding
In a video game, or some other pathfinding scenario, you want to search a state space and find
out how to get from somewhere you are to somewhere you want to be, without bumping into
walls or going too far. For reasons we will see later, the A* algorithm will not only find a path, if
there is one, but it will find the shortest path. A state in pathfinding is simply a position in the
world. In the example of a maze game like Pacman you can represent where everything is using
a simple 2d grid. The start state for a ghost say, would be the 2d coordinate of where the ghost is
at the start of the search. The goal state would be where pacman is so we can go and eat him.
There is also example code to do pathfinding on the github site.

Figure 2 : The first three steps of a pathfinding state space

35
Implementing A*
We are now ready to look at the operation of the A* algorithm. What we need to do is start with
the goal state and then generate the graph downwards from there. Let's take the 8-puzzle in
figure 1. We ask how many moves can we make from the start state? The answer is 2, there are
two directions we can move the blank tile, and so our graph expands.
If we were just to continue blindly generating successors to each node, we could potentially fill
the computer's memory before we found the goal node. Obviously we need to remember the best
nodes and search those first. We also need to remember the nodes that we have expanded
already, so that we don't expand the same state repeatedly.
Let's start with the OPEN list. This is where we will remember which nodes we haven't yet
expanded. When the algorithm begins the start state is placed on the open list, it is the only state
we know about and we have not expanded it. So we will expand the nodes from the start and put
those on the OPEN list too. Now we are done with the start node and we will put that on the
CLOSED list. The CLOSED list is a list of nodes that we have expanded.

f=g+h

Using the OPEN and CLOSED list lets us be more selective about what we look at next in the
search. We want to look at the best nodes first. We will give each node a score on how good we
think it is. This score should be thought of as the cost of getting from the node to the goal plus
the cost of getting to where we are. Traditionally this has been represented by the letters f, g and
h. 'g' is the sum of all the costs it took to get here, 'h' is our heuristic function, the estimate of
what it will take to get to the goal. 'f' is the sum of these two. We will store each of these in our
nodes.
Using the f, g and h values the A* algorithm will be directed, subject to conditions we will look
at further on, towards the goal and will find it in the shortest route possible.

So far we have looked at the components of the A*, let's see how they all fit together to make the
algorithm :

Pseudocode

Hopefully the ideas we looked at in the preceding paragraphs will now click into place as we
look at the A* algorithm pseudocode. You may find it helpful to print this out or leave the
window open while we discuss it.

To help make the operation of the algorithm clear we will look again at the 8-puzzle problem in
figure 1 above. Figure 3 below shows the f,g and h scores for each of the tiles.

36
Figure 3 : 8-Puzzle state space showing f,g,h scores

First of all look at the g score for each node. This is the cost of what it took to get from the start
to that node. So in the picture the center number is g. As you can see it increases by one at each
level. In some problems the cost may vary for different state changes. For example in
pathfinding there is sometimes a type of terrain that costs more than other types.
Next look at the last number in each triple. This is h, the heuristic score. As I mentioned above I
am using a heuristic known as Nilsson's Sequence, which converges quickly to a correct solution
in many cases. Here is how you calculate this score for a given 8-puzzle state :

Advantages:

It is complete and optimal.

It is the best one from other techniques. It is used to solve very complex problems.

It is optimally efficient, i.e. there is no other optimal algorithm guaranteed to expand fewer nodes
than A*.

Disadvantages:

This algorithm is complete if the branching factor is finite and every action has fixed cost.

The speed execution of A* search is highly dependant on the accuracy of the heuristic algorithm
that is used to compute h (n).

37
AO* Search: (And-Or) Graph

The Depth first search and Breadth first search given earlier for OR trees or graphs can be easily
adopted by AND-OR graph. The main difference lies in the way termination conditions are
determined, since all goals following an AND nodes must be realized; where as a single goal
node following an OR node will do. So for this purpose we are using AO* algorithm.

Like A* algorithm here we will use two arrays and one heuristic function.

OPEN:

It contains the nodes that has been traversed but yet not been marked solvable or unsolvable.

CLOSE:

It contains the nodes that have already been processed.

6 7:The distance from current node to goal node.

Algorithm:

Step 1: Place the starting node into OPEN.

Step 2: Compute the most promising solution tree say T0.

Step 3: Select a node n that is both on OPEN and a member of T0. Remove it from OPEN and
place it in

CLOSE

Step 4: If n is the terminal goal node then leveled n as solved and leveled all the ancestors of n
as solved. If the starting node is marked as solved then success and exit.

Step 5: If n is not a solvable node, then mark n as unsolvable. If starting node is marked as
unsolvable, then return failure and exit.

Step 6: Expand n. Find all its successors and find their h (n) value, push them into OPEN.

Step 7: Return to Step 2.

Step 8: Exit.

38
Implementation:

Let us take the following example to implement the AO* algorithm.

Step 1:

In the above graph, the solvable nodes are A, B, C, D, E, F and the unsolvable nodes are G, H.
Take A as the starting node. So place A into OPEN.

39
40
41
Advantages:

It is an optimal algorithm.

If traverse according to the ordering of nodes. It can be used for both OR and AND graph.

Disadvantages:

Sometimes for unsolvable nodes, it can’t find the optimal path. Its complexity is than other
algorithms.

PROBLEM REDUCTION

Problem Reduction with AO* Algorithm.

When a problem can be divided into a set of sub problems, where each sub problem can be
solved separately and a combination of these will be a solution, AND-OR graphs or AND - OR
trees are used for representing the solution. The decomposition of the problem or problem
reduction generates AND arcs. One AND are may point to any number of successor nodes. All
42
these must be solved so that the arc will rise to many arcs, indicating several possible solutions.
Hence the graph is known as AND - OR instead of AND. Figure shows an AND - OR graph.

An algorithm to find a solution in an AND - OR graph must handle AND area appropriately. A*
algorithm can not search AND - OR graphs efficiently. This can be understand from the give
figure.

FIGURE : AND - OR graph

In figure (a) the top node A has been expanded producing two area one leading to B and leading
to C-D . the numbers at each node represent the value of f ' at that node (cost of getting to the
goal state from current state). For simplicity, it is assumed that every operation(i.e. applying a
rule) has unit cost, i.e., each are with single successor will have a cost of 1 and each of its
components. With the available information till now , it appears that C is the most promising
node to expand since its f ' = 3 , the lowest but going through B would be better since to use C
we must also use D' and the cost would be 9(3+4+1+1). Through B it would be 6(5+1).

Thus the choice of the next node to expand depends not only n a value but also on whether that
node is part of the current best path form the initial mode. Figure (b) makes this clearer. In figure
the node G appears to be the most promising node, with the least f ' value. But G is not on the
current beat path, since to use G we must use GH with a cost of 9 and again this demands that
arcs be used (with a cost of 27). The path from A through B, E-F is better with a total cost of
(17+1=18). Thus we can see that to search an AND-OR graph, the following three things must
be done.
1. traverse the graph starting at the initial node and following the current best path,
and accumulate the set of nodes that are on the path and have not yet been
expanded.

2. Pick one of these unexpanded nodes and expand it. Add its successors to the graph
and computer f ' (cost of the remaining distance) for each of them.

43
3. Change the f ' estimate of the newly expanded node to reflect the new information
produced by its successors. Propagate this change backward through the graph. Decide
which of the current best path.

The propagation of revised cost estimation backward is in the tree is not necessary in A*
algorithm. This is because in AO* algorithm expanded nodes are re-examined so that the current
best path can be selected. The working of AO* algorithm is illustrated in figure as follows:

Referring the figure. The initial node is expanded and D is Marked initially as promising node. D
is expanded producing an AND arc E-F. f ' value of D is updated to 10. Going backwards we can
see that the AND arc B-C is better . it is now marked as current best path. B and C have to be
expanded next. This process continues until a solution is found or all paths have led to dead ends,
indicating that there is no solution. An A* algorithm the path from one node to the other is
always that of the lowest cost and it is independent of the paths through other nodes.

The algorithm for performing a heuristic search of an AND - OR graph is given below. Unlike
A* algorithm which used two lists OPEN and CLOSED, the AO* algorithm uses a single
structure G. G represents the part of the search graph generated so far. Each node in G points
down to its immediate successors and up to its immediate predecessors, and also has with it the
value of h' cost of a path from itself to a set of solution nodes. The cost of getting from the start
nodes to the current node "g" is not stored as in the A* algorithm. This is because it is not
possible to compute a single such value since there may be many paths to the same state. In AO*
algorithm serves as the estimate of goodness of a node. Also a there should value called
FUTILITY is used. The estimated cost of a solution is greater than FUTILITY then the search is
abandoned as too expansive to be practical.
For representing above graphs AO* algorithm is as follows

AO* ALGORITHM:
1. Let G consists only to the node representing the initial state call this node INTT.
Compute h' (INIT).

2. Until INIT is labeled SOLVED or hi (INIT) becomes greater than FUTILITY, repeat the
following procedure.

44
(I) Trace the marked arcs from INIT and select an unbounded node NODE.

(II) Generate the successors of NODE . if there are no successors then assign FUTILITY as
h' (NODE). This means that NODE is not solvable. If there are successors then for each
one
called SUCCESSOR, that is not also an ancester of NODE do the following

(a) add SUCCESSOR to graph G

(b) if successor is not a terminal node, mark it solved and assign zero to its h ' value.

(c) If successor is not a terminal node, compute it h' value.

(III) propagate the newly discovered information up the graph by doing the following . let S be
a set of nodes that have been marked SOLVED. Initialize S to NODE. Until S is empty
repeat
the following procedure;

(a) select a node from S call if CURRENT and remove it from S.

(b) compute h' of each of the arcs emerging from CURRENT , Assign minimum h' to
CURRENT.

(c) Mark the minimum cost path a s the best out of CURRENT.

(d) Mark CURRENT SOLVED if all of the nodes connected to it through the new marked
are have been labeled SOLVED.

(e) If CURRENT has been marked SOLVED or its h ' has just changed, its new status
must
be propagate backwards up the graph . hence all the ancestors of CURRENT are added
to S.
(Refered From Artificial Intelligence TMH)

AO* Search Procedure.

1. Place the start node on open.

2. Using the search tree, compute the most promising solution tree TP .

3. Select node n that is both on open and a part of tp, remove n from open and place it no closed.

4. If n is a goal node, label n as solved. If the start node is solved, exit with success where tp
is the solution tree, remove all nodes from open with a solved ancestor.
45
5. If n is not solvable node, label n as unsolvable. If the start node is labeled as unsolvable,
exit with failure. Remove all nodes from open ,with unsolvable ancestors.

6. Otherwise, expand node n generating all of its successor compute the cost of for each
newly generated node and place all such nodes on open.

7. Go back to step(2)

Note: AO* will always find minimum cost solution.

UNIT 3

CONSTRAINT SATISFACTION:-

Many problems in AI can be considered as problems of constraint satisfaction, in which the goal
state satisfies a given set of constraint. constraint satisfaction problems can be solved by using
any of the search strategies. The general form of the constraint satisfaction procedure is as
follows:

Until a complete solution is found or until all paths have led to lead ends, do

1. select an unexpanded node of the search graph.

2. Apply the constraint inference rules to the selected node to generate all possible
new constraints.

3. If the set of constraints contains a contradiction, then report that this path is a dead end.

4. If the set of constraints describes a complete solution then report success.

5. If neither a constraint nor a complete solution has been found then apply the rules to
generate new partial solutions. Insert these partial solutions into the search graph.

Example: consider the crypt arithmetic problems.

SEND
+ MORE

MONEY

Assign decimal digit to each of the letters in such a way that the answer to the problem is correct
to the same letter occurs more than once , it must be assign the same digit each time . no two
different letters may be assigned the same digit. Consider the crypt arithmetic problem.

46
 SEND
+ MORE

MONEY

CONSTRAINTS:-

1. no two digit can be assigned to same letter.

2. only single digit number can be assign to a letter.

1. no two letters can be assigned same digit.

2. Assumption can be made at various levels such that they do not contradict each other.

3. The problem can be decomposed into secured constraints. A constraint satisfaction

approach may be used.

4. Any of search techniques may be used.

5. Backtracking may be performed as applicable us applied search techniques.

6. Rule of arithmetic may be followed.

Initial state of problem.

D=?
E=?
Y=?
N=?
R=?
O=?
S=?
M=?
C1=?
C2=?
C1 ,C 2, C3 stands for the carry variables respectively.

Goal State: the digits to the letters must be assigned in such a manner so that the sum is satisfied.

Solution Process:

We are following the depth-first method to solve the problem.

1. initial guess m=1 because the sum of two single digits can generate at most a carry '1'.

47
2. When n=1 o=0 or 1 because the largest single digit number added to m=1 can generate
the sum of either 0 or 1 depend on the carry received from the carry sum. By this we
conclude that o=0 because m is already 1 hence we cannot assign same digit another
letter(rule no.)

3. We have m=1 and o=0 to get o=0 we have s=8 or 9, again depending on the carry
received from the earlier sum.

The same process can be repeated further. The problem has to be composed into various
constraints. And each constraints is to be satisfied by guessing the possible digits that the letters
can be assumed that the initial guess has been already made . rest of the process is being shown
in the form of a tree, using depth-first search for the clear understandability of the solution
process.

48
D>6(Controduction)

49
50
MEANS - ENDS ANALYSIS:-

Most of the search strategies either reason forward of backward however, often a mixture o the
two directions is appropriate. Such mixed strategy would make it possible to solve the major
parts of problem first and solve the smaller problems the arise when combining them together.
Such a technique is called "Means - Ends Analysis".

The means -ends analysis process centers around finding the difference between current state and
goal state. The problem space of means - ends analysis has an initial state and one or more goal
state, a set of operate with a set of preconditions their application and difference functions that
computes the difference between two state a(i) and s(j). A problem is solved using means - ends
analysis by

1. Computing the current state s1 to a goal state s2 and computing their difference D12.

2. Satisfy the preconditions for some recommended operator op is selected, then to reduce
the difference D12.

3. The operator OP is applied if possible. If not the current state is solved a goal is created
and means- ends analysis is applied recursively to reduce the sub goal.

4. If the sub goal is solved state is restored and work resumed on the original problem.

( the first AI program to use means - ends analysis was the GPS General problem solver)

means- ends analysis I useful for many human planning activities. Consider the example of
planing for an office worker. Suppose we have a different table of three rules:

1. If in out current state we are hungry , and in our goal state we are not hungry , then either
the "visit hotel" or "visit Canteen " operator is recommended.

2. If our current state we do not have money , and if in your goal state we have money, then
the "Visit our bank" operator or the "Visit secretary" operator is recommended.

3. If our current state we do not know where something is , need in our goal state we do
know, then either the "visit office enquiry" , "visit secretary" or "visit co worker " operator is
recommended.

UNIT3:
Game Playing

• Charles Babbage, the nineteenth-century computer architect thought about programming

his analytical engine to play chess and later of building a machine to play tic-tac-toe.
• There are two reasons that games appeared to be a good domain.
1. They provide a structured task in which it is very easy to measure success or
51
 failure.
2. They are easily solvable by straightforward search from the starting state to a
winning position.
• The first is true is for all games bust the second is not true for all, except simplest games.
• For example, consider chess.
• The average branching factor is around 35. In an average game, each player might make
50.
• So in order to examine the complete game tree, we would have to examine 35100
• Thus it is clear that a simple search is not able to select even its first move during the
lifetime of its opponent.
• It is clear that to improve the effectiveness of a search based problem-solving program
two things can do.
1. Improve the generate procedure so that only good moves generated.
2. Improve the test procedure so that the best move will recognize and explored first.
• If we use legal-move generator then the test procedure will have to look at each of them
because the test procedure must look at so many possibilities, it must be fast.
• Instead of the legal-move generator, we can use plausible-move generator in which only
some small numbers of promising moves generated.
• As the number of lawyers available moves increases, it becomes increasingly important
in applying heuristics to select only those moves that seem more promising.
• The performance of the overall system can improve by adding heuristic knowledge into
both the generator and the tester.
• In game playing, a goal state is one in which we win but the game like chess. It is not
possible. Even we have good plausible move generator.
• The depth of the resulting tree or graph and its branching factor is too great.
• It is possible to search tree only ten or twenty moves deep then in order to choose the best
move. The resulting board positions must compare to discover which is most
advantageous.
• This is done using static evolution function, which uses whatever information it has to
evaluate individual board position by estimating how likely they are to lead eventually to
a win.
• Its function is similar to that of the heuristic function h’ in the A* algorithm: in the
absence of complete information, choose the most promising position.
MINIMAX Search Procedure

• The minimax search is a depth-first and depth limited procedure.

• The idea is to start at the current position and use the plausible-move generator to
generate the set of possible successor positions.

52
 • Now we can apply the static evolution function to those positions and simply choose the
best one.
• After doing so, we can back that value up to the starting position to represent our
evolution of it.
• Here we assume that static evolution function returns larger values to indicate good
situations for us.
• So our goal is to maximize the value of the static evaluation function of the next board
position.
• The opponents’ goal is to minimize the value of the static evaluation function.
• The alternation of maximizing and minimizing at alternate ply when
evaluations are to be pushed back up corresponds to the opposing strategies
of the two players is called MINIMAX.
• It is the recursive procedure that depends on two procedures
• MOVEGEN(position, player)— The plausible-move generator, which returns a
list of nodes representing the moves that can make by Player in Position.
• STATIC(position, player)– static evaluation function, which returns a number
representing the goodness of Position from the standpoint of Player.
• With any recursive program, we need to decide when recursive procedure should stop.
• There are the variety of factors that may influence the decision they are,
• Has one side won?
• How many plies have we already explored? Or how much time is left?
• How stable is the configuration?
• We use DEEP-ENOUGH which assumed to evaluate all of these factors and to return
TRUE if the search should be stopped at the current level and FALSE otherwise.
• It takes two parameters, position, and depth, it will ignore its position parameter and
simply return TRUE if its depth parameter exceeds a constant cut off value.
• One problem that arises in defining MINIMAX as a recursive procedure is that it needs to
return not one but two results.
• The backed-up value of the path it chooses.
• The path itself. We return the entire path even though probably only the first
element, representing the best move from the current position, actually needed.
• We assume that MINIMAX returns a structure containing both results and we have two
functions, VALUE and PATH that extract the separate components.
• Initially, It takes three parameters, a board position, the current depth of the search, and
the player to move,
• MINIMAX(current,0,player-one) If player –one is to move
• MINIMAX(current,0,player-two) If player –two is to move

Adding alpha-beta cutoffs

• Minimax procedure is a depth-first process. One path is explored as far as time allows,
the static evolution function is applied to the game positions at the last step of the path.
• The efficiency of the depth-first search can improve by branch and bound technique in
which partial solutions that clearly worse than known solutions can abandon early.
• It is necessary to modify the branch and bound strategy to include two bounds, one for
each of the players.
• This modified strategy called alpha-beta pruning.

53
 • It requires maintaining of two threshold values, one representing a lower bound on that a
maximizing node may ultimately assign (we call this alpha).
• And another representing an upper bound on the value that a minimizing node may assign
(this we call beta).
• Each level must receive both the values, one to use and one to pass down to the next level
to use.
• The MINIMAX procedure as it stands does not need to treat maximizing and minimizing
levels differently. Since it simply negates evaluation each time it changes levels.
• Instead of referring to alpha and beta, MINIMAX uses two values, USE-THRESH and
PASSTHRESH.
• USE-THRESH used to compute cutoffs. PASS-THRESH passed to next level as its
USETHRESH.
• USE-THRESH must also pass to the next level, but it will pass as PASS-THRESH so that
it can be passed to the third level down as USE-THRESH again, and so forth.
• Just as values had to negate each time they passed across levels.
• Still, there is no difference between the code required at maximizing levels and that
required at minimizing levels.
• PASS-THRESH should always the maximum of the value it inherits from above and the
best move found at its level.
• If PASS-THRESH updated the new value should propagate both down to lower levels.
And back up to higher ones so that it always reflects the best move found anywhere in the
tree.
• The MINIMAX-A-B requires five arguments, position, depth, player, Use-thresh, and
passThresh.
• MINIMAX-A-B(current,0,player-one,maximum value static can compute, minimum
value static can compute).
Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS)
There are two common ways to traverse a graph, BFS and DFS. Considering a Tree (or Graph)
of huge height and width, both BFS and DFS are not very efficient due to following reasons.
1. DFS first traverses nodes going through one adjacent of root, then next adjacent. The
problem with this approach is, if there is a node close to root, but not in first few subtrees
explored by DFS, then DFS reaches that node very late. Also, DFS may not find shortest
path to a node (in terms of number of edges).

54
 2. BFS goes level by level, but requires more space. The space required by DFS is O(d)
where d is depth of tree, but space required by BFS is O(n) where n is number of nodes in
tree (Why? Note that the last level of tree can have around n/2 nodes and second last
level n/4 nodes and in BFS we need to have every level one by one in queue).
IDDFS combines depth-first search’s space-efficiency and breadth-first search’s fast search (for
nodes closer to root).
How does IDDFS work?
IDDFS calls DFS for different depths starting from an initial value. In every call, DFS is
restricted from going beyond given depth. So basically we do DFS in a BFS fashion.
Algorithm:

// Returns true if target is reachable from

// src within max_depth
bool IDDFS(src, target, max_depth)
for limit from 0 to max_depth

if DLS(src, target, limit) == true

return true

return false

bool DLS(src, target, limit)

if (src == target)
return true;

// If reached the maximum depth,

// stop recursing.
if (limit <= 0)
return false;

55
foreach adjacent i of src

56
 if DLS(i, target, limit?1)
return true

return false

An important thing to note is, we visit top level nodes multiple times. The
last (or max depth) level is visited once, second last level is visited twice,
and so on. It may seem expensive, but it turns out to be not so costly,
since in a tree most of the nodes are in the bottom level. So it does not
matter much if the upper levels are visited multiple times.

57