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.

I was looking at a problem in the early chapters of Artificial Intelligence: A Modern Approach. It’s called Vacuum World. This is a very simple agent problem consisting of a vacuum placed on a grid. The grid has only two squares, each of which is either dirty or clean. The vacuum has three actions: move left, move right, and suck.

I wrote a simple implementation of this in Java (because the course I’m taking uses Java), starting out something like this:

public class Vacuum {
    private GridSquare location;
    public void moveLeft() { ... };
    public void moveRight() { ... };
    public void suck() { ... };
}

Obvious, beginner’s OOP, right? But then I start to second-guess myself. Is location really a property of the vacuum? Or is it a property of the vacuum in its environment? That is, does the location variable belong in the Vacuum class, in the Grid class (the environment), or in some “world” object that encompasses both the vacuum and the grid? Should Vacuum even be allowed to have a reference directly to its location, or should it query the environment indirectly, as in “Is the square I am currently occupying (wherever it may be) dirty?”

The example code on the A.I.M.A. web site seems to go out of its way to be inscrutably OO, with the behavior of the vacuum divided among half a dozen abstract “agent” classes. I think the vacuum there stores its location as an integer, but I couldn’t swear it to you.

This poster hangs in my cubicle. The caption reads, “If a pretty poster and a cute saying are all it takes to motivate you, you probably have a very easy job, the kind robots will be doing soon.”

Besides saying “nyah nyah” to the superiors who never stay in my cubicle long enough to read the caption, I more or less believe what the poster says. My job is very easy. In a few years, a robot will be able to do it.

One of my primary job functions is to be a human interface to technology, so that the important people don’t have to be bothered to learn how to use their computers. With better A.I. — not even strong A.I., just better language handling and learning algorithms — a computer could learn to interpret vague requests and do the right thing. The important people wouldn’t even lose the ability to blame their mistakes on their underlings — they could just blame their computers, and people nowadays are more understanding of computer errors than human error. And with handwriting and voice recognition, no one would ever need a human typist.

The second function of my job is searching for, sorting, and organizing information. Computers are great at that already, and soon software will bridge the gap from today’s web search, e.g. “Seth Greenberg San Francisco lawyer,” to “Find the phone number of the lawyer I talked to at the conference in San Francisco last month.” Pattern recognition systems are already widely used in areas such as finance and medicine. A.I. — again, not strong A.I., just better — will give us general-purpose pattern recognition systems that can be applied to any type of data. Internet research is already very useful, and “search agent” software that can learn to recognize items of interest will be eventually be more thorough than a human researcher. Currently, the public web lacks sufficient accurate information for serious research. The really good sources are locked up in proprietary databases with their own restricted search interfaces. Those interfaces will need to be opened up to third-party search systems — which does not preclude charging for the content in the database itself — to remain competitive in a software agent-driven research market.

The third major function of my job is basically minor physical labor: printing, photocopying, stuffing envelopes, mailing, and generally trasporting physical documents from one location to another. Once we more fully embrace digital communications, this task will dwindle down to nothing. This embrace will depend on a few things: 1) computer displays that are equal or superior to printed text for reading long documents, 2) a legal framework that accepts electronic “signatures” as valid, and 3) a generational change of attitude.

So I will, within a couple of decades, be replaced by a robot. There will not be an android sitting in my cubicle, but a combination of better hardware, smarter software, and cultural changes will leave me with nothing to do. Hopefully by then I’ll be doing something more interesting.

Quiet A.I. I think this will be the way A.I. ultimately sneaks in to everyday life. It’s already happening on the web. But this response on kuro5hin is a fair warning. Choose carefully what you feed your digital “children”!