Module - 2

CSG3007 - DESIGN GAME USING ARTIFICIAL INTELLIGENCE AND MACHINE LEARNING

 Module - 2
Gaming Problem-Solving Approaches:
Problem-solving Methods, Search Strategies, Solving Problems by Searching,
Problem-solving agents, Problem types, Problem formulation Example problems;

Basic search algorithms:

Uninformed/Blind Search Strategies, Informed/Heuristics Search Strategies, Local
Search Algorithms, A* search, Constraint Satisfaction Problems;

Game Playing:
Optimal Decisions in Games, Alpha - Beta Pruning, Movement Planning.
Artificial Intelligence
Gaming Problem-Solving Approaches:

General Problem-solving Methods Problem-solving Methods in gaming

Problem-solving methods are systematic approaches used Problem-solving in gaming involves a combination of cognitive
to analyze and resolve complex issues. These methods are skills, strategies, and methodologies used to overcome challenges,
applied in various domains, including engineering, puzzles, and obstacles within a game
business, gaming, and daily life
Analytical Thinking Trial and Error
Trial and Error Pattern Recognition
Pattern Recognition Divide and Conquer
Divide and Conquer Heuristic Approaches
Root Cause Analysis (RCA) Backward Reasoning
Brainstorming Simulation and Hypothesis Testing
Lateral Thinking & Reverse Engineering Resource Management
Decision Matrix Analysis Lateral Thinking
Simulation and Modeling Collaboration and Teamwork
Algorithmic & Collaborative Problem-Solving Algorithmic Thinking
Gaming Problem-Solving Approaches:
✔ Players test different approaches until they find a successful one.
Trial and Error
✔ eg. In The Legend of Zelda, players may try different combinations to solve a puzzle
✔ Identifying recurring sequences or behaviors
Pattern Recognition
✔ eg. In Dark Souls, recognizing enemy attack patterns helps in dodging and countering effectively
✔ Breaking down complex problems into smaller, manageable parts.
Divide and Conquer ✔ eg. In StarCraft, players divide tasks (resource gathering, army building, defense) for efficient
gameplay
✔ Using educated guesses or shortcuts to find quick solutions.
Heuristic Approaches
✔ eg. In chess games like Deep Blue, heuristic algorithms evaluate the best possible moves.
✔ Working backward from the goal to determine the best path.
Backward Reasoning
✔ eg. In Hitman, players start with the target's elimination and plan steps backward.
✔ Predicting possible outcomes before making a move.
Simulation and Hypothesis Testing
✔ eg. In XCOM, players simulate attack probabilities before engaging enemies.
✔ Efficient allocation of limited resources to optimize gameplay.
Resource Management
✔ eg. In Minecraft, players manage food, tools, and materials to survive.
✔ Thinking outside the box to solve unconventional problems.
Lateral Thinking
✔ eg. Portal requires players to use portals creatively to navigate the environment.
✔ Working with others to solve problems collectively.
Collaboration and Teamwork
✔ eg. In Dota 2, teams strategize and assign roles to secure victory.
✔ Developing step-by-step procedures to solve game-related challenges.
Algorithmic Thinking.
✔ eg. Human Resource Machine and Factorio encourage logical programming solutions
Search Strategies
Search strategies are systematic approaches used to locate information, solutions, or optimal paths in a given problem
space. These strategies are widely used in artificial intelligence (AI), databases, game theory, and real-world
decision-making. Below are various search strategies categorized into uninformed and informed methods

We will see several uninformed search algorithms—algorithms that are given no information about the problem other than
its definition. Although some of these algorithms can solve any solvable problem, none of them can do so efficiently.
Uninformed search methods explore the search space without prior knowledge about the goal.

Informed search algorithms, on the other hand, can do quite well given some guidance on where to look for solutions.
Informed search methods use problem-specific knowledge (heuristics) to find solutions efficiently.

uninformed search algorithms Informed search algorithms Adversarial Search (Game Search)
Uninformed (Blind) Search Strategies Informed (Heuristic) Search Strategies Used in competitive environments like
Breadth-First Search (BFS) Greedy Best-First Search games

Depth-First Search (DFS) A Search*

Depth-Limited Search (DLS) Beam Search
Local Search Algorithms And
Iterative Deepening Depth-First Search (IDDFS) Hill Climbing Optimization Problems
Uniform-Cost Search (UCS) Simulated Annealing
 Solving Agents

An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that
environment through effectors.

A human agent has eyes, ears, and other organs for sensors, and
hands, legs, mouth, and other body parts for effectors.

A robotic agent substitutes cameras and infrared range finders

for the sensors and various motors for the effectors.

A software agent has encoded bit strings as its percepts and

actions

Agents interact with environments through sensors and effectors

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Solving Agents

In Artificial Intelligence, an agent is any entity that perceives its environment and takes actions. A rational agent is a
specific type of agent that always aims to make the best possible decision to maximize its performance measure.

A rational agent is an intelligent entity that takes actions to maximize its performance measure based on the available
information and knowledge about its environment. Rationality in AI refers to making the best possible decision in a
given situation.

All rational agents are agents, but not all agents are rational.

Aspect Agent Rational Agent

An agent that always chooses the optimal
Definition An entity that perceives and acts in an environment.
action to maximize success.
Always selects the best action based on
Decision-Making Can act randomly or sub-optimally.
knowledge and reasoning.
Evaluates actions based on a performance
Performance Measure May not follow an evaluation metric strictly.
measure.
A chatbot that learns and provides the most
Example A simple chatbot responding to user input.
relevant responses.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Rational agent
A rational agent is one that does the right thing. Obviously, this is better than doing the wrong thing, but what does it mean?

As a first approximation, we will say that the right action is the one that will cause the agent to be most successful. That leaves us with the
problem of deciding how and when to evaluate the agent's success.

We use the term performance measure for the how—the criteria that determine how successful an agent is. Obviously, there is not one
fixed measure suitable for all agents.

We will insist on an objective performance measure imposed by some authority. In other words, we as outside observers establish a
standard of what it means to be successful in an environment and use it to measure the performance of agents.

As an example,
Consider the case of an agent that is supposed to vacuum a dirty floor.
1. A plausible performance measure would be the amount of dirt cleaned up in a single eight-hour shift.
2. A more sophisticated performance measure would factor in the amount of electricity consumed and the amount of noise generated as
well.
3. A third performance measure might give highest marks to an agent that not only cleans the floor quietly and efficiently, but also finds
time to go windsurfing at the weekend.

when of evaluating performance is also important. If we measured how much dirt the agent had cleaned up in the first hour of the day, we
would be rewarding those agents that start fast (even if they do little or no work later on), and punishing those that work consistently. Thus,
we want to measure performance over the long run, be it an eight-hour shift or a lifetime.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Rational agent

The job of AI is to design the agent program: a function that implements the agent mapping from percepts to actions. We assume this
program will run on some sort of computing device, which we will call the architecture.

Obviously, the program we choose has to be one that the architecture will accept and run. The architecture might be a plain computer, or it
might include special-purpose hardware for certain tasks, such as processing camera images or filtering audio input.
It might also include software that provides a degree of insulation between the raw computer and the agent program, so that we can
program at a higher level. In general, the architecture makes the percepts from the sensors available to the program, runs the program, and
feeds the program's action choices to the effectors as they are generated.

The relationship among agents, architectures, and programs can be summed up as follows:

agent = architecture + program

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Rational agent

Examples of agent types and their PAGE (Percept, action, goals and Environment) descriptions

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Rational Agent Example: Self-Driving Car

Component Example in a Self-Driving Car

Perception Sensors detect traffic lights, road signs, obstacles.

Knowledge Traffic rules, past experiences, GPS data.

Goal Safely reach the destination with minimal delay.

Action Accelerate, brake, steer, overtake, slow down.

Performance Minimize accidents, optimize fuel, follow rules.

 Rational agent
There four types of agent program:
1. Simple Reflex Agent
✔ Reacts based on current perception (no history).
✔ Example: A thermostat turning AC on/off.
2. Model-Based Reflex Agent
✔ Uses an internal model to track past states.
✔ Example: A self-driving car tracking road conditions.
3. Goal-Based Agent
✔ Works towards a specific goal.
✔ Example: A chess AI aiming to win the game.
4. Utility-Based Agent
✔ Chooses actions that maximize overall utility (benefit).
✔ Example: A trading bot maximizing profit.
5. Learning Agent
✔ Improves decision-making over time using machine learning.
✔ Example: A voice assistant adapting to user preferences.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Rational agent

We will consider four types of agent program:

• Simple reflex agents

• Agents that keep track of the world
• Goal-based agents
• Utility-based agents

"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 written as

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

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Rational agent

We will consider four types of agent program:

• Simple reflex agents

• Agents that keep track of the world
• Goal-based agents
• Utility-based agents

Even for the simple braking rule, our driver will have to maintain some sort of internal state in order to choose an action. Here, the internal
state is not too extensive—it just needs the previous frame from the camera to detect when two red lights at the edge of the vehicle go on or
off simultaneously

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Rational agent

We will consider four types of agent program:

• Simple reflex agents

• Agents that keep track of the world
• Goal-based agents
• Utility-based agents

Along with the current state description, the agent needs some sort of goal information, which describes situations that are desirable

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Rational agent

We will consider four types of agent program:

• Simple reflex agents

• Agents that keep track of the world
• Goal-based agents
• Utility-based agents

Utility is therefore a function that maps a state onto a real number, which describes the associated degree of happiness. A complete
specification of the utility function allows rational decisions in two kinds of cases where goals have trouble.

First, when there are conflicting goals,

Second, when there are several goals that the agent can aim for,

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Rational agent - Properties of environments
Accessible vs. inaccessible.

If an agent's sensory apparatus gives it access to the complete state of the environment, then we say that the environment is accessible to
that agent. An environment is effectively accessible if the sensors detect all aspects that are relevant to the choice of action. An accessible
environment is convenient because the agent need not maintain any internal state to keep track of the world

Deterministic vs. nondeterministic.

If the next state of the environment is completely determined by the current state and the actions selected by the agents, then we say the
environment is deterministic. In principle, an agent need not worry about uncertainty in an accessible, deterministic environment. If the
environment is inaccessible, however, then it may appear to be nondeterministic. This is particularly true if the environment is complex,
making it hard to keep track of all the inaccessible aspects. Thus, it is often better to think of an environment as deterministic or
nondeterministic/rom the point of view of the agent.

Episodic vs. nonepisodic.

In an episodic environment, the agent's experience is divided into "episodes." Each episode consists of the agent perceiving and then
acting. The quality of its action depends just on the episode itself, because subsequent episodes do not depend on what actions occur in
previous episodes. Episodic environments are much simpler because the agent does not need to think ahead.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Rational agent - Properties of environments

Static vs. dynamic.

If the environment can change while an agent is deliberating, then we say the environment is dynamic for that agent; otherwise it is static.
Static environments are easy to deal with because the agent need not keep looking at the world while it is deciding on an action, nor need it
worry about the passage of time. If the environment does not change with the passage of time but the agent's performance score does, then
we say the environment is semidynamic.

Discrete vs. continuous.

If there are a limited number of distinct, clearly defined percepts and actions we say that the environment is discrete. Chess is
discrete—there are a fixed number of possible moves on each turn. Taxi driving is continuous—the speed and location of the taxi and the
other vehicles sweep through a range of continuous values.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Other agent

Reflex agents, cannot operate well in environments for which mapping from states to actions would be too large to store and would take too
long to learn.

Goal-based agents, on the other hand, consider future actions and the desirability of their outcomes. One such kind of goal-based agent
called a problem-solving agent.

Problem-solving agents use atomic representations, that is, states of the world are considered as wholes, with no internal structure visible to
the problem solving algorithms.

Goal-based agents that use more advanced factored or structured representations are usually called planning agents.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Problem types

Problems can be categorized based on their structure, complexity, and the methods required to solve them. In AI and computational
problem-solving, problems are generally classified as follows

▪ Well-Defined Problems(Have clear initial states, goal states, and rules),

▪ Ill-Defined Problems(The goal or constraints are ambiguous),
▪ Search-Based Problems(Problems where an agent must search for a solution in a state space.),
▪ Optimization Problems(Problems where the goal is to maximize or minimize an objective function.),
▪ Constraint Satisfaction Problems(Problems with variables and constraints that must be satisfied.),
▪ Decision Problems(Problems requiring a yes/no answer based on given constraints),
▪ Planning Problems(Problems that involve finding a sequence of actions to achieve a goal),
▪ Real-Time Problems(Problems requiring decisions within a time limit),
▪ Learning Problems(Problems where the solution improves over time using data)

Problem types require different problem-solving techniques. The choice depends on factors like structure, constraints, optimization needs,
and real-time requirements.
Problem formulation Example problems

Problem formulation in AI involves defining a problem in a structured way so that an agent can find a solution using search or optimization
techniques

Problem formulation is critical in AI as it determines the choice of search or optimization algorithm. Defining a clear initial state, actions,
goal, and cost function ensures efficient problem-solving.

Example Finding the shortest path in a 5x5 grid.

Pathfinding Problem (Grid Navigation)

Problem Formulation:
Initial State : Starting position (e.g., (0,0)). Traveling Salesman Problem (TSP)
Actions : Move Up, Down, Left, Right (within grid limits).
8-Puzzle Problem
State Space : All valid positions in the grid.
Robot Vacuum Cleaner Problem
Goal Test : Reaching the target position (e.g., (4,4)).
Path Cost : The number of moves taken (or distance traveled). Job Scheduling Problem

Solution Approach : Breadth-First Search (BFS) for the shortest path.

Basic search algorithms : Uninformed (Blind) Search Strategies

Solving Problems by Searching

Search algorithms are one of the most important areas of Artificial Intelligence.

Based on the search problems we can classify the search algorithms into uninformed (Blind
search) search and informed search (Heuristic search) algorithms.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : (Solving Problems by Searching)

Search Algorithm Terminologies:

✔ Search: Searching is a step by step procedure to solve a search-problem in a given search space. A search problem can have three main
factors:
✔ Search Space: Search space represents a set of possible solutions, which a system may have.
✔ Start State: It is a state from where agent begins the search.
✔ Goal test: It is a function which observe the current state and returns whether the goal state is achieved or not.
✔ Search tree: A tree representation of search problem is called Search tree. The root of the search tree is the root node which is
corresponding to the initial state.
✔ Actions: It gives the description of all the available actions to the agent.
✔ Transition model: A description of what each action do, can be represented as a transition model.
✔ Path Cost: It is a function which assigns a numeric cost to each path.
✔ Solution: It is an action sequence which leads from the start node to the goal node.
✔ Optimal Solution: If a solution has the lowest cost among all solutions.

[Link]
Basic search algorithms : (Solving Problems by Searching)

Properties of Search Algorithms:

Following are the four essential properties of search algorithms to compare the efficiency of these algorithms:
1. Completeness: A search algorithm is said to be complete if it guarantees to return a solution if at least any solution exists
for any random input.
2. Optimality: If a solution found for an algorithm is guaranteed to be the best solution (lowest path cost) among all other
solutions, then such a solution for is said to be an optimal solution.
3. Time Complexity: Time complexity is a measure of time for an algorithm to complete its task.
4. Space Complexity: It is the maximum storage space required at any point during the search, as the complexity of the
problem.

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

• The uninformed search does not contain any domain knowledge such as closeness, the location of the goal.
• It operates in a brute-force way as it only includes information about how to traverse the tree and how to identify leaf and goal nodes.
• Uninformed search applies a way in which search tree is searched without any information about the search space like initial state
operators and test for the goal, so it is also called blind search.
• It can be divided into five main types:
1. Breadth-first search
2. Uniform cost search
3. Depth-first search
4. Iterative deepening depth-first search
5. Bidirectional Search

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Breadth-first Search
•Breadth-first search is the most common search strategy for traversing a
tree or graph. This algorithm searches breadthwise in a tree or graph, so
it is called breadth-first search.
•BFS algorithm starts searching from the root node of the tree and
expands all successor node at the current level before moving to nodes of
next level.
•The breadth-first search algorithm is an example of a general-graph
search algorithm.
•Breadth-first search implemented using FIFO queue data structure.
•BFS search algorithm traverse in layers, so it will follow the path which
is shown by the dotted arrow, and the traversed path will be:

S ABCDGH
EFIK

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Breadth-first Search

Advantages:
•BFS will provide a solution if any solution exists.
•If there are more than one solutions for a given problem, then BFS will
provide the minimal solution which requires the least number of steps.

Disadvantages:
•It requires lots of memory since each level of the tree must be saved into
memory to expand the next level.
•BFS needs lots of time if the solution is far away from the root node

AD

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Breadth-first Search

Time Complexity: Time Complexity of BFS algorithm can be obtained

by the number of nodes traversed in BFS until the shallowest Node.
Where the d= depth of shallowest solution and b is a node at every state.
T (b) = 1+b2+b3+.......+ bd= O (bd)
Space Complexity: Space complexity of BFS algorithm is given by the
Memory size of frontier which is O(bd).
Completeness: BFS is complete, which means if the shallowest goal
node is at some finite depth, then BFS will find a solution.
Optimality: BFS is optimal if path cost is a non-decreasing function of
the depth of the node.

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Depth-first Search

Depth-first search is a recursive algorithm for traversing a tree or graph

data structure.
It is called the depth-first search because it starts from the root node and
follows each path to its greatest depth node before moving to the next
path.
DFS uses a stack data structure for its implementation.
The process of the DFS algorithm is similar to the BFS algorithm.

In the below search tree, we have shown the flow of depth-first search,
and it will follow the order as:
Root node--->Left node ----> right node.

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Depth-first Search

Advantage:
•DFS requires very less memory as it only needs to store a stack of the
nodes on the path from root node to the current node.
•It takes less time to reach to the goal node than BFS algorithm (if it
traverses in the right path).
Disadvantage:
•There is the possibility that many states keep re-occurring, and there is
no guarantee of finding the solution.
•DFS algorithm goes for deep down searching and sometime it may go to
the infinite loop.

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Depth-first Search

Completeness: DFS search algorithm is complete within finite state

space as it will expand every node within a limited search tree.
Time Complexity: Time complexity of DFS will be equivalent to the
node traversed by the algorithm. It is given by:
T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
Where, m= maximum depth of any node and this can be much
larger than d (Shallowest solution depth)
Space Complexity: DFS algorithm needs to store only single path from
the root node, hence space complexity of DFS is equivalent to the size
of the fringe set, which is O(bm).
Optimal: DFS search algorithm is non-optimal, as it may generate a
large number of steps or high cost to reach to the goal node.

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Depth-limited Search

A depth-limited search algorithm is similar to depth-first search with a

predetermined limit. Depth-limited search can solve the drawback of the
infinite path in the Depth-first search. In this algorithm, the node at the
depth limit will treat as it has no successor nodes further.
Depth-limited search can be terminated with two Conditions of failure:
Standard failure value: It indicates that problem does not have any
solution.
Cutoff failure value: It defines no solution for the problem within a
given depth limit.

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Depth-limited Search

Advantages:
Depth-limited search is Memory efficient.
Disadvantages:
•Depth-limited search also has a disadvantage of incompleteness.
•It may not be optimal if the problem has more than one solution.

[Link]
Basic search algorithms : Uninformed (Blind) Search Strategies

Depth-limited Search

Completeness: DLS search algorithm is complete if the solution is

above the depth-limit.
Time Complexity: Time complexity of DLS algorithm is O(bℓ).
Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
Optimal: Depth-limited search can be viewed as a special case of DFS,
and it is also not optimal even if ℓ>d.

[Link]
Basic search algorithms : Informed (Heuristic ) Search Strategies

Informed search strategy

—one that uses problem-specific knowledge beyond the definition of the problem itself
—can find solutions more efficiently than can an uninformed strategy

The general approach we consider is called The choice of f determines the search strategy.
best-first search.
Most best-first algorithms include as a component of f a heuristic function, denoted
Best-first search is an instance of the general h(n):h(n) = estimated cost of the cheapest path from the state at node n to a goal state.
TREE-SEARCH or GRAPH-SEARCH Heuristic functions are the most common form in which additional knowledge of the
algorithm in which a node is selected for problem is imparted to the search algorithm
expansion based on an evaluation function, we consider them to be arbitrary, nonnegative, problem-specific functions, with one
f(n). constraint: if n is a goal node, then h(n)=0.
.
The evaluation function is construed as a cost
estimate, so the node with the lowest two ways to use heuristic information to guide search
evaluation is expanded first. The Greedy best-first search
implementation of best-first graph search is
identical to that for uniform-cost search, A* search: Minimizing the total estimated solution cost
except for the use of f instead of g to order
the priority queue.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies Solving Problems by Searching

Informed search algorithms use domain knowledge.

In an informed search, problem information is available which can guide the search.
Informed search strategies can find a solution more efficiently than an uninformed search strategy.
A heuristic is a way which might not always be guaranteed for best solutions but guaranteed to find a good solution in reasonable time.
Informed search can solve much complex problem which could not be solved in another way.
Informed search algorithm contains an array of knowledge such as how far we are from the goal, path cost, how to reach to goal node,
etc. This knowledge help agents to explore less to the search space and find more efficiently the goal node.
The informed search algorithm is more useful for large search space. Informed search algorithm uses the idea of heuristic, so it is also
called Heuristic search.
Informed search algorithms
• Greedy Best-First Search
• A* Search Algorithm

[Link]
Basic search algorithms : Informed (Heuristic ) Search Strategies

Heuristics function: Heuristic is a function which is used in Informed Search, and it finds the most promising path. It takes the current
state of the agent as its input and produces the estimation of how close agent is from the goal. The heuristic method, however, might not
always give the best solution, but it guaranteed to find a good solution in reasonable time. Heuristic function estimates how close a state is
to the goal. It is represented by h(n), and it calculates the cost of an optimal path between the pair of states. The value of the heuristic
function is always positive.

Admissibility of the heuristic function is given as:

h(n) <= h*(n)
Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should be less than or equal to the estimated cost.

Pure heuristic search is the simplest form of heuristic search algorithms. It expands nodes based on their heuristic value h(n).
It maintains two lists, OPEN and CLOSED list. In the CLOSED list, it places those nodes which have already expanded and in the OPEN
list, it places nodes which have yet not been expanded.
On each iteration, each node n with the lowest heuristic value is expanded and generates all its successors and n is placed to the closed
list. The algorithm continues unit a goal state is found.

[Link]
Basic search algorithms : Informed (Heuristic ) Search Strategies

Best-first Search Algorithm (Greedy Search):

Greedy best-first search algorithm always selects the path which appears best at that moment.
It is the combination of depth-first search and breadth-first search algorithms. It uses the heuristic function and search.
Best-first search allows us to take the advantages of both algorithms. With the help of best-first search, at each step, we can choose the
most promising node.

In the best first search algorithm, we expand the node which is closest to the goal node and the closest cost is estimated by heuristic
function, i.e.
f(n)= g(n).
Were, h(n)= estimated cost from node n to the goal.
The greedy best first algorithm is implemented by the priority queue.

[Link]
Basic search algorithms : Informed (Heuristic ) Search Strategies

Best-first Search Algorithm (Greedy Search):

Step 1: Place the starting node into the OPEN list.
Step 2: If the OPEN list is empty, Stop and return failure.
Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and places it in the CLOSED list.
Step 4: Expand the node n, and generate the successors of node n.
Step 5: Check each successor of node n, and find whether any node is a goal node or not. If any successor node is goal
node, then return success and terminate the search, else proceed to Step 6.
Step 6: For each successor node, algorithm checks for evaluation function f(n), and then check if the node has been in either
OPEN or CLOSED list. If the node has not been in both list, then add it to the OPEN list.
Step 7: Return to Step 2.

[Link]
Basic search algorithms : Informed (Heuristic ) Search Strategies straight line distance heuristic (hsld)
Greedy best-first search
Greedy best-first search tries to expand the node that is closest to the
goal, on the grounds that this is likely to lead to a solution quickly.
Thus, it evaluates nodes by using just the heuristic function; that is, f(n)
= h(n).
Route-finding problems in Romania: we use the straight line distance
heuristic, which we will call hSLD. If the goal is Bucharest, we need to
know the straight-line distances to Bucharest, which are shown in
Figure.
For example,hSLD(In(Arad))=366. Notice that the values of hSLD
cannot be computed from the problem description itself. Moreover, it
takes a certain amount of experience to know that hSLD is correlated
with actual road distances and is, therefore, a useful heuristic.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Greedy best-first search

straight line distance heuristic (hsld)

The first node to be expanded from Arad will be Sibiu because it is closer to Bucharest than either Zerind or Timisoara.
The next node to be expanded will be Fagaras because it is closest. Fagaras in turn generates Bucharest, which is the goal.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

D
70
C
150
A 36 F 17 80
B 0 G 19

C 37 H 10 A
140 E 100
D 38 I 32
120 F
E 25 J 24 80
I G 210
95
110 J 50
H

100 B
Basic search algorithms : Informed (Heuristic ) Search Strategies

Greedy best-first search

straight line distance heuristic (hsld)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Greedy best-first search

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Greedy best-first search

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Greedy best-first search

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Greedy best-first search

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

A* search: Minimizing the total estimated solution cost

The most widely known form of best-first search is called A* search (pronounced “A-star search”).
It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to get from the node to the goal:
f(n) = g(n) + h(n) .
Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the
goal, we have
f(n) = estimated cost of the cheapest solution through n .

A∗ search is both complete and optimal. The algorithm is identical to UNIFORM-COST-SEARCH except that A* uses g +
h instead of g.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

A* search: Minimizing the total estimated solution cost

Conditions for optimality: Admissibility and consistency

The first condition we require for optimality is that h(n) be an admissible heuristic. An admissible heuristic is one that never overestimates
the cost to reach the goal.

Because g(n) is the actual cost to reach n along the current path, and f(n)=g(n) + h(n), we have as an immediate consequence that f(n) never
overestimates the true cost of a solution along the current path through n.

Straight-line distance hsld is admissible because the shortest path between any two points is a straight line, so the straight line cannot be an
overestimate

Second, slightly stronger condition called consistency (or sometimes monotonicity) is required only for applications of A* to graph search.

A heuristic h(n) is consistent if, for every node n and every successor n’ of n generated by any action a, the estimated cost of reaching the
goal from n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal from n’:
h(n) ≤ c(n, a, n’) + h(n) .

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

A* search: Minimizing the total estimated solution cost

Conditions for optimality: Admissibility and consistency

straight line distance heuristic (hsld)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

A* search: Minimizing the total estimated solution cost

Conditions for optimality: Admissibility and consistency

straight line distance heuristic (hsld)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

A* search: Minimizing the total estimated solution cost

Conditions for optimality: Admissibility and consistency

straight line distance heuristic (hsld)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies
A* search: Minimizing the total estimated solution cost
Conditions for optimality: Admissibility and consistency

straight line distance heuristic (hsld)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies
A* search: Minimizing the total estimated solution cost
Conditions for optimality: Admissibility and consistency

straight line distance heuristic (hsld)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

A* search: Minimizing the total estimated solution cost

Conditions for optimality: Admissibility and consistency

straight line distance heuristic (hsld)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

function HILL-CLIMBING( problem) return a state that is a local maximum

input: problem, a problem
local variables: current, a node.
neighbor, a node.

current ← MAKE-NODE(INITIAL-STATE[problem])
loop do
neighbor ← a highest valued successor of current
if VALUE [neighbor] ≤ VALUE[current] then return STATE[current]
current ← neighbor
min version will reverse inequalities and look for lowest valued successor

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

• “a loop that continuously moves towards increasing value”

• terminates when a peak is reached
• Aka greedy local search
• Value can be either
• Objective function value
• Heuristic function value (minimized)

• Hill climbing does not look ahead of the immediate neighbors

• Can randomly choose among the set of best successors
• if multiple have the best value

• “climbing Mount Everest in a thick fog with amnesia”

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

• Put n queens on an n x n board with no two queens on the same row, column, or diagonal

• Is it a satisfaction problem or optimization?

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

• Need to convert to an optimization problem

• h = number of pairs of queens that are attacking each other
• h = 17 for the above state

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

• Is this a solution?
• What is h?

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

• Is this a solution?
• What is h?

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

• Randomly generated 8-queens starting states…

• 14% the time it solves the problem
• 86% of the time it get stuck at a local minimum

• However…
• Takes only 4 steps on average when it succeeds
• And 3 on average when it gets stuck
• (for a state space with 8^8 =~17 million states)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search Drawbacks

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 upward toward the peak
but will then be stuck with nowhere else to go.

Ridges: Ridges result in a sequence of local maxima

that is very difficult for greedy algorithms to navigate.

Plateaux: a plateau is a flat area of the state-space landscape. It

can be a flat local maximum, from which no uphill exit exists,
or a shoulder, from which progress is possible. A hill-climbing
search might get lost on the plateau.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

• If no downhill (uphill) moves, allow sideways moves in hope that algorithm can escape
• Need to place a limit on the possible number of sideways moves to avoid infinite loops
• For 8-queens
• Now allow sideways moves with a limit of 100
• Raises percentage of problem instances solved from 14 to 94%
• However….
• 21 steps for every successful solution
• 64 for each failure

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

Hill-climbing: stochastic variations

• Stochastic hill-climbing
• Random selection among the uphill moves.
• The selection probability can vary with the steepness of the uphill move.

• To avoid getting stuck in local minima

• Random-walk hill-climbing
• Random-restart hill-climbing
• Hill-climbing with both

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

When the state-space landscape has local minima, any search that moves only in the greedy
direction cannot be complete

Random walk, on the other hand, is

asymptotically complete

Idea: Put random walk into greedy hill-climbing

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Hill-climbing search

• Random-restart hill climbing adopts the well-known adage If at first you don’t succeed, try, try again!
• Different variations
• For each restart: run until termination vs. run for a fixed time
• Run a fixed number of restarts or run indefinitely

• It is trivially complete with probability approaching

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Simulated Annealing

A hill-climbing algorithm that never makes “downhill” moves toward states with lower value (or higher cost) is guaranteed
to be incomplete, because it can get stuck on a local maximum.
In contrast, a purely random walk—that is, moving to a successor chosen uniformly at random from the set of
successors—is complete but extremely inefficient.

Therefore, it seems reasonable to try to combine hill climbing with a random walk in some way that yields both efficiency
and completeness. Simulated annealing is such an algorithm.

In metallurgy, annealing is the process used to temper or harden metals and glass by heating them to a high temperature
and then gradually cooling them, thus allowing the material to reach a lowenergy crystalline state.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Simulated Annealing

• Simulated Annealing = physics inspired twist on random walk

• Basic ideas:
• like hill-climbing identify the quality of the local improvements
• instead of picking the best move, pick one randomly
• say the change in objective function is d
• if d is positive, then move to that state
• otherwise:
• move to this state with probability proportional to d
• thus: worse moves (very large negative d) are executed less often
• however, there is always a chance of escaping from local maxima
• over time, make it less likely to accept locally bad moves
• (Can also make the size of the move random as well, i.e., allow “large” steps in state space)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Simulated Annealing

• A Physical Analogy:
• imagine letting a ball roll downhill on the function surface
• this is like hill-climbing (for minimization)
• now imagine shaking the surface, while the ball rolls, gradually reducing the amount of shaking
• this is like simulated annealing

• Annealing = physical process of cooling a liquid or metal until particles achieve a certain frozen crystal state
• simulated annealing:
• free variables are like particles
• seek “low energy” (high quality) configuration
• slowly reducing temp. T with particles moving around randomly

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Simulated Annealing
function SIMULATED-ANNEALING( problem, schedule) return a solution state
input: problem, a problem
schedule, a mapping from time to temperature
local variables: current, a node. the amount ΔE by which the evaluation is worsened.
next, a node.
T, a “temperature” controlling the prob. of downward steps
current ← MAKE-NODE(INITIAL-STATE[problem]) • high T: probability of “locally bad” move is higher
for t ← 1 to ∞ do
T ← schedule[t] • low T: probability of “locally bad” move is lower
if T = 0 then return current • typically, T is decreased as the algorithm runs longer
next ← a randomly selected successor of current
∆E ← VALUE[next] - VALUE[current] • i.e., there is a “temperature schedule”
if ∆E > 0 then current ← next
else current ← next only with probability e∆E /T

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Local beam search

Keeping just one node in memory might seem to be an extreme reaction to the problem of memory limitations. The local beam
search algorithm keeps track of k states rather than just one.

• Keep track of k states instead of one

• Initially: k randomly selected states
• Next: determine all successors of k states
• If any of successors is goal → finished
• Else select k best from successors and repeat
• Not the same as k random-start searches run in parallel!
• Searches that find good states recruit other searches to join them
• Problem: quite often, all k states end up on same local hill
• Idea: Stochastic beam search
• Choose k successors randomly, biased towards good ones
• Observe the close analogy to natural selection!

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Genetic algorithms
• Twist on Local Search: successor is generated by combining two parent states
• A state is represented as a string over a finite alphabet (e.g. binary)
• 8-queens
• State = position of 8 queens each in a column
• Start with k randomly generated states (population)
• Evaluation function (fitness function):
• Higher values for better states.
• Opposite to heuristic function, e.g., # non-attacking pairs in 8-queens
String representation 16257483
• Produce the next generation of states by “simulated evolution”
• Random selection Can we evolve 8-queens through genetic algorithms?

• Crossover
• Random mutation

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Genetic algorithms

4 states for 2 pairs of 2 states randomly New states Random

8-queens selected based on fitness. after crossover mutation
problem Random crossover points applied
selected
• Fitness function: number of non-attacking pairs of queens (min = 0, max = 8
× 7/2 = 28)
• 24/(24+23+20+11) = 31%
• 23/(24+23+20+11) = 29% etc

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Genetic algorithms

4 states for 2 pairs of 2 states New states Random

8-queens randomly selected based after crossover mutation
problem on fitness. Random applied
crossover points selected
• Fitness function: number of non-attacking pairs of queens (min = 0, max = 8
× 7/2 = 28)
• 24/(24+23+20+11) = 31%
• 23/(24+23+20+11) = 29% etc

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Genetic algorithms

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Basic search algorithms : Informed (Heuristic ) Search Strategies

Genetic algorithms
• Genetic algorithm is a variant of “stochastic beam search”
• Positive points
• Random exploration can find solutions that local search can’t
• (via crossover primarily)
• Appealing connection to human evolution
• “neural” networks, and “genetic” algorithms are metaphors!
• Negative points
• Large number of “tunable” parameters
• Difficult to replicate performance from one problem to another
• Lack of good empirical studies comparing to simpler methods
• Useful on some (small?) set of problems but no convincing evidence that GAs are better than
hill-climbing w/random restarts in general

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

LOCAL SEARCH ALGORITHMS AND OPTIMIZATION PROBLEMS

We had seen previously category of problems: observable, deterministic,

known environments where the solution is a sequence of actions.
Algorithms that perform purely local search in the state space, evaluating
and modifying one or more current states rather than systematically
exploring paths from an initial state.
These algorithms are suitable for problems in which all that matters is the
solution state, not the path cost to reach it.
The family of local search algorithms includes methods inspired by
statistical physics (simulated annealing) and evolutionary biology (genetic
algorithms).
The search algorithms that we have seen so far are designed to explore
search spaces systematically.
This systematicity is achieved by keeping one or more paths in memory and –E.g., 8-queens
by recording which alternatives have been explored at each point along the
path. what matters is the final configuration of
When a goal is found, the path to that goal also constitutes a solution to the queens, not the order in which they are
problem. In many problems, however, the path to the goal is irrelevant. added.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

LOCAL SEARCH ALGORITHMS AND OPTIMIZATION PROBLEMS

Local search algorithms operate using a single current node (rather than multiple paths) and generally move only to
neighbors of that node. Typically, the paths followed by the search are not retained.

Although local search algorithms are not systematic, they have two key advantages:
(1) they use very little memory—usually a constant amount; and
(2) they can often find reasonable solutions in large or infinite (continuous) state spaces for which systematic
algorithms are unsuitable.

In addition to finding goals, local search algorithms are useful for solving pure optimization problems, in which the
aim is to find the best state according to an objective function.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

LOCAL SEARCH ALGORITHMS AND OPTIMIZATION PROBLEMS

To understand local search, we find it useful to consider the

state-space landscape

A landscape has both “location” (defined by the state) and

“elevation” (defined by the value of the heuristic cost
function or objective function).

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

LOCAL SEARCH ALGORITHMS AND OPTIMIZATION PROBLEMS

To understand local search, we find it useful to consider the state-space landscape

A landscape has both “location” (defined by the state) and

“elevation” (defined by the value of the heuristic cost
function or objective function).

If elevation corresponds to cost, then the aim is to find

the lowest valley—a global minimum;

if elevation corresponds to an objective function, then the

aim is to find the highest peak—a global maximum.
(You can convert from one to the other just by inserting a
minus sign.)

A complete local search algorithm always finds a goal if one exists;

an optimal algorithm always finds a global minimum/maximum.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Example problem: Map coloring

• Variables WA, NT, Q, NSW, V, SA, T

• Domains Di = {red,green,blue}
• Constraints: adjacent regions must have different colors
e.g., WA ≠ NT, or (WA,NT) in {(red,green),(red,blue),(green,red),(green,blue),(blue,red),(blue,green)}

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Example problem: Map coloring

• Solutions are complete and consistent assignments

• e.g., WA = red, NT = green, Q = red, NSW = green,V = red,SA = blue,T = green

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Constraint graph

It can be helpful to visualize a CSP as a constraint graph

• Binary CSP: each constraint relates two variables
• Constraint graph: nodes are variables, arcs are constraints

The nodes of the graph correspond to variables of the

problem, and a link connects any two variables that
participate in a constraint.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 CONSTRAINT PROPAGATION: INFERENCE IN CSPS

The key idea is local consistency. If we treat each variable as a node in a graph and each binary constraint as an arc, then the process of
enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph.

In CSPs there is a choice:

an algorithm can search (choose a new variable assignment from several possibilities) or do a specific type of inference called constraint
propagation. using the constraints to reduce the number of legal values for a variable, which in turn can reduce the legal values for
another variable, and so on.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT PROPAGATION: INFERENCE IN CSPS

A single variable (corresponding to a node in the CSP network) is node-consistent if all the values
Node consistency
in the variable’s domain satisfy the variable’s unary constraints.

For example, in the variant of the Australia map-coloring problem where South Australians dislike
green, the variable SA starts with domain {red , green, blue}, and we can make it node consistent by
eliminating green, leaving SA with the reduced domain {red , blue}.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT PROPAGATION: INFERENCE IN CSPS

Arc consistency A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary
constraints. More formally, Xi is arc-consistent with respect to another variable Xj if for every value
in the current domain Di there is some value in the domain Dj that satisfies the binary constraint on
the arc (Xi,Xj).

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT PROPAGATION: INFERENCE IN CSPS

Arc consistency
• Simplest form of propagation makes each arc consistent
• X 🡪Y is consistent iff
for every value x of X there is some allowed y

• If X loses a value, neighbors of X need to be rechecked

• Arc consistency detects failure earlier than forward checking
• Can be run as a preprocessor or after each assignment

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT PROPAGATION: INFERENCE IN CSPS

The arc-consistency algorithm AC-3

After applying AC-3, either

every arc is arc-consistent, or
some variable has an empty
domain, indicating that the CSP
cannot be
solved.

The name “AC-3” was used by

the algorithm’s inventor
(Mackworth, 1977)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

BACKTRACKING SEARCH FOR CSPS

• Variable assignments are commutative, i.e.,

[ WA = red then NT = green ] same as [ NT = green then WA = red ]
• => Only need to consider assignments to a single variable at each node
• Depth-first search for CSPs with single-variable assignments is called backtracking
search
• Can solve n-queens for n ≈ 25

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

BACKTRACKING SEARCH FOR CSPS
BACKTRACKING SEARCH FOR CSPS
BACKTRACKING SEARCH FOR CSPS
BACKTRACKING SEARCH FOR CSPS
BACKTRACKING SEARCH FOR CSPS

Improving backtracking efficiency

General-purpose methods can give huge gains in speed:
◦ Which variable should be assigned next?
◦ In what order should its values be tried?
◦ Can we detect inevitable failure early?

Most constrained variable:

choose the variable with the fewest legal values

a.k.a. minimum remaining values (MRV) heuristic

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

BACKTRACKING SEARCH FOR CSPS

Most constraining variable

A good idea is to use it as a tie-breaker among most constrained variables

Most constraining variable:
◦ choose the variable with the most constraints on remaining variables

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

BACKTRACKING SEARCH FOR CSPS

Least constraining value

Given a variable to assign, choose the least constraining value:

◦ the one that rules out the fewest values in the remaining variables

Combining these heuristics makes 1000 queens feasible

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Example problem: Job-shop scheduling

Consider the problem of scheduling the assembly of a car. The whole job is composed of tasks, and we can model each task
as a variable, where the value of each variable is the time that the task starts, expressed as an integer number of minutes.

We can represent the tasks with 15 variables:

X = {AxleF , AxleB,WheelRF ,WheelLF ,WheelRB,WheelLB, NutsRF ,NutsLF , NutsRB, NutsLB, CapRF , CapLF , CapRB, CapLB,
Inspect} .

Constraints can assert that one task must occur before another—for example, a wheel must be installed before the hubcap is
put on—and that only so many tasks can go on at once. Constraints can also specify that a task takes a certain amount of time
to complete.

The value of each variable is the time that the task starts. Next we represent precedence constraints between individual
tasks. Whenever a task T1 must occur before task T2 , and task T1 takes duration d1 to complete, we add an arithmetic
constraint of the form T1 + d1 ≤ T2 .

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Example problem: Job-shop scheduling

We can represent the tasks with 15 variables:

X = {AxleF , AxleB,WheelRF ,WheelLF ,WheelRB,WheelLB, NutsRF ,NutsLF , NutsRB, NutsLB, CapRF , CapLF , CapRB, CapLB,
Inspect} .

Precedence constraints

AxleF + 10 ≤ WheelRF ; AxleF + 10 ≤ WheelLF ;

AxleB + 10 ≤ WheelRB; AxleB +10 ≤ WheelLB
WheelRF + 1 ≤ NutsRF ; NutsRF + 2 ≤ CapRF ;
WheelLF + 1 ≤ NutsLF ; NutsLF +2 ≤ CapLF ;
WheelRB + 1 ≤ NutsRB; NutsRB + 2 ≤ CapRB;
WheelLB + 1 ≤ NutsLB; NutsLB + 2 ≤ CapLB .

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Example problem: Job-shop scheduling

Suppose we have four workers to install wheels, but they have to share one tool that helps put the axle in place.

We need a disjunctive constraint to say that AxleF and AxleB must not
overlap in time; either one comes first or the other does:
(AxleF + 10 ≤ AxleB) or (AxleB + 10 ≤ AxleF ) .

We also need to assert that the inspection comes last and takes 3 minutes. For every variable except Inspect we add a
constraint of the form X +dX ≤ Inspect .

Finally, suppose there is a requirement to get the whole assembly done in 30 minutes. We can achieve that by limiting the
domain of all variables:
Di = {1, 2, 3, . . . , 27} .

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Variations on the CSP formalism

• Discrete variables
• finite domains:
• n variables, domain size d 🡪 O(dn) complete assignments
• e.g., Boolean CSPs, incl. Boolean satisfiability (NP-complete)
• infinite domains:
• set of integers, strings, etc.
• e.g., job scheduling, variables are start/end days for each job
• need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3

• Continuous variables
• e.g., start/end times for Hubble Space Telescope observations
• linear constraints solvable in polynomial time by LP

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Varieties of constraints

• Unary constraints involve a single variable,

• e.g., SA ≠ green
• Binary constraints involve pairs of variables,
• e.g., SA ≠ WA
• Higher-order constraints involve 3 or more variables,
• e.g., cryptarithmetic column constraints
• Global constraints involve arbitrary number of variables,
• e.g., in Sudoku all variables in a row or column must satisfy an Alldiff constraint

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

CONSTRAINT SATISFACTION PROBLEMS

Example: Cryptarithmetic

ordinary nodes
• Variables: F T U W R O X1 X2 X3
hypernodes (the squares),
• Domains: {0,1,2,3,4,5,6,7,8,9}
CONSTRAINT hypergraph ,
• Constraints: Alldiff (F,T,U,W,R,O)
• O + O = R + 10 · X1
X1 + W + W = U + 10 · X2
X2 + T + T = O + 10 · X3
• X3 = F, T ≠ 0, F ≠ 0

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Game Playing
In Multiagent environments, each agent needs to consider the actions of other agents and how they affect its own welfare. The
unpredictability of these other agents can introduce contingencies into the agent’s problem-solving process.
In this competitive environments, in which the agents’ goals are in conflict, giving rise to adversarial search problems—often known as
games.
▪ Rich tradition of creating game-playing programs in AI
▪ Many similarities to search
▪ Most of the games studied
battleship
▪ have two players,
Krieg spiel
▪ are zero-sum: what one player wins, the other loses
▪ have perfect information: the entire state of the game is known to both players at all times Types of Games
▪ E.g., tic-tac-toe, checkers, chess, Go, backgammon, …
▪ Recently more interest in other games
• Esp. games without perfect information; e.g., poker
• Need probability theory, game theory for such games

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing
Game tree (2-player, deterministic, turns)

How do we search this tree to find the optimal move?

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Search versus Games

• Search – no adversary
• Solution is (heuristic) method for finding goal
• Heuristics and CSP techniques can find optimal solution
• Evaluation function: estimate of cost from start to goal through given node
• Examples: path planning, scheduling activities

• Games – adversary
• Solution is strategy
• strategy specifies move for every possible opponent reply.
• Time limits force an approximate solution
• Evaluation function: evaluate “goodness” of game position
• Examples: chess, checkers, Othello, backgammon

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Games as Search
• Two players: MAX and MIN
• MAX moves first and they take turns until the game is over
• Winner gets reward, loser gets penalty.
• “Zero sum” means the sum of the reward and the penalty is a constant.
• Formal definition as a search problem:
• Initial state: Set-up specified by the rules, e.g., initial board configuration of chess.
• 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): Transition model defines the result of a move.
• Successor function: list of (move,state) pairs specifying legal moves.
• Terminal-Test(s): Is the game finished? True if finished, false otherwise.
• Utility function(s,p): Gives numerical value of terminal state s for player p.
• E.g., win (+1), lose (-1), and draw (0) in tic-tac-toe.
• E.g., win (+1), lose (0), and draw (1/2) in chess.
• MAX uses search tree to determine next move.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

A (partial) game tree for the game of tic-tac-toe. The

top node is the initial state, and MAX moves first,
placing an X in an empty square. We show part of the
tree, giving alternating moves by MIN (O) and MAX
(X), until we eventually reach terminal states, which
can be assigned utilities according to the rules of the
game.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Optimal Decisions in Games

Designed to find the optimal strategy for Max and find best move:

• Generate the whole game tree, down to the leaves.

• Apply utility (payoff) function to each leaf.

• Back-up values from leaves through branch nodes:

• a Max node computes the Max of its child values
• a Min node computes the Min of its child values

• At root: choose the move leading to the child of highest value.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Optimal Decisions in Games

A two-ply game tree. The nodes are “MAX

nodes,” in which it is MAX’s turn to move, and
the nodes are “MIN nodes.” The terminal nodes
show the utility values
for MAX; the other nodes are labeled with their
minimax values. MAX’s best move at the root is
a1, because it leads to the state with the highest
minimax value, and MIN’s best reply is b1,
because it leads to the state with the lowest
minimax value.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing
Optimal Decisions in Games
Pseudocode for Minimax Algorithm
function MINIMAX-DECISION(state) returns an action
inputs: state, current state in game
return arg maxa∈ACTIONS(state) MIN-VALUE(Result(state,a))

function MAX-VALUE(state) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)
v ← −∞
for a in ACTIONS(state) do
v ← MAX(v,MIN-VALUE(Result(state,a)))
return v

function MIN-VALUE(state) returns a utility value

if TERMINAL-TEST(state) then return UTILITY(state)
v ← +∞
for a in ACTIONS(state) do
v ← MIN(v,MAX-VALUE(Result(state,a)))
return v

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Optimal Decisions in Games

• Complete?
• Yes (if tree is finite).

• Optimal?
• Yes (against an optimal opponent).
Can it be beaten by an opponent playing sub-optimally?
Properties of minimax • No.
• Time complexity?
• O(bm)

• Space complexity?
• O(bm) (depth-first search, generate all actions at once)
• O(m) (backtracking search, generate actions one at a time)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

The problem with minimax search is that the number of game states it has to examine is exponential in the depth of the tree.
Unfortunately, we can’t eliminate the exponent, but it turns out we can effectively cut it in half.

The trick is that it is possible to compute the correct minimax decision without looking at every node in the game tree. That
is, we can do with the idea of pruning to eliminate large parts of the tree from consideration.

The particular technique we examine is called alpha–beta pruning. When applied to a standard minimax tree, it returns the
same move as minimax would, but prunes away branches that cannot possibly influence the final decision.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

• If a position is provably bad:

• It is NO USE expending search time to find out exactly how bad

• If the adversary can force a bad position:

• It is NO USE expending search time to find out the good positions that the adversary won’t
let you achieve anyway

• Bad = not better than we already know we can achieve elsewhere.

• Contrast normal search:

• ANY node might be a winner.
• ALL nodes must be considered.
• (A* avoids this through knowledge, i.e., heuristics)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

Stages in the calculation of the optimal decision for the game tree

a) The first leaf below B has the value 3. Hence, B, which is a MIN node, has a value of at most 3.

b) The second leaf below B has a value of 12; MIN would avoid this move, so the value of B is still at most 3.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

Stages in the calculation of the optimal decision for the game tree

(c) The third leaf below B has a value of 8; we have seen all B’s successor states, so the value of B is exactly 3. Now,
we can infer that the value of the root is at least 3, because MAX has a choice worth 3 at the root.

(d) The first leaf below C has the value 2. Hence, C, which is a MIN node, has a value of at most 2. But we know that B
is worth 3, so MAX would never choose C. Therefore, there is no point in looking at the other successor states of C.
This is an example of alpha–beta pruning.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

Stages in the calculation of the optimal decision for the game tree

(e) The first leaf below D has the value 14, so D is worth at most 14. This is still higher than MAX’s best alternative (i.e.,
3), so we need to keep exploring D’s successor states. Notice also that we now have bounds on all of the successors of the
root, so the root’s value is also at most 14.

(f) The second successor of D is worth 5, so again we need to keep exploring. The third successor is worth 2, so now D is
worth exactly 2. MAX’s decision at the root is to move to B, giving a value of 3.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

• Consider a node n in the tree ---

• If player has a better choice at:
• Parent node of n
• Or any choice point further up
• Then n will never be reached in play.
• Hence, when that much is known about n, it can be
pruned.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing
Alpha - Beta Pruning

• Depth first search

• only considers nodes along a single path from root at any time
a = highest-value choice found at any choice point of path for MAX
(initially, a = −infinity)
b = lowest-value choice found at any choice point of path for MIN
(initially, β = +infinity)

• Pass current values of a and b down to child nodes during search.

• Update values of a and b during search:
• MAX updates α at MAX nodes
• MIN updates β at MIN nodes
• Prune remaining branches at a node when a ≥ b

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

• When ?

• Prune whenever α ≥ β.

• Prune below a Max node whose alpha value becomes greater than or equal
to the beta value of its ancestors.
• Max nodes update alpha based on children’s returned values.

• Prune below a Min node whose beta value becomes less than or equal to the
alpha value of its ancestors.
• Min nodes update beta based on children’s returned values.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

function ALPHA-BETA-SEARCH(state) returns an action
inputs: state, current state in game
v←MAX-VALUE(state, - ∞ , +∞)
return the action in ACTIONS(state) with value v

function MAX-VALUE(state,α , β) returns a utility value

Pseudocode for Alpha-Beta Algorithm if TERMINAL-TEST(state) then return UTILITY(state)
v←-∞
for a in ACTIONS(state) do
v ← MAX(v,MIN-VALUE(Result(s,a), α , β))
if v ≥ β then return v
α ← MAX(α ,v)
return v

(MIN-VALUE is defined analogously)

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing
• Worst-Case
Alpha - Beta Pruning • branches are ordered so that no pruning takes place. In this case alpha-beta
gives no improvement over exhaustive search

• Best-Case
• each player’s best move is the left-most child (i.e., evaluated first)
• in practice, performance is closer to best rather than worst-case
• E.g., sort moves by the remembered move values found last time.
Effectiveness of Alpha-Beta Search • E.g., expand captures first, then threats, then forward moves, etc.
• E.g., run Iterative Deepening search, sort by value last iteration.

• In practice often get O(b(d/2)) rather than O(bd)

• this is the same as having a branching factor of sqrt(b),
• (sqrt(b))d = b(d/2),i.e., we effectively go from b to square root of b
• e.g., in chess go from b ~ 35 to b ~ 6
• this permits much deeper search in the same amount of time

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing

Alpha - Beta Pruning

• Pruning does not affect final results

• Entire subtrees can be pruned.

Comment on Alpha-Beta Search

• Good move ordering improves effectiveness of pruning

• Repeated states are again possible.

• Store them in memory = transposition table

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Game Playing
Alpha - Beta Pruning

Example -which nodes can be pruned?

5 6
3 4 1 2 7 8
Game Playing

Alpha - Beta Pruning

Answer Max -which nodes can be pruned?

Answer: NONE! Because the most

favorable nodes for both are explored last
(i.e., in the diagram, are on the right-hand
side).
Min

Max

5 6
3 4 1 2 7 8
Game Playing

Alpha - Beta Pruning

Second Example
(the exact mirror image of the first
example) -which nodes can be pruned?

3 4
6 5 8 7 2 1
Game Playing

Alpha - Beta Pruning

Answer -which nodes can be pruned?

Max

Answer: LOTS! Because the most

favorable nodes for both are
Min explored first (i.e., in the diagram,
are on the left-hand side).

Max

3 4
6 5 8 7 2 1
 Movement Planning

The effectiveness of alpha–beta pruning is highly dependent on the order in which the states are examined. For example, in Figure (e) and
(f), we could not prune any successors of D at all because the worst successors (from the point of view of MIN) were generated first.
If the third successor of D had been generated first, we would have been able to prune the other two. This suggests that it might be
worthwhile to try to examine first the successors that are likely to be best.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Movement Planning

Adding dynamic move-ordering schemes, such as trying first the moves that were found to be best in the past, brings us quite close to the
theoretical limit. The past could be the previous move—often the same threats remain—or it could come from previous exploration of the
current move. One way to gain information from the current move is with iterative deepening search.

In practice, iterative deepening search (IDS) is used

• IDS runs depth-first search with an increasing depth-limit
• when the clock runs out we use the solution found at the previous depth limit

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

 Movement Planning
In practice, iterative deepening search (IDS) is used
• IDS runs depth-first search with an increasing depth-limit
• when the clock runs out we use the solution found at the previous depth limit
First, search 1 ply deep and record the best path of moves. Then search 1 ply deeper, but use the recorded path to inform move ordering.

The best moves are often called killer moves and to try them first is called the killer move heuristic.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Extra
Solving Problems by Searching
PROBLEM-SOLVING AGENTS

Intelligent agents are supposed to maximize their performance measure. Achieving this is
sometimes simplified if the agent can adopt a goal and aim at satisfying it. Let us first look at
why and how an agent might do this.

Imagine an agent in the city of Arad, Romania, enjoying a touring holiday. The agent’s
performance measure contains many factors: it wants to improve its suntan, improve its
Romanian, take in the sights, enjoy the nightlife (such as it is), avoid hangovers, and so on.
The decision problem is a complex one involving many tradeoffs and careful reading of
guidebooks. Now, suppose the agent has a nonrefundable ticket to fly out of Bucharest the
following day. In that case, it makes sense for the agent to adopt the goal of getting to
Bucharest.
Courses of action that don’t reach Bucharest on time can be rejected without further
consideration and the agent’s decision problem is greatly simplified. Goals help organize
behavior by limiting the objectives that the agent is trying to achieve and hence the actions it
needs to consider.
Goal formulation, based on the current situation and the agent’s performance measure, is the
first step in problem solving.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Solving Problems by Searching
PROBLEM-SOLVING AGENTS
We will consider a goal to be a set of world states—exactly those states in which
the goal is satisfied. The agent’s task is to find out how to act, now and in the
future, so that it reaches a goal state. Before it can do this, it needs to decide (or we
need to decide on its behalf) what sorts of actions and states it should consider.

Problem formulation is the process of deciding what actions and states to

consider, given a goal.

Let us assume that the agent will consider actions at the level of driving from one
major town to another. Each state therefore corresponds to being in a particular
town.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Solving Problems by Searching
PROBLEM-SOLVING AGENTS

The process of looking for a sequence of

actions that reaches the goal is called
search.

A search algorithm takes a problem as

input and returns a solution in the form of
an action sequence.

Once a solution is found, the actions it

recommends can be carried out. This is
called the execution phase.

Thus, we have a simple “formulate,

search, execute” design for the agent,

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Solving Problems by Searching
PROBLEM-SOLVING AGENTS

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Solving Problems by Searching

Our agent has now adopted the goal of driving to

Bucharest and is considering where to go from
Arad. Three roads lead out of Arad, one toward
Sibiu, one to Timisoara, and one to Zerind.

If the agent has no additional information—i.e., if

the environment is unknown—then it is has no
choice but to try one of the actions at random

But suppose the agent has a map of Romania. The

point .of a map is to provide the agent with
information about the states it might get itself into
and the actions it can take. The agent can use this
information to consider subsequent stages of a
hypothetical journey via each of the three towns,
trying to find a journey that eventually gets to
Bucharest.

Once it has found a path on the map from Arad to

Bucharest, it can achieve its goal by carrying out
the driving actions that correspond to the legs of
the journey.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Solving Problems by Searching
INFORMED (HEURISTIC) SEARCH STRATEGIES
Informed search strategy
—one that uses problem-specific knowledge beyond the definition of the problem itself
—can find solutions more efficiently than can an uninformed strategy

The successors of Sibiu are Rimnicu Vilcea and Fagaras, with costs 80 and 99, respectively
Rimnicu Vilcea, is expanded next, adding Pitesti with cost 80 + 97=177.
The least-cost node is now Fagaras, so it is expanded, adding Bucharest with cost 99+211=310.
goal node has been generated,but uniform-cost search keeps going, Pitesti to Bucharest with cost 80+97+101= 278
checks to see if this new path is better than the old one; it is, so the old one is discarded. Bucharest, now with g-cost 278

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Solving Problems by Searching
PROBLEM-SOLVING AGENTS
A problem can be defined formally by five components:
• The initial state that the agent starts in. For example, the initial state for our agent in Romania might be described as
In(Arad).
• A description of the possible actions available to the agent. Given a particular state s, ACTIONS(s) returns the set of actions
that can be executed in s. We say that each of these actions is applicable in s. For example, from the state In(Arad), the
applicable actions are {Go(Sibiu), Go(Timisoara), Go(Zerind)}.
• A description of what each action does; the formal name for this is the transition model, specified by a function RESULT(s,
a) that returns the state that results from doing action a in state s.
• The goal test, which determines whether a given state is a goal state. Sometimes there is an explicit set of possible goal
states, and the test simply checks whether the given state is one of them. The agent’s goal in Romania is the singleton set
{In(Bucharest )}.
• A path cost function that assigns a numeric cost to each path. The problem-solving agent chooses a cost function that reflects
its own performance measure.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig

Solving Problems by Searching
INFORMED (HEURISTIC) SEARCH STRATEGIES
Informed search strategy
—one that uses problem-specific knowledge beyond the definition of the problem itself
—can find solutions more efficiently than can an uninformed strategy

The general approach we consider is called

best-first search.

Best-first search is an instance of the general

TREE-SEARCH or GRAPH-SEARCH algorithm in
which a node is selected for expansion based
on an evaluation function, f(n).

The evaluation function is construed as a cost

estimate, so the node with the lowest evaluation
is expanded first. The implementation of
best-first graph search is identical to that for
uniform-cost search, except for the use
of f instead of g to order the priority queue.

Artificial Intelligence A Modern Approach - Stuart J. Russell , Peter Norvig