Brute-Force
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.
Contents
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
- Alpha-Beta
- Backtracking
- Brute Force (Program)
- De Bruijn Sequence Generator
- Endgame Tablebases
- Looking for Magics
- Minimax
- Saitek Brute Force
- Selective Search versus Brute Force - Conference at WCCC 1986
- Selectivity
- Shannon's Type A Strategy
- Shannon's Type B Strategy
- Trial and Error
Publications
1949
1970 ...
- James Gillogly (1972). The Technology Chess Program. Artificial Intelligence, Vol. 3, pp. 145-163, reprinted (1988) in Computer Chess Compendium
- David Slate and Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium
1980 ...
- Hans Berliner (1981). An Examination of Brute Force Intelligence. IJCAI 81
- Richard Korf (1984). The Complexity of Brute Force Search. Technical Report, Department of Computer Science, Columbia University [3] [4]
- David Slate (1984). Interior-node Score Bounds in a Brute-force Chess Program. ICCA Journal, Vol. 7, No. 4
- David Levy (1986). When will Brute Force Programs beat Kasparov? ICCA Journal, Vol. 9, No. 2
- Hermann Kaindl, Helmut Horacek, Marcus Wagner (1986). Selective Search versus Brute Force. ICCA Journal, Vol. 9, No. 3
- Richard Wheen (1989). Brute Force Programming for Solving Double Dummy Bridge Problems. Heuristic Programming in AI 1
- Donald Michie (1989). Brute Force in Chess and Science. ICCA Journal, Vol. 12, No. 3
1990 ...
- Donald Michie (1990). Brute Force in Chess and Science. Computers, Chess, and Cognition
- Alan Frank (1991). Brute Force Search in Games of Imperfect Information. Heuristic Programming in AI 2
- Jonathan Schaeffer, Paul Lu, Duane Szafron, Rob Lake (1993). A Re-examination of Brute-force Search. Intelligent Games: Planning and Learning. (AAAI 1993 Report FS9302, Proccedings of the AAAI Fall Symposiuem, eds. S. Epstein and R. Levinson), pp. 51-58, AAAI Press, Menol Park, CA. ISBN 0-929-28051-2. pdf
- Miikka Maki-Uuro (1999). Limits to the brute force intelligence in computer chess. Proc. 1999 HeCSE Winter School, (ed. Tapio Elomaa), Report No. C-1999-1, Department of Computer Science, University of Helsinki [5]
Forum Posts
- alpha-beta pruning != brute force by Feng-hsiung Hsu, rgc, September 22, 1993 » Alpha-Beta
- Brute Force vs. Selective Search Re: Fernando & Jim by Melvin S. Schwartz, CCC, January 24, 1999
- Brute force base of good game. True or not true? by Leonid, CCC, September 07, 1999
- How make Fritz execute brute force search? by Leonid, CCC, July 26, 2000 » Fritz
External Links
- Subject: brute-force vs. intuition in math & chess by Bill Dubuque, August 1996
- Middle Game: Computer Chess Comes of Age - Brute Force vs Knowledge from The Computer History Museum
- Brute-force search from Wikipedia
- brute force - Wiktionary
- Brute force attack from Wikipedia
- Brute Force (1947 film) from Wikipedia [6]
- Backtracking from Wikipedia
- Proof by exhaustion from Wikipedia
- Trial and error from Wikipedia
References
- ↑ Brute Force (1947 film) from Wikipedia
- ↑ Claude Shannon (1949). Programming a Computer for Playing Chess. pdf
- ↑ Paper is mentioned by Richard Korf at Judea Pearl Symposium, 2010
- ↑ Quoted by Hans Berliner, Gordon Goetsch (1985). A Study of Search Methods : The Effect of Constraint Satisfaction and Adventurousness, pdf, pdf
- ↑ University of Helsinki - Department of Computer Science - Annual Report 1999 (pdf)
- ↑ Chess In The Cinema - Chess scenes from the movie Brute Force (Burt Lancaster)
