Home * Search * Brute-Force
Bruteforcedvd.jpg

Brute-Force performs an exhaustive search, which enumerates all possible candidates for the solution to prove whether it satisfies the problem statement. Brute-force algorithms are conceptually simple, but usually suffer from exponential growing search space.
Brute Force, 1947 [1]

Search Algorithms

In 1949, Claude Shannon categorized brute-force minimax search as Type A strategy, which enumerates and minimaxes all leaf positions of a tree with an uniform depth, and concluded a machine operating according to the type A strategy would be both slow and a weak player [2]. Considering the branching factor potentiated by depth, Shannon favored the Type B strategy, a selective approach only searching "important" branches as the most promising.

However, with the advent of brute-force alpha-beta, and programs like Daly CP, Tech, Kaissa and Chess 4.5 in the early 70s, the era of the former dominating Type B programs drew to a close. Today most programs are closer to Type A, but have some characteristics of a Type B due to selectivity.

Backtracking

Backtracking discards large sets of incrementally build candidates to a solution, and "backtracks" a partial candidate as soon as it determines it cannot become member of the solution, for instance as demonstrated by the recursive De Bruijn Sequence Generator. Backtracking algorithms are not considered brute-force.

See also


Publications

1949

1970 ...

1980 ...

1990 ...


Forum Posts


External Links


References

  1. ^ Brute Force (1947 film) from Wikipedia
  2. ^ Claude Shannon (1949). Programming a Computer for Playing Chess. pdf
  3. ^ Quoted by Hans Berliner, Gordon Goetsch (1985). A Study of Search Methods : The Effect of Constraint Satisfaction and Adventurousness, pdf, pdf
  4. ^ University of Helsinki - Department of Computer Science - Annual Report 1999 (pdf)
  5. ^ Chess In The Cinema - Chess scenes from the movie Brute Force (Burt Lancaster)

What links here?


Up one Level