Breadth-first and Depth-first Searching

I’m playing some more with the early chapters of Artificial Intelligence: A Modern Approach, looking at basic tree search techniques for the 8-puzzle. I wrote simple breadth-first and depth-first search algorithms for this puzzle in Common Lisp. Here’s the code. It’s an interesting demonstation of how inefficient these alogrithms really are.

I represent the puzzle as a simple list of integers numbered 0 through 7, with the symbol B representing the “hole.” The “winning” position is (0 1 2 3 4 5 6 7 B). I also added a little code to have the algorithm track the number of iterations; how many “nodes,” or board positions, it has to expand in the search tree; and the maximum number of positions it has to keep stored in memory.

Just to test that I’ve coded it right, I make sure the algorithm does nothing when given a solved puzzle to start with:

CL-USER> (breadth-first-search '(0 1 2 3 4 5 6 7 B))
"Found (0 1 2 3 4 5 6 7 B) in 0 steps.
Expanded 0 nodes, stored a maximum of 0 nodes."

Next, I try it on a puzzle that is just one move away from a solution:

CL-USER> (breadth-first-search '(0 1 2 3 4 5 6 b 7))
"Found (0 1 2 3 4 5 6 7 B) in 3 steps.
Expanded 9 nodes, stored a maximum of 5 nodes."

All well and good. Now lets try shuffling the pieces a bit more:

CL-USER> (breadth-first-search '(0 1 2 b 3 6 4 5 7))
"Found (0 1 2 3 4 5 6 7 B) in 18327 steps.
Expanded 49075 nodes, stored a maximum of 8422 nodes."

Ouch. That’s kind of slow. And that wasn’t even the hardest possible starting arrangement. So much for that.

Let’s see how depth-first search does on the one-move-away puzzle:

CL-USER> (depth-first-search '(0 1 2 3 4 5 6 b 7))

Dum de dum dum. Tick tock.

Half an hour later, I get bored and interrupt it. Obviously depth-first search is not a very good algorithm for solving the 8-puzzle. I’ll have to wait for the next chapter, which introduces A* and other informed searches.

It’s funny to me, because both of these algorithms seem like reasonable ways of searching a tree of possibilities. I guess it’s hard for my mind to grasp just how overwhelmingly large exponential growth really is.