Search & Planning10 min read

State Space Search

Exploring every possible move to find the goal
scope:Core Conceptdifficulty:Beginner

Lost in a Maze

Imagine you're standing at the entrance of a giant maze. You can see corridors branching off in every direction, but you have no map. Your goal? Find the exit.

You have two strategies:

  • Strategy 1 (BFS): Check every corridor one step away. Then every corridor two steps away. Then three. You spread out like a wave, exploring level by level.
  • Strategy 2 (DFS): Pick one corridor and walk all the way to the end. Hit a dead end? Backtrack and try the next one. You dive deep before going wide.

This is exactly how AI solves problems. The maze is a state space — every position you could be in is a state, every step you take is a transition, and the exit is the goal state.

What is a State Space?

A state space is just a fancy way of saying "all possible configurations of a problem." Think of a Rubik's Cube — every possible arrangement of colored squares is a state. Every twist is a transition. The solved cube is the goal state.

The state space for a Rubik's Cube has 43 quintillion states. You can't check them all. That's why search strategy matters.

BFS: The Cautious Explorer

Breadth-First Search (BFS) explores all neighbors before moving deeper. Think of dropping a stone in water — the ripples spread outward evenly.

BFS is guaranteed to find the shortest path (if one exists), because it checks all paths of length 1 before length 2, length 2 before length 3, and so on. The downside? It uses a lot of memory, because it has to remember every state at the current level.

DFS: The Bold Adventurer

Depth-First Search (DFS) dives as deep as possible before backtracking. It's like reading a choose-your-own-adventure book by always picking the first option until you reach an ending, then going back to try the next option.

DFS uses much less memory (it only needs to remember the current path), but it doesn't guarantee the shortest path. It might find a long, winding route to the goal even when a shortcut exists.

BFS and DFS in Action

from collections import deque


def bfs(graph, start, goal):
    """Breadth-First Search — explore level by level."""
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None


def dfs(graph, start, goal):
    """Depth-First Search — dive deep first."""
    stack = [(start, [start])]
    visited = {start}
    
    while stack:
        node, path = stack.pop()
        if node == goal:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append((neighbor, path + [neighbor]))
    return None


# A simple maze as a graph
maze = {
    'Start': ['A', 'B'],
    'A': ['C', 'D'],
    'B': ['E'],
    'C': [],
    'D': ['Goal'],
    'E': ['Goal'],
    'Goal': []
}


print("BFS path:", bfs(maze, 'Start', 'Goal'))
print("DFS path:", dfs(maze, 'Start', 'Goal'))
Output
BFS path: ['Start', 'B', 'E', 'Goal']
DFS path: ['Start', 'B', 'E', 'Goal']
Note: BFS vs DFS trade-off: BFS guarantees the shortest path but eats memory like a buffet. DFS is memory-friendly but might wander down a rabbit hole. In practice, many AI systems use a hybrid called Iterative Deepening DFS — it runs DFS with increasing depth limits, getting the best of both worlds.

Real-World State Spaces

State space search isn't just for mazes. It's everywhere in AI:

  • GPS navigation — each intersection is a state, each road is a transition, your destination is the goal.
  • Game AI — each board position is a state, each legal move is a transition, checkmate is the goal.
  • Robot planning — each configuration of the robot's joints is a state, each motor command is a transition.
  • Puzzle solvers — sliding puzzles, Sudoku, and the Rubik's Cube are all state space problems.

The challenge is always the same: the state space is enormous, and you need a clever strategy to find the goal without exploring everything.

Quick check

What does BFS guarantee that DFS does not?
Challenge

Continue reading