Counting and Search

This is Unit Two of Artificial Intelligence: counting and search. The unit opens with arithmetic, and the arithmetic decides everything after it. When each step of a plan offers several choices and the plan runs many steps deep, the number of possible plans multiplies rather than adds — and multiplied often enough it exceeds what any machine could ever examine. That wall is mathematical rather than technological. A faster computer moves it slightly and does not remove it, which means acting intelligently in any interesting problem requires choosing what to look at. Then the unit does something clarifying. Every search strategy here shares one loop and one bookkeeping structure, and they differ in exactly one decision — which candidate to examine next. Everything else is identical, which turns a list of algorithms into one algorithm with a slot in it. And each choice for that slot is a purchase: a guarantee bought, a cost paid. The question is never which is smarter — it is what does this one promise, and at what price. By the end you will be able to do five things. One: say why possibilities multiply, and what that rules out. Two: say what every strategy shares, and where they differ. Three: state a guarantee and its cost as a purchase. Four: say why an estimate must be optimistic before it is accurate. Five: manufacture an estimate by deleting rules.

Three objects the whole unit is built on, and one warning worth taking seriously. These get drawn on a page, and nothing about how the drawing looks carries information — only the connections do.

The first object.

AI 0061 The Graph

A collection of items together with the connections between them, and nothing else. Distance and position on a drawing mean nothing — reading them as facts is a mistake the picture invites.

The second.

AI 0062 The Path

A sequence of connections leading from one item to another. Between any two there may be many, or there may be none — nothing about a graph promises one exists.

The third.

AI 0063 The Tree

A graph growing from one root by branching, with exactly one path from the root to anything else. No connection ever loops back, and that single restriction is the entire definition.

Two numbers describing a tree, the law relating them, and what that law rules out. This is where the unit's central fact gets established, and the last entry prices it by hand so the size is felt rather than asserted.

How wide.

AI 0064 The Branching Factor

The number of choices available at each step. Real trees branch unevenly, so this is one number standing in for a varying reality — typical or exact, depending on the problem.

How deep.

AI 0065 Depth

The number of steps from the root — how many choices deep a plan has gone. It counts decisions rather than elapsed time, which are different things.

The law.

AI 0066 Possibilities Multiply

With several choices at every step over many steps, the number of distinct plans is the branching factor multiplied by itself once per step. It is not the two numbers multiplied together — three choices over sixteen steps is over forty million.

What that rules out.

AI 0067 No Agent Examines Everything

Interesting problems branch enough that nothing can examine every plan. The wall is mathematical rather than technological — faster machines move it barely, and never remove it.

Pricing one by hand.

AI 0068 Pricing a Tree by Hand

An exponent too large to compute directly gets priced by repeated squaring — a few multiplications, then name the magnitude. The grid is invented so the arithmetic stays exact.

Four entries that turn everything after this into one algorithm. A problem definition, a to-do list, a loop of three moves — and then the observation that all the strategies in this unit differ in exactly one decision.

The problem.

AI 0076 The Search Problem

Four things: the states a situation can be in, the actions connecting them, where you start, and a test for having arrived. Anything with situations and moves between them fits.

The to-do list.

AI 0077 The Frontier

The set of paths built so far and not yet extended. It holds paths rather than places — a subtle distinction that carries weight later.

The loop.

AI 0078 The Search Loop

Take a path from the list, stop if it has arrived, otherwise extend it and file the results. And an empty list with nothing found is an answer — it means no solution exists.

And the one difference.

AI 0079 The Selection Slot

Strategies differ in which waiting path they select. The loop, the list and the filing stay identical across every one of them — so there is one algorithm with a slot.

One choice for that slot, run all the way through on a small map — and then an entry deflating what watching it might suggest. It is worth noticing that the deflation cuts both ways.

The choice.

AI 0080 Breadth-First Search

Always take the path that has waited longest, finishing every one-step path before starting any two-step path. Nothing about the goal's direction is consulted — arrival order alone drives it.

Run whole.

AI 0081 Breadth-First, Run Whole

A complete run on a small map, showing competence assembling out of pure bookkeeping. Each turn is: remove a path, check its last entry, extend it, file the results.

And what it does not show.

AI 0082 "The Machine Understood the Map"

Watching the search find a route does not show anything understood the map — every turn was label-copying a clerk could perform. And the deflation runs the other way too: bookkeeping that reliably produces the right answer is worth respecting.

Two entries stating a promise and the bill attached to it. Both are real, and stating them together is what makes the next topic's framing possible.

The promise.

AI 0083 The Fewest-Steps Guarantee

It will find a solution with the fewest steps, because paths are served strictly in order of length. The guarantee is structural rather than lucky — every shorter candidate was tried first.

The bill.

AI 0084 The Memory Bill

The waiting list grows exponentially with depth, following the counting law from Topic Two. Honest bookkeeping states the guarantee and the appetite in the same breath.

A different choice for the same slot, and a genuinely instructive result: run on the same problem, it can be brilliant or terrible, and which one it is depends on nothing more than the order the options were listed in.

The choice.

AI 0085 Depth-First Search

Always take the most recently built path, following one line to its end before backing up. Where the first strategy sweeps, this one dives — and a dive can be lucky.

Run whole.

AI 0086 Depth-First, Run Whole

A complete run showing the strategy at its best, and then what that speed depended on. Both demonstrations are the same algorithm — the brilliance and the blunder differ only in ordering.

What it buys.

AI 0087 Thrift Without Promises

Almost no memory — one line of descent at a time — and no promise at all about the solution's length. The outcome hangs on accidents rather than on structure.

The framing that makes sense of all of it, plus one thing every practical search needs and one pitch to be suspicious of. The framing replaces a question people ask constantly with a better one.

The framing.

AI 0088 Strategies Are Purchases

Choosing a strategy is buying a guarantee and paying a cost — fewest steps for memory, thrift for risk. Which is smarter is the wrong question; what does this promise and at what price is the right one.

What practice requires.

AI 0089 Remembering Where You Have Been

A search that does not track where it has already been can rebuild the same paths indefinitely, so practical searches keep a log. Memory of the world and memory of the search are separate records.

The pitch to distrust.

AI 0090 "A Bigger Computer Would Fix It"

When blind search fails at scale, more hardware is not the answer — the obstacle is the multiplication of possibilities. Pitches promising to beat a combinatorial space by scale alone have a poor record.

And what this all buys.

AI 0091 What Blind Search Buys

Systematic search solves anything drawable as a finite graph with a recognisable goal — right up until the graph outgrows any affordable machine. Past that, the slot needs an opinion in it.

Three entries introducing the second half. A distinction the first strategy's guarantee misses entirely, the object that lets a search hold an opinion, and the property that opinion has to have.

Cheapest, not shortest.

AI 0101 Path Cost

A path's cost is the sum of its actions' costs, and the best solution is the cheapest rather than the one with fewest steps. The earlier guarantee was about the wrong quantity.

The opinion.

AI 0102 The Heuristic

A quick estimate, attached to each state, of the cost still remaining. It is an opinion with a number on it, and its quality decides a great deal.

The property it needs.

AI 0103 Admissible

Admissible means never overestimating what remains — systematically optimistic, never inflated. Optimism is the load-bearing property here, and accuracy is a luxury.

One more choice for the selection slot — follow the estimate alone — and a map built specifically to punish it. What the trap shows is subtle: the failure belongs to the strategy, not to the estimate.

The choice.

AI 0104 Greedy Search

Always extend whichever path ends closest to the goal by the estimate — inheriting every blind spot that estimate has. On looping maps it can circle among promising-looking states indefinitely.

The trap.

AI 0105 The Gorge Trap

A purpose-built map where this selection walks into a trap that even an admissible and accurate estimate cannot prevent. The same numbers serve a different strategy perfectly well.

The strategy that fixes it, and the fix is one addition: score a path by what has already been spent plus what is estimated to remain. Then the same trap, replayed — and the difference in behaviour is precise.

The strategy.

AI 0106 A-star

Score each path by the cost already incurred plus the estimated cost remaining, and always extend the lowest score. The scores get their meaning from the estimate's optimism.

The same trap, replayed.

AI 0107 A-star Beats the Gorge

Under the combined score, the lure is examined, priced, and declined. It was not avoided — it was inspected and out-priced, which is a different and more reliable thing.

The capstone. One town, one route.

AI 0108 The Eight-Kilometer Delivery

A complete run on one town, from an empty list through to a certified cheapest route. Every number in it is checkable by hand — and checking a single turn teaches more than watching all of them.

The guarantee.

AI 0109 The Optimism Guarantee

With an admissible estimate, this returns a lowest-cost solution. The fine print is mild — bounded branching, and every action costing something — and any real map satisfies it.

Three entries closing the unit. Which property of an estimate actually matters, a reliable method for building one, and what the whole apparatus has bought — along with two assumptions still standing underneath it.

Which property matters.

AI 0110 "A Helpful Estimate Must Be Accurate"

A useful estimate need not be accurate — it needs to be optimistic. Accuracy buys speed while optimism protects the answer. An estimate that is impressively accurate but occasionally too high can return the wrong route.

How to build one.

AI 0111 Relax the Problem

Delete rules from the problem, solve the easier version exactly, and use that answer as the estimate. Every legal route is also legal in the relaxed problem, so the relaxed answer can never be too high.

And what it bought.

AI 0112 What Guessing Well Buys

Informed search converts an unaffordable exhaustive exploration into an affordable selective one, at the price of building a good estimate. Two assumptions remain underneath everything: the world holds still, and one agent is acting.

Five things you can now do. You can say why possibilities multiply rather than add, and what follows — a wall that is mathematical rather than technological, which more hardware barely moves. You can say what every strategy shares — one loop, one waiting list — and that they differ in exactly one decision, which path to take next. You can state a strategy as a purchase: fewest steps bought with memory, thrift bought with the loss of every promise. You can say why an estimate must be optimistic before accurate — optimism protects the answer and accuracy only buys speed. And you can manufacture an estimate by deleting rules and solving the easier problem exactly, which guarantees the result is never too high.