The Heuristic Wiki

Brute-Force Search

Brute-force search, also known as exhaustive search, is the simplest and crudest of all possible heuristics: it means checking every single point in the function space.

Nearly all thought in heuristic pertains to how to find a solution, an optimum, or a pretty good combination without searching every point in the design space. Thus brute-force search is the null heuristic. It's what you do when you don't know of any heuristic that could simplify the problem. That said, though, brute force always has the last word. However you whittle down your search space, you still must examine one possibility at a time, even in your much-reduced search space.

Using computers, brute-force search is becoming more and more feasible for more kinds of problems. Brute-force search always has the advantage that it requires no imagination or cleverness. There is none of the metaheuristic problem of finding a good heuristic. If you want results fast, and the problem is small enough that brute-force search can find the solution, brute-force search is the way to go.

No matter how fast computers get, though, the vast majority of interesting problems will never submit to brute force. The reason is that in many problems, the number of combinations grows so quickly that even if all the universe's matter were converted into the fastest computers, it would still take more years to find the solution than there are sub-atomic particles in the universe.

For example, brute force cannot figure out optimal play in chess. There are 20 possible opening moves in chess, and approximately that number of possible responses. 20 x 20 x 20 x 20 x ... soon multiplies out to a vaster number than anything that any computer could ever deal with.

But, sometimes you can find a clever way to use brute force on part of a problem. And often that's a huge advance. Ken Thompson, one of the creators of the Unix operating system, used a computer to generate all possible 5-piece endgames in chess. This means that you can play this final fraction of a chess game against a computer and know that you are playing "chess with God."

See Computer Chess Programming.

Version 2 2004-Jul-05 11:42 UTC

Last edit by Ben Kovitz