25,161
edits
Changes
Created page with "'''Home * Search * Brute-Force''' FILE:Bruteforcedvd.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/Brute_Force_%281947_film%29|Brute Force, 19..."
'''[[Main Page|Home]] * [[Search]] * Brute-Force'''
[[FILE:Bruteforcedvd.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/Brute_Force_%281947_film%29|Brute Force, 1947 <ref>[https://en.wikipedia.org/wiki/Brute_Force_%281947_film%29 Brute Force (1947 film) from Wikipedia]</ref> ]]
'''Brute-Force''' performs an exhaustive search, which enumerates all possible candidates for the solution to prove whether it satisfies the [https://en.wikipedia.org/wiki/Problem_statement problem statement]. Brute-force algorithms are conceptually simple, but usually suffer from exponential growing [[Search Space|search space]].
=Search Algorithms=
In 1949, [[Claude Shannon]] categorized brute-force [[Minimax|minimax search]] as [[Type A Strategy|Type A strategy]], which enumerates and minimaxes all leaf positions of a [[Search Tree|tree]] with an uniform [[Depth|depth]], and concluded a machine operating according to the type A strategy would be both slow and a weak player <ref>[[Claude Shannon]] ('''1949'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf pdf]</ref>. Considering the [[Branching Factor|branching factor]] potentiated by depth, Shannon favored the [[Type B Strategy|Type B strategy]], a selective approach only searching "important" branches as the most promising.
However, with the advent of brute-force [[Alpha-Beta|alpha-beta]], and programs like [[Daly CP]], [[Tech]], [[Kaissa]] and [[Chess (Program)|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|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 [[Recursion|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]]
* [[WCCC 1986#Workshop|Selective Search versus Brute Force - Conference at WCCC 1986]]
* [[Selectivity]]
* [[Type A Strategy|Shannon's Type A Strategy]]
* [[Type B Strategy|Shannon's Type B Strategy]]
* [[Trial and Error]]
=Publications=
==1949==
* [[Claude Shannon]] ('''1949'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf pdf]
==1970 ...==
* [[James Gillogly]] ('''1972'''). ''[http://www.sciencedirect.com/science/article/pii/0004370272900458 The Technology Chess Program]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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.'' [[Conferences#IJCAI1981|IJCAI 81]]
* [[Richard Korf]] ('''1984'''). ''The Complexity of Brute Force Search''. Technical Report, Department of Computer Science, [[Columbia University]] <ref>Quoted by [[Hans Berliner]], [[Gordon Goetsch]] ('''1985'''). ''A Study of Search Methods : The Effect of Constraint Satisfaction and Adventurousness'', [http://dli.iiit.ac.in/ijcai/IJCAI-85-VOL2/PDF/083.pdf pdf], [http://dli.iiit.ac.in/ijcai/IJCAI-85-VOL2/PDF/083.pdf pdf]</ref>
* [[David Slate]] ('''1984'''). ''Interior-node Score Bounds in a Brute-force Chess Program.'' [[ICGA Journal#7_4|ICCA Journal, Vol. 7, No. 4]]
* [[David Levy]] ('''1986'''). ''When will Brute Force Programs beat Kasparov?'' [[ICGA Journal#9_2|ICCA Journal, Vol. 9, No. 2]]
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Richard Wheen]] ('''1989'''). ''Brute Force Programming for Solving Double Dummy Bridge Problems''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]]
* [[Donald Michie]] ('''1989'''). ''Brute Force in Chess and Science''. [[ICGA Journal#12_3|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''. [[2nd Computer Olympiad#Workshop|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. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.4488&rep=rep1&type=pdf pdf]
* [[Miikka Maki-Uuro]] ('''1999'''). ''Limits to the brute force intelligence in computer chess''. Proc. 1999 HeCSE Winter School, (ed. [http://www.cs.tut.fi/~elomaa/ Tapio Elomaa]), Report No. C-1999-1, Department of Computer Science, [[University of Helsinki]] <ref>[http://www.cs.helsinki.fi/research/hallinto/TOIMINTARAPORTIT/1999/CS_Annual_Report_1999.pdf University of Helsinki - Department of Computer Science - Annual Report 1999] (pdf)</ref>
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess/XQWb-ZjSsy0/MiYEhpjTT08J alpha-beta pruning != brute force] by [[Feng-hsiung Hsu]], [[Computer Chess Forums|rgc]], September 22, 1993 » [[Alpha-Beta]]
* [https://www.stmintz.com/ccc/index.php?id=40680 Brute Force vs. Selective Search Re: Fernando & Jim] by Melvin S. Schwartz, [[CCC]], January 24, 1999
* [https://www.stmintz.com/ccc/index.php?id=67695 Brute force base of good game. True or not true?] by [[Leonid Liberman|Leonid]], [[CCC]], September 07, 1999
* [https://www.stmintz.com/ccc/index.php?id=121789 How make Fritz execute brute force search?] by [[Leonid Liberman|Leonid]], [[CCC]], July 26, 2000 » [[Fritz]]
=External Links=
* [http://www.mathematik.uni-bielefeld.de/%7Esillke/NEWS/brute-force Subject: brute-force vs. intuition in math & chess] by [https://en.wikipedia.org/wiki/Macsyma Bill Dubuque], August 1996
* [http://www.computerhistory.org/chess/main.php?sec=thm-42eeabf470432&sel=thm-42f15c52333a3 Middle Game: Computer Chess Comes of Age - Brute Force vs Knowledge] from [[The Computer History Museum]]
* [https://en.wikipedia.org/wiki/Brute-force_search Brute-force search from Wikipedia]
* [http://en.wiktionary.org/wiki/brute_force brute force - Wiktionary]
* [https://en.wikipedia.org/wiki/Brute_force_attack Brute force attack from Wikipedia]
* [https://en.wikipedia.org/wiki/Brute_Force_%281947_film%29 Brute Force (1947 film) from Wikipedia] <ref>[http://www.chess-in-the-cinema.de/showfilm.php?filmfile=4708.txt&pfad=4049 Chess In The Cinema - Chess scenes from the movie Brute Force (Burt Lancaster)]</ref>
* [https://en.wikipedia.org/wiki/Backtracking Backtracking from Wikipedia]
* [https://en.wikipedia.org/wiki/Proof_by_exhaustion Proof by exhaustion from Wikipedia]
* [https://en.wikipedia.org/wiki/Trial_and_error Trial and error from Wikipedia]
=References=
<references />
'''[[Search|Up one Level]]'''
[[FILE:Bruteforcedvd.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/Brute_Force_%281947_film%29|Brute Force, 1947 <ref>[https://en.wikipedia.org/wiki/Brute_Force_%281947_film%29 Brute Force (1947 film) from Wikipedia]</ref> ]]
'''Brute-Force''' performs an exhaustive search, which enumerates all possible candidates for the solution to prove whether it satisfies the [https://en.wikipedia.org/wiki/Problem_statement problem statement]. Brute-force algorithms are conceptually simple, but usually suffer from exponential growing [[Search Space|search space]].
=Search Algorithms=
In 1949, [[Claude Shannon]] categorized brute-force [[Minimax|minimax search]] as [[Type A Strategy|Type A strategy]], which enumerates and minimaxes all leaf positions of a [[Search Tree|tree]] with an uniform [[Depth|depth]], and concluded a machine operating according to the type A strategy would be both slow and a weak player <ref>[[Claude Shannon]] ('''1949'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf pdf]</ref>. Considering the [[Branching Factor|branching factor]] potentiated by depth, Shannon favored the [[Type B Strategy|Type B strategy]], a selective approach only searching "important" branches as the most promising.
However, with the advent of brute-force [[Alpha-Beta|alpha-beta]], and programs like [[Daly CP]], [[Tech]], [[Kaissa]] and [[Chess (Program)|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|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 [[Recursion|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]]
* [[WCCC 1986#Workshop|Selective Search versus Brute Force - Conference at WCCC 1986]]
* [[Selectivity]]
* [[Type A Strategy|Shannon's Type A Strategy]]
* [[Type B Strategy|Shannon's Type B Strategy]]
* [[Trial and Error]]
=Publications=
==1949==
* [[Claude Shannon]] ('''1949'''). ''[http://www.pi.infn.it/%7Ecarosi/chess/shannon.txt Programming a Computer for Playing Chess]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf pdf]
==1970 ...==
* [[James Gillogly]] ('''1972'''). ''[http://www.sciencedirect.com/science/article/pii/0004370272900458 The Technology Chess Program]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 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.'' [[Conferences#IJCAI1981|IJCAI 81]]
* [[Richard Korf]] ('''1984'''). ''The Complexity of Brute Force Search''. Technical Report, Department of Computer Science, [[Columbia University]] <ref>Quoted by [[Hans Berliner]], [[Gordon Goetsch]] ('''1985'''). ''A Study of Search Methods : The Effect of Constraint Satisfaction and Adventurousness'', [http://dli.iiit.ac.in/ijcai/IJCAI-85-VOL2/PDF/083.pdf pdf], [http://dli.iiit.ac.in/ijcai/IJCAI-85-VOL2/PDF/083.pdf pdf]</ref>
* [[David Slate]] ('''1984'''). ''Interior-node Score Bounds in a Brute-force Chess Program.'' [[ICGA Journal#7_4|ICCA Journal, Vol. 7, No. 4]]
* [[David Levy]] ('''1986'''). ''When will Brute Force Programs beat Kasparov?'' [[ICGA Journal#9_2|ICCA Journal, Vol. 9, No. 2]]
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Richard Wheen]] ('''1989'''). ''Brute Force Programming for Solving Double Dummy Bridge Problems''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]]
* [[Donald Michie]] ('''1989'''). ''Brute Force in Chess and Science''. [[ICGA Journal#12_3|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''. [[2nd Computer Olympiad#Workshop|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. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.4488&rep=rep1&type=pdf pdf]
* [[Miikka Maki-Uuro]] ('''1999'''). ''Limits to the brute force intelligence in computer chess''. Proc. 1999 HeCSE Winter School, (ed. [http://www.cs.tut.fi/~elomaa/ Tapio Elomaa]), Report No. C-1999-1, Department of Computer Science, [[University of Helsinki]] <ref>[http://www.cs.helsinki.fi/research/hallinto/TOIMINTARAPORTIT/1999/CS_Annual_Report_1999.pdf University of Helsinki - Department of Computer Science - Annual Report 1999] (pdf)</ref>
=Forum Posts=
* [https://groups.google.com/d/msg/rec.games.chess/XQWb-ZjSsy0/MiYEhpjTT08J alpha-beta pruning != brute force] by [[Feng-hsiung Hsu]], [[Computer Chess Forums|rgc]], September 22, 1993 » [[Alpha-Beta]]
* [https://www.stmintz.com/ccc/index.php?id=40680 Brute Force vs. Selective Search Re: Fernando & Jim] by Melvin S. Schwartz, [[CCC]], January 24, 1999
* [https://www.stmintz.com/ccc/index.php?id=67695 Brute force base of good game. True or not true?] by [[Leonid Liberman|Leonid]], [[CCC]], September 07, 1999
* [https://www.stmintz.com/ccc/index.php?id=121789 How make Fritz execute brute force search?] by [[Leonid Liberman|Leonid]], [[CCC]], July 26, 2000 » [[Fritz]]
=External Links=
* [http://www.mathematik.uni-bielefeld.de/%7Esillke/NEWS/brute-force Subject: brute-force vs. intuition in math & chess] by [https://en.wikipedia.org/wiki/Macsyma Bill Dubuque], August 1996
* [http://www.computerhistory.org/chess/main.php?sec=thm-42eeabf470432&sel=thm-42f15c52333a3 Middle Game: Computer Chess Comes of Age - Brute Force vs Knowledge] from [[The Computer History Museum]]
* [https://en.wikipedia.org/wiki/Brute-force_search Brute-force search from Wikipedia]
* [http://en.wiktionary.org/wiki/brute_force brute force - Wiktionary]
* [https://en.wikipedia.org/wiki/Brute_force_attack Brute force attack from Wikipedia]
* [https://en.wikipedia.org/wiki/Brute_Force_%281947_film%29 Brute Force (1947 film) from Wikipedia] <ref>[http://www.chess-in-the-cinema.de/showfilm.php?filmfile=4708.txt&pfad=4049 Chess In The Cinema - Chess scenes from the movie Brute Force (Burt Lancaster)]</ref>
* [https://en.wikipedia.org/wiki/Backtracking Backtracking from Wikipedia]
* [https://en.wikipedia.org/wiki/Proof_by_exhaustion Proof by exhaustion from Wikipedia]
* [https://en.wikipedia.org/wiki/Trial_and_error Trial and error from Wikipedia]
=References=
<references />
'''[[Search|Up one Level]]'''
