Module 3: Informed and Adversarial Search

By
Ms. Sarika Dharangaonkar
Assistant Professor,
KJSCE

2/18/2025 1
 Contents: Module 3

• 3.1 Heuristic functions, Best First Search, Greedy BFS, A*

• 3.2 Local search algorithms and optimization problems, Hill Climbing, Simulated
Annealing and Genetic algorithms
• 3.3 Game Playing, Min-Max Search, Alpha Beta pruning

2/18/2025 2
 Informed Search

• Informed search (also called heuristic search) is a type of search algorithm in

artificial intelligence (AI) that uses additional information (a heuristic) to guide
the search process towards a goal more efficiently. Unlike uninformed search,
which explores blindly, informed search estimates the best path to the goal
using heuristics.
• One that uses problem- specific knowledge beyond the definition of the
problem itself
• can find solutions more efficiently than can an uninformed strategy.
• Imagine you are navigating a city with a GPS. If you only have a list of roads
but no idea which leads to your destination, that’s uninformed search. If you use
real-time traffic updates to choose the fastest route to reach to destination, that’s
informed search.

2/18/2025 3
 Component of Informed Search

•Heuristic Function h(n): Estimates the cost from a node to the goal.
•Evaluation Function f(n): Determines node selection based on heuristic
and/or path cost.

2/18/2025 4
 Heuristic Functions
• A heuristic function is an estimate of the cost to reach the goal from a given
node n.
• It helps guide informed search algorithms by prioritizing nodes that seem closer
to the goal. Denoted by: h(n)
• Example: Finding the shortest route on google map
o Imagine you are driving from Point A (Home) to Point B (Office), and you have three
possible routes:
1. Route 1: 10 km, but heavy traffic
2. Route 2: 12 km, but moderate traffic
3. Route 3: 15 km, but clear road
• A basic search algorithm (like Uniform Cost Search) might just consider
distance and choose Route 1 because it's the shortest. But, Google Maps uses a
heuristic function (estimated travel time) to choose the best route.

2/18/2025 5
 Heuristic Functions
• How Heuristic Functions Help?
• The heuristic function here is estimated travel time h(n), which considers:
Traffic conditions
Estimated speed on each road
Road type (highway vs. local road)
• Now, based on the heuristic function:
Route 1 → 10 km but 40 mins (high traffic)
Route 2 → 12 km but 25 mins (moderate traffic)
Route 3 → 15 km but 20 mins (clear road)
• Even though Route 3 is the longest in distance, it has the lowest heuristic cost (20 mins) and is
selected as the best option.

2/18/2025 6
 Heuristic Functions
Why Is This Important?
• Without heuristics: The algorithm might choose the shortest distance (not
always the fastest).
• With heuristics: The search is more intelligent and efficient, selecting the
best route based on real conditions.
• This is why heuristic functions are crucial—they add problem-specific
knowledge to the search algorithm, making it more practical in real-world
applications like pathfinding, robotics, and AI decision-making.

2/18/2025 7
 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.
• Most best-first algorithms include as a component of f a heuristic function,
denoted h(n): estimated cost of the cheapest path from the state at node n to a goal
state.

2/18/2025 8
 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).
• Greedy Best-First Search (Greedy BFS) is an informed search algorithm that
always expands the node with the lowest heuristic cost (estimated cost to the
goal).
• It does not consider the actual cost taken to reach a node.
• It relies only on the heuristic function h(n), which estimates how close a node is to
the goal.
• It is called "greedy" because it chooses the best option at each step, hoping to reach
the goal faster.

2/18/2025 9
 Greedy Best First Search
• Let’s take a simple city map where we want to find the shortest route from City
A (Start) to City G (Goal).
Each city is represented as a node.
The numbers on the edges represent distances.
The heuristic function h(n) estimates the straight-line distance from each city
to the goal City G (ignoring actual road distances).

2/18/2025 10
 Greedy Best First Search

B C

D E F

1️⃣ Start at City A. G

•Possible moves: B (h=8), C (h=7) 3️⃣ Move to City F.
•Choose C (since h(C)=7 is the lowest). •Possible moves: G (h=0, Goal!)
2️⃣ Move to City C. •Choose G (Goal reached).
•Possible moves: F (h=5) Path Found: A → C → F → G
•Choose F (since h(F)=5 is the lowest).
2/18/2025 11
 Greedy Best First Search
• Disadvantages:
• Greedy BFS only considers heuristic values and ignores actual road distances.
• Example Issue:
• If B → E → G was a shorter route in terms of actual road distance, but Greedy BFS
ignores it due to its high heuristic value, it may not find the optimal path.
• It can get stuck in local minima (choosing a promising route too early without considering
better long-term paths).
Fast but not always optimal: It is quick but does not always find the shortest path.
Uses heuristic function: Makes decisions based only on estimated distance to the goal.
Works well for simple problems: But struggles with complex graphs and obstacles.
Alternative?
A* Search (combines heuristic + actual cost traveled) is more reliable for finding optimal
paths.

2/18/2025 12
 A* Algorithm

• The A (A-Star) Search Algorithm* is an informed search algorithm used for finding
the shortest path between nodes in a graph. It combines the best aspects of Dijkstra’s
Algorithm (which considers the actual cost) and Greedy Best-First Search (which
considers the heuristic).
• A* uses the following cost function to evaluate each node:
• f(n)=g(n)+h(n);
o Where:
• g(n)= Actual cost from the start node to the current node.
• h(n) = Heuristic function (estimated cost from current node to the goal).
• f(n) = Total estimated cost of the path passing through node n.
o A* expands the node with the lowest f(n) value first, ensuring an optimal solution.

2/18/2025 13
 A* Algorithm

• Example

2/18/2025 14
 Local Searching Algorithms and optimization problems
• Local search algorithms are heuristic-based methods used to find optimal solutions in
large search spaces when exhaustive search is impractical. They work by iteratively
improving a candidate solution based on a given objective function.
• Key Characteristics:
Work well for optimization problems
Do not maintain an explicit search tree
Efficient for large problem spaces
May get stuck in local optima
• Example Applications:
• Pathfinding (e.g., Google Maps, GPS Navigation)
• Scheduling (e.g., Job Scheduling)
• Machine Learning

2/18/2025 15
 Hill Climbing Algorithm

• Hill Climbing is a greedy local search algorithm that continuously moves towards a
better solution by making small changes, never backtracks.
• It is simply a loop that continually moves in the direction of increasing value i.e. uphill
• It terminates when it reaches a PEAK where no neighbors has higher value.
• Algorithm Steps:
1. Start with an initial solution(random point).
2. Evaluate its fitness(score or value of solution).
3. Explore its neighboring states(possible next solution).
4. Move to the neighbor with the highest fitness(better solution).
5. Repeat until no better neighbor exists (local optimum).

2/18/2025 16
 Hill Climbing Algorithm
• Challenges: Unfortunately, hill climbing often gets stuck for the following reasons:

(i) Local Maxima

•The algorithm can get stuck at a peak that is not the global
maximum.
•Solution: Use Simulated Annealing or Random Restarts.

(ii) Plateaus
•A flat area where all neighbors have the same value.
•Solution: Use random jumps to escape.

(iii) Ridges
•A path that requires moving downward first to reach the
best solution.
•Solution: Modify the algorithm to allow occasional
downward moves.

2/18/2025 17
 Simulated Annealing

• Hill climbing is an optimization algorithm that makes moves only towards states with higher values
(or lower costs).
• However, it suffers from incompleteness, as it can get stuck in local maxima. In contrast, a purely
random walk is complete but highly inefficient.
• Simulated Annealing is an algorithm that combines hill climbing with a random walk in a structured
way to balance efficiency and completeness.
• Inspired by the metallurgical annealing process, Simulated Annealing starts with a high probability
of accepting worse solutions, gradually reducing this probability over time. This allows it to escape
local optima and find better global solutions.
• The analogy is like shaking a bumpy surface to help a rolling ball escape local pits and reach the
deepest point, representing the global minimum.

2/18/2025 18
 Genetic Algorithm
• A Genetic Algorithm (GA) is an optimization technique based on the principles of natural
selection and genetics.
• a genetic algorithm as a heuristic search algorithm to solve optimization problems, given by
John Holland
• Basic terminology:
o Population: Population is the subset of all possible or probable solutions, which can
solve the given problem.
o Fitness Function: The fitness function is used to determine the individual's fitness level
in the population. It means the ability of an individual to compete with other individuals.
In every iteration, individuals are evaluated based on their fitness function.
o Selection: After calculating the fitness of every existent in the population, a selection
process is used to determine which of the individualities in the population will get to
reproduce and produce the seed that will form the coming generation.

2/18/2025 19
 Genetic Algorithm
o Crossover: The crossover plays a most significant role in the reproduction phase of the genetic
algorithm. In this process, a crossover point is selected at random within the genes. Then the
crossover operator swaps genetic information of two parents from the current generation to
produce a new individual representing the offspring.

o The genes of parents are exchanged among themselves until the crossover point is met. These
newly generated offspring are added to the population. This process is also called or crossover.

2/18/2025 20
 Genetic Algorithm
o Mutation: The mutation operator inserts random genes in the offspring (new child) to maintain the
diversity in the population. It can be done by flipping some bits in the chromosomes. Mutation
helps in solving the issue of premature convergence and enhances diversification. The below
image shows the mutation process:

o Termination: After the reproduction phase, a stopping criterion is applied as a base for
termination. The algorithm terminates after the threshold fitness solution is reached. It will identify
the final solution as the best solution in the population.

2/18/2025 21
 Genetic Algorithm

The steps of the algorithm can be summarized as:

1) Randomly initialize populations p
2) Determine fitness of population
3) Until convergence repeat:
a) Select parents from population
b) Crossover and generate new population
c) Perform mutation on new population
d) Calculate fitness for new population

2/18/2025 22
 Game Playing
• A game in game theory is a mathematical model that represents a competitive situation
where two or more players make strategic decisions to maximize their benefits. A game
consists of:
• Players (decision-makers)
• Actions (available choices)
• Payoffs (outcomes based on actions)
• Example: Chess, Poker, Rock-Paper-Scissors.
• Players
• Players are the decision-makers in a game. Each player has a set of possible actions and aims
to maximize their payoff.
• Example: In a chess game, there are two players—one playing White and the other playing
Black.

2/18/2025 23
 Game Playing
• Actions
• An action is a move or decision that a player can take at any point in the game. The set of all available
actions is called the action space.
o Example:
• In Tic-Tac-Toe, a player’s action is placing "X" or "O" in an empty cell.
• Payoff
• A payoff is the reward or outcome a player receives after making a decision. The payoff depends on
the strategy of all players in the game.
• Zero-Sum Game
• A zero-sum game is a situation where one player's gain is exactly balanced by another player's loss.
The total sum of payoffs remains zero.
o Example:
• Chess & Poker: If one player wins, the other loses.
• Tic-Tac-Toe: If one player wins (+1), the other loses (-1), making the sum zero.

2/18/2025 24
 Game Playing
• Non-Zero-Sum Game
• A non-zero-sum game is a game where the total payoff is not necessarily zero. Players can
cooperate to get better outcomes, or both can lose.
• Simultaneous Game
• A simultaneous game is one where all players make their decisions at the same time,
without knowing what the other players chose.
o Example:
• Rock-Paper-Scissors: Both players select their moves simultaneously.
• Sequential Game
• A sequential game is one where players take turns, and each player can see the previous
moves before making a decision.
o Example:
• Chess: Players take turns making moves.
• Tic-Tac-Toe: The game progresses step by step, with each player reacting to the opponent’s move.

2/18/2025 25
 Game Playing
• Non-Cooperative Game
• A non-cooperative game is a game where players compete without forming alliances. Each
player acts in their own best interest.
o Example:
• Chess & Poker: Each player plays for themselves.
• Cooperative Game
• A cooperative game is one where players form alliances or coalitions and share payoffs to
achieve a better outcome.
o Example:
• Business partnerships: Companies form alliances to increase profits.
• Team sports (Football, Basketball): Players work together to win.

2/18/2025 26
 Game Playing
• Complete Information
• A complete information game is one where all players know everything about the game,
including:
• All available actions
• Payoff functions
• Strategies of opponents
o Example:
• Chess: Players see the entire board and know all possible moves.
• Tic-Tac-Toe: Players know all game rules and strategies.
• Incomplete Information
• A game with incomplete information is one where players do not know everything about
the game, such as the opponent's strategy or payoffs.
o Example:
• Poker: Players do not know the opponent’s cards.
• Bidding in an auction: Bidders don’t know the values other players assign to an item.

2/18/2025 27
 Game Playing
• Game Metrics:Game metrics are measurable factors used to evaluate game performance,
player strategies, and AI decision-making in game-playing scenarios.
• Example: Rock-Paper-Scissor

2/18/2025 28
 Game Playing
• Search – no adversary
o Solution is (heuristic) method for finding goal
o Heuristic techniques can find optimal solution
o Evaluation function: estimate of cost from start to goal through given node
o Examples: path planning, scheduling activities

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

2/18/2025 29
 Game Playing
• Game setup:
o Initial state is initial position: e.g. board configuration of chess
o Successor function: list of (move, state) pairs specifying legal moves from any position.
o Terminal test: Is the game over?
o Utility function: Gives numerical value of terminal states. Numerical outcome for the game. E.g.
win (+1), lose (-1) and draw (0) in tic-tac-toe or chess
• Basic Strategy
o Grow a search tree
o Only one player can move at each turn
o Assume we can assign a payoff to each final position- called a utility
o We can propagate values from the final positions
o Assume the opponent always makes moves worst for us
o Pick best moves on own turn

2/18/2025 30
 Game Playing
• Two Player Games:
o Two players
o Zero Sum
o Perfect Information

• The two players take turns and try respectively to maximize and minimize a utility function
• The two players are called respectively as MAX and MIN. We assume that the MAX player
makes the first move. They take turns until the game is over. Winner gets award, loser gets
penalty
• The leaves represent the terminal positions
• Successive nodes represent positions where different players must move. We call the nodes as MAX
or MIN nodes depending on who is the player that must move at that node.
• A game tree could be infinite
• The ply of the node(depth of the deepest node) is the number of moves needed to reach that node (i.e.
arcs from the root of the tree).

2/18/2025 31
 Game Playing
• Example:

2/18/2025 32
 Game Tree for 5 stone Nim
• Start at root node and generate entire search tree till the leaf positions assuming that
the tree is finite. Feasible for only small games.
• Example of simple 5-Stone Nim
o Played with two players and pile of stones
o Each Player removes 1 or 2 stones from the pile
o Player who removes last stone wins the games

2/18/2025 33
 Game Tree for 5 stone Nim
Utility Value: +1 for maximizing player and -1 for minimizing player

2/18/2025 34
 Game Tree for 5 stone Nim

2/18/2025 35
 Partial Game Tree for Tic-Tac-Toe

2/18/2025 36
 Partial Game Tree for Tic-Tac-Toe

2/18/2025 How do we search this tree to find the optimal move? 37

 Minimax strategy: Look ahead and reason backwards
• The Minimax Theorem states that in any two-player zero-sum game, one of the following
is always true:
1. One player has a guaranteed win (if they play optimally).
2. The game will always end in a draw, if both players play perfectly.
• The Minimax Algorithm helps to find the best move for a player (MAX) by assuming the
opponent (MIN) will also play perfectly. If a winning move exists, Minimax will find it.
Otherwise, it will force a draw.
• Minimax ensures optimal play in two-player competitive games.
• It assumes the opponent always plays the best move, so it picks moves accordingly.
• Some games (like Tic-Tac-Toe) will always end in a draw if played perfectly.

2/18/2025 38
 Minimax Algorithm

2/18/2025 39
 Minimax Algorithm

2/18/2025 40
 Example of Minimax Algorithm Execution

2/18/2025 41
 Minimax Algorithm
• Problems with Minimax Search
1. Exponential Time Complexity
1. Minimax explores all possible moves in a game tree.
2. The number of states grows exponentially as the game progresses.
3. For a game with a branching factor b and depth d, the complexity is O(b^d).
4. Example: Chess has b ≈ 35 and d ≈ 50, leading to a massive search space.
2. Limited Depth in Real-Time Games
• Some games (like Chess and Go) have deep game trees, making full search impossible.
Evaluating every possible outcome takes too long for practical decision-making.
3. Assumes Perfect Play
• Minimax assumes the opponent always plays optimally.
• In real-world games, players make mistakes or have different strategies.

2/18/2025 42
 Alpha-Beta Pruning Algorithm
• Depth first search – only considers nodes along a single path at any time
• It gets its name from two parameters that describe the bounds on the backed-up
values that appear anywhere along the path
 = the value of the best (highest-value) choice that we have found so far at any
choice point along the path of MAX
 = the value of the best (lowest-value) choice that we have found so far at any
choice point along the path of MIN
• update values of  and  during search and prunes remaining branches as soon as
the value is known to be worse than the current  or  value for MAX or MIN
respectively.

2/18/2025 43
 Alpha-Beta Pruning Example

2/18/2025 44
 Alpha-Beta Pruning Algorithm

2/18/2025 45
 Alpha-Beta Pruning Algorithm
Solve the given example:

2/18/2025 46
 Alpha-Beta Pruning Algorithm

2/18/2025 47
 Thank You

2/18/2025 48