Joyous Brands

Artificial Intelligence: A Visual Learner's Series

Part 2: Search

Author: Christopher DanosAI by Claude

Many AI problems are about finding a route from where you are to where you want to be.

Problems as maps of states

In one line: Describe every situation the problem can be in and every move between situations, then look for a route to the goal.

  [scrambled puzzle] ─slide─▶ [one tile moved] ─slide─▶ … ─▶ [solved]
       initial state          action → new state          goal test

Key terms: states, initial state, actions, transition model, goal test, path cost. Together the states and moves form the state space.

Watch out: State spaces explode. The 8-tile puzzle has about 181,000 reachable states; the 15-tile one about 10 trillion.

Searching without hints

In one line: With no clue where the goal is, the only choice is the order in which you explore.

Same tree, two visiting orders: numbers show which node is explored whenBreadth-first: level by level1234567Finds the shallowest goal; memory-hungryDepth-first: one branch at a time1253467Little memory; can wander far from the goal

  • Breadth-first checks everything one step away, then two, so it finds the shortest route when steps cost the same.

  • Depth-first dives down one branch before backing up, using little memory.

  • Uniform-cost search expands the cheapest path so far; iterative deepening reruns depth-first with growing depth limits.

Watch out: Track visited states, or search can bounce between the same two forever.

Searching with a hint: A*

In one line: If you can estimate how far each state is from the goal, explore the promising ones first.

A* ranks each state by cost so far plus estimated cost to goStartnGoalg(n): actual cost so farh(n): estimated cost to goe.g. straight-line distancef(n) = g(n) + h(n): explore the lowest f first

  • A heuristic is admissible if it never overestimates. Straight-line distance is admissible because no road is shorter than a straight line.

  • With an admissible heuristic, A* is guaranteed to find the cheapest path.

Watch out: Set h = 0 and A* becomes uniform-cost search. All the speedup comes from the hint.

In one line: When only the final answer matters, start somewhere and keep making small improvements.

Always climbing can strand you on the wrong peakHill climbing stops hereevery neighbor is lowerHighest pointSimulated annealing sometimes steps down hereto reach the taller slope

  • Hill climbing moves to the best neighbor until none is better.

  • Random restarts and simulated annealing are two ways to escape a false peak.

  • Used for scheduling, layout and tuning. Training neural networks (Part 7) works the same way, stepping downhill on error.

Playing against an opponent

In one line: Assume your opponent will make the move that's worst for you, and pick the move whose worst case is best.

            You (max)          pick the highest of
           /    |    \
        Opp   Opp    Opp       each picks the lowest of
        3 12  2 4    14 1      final scores
        ↓     ↓      ↓
        3     2      1   →  you pick 3

Key terms: minimax; alpha-beta pruning skips branches that can't change the decision; evaluation functions estimate who's winning when you can't search to the end; Monte Carlo tree search estimates positions by simulating many games.

Watch out: Minimax assumes a perfect opponent; the evaluation function is usually the weak spot.

Self-test

  1. Redraw the seven-node tree and number it for breadth-first and depth-first order.

  2. Draw the A* diagram and explain why an overestimating h breaks the guarantee.

  3. Sketch a landscape with three peaks and show where hill climbing could get stuck.