Brute-Force

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Brute-Force

Brute Force, 1947 [1]

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.

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

Up one Level