https://www.chessprogramming.org/index.php?title=Brute-Force&feed=atom&action=historyBrute-Force - Revision history2024-03-28T19:28:08ZRevision history for this page on the wikiMediaWiki 1.30.1https://www.chessprogramming.org/index.php?title=Brute-Force&diff=8687&oldid=prevGerdIsenberg at 12:03, 24 November 20182018-11-24T12:03:19Z<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="en">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 12:03, 24 November 2018</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l36" >Line 36:</td>
<td colspan="2" class="diff-lineno">Line 36:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==1980 ...==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==1980 ...==</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Hans Berliner]] ('''1981'''). ''An Examination of Brute Force Intelligence.'' [[Conferences#IJCAI1981|IJCAI 81]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Hans Berliner]] ('''1981'''). ''An Examination of Brute Force Intelligence.'' [[Conferences#IJCAI1981|IJCAI 81]]</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [[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></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [[Richard Korf]] ('''1984'''). ''The Complexity of Brute Force Search''. Technical Report, Department of Computer Science, [[Columbia University]] <ins class="diffchange diffchange-inline"><ref>Paper is mentioned by [[Richard Korf#JudeaPearl|Richard Korf]] at [[Judea Pearl#Symposium|Judea Pearl Symposium]], 2010</ref> </ins><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></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[David Slate]] ('''1984'''). ''Interior-node Score Bounds in a Brute-force Chess Program.'' [[ICGA Journal#7_4|ICCA Journal, Vol. 7, No. 4]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[David Slate]] ('''1984'''). ''Interior-node Score Bounds in a Brute-force Chess Program.'' [[ICGA Journal#7_4|ICCA Journal, Vol. 7, No. 4]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[David Levy]] ('''1986'''). ''When will Brute Force Programs beat Kasparov?'' [[ICGA Journal#9_2|ICCA Journal, Vol. 9, No. 2]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[David Levy]] ('''1986'''). ''When will Brute Force Programs beat Kasparov?'' [[ICGA Journal#9_2|ICCA Journal, Vol. 9, No. 2]]</div></td></tr>
</table>GerdIsenberghttps://www.chessprogramming.org/index.php?title=Brute-Force&diff=1338&oldid=prevGerdIsenberg: 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..."2018-05-02T09:14:12Z<p>Created page with "'''<a href="/Main_Page" title="Main Page">Home</a> * <a href="/Search" title="Search">Search</a> * Brute-Force''' FILE:Bruteforcedvd.jpg|border|right|thumb|link=https://en.wikipedia.org/wiki/Brute_Force_%281947_film%29|Brute Force, 19..."</p>
<p><b>New page</b></p><div>'''[[Main Page|Home]] * [[Search]] * Brute-Force'''<br />
<br />
[[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> ]] <br />
<br />
'''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]]. <br />
<br />
=Search Algorithms= <br />
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.<br />
<br />
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]]. <br />
<br />
=Backtracking= <br />
[[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.<br />
<br />
=See also= <br />
* [[Alpha-Beta]]<br />
* [[Backtracking]]<br />
* [[Brute Force (Program)]]<br />
* [[De Bruijn Sequence Generator]]<br />
* [[Endgame Tablebases]]<br />
* [[Looking for Magics]]<br />
* [[Minimax]]<br />
* [[Saitek Brute Force]]<br />
* [[WCCC 1986#Workshop|Selective Search versus Brute Force - Conference at WCCC 1986]]<br />
* [[Selectivity]]<br />
* [[Type A Strategy|Shannon's Type A Strategy]]<br />
* [[Type B Strategy|Shannon's Type B Strategy]]<br />
* [[Trial and Error]]<br />
<br />
=Publications=<br />
==1949==<br />
* [[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]<br />
==1970 ...==<br />
* [[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]]<br />
* [[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]]<br />
==1980 ...==<br />
* [[Hans Berliner]] ('''1981'''). ''An Examination of Brute Force Intelligence.'' [[Conferences#IJCAI1981|IJCAI 81]]<br />
* [[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><br />
* [[David Slate]] ('''1984'''). ''Interior-node Score Bounds in a Brute-force Chess Program.'' [[ICGA Journal#7_4|ICCA Journal, Vol. 7, No. 4]]<br />
* [[David Levy]] ('''1986'''). ''When will Brute Force Programs beat Kasparov?'' [[ICGA Journal#9_2|ICCA Journal, Vol. 9, No. 2]]<br />
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]<br />
* [[Richard Wheen]] ('''1989'''). ''Brute Force Programming for Solving Double Dummy Bridge Problems''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]]<br />
* [[Donald Michie]] ('''1989'''). ''Brute Force in Chess and Science''. [[ICGA Journal#12_3|ICCA Journal, Vol. 12, No. 3]]<br />
==1990 ...==<br />
* [[Donald Michie]] ('''1990'''). ''Brute Force in Chess and Science''. [[Computers, Chess, and Cognition]]<br />
* [[Alan Frank]] ('''1991'''). ''Brute Force Search in Games of Imperfect Information''. [[2nd Computer Olympiad#Workshop|Heuristic Programming in AI 2]]<br />
* [[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]<br />
* [[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><br />
<br />
=Forum Posts=<br />
* [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]]<br />
* [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<br />
* [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<br />
* [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]]<br />
<br />
=External Links= <br />
* [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<br />
* [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]]<br />
* [https://en.wikipedia.org/wiki/Brute-force_search Brute-force search from Wikipedia]<br />
* [http://en.wiktionary.org/wiki/brute_force brute force - Wiktionary]<br />
* [https://en.wikipedia.org/wiki/Brute_force_attack Brute force attack from Wikipedia]<br />
* [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><br />
* [https://en.wikipedia.org/wiki/Backtracking Backtracking from Wikipedia]<br />
* [https://en.wikipedia.org/wiki/Proof_by_exhaustion Proof by exhaustion from Wikipedia]<br />
* [https://en.wikipedia.org/wiki/Trial_and_error Trial and error from Wikipedia]<br />
<br />
=References= <br />
<references /><br />
<br />
'''[[Search|Up one Level]]'''</div>GerdIsenberg