Search Algorithms

Search is one of the most fundamental concepts in artificial intelligence. Before machine learning rose to prominence, AI research treated search as its central problem. Early systems such as Newell and Simon’s General Problem Solver (1957) framed reasoning itself as search: to solve a problem, you define the states you can be in, the actions that move between them, and a goal test, then explore the resulting space until you reach a goal. This idea still drives planning, theorem proving, route finding, and game playing today. In this chapter we explore how to implement classic search algorithms in Scala 3, taking advantage of its elegant functional features and clean syntax.

We will build three examples:

1. Graph Search: Implementing Depth-First Search (DFS) and Breadth-First Search (BFS) over a graph of cities.
2. Maze Solving: Generating a random maze using depth-first carving and solving it with BFS to guarantee the shortest path.
3. Game Tree Search: Implementing the Minimax algorithm with alpha-beta pruning to play an optimal game of Tic-Tac-Toe.

All code is in the directory source-code/search.

The three examples in this chapter look different on the surface, but they share one structure. We can state any of them with five parts:

• A state space: the set of all configurations the world can take. For the city to city route planning graph a state is a graph where the nodes are city names, for the maze it is a grid cell, and for Tic-Tac-Toe it is a board position.
• An initial state: where the search begins.
• A successor function: given a state, it returns the states reachable in one step. In our code this is neighbors, openNeighbors, or emptyCells.
• A goal test: a predicate that tells us when we have finished.
• A path cost: a number we may want to minimize, such as the count of edges on the path.

A search algorithm grows two sets as it runs. The frontier holds states we have generated but not yet expanded. The explored set (the visited set in our code) holds states we have already expanded, so we never process one twice. The algorithms in this chapter differ in just one way: how they pick the next state from the frontier. That single choice fixes both their behavior and their cost.

We judge a search algorithm on four properties:

• Completeness: does it always find a solution when one exists?
• Optimality: does it find the lowest-cost solution?
• Time complexity: how many states does it generate?
• Space complexity: how many states does it hold in memory at once?

We write for the branching factor (the average number of successors per state) and for the depth of the shallowest goal. These two numbers drive the cost of every algorithm below.

To search a graph, we first need to represent it. We define a simple immutable representation in search/Graph.scala using Scala 3 case classes. A node contains a name and coordinates, and the graph itself tracks a vector of nodes and undirected edge pairs:

This is an edge list representation. We store nodes in a Vector, which gives effectively constant-time indexed access, and we refer to each node by its integer index rather than by name. Integer indices are cheap to compare, cheap to store in a Set, and let us key the visited set on a primitive rather than on a string.

The neighbors method scans the whole edge list on each call, so it costs time for edges. For the small graphs in this chapter that cost does not matter. For a large graph you would instead precompute an adjacency list, a Map[Int, List[Int]] that answers neighbors in O(1) time at the cost of memory. The edge list keeps the example short and makes the undirected nature of the graph explicit: a single pair (a, b) yields b as a neighbor of a and a as a neighbor of b, which is exactly what the two case clauses in the collect express.

We also include a distance method that returns the straight-line (Euclidean) distance between two nodes. Uninformed searches like DFS and BFS ignore it, but an informed search such as A* would use it as a heuristic: an estimate of the remaining cost to the goal that guides the search toward promising nodes first.

DFS and BFS are the two basic uninformed (or “blind”) search strategies. Neither uses any knowledge of where the goal lies, so both differ only in the order they pull states off the frontier. DFS treats the frontier as a stack and always expands the deepest unexpanded state. BFS treats the frontier as a queue and always expands the shallowest. That one difference produces sharply different guarantees:

Here is the maximum depth of the state space, which can be much larger than (the depth searched before finding the goal node). The table shows the core trade-off. BFS keeps a whole layer of the frontier in memory, so its space cost grows exponentially with depth, but it never overlooks a shallow goal. DFS holds only the current path plus its siblings, so its memory cost is linear, but it can plunge down a deep or infinite branch and miss a nearby solution.

Both of our implementations track a visited set. On a general graph with cycles this set is what keeps the searches complete: without it, DFS could loop forever around a cycle. Tracking visited states bounds both searches at time and space, since each node is expanded at most once and each edge examined at most twice. We trade memory for the guarantee that we never revisit a state.

We implement both searches in a purely functional manner in search/GraphSearch.scala. Each returns an Option[List[Int]] holding the path of node indices from start to goal, or None if no path exists.

DFS uses recursive backtracking. It explores as deep as possible along each branch before backing up, and it carries the visited set forward so it never re-enters a node already on the current search:

The recursion carries the base case cleanly: if node is the goal, we return a one-element path. Otherwise we filter out visited neighbors and search each in turn. The key detail is .view. It turns the flatMap into a lazy computation, so headOption forces only as many recursive searches as it needs to find the first branch that reaches the goal. The moment one branch succeeds, the remaining neighbors are never explored. This is the functional equivalent of an early return inside a loop, and it keeps DFS from doing needless work after it finds a path. Each successful frame then prepends its own node with node :: _, so the path is rebuilt in the correct start-to-goal order as the recursion unwinds.

Breadth First Search (BFS) explores all neighbors at the current depth before moving deeper. We implement it with a queue of partial paths. Because it always expands the shallowest node first, the first time it reaches the goal it has done so by a path with the fewest possible edges. This is why BFS is optimal for unweighted graphs: every path of length is fully explored before any path of length begins, so no shorter path to the goal can remain undiscovered:

Two implementation choices deserve attention. First, the @annotation.tailrec annotation asks the compiler to verify that search is tail recursive. Because the recursive call is the last action in the function, the compiler rewrites it into a plain loop, so BFS runs in constant stack space no matter how large the graph. Second, we add nodes to the visited set the moment we enqueue them (newVisited = visited ++ nextNodes), not when we later dequeue them. This matters: if two different frontier nodes both border the same unvisited node, marking on enqueue stops that node from entering the queue twice. Without it the queue could hold many copies of the same state, which wastes memory and can break the shortest-path reasoning. We build each partial path by prepending (n :: path), which is a constant-time operation on an immutable list, then reverse once at the end when we return the finished path.

We run all the search examples with one test program. Here we only show the output for the Depth First Search (DFS) and Breadth First Search (BFS) city route planing example:

Solving mazes is another classic search benchmark. We represent a maze as a 2D grid of booleans where true is a wall and false is an open passage. We generate a random maze using a DFS-based recursive backtracking algorithm (carving paths through walls) in search/Maze.scala:

The generator is worth understanding, because it explains why BFS behaves the way it does on the result. The recursive backtracker starts with every cell walled off, then carves a path. It marks the current cell open, shuffles the four directions, and for each direction steps two cells away. If that far cell is still a wall (still unvisited), it knocks out the wall between the two cells and recurses into the far cell.

Notice in the first block that DFS and BFS return different paths from Atlanta to Erie: DFS follows the first branch it happens to descend (through Denver and Chicago), while BFS finds the shorter two-edge route through Chicago, exactly as the optimality guarantee predicts:

Cells sit on odd coordinates and the wall between two cells sits at the midpoint, which is why the steps are of size two and the wall is knocked out at r + dr / 2. Because the algorithm only ever carves into a cell that no path has reached yet, it can never create a loop, and because it visits every reachable cell, it leaves no region walled off. The result is a perfect maze: a spanning tree over the grid of cells with exactly one simple path between any two cells and no cycles.

That property has a direct consequence for solving. On a perfect maze the path between start and goal is unique, so any complete search finds it. BFS still earns its keep, because the moment you add loops (a “braided” maze with more than one route) BFS returns the shortest route while DFS returns the first one it stumbles into, which may wander. We solve the maze with either MazeSearch.depthFirst or MazeSearch.breadthFirst. The BFS solver uses the exact same queue-based strategy shown for graphs, so it carries the same shortest-path guarantee:

The only change from the graph version is that the state is a Location (a row and column) instead of an integer index, and the successor function is openNeighbors instead of neighbors. The maze is a graph whose nodes are open cells and whose edges connect adjacent open cells, so the same algorithm applies without change. This reuse is the payoff of the formal framing at the start of the chapter: once you can express a problem as states, successors, and a goal test, the search code carries over untouched.

We run all the search examples with one test program. Here we only show the output for the maze search example:

Game playing requires looking ahead to predict opponent moves. Where DFS and BFS search a space of states we pass through, a game search explores a game tree in which the players alternate turns. Each level of the tree is one ply (one move by one player). The nodes on our levels belong to the player to move, and the nodes on the opponent’s levels belong to the opponent.

Tic-Tac-Toe is a two-player, zero-sum, perfect-information game: whatever is good for one player is exactly as bad for the other, and both players see the full board. For such games John von Neumann’s minimax theorem (1928) guarantees that a well-defined optimal value exists for every position, the score each player can force if both play perfectly. (Dear reader, some personal history: my father knew and worked with John van Neumann at the Institutue for Advanced Study in Princeton. My father said that von Neuman would work late into the night (like some modern programmers!) and he liked to play German classic music loudly in his office.) The Minimax algorithm computes that value directly. On our turn (the maximizing player) we pick the move with the highest score. On the opponent’s turn (the minimizing player) we assume they pick the move with the lowest score for us. Applied recursively down to terminal positions, this yields the strongest move we can make against an opponent who never errs.

We define the game state in search/TicTacToe.scala:

Terminal positions need a numeric value, and the exact scoring encodes the behavior we want. A win scores 10 - depth and a loss scores depth - 10, where depth is how many plies deep the search had to look:

The depth term is not cosmetic. Subtracting it from a win means a win found in fewer moves scores higher than the same win found later, so the engine prefers to win quickly rather than dawdle. Adding it to a loss means a loss delayed by more moves is less bad, so a losing engine puts up the longest possible fight instead of giving up at once. Without the depth term the engine would still play perfectly in outcome, but it might toy with a doomed opponent instead of finishing, or resign into a fast loss.

The full game tree for Tic-Tac-Toe is small enough to search exhaustively. From the empty board there are at most move sequences, and in practice far fewer once you stop at terminal positions. General game search is not so lucky: the count of leaves grows as , which for chess (branching factor near 35) is astronomical even at modest depth. That growth is what motivates the pruning we add next.

Alpha-beta pruning searches the same game tree as plain minimax and returns the exact same move, but it skips branches that provably cannot change the result. We carry two bounds down the recursion. alpha is the best score the maximizing player can already guarantee somewhere higher in the tree. beta is the best score the minimizing player can already guarantee. The instant alpha >= beta, the current node is worse for one player than an option they have already secured elsewhere, so no move here can influence the final choice and we stop searching this node.

We use Scala 3’s scala.util.boundary and break utilities to exit the loop cleanly the moment a cutoff fires:

The maximizing branch raises its local alpha (a) as it finds stronger moves and breaks as soon as that value meets beta, since the minimizing player above would never allow the search to reach this node. The minimizing branch mirrors it, lowering beta (b2) and breaking against alpha. The boundary block gives us a safe non-local exit: break(best) jumps straight out of the for loop with the current best value, which reads more clearly than a mutable flag and a guarded loop.

Pruning does not change correctness, only speed, and how much speed depends on move ordering. With adversarial (worst-case) ordering, alpha-beta examines the same nodes as plain minimax and saves nothing. With perfect ordering, where the best move is tried first at every node, it examines only about nodes. That square-root reduction effectively doubles the depth you can search in the same time, which is why strong game engines invest heavily in trying likely-best moves first. We return to exactly this idea, with real move-ordering heuristics, in the chess engine chapter.

We run all the search examples with one test program. Here we only show the output for the maze search example:

The Tic-Tac-Toe result is the practical face of the minimax theorem. Two optimal players of a solved game can never beat each other, so a game between two copies of our engine always ends in a draw. The same search, given a game the opponent misplays, would convert every mistake into a win.

We have already seen example output for the three examples. Now we look at the test harness code. The entry point in search/Main.scala coordinates all three search demos. First, it searches a small city graph:

We already looked at the code to set up the maze and tic-tac-toe examples.

Running the project via scala-cli run . produces outputs we saw previously showing the DFS and BFS paths, the solved maze grid (drawing a path using .), and a complete optimal Tic-Tac-Toe game where two computers play each other to a draw.