PART 5 • INTELLIGENT SYSTEMS & CAREER • LEVEL 23
Classical AI, Search & Reasoning
Turn goals into state spaces, choose search strategies deliberately, reason through adversarial games and constraints, and represent knowledge that an intelligent system can query and explain.
SEARCH CONTRACTstate • action • cost • heuristic • goal test
f(n) = g(n) + h(n)LEARNING OUTCOMES
By the End of This Level, You Can
QUICK REVISION
Six Building Blocks of Classical AI
Classical AI makes the decision process explicit: what the system knows, what it may do and why one choice is preferred.
Contains the information required to choose a valid next action.
Transforms one state into a successor according to the model.
Adds distance, time, risk or another measurable objective.
Guides informed search without replacing the true accumulated cost.
Prunes assignments that cannot belong to a complete solution.
Derives consequences from facts, rules or probabilistic dependencies.
CONCEPT 01
A Search Problem Begins with a Precise Model
Before selecting an algorithm, define what a state means, which actions are legal and what counts as success.
The current board, city, machine configuration or partial assignment.
Each action has a precondition and a deterministic or stochastic result.
A predicate checks whether the current state satisfies the task.
The sum of edge costs may represent distance, latency, money or danger.
A state must contain enough information to predict valid successors, but no irrelevant history. The state space is the directed graph induced by the transition model; a search tree is the algorithm’s evolving view of that graph. Repeated-state detection matters because different action sequences can reach the same state. The solution is not merely a goal state: it is a sequence of actions whose total cost can be evaluated. A weak formulation creates an enormous graph or accepts invalid plans, so formulation quality often matters more than a clever implementation.
In route planning, a state can be the current city, an action is a road, the transition reaches its destination, the goal test compares cities and edge cost is travel time.
State whether the environment is fully observable, deterministic, static, discrete and single-agent before choosing a method.
The search tree and state graph are not identical. One graph state may appear through many tree paths unless duplicates are controlled.
CONCEPT 02
Uninformed Strategies Differ in Expansion Order
BFS, DFS and uniform-cost search use no estimate of distance to the goal, yet their guarantees differ sharply.
FIFO queue. Complete with finite branching and optimal only when step costs are equal.
frontier = deque([start])Stack or recursion. Memory-efficient, but can follow an infinite or unhelpful branch.
frontier = [start]Priority queue. Complete and optimal when action costs have a positive lower bound.
priority = path_costBFS expands every node at depth d before depth d+1, so its time and space can grow as O(b^d). DFS stores roughly one path plus unexplored siblings, often O(bm), but its answer depends strongly on successor order. Uniform-cost search generalizes BFS to unequal non-negative edge costs and may revisit a state when a cheaper path is discovered. A visited set should be applied at the correct time: for optimal cost search, maintain the best known cost and ignore stale queue entries rather than permanently closing a state too early.
Use BFS for minimum moves with equal costs, UCS for minimum total cost, and DFS for bounded exploration where memory is tight and optimality is unnecessary.
Report branching factor b, shallowest solution depth d, maximum depth m and whether costs can be zero or negative.
Fewest edges is not necessarily cheapest. BFS can return an expensive two-edge route while UCS finds a cheaper three-edge route.
CONCEPT 03
Heuristics Trade Search Effort for Informed Direction
Greedy best-first uses the estimated distance alone; A* balances distance already paid with distance believed to remain.
f(n) = h(n)Often reaches a goal quickly, but can choose a cheap-looking route with a high true cost.
f(n) = g(n) + h(n)Balances accumulated evidence and a future estimate.
h(n) ≤ h*(n)Never overestimates the true optimal remaining cost.
h(n) ≤ c(n,n′)+h(n′)Satisfies a triangle inequality so f-values do not decrease along a path.
A heuristic injects domain knowledge while preserving a general search procedure. With non-negative costs and an admissible heuristic, tree-search A* is optimal; graph-search A* is simplest when the heuristic is consistent, though reopening states also supports broader cases. A zero heuristic reduces A* to UCS. A more accurate admissible heuristic usually expands fewer nodes, but computing it may be expensive. Heuristics often come from relaxed problems—for example, Manhattan distance ignores obstacles while retaining the minimum grid movement required.
If two admissible heuristics satisfy h₂(n) ≥ h₁(n) everywhere, h₂ is more informed and A* generally expands no more nodes under comparable conditions.
Explain admissibility, consistency, reopen logic and the termination condition; do not only quote f=g+h.
An admissible heuristic estimates remaining cost; it does not need to be close, and a larger arbitrary value can destroy optimality.
CONCEPT 04
A Correct A* Implementation Manages Competing Paths
The priority queue may hold multiple entries for one state, so best costs and parent pointers must be authoritative.
Store f=h(start), g=0 and no parent.
Remove the smallest priority entry.
Ignore entries whose g exceeds best_g[state].
Update a successor only when tentative g is lower.
Follow parents from goal back to start.
Priority queues commonly lack an efficient decrease-key operation, so implementations push a new entry whenever a lower cost is found. Old entries remain but become stale. The best_g map prevents them from corrupting the result. Parent pointers must change together with best_g so reconstruction follows the cheapest discovered predecessor. With a consistent heuristic, the first time the goal is popped its path is optimal. Stopping when the goal is merely generated is unsafe because another frontier node may still lead to a cheaper goal path.
best_g[s] is the lowest discovered cost to state s; every accepted relaxation strictly improves it.
Add a deterministic tie-break counter when states are not comparable or reproducible expansion order matters.
Marking a node permanently visited when first inserted can discard a later, cheaper path.
CONCEPT 05
Adversarial Search Reasons About an Opponent
Minimax selects an action whose worst rational response is as strong as possible; alpha–beta proves that some branches cannot change that choice.
Represents the decision maker whose utility is being optimized.
Represents an opponent assumed to minimize MAX’s outcome.
Travels down the current path as a lower bound.
Acts as an upper bound; prune when α ≥ β.
Terminal utilities describe outcomes from MAX’s perspective. Minimax backs leaf values upward by alternating maximum and minimum. For large games, depth-limited search applies an evaluation function at the cutoff, so better evaluation and deeper search improve decisions. Alpha–beta returns the same move as full minimax while avoiding branches already proven irrelevant. Good move ordering tightens α and β early and can approach O(b^(d/2)) effective work in ideal cases, compared with O(b^d) minimax.
If MAX already has an option worth 6 and a MIN branch reveals a child worth 4, MIN can force at most 4 there; the rest of that branch cannot attract MAX.
State whose perspective the evaluation uses, whether chance nodes exist and how the cutoff evaluator is validated.
Alpha–beta does not approximate minimax. With the same depth and evaluator, it returns the identical result using fewer evaluations.
CONCEPT 06
Constraint Satisfaction Searches Assignments, Not Paths
A CSP separates variables, domains and constraints, enabling heuristics that exploit structure before exploring every combination.
Choose the unassigned variable with the fewest legal values to fail early.
Prefer the variable constraining the largest number of unassigned neighbours.
Try the value that removes the fewest options from neighbours.
Forward checking or arc consistency removes unsupported values before recursion.
Backtracking assigns one variable at a time and reverses a choice after detecting inconsistency. MRV reduces wasted branching by exposing a likely contradiction early. Forward checking updates neighbouring domains after each assignment; AC-3 repeatedly enforces that every value has support across each binary constraint. Constraint graphs reveal independent components and tree structure that can be solved more efficiently. These techniques preserve completeness because they remove only values that cannot participate in a consistent extension.
In exam scheduling, variables are exams, domains are time slots and constraints forbid clashes for shared students or rooms.
Ask whether a global constraint such as AllDifferent is more expressive and efficient than many pairwise inequalities.
Greedily picking the first legal value is not backtracking unless the system can undo the assignment and explore alternatives.
CONCEPT 07
Knowledge Representation Makes Assumptions Queryable
Facts, predicates and rules support explainable deductions when their semantics and limits are explicit.
Useful for finite Boolean relationships and SAT-style reasoning.
Represents reusable claims such as every enrolled student has an identifier.
Repeatedly fire rules whose premises are known until no new fact appears.
Start from the desired conclusion and search for rules that could prove it.
A knowledge base entails a statement when that statement is true in every model satisfying the knowledge base. Sound inference derives only entailed conclusions; complete inference can derive every entailed conclusion in the chosen language. Horn clauses permit efficient chaining and underlie many rule systems. Real systems must also define whether an absent fact means false, unknown or inaccessible. Provenance—recording which facts and rules supported a result—turns symbolic reasoning into an inspectable decision trail.
eligible(x) ∧ registered(x) → may_interview(x). A backward query asks which premises must be proved for a particular student.
Knowledge graphs, policy engines and neuro-symbolic systems still rely on careful entity identity, relation semantics and provenance.
Failure to prove a claim does not automatically prove its negation unless the system explicitly adopts a closed-world assumption.
CONCEPT 08
Bayesian Networks Reason Under Uncertainty
A directed acyclic graph encodes conditional dependencies and factorizes a joint probability distribution.
X₁ → X₂ → X₃Edges encode direct conditional dependence assumptions, not automatically causal truth.
P(x₁,…,xₙ)=∏P(xᵢ|paᵢ)Each variable depends directly on its parents rather than the entire history.
P(H|E) ∝ P(E|H)P(H)Evidence updates belief through exact elimination or approximate sampling.
Conditional independence makes a large joint distribution compact. Variable elimination multiplies relevant factors and sums out hidden variables, but its cost depends on graph structure and elimination order. Sampling methods approximate posterior probabilities when exact inference is too expensive. Explaining-away occurs when two independent causes become dependent after observing their common effect. A Bayesian network can express observational dependence; causal interpretation needs additional assumptions about how the graph was generated and how interventions differ from observations.
If rain and a sprinkler can both cause wet grass, seeing wet grass raises belief in both. Learning that it rained can reduce the need to explain the grass using the sprinkler.
Distinguish marginal, conditional and posterior probability, then identify which variables are observed, queried and marginalized.
A directed edge is not proof of causation; observational data can support several equivalent dependency structures.
PREMIUM COMPUTATIONAL VISUALIZER
CodeBhavya • Expand, Relax, Reconstruct🧭 Graph Search & A* Laboratory
Run BFS, uniform-cost, greedy or A* on the same graph. Inspect every expansion, frontier priority, best-known cost and reconstructed path.
Changing a control rebuilds the event trace. The graph uses positive edge costs and deterministic tie-breaking.
ADVERSARIAL REASONING VISUALIZER
CodeBhavya • Evaluate, Bound, Prune♟️ Minimax & Alpha–Beta Laboratory
Evaluate a real game tree event by event. Compare complete minimax with alpha–beta, change move order and see exactly which branches become irrelevant.
The same terminal utilities are preserved. Ordering changes work performed, not the minimax decision.
PROGRAM TRACING • TRUE LOOP EXECUTION
Trace A* Search from First Principles
Follow every heap pop, stale-entry test, neighbour relaxation, priority push and parent lookup. The cursor returns through the while and for loops exactly as Python executes.
Press Next to initialize the graph.
EXPRESSION
—OUTPUT
Waiting for print(...)
Step 0
PROGRAMMING PROBLEMS • CODEBHAVYA PATTERN
💻 Classical AI & Search Challenges
Attempt each program independently. Workspaces, hints and model programs remain collapsed initially.
0 / 5Solved independently0 / 500Best score
QUICK KNOWLEDGE CHECK
Test Your Search & Reasoning
Select one answer per question. Results show your choice, the correct answer and a clear explanation.
Not checked yet
PLACEMENT CHECKPOINT
Diagnose Search Systems Like an AI Engineer
State the guarantee you need, verify assumptions and inspect intermediate decisions before replacing the algorithm.
Check whether BFS was used with unequal costs, whether relaxations reopen states and whether termination happened on generation.
Measure heuristic accuracy and computation cost; compare against the zero-heuristic UCS baseline.
Check utility perspective, cutoff depth, evaluation calibration, horizon effects and move ordering.
Add MRV, propagation and structure-aware constraints; inspect which assignment first empties a domain.
Separate absent facts, unmatched entities, rule direction, inference incompleteness and access restrictions.
Verify conditional tables, observed evidence, normalization, independence assumptions and causal interpretation.
CodeBhavya interview pattern:Formulate states and goals → Specify costs and guarantees → Select expansion rule → State assumptions → Trace frontier or recursion → Control repeated work → Prove stopping condition → Reconstruct or explain result → Measure time and space → Describe failure modes and alternatives.
INTERVIEW PREPARATION
🎤 Classical AI, Search & Reasoning — Interview Questions
Answer aloud before selecting Show Answer for each detailed explanation.
KEY TAKEAWAY
Intelligence Begins with an Explicit Decision Model
Define state, action, goal and cost.
Choose the next state or move deliberately.
Record better paths, bounds or domains.
Stop only when the guarantee is satisfied.
Return the path, proof or decision trail.
A strong AI solution is not only a final answer—it is a justified sequence of choices whose assumptions, costs and stopping rule can be inspected.
EXTRA TIPS
Eight Practical Search & Reasoning Habits
Write the state representation and goal predicate before writing the frontier loop.
Use BFS only when step costs are equal and minimum depth is the objective.
Maintain best costs and skip stale priority-queue entries.
Test A* with h=0 to obtain a uniform-cost correctness baseline.
Reconstruct paths using parents instead of copying complete paths into every queue item.
Order promising game moves first to expose alpha–beta pruning.
Use MRV and propagation to reveal CSP contradictions before deep recursion.
Record provenance for every rule-based or probabilistic conclusion.
EXTRA PRACTICE QUESTIONS
Strengthen Search & Reasoning
Calculate intermediate values and defend every expansion, pruning and inference decision.
- 01
Formulate the 8-puzzle as a search problem.
- 02
Trace BFS and DFS on the same cyclic graph.
- 03
Explain why UCS handles unequal edge costs.
- 04
Calculate A* priorities for five frontier states.
- 05
Design an admissible heuristic for grid routing.
- 06
Construct an inconsistent but admissible heuristic.
- 07
Explain stale heap entries and reopen logic.
- 08
Back up a three-ply minimax tree by hand.
- 09
Mark alpha–beta cutoffs for two move orders.
- 10
Model exam scheduling as a CSP.
- 11
Apply MRV, LCV and forward checking to map coloring.
- 12
Compare forward and backward chaining.
- 13
Identify an explaining-away pattern.
- 14
Separate probabilistic association from intervention.