Search Algorithms

Overview

The systematic exploration of a problem's state space to find a solution is one of the most fundamental paradigms in Artificial Intelligence. This process, known as search, provides a powerful framework for problem-solving, from navigating a route between two cities to solving complex logical puzzles. In this chapter, we shall explore the foundational algorithms that enable an intelligent agent to methodically find a path from an initial state to a desired goal state. A thorough understanding of these techniques is not merely an academic exercise; it is essential for building systems that can reason, plan, and make decisions in a structured manner.

Our study is organized into three principal categories of search. We begin with Uninformed Search strategies, which explore the search space systematically without any domain-specific knowledge beyond the problem's definition. Subsequently, we advance to Informed Search, where we introduce the concept of a heuristic function—an estimate of the cost to reach a goal—to guide the search more efficiently toward a solution. Finally, we will examine Adversarial Search, a specialized category designed for competitive, multi-agent environments such as games, where the agent must make optimal decisions while accounting for the actions of an opponent.

For the GATE examination, proficiency in search algorithms is paramount. Questions frequently test not only the procedural execution of these algorithms but also a deep conceptual understanding of their properties. Candidates are expected to analyze and compare algorithms based on their completeness, optimality, time complexity (e.g., $O(b^d)$ ), and space complexity. Mastery of this chapter will equip you with the analytical tools necessary to deconstruct complex problems and evaluate the trade-offs inherent in different search strategies, a skill that is consistently assessed in the examination.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Uninformed Search | Systematic exploration without domain-specific knowledge. |
| 2 | Informed Search | Using heuristic functions to guide search. |
| 3 | Adversarial Search | Optimal decision-making in competitive environments. |

---

Learning Objectives

---

We now turn our attention to Uninformed Search...

Part 1: Uninformed Search

Introduction

In the domain of Artificial Intelligence, a fundamental problem is that of search: finding a sequence of actions that leads from an initial state to a desired goal state. Search algorithms provide the mechanism for exploring the state space to find such a solution. We begin our study with the most basic class of these algorithms, known as Uninformed Search, or blind search.

These methods are termed "uninformed" because they are provided with no domain-specific knowledge beyond the problem definition itself. They do not possess any information about the cost or distance to the goal, nor do they have a preference for which non-goal state is more promising than another. The search strategy is therefore systematic but blind, exploring the state space based on the order and structure of the nodes. Despite their simplicity, these algorithms form the foundational bedrock upon which more sophisticated, informed search techniques are built. For the GATE examination, a thorough understanding of their mechanics, properties, and comparative performance is essential.

---

Key Concepts

The core of any search algorithm is the systematic exploration of the state space graph. This is managed by maintaining a collection of discovered but not-yet-explored nodes, often called the fringe or frontier. The specific data structure used to manage this fringe dictates the nature of the search. We will also maintain a set of already explored nodes, often called the closed list or explored set, to prevent redundant exploration in graph search.

Let us consider the following state space graph for our worked examples. The start state is 'S' and the goal state is 'G'.

S


A


B


C


D

G

For all examples, we will assume that when a node is expanded, its successors are added to the fringe in alphabetical order.

1. Breadth-First Search (BFS)

Breadth-First Search explores the state space layer by layer. It expands the shallowest unexpanded node first. This behavior is achieved by implementing the fringe as a First-In, First-Out (FIFO) queue. We place newly generated successor nodes at the back of the queue, and the node to be expanded next is always taken from the front.

BFS is guaranteed to find the shallowest goal state, which, for a uniform step cost, corresponds to the optimal solution (the path with the fewest edges).

Worked Example: BFS

Problem: Find a path from state 'S' to state 'G' in the example graph using BFS. List the sequence of nodes expanded.

Solution:

We maintain a queue for the fringe and a set for the explored nodes.

Initial State:

• Fringe (Queue): `[S]`


• Explored: `{}`

Step 1: Dequeue 'S' and expand it. Add 'S' to Explored. Successors are 'A', 'B'. Add them to the queue.

• Node Expanded: `S`


• Fringe (Queue): `[A, B]`


• Explored: `{S}`

Step 2: Dequeue 'A' and expand it. Add 'A' to Explored. Successors are 'C', 'D'. Add them to the queue.

• Node Expanded: `A`


• Fringe (Queue): `[B, C, D]`


• Explored: `{S, A}`

Step 3: Dequeue 'B' and expand it. Add 'B' to Explored. Successor is 'D'. 'D' is already in the fringe, so we typically do not add it again in a graph search. (Even if we did, it would be explored later).

• Node Expanded: `B`


• Fringe (Queue): `[C, D]`


• Explored: `{S, A, B}`

Step 4: Dequeue 'C' and expand it. Add 'C' to Explored. Successor is 'G'. Add 'G' to the queue.

• Node Expanded: `C`


• Fringe (Queue): `[D, G]`


• Explored: `{S, A, B, C}`

Step 5: Dequeue 'D' and expand it. Add 'D' to Explored. Successor is 'G'. 'G' is already in the fringe.

• Node Expanded: `D`


• Fringe (Queue): `[G]`


• Explored: `{S, A, B, C, D}`

Step 6: Dequeue 'G'. Goal test is successful. The search terminates.

• Node Expanded: `G`


• Fringe (Queue): `[]`


• Explored: `{S, A, B, C, D, G}`

Answer: The sequence of expanded nodes is S, A, B, C, D, G. The path found is S -> A -> C -> G.

---

---

2. Depth-First Search (DFS)

Depth-First Search explores the state space by going as deep as possible along each branch before backtracking. This is achieved by implementing the fringe as a Last-In, First-Out (LIFO) stack. When a node is expanded, its successors are pushed onto the stack, and the node to be expanded next is always popped from the top of the stack.

DFS is not optimal; it may find a longer path to a goal before it finds a shorter one. Furthermore, in infinite state spaces or graphs with cycles, a pure tree-search DFS may never terminate. Using an explored list (graph search) prevents infinite loops in finite graphs with cycles.

Worked Example: DFS

Problem: Find a path from state 'S' to state 'G' in the example graph using DFS. List the sequence of nodes expanded.

Solution:

We maintain a stack for the fringe and a set for the explored nodes.

Initial State:

• Fringe (Stack): `[S]`


• Explored: `{}`

Step 1: Pop 'S' and expand it. Add 'S' to Explored. Successors are 'A', 'B'. Push them onto the stack (alphabetical order: A then B, so B is on top).

• Node Expanded: `S`


• Fringe (Stack): `[A, B]` (Top -> B)


• Explored: `{S}`

Step 2: Pop 'B' and expand it. Add 'B' to Explored. Successor is 'D'. Push 'D' onto the stack.

• Node Expanded: `B`


• Fringe (Stack): `[A, D]` (Top -> D)


• Explored: `{S, B}`

Step 3: Pop 'D' and expand it. Add 'D' to Explored. Successor is 'G'. Push 'G' onto the stack.

• Node Expanded: `D`


• Fringe (Stack): `[A, G]` (Top -> G)


• Explored: `{S, B, D}`

Step 4: Pop 'G'. Goal test is successful. The search terminates.

• Node Expanded: `G`

Answer: The sequence of expanded nodes is S, B, D, G. The path found is S -> B -> D -> G. Observe that this path is longer than the one found by BFS, and fewer nodes were expanded to find a solution.

---

3. Iterative Deepening Depth-First Search (IDDFS)

Iterative Deepening Search (IDS) is a hybrid strategy that combines the space-efficiency of DFS with the completeness and optimality (for unit costs) of BFS. It works by performing a series of depth-limited searches (DLS). It first runs DLS with a depth limit of 0, then 1, then 2, and so on, until a goal is found.

Although it seems wasteful because it re-generates nodes in upper levels of the search tree multiple times, the overhead is not prohibitive. The number of nodes at a given level grows exponentially with depth, so the majority of the work is done at the deepest level of the search, which is only generated once.

---

Problem-Solving Strategies

When faced with a search problem in the GATE exam, a systematic approach is critical. The problem statement often contains subtle but crucial constraints, such as tie-breaking rules or whether previously visited states are re-explored.

---

Common Mistakes

A frequent source of error in GATE is a misunderstanding of the fundamental mechanics of the search algorithms or misinterpretation of the problem statement.

---

Practice Questions

:::question type="MCQ" question="Consider a state space where the start state is 2. The successor function for a state numbered $n$ returns two states: $2n$ and $2n+1$. The goal state is 11. Assume that when multiple nodes are available for expansion, the one with the lower number is chosen first. Which algorithm expands fewer nodes to find the goal?" options=["BFS expands fewer nodes than DFS.", "DFS expands fewer nodes than BFS.", "Both expand the same number of nodes.", "Neither algorithm can find the goal."] answer="DFS expands fewer nodes than BFS." hint="Trace both BFS and DFS step-by-step, maintaining the fringe and explored list. The tie-breaking rule is to expand the lower-numbered node first." solution="
BFS Trace:

• Start: Fringe=[2], Explored={}


• Expand 2: Fringe=[4, 5], Explored={2}


• Expand 4: Fringe=[5, 8, 9], Explored={2, 4}


• Expand 5: Fringe=[8, 9, 10, 11], Explored={2, 4, 5}


• Expand 8: Fringe=[9, 10, 11, 16, 17], Explored={2, 4, 5, 8}


• Expand 9: Fringe=[10, 11, 16, 17, 18, 19], Explored={2, 4, 5, 8, 9}


• Expand 10: Fringe=[11, 16, 17, 18, 19, 20, 21], Explored={2, 4, 5, 8, 9, 10}


• Expand 11: Goal found.


• BFS Expanded Nodes: 2, 4, 5, 8, 9, 10, 11 (Total: 7)

DFS Trace (assuming successors $2n$ and $2n+1$ are pushed onto the stack in increasing order, so $2n+1$ is on top and expanded first):

• Start: Fringe (Stack)=[2], Explored={}


• Expand 2: Pop 2. Successors: 4, 5. Push 4, then 5. Fringe=[4, 5]. Explored={2}. (5 is on top)


• Expand 5: Pop 5. Successors: 10, 11. Push 10, then 11. Fringe=[4, 10, 11]. Explored={2, 5}. (11 is on top)


• Expand 11: Pop 11. Goal found.


• DFS Expanded Nodes: 2, 5, 11 (Total: 3)

Therefore, DFS expands fewer nodes.
Answer: \boxed{DFS expands fewer nodes than BFS.}
"
:::

:::question type="NAT" question="In the state space graph provided in the worked example (with start S and goal G), how many nodes are in the fringe (queue) immediately after node 'B' is expanded by a Breadth-First Search?" answer="2" hint="Follow the step-by-step trace of BFS. After expanding 'B', list the contents of the queue." solution="
Step 1: Initial Fringe: `[S]`
Step 2: Expand S. Fringe becomes `[A, B]`
Step 3: Expand A. Fringe becomes `[B, C, D]`
Step 4: Expand B. Successor is D. Since D is already in the fringe, it is not added again. The fringe becomes `[C, D]`.
The number of nodes in the fringe is 2.
Answer: \boxed{2}
"
:::

:::question type="MSQ" question="Which of the following statements about Iterative Deepening Depth-First Search (IDDFS) are true?" options=["IDDFS has the same space complexity as Breadth-First Search.", "IDDFS is guaranteed to find an optimal solution if all step costs are equal.", "IDDFS combines the memory benefits of DFS with the completeness of BFS (for finite branching factor).", "In the worst case, the time complexity of IDDFS is significantly higher than that of BFS."] answer="B,C" hint="Analyze the properties of IDDFS in terms of completeness, optimality, time, and space complexity relative to BFS and DFS." solution="

• A is false: IDDFS has a space complexity of $O(bd)$, which is the same as DFS, not BFS ($O(b^d)$). This is its primary advantage.


• B is true: Because IDDFS explores the search space level by level (similar to BFS), it is guaranteed to find the shallowest goal. If step costs are uniform, this corresponds to the optimal path.


• C is true: This statement accurately describes the main benefit of IDDFS. It uses space proportional to the depth of the search (like DFS) but is complete (like BFS).


• D is false: While IDDFS does re-generate nodes, the overhead is not asymptotically significant. For a tree, the time complexity of both BFS and IDDFS is $O(b^d)$. The constant factors for IDDFS are slightly larger, but it is not considered 'significantly higher' in terms of asymptotic complexity.

Answer: \boxed{B,C}
"
:::

---

Summary

---

What's Next?

---

---

Part 2: Informed Search

Introduction

In our study of search algorithms, we have previously examined uninformed or "blind" search strategies. Such methods, while systematic, are often inefficient as they possess no problem-specific knowledge to guide their exploration of the state space. They methodically explore paths without any preference for one direction or another. We now turn our attention to a more powerful class of algorithms known as informed search, or heuristic search.

Informed search strategies leverage problem-specific knowledge to find solutions more efficiently. The core of this approach lies in the use of a heuristic function, which estimates the "desirability" of expanding a node. This function provides an estimate of the cost from a given node to the nearest goal state. By prioritizing nodes that appear to be closer to the goal, informed search algorithms can often find solutions much more quickly than their uninformed counterparts, significantly reducing the search space that must be explored. The central idea is to expand the most promising node first, a principle embodied in the family of algorithms known as Best-First Search.

---

Key Concepts

1. Greedy Best-First Search

Greedy Best-First Search is an informed search algorithm that attempts to expand the node that is judged to be closest to the goal. It evaluates nodes using only the heuristic function, effectively making a "greedy" choice at each step.

The evaluation function for Greedy Best-First Search is simply:

The algorithm maintains a priority queue of nodes to be explored, ordered by increasing $h(n)$ values. At each step, it expands the node with the lowest heuristic value. While this strategy can be very fast, it is susceptible to being misled by an imperfect heuristic. Since it ignores the cost already incurred to reach a node ($g(n)$), it may follow a path that seems promising initially but ultimately proves to be a long and costly dead end. Consequently, Greedy Best-First Search is neither optimal nor complete (it can get stuck in loops in infinite state spaces).

2. A* Search Algorithm

The A* search algorithm is arguably the most widely known and effective informed search algorithm. It improves upon Greedy Best-First Search by considering both the cost to reach the current node and the estimated cost to get from the current node to the goal. It seeks to find a path with the minimum total cost.

A* evaluates nodes by combining $g(n)$, the cost of the path from the start node to node $n$, and $h(n)$, the heuristic estimate of the cost from $n$ to the goal.

The A algorithm maintains a priority queue of nodes to visit (the frontier or open list), ordered by the lowest $f(n)$ value. It also keeps track of nodes already visited (the explored set or closed list*). At each step, it removes the node with the lowest $f(n)$ value from the frontier, expands it by generating its successors, and adds the successors to the frontier.

Worked Example:

Problem:
Consider the following state graph where the start node is S and the goal node is G. The numbers on the edges represent the actual path costs, and the heuristic value $h(n)$ for each node is given. Find the sequence of nodes expanded by the A* algorithm.

Sh=10
Ah=9
Bh=5
Ch=4
Gh=0
1
2
8
3
5

Solution:

We trace the algorithm's execution, maintaining a priority queue (Frontier) ordered by $f(n)$. The expanded nodes are tracked separately.

Step 1: Initialize the frontier with the start node S.

• Frontier: { S }
• Expanded: { }
• Calculation for S: $g(S)=0$, $h(S)=10 \implies f(S) = 0 + 10 = 10$.
• Frontier state: { (S, f=10) }

Step 2: Expand S (lowest $f$-value).

• Node expanded: S
• Successors: A, B
• Expanded: { S }
• Calculation for A: $g(A) = g(S) + \text{cost}(S,A) = 0 + 1 = 1$. $h(A)=9 \implies f(A) = 1 + 9 = 10$.
• Calculation for B: $g(B) = g(S) + \text{cost}(S,B) = 0 + 2 = 2$. $h(B)=5 \implies f(B) = 2 + 5 = 7$.
• Frontier state: { (B, f=7), (A, f=10) }

Step 3: Expand B (lowest $f$-value).

• Node expanded: B
• Successors: C
• Expanded: { S, B }
• Calculation for C from B: $g(C) = g(B) + \text{cost}(B,C) = 2 + 3 = 5$. $h(C)=4 \implies f(C) = 5 + 4 = 9$.
• Frontier state: { (C, f=9), (A, f=10) }

Step 4: Expand C (lowest $f$-value).

• Node expanded: C
• Successors: G
• Expanded: { S, B, C }
• Calculation for G from C: $g(G) = g(C) + \text{cost}(C,G) = 5 + 5 = 10$. $h(G)=0 \implies f(G) = 10 + 0 = 10$.
• Frontier state: { (A, f=10), (G, f=10) }
• We observe a tie in $f$-values between A and G. The tie-breaking rule can vary, but a common one is FIFO (First-In, First-Out). Since A was added to the frontier before G, we expand A next.

Step 5: Expand A (chosen by tie-breaking).

• Node expanded: A
• Successors: C
• Expanded: { S, B, C, A }
• Calculation for C from A: $g(C) = g(A) + \text{cost}(A,C) = 1 + 8 = 9$.
• We observe that a path to C already exists in the frontier with $g(C)=5$. Since the new path via A is more expensive ($g=9$), we discard it. The frontier remains unchanged.
• Frontier state: { (G, f=10) }

Step 6: Expand G (lowest $f$-value).

• Node expanded: G
• G is the goal state. The search terminates.
• Expanded: { S, B, C, A, G }

Answer: The sequence of nodes expanded by the A* algorithm is S, B, C, A, G.

---

3. Properties of Heuristics

The performance and correctness of A* search are critically dependent on the properties of the heuristic function $h(n)$.

Admissibility

The most important property for ensuring optimality is admissibility.

If the heuristic function used by A is admissible, then A is guaranteed to return an optimal solution. An admissible heuristic is optimistic; it always assumes the path to the goal is at least as good as the true path.

Consistency

Consistency is a stronger condition than admissibility. It is also known as the monotonicity property.

If a heuristic is consistent, it can be proven that it is also admissible. The primary advantage of using a consistent heuristic is that it guarantees that the $f$-values of the nodes expanded by A are non-decreasing. This means that when A selects a node $n$ for expansion, it has already found the optimal path to $n$, and it will never need to be re-opened.

Combining Admissible Heuristics

In some problems, we might devise several different admissible heuristics. Consider two admissible heuristics, $h_1(n)$ and $h_2(n)$. We can combine them to create a new, potentially better heuristic.

Let $h(n) = \max(h_1(n), h_2(n))$.

This new heuristic $h(n)$ is also admissible. Since both $h_1(n) \le h^$(n)h1​(n)≤h∗(n) and $h_2(n) \le h^$(n), their maximum must also be less than or equal to $h^$(n)h∗(n). Furthermore, this composite heuristic is more informed (or dominates) the individual ones, as its value is greater than or equal to both $h_1(n)$ and $h_2(n)$. A more informed heuristic allows A to prune the search space more effectively, leading to faster performance.

Conversely, a sum of two admissible heuristics, $h_1(n) + h_2(n)$, is generally not admissible, as the sum can easily overestimate the true cost $h^*(n)$.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="An A search algorithm uses a heuristic $h(n)$ that is admissible but not consistent. What is the primary consequence of the lack of consistency?" options=["The algorithm is no longer guaranteed to find an optimal solution.","The algorithm may re-expand nodes that have already been visited.","The algorithm will behave identically to a Greedy Best-First search.","The algorithm will fail to terminate if the state space contains cycles."] answer="The algorithm may re-expand nodes that have already been visited." hint="Consistency ensures that once a node is expanded, the optimal path to it has been found. What happens if this guarantee is removed?" solution="Consistency guarantees that the $f$-values of expanded nodes are non-decreasing. If a heuristic is admissible but not consistent, the $f$-values may not be monotonic. This can lead to a situation where A finds a path to a node $n$, expands it, and later discovers a cheaper path to $n$. If this happens, $n$ may need to be added back to the frontier and expanded again to propagate the new, lower cost to its successors. Admissibility alone is sufficient to guarantee optimality, but consistency provides greater efficiency by preventing re-expansion of nodes."
:::

:::question type="NAT" question="In an A search, a node $N$ is reachable from the start node $S$ via two paths. Path 1: $S \rightarrow A \rightarrow N$ with total cost $g_1(N)=12$. Path 2: $S \rightarrow B \rightarrow N$ with total cost $g_2(N)=10$. The heuristic value is $h(N)=5$. When node $N$ is first placed on the frontier via Path 1, what is its initial $f$-value?" answer="17" hint="The $f$-value is calculated using the $g$-value of the path through which the node was discovered." solution="The A evaluation function is $f(n) = g(n) + h(n)$. When node $N$ is first discovered via the path $S \rightarrow A \rightarrow N$, its path cost is given as $g_1(N)=12$. The heuristic value is $h(N)=5$.

Step 1: Apply the A* evaluation formula.

Step 2: Substitute the given values.

Step 3: Calculate the result.

Result: The initial $f$-value for node $N$ is 17. (Later, if the path via $B$ is discovered, its entry in the frontier would be updated to $f(N) = 10 + 5 = 15$).
"
:::

:::question type="MSQ" question="Let $h_1(n)$ and $h_2(n)$ be two different admissible heuristics for a search problem. Which of the following heuristics are also guaranteed to be admissible?" options=["$h_3(n) = \frac{h_1(n) + h_2(n)}{2}$","$h_4(n) = \min(h_1(n), h_2(n))$","$h_5(n) = h_1(n) \times h_2(n)$","$h_6(n) = 2 \times h_1(n)$"] answer="A,B" hint="An admissible heuristic must never overestimate the true cost $h^$(n)h∗(n). Check if each combination can exceed $h^$(n)." solution="Let $h^$(n)h∗(n) be the true optimal cost from node $n$ to the goal. Since $h_1$ and $h_2$ are admissible, we know $0 \le h_1(n) \le h^$(n) and $0 \le h_2(n) \le h^*(n)$.

• A: $h_3(n) = \frac{h_1(n) + h_2(n)}{2}$: We have

Therefore, This heuristic is admissible.

• B: $h_4(n) = \min(h_1(n), h_2(n))$: Since $h_1(n) \le h^$(n)h1​(n)≤h∗(n) and $h_2(n) \le h^$(n), the minimum of the two must also be less than or equal to $h^*(n)$. This heuristic is admissible.

• C: $h_5(n) = h_1(n) \times h_2(n)$: This is not generally admissible. For example, if $h^$(n)=5h∗(n)=5, we could have $h_1(n)=4$ and $h_2(n)=3$. Then $h_1(n) \times h_2(n) = 12$, which is greater than $h^$(n)=5. This overestimates the cost.

• D: $h_6(n) = 2 \times h_1(n)$: This is not generally admissible. If $h^$(n)=5h∗(n)=5 and $h_1(n)=4$, then $2 \times h_1(n) = 8$, which is greater than $h^$(n)=5. This overestimates the cost.

Thus, only options A and B are guaranteed to be admissible." :::

:::question type="MCQ" question="Consider the state graph below, with start node S and goal node G. Heuristic values are shown next to each node. Which path will Greedy Best-First Search explore to reach G?"







Sh=12
Ah=5
Bh=10
Ch=6
Gh=0
1
10
20
1
1

options=["S → A → C → G","S → B → G","S → A → G (path does not exist)","S → B → C → G (path does not exist)"] answer="S → A → C → G" hint="Greedy Best-First search only considers the heuristic value $h(n)$ and ignores path costs." solution="Greedy Best-First Search expands the node with the lowest $h(n)$ value.

Start at $S$. Successors are $A$ ($h=5$) and $B$ ($h=10$).

Expand $A$ because $h(A) < h(B)$.

From $A$, the only successor is $C$ ($h=6$). The frontier contains {$C$, $B$}.

Expand $C$ because $h(C) < h(B)$. (Note: even though path cost to $C$ is huge, Greedy search ignores it).

From $C$, the successor is $G$ ($h=0$).

Expand $G$. The path found is $S \rightarrow A \rightarrow C \rightarrow G$. The total cost is $1+20+1=22$. The algorithm does not realize the path $S \rightarrow B \rightarrow G$ has a cost of only $10+1=11$ because it was greedily attracted to node $A$."

:::

---

Summary

---

What's Next?

---

---

Part 3: Adversarial Search

Introduction

In the domain of artificial intelligence, many problems can be modeled as a search through a state space for a solution. However, a special class of problems involves multiple agents with conflicting goals, a scenario most commonly observed in games like chess, checkers, or Go. This is the realm of adversarial search, where the actions of one agent are designed to counteract the objectives of another. The challenge lies not merely in finding a path to a goal state, but in formulating a strategy or policy that selects the optimal move, assuming the opponent will also play optimally.

We will explore the foundational algorithm for decision-making in such environments: the Minimax algorithm. This provides a formal method for determining the best move by recursively exploring the game tree. Subsequently, we will turn our attention to a crucial optimization, Alpha-Beta Pruning, which significantly reduces the search space by eliminating branches that cannot possibly influence the final outcome. A thorough understanding of these techniques is essential for solving problems involving strategic decision-making under competitive conditions, a recurring theme in the GATE examination.

---

Key Concepts

1. The Minimax Algorithm

The Minimax algorithm is a decision-making algorithm used in two-player, zero-sum games. It operates by exploring the entire game tree down to its terminal nodes (leaves), which represent the end of the game. A utility function is applied to these terminal nodes to assign a numerical score representing the outcome from MAX's perspective (e.g., +1 for a win, -1 for a loss, 0 for a draw). These values are then propagated back up the tree to determine the optimal move from the current state.

The core principle is that the MAX player will always choose a move that leads to a state with the maximum possible score, while the MIN player will always choose a move that leads to a state with the minimum possible score.

Let us consider a node $n$ in the game tree. The minimax value of this node, denoted $V(n)$, is computed as follows:

• If $n$ is a terminal node, $V(n)$ is the utility of that state.
• If $n$ is a MAX player's turn,

• If $n$ is a MIN player's turn,

The algorithm performs a complete depth-first exploration of the game tree.

MAX
MIN
MAX
Terminal

A
3

B
3

C
2

D
3

E
5

F
2

G
9

3

12

8

5

2

4

6

9

Worked Example:

Problem: Determine the optimal move for the MAX player at the root node A using the Minimax algorithm for the tree shown above.

Solution:

Step 1: Compute values for the lowest level of MAX nodes (D, E, F, G).

For node D, its children have utilities 3 and 12. Since D is a MAX node:

For node E, its children have utilities 8 and 5. Since E is a MAX node:

For node F, its children have utilities 2 and 4. Since F is a MAX node:

For node G, its children have utilities 6 and 9. Since G is a MAX node:

Step 2: Compute values for the MIN nodes (B, C) using the values from their children (D, E, F, G).

For node B, its children are D and E. Since B is a MIN node:

For node C, its children are F and G. Since C is a MIN node:

Step 3: Compute the value for the root MAX node (A) using the values from its children (B, C).

For node A, its children are B and C. Since A is a MAX node:

Step 4: Determine the optimal move.

The value of the root node A is 8. This value comes from child B. Therefore, the optimal move for MAX at the root is to move to state B.

Answer: The minimax value of the root is 8.

---

2. Alpha-Beta Pruning

The primary drawback of the Minimax algorithm is its time complexity. For a game tree with a branching factor of $b$ and a maximum depth of $d$, the complexity is $O(b^d)$. This is computationally infeasible for all but the simplest games. Alpha-Beta pruning is an optimization technique that reduces the number of nodes evaluated by the Minimax algorithm without affecting the final decision.

The algorithm maintains two values, alpha ($\alpha$) and beta ($\beta$), which represent the lower and upper bounds on the possible minimax value.

These values are passed down the tree during the search. A MAX node can update $\alpha$, and a MIN node can update $\beta$.

Explanation of Pruning:

• Pruning at a MIN node: If a MIN node's current value (which can only decrease) becomes less than or equal to $\alpha$, the MAX player (higher up the tree) who set that $\alpha$ value will never choose this path. MAX already has a choice that guarantees a score of at least $\alpha$, so there is no need to explore this branch further, as MIN will ensure a score no better than the current one.


• Pruning at a MAX node: If a MAX node's current value (which can only increase) becomes greater than or equal to $\beta$, the MIN player (higher up the tree) who set that $\beta$ value will never allow play to reach this node. MIN already has a choice that guarantees a score of at most $\beta$.

Worked Example:

Problem: Apply Alpha-Beta pruning to the game tree below. The search proceeds from left to right. Identify which nodes are pruned.

MAX
MIN
MAX

A
α=3, β=∞

B
α=-∞, β=3

C
α=3, β=∞

D
α=-∞, β=∞

E
α=-∞, β=3

F
α=3, β=∞

G
α=3, β=∞

3
5
6
9
1
2
0
1

Solution:

We trace the execution, keeping track of $\alpha$ and $\beta$ at each node.

Step 1: Start at root A (MAX).

• Initialize $V_A = -\infty$, $\alpha = -\infty$, $\beta = +\infty$.


• Descend to child B (MIN). Pass down $\alpha, \beta$.

Step 2: At node B (MIN).

• Initialize $V_B = +\infty$. Receives $\alpha = -\infty, \beta = +\infty$.


• Descend to child D (MAX). Pass down $\alpha, \beta$.

Step 3: At node D (MAX).

• Initialize $V_D = -\infty$. Receives $\alpha = -\infty, \beta = +\infty$.


• Evaluate first child (utility 3). $V_D$ becomes 3. MAX node updates its own $\alpha$. Local $\alpha$ becomes 3.


• Evaluate second child (utility 5). $V_D$ becomes $\max(3, 5) = 5$.


• D returns value 5 to B.

Step 4: Back at node B (MIN).

• Receives 5 from D. $V_B$ becomes $\min(+\infty, 5) = 5$. MIN node updates its own $\beta$. Local $\beta$ becomes 5.


• Descend to child E (MAX). Pass down B's current range: $\alpha = -\infty, \beta = 5$.

Step 5: At node E (MAX).

• Initialize $V_E = -\infty$. Receives $\alpha = -\infty, \beta = 5$.


• Evaluate first child (utility 6). $V_E$ becomes 6. Local $\alpha$ becomes 6.


• Check pruning condition: Is local $\alpha \ge \beta$? Is $6 \ge 5$? Yes.


• Pruning occurs. The remaining children of E (the node with value 9) are not evaluated. E can return immediately. The value it returns is 6, although this value is not used by B.


• B received 5 from D, and now sees that path E will result in a value of at least 6. Since B is a MIN node, it will prefer the path through D with value 5. So B's final value is 5.

Step 6: Back at node A (MAX).

• Receives 5 from B. $V_A$ becomes $\max(-\infty, 5) = 5$. MAX node updates its $\alpha$. A's $\alpha$ is now 5.


• Descend to child C (MIN). Pass down A's current range: $\alpha = 5, \beta = +\infty$.

Step 7: At node C (MIN).

• Initialize $V_C = +\infty$. Receives $\alpha = 5, \beta = +\infty$.


• Descend to child F (MAX). Pass down $\alpha = 5, \beta = +\infty$.

Step 8: At node F (MAX).

• Initialize $V_F = -\infty$. Receives $\alpha = 5, \beta = +\infty$.


• Evaluate first child (utility 1). $V_F$ becomes 1.


• Evaluate second child (utility 2). $V_F$ becomes $\max(1, 2) = 2$.


• F returns value 2 to C.

Step 9: Back at node C (MIN).

• Receives 2 from F. $V_C$ becomes $\min(+\infty, 2) = 2$. C updates its local $\beta$ to 2.


• Check pruning condition: Is parent's $\alpha \ge$ my $\beta$? Is $5 \ge 2$? Yes.


• Pruning occurs. The MIN player at C knows it can achieve a score of 2 (or less). The MAX player at A already has a move that guarantees a score of 5. MAX will never choose the move to C. Therefore, the rest of C's children (node G and its subtree) are pruned.


• C can return its current value of 2.

Step 10: Back at node A (MAX).

• Receives 2 from C. $V_A$ becomes $\max(5, 2) = 5$.


• All children of A have been explored. The final value is 5.

Answer: The nodes pruned are the terminal node with value 9 (child of E) and the entire subtree under node G. The final minimax value is 5.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="In the Alpha-Beta pruning algorithm, $\alpha$ represents the minimum score that the maximizing player is assured of, and $\beta$ represents the maximum score that the minimizing player is assured of. Pruning occurs when a condition between $\alpha$ and $\beta$ is met. Which of the following statements is correct?" options=["A MAX node updates $\alpha$ and pruning occurs if $\alpha \le \beta$","A MIN node updates $\alpha$ and pruning occurs if $\alpha \ge \beta$","A MAX node updates $\alpha$ and pruning occurs if $\alpha \ge \beta$","A MIN node updates $\beta$ and pruning occurs if $\beta \ge \alpha$"] answer="A MAX node updates $\alpha$ and pruning occurs if $\alpha \ge \beta$" hint="Recall which player is associated with which bound and what the pruning condition signifies." solution="The value $\alpha$ is the best score (highest) guaranteed for the MAX player, so MAX nodes update it. The value $\beta$ is the best score (lowest) guaranteed for the MIN player, so MIN nodes update it. The fundamental condition for pruning is when the lower bound for MAX ($\alpha$) is greater than or equal to the upper bound for MIN ($\beta$), i.e., $\alpha \ge \beta$. Therefore, the correct statement is that a MAX node updates $\alpha$ and pruning occurs if $\alpha \ge \beta$.
Answer: $\boxed{\text{A MAX node updates } \alpha \text{ and pruning occurs if } \alpha \ge \beta}$"
:::

:::question type="NAT" question="Consider the given game tree where the first level is a MAX node. The terminal nodes have utility values. Using the Alpha-Beta pruning algorithm and exploring children from left to right, what is the final value computed for the root node?"


MAX
MIN
A
B
C


7
8
5
6
4
9







answer="5" hint="Trace the algorithm step-by-step, passing alpha and beta values down the tree and checking for pruning at each step." solution="
Step 1: Root A (MAX) starts with $\alpha=-\infty, \beta=+\infty$. It explores child B (MIN).
Step 2: Node B (MIN) receives $\alpha=-\infty, \beta=+\infty$. It explores its children.
Step 3: B evaluates its first child (7). B is a MIN node, so its value is at most 7. It sets its local $\beta=7$.
Step 4: B evaluates its second child (8). Its value is $\min(7, 8) = 7$. No change to $\beta$.
Step 5: B evaluates its third child (5). Its value is $\min(7, 5) = 5$. B updates its local $\beta=5$.
Step 6: B has explored all children and returns its final value, 5, to A.
Step 7: Root A (MAX) receives 5. Its value is at least 5. It updates its $\alpha=5$.
Step 8: A explores its second child C (MIN), passing down $\alpha=5, \beta=+\infty$.
Step 9: Node C (MIN) receives $\alpha=5, \beta=+\infty$. It explores its first child (6).
Step 10: C's value is at most 6. It updates its local $\beta=6$.
Step 11: C evaluates its second child (4). Its value is $\min(6, 4) = 4$. It updates its local $\beta=4$.
Step 12: C now checks for pruning. The condition is $\alpha \ge \beta$. Here, $5 \ge 4$. The condition is met.
Step 13: The rest of C's children (the node with value 9) are pruned. C returns its current value, 4.
Step 14: A receives 4 from C. A's value is $\max(5, 4) = 5$.
Answer: $\boxed{5}$
"
:::

:::question type="MSQ" question="Which of the following statements about the Alpha-Beta pruning algorithm are correct?" options=["The algorithm may not find the optimal minimax value if the tree is not searched in an optimal order.","The number of nodes explored depends on the order in which children are evaluated.","Alpha-Beta pruning can be applied to game trees of any depth.","The value of $\alpha$ at any MAX node can never decrease."] answer="B,C,D" hint="Consider the core properties of the algorithm: its correctness, its dependency on ordering, its applicability, and the monotonic nature of its bounds." solution="

• Option A is incorrect. Alpha-Beta pruning is a correct optimization of Minimax. It is guaranteed to return the exact same minimax value as the full Minimax algorithm, regardless of the move ordering. The ordering only affects the efficiency (how many nodes are pruned), not the correctness of the result.


• Option B is correct. The efficiency of Alpha-Beta pruning is highly dependent on move ordering. An optimal ordering (best moves first) prunes a maximal number of nodes, while a pessimal ordering (worst moves first) may result in no pruning at all.


• Option C is correct. The algorithm is recursive and works on the principle of bounds. It can be applied to a game tree of any finite depth. For very deep trees, it is often combined with a cutoff depth and an evaluation function.


• Option D is correct. The value of $\alpha$ represents the best score (maximum) found so far for the MAX player. As the search progresses, MAX will only update $\alpha$ if it finds a path leading to an even better (higher) score. Therefore, $\alpha$ is non-decreasing. Similarly, $\beta$ is non-increasing.

Answer: $\boxed{\text{B,C,D}}$
"
:::

:::question type="MCQ" question="In a game tree, a MIN node $M$ has an $(\alpha, \beta)$ window of $(5, 12)$ passed to it from its parent MAX node. Node $M$ evaluates its first child, which returns a value of 4. What is the immediate consequence?" options=["The $(\alpha, \beta)$ window for $M$'s subsequent children becomes $(5, 4)$.","Node $M$ immediately returns the value 4 and its other children are pruned.","Node $M$ updates its local $\beta$ to 4 and continues evaluating its other children.","Node $M$ updates its local $\alpha$ to 5 and its local $\beta$ to 4."] answer="Node $M$ immediately returns the value 4 and its other children are pruned." hint="After evaluating a child, a node updates its bounds and checks the pruning condition." solution="
Step 1: The MIN node $M$ receives the window $\alpha=5, \beta=12$.
Step 2: It evaluates its first child and gets a value of 4.
Step 3: As a MIN node, its objective is to find the minimum value. Its current best value is 4. It updates its local $\beta$ value to 4.
Step 4: It checks the pruning condition: Is $\alpha \ge \beta$? Here, we check if $5 \ge 4$.
Step 5: The condition is true. This means that the MIN node $M$ has found a move that leads to a score of 4. However, its parent MAX node already has an option that guarantees a score of at least 5 (the value of $\alpha$). The MAX player will never choose the path through $M$.
Step 6: Therefore, there is no need to explore the remaining children of $M$. The subtree is pruned, and $M$ can immediately return its current value of 4.
Answer: $\boxed{\text{Node } M \text{ immediately returns the value 4 and its other children are pruned.}}$
"
:::

---

Summary

---

What's Next?

---

Chapter Summary

In this chapter, we have undertaken a comprehensive exploration of the fundamental algorithms that underpin problem-solving in Artificial Intelligence. We began by classifying search strategies into two primary categories: uninformed and informed search. Our discussion of uninformed search covered foundational algorithms such as Breadth-First Search (BFS) and Depth-First Search (DFS), for which we analyzed the critical properties of completeness, optimality, and time/space complexity. We then advanced to informed, or heuristic, search strategies. The cornerstone of this section was the A algorithm, where we rigorously examined the roles of the cost function $g(n)$ and the heuristic function $h(n)$. The concepts of admissibility and consistency were established as the necessary conditions for guaranteeing the optimality of A. Finally, we shifted our focus to multi-agent environments with an introduction to adversarial search. We detailed the Minimax algorithm as the theoretical basis for decision-making in two-player, zero-sum games and introduced Alpha-Beta pruning as a powerful optimization that significantly reduces the search space without affecting the final outcome. It is clear from our discussion that the choice of a search algorithm is a critical design decision, involving a trade-off between computational resources and the quality of the solution required.

---

Chapter Review Questions

:::question type="MCQ" question="Consider the game tree below, where the root is a MAX node. The values at the leaf nodes represent the utility for the MAX player. Which of the following nodes will be pruned if Alpha-Beta pruning is applied? Assume children are visited from left to right." options=["D", "J", "F", "L"] answer="J" hint="Trace the Minimax algorithm while keeping track of the alpha (for MAX) and beta (for MIN) values. A prune occurs when alpha becomes greater than or equal to beta." solution="
Let's trace the Alpha-Beta pruning algorithm, assuming children are visited from left to right.
We maintain $\alpha$ (best value for MAX found so far on the path to the root) and $\beta$ (best value for MIN found so far on the path to the root).

Root A (MAX node): Initialize $\alpha = -\infty$, $\beta = +\infty$.

Explore Branch B (MIN node): A passes $(\alpha=-\infty, \beta=+\infty)$ to B.

- B explores E: E returns 3. B's current value is $\le 3$. Update B's $\beta = 3$.
- B explores F: F returns 5. B's current value is $\min(3, 5) = 3$.
- B explores G: G returns 2. B's current value is $\min(3, 2) = 2$.
- B returns 2 to A.
- At A, update $\alpha = \max(-\infty, 2) = 2$.

Explore Branch C (MIN node): A passes $(\alpha=2, \beta=+\infty)$ to C.

- C explores H: H returns 9. C's current value is $\le 9$. Update C's $\beta = 9$.
- C explores I: I returns 1. C's current value is $\min(9, 1) = 1$. Update C's $\beta = 1$.
- Pruning Check at C: At this point, for node C, we have $\beta=1$. The $\alpha$ value inherited from A is $\alpha=2$. Since $\alpha \ge \beta$ ($2 \ge 1$), MAX (at A) already has a guaranteed score of 2 from branch B. MIN (at C) has found a move (to I) that yields a score of 1. Since MAX will never choose a branch that yields 1 when it can get 2, the rest of C's children can be pruned.
- Therefore, Node J is pruned.
- C returns 1 to A.
- At A, update $\alpha = \max(2, 1) = 2$.

Explore Branch D (MIN node): A passes $(\alpha=2, \beta=+\infty)$ to D.

- D explores L: L returns 8. D's current value is $\le 8$. Update D's $\beta = 8$.
- D explores M: M returns 4. D's current value is $\min(8, 4) = 4$. Update D's $\beta = 4$.
- D explores N: N returns 2. D's current value is $\min(4, 2) = 2$. Update D's $\beta = 2$.
- Pruning Check at D: At this point, for node D, we have $\beta=2$. The $\alpha$ value inherited from A is $\alpha=2$. Since $\alpha \ge \beta$ ($2 \ge 2$), any subsequent children of D would be pruned. However, N is the last child of D, so no further pruning occurs within this branch.
- D returns 2 to A.
- At A, update $\alpha = \max(2, 2) = 2$.

The final value for MAX is 2. The only node among the options that was pruned is J.

Answer: \boxed{J}
"
:::

:::question type="NAT" question="A state space is represented as a tree where every internal node has a branching factor of 4. If the shallowest goal node is at depth 3 (with the root at depth 0), what is the maximum number of nodes that must be generated by a Breadth-First Search (BFS) before it finds the solution? Assume the goal is the last node to be explored at its depth level." answer="85" hint="BFS explores the tree level by level. Calculate the total number of nodes at depths 0, 1, 2, and 3." solution="
Breadth-First Search (BFS) performs a complete level-by-level exploration of the search tree. The number of nodes at any given depth $k$ in a tree with a uniform branching factor $b$ is $b^k$.

The total number of nodes generated by BFS to find a goal at depth $d$ (assuming it's the last node at that level) is the sum of all nodes from the root (depth 0) up to and including depth $d$.

The formula for the total nodes generated is:

Given parameters:

• Branching factor, $b = 4$


• Depth of the goal node, $d = 3$

We calculate the number of nodes at each level:

• Depth 0 (root): $4^0 = 1$ node


• Depth 1: $4^1 = 4$ nodes


• Depth 2: $4^2 = 16$ nodes


• Depth 3: $4^3 = 64$ nodes

The maximum number of nodes generated is the sum of nodes at all these levels:

Alternatively, we can use the formula for the sum of a geometric series:

Thus, a maximum of 85 nodes will be generated.
Answer: \boxed{85}
"
:::

:::question type="MCQ" question="Which of the following statements about search algorithm properties is FALSE?" options=["An A search with an admissible but inconsistent heuristic is guaranteed to find an optimal solution, but may re-open nodes on the closed list.", "Depth-First Search is not complete in state spaces with infinite paths or cycles.", "Greedy Best-First Search is an optimal algorithm because it always expands the node that is heuristically closest to the goal.", "Uniform Cost Search is a special case of A search where the heuristic function $h(n)$ is always zero."] answer="C" hint="Consider whether minimizing the heuristic value at each step guarantees minimizing the total path cost." solution="
Let us analyze each statement to determine its validity.

• (A) An A search with an admissible but inconsistent heuristic is guaranteed to find an optimal solution, but may re-open nodes on the closed list. This statement is TRUE. Admissibility ($h(n) \le h^$(n)) is the sole condition required to guarantee the optimality of A*. Consistency (a stronger condition) guarantees that once a node is expanded, a better path to it will not be found later, thus avoiding the need to re-open closed nodes. If a heuristic is admissible but not consistent, optimality is maintained, but efficiency may decrease due to re-opening nodes.

• (B) Depth-First Search is not complete in state spaces with infinite paths or cycles. This statement is TRUE. DFS explores a single path as deeply as possible before backtracking. If it goes down an infinite path, it will never backtrack to explore other paths, and thus will never find a solution that may exist on a different branch.

• (C) Greedy Best-First Search is an optimal algorithm because it always expands the node that is heuristically closest to the goal. This statement is FALSE. Greedy Best-First Search uses the evaluation function $f(n) = h(n)$. It expands the node that appears to be closest to the goal. However, this approach can lead it down a path that seems promising initially but turns out to be a long and costly dead end. It does not account for the cost already incurred ($g(n)$), and is therefore both incomplete (can get stuck in loops) and not optimal.

• (D) Uniform Cost Search is a special case of A search where the heuristic function $h(n)$ is always zero. This statement is TRUE. The evaluation function for A is $f(n) = g(n) + h(n)$. If we set $h(n) = 0$ for all nodes $n$, the function becomes $f(n) = g(n)$. This is precisely the evaluation function for Uniform Cost Search, which always expands the node with the lowest path cost from the start.

Therefore, the false statement is (C). Answer: \boxed{C} " :::

:::question type="NAT" question="In a grid-based pathfinding problem, an agent can move one step at a time to any of its 8 adjacent cells (including diagonals). The cost of a horizontal or vertical move is 1, and the cost of a diagonal move is $\sqrt{2}$. The goal is at coordinates (15, 20). What is the Chebyshev distance heuristic value for a node located at coordinates (8, 12)?" answer="8" hint="The Chebyshev distance (or $L_\infty$ distance) between two points $(x_1, y_1)$ and $(x_2, y_2)$ is defined as $\max(|x_1 - x_2|, |y_1 - y_2|)$. This heuristic is admissible for a grid where diagonal movement is allowed." solution="
The Chebyshev distance is an admissible heuristic for grids where 8-directional movement is permitted. It calculates the minimum number of moves required to reach the goal if movement is unrestricted, which corresponds to the maximum difference in either the x or y coordinates.

The formula for the Chebyshev distance $D_\infty$ between a node $n$ at $(x_n, y_n)$ and the goal $g$ at $(x_g, y_g)$ is:

Given:

• Node coordinates: $(x_n, y_n) = (8, 12)$


• Goal coordinates: $(x_g, y_g) = (15, 20)$

First, we calculate the absolute differences in the coordinates:

• Difference in x-coordinates: $|8 - 15| = |-7| = 7$


• Difference in y-coordinates: $|12 - 20| = |-8| = 8$

Next, we take the maximum of these two values:

The Chebyshev distance heuristic value is 8. This represents the fact that at least 8 moves are required to cover the distance of 8 units in the y-direction, during which the distance of 7 units in the x-direction can also be covered simultaneously via diagonal moves.
Answer: \boxed{8}
"
:::

---

What's Next?