Artificial Intelligence: A Conceptual Learner's Series
Part 2: Search
Many AI problems can be framed as finding a path from where you are to where you want to be. This part covers how to frame a problem that way and five families of methods for finding the path.
Concept 1: Problems as state spaces
In one line: To let a computer solve a problem, describe every situation it could be in and every move that leads from one situation to another, then look for a route to the goal.
Example: Picture a sliding-tile puzzle: eight numbered tiles in a 3 × 3 frame with one empty square. Each arrangement of tiles is a situation. Each slide of a tile into the gap is a move that produces a new arrangement. Solving the puzzle means finding a sequence of slides from the scrambled arrangement to the ordered one. The computer doesn't need to "understand" puzzles; it just needs this map of situations and moves.
Formally: A search problem has:
States: every possible configuration (each tile arrangement).
Initial state: where you start (the scrambled board).
Actions: the moves available in a state (slide up, down, left or right).
Transition model: which state each action produces.
Goal test: how to recognize success (tiles in order).
Path cost: how expensive a route is (usually the number of moves).
The states and transitions form a graph called the state space. A solution is a path from the initial state to a goal state; an optimal solution has the lowest path cost.
Connections: This is how a goal-directed rational agent (Part 1, Concept 4) plans ahead when the world is predictable and fully visible.
Watch out:
State spaces explode. The 8-tile puzzle has about 181,000 reachable states; the 15-tile version has about 10 trillion.
Framing is most of the work. Leave irrelevant detail out of the state (the color of the tiles), or the space grows for nothing.
Concept 2: Uninformed search
In one line: When you have no hint about which direction leads to the goal, you can still search systematically by deciding the order in which to try possibilities.
Example: You've lost your keys somewhere in the house. One strategy: check every spot in the room you're in, then every adjacent room, then rooms two doors away, expanding outward. You'll find the keys in the nearest place they could be, but you check a lot of spots. Another strategy: pick a hallway and go all the way to the end, checking as you go, before backing up to try another. That uses less mental bookkeeping but might send you to the attic while the keys sit on the next table.
Formally:
Breadth-first search (BFS) explores all states one step away, then two steps, and so on. It finds the shortest path when every step costs the same, but its memory use grows very fast.
Depth-first search (DFS) follows one path as deep as possible before backtracking. It uses little memory but can wander far and miss nearby solutions.
Uniform-cost search always expands the cheapest path found so far. It finds the optimal solution when step costs differ.
Iterative deepening runs depth-first search with a depth limit of 1, then 2, then 3, combining DFS's small memory with BFS's completeness.
The frontier is the set of paths waiting to be explored; the strategy is simply the rule for which one to take next.
Connections: These strategies are the baseline that smarter heuristic search (Concept 3) improves on.
Watch out:
Memory, not time, usually runs out first for breadth-first search.
Track visited states. Without it, search can loop back and forth between the same two states forever.
Concept 3: Heuristic search and A*
In one line: If you have a rough estimate of how far each state is from the goal, you can search the promising directions first and save enormous amounts of work.
Example: A navigation app is routing you across a city. It doesn't know the exact remaining drive time from every intersection, but it knows the straight-line distance to your destination. So it prefers roads that head toward the destination, while still adding up the actual time driven so far. It rarely bothers exploring roads that lead the opposite way.
Formally:
A heuristic h(n) estimates the cost from state n to the nearest goal.
A* search expands the state with the lowest total estimate:
Here g(n) is the actual cost to reach n so far, and h(n) is the estimated remaining cost.
A heuristic is admissible if it never overestimates the true remaining cost. Straight-line distance is admissible because no road is shorter than a straight line. With an admissible heuristic, A* is guaranteed to find an optimal path.
A more accurate admissible heuristic means fewer states explored.
Connections: A good heuristic is a form of built-in knowledge (Part 1, Concept 4) and a practical answer to limited computation (Part 1, Concept 5).
Watch out:
Overestimating breaks the guarantee. An inadmissible heuristic can be faster but may return a worse path.
h = 0 turns A* back into uniform-cost search. The heuristic is where all the speedup comes from.
Concept 4: Local search
In one line: When you only care about finding a good final state, not the path to it, you can start somewhere and keep making small improvements.
Example: You're on a mountain in thick fog, trying to reach the highest point. You can't see the summit, only the ground right around you. So you keep stepping in whichever direction goes up. This works until you reach a small hilltop where every direction goes down. You're on a peak, just not the highest one. A smarter hiker sometimes takes a step downhill early on, accepting a short-term loss in order to find a taller slope.
Formally:
Local search keeps a single current state and moves to neighboring states, ignoring the path.
Hill climbing always moves to the best neighbor. It is fast but gets stuck on local maxima (peaks that aren't the highest) and flat plateaus.
Random restarts run hill climbing many times from random starting points and keep the best result.
Simulated annealing sometimes accepts worse moves, with a probability that shrinks over time, so it can escape local maxima early and settle down later.
Useful for optimization problems such as scheduling, layout and tuning, where the goal is the best configuration.
Connections: Training a neural network (Part 7) is a form of local search: gradient descent steps downhill on an error surface.
Watch out:
A local optimum can look like success. Always ask whether a better solution might exist elsewhere.
Local search gives no optimality guarantee. It trades certainty for speed on huge problems.
Concept 5: Adversarial search
In one line: When an opponent is choosing moves against you, plan by assuming they'll make the move that's worst for you, and pick the move that leaves you best off anyway.
Example: In tic-tac-toe, before placing an X, you think: "If I play here, what's the best reply for my opponent? And then my best reply to that?" You follow each line to the end of the game. A move that looks good but lets your opponent force a win is a bad move. You choose the move whose worst-case outcome is still the best available.
Formally:
A game tree lays out alternating moves by each player down to the game's end.
Minimax: the maximizing player picks the move with the highest value, assuming the minimizing opponent always picks the lowest. Values propagate up from the end positions.
Alpha-beta pruning skips branches that can't affect the final decision. With good move ordering it lets a program search roughly twice as deep in the same time.
For big games, search stops at a depth limit and an evaluation function estimates who is winning (for example, material count in chess).
Monte Carlo tree search estimates a position's value by playing many quick random or guided games from it, an approach used in strong Go programs.
Connections: This extends search (Concepts 2 and 3) to a world where another agent's goals oppose yours. Evaluation functions are heuristics (Concept 3) for game positions.
Watch out:
Minimax assumes a perfect opponent. Against a weak or unpredictable one, the safest move may not be the most profitable.
The evaluation function is the weak spot. A deep search with a poor evaluation can confidently pick bad moves.
Retention kit
Answer from memory, then check. Review at about 1 day, 3 days, 1 week, 2 weeks and 1 month.
What six parts define a search problem? Use the sliding-tile puzzle as your example.
When would you choose breadth-first search over depth-first search, and what does each cost?
Write the A* formula and explain each term. What makes a heuristic admissible, and why does it matter?
Why does hill climbing get stuck, and name two ways to get unstuck.
How does minimax choose a move, and what does alpha-beta pruning add?
Build exercise (1–2 hours): Generate a 30 × 30 grid maze with random walls. Implement breadth-first search and A* with Manhattan distance as the heuristic. Count how many cells each one expands to find the same path. Then double the heuristic (making it inadmissible) and check whether A* still finds the shortest path.
Python algorithms
One file covering every method in this part: breadth-first search and A* on a maze (Concepts 2–3), hill climbing versus simulated annealing (Concept 4), and minimax with alpha-beta pruning on tic-tac-toe (Concept 5). Runs with plain Python 3.
import heapq, math, random
from collections import deque
# Grid maze: 0 = open, 1 = wall. Moves: up/down/left/right, cost 1 each.
MAZE = [
[0, 0, 0, 0, 1, 0, 0],
[1, 1, 0, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 1, 0],
]
def neighbors(cell, grid):
r, c = cell
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 0:
yield (nr, nc)
def bfs(start, goal, grid):
"""Breadth-first search: shortest path when every step costs the same."""
frontier, parent, expanded = deque([start]), {start: None}, 0
while frontier:
cell = frontier.popleft()
expanded += 1
if cell == goal:
break
for nxt in neighbors(cell, grid):
if nxt not in parent: # track visited states
parent[nxt] = cell
frontier.append(nxt)
return reconstruct(parent, goal), expanded
def astar(start, goal, grid, weight=1.0):
"""A*: expand the cell with the lowest f = g + h."""
h = lambda c: weight * (abs(c[0] - goal[0]) + abs(c[1] - goal[1])) # Manhattan
frontier = [(h(start), 0, start)]
g, parent, expanded = {start: 0}, {start: None}, 0
while frontier:
_, cost, cell = heapq.heappop(frontier)
if cost > g[cell]:
continue
expanded += 1
if cell == goal:
break
for nxt in neighbors(cell, grid):
new = cost + 1
if new < g.get(nxt, math.inf):
g[nxt], parent[nxt] = new, cell
heapq.heappush(frontier, (new + h(nxt), new, nxt))
return reconstruct(parent, goal), expanded
def reconstruct(parent, goal):
path, cell = [], goal
while cell is not None:
path.append(cell)
cell = parent.get(cell)
return path[::-1]
def simulated_annealing(f, x0, steps=5000, temp=5.0, seed=0):
"""Maximize f over integers; sometimes accept worse moves early on."""
rng, x = random.Random(seed), x0
best = x
for t in range(steps):
T = temp * (1 - t / steps) + 1e-9 # cooling schedule
nxt = x + rng.choice([-1, 1])
delta = f(nxt) - f(x)
if delta > 0 or rng.random() < math.exp(delta / T):
x = nxt
if f(x) > f(best):
best = x
return best
def hill_climb(f, x0):
x = x0
while True:
nxt = max([x - 1, x + 1], key=f)
if f(nxt) <= f(x):
return x # local maximum
x = nxt
# Tic-tac-toe with minimax + alpha-beta pruning
LINES = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)]
def winner(b):
for a, c, d in LINES:
if b[a] != " " and b[a] == b[c] == b[d]:
return b[a]
return None
def minimax(b, player, alpha=-2, beta=2):
"""Returns (value, move) from X's point of view: +1 win, 0 draw, -1 loss."""
w = winner(b)
if w:
return (1 if w == "X" else -1), None
if " " not in b:
return 0, None
best_move = None
for m in [i for i, s in enumerate(b) if s == " "]:
b[m] = player
val, _ = minimax(b, "O" if player == "X" else "X", alpha, beta)
b[m] = " "
if player == "X" and val > alpha:
alpha, best_move = val, m
elif player == "O" and val < beta:
beta, best_move = val, m
if alpha >= beta: # prune: can't change the decision
break
return (alpha if player == "X" else beta), best_move
if __name__ == "__main__":
start, goal = (0, 0), (4, 6)
p, e = bfs(start, goal, MAZE); print(f"BFS: path length {len(p)-1}, expanded {e}")
p, e = astar(start, goal, MAZE); print(f"A*: path length {len(p)-1}, expanded {e}")
f = lambda x: -((x - 2) ** 2) + 10 if x < 6 else -((x - 10) ** 2) + 20 # peaks at 2 and 10
print("Hill climbing from 0 stops at:", hill_climb(f, 0))
print("Simulated annealing finds:", simulated_annealing(f, 0))
print("Tic-tac-toe value with perfect play (0 = draw):", minimax(list(" " * 9), "X")[0])Output when run:
BFS: path length 10, expanded 20
A*: path length 10, expanded 12
Hill climbing from 0 stops at: 2
Simulated annealing finds: 10
Tic-tac-toe value with perfect play (0 = draw): 0Try it:
Call
astar(..., weight=3)to make the heuristic inadmissible, and check on a bigger maze whether the path stays shortest.Lower the annealing
tempto 1 and run several seeds: it gets stuck on the smaller peak more often.