You are standing at the entrance of a maze.
Somewhere inside is the exit.
You can move:
- Up
- Down
- Left
- Right
Some paths are blocked.
Some look promising.
And some are spectacularly bad ideas.
Your mission is simple:
Find the exit.
Now imagine an AI system standing beside you.
It has exactly the same problem.
So who gets out first?
You?
Or the machine?
There is one small complication.
The AI does not magically know the route either.
It has to:
Search.
And that simple word leads us into one of the oldest, and still one of the most important, ideas in Artificial Intelligence.
The Challenge
Let us begin with a puzzle.
Here is our maze.
S = Start
G = Goal
Dark squares are blocked.
You may move:
- Up
- Down
- Left
- Right
but not diagonally.
Your task:
Find a shortest path from S to G.
Take a few seconds before continuing.
Can you see a route?
Do not worry.
There is no timer.
The AI is not judging you.
Probably.
But instead of asking only:
“What is the answer?”
let us ask the more interesting AI question:
How should an intelligent system search for the answer?
There Is More Than One Way to Search
Imagine arriving at a junction with three possible paths.
What should you do?
You could:
Option A
Pick one path and keep going until something forces you to stop.
Option B
Explore everything nearby first before moving farther away.
Option C
Use some clue about which direction appears most promising.
Those simple strategies lead us toward several important search algorithms.
One behaves a little like:
“I have chosen this path and I am now emotionally committed to it.”
Another behaves like:
“Nobody moves until I have checked every nearby possibility.”
And another says:
“That direction looks promising. What could possibly go wrong?”
Quite a lot, as we will soon discover.
Depth-First Search: Pick a Path and Commit
Depth-First Search, usually called DFS, explores one path as deeply as possible before trying another.
Imagine entering the maze and deciding:
Left.
Then left again.
Then forward.
Then right.
Then forward.
Then…
Wall.
DFS now backtracks.
It returns to the most recent junction and tries another unexplored direction.
Conceptually:
Choose -> Explore deeply -> Hit a dead end -> Backtrack -> Try again
DFS has an important advantage.
It usually does not need to remember every possible state at once.
So its memory requirements can be relatively modest.
But there is a catch.
The first route DFS finds is not necessarily the shortest route.
Sometimes DFS gets lucky.
Sometimes it takes the scenic route.
A very scenic route.
Breadth-First Search: Everybody Gets a Turn
Breadth-First Search, or BFS, behaves differently.
Instead of following one path deeply, BFS first explores:
Everything one move away.
Then:
Everything two moves away.
Then:
Everything three moves away.
It expands outward layer by layer.
If every move has the same cost, BFS has a very useful property:
The first time BFS reaches the goal, it has found a shortest path.
That sounds excellent.
But BFS may need to store many possible states simultaneously.
So we already have a trade-off.
DFS
Uses relatively little memory, but may wander down an unfortunate path.
BFS
Systematic and capable of finding a shortest path in an unweighted maze, but may explore many possibilities.
In human terms:
DFS is the friend who says:
“Trust me. I know a shortcut.”
BFS is the friend who checks:
- Google Maps
- Apple Maps
- Road signs
- Traffic reports
- And possibly the original town-planning documents
The Search Tree
A maze can also be represented as a tree of decisions.
Suppose that from one position we have three possible moves.
Each of those gives us another three possibilities.
And each of those gives another three.
Very quickly, the number of possible paths begins to grow.
Suppose every step gives us approximately three choices.
After one step:
3^1 = 3 possibilities
After two:
3^2 = 9
After five:
3^5 = 243
After ten:
3^10 = 59,049
After twenty:
3^20 = 3,486,784,401
Yes.
More than:
3.4 billion possibilities.
At this point:
“Just try everything”
stops sounding like an algorithm.
It starts sounding like a cry for help.
Combinatorial Explosion
This rapid growth is called:
Combinatorial Explosion.
Suppose:
b = number of possible choices at each step
and:
d = number of decisions we make
A rough estimate of the size of the search space may behave like:
That exponent is the important part.
Even when b is relatively small, increasing d can produce an enormous number of possibilities.
This tells us something fundamental about Artificial Intelligence.
Intelligent search cannot simply mean:
Examine everything.
If the number of possibilities becomes enormous, we need another strategy.
We need to decide:
Which possibilities deserve attention first?
And that brings us to:
Heuristics.
The AI Has a GPS. Sort Of.
A heuristic is a useful estimate.
It does not tell us the exact answer.
It gives us a clue about which options appear more promising.
Suppose you are standing inside a maze.
You know the goal is somewhere northeast.
A path heading northeast may seem more promising than one heading far southwest.
Does that guarantee success?
No.
There may be a wall ahead.
But the clue can still help.
In search algorithms, we often represent a heuristic as:
where n represents the current state.
You can think of it as:
The important word is:
Estimated.
The AI is not clairvoyant.
It simply has a mathematically educated guess.
Which is already better than some of us trying to find the correct exit in a shopping mall.
Manhattan Distance
Suppose our world is a simple grid.
We can move only:
- Up
- Down
- Left
- Right
No diagonal movement.
If our current position is:
and the goal is:
one useful heuristic is:
This is called:
Manhattan Distance.
Suppose we need to travel:
6 blocks horizontally
and:
4 blocks vertically
Then:
Why is it called Manhattan distance?
Imagine travelling through city blocks.
You cannot simply walk diagonally through the buildings.
Well…
technically you can try.
The buildings may object.
The important point is that Manhattan distance gives the AI a simple estimate of:
How far might the goal still be?
Greedy Search: That Looks Close Enough
Now imagine an AI that always chooses whichever position appears closest to the goal according to the heuristic.
This leads us toward:
Greedy Best-First Search.
Greedy search focuses strongly on:
Its thinking is essentially:
“Which option looks closest to the goal right now?”
That can make it fast.
But it can also make it spectacularly overconfident.
Imagine that the goal is directly above us.
The most obvious path moves straight toward it.
Perfect.
Except…
There is a wall.
Meanwhile, another path initially moves sideways, apparently away from the goal, but goes around the obstacle and reaches the goal.
The lesson is important:
The path that looks best right now may not be the best path overall.
This idea should sound familiar.
In Reinforcement Learning, we saw:
Immediate reward may not produce the best long-term outcome.
In Optimization, we saw:
A locally attractive solution may not be globally best.
And now Search tells us:
The option that looks closest may still lead us into trouble.
Mathematics has a habit of appearing again wearing a different hat.
A* Search: Cost So Far + Best Guess Ahead
Now we arrive at one of the most famous search algorithms:
A Search*
A* combines two pieces of information.
First:
How much has the journey already cost?
We call this:
Second:
How much do we estimate remains?
We call this:
A* combines them:
where:
g(n) = cost from the start to the current node
h(n) = estimated cost from the current node to the goal
f(n) = estimated total cost of a path through that node
This is a beautiful idea.
A* does not ask only:
“Which option looks closest to the goal?”
It asks:
“Considering what I have already spent and what probably remains, which path looks best overall?”
That is a much more balanced decision.
A Tiny A* Example
Suppose the AI has two candidate routes.
Route A
Cost already travelled:
Estimated remaining cost:
Therefore:
Now consider:
Route B
Cost already travelled:
Estimated remaining cost:
Therefore:
Which route does A* prefer?
Route A.
Why?
Because:
Notice something interesting.
Route B has travelled less so far.
But A* does not care only about the cost already paid.
It also considers what may still lie ahead.
That is the intelligence of the strategy.
Past cost + future estimate.
Can A* Always Find the Best Path?
Under the appropriate conditions, A* can find an optimal path.
One particularly important idea is that our heuristic should not exaggerate the remaining cost.
Such a heuristic is called:
An admissible heuristic.
Conceptually:
In other words:
The heuristic should not pretend the remaining journey is more expensive than it really is.
For graph-search implementations, a stronger property called consistency is also commonly useful.
We do not need the full proof here.
The important intuition is:
A heuristic should guide the search without pretending to know more than it actually knows.
Interestingly, that principle applies to more than search algorithms.
It is not terrible advice for AI systems in general.
Comparing the Search Strategies
We now have four different approaches.
Depth-First Search
Explore deeply.
Backtrack when necessary.
Memory efficient.
Not guaranteed to find a shortest path.
Breadth-First Search
Explore layer by layer.
Finds a shortest path when all moves have equal cost.
May explore many states.
Greedy Best-First Search
Follow what looks closest according to the heuristic.
Often fast.
Can be misled.
A Search*
Balance:
Cost so far plus estimated cost remaining.
With the right heuristic conditions, it can find an optimal path efficiently.
Notice the more interesting question is not:
“Which algorithm is smartest?”
It is:
“What information does each algorithm use when deciding what to explore next?”
That is a much better way to understand AI algorithms.
Search Is Not Just About Mazes
Now remove the maze.
The same fundamental problem appears in many real AI systems.
Navigation
Find a route from one location to another.
Robotics
Choose collision-free movements.
Games
Explore possible moves and countermoves.
Scheduling
Decide the order in which jobs should be completed.
Puzzle Solving
Explore different configurations.
Planning
Choose a sequence of actions that reaches a goal.
AI Agents
Decide what action or tool to use next.
Suddenly our tiny maze is starting to look much more important.
The maze was never really the point.
It simply made the search problem visible.
How AI Agents Use Search
Imagine an AI research agent receives this task:
“Find suitable university programmes for this student.”
The agent may have several possible next actions.
It could:
- Search university websites
- Check programme requirements
- Examine eligibility
- Compare tuition
- Verify application deadlines
- Look for scholarships
- Ask the student for missing information
It cannot investigate every possible path indefinitely.
It needs to choose:
What should I do next?
A simplified agent workflow might look like:
Current State
-> Generate Possible Actions
-> Evaluate the Actions
-> Choose a Promising Action
-> Observe the Result
-> Update the State
-> Repeat
That is a search-and-planning problem.
Instead of maze corridors:
We have actions.
Instead of walls:
We have constraints.
Instead of a physical exit:
We have a goal.
And instead of distance:
We may measure time, cost, uncertainty, usefulness or risk.
What Makes a Good Heuristic?
Suppose we are planning a delivery route.
A useful heuristic might estimate:
Remaining distance.
For scheduling:
Remaining processing time.
For a puzzle:
Number of pieces still misplaced.
For an AI research agent:
Which action is most likely to reduce uncertainty?
A useful heuristic should usually be:
Informative
It should help distinguish promising possibilities from poor ones.
Cheap to compute
If calculating the heuristic takes longer than solving the original problem…
Congratulations.
We have invented a second problem.
Relevant
The heuristic should actually relate to the goal.
An estimate can be mathematically sophisticated and still be completely useless if it measures the wrong thing.
Search, Optimization and Reinforcement Learning
Now we can connect several of the ideas from this blog series.
Optimization asks:
Which solution gives the best objective value?
Reinforcement Learning asks:
Which actions produce the best long-term reward?
Search asks:
Which possibilities should we explore to reach the goal?
These are not identical problems.
But they share a common structure:
Choosing intelligently among alternatives.
That is one reason Mathematics appears repeatedly across Artificial Intelligence.
Different applications.
Different algorithms.
Different terminology.
But underneath them we repeatedly find:
- Choices
- Costs
- Objectives
- Estimates
- Uncertainty
- Decisions
Can Humans Beat AI at the Maze?
Sometimes.
Humans bring something very useful:
- Pattern recognition
- Visual intuition
- Experience
- Prior knowledge
You may look at a maze and immediately ignore an entire region.
Why?
Because something about it simply looks unlikely to help.
That is effectively a heuristic.
You are using knowledge to reduce the search space.
So if you solved the maze before the algorithm:
Congratulations.
You were not cheating.
You were using intelligence.
The Bigger Idea
The most important lesson from search is not:
DFS is good.
BFS is good.
Greedy Search is bad.
A* is brilliant.
The bigger lesson is:
Intelligence often comes from deciding what not to explore.
When the number of possibilities becomes enormous, efficiency matters.
A smart system must somehow decide:
- What looks promising?
- What can probably be ignored?
- How much has this path already cost?
- How much might still remain?
- What information should guide the next decision?
The little maze has now turned into a much bigger question:
How do we make good decisions when there are too many possibilities to examine them all?
That is a question far beyond mazes.
It lies at the heart of many problems in Artificial Intelligence.
The Takeaway
The next time you watch an AI:
- Solve a puzzle
- Plan a route
- Play a game
- Choose a tool
- Decide its next action
remember:
It may not be considering every possible future.
It may be doing something much more useful.
Searching selectively.
Using:
- Structure
- Cost
- Heuristics
- Estimates
- Constraints
And sometimes one beautifully simple equation:
Cost so far.
Plus a useful estimate of what remains.
That is the heart of A*.
And it shows us how mathematics can transform:
“Try everything.”
into:
“Search intelligently.”
Learning with Purpose
At The Learning Studio, I like using puzzles such as mazes because they make abstract ideas visible.
A learner may first see:
and think:
“Another formula.”
But place the formula inside a maze and suddenly:
becomes the road already travelled.
becomes our best estimate of the road ahead.
And:
becomes our estimate of the total journey.
The mathematics now has a purpose.
The learning journey becomes:
Puzzle -> Intuition -> Mathematics -> Algorithm -> Experiment -> Question
Because mathematics becomes far more interesting when we can actually see what the equations are doing.
Coming Next
Can AI Solve a Sudoku Without Trying Every Answer?
Constraint Satisfaction, Backtracking and the Mathematics of Eliminating Possibilities
A Sudoku puzzle contains many empty cells.
At first glance there may appear to be an enormous number of possible combinations.
So does an AI really need to try:
Every possible number?
Fortunately:
No.
Rules eliminate possibilities.
Constraints shrink the search space.
Logic tells us which choices cannot work.
And when a choice leads to a contradiction:
Backtrack.
In the next article, we will explore:
- Constraint Satisfaction Problems
- Backtracking
- Logical elimination
- Search spaces
- Sudoku
And one more beautiful idea from Artificial Intelligence:
Sometimes solving a problem is less about finding the right answer and more about eliminating the impossible ones.