By Piyush Wairale · GATE DA Educator & Course Instructor, IIT Madras BS Programme · Updated August 2026

From Uninformed to Informed Search

BFS and DFS explore blindly — they know the graph but nothing about where the goal is. Informed search adds a heuristic h(n): an estimate of the cheapest cost from n to the goal. Spend that information well and you expand dramatically fewer nodes; spend it badly (an overestimating h) and you can lose optimality. The AI section of the official GATE DA syllabus names informed search and adversarial search explicitly, and the AI search pillar maps the whole family — this post works the two members GATE actually makes you trace.

Admissible and Consistent Heuristics

Admissible: h(n) ≤ h*(n) for every n — the heuristic never overestimates the true remaining cost (straight-line distance for road maps is the canonical example). Consistent (monotone): h(n) ≤ c(n, n′) + h(n′) for every edge — a triangle inequality. Two exam facts: consistency implies admissibility (not the converse), and with a consistent h, f never decreases along a path, so A* can finalise a node the first time it expands it. h(goal) must be 0 in both cases.

A*, Traced Completely

Edges: S–A = 1, S–B = 4, A–B = 2, A–C = 5, B–C = 2, C–G = 3. Expand the lowest-f node each step:

Expansion order: S, A, B, C, G. Optimal path S → A → B → C → G, cost 1+2+2+3 = 8. Two trace details worth marks: B was first generated via S with f = 8, then improved to f = 7 when a cheaper path through A appeared; and the direct S–B and A–C edges are never used in the final path even though they were explored.

Why Admissibility Guarantees Optimality

Suppose A* expands a goal reached by a suboptimal path (cost C > C*). Some node n on the optimal path is still open, and its f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C* < C = f(goal) — so n would have been expanded first. Contradiction: the first goal expanded is optimal. Check the trace above: h is admissible everywhere (e.g. h(S) = 7 ≤ 8 true cost), and A* duly returned cost 8.

Counterexample with an inflated h: set h(B) = 10 (true remaining cost is 5 — overestimate). Now B’s f = 3 + 10 = 13, so A* expands C via A (f = 8) and reaches G with cost 6 + 3 = 9 before ever touching B — returning the suboptimal S–A–C–G. One bad heuristic value, optimality gone. That is the entire content of “why must h be admissible?” MCQs.

Greedy Best-First vs UCS vs A*

Special cases GATE tests: h ≡ 0 turns A* into UCS; and UCS on unit-cost graphs behaves like BFS. Uncertainty-flavoured AI questions continue in the reasoning under uncertainty deep dive.

Minimax on a Game Tree, Worked

Adversarial search: MAX picks the move leading to the highest value assuming MIN replies optimally. Tree: MAX root with three MIN children B, C, D whose leaves are [3, 12, 8], [2, 4, 6], [14, 5, 2].

Back up the values: B = min(3, 12, 8) = 3; C = min(2, 4, 6) = 2; D = min(14, 5, 2) = 2. Root = max(3, 2, 2) = 3 — MAX plays toward B. Plain minimax evaluated all 9 leaves.

Alpha-Beta Pruning: the Same Answer, Fewer Leaves

α = best guarantee for MAX so far; β = best for MIN. Prune when β ≤ α. Left-to-right on the same tree:

Subtree B: no bounds yet — evaluate 3, 12, 8 fully → B = 3. Root now has α = 3.

Subtree C: first leaf 2 → C’s β = 2. Test: β = 2 ≤ α = 3 → cutoff — leaves 4 and 6 are never evaluated. MIN can already hold MAX to 2 here, and MAX already has 3 elsewhere; nothing below can change the root.

Subtree D: leaf 14 → β = 14 > α, continue; leaf 5 → β = 5 > α, continue; leaf 2 → β = 2, subtree exhausted → D = 2. No cutoff fires — the low leaf arrived last.

Total: 7 of 9 leaves evaluated, 2 pruned, root value still 3 — alpha-beta never changes the minimax answer, only the work.

Move Ordering: Why Pruning Power Varies

Pruning depends on encountering good moves early. Had subtree D been searched before B (its value 2 found first), less would prune; had each MIN node’s smallest leaf come first and the best MAX subtree been searched first, cutoffs fire maximally. With perfect ordering, alpha-beta examines about O(b^d/2) nodes instead of O(b^d) — effectively doubling the searchable depth. That asymptotic pair is a memorise-it fact for MCQs.

Three GATE-Style Problems, Solved

Problem 1 (MCQ/NAT). In the graph traced above, which node does A* expand third, and what is the final path cost?

Solution. Expansion order S, A, B, C, G — third is B (after its path improved through A to f = 7). Path cost = 8. Distractor options use the never-updated f = 8 for B — precisely the update step careless traces skip.

Problem 2 (MCQ). True remaining costs are h*(S) = 8, h*(A) = 7, h*(B) = 5, h*(C) = 3. Which heuristic table is admissible? (a) h = (7, 6, 4, 2) (b) h = (8, 7, 5, 3) (c) h = (9, 6, 4, 2) (d) h = (7, 8, 4, 2)

Solution. Admissible needs h ≤ h* at every node. (a): 7≤8, 6≤7, 4≤5, 2≤3 → admissible (our trace’s h). (b) equals h* — also admissible, the “perfect heuristic”. (c) fails at S (9 > 8); (d) fails at A (8 > 7). Answer: (a) and (b) — and expect exactly this multiple-select format.

Problem 3 (NAT). A MAX-root tree has three MIN children with leaves [5, 8, 6], [3, 9, 7], [1, 4, 2], searched left to right. How many leaves does alpha-beta skip?

Solution. Subtree 1: full evaluation → value 5, α = 5. Subtree 2: first leaf 3 → β = 3 ≤ 5 → prune 9, 7 (2 skipped). Subtree 3: first leaf 1 → β = 1 ≤ 5 → prune 4, 2 (2 skipped). Total skipped = 4, evaluated 5 of 9, root = 5.

Common Mistakes to Avoid

Confusing g and h. g is exact cost from the start; h estimates cost to the goal. Greedy uses only h, UCS only g, A* both.

Stopping when the goal is generated. A* is optimal only if you stop when the goal is expanded (popped with lowest f). Our trace generates G at step 4 but stops at step 5.

Forgetting to update a node’s g when a cheaper path appears. B’s improvement from f = 8 to f = 7 changed the expansion order.

Pruning with the wrong test. The cutoff condition is β ≤ α. Applying strict < delays cutoffs by one leaf, changing every count.

Assuming alpha-beta changes the result. It never does — identical root value and move, only fewer evaluations. “Same answer, less work” is a guaranteed true statement.

How GATE DA Asks A* and Alpha-Beta

Recurring shapes: (1) NAT/MCQ — A* expansion order or final path cost on a 5–6 node graph with printed h; (2) MCQ — admissibility/consistency checks of a heuristic table; (3) NAT — leaves evaluated or pruned by alpha-beta on a 2-ply tree (state the search order in your trace!); (4) MCQ — properties: UCS = A* with h = 0, pruning never changes the value, O(b^d/2) best case. Keep the two bookkeeping tables from this post and each is a 3-minute question. The AI search pillar covers the surrounding family; reasoning under uncertainty completes the AI section.

FAQs: A* & Alpha-Beta for GATE DA

This completes the GATE DA deep-dive series: revisit the AI search pillar, the BFS & DFS traversals these algorithms build on, and the reasoning under uncertainty guide, and track your full preparation against the GATE DA 2027 syllabus. New AI problem-solving sessions drop regularly on my YouTube channel — subscribe so you don’t miss them.