ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 B.

Tech CSE | JNTUH

ARTIFICIAL INTELLIGENCE
CS832OE | R22 [Link] CSE | JNTUH

UNIT – II: PROBLEM SOLVING METHODS

Based on: Russell & Norvig — Artificial Intelligence: A Modern Approach (2nd Ed.)
Prepared by: Department of Computer Science & Engineering

Dept. of CSE | JNTUH Affiliated College Page 1

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

UNIT II SYLLABUS (R22 Pattern)

Problem Solving Methods | Search Strategies: Searching for Solutions | Uniformed
Search Strategies: Breadth First Search, Depth First Search | Search with Partial
Information (Heuristic Search): Hill Climbing | A*, AO* Algorithms | Problem Reduction |
Game Playing – Adversarial Search | Games | Mini-max Algorithm | Optimal Decisions in
Multiplayer Games | Problem in Game Playing | Alpha-Beta Pruning | Evaluation
Functions

2.1 SEARCHING FOR SOLUTIONS

2.1.1 Search Strategies Overview
Once a problem is formulated, the agent must search for a solution — a sequence of actions that
reaches the goal. The search process explores the state space, which is the set of all possible
states reachable from the initial state by any sequence of actions.
A search strategy is defined by the order in which nodes are expanded. Strategies are evaluated by:
Completeness: Does the algorithm always find a solution if one exists?
Optimality: Does it find the least-cost solution?
Time Complexity: Number of nodes generated/expanded (Big-O in terms of b, d, m)
Space Complexity: Maximum number of nodes stored in memory

2.1.2 The Search Tree and Node Structure

The search tree is superimposed on the state space graph. Each node in the search tree represents
a state and contains:
• STATE: The state it represents in the state space
• PARENT: The node that generated this node
• ACTION: The action applied to the parent to generate this node
• PATH-COST (g): Cost of the path from initial state to this node
• DEPTH: Number of steps along the path from the root

Key Distinction: State vs. Node

A STATE is a configuration of the world. A NODE is a data structure used in the search
tree. Multiple nodes can represent the same state (if the state is reached by different
paths). This is why we must check for repeated states to avoid infinite loops.

The frontier (or open list) is the set of all leaf nodes available for expansion. The explored set (or
closed list) stores all expanded nodes to avoid revisiting states.

2.2 UNINFORMED (BLIND) SEARCH STRATEGIES

Uninformed search strategies have no additional information about states beyond the problem
definition. They cannot estimate how close a state is to the goal. Also called blind search.

Dept. of CSE | JNTUH Affiliated College Page 2

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

2.2.1 Breadth-First Search (BFS)

BFS expands all nodes at depth d before expanding nodes at depth d+1. It uses a FIFO queue for
the frontier.

BFS Algorithm
1. Initialize frontier as a FIFO queue with the initial state node 2. Initialize explored set as
empty 3. Loop: a. If frontier is empty → return FAILURE b. node ← Pop(frontier) [from
front] c. If GOAL-TEST([Link]) → return SOLUTION d. Add [Link] to
explored set e. For each action in ACTIONS([Link]): child ← CHILD-
NODE(problem, node, action) If [Link] not in explored or frontier → Add to
frontier

Properties of BFS:
Property BFS Explanation
Complete? Yes (if b is finite) Always finds a solution if one exists
Optimal? Yes (if step costs = Finds shallowest (fewest steps) solution
1)
Time Complexity O(b^(d+1)) Expands all nodes up to depth d+1
Space Complexity O(b^(d+1)) Stores entire frontier — major problem!

Example BFS trace on 8-puzzle or simple grid:

Start: A. Goal: G. Tree: A→{B,C}, B→{D,E}, C→{F,G}
BFS explores: A, B, C, D, E, F, G (finds G at depth 2). BFS guarantees shortest path!

EXAM TIP: BFS time/space is O(b^(d+1)). If b=10, d=6, BFS generates 11,111,110
nodes and needs ~10 GB of memory at 1KB/node. Memory is the critical limitation of
BFS, not time. This motivates depth-first and iterative deepening searches.

2.2.2 Uniform-Cost Search (UCS)

BFS finds the shallowest solution. When step costs are unequal, we need uniform-cost search. UCS
expands the node with the lowest path cost g(n). It uses a priority queue ordered by g(n).
UCS is optimal and complete for any step cost > ε > 0. It is essentially Dijkstra's algorithm for
shortest paths.
Key difference from BFS: UCS expands based on path cost, not depth. A deeper node with lower
cost will be expanded before a shallower node with higher cost.

2.2.3 Depth-First Search (DFS)

DFS expands the deepest node in the frontier first. It uses a LIFO stack (or recursion) for the
frontier.

DFS Algorithm
1. Initialize frontier as LIFO stack with initial state 2. Loop: a. If frontier empty →

Dept. of CSE | JNTUH Affiliated College Page 3

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

FAILURE b. node ← Pop(frontier) [from top/last] c. If GOAL-TEST(node) →

SOLUTION d. Add node to explored e. Push all children onto stack (right-to-left for
left-to-right exploration)

Property DFS Explanation

Complete? No (infinite states) Can loop forever in infinite state spaces; Yes in
finite acyclic graphs
Optimal? No May find a long solution before a short one
Time Complexity O(b^m) m = max depth; could be much larger than d
Space Complexity O(bm) Linear space! Stores only current path + siblings

The key advantage of DFS is its space efficiency — O(bm) vs O(b^d) for BFS. This makes DFS
practical for large state spaces when memory is limited.
Backtracking Search: A variant of DFS that generates one successor at a time rather than all
successors. Uses even less memory — O(m) total.

2.2.4 Depth-Limited Search (DLS)

DFS's weakness is that it may explore very deep (or infinite) paths. Depth-Limited Search solves
this by imposing a depth limit l — nodes at depth l are treated as having no successors.

DLS Algorithm
DLS(problem, limit): 1. node ← MAKE-NODE([Link]-STATE) 2. return
RECURSIVE-DLS(node, problem, limit) RECURSIVE-DLS(node, problem, limit): 1. If
GOAL-TEST([Link]) → return node 2. Else if DEPTH(node) == limit → return
'cutoff' 3. Else: cutoff_occurred ← False For each action in ACTIONS([Link]):
child ← CHILD-NODE(node, action) result ← RECURSIVE-DLS(child, problem, limit)
If result == 'cutoff': cutoff_occurred ← True Else if result ≠ failure: return result If
cutoff_occurred: return 'cutoff' else return 'failure'

If limit < d, DLS is incomplete. If limit ≥ d, it is complete. Choosing the right limit requires domain
knowledge (e.g., for Romania road map: 9 cities → diameter is at most 9).

2.2.5 Iterative Deepening Depth-First Search (IDDFS)

IDDFS overcomes the depth-limit selection problem by progressively increasing the limit from 0, 1,
2, 3, ... until a solution is found. It combines the memory efficiency of DFS with the completeness
and optimality (for unit costs) of BFS.

IDDFS Algorithm
ITERATIVE-DEEPENING-SEARCH(problem): For depth = 0 to infinity: result ←
DEPTH-LIMITED-SEARCH(problem, depth) If result ≠ cutoff: return result

Strategy Complete? Optimal? Time Space

BFS Yes* Yes* O(b^d) O(b^d)
DFS No No O(b^m) O(bm)
DLS If l≥d No O(b^l) O(bl)

Dept. of CSE | JNTUH Affiliated College Page 4

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

Strategy Complete? Optimal? Time Space

IDDFS Yes* Yes* O(b^d) O(bd)
UCS Yes* Yes O(b^(C*/ε)) O(b^(C*/ε))

*Complete and optimal assuming b is finite and step costs ≥ ε > 0

Why IDDFS is preferred over BFS: In IDDFS, nodes at depth d are regenerated multiple times. But
the top-level nodes are regenerated far fewer times than bottom-level nodes, so the total overhead
is small. For b=10, d=5: BFS generates 1,111,111 nodes; IDDFS generates 123,456 nodes (roughly
d×b^d for large b).

EXAM TIP: IDDFS is often asked as 'the best uninformed search strategy' combining
BFS's completeness/optimality with DFS's space efficiency. Time: O(b^d), Space: O(bd).
Understand WHY it is O(b^d) despite re-expanding nodes — nodes near root are cheap
to regenerate.

2.2.6 Bidirectional Search

Instead of searching forward from initial state to goal, bidirectional search runs two simultaneous
searches — one forward from initial state and one backward from goal — until they meet in the
middle.
If each search has depth d/2, then total nodes = 2 × b^(d/2) << b^d. For b=10, d=6: BFS = 1M
nodes; Bidirectional = 2,200 nodes. Major improvement!
Limitation: We must know what states to test against, the inverse of each action must be defined,
and goal state must be explicit (not just a test).

Dept. of CSE | JNTUH Affiliated College Page 5

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

2.3 HEURISTIC (INFORMED) SEARCH STRATEGIES

Informed search strategies use problem-specific knowledge — called heuristic information — to find
solutions more efficiently. They estimate the cost to reach the goal and use this to choose which
states to explore first.
A heuristic function h(n) estimates the cost of the cheapest path from node n to the goal.
Admissible heuristic: h(n) never overestimates the true cost to reach the goal: h(n) ≤ h*(n) for
all n
Consistent (monotone) heuristic: h(n) ≤ c(n, a, n') + h(n') for every node n and successor n'

2.3.1 Hill-Climbing Search

Hill climbing is the simplest heuristic search. It continuously moves in the direction of increasing
value (for maximization) or decreasing heuristic value (for minimization), trying to reach the
peak/best state.

Hill Climbing Algorithm

Hill-Climbing(problem): 1. current ← MAKE-NODE([Link]-STATE) 2. Loop
forever: a. neighbor ← highest-valued successor of current b. If VALUE(neighbor) ≤
VALUE(current): return current c. current ← neighbor

Hill climbing is like climbing a mountain in thick fog — you can only see what's immediately around
you. It greedily moves to the best neighbor.
Problems with Hill Climbing:
• Local Maxima: A peak that is higher than its neighbors but lower than the global maximum.
The algorithm gets stuck here.
• Ridges: A sequence of local maxima that makes progress very difficult because movement
in any direction leads downward.
• Plateaux (Flat local maxima): An area where all neighbors have the same evaluation value.
The algorithm may wander randomly.

Variants to Escape Local Maxima:

Random Restart Hill Climbing: Restart the search from randomly chosen initial states. With
enough restarts, finds the global optimum eventually.
Simulated Annealing: Occasionally accepts worse moves with probability e^(-ΔE/T), where T is
'temperature' that decreases over time. Provably finds global optimum given infinite time.
Local Beam Search: Tracks k states simultaneously. Each iteration generates all successors of
all k states and selects the k best.

EXAM TIP: Hill climbing questions often ask about the three problems: local maxima,
ridges, plateaux. Also know the solutions: random restart, simulated annealing. The 8-
queens problem is a classic hill-climbing example — heuristic = number of attacking pairs
of queens.

Dept. of CSE | JNTUH Affiliated College Page 6

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

2.3.2 Best-First Search

Best-First Search is a general search strategy that uses an evaluation function f(n) to choose which
node to expand next. The node with the best (lowest) f(n) is expanded first.
Greedy Best-First Search: f(n) = h(n). Expands the node closest to the goal according to the
heuristic. Fast but not optimal.
A* Search: f(n) = g(n) + h(n). Combines actual cost from start (g) with estimated cost to goal (h).
Both complete and optimal when h is admissible.

2.3.3 Greedy Best-First Search

Greedy BFS tries to expand the node that appears to be closest to the goal using only the heuristic:
f(n) = h(n). It ignores the cost already incurred to reach n.
Example: Romania map. Straight-line distance (SLD) heuristic from city to Bucharest:
• h(Arad) = 366, h(Sibiu) = 253, h(Fagaras) = 176, h(Bucharest) = 0
• Greedy BFS finds: Arad → Sibiu → Fagaras → Bucharest (Total: 450)
• But optimal route is: Arad → Sibiu → Rimnicu → Pitesti → Bucharest (418)

Property Greedy BFS

Complete? No (can loop in cyclic graphs without explored set check)
Optimal? No
Time Complexity O(b^m) worst case, but often much better with good heuristic
Space Complexity O(b^m) — stores all nodes in memory

2.3.4 A* Search Algorithm

A* is the most widely known form of best-first search. It evaluates nodes using: f(n) = g(n) + h(n),
where g(n) is the cost to reach node n and h(n) is the estimated cost from n to goal.
A* combines Uniform-Cost Search (g only) and Greedy BFS (h only), getting the best of both
worlds.

A* Algorithm
ASTAR-SEARCH(problem): 1. frontier ← priority queue ordered by f(n) = g(n) + h(n), with
initial node 2. explored ← empty set 3. Loop: a. If frontier empty → FAILURE b. node
← Extract-Min(frontier) [lowest f(n)] c. If GOAL-TEST([Link]) → return
SOLUTION d. Add [Link] to explored e. For each action in
ACTIONS([Link]): child ← CHILD-NODE(problem, node, action) If
[Link] not in explored: Insert child into frontier (or update if already there with
lower g)

Conditions for Optimality of A*

A* is optimal if the heuristic h(n) is admissible (for tree search) or consistent (for graph search).
Proof sketch: If h is admissible, whenever A* selects a node n for expansion, it has found the
optimal path to n. This is because f(n) = g(n) + h(n) ≤ g(n) + h*(n) = f*(n) for the optimal path.

Dept. of CSE | JNTUH Affiliated College Page 7

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

A* on Romania (SLD heuristic):

Step Expand f values in frontier
1 Arad (f=366) Sibiu(f=393), Timisoara(f=447), Zerind(f=449)
2 Sibiu (f=393) Rimnicu(f=413), Fagaras(f=415.4), Pitesti(f=417),
Timisoara(f=447)
3 Rimnicu (f=413) Fagaras(f=415), Pitesti(f=417), Craiova(f=526)...
4 Fagaras (f=415) Bucharest(f=450), Pitesti(f=417)...
5 Pitesti (f=417) Bucharest(f=418) — optimal path found!

A* finds Arad → Sibiu → Rimnicu → Pitesti → Bucharest with total cost 418, which is optimal.

Properties of A*
Property A* (admissible h) Notes
Complete? Yes Assuming b finite and step costs ≥ ε
Optimal? Yes With admissible (tree) or consistent (graph)
heuristic
Optimally Efficient? Yes No other algorithm expands fewer nodes for
same guarantee
Time Complexity O(b^(h*-h) d) Exponential unless |h(n) - h*(n)| = O(log h*(n))
Space Complexity O(b^d) Keeps all nodes in memory — major weakness

Memory-Bounded Variants:
IDA* (Iterative Deepening A*): Uses iterative deepening with f-cost limit instead of depth limit.
Memory O(bd), finds optimal solution.
RBFS (Recursive Best-First Search): Simulates A* using O(bd) space. Slightly more node
regeneration than A*.
MA* / SMA* (Simplified Memory-Bounded A*): Uses available memory completely, discards
worst leaf nodes when memory fills up.

EXAM TIP: A* is the most important search algorithm in this unit. Know: f(n)=g(n)+h(n),
admissibility condition h(n)≤h*(n), trace A* on Romania map, and properties table.
Common 10-mark question: 'Apply A* algorithm to find the shortest path from Arad to
Bucharest given the straight-line distances.'

2.3.5 Heuristic Functions for 8-Puzzle

The 8-puzzle has two well-known admissible heuristics:
h1 — Misplaced Tiles: Count of tiles not in their goal position (excluding blank). h1 ≤ h*
because each misplaced tile needs at least one move.
h2 — Manhattan Distance: Sum of distances (vertical + horizontal) of each tile from its goal
position. h2 ≤ h* because each move can reduce a tile's Manhattan distance by at most 1.

Dept. of CSE | JNTUH Affiliated College Page 8

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

Since h2(n) ≥ h1(n) for all n, h2 dominates h1. A* with h2 expands fewer nodes than with h1. For
random 8-puzzle instances, A* with h2 expands about 1200 nodes; with h1 about 13000 nodes.
How to construct better heuristics: Use relaxed problems (remove constraints) or pattern databases.

Dept. of CSE | JNTUH Affiliated College Page 9

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

2.4 AO* ALGORITHM (AND-OR GRAPHS)

2.4.1 Problem Reduction and AND-OR Graphs
Not all problems can be solved by simple state-space search. Problem reduction decomposes a
problem into subproblems. To solve the original problem, ALL subproblems must be solved (AND
condition) or ANY one subproblem must be solved (OR condition). This leads to AND-OR graphs.
AND-OR Graph:
• OR nodes: A node where any one successor can be chosen (regular state-space search)
• AND nodes (marked with an arc): ALL successors must be solved
• A solution is a subgraph where the initial node is solved and every AND node has all
successors in the solution graph

Example: To prove theorem T, we can either use Method A (OR choice) or use Lemmas L1 AND L2
(AND node — both must be proved).

2.4.2 AO* Algorithm

AO* (And-Or A*) is the heuristic search algorithm for AND-OR graphs. It maintains a cost estimate
for each node and propagates costs backwards through AND/OR nodes.

AO* Algorithm (Conceptual)

1. Initialize: graph has only initial node with h=h(s) 2. Select best partial solution graph
(using f values) 3. Expand one unexpanded tip node from this graph 4. Add children;
compute h for each leaf 5. Propagate revised cost estimates backward: - For OR node:
f(n) = min over children c of [cost(n,c) + f(c)] - For AND node: f(n) = sum over children c
of [cost(n,c) + f(c)] 6. Mark nodes SOLVED if all descendants are solved or leaf nodes at
goal 7. If initial node SOLVED → SUCCESS; if UNSOLVABLE → FAILURE 8. Repeat
from step 2

Cost propagation rules:

• OR node: f(n) = min{c(n, ni) + f(ni)} — pick cheapest child path
• AND node: f(n) = Σ{c(n, ni) + f(ni)} — must solve all children

AO* guarantees finding optimal solutions in AND-OR graphs when heuristic is admissible. It
expands nodes in best-first order based on the estimated solution cost.

EXAM TIP: AO* is commonly asked with AND-OR graph diagrams. You must trace the
algorithm step by step, showing how costs propagate backward. AND nodes sum costs;
OR nodes take minimum cost. AO* is used for hierarchical planning and PROLOG-style
reasoning.

Dept. of CSE | JNTUH Affiliated College Page 10

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

2.5 GAME PLAYING — ADVERSARIAL SEARCH

2.5.1 Games as Search Problems
Games represent a class of environments that are multi-agent, partially or fully observable,
deterministic or stochastic. Two-player zero-sum games (like chess, tic-tac-toe) are the most
studied:
Zero-sum: One player's gain is exactly the other's loss. If MAX wins (+1), MIN loses (-1).
Perfect information: Fully observable games like chess, checkers, Go
Imperfect information: Partially observable games like poker, bridge

Game definition components:

• S0: Initial state (e.g., empty chess board)
• PLAYER(s): Which player has the move in state s
• ACTIONS(s): Legal moves in state s
• RESULT(s, a): Transition model (outcome of move a in state s)
• TERMINAL-TEST(s): True when game is over (terminal state)
• UTILITY(s, p): Defines the final numeric value for player p in terminal state s

2.5.2 Mini-Max Algorithm

The minimax algorithm provides a strategy for two-player zero-sum games. MAX tries to maximize
utility, MIN tries to minimize utility. MIN and MAX alternate moves.

Minimax Algorithm
MINIMAX(state, player): MAX-VALUE(state): If TERMINAL-TEST(state): return
UTILITY(state) v ← -∞ For each a in ACTIONS(state): v ← max(v, MIN-
VALUE(RESULT(state, a))) return v MIN-VALUE(state): If TERMINAL-TEST(state):
return UTILITY(state) v ← +∞ For each a in ACTIONS(state): v ← min(v, MAX-
VALUE(RESULT(state, a))) return v

Minimax Example — Tic-Tac-Toe:

Trace from a position where it's MAX's turn (X). The tree expands all possible moves, assigns
terminal values (+1 = X wins, -1 = O wins, 0 = draw), and backs up values using max at MAX nodes
and min at MIN nodes.

Property Minimax Details

Complete? Yes (in finite game But game trees can be astronomically large
tree)
Optimal? Yes against optimal Finds best move assuming opponent plays
opponent optimally
Time Complexity O(b^m) Must explore entire game tree
Space Complexity O(bm) Like DFS — only current path on stack

Dept. of CSE | JNTUH Affiliated College Page 11

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

Practical Challenge: Chess has branching factor ≈ 35 and game length ≈ 80 moves. O(35^80) =
10^123 nodes — more than atoms in the universe! We need to prune the search tree.

2.5.3 Optimal Decisions in Multiplayer Games

When there are more than two players, each player has their own utility vector [u1, u2, ..., un]. At
each node, the current player chooses the action that maximizes their own utility component. There
is no longer a simple minimax backup — instead, each player backs up the value vector that
maximizes their own component.
Alliances can form: if two players can cooperate against the third, the game becomes more complex
than zero-sum two-player games. Most game AI focuses on two-player zero-sum games for
simplicity.

2.5.4 Alpha-Beta Pruning

Alpha-beta pruning reduces the number of nodes that must be evaluated in the minimax tree. It
prunes (removes) branches that cannot possibly influence the final decision.

Key Idea of Alpha-Beta

Alpha (α): Best value MAX can guarantee along the current path (initialized to -∞) Beta
(β): Best value MIN can guarantee along the current path (initialized to +∞) Prune a node
when: - At MIN node: if current value ≤ α (MAX already has better option) → prune - At
MAX node: if current value ≥ β (MIN already has better option) → prune

Alpha-Beta Algorithm
ALPHA-BETA-SEARCH(state): return action in ACTIONS(state) with max ALPHA-
BETA-VALUE MAX-VALUE(state, α, β): If TERMINAL-TEST(state): return
UTILITY(state) v ← -∞ For each a in ACTIONS(state): v ← max(v, MIN-
VALUE(RESULT(state,a), α, β)) If v ≥ β: return v [prune remaining] α ← max(α, v)
return v MIN-VALUE(state, α, β): If TERMINAL-TEST(state): return UTILITY(state) v
← +∞ For each a in ACTIONS(state): v ← min(v, MAX-VALUE(RESULT(state,a), α,
β)) If v ≤ α: return v [prune remaining] β ← min(β, v) return v

Effectiveness of Alpha-Beta Pruning:

• Best case (perfect ordering): O(b^(m/2)) — effectively doubles searchable depth
• Average case (random ordering): O(b^(3m/4))
• Worst case (no pruning): O(b^m) — same as minimax

With b=35 and perfect ordering: minimax explores 35^m nodes, alpha-beta explores only 35^(m/2) =
(35^m)^0.5 nodes. For chess: reduces effective branching factor from 35 to about 6, allowing 2× the
search depth in same time!

Alpha-Beta Trace Example:

Consider a game tree with values at leaves: [3, 5, 2, 9, 1, 4, 7, 6]. Show α-β cutoffs step by step:
Step Node Action α β Prune?
1 Root (MAX) Explore left subtree -∞ +∞ No

Dept. of CSE | JNTUH Affiliated College Page 12

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

Step Node Action α β Prune?

2 Left MIN node Left child = 3 -∞ 3 No
3 Left MIN node Right child = 5 -∞ 3 No (take min=3)
4 Root (MAX) Left = 3, update α=3 3 +∞ No
5 Right MIN Left child = 2 3 2 YES (2 ≤ α=3)
node
6 Root Return max(3) = 3 3 +∞ Done

EXAM TIP: Alpha-Beta questions always ask you to trace the algorithm and show which
branches are pruned. Remember: At MAX node, prune if v ≥ β. At MIN node, prune if v ≤
α. Alpha is the current best for MAX (updates at MAX nodes), Beta is current best for MIN
(updates at MIN nodes). Move ordering matters — evaluate best moves first for
maximum pruning.

2.5.5 Evaluation Functions

Real games (chess, Go) have state spaces too large for complete search even with alpha-beta. We
use evaluation functions (heuristic functions) to estimate the utility of non-terminal states.
A good evaluation function should:
• Order terminal states the same way as the true utility function
• Not be too time-consuming to compute
• Strongly correlate with actual chances of winning

For chess, a typical evaluation function uses material value:

Piece Value Notes
Pawn 1 Baseline unit
Knight 3 Worth about 3 pawns
Bishop 3 Slightly better than knight in open positions
Rook 5 Major piece
Queen 9 Most powerful piece
King ∞ Cannot be traded

Evaluation = (White material) - (Black material) + positional bonuses (king safety, pawn structure,
center control, piece mobility).
Horizon Effect: Alpha-beta can make bad decisions by not seeing dangers just beyond its search
horizon. Quiescence search extends the search for 'quiet' positions before applying evaluation.

2.5.6 Problems in Game Playing

Several issues arise in practical game AI:
• Time Constraint: Programs must move within a fixed time limit. Use iterative deepening —
always have a best move available, deepen as time allows.

Dept. of CSE | JNTUH Affiliated College Page 13

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

• Opening Books: Store thousands of expert-analyzed opening positions; avoid spending time
on well-studied early game.
• Endgame Databases: Pre-compute optimal play for positions with few pieces remaining
(chess endgames with 5 or fewer pieces are completely solved).
• Stochastic Games: With chance nodes (dice, card draws), use expectiminimax: chance
nodes compute weighted average of successor values.
• Imperfect Information: Cannot directly apply minimax. Strategies include belief states
(tracking possible states) or Monte Carlo sampling.

2.5.7 Monte Carlo Tree Search (MCTS)

Modern approach used in AlphaGo and many successful game AIs. MCTS builds a game tree by
simulating random playouts (rollouts):
• Selection: Traverse tree using UCB1 formula to balance exploration and exploitation
• Expansion: Add one or more child nodes
• Simulation: Play randomly to terminal state
• Backpropagation: Update visit counts and win statistics up the tree

MCTS does not require an evaluation function — it estimates position quality through simulation
results. Combined with deep neural networks (as in AlphaZero), it achieves superhuman
performance.

Dept. of CSE | JNTUH Affiliated College Page 14

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

2.6 SUMMARY AND EXAM QUESTIONS — UNIT II

Comparison of All Search Strategies
Strategy Complete Optimal? Time Space Heuristic?
?
BFS Yes Yes (unit O(b^d) O(b^d) No
cost)
DFS No No O(b^m) O(bm) No
(infinite)
DLS If l≥d No O(b^l) O(bl) No
IDDFS Yes Yes (unit O(b^d) O(bd) No
cost)
UCS Yes Yes O(b^(C*/ε)) O(b^(C*/ε)) No
Greedy BFS No No O(b^m) O(b^m) Yes (h only)
A* Yes Yes O(b^d) O(b^d) Yes (g+h)
(admissibl
e)
Hill Climbing No No O(∞) O(1) Yes
Minimax Yes (finite) Yes vs O(b^m) O(bm) No
optimal
Alpha-Beta Yes (finite) Yes vs O(b^(m/2)) O(bm) No
optimal

Previous Year Questions — Unit II

Question Marks Year
Explain BFS and DFS with algorithms and examples. 10M 2023
Compare their complexities.
What is IDDFS? Why is it preferred over BFS? 10M 2022
Explain with algorithm and example.
Explain A* algorithm. What conditions must a 10M 2023
heuristic satisfy for A* to be optimal?
Apply A* algorithm to find the shortest path from Arad 10M 2021
to Bucharest using SLD heuristic.
Explain the minimax algorithm with a suitable game 10M 2022
tree example.
What is alpha-beta pruning? Trace through a game 10M 2023
tree showing pruned branches.
Explain hill climbing search. What are its limitations? 10M 2021
How are they overcome?
Write notes on: (a) AO* Algorithm (b) Evaluation 10M 2022
Functions in Game Playing
What is the horizon effect in game playing? Explain 5M 2023

Dept. of CSE | JNTUH Affiliated College Page 15

ARTIFICIAL INTELLIGENCE | UNIT II: PROBLEM SOLVING METHODS | R22 [Link] CSE | JNTUH

Question Marks Year

quiescence search.
Compare admissible and consistent heuristics. Give 5M 2022
examples for 8-puzzle.

Key Formulas to Remember

Quick Reference — Formulas
BFS: Time = O(b^(d+1)), Space = O(b^(d+1)) DFS: Time = O(b^m), Space = O(bm)
IDDFS: Time = O(b^d), Space = O(bd) A*: f(n) = g(n) + h(n); Admissibility: h(n) ≤ h*(n);
Consistency: h(n) ≤ c(n,a,n') + h(n') Minimax: Time = O(b^m), Space = O(bm) Alpha-Beta
best case: O(b^(m/2)) — doubles effective search depth Manhattan Distance (8-puzzle):
h2(n) = Σ|xi-xgi| + |yi-ygi| for each tile i

EXAM TIP: Unit II carries approximately 30-40% of the exam marks. Focus on: (1) Trace
BFS/DFS on small graphs, (2) Apply A* with complete trace and g/h/f values table, (3)
Minimax trace with backed-up values, (4) Alpha-beta trace showing α, β values and
pruning. Always draw trees for these problems — they earn most marks.

Dept. of CSE | JNTUH Affiliated College Page 16