Search in AI and the state space
Many problems can be solved by searching: trying possible steps in an organised way until we reach the goal.
To let a computer search, we describe the problem as a state space:
- State: one situation, for example the robot's square in a maze.
- Initial state: where we start (S).
- Actions: the moves allowed from a state (up, down, left, right).
- Goal test: a check that says "we have arrived" (G).
- Path cost: how much a path costs, for example the number of moves.
States and moves together form a graph or a search tree. A solution is a path from the start to a goal. An optimal solution is the cheapest one.
The search keeps a list of states waiting to be opened, called the frontier. Opening a state means looking at its neighbours and adding new ones to the frontier. Search algorithms differ only in which frontier state they open next.
Blind (uninformed) search: BFS and DFS
Blind or uninformed search only knows the rules of the problem. It has no idea which direction the goal is.
Breadth-first search (BFS)
BFS opens states level by level: all states 1 move away, then all states 2 moves away, and so on. The frontier is a queue (first in, first out).
- Complete: it always finds a solution if one exists.
- Optimal when every move costs the same: the first path found is the shortest.
- Needs a lot of memory, because a whole level is stored at once.
Depth-first search (DFS)
DFS goes deep along one path and backs up (backtracks) only when stuck. The frontier is a stack (last in, first out).
- Uses little memory: it stores only the current path and its side branches.
- Not optimal: the first path found may be long.
- Can get lost in very deep or endless spaces unless we limit the depth.
Other blind methods: uniform-cost search (open the cheapest path so far, used when moves cost different amounts) and iterative deepening (DFS again and again with depth limit 1, 2, 3…).
Informed search: heuristics, greedy search and A*
A heuristic h(n) is a quick, smart guess of how far state n is from the goal. In a grid maze a good heuristic is the Manhattan distance: h = |x − xgoal| + |y − ygoal|. It ignores walls, so it is fast to compute.
- Greedy best-first search always opens the state with the smallest h. It is fast but can be fooled by walls and is not always optimal.
- A* search opens the state with the smallest f = g + h, where g is the real cost from the start so far. It balances "how far I have come" and "how far I guess is left".
If the heuristic is admissible (it never guesses more than the real distance), A* always finds the shortest path. The better (closer to the truth) the heuristic, the fewer states A* opens.
Straight-line distance on a road map and Manhattan distance on a grid are both admissible. A heuristic of 0 turns A* into uniform-cost search.
Problems needing intelligent search: paths, puzzles and games
Paths: route planning on maps, robot motion, network routing. States are places; costs are distance or time. A* is the usual choice.
Puzzles: 8-puzzle, Rubik's cube, Sudoku, the water-jug puzzle. States are puzzle positions. The number of states grows very fast (the combinatorial explosion), so blind search is too slow and heuristics are needed.
Games: in chess or tic-tac-toe two players take turns. A game tree shows my moves, then the opponent's replies. Minimax assumes the opponent plays their best: I choose the move whose worst outcome is the best for me. Alpha–beta pruning skips branches that cannot change the decision. Programs also stop at a fixed depth and use an evaluation function (a heuristic score of the position).
Search by halving: binary search and bisection
Some searches are not on a maze but on a sorted list or a number line. Here a clever rule cuts the work in half each step.
- Binary search: in a sorted list, look at the middle item. If the target is smaller, keep the left half; if larger, the right half. A list of 1,000 items needs at most 10 looks, because 210 = 1024.
- Bisection: to find where a function f(x) crosses zero between a and b (with f(a) and f(b) of opposite signs), test the midpoint and keep the half where the sign changes. Each step halves the error. It also gives square roots: √2 is the root of x² − 2 = 0.
Both are examples of using information about the problem (the list is sorted, the sign changes) to avoid checking everything, the same idea as a heuristic.
Try it
In the 3D: in free play, make a long wall with one gap far from the goal. Predict: will A* still open fewer squares than BFS? Run both and write down "squares opened" and "path length".
At home: draw a 5 × 5 grid on paper, put S and G in corners and shade 5 walls. Number the squares in the order BFS would open them (use a queue written on the side). Then write the Manhattan distance to G in each square and repeat with A*.
Key formulas and definitions
- Problem = initial state + actions + goal test + path cost
- BFS frontier = queue (FIFO); DFS frontier = stack (LIFO)
- Manhattan distance: h = |x − xG| + |y − yG|
- A*: f(n) = g(n) + h(n); open the smallest f first
- Admissible heuristic: h(n) ≤ real cost to goal → A* is optimal
- Binary search on n items: at most ⌈log₂(n + 1)⌉ looks
Worked examples
1. Write the state space for a robot in a 3 × 3 grid that starts at the top-left and must reach the bottom-right, with no walls.
States: the 9 squares (row, column). Initial state: (1,1). Actions: move up, down, left or right if still inside the grid. Goal test: state = (3,3). Path cost: number of moves. The shortest solution has 4 moves, for example right, right, down, down.
2. In a tree, A has children B and C. B has children D and E. C has children F and G. In which order do BFS and DFS open the nodes (children left to right)?
BFS opens level by level: A, B, C, D, E, F, G. DFS goes deep first: A, B, D, E, C, F, G.
3. On a grid, the goal G is at (6, 2). Find the Manhattan heuristic for square (2, 5). If the path cost so far to (2, 5) is g = 3, find f for A*.
h = |2 − 6| + |5 − 2| = 4 + 3 = 7. f = g + h = 3 + 7 = 10.
4. A* has two frontier squares: P with g = 4, h = 5 and Q with g = 6, h = 2. Which is opened first? Which would greedy search open?
A*: f(P) = 9, f(Q) = 8, so Q is opened first. Greedy uses only h: h(Q) = 2 < h(P) = 5, so greedy also opens Q. They can disagree in other cases, e.g. g = 2, h = 5 (f = 7) against g = 8, h = 1 (f = 9): A* picks the first, greedy the second.
5. Use binary search to find 37 in the sorted list 3, 8, 15, 21, 29, 37, 44, 52, 60.
Middle (5th) = 29; 37 > 29 so keep 37, 44, 52, 60. Middle = 44 (take the 2nd of 4); 37 < 44 so keep 37. Found in 3 looks, instead of 6 looks with linear search.
6. In tic-tac-toe it is my turn. Move X leads to positions scored (by the opponent's best replies) +1 and −1; move Y leads to 0 and 0. Which move does minimax choose?
Minimax assumes the opponent picks the worst outcome for me. Worst of X = −1, worst of Y = 0. The best of these is 0, so minimax plays Y (a safe draw instead of risking a loss).
Common mistakes
- Thinking DFS always finds the shortest path. It finds a path, often a long one; BFS (equal costs) or A* (admissible h) find the shortest.
- Mixing up the frontier: BFS uses a queue (first in, first out), DFS uses a stack (last in, first out).
- Using a heuristic that over-guesses and still expecting A* to be optimal. Only an admissible heuristic (never more than the true cost) guarantees the shortest path.
- Forgetting to mark visited states, so the search goes round in circles and repeats work.