Search-Based Problem Solving in AI: State Space, Search Trees, Heuristics, A*, Local Search, and Game Search

Cross-posted from Zeromath. Original article: https://zeromathai.com/en/ai-search-based-problem-solving-en/

A lot of AI systems do not “know” one fixed answer in advance.

They solve problems by searching through possibilities.

That idea shows up in route planning, puzzle solving, robotics, optimization, and game-playing agents. The surface details change, but the pattern is often the same: represent the problem as a set of states, define how you can move between them, and then search for a good path or decision.

This is one of the most useful foundations in AI because it connects topics that are often taught separately:

• classical search


• heuristic search


• pathfinding


• optimization


• game-playing AI


• planning


• reinforcement learning

Once you see search as the common pattern, a lot of AI starts to feel less like a bag of unrelated algorithms and more like one connected design space.

Why search matters

Beginners often meet AI through deep learning, LLMs, or generative models. But long before those became dominant, AI was already focused on a core question:

How can an agent move from the current state to a desired goal efficiently?

That question leads to a practical engineering mindset.

Instead of asking only, “What is the answer?”, search-based AI asks:

• What are the valid states?


• What actions move us between states?


• What counts as success?


• What makes one solution better than another?


• How do we avoid exploring everything blindly?

This is why search matters. It turns vague problems into structured ones.

Start with problem formulation

Before choosing BFS, DFS, or A*, the real first step is modeling the problem correctly.

Search only works well when the problem is expressed in a form an algorithm can actually explore. That is usually done with a state space model.

A search problem usually includes these pieces:

State

A state is a snapshot of the world at a given moment.

Examples:

• in a maze: your current position


• in chess: the full board configuration


• in route planning: the city or node you are currently at

Initial state

This is where the search begins.

Actions or operators

These are the legal moves available from a state.

Examples:

• moving a tile in the 8-puzzle


• driving from one road segment to another


• making a move in a board game

Transition model

This defines what happens when you apply an action in a state.

In simple deterministic problems, the next state is predictable.

In more realistic environments, one action may lead to multiple possible outcomes.

Goal test

This checks whether the current state satisfies the objective.

Examples:

• “arrive in Seoul”


• “reach the exit”


• “put all tiles in the correct order”

Path cost

This tells us how expensive a solution is.

That cost might represent:

• number of steps


• distance


• time


• fuel


• energy


• risk

This matters because getting to the goal is often not enough. We want to get there well.

Why formulation matters more than people expect

A poorly formulated problem can make even a good algorithm look bad.

If the state space is too large, search becomes infeasible.

If the goal is vague, the algorithm may solve the wrong thing.

If the cost function is badly designed, you may get technically valid but practically useless solutions.

That is why problem formulation is one of the most underrated skills in AI.

State space vs. search tree

This is one of the easiest ideas to gloss over, and one of the most important to get right.

State space

The state space is the full problem world: all possible states and transitions.

Search tree

The search tree is what the algorithm actually builds while exploring from the start.

• the root is the initial state


• branches represent actions


• child nodes represent successor states

These are not the same thing.

The same state can appear multiple times in a search tree if different action sequences reach it. That is why graph-search methods usually track visited states, while naive tree-search methods may repeat work.

This distinction explains a lot of practical issues:

• duplicate exploration


• loops


• wasted computation


• memory growth

Why search becomes expensive so quickly

Search algorithms expand nodes, and each expansion creates more possibilities.

That sounds manageable at first, but a few factors make search explode fast.

Branching factor

This is the average number of children each node produces.

If each state gives you many choices, the search tree grows very quickly.

Depth

Even with a moderate branching factor, a deep goal can become expensive to find.

Duplicate states

Different paths may lead to the same state. Without tracking, the search may repeat the same work.

Cycles

If the state space contains loops, a naive method may keep revisiting old states forever.

This is why brute force search does not scale well. It also explains why heuristics are such a big deal in AI: they reduce wasted exploration.

Uninformed search: no extra guidance

Uninformed search, or blind search, uses only the problem structure.

It knows:

• the current state


• the available actions


• whether the goal has been reached

It does not know which direction looks more promising.

These algorithms matter because they give us the baseline.

Breadth-First Search (BFS)

BFS explores level by level.

It expands all nodes at depth 1 before depth 2, all of depth 2 before depth 3, and so on.

Good at:

• completeness in finite branching spaces


• shortest paths when all step costs are equal

Weak at:

• memory usage


• wide search trees

A useful intuition: BFS is like checking every room on one floor before moving to the next floor.

Depth-First Search (DFS)

DFS follows one branch as deeply as possible before backtracking.

Good at:

• low memory usage


• finding deep solutions quickly in some cases

Weak at:

• getting stuck down bad branches


• non-optimal solutions


• incompleteness in cyclic or infinite-depth spaces without safeguards

Intuition: DFS is like choosing one hallway and following it to the end before trying another.

Iterative Deepening Search (IDS)

IDS repeatedly runs depth-limited DFS:

• first with depth limit 1


• then 2


• then 3


• and so on

This sounds redundant, but it works surprisingly well.

Why it matters:

• it gets the completeness of BFS


• while keeping much of the memory efficiency of DFS

That makes IDS one of the nicest compromises in classical search.

What uninformed search teaches

The big lesson is simple:

search is expensive when you have no sense of direction.

That naturally leads to heuristics.

Heuristic search: adding direction

In many problems, we do not know the exact distance to the goal.

But we may still have a decent estimate.

That estimate is a heuristic.

A heuristic is a rule of thumb that helps the search focus on more promising states.

Examples:

• straight-line distance in route planning


• number of misplaced tiles in a puzzle


• estimated material advantage in a game position

Formally, we often write this as h(n):

the estimated remaining cost from node n to a goal.

A perfect heuristic is rare.

A useful heuristic is often enough.

Why heuristics matter

Without heuristics, search wastes time on obviously bad branches.

With heuristics, search becomes more goal-directed.

That can be the difference between:

• a problem that is solvable in practice


• and a problem that is theoretically solvable but computationally painful

Greedy Best-First Search

Greedy best-first search always expands the node that looks closest to the goal according to h(n).

That can make it fast.

But it has a weakness: it ignores how much cost has already been spent getting there.

So greedy search can be efficient, but it can also be shortsighted.

A* search: balancing past cost and future estimate

A* is one of the most important search algorithms in AI because it combines two kinds of information:

• 
  g(n): the real cost from the start to node n
  


• 
  h(n): the estimated remaining cost from n to the goal

Its evaluation function is:

f(n) = g(n) + h(n)

This means A* asks a better question than greedy search.

Not just:

“Which node looks closest to the goal?”

But:

“Which path currently looks best overall?”

That balance is what makes A* so useful.

Why A* works so well

Greedy search can overcommit to something that merely looks promising.

A* is more disciplined. It considers:

• how much has already been spent


• how much is likely left

That is why A* shows up so often in:

• pathfinding


• planning


• robotics


• navigation systems

When A* is optimal

A* can return an optimal solution if the heuristic is admissible.

An admissible heuristic never overestimates the true remaining cost.

In simple terms:

• it can be optimistic


• but it cannot be misleading in the wrong direction

A stronger property, consistency, is also important in graph search because it helps avoid messy re-expansions.

A quick intuition

A simple mental model is:

• BFS: explore evenly


• Greedy search: rush toward what looks closest


• A*: choose what looks cheapest overall

That is why A* is often the default “smart search” example in AI courses.

Search performance is always a trade-off

A search algorithm is not judged only by whether it eventually finds a solution.

In AI, we usually evaluate it with four classic criteria:

Completeness

Will it find a solution if one exists?

Optimality

Will it find the best solution according to the path cost?

Time complexity

How much computation does it require?

Space complexity

How much memory does it require?

These criteria matter because every search method trades something off.

• one method may be complete but memory-heavy


• another may be fast but non-optimal


• another may perform well only with a strong heuristic

In practice, search design is about balancing:

• speed


• memory


• solution quality

That trade-off shows up everywhere in AI.

Local search: when the path does not matter

Not every problem is about finding a full start-to-goal path.

Sometimes the real objective is simpler:

find a very good state

That is where local search comes in.

Local search methods usually keep only the current state and move toward better neighboring states. This makes them useful when:

• the state space is huge


• the exact path is unimportant


• the task is optimization

Hill climbing

Hill climbing repeatedly moves to a better neighboring state.

It is simple and often effective, but it has a classic weakness:

it can get stuck at a local optimum.

That is a state that looks best nearby, but is not globally best.

Simulated annealing

Simulated annealing sometimes accepts worse moves temporarily.

That sounds wrong at first, but it helps the search escape local optima and keep exploring.

Local beam search and genetic algorithms

These methods maintain multiple candidate states at once instead of one.

That broader exploration can improve robustness and reduce the chance of getting trapped too early.

A useful ML connection

Local search is not only for discrete problems.

You can also interpret neural network training as a kind of search in a high-dimensional parameter space. Gradient descent is effectively moving through that space to reduce a cost function.

So even modern machine learning can be viewed, in a broad sense, as search.

Adversarial search: when another agent fights back

Some environments are not single-agent problems.

They are competitive.

In those cases, the agent must choose actions while assuming another agent is actively trying to block or exploit it.

That is the domain of adversarial search.

Classic examples:

• chess


• Go


• tic-tac-toe


• many strategy games

Game tree

A game tree expands alternating possibilities:

• your move


• the opponent’s reply


• your next move


• the opponent’s next reply

This makes game search different from ordinary pathfinding.

Minimax

Minimax assumes the opponent plays optimally.

It chooses the move that maximizes your guaranteed outcome under that assumption.

This gives a rational strategy for competitive settings.

Alpha-Beta pruning

Game trees get huge very quickly.

Alpha-beta pruning reduces the amount of search by cutting off branches that cannot affect the final decision.

The nice part is that it preserves the same final result as minimax, just with less work.

Why game search matters

Adversarial search expands the search framework from:

“find a path”

to:

“make the best decision against resistance”

That connects search to:

• game theory


• decision theory


• multi-agent systems


• reinforcement learning

Search in more realistic environments

A lot of classical search assumes the environment is:

• fully observable


• deterministic


• static


• known in advance

Real systems rarely get all of that.

Nondeterministic actions

Sometimes one action can lead to multiple outcomes.

In that case, the agent cannot plan for just one future. It has to handle multiple possible futures.

This leads to structures like AND-OR trees, where some branches are choices and others represent required contingency handling.

Partial observability

Sometimes the agent does not know the exact current state.

Instead, it reasons over a belief state: a set or distribution of possible states consistent with its observations.

That changes the search problem dramatically because now the agent is searching in a space of uncertainty.

Online search

Sometimes the environment is not fully known ahead of time.

Then the agent must interleave:

• acting


• observing


• updating


• replanning

A robot exploring an unfamiliar building is a good example. It cannot compute the full plan first and then execute it. It has to learn while moving.

Why this matters

These cases are important because they connect classical search to more advanced AI topics:

• reinforcement learning


• POMDPs


• robotics


• exploration


• decision-making under uncertainty

Search is one of AI’s unifying ideas

One reason this topic matters so much is that it ties together multiple parts of AI.

In planning, search finds action sequences.

In optimization, search looks for high-quality states.

In games, search evaluates strategic futures.

In robotics, search helps with navigation and action selection.

In machine learning, training can often be interpreted as searching parameter space.

In reinforcement learning, the agent is effectively searching for a policy that maximizes long-term reward.

That is why search-based problem solving is not just one chapter in AI.

It is one of the field’s core ways of thinking.

A simple intuition to keep in mind

A good way to remember the whole topic is this:

AI often solves problems by exploring possibilities under constraints.

Some methods explore broadly.

Some go deep.

Some use heuristics.

Some optimize locally.

Some handle uncertainty.

Some compete against opponents.

But they are all variations of the same core question:

What should we explore, what should we ignore, and what should we pursue next?

That is the heart of search.

Final takeaway

Search-based problem solving gives AI a general framework for turning messy problems into structured decision spaces.

It helps us define:

• what the world looks like


• how actions change it


• what success means


• how to compare alternatives


• how to explore efficiently without brute force

Once you understand the major building blocks:

• problem formulation


• state space


• search tree


• uninformed search


• heuristic search


• A*


• local search


• adversarial search


• search under uncertainty


• performance trade-offs

a lot of AI starts to feel more connected.

That is the real value of this topic. It is not just about memorizing BFS, DFS, and A*.

It is about learning one of AI’s most reusable mental models.

What do you think is the most underrated part of search in AI today?

Is classical search still underappreciated compared with deep learning?

And when you build real systems, do you think better heuristics matter more than better raw compute?