Metadata Card
- Prerequisites: Vol 2 Graphs & Trees, Vol 10 Linear Algebra
- Estimated time: 45 minutes
- Core difficulty: Advanced
- Reading mode: High focus
- Completion: Able to implement BFS, DFS, A*, and Minimax search in Python
Your Progress
Remembering what Ahua wrote in her letter—"I wish it could learn on its own"—you push open the door of the Model Workshop, starting with the simplest intelligent behavior: finding a path within a given space.
Your Task
When an agent faces an unknown environment, what's the first ability it needs? Search. Finding a target within a known state space is the starting point of all reasoning and learning. This chapter implements four search algorithms and observes how they trade off cost and optimality in different scenarios.
Chapter Layers
- Required: BFS, DFS, A*
- Optional: Game tree search and alpha-beta pruning
- Advanced: Viewing search as a general problem-solving framework
Breaking Through · Tracing the Origin
Imagine standing at the entrance of a maze. Countless forks in the road before you, the goal behind some door. How do you find it?
The simplest thought: go down one path until the end, hit a wall, backtrack to the last fork—this is depth-first search. But it doesn't guarantee the shortest path. So try differently: explore all forks by their distance from the entrance—this is breadth-first search, guaranteeing the shortest path but needing to remember many useless paths.
If every path in the maze has "traffic conditions" (which is shorter, which has obstacles), you can use A*: choose a heuristic function (like straight-line distance) to guide you toward the "most likely" direction first. This is the leap from blind search to heuristic search.
BFS and DFS
We start with the simplest state: a tree structure where each node has several children.
The first tool in the Model Workshop is search. BFS uses a queue to expand layer by layer, DFS uses a stack to go down one path until the end—they differ by just one line of code (deque.popleft vs stack.pop), but their search paths are completely different.
# ch01_search.py
from collections import deque
def bfs(tree, root, target):
"""Breadth-first: layer-by-layer search"""
queue = deque([root])
visited = set()
while queue:
node = queue.popleft()
if node == target:
return True
visited.add(node)
for child in tree.get(node, []):
if child not in visited:
queue.append(child)
return False
def dfs(tree, root, target):
"""Depth-first: go down one path"""
stack = [root]
visited = set()
while stack:
node = stack.pop()
if node == target:
return True
visited.add(node)
for child in tree.get(node, []):
if child not in visited:
stack.append(child)
return FalseLet's run it:
tree = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['G'],
'F': [],
'G': []
}
print(bfs(tree, 'A', 'G')) # True
print(dfs(tree, 'A', 'G')) # TrueBoth can find the target, but the routes differ. BFS goes A→B→C→D→E→F→G, DFS goes A→C→F→...→B→E→G. On a wider tree, BFS needs O(b^d) space (b = branching factor, d = depth), while DFS only needs O(d).
A Search*
Now introduce costs. Each edge has a traversal cost, and you want to find the path with the minimum total cost. Dijkstra can solve this (the weighted version of BFS), but it's too slow when the search space is huge. A* adds a heuristic function h(n) to estimate the distance from n to the goal, preferring to explore nodes with the smallest f(n) = g(n) + h(n), where g(n) is the actual cost from the start to n.
A* adds a heuristic as a compass on top of Dijkstra—without it you have to explore all directions; with it, you only head toward the most promising direction. Here's the complete implementation:
import heapq
def a_star(graph, start, goal, heuristic):
"""A* search: g(n) + h(n) guides the search direction"""
open_set = [(0, start)]
g_score = {start: 0}
came_from = {}
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
return path[::-1]
for neighbor, cost in graph.get(current, []):
tentative_g = g_score[current] + cost
if tentative_g < g_score.get(neighbor, float('inf')):
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score = tentative_g + heuristic(neighbor, goal)
heapq.heappush(open_set, (f_score, neighbor))
return None # no pathIf h(n)=0, A* degenerates to Dijkstra. If h(n) is a lower bound on the actual shortest distance (admissible), A* is guaranteed to find the optimal solution. Manhattan distance is a commonly used admissible heuristic on grid maps.
The process of finding the optimal path is a process of pruning the search space—A uses heuristics to tell you which directions are worth exploring.*
Game Tree Search
Search isn't just for paths. When playing chess, you're also searching: in the current state (position), which move maximizes your winning chances? The Minimax algorithm recursively evaluates each move: you choose the one most favorable to you, the opponent chooses the one most unfavorable to you.
Game tree search is another face of search: not finding paths, but finding optimal decisions. The maximizing player picks the maximum, the minimizing player picks the minimum—the alternating structure of this decision tree precisely captures the nature of zero-sum games.
def minimax(state, depth, maximizing):
if depth == 0 or is_terminal(state):
return evaluate(state)
if maximizing:
value = -float('inf')
for move in get_moves(state):
value = max(value, minimax(move, depth - 1, False))
return value
else:
value = float('inf')
for move in get_moves(state):
value = min(value, minimax(move, depth - 1, True))
return valueThis tree alternates between max layers and min layers. Alpha-beta pruning records two values during traversal: alpha (the current maximum lower bound) and beta (the current minimum upper bound). Once beta <= alpha, the remaining branches are pruned.
Adding alpha-beta pruning reduces search space from O(b^d) to O(b^{d/2})—doubling the effective search depth with only two lines of extra code.
def alpha_beta(state, depth, alpha, beta, maximizing):
if depth == 0 or is_terminal(state):
return evaluate(state)
if maximizing:
value = -float('inf')
for move in get_moves(state):
value = max(value, alpha_beta(move, depth - 1, alpha, beta, False))
alpha = max(alpha, value)
if beta <= alpha:
break # beta prune
return value
else:
value = float('inf')
for move in get_moves(state):
value = min(value, alpha_beta(move, depth - 1, alpha, beta, True))
beta = min(beta, value)
if beta <= alpha:
break # alpha prune
return valueIdeally, alpha-beta pruning reduces search space from O(b^d) to O(b^{d/2})—doubling search depth at zero cost.
Common Pitfalls
- BFS and DFS struggle with infinite state spaces: BFS may exhaust memory, DFS may never backtrack (use depth-limited or iterative deepening).
- An inadmissible A* heuristic can significantly speed up search but sacrifices optimality.
- Minimax is extremely sensitive to search depth—without alpha-beta pruning, a 10-ply chess tree has about 35^10 ≈ 2.7e15 nodes.
- Search algorithms depend on state representation—the same maze, expressed as an abstract "room-corridor" graph vs pixel-level grid, has search costs differing by orders of magnitude.
Pass Challenges
- Warm-up (10 min): On a 5×5 grid, use A* to find a path around obstacles. Try Manhattan distance and Euclidean distance as heuristics, observe the difference in node visits.
- Challenge (30 min): Implement a Tic-Tac-Toe AI using alpha-beta pruning. Play against it—can you beat it?
- Observation: Print the f, g, h values of each expanded node in A* to understand how the three values work together.
Traveler's Notes
Search is the fundamental operation of intelligence. From path planning to game playing, it's always about making choices in a state space—the difference is only in the cost function and search strategy.
-> Next Chapter Preview
Having solved "how to find," the next step is "how to represent knowledge so machines can reason."