3 Intelligent search

This chapter introduces intelligent search by showing how domain knowledge can steer exploration toward good solutions faster than uninformed strategies. It frames heuristics as problem-specific, educated guesses that score or constrain states when exact optimization is infeasible. Through everyday and practical examples—routing, preference scoring, and content matching—it illustrates how a well-chosen heuristic reshapes a search space. A weighted-maze scenario further grounds the idea: when some moves are costlier than others, the “best” path is determined by both the number of steps and their cumulative costs, so a heuristic that favors cheaper, shorter routes becomes a powerful guide.

The chapter then focuses on informed search methods, emphasizing A* as the workhorse. A* evaluates candidates by combining actual cost so far (g) with a heuristic estimate to the goal (h), exploring nodes via a priority queue that always selects the lowest estimated total cost (f = g + h). With an admissible (and, for graphs, consistent) heuristic, A* is guaranteed to find the optimal path while avoiding large swaths of unpromising nodes; with a poor heuristic, it forfeits that guarantee and efficiency. Practical details—tracking parents to reconstruct solutions, calculating costs on the fly, and choosing sensible heuristics like Manhattan distance—highlight how A* blends breadth- and depth-wise behavior in service of speed and optimality. Typical applications include game pathfinding, network routing, decoding in NLP, and puzzle solving.

Finally, the chapter turns to adversarial search, where outcomes depend on an opponent’s choices in zero-sum settings. Using Connect Four as a running example, it explains how min-max simulates alternating turns to a fixed depth, applies a heuristic to score leaf states (wins, losses, draws), and propagates values upward by alternating maximize/minimize decisions. Because the game tree grows explosively, the chapter introduces alpha-beta pruning, which maintains bounds (alpha for the maximizer, beta for the minimizer) to cut off branches that cannot change the final decision—yielding the same choice with far less computation. The section closes with use cases, from agents for perfect- and imperfect-information games to hybrid approaches that pair adversarial search with techniques like ant colony optimization for real-world routing.

Comparison of two audio clips using frequency distribution

Adjustments to the maze example: gravity

All possible movement options represented as a tree

The function for the A* search algorithm

The sequence of tree processing using A* search (part 1)

The sequence of tree processing using A* search (part 2)

Flow for the A* search algorithm

The sequence of tree processing using A* search (part 1)

The sequence of tree processing using A* search (part 2)

Nodes visited in the entire tree after A* search

The game of Connect Four

The sequence of tree processing using min-max search

The explosion of possibilities while searching the game tree

Scoring for the agent versus scoring for the opponent

Flow for the min-max search algorithm

A representation of the possible states in a Connect Four game

The possible end states in a Connect Four game

The possible scores for end states in a Connect Four game (part 1)

The possible scores for end states in a Connect Four game (part 2)

The possible scores for end states in a Connect Four game (part 3)

Simplified game tree with min-max scoring

An example of alpha-beta pruning

Flow for the min-max search algorithm with alpha-beta pruning

FAQ