speed and smarts

Is Deep Blue intelligent? The computer was victorious in its 1997 rematch against World Chess Champion Garry Kasparov. Here I consider the value of brute force methods for artificial intelligence as a whole.

By a brute force method, I mean, rather vaguely, a technique that emphasizes calculation over knowledge. Deep Blue includes a lot of chess knowledge, and the knowledge is essential to its performance, but its search tree is huge compared to its knowledge base.

There is no easy way to transplant Deep Blue's power to other domains--it's a chess program, and that's all it is. Nevertheless I'll argue that brute force methods as a class are important, promising, and underappreciated despite their success.

the value of speed

The first rule of brute force is that the more you have of it, the more you can do with it. "If brute force don't work, ya ain't usin' enough of it." In 1975, many chess players thought that chess computers would never reach master strength. In 1985, the barrier was grandmaster strength. In 1995, the barrier was the world champion. Every time, it turned out that faster computers--more brute force--crossed the hurdle.

How broadly are brute force methods applicable? IBM's Deep Blue web site suggests data mining, molecular dynamics and financial analysis as suitable domains for brute-force attack. Many, many other domains are candidates as well; for example, design domains, like VLSI design, often have appropriate problems. Surprising applications exist too: Matt Ginsberg's bridge program GIB relies on a brute force method for card play, although knowledge-based methods had usually been considered necessary.

But new applications are less than half the story. Most combinatorial optimization algorithms are brute force algorithms, with just a dash of smarts. For example, the knowledge embodied in a genetic algorithm consists of a few selection and recombination rules--far less knowledge than Deep Blue relies on. A genetic algorithm is a brute force method (or else Deep Blue's algorithm isn't!). In the same way, dynamic programming algorithms, constraint satisfaction algorithms, and even the simplex algorithm are brute force methods that take a little knowledge a long way.

In the same way that all programs can be seen as a combination of data structures and algorithms, all problem solving can be seen as a combination of search and knowledge. In making a decision, you either know what to do, or else you must consider the options; knowing and searching are the only possibilities. So search is half of all thinking, and it shouldn't be surprising that we can get good results by searching well.

This view can be traced back at least as far as Newell and Simon's General Problem Solver, and it is directly embodied in Soar. It is a weak view, in that by itself it doesn't say anything about what knowledge to use or how to search, but by the same token it is completely general.

Humans think slowly. We don't have any choice but to prefer knowledge over search in our reasoning, because we're too sluggish to search much. Computers don't have that limitation, so for an automated problem solver we should explore the entire range of the search/knowledge tradeoff. In fact, as long as we have difficulty encoding knowledge so that programs can use it--as long as there is a "knowledge acquisition bottleneck"--in practice we should often prefer brute force methods.

the value of smarts

Besides being the fastest chess program, Deep Blue is also thought to be one of the smartest. Because its evaluation function is implemented in custom hardware, Deep Blue can apply evaluation knowledge in parallel. That means it can take advantage of more knowledge in each evaluation without slowing down, whereas a software-only chess program becomes slower when knowledge is added.

Brute force alone solves nothing. The knowledge is essential; to play at world-class level, Deep Blue needs extensive knowledge of what's important in many different types of chess positions. Skill is a rectangle whose dimensions are speed and smarts, and increasing the smarts is as important as increasing the speed. In fact, if you already have the speed then increasing the smarts may be the easiest way to advance.

Many problems are knowledge-intensive and can't be approached at all without lots of knowledge. Natural language understanding is one. The success of expert systems shows that the knowledge-rich, search-poor range of the knowledge/search tradeoff is accessible to machines as well as to humans. An extreme example is Cyc, a large knowledge base created with the hope of duplicating common sense.

the lessons

Search is half of thinking. It may be the easy half, but that's not what counts! When you can, take advantage of the fact that it's the easy half. Keep an eye out for that little bit of knowledge that will make your problem tractable for a brute force method.

If you need knowledge, you should look for ways to be smart quickly. Deep Blue's big lesson is that you can do best if you can apply knowledge efficiently.

references

Cycorp
Web page. Cyc is another ambitious project, started by Douglas Lenat, to create a huge knowledge base of "common sense" information. Cycorp is the company created to commercialize the result.

GIB
Matt Ginsberg
Web page for the bridge program. It uses exhaustive search in a surprising way.

GPS, a program that simulates human thought (1963)
Allen Newell and Herbert A. Simon
From Computers and Thought, edited by E.A. Feigenbaum and J. Feldman, New York: McGraw-Hill.
This is the original source on the General Problem Solver. To my knowledge it is not online anywhere.

Kasparov vs. Deep Blue: The Rematch
The official IBM web site.

Soar
Web page. This is an ambitious project involving many researchers. "Our intention is for Soar to support all the capabilities required of a general intelligent agent."