25,161
edits
Changes
no edit summary
They usually have huge memory requirements, since they keep an exponentially growing search space in memory.
* [[B*]] as used by [[Hans Berliner|Hans Berliner's]] chess-program [[HiTech]]
* [[Best-First Minimax Search]]
* [[Conspiracy Number Search]]
* [[MCαβ]]
=Parallel Search=
* [[Parallel Search]]
* [[Conspiracy Number Search#PCCNS|Parallel Controlled Conspiracy Number Search]] as used by [[Ulf Lorenz|Ulf Lorenz's]] program [[P.ConNerS]]
=Using Time=
=Publications=
==1960 ...==
* [[Daniel Edwards]], [[Timothy Hart]] ('''1961'''). ''The Alpha-Beta Heuristic'', AIM-030, reprint available from [http://dspace.mit.edu/handle/1721.1/6098 DSpace] at [[Massachusetts Institute of Technology|MIT]]. Retrieved on 2006-12-21.
* [[Alexander Brudno]] ('''1963'''). ''Bounds and valuations for shortening the search of estimates''. Problemy Kibernetiki (10) 141–150 and Problems of Cybernetics (10) 225–241
* [[James R. Slagle]] ('''1963'''). ''Game Trees, M & N Minimaxing, and the M & N alpha-beta procedure.'' Artificial Intelligence Group Report 3, UCRL-4671, University of California
* [[Jim Doran]], [[Donald Michie]] ('''1966'''). ''[https://royalsocietypublishing.org/doi/10.1098/rspa.1966.0205 Experiments with the Graph Traverser Program]''. [https://en.wikipedia.org/wiki/Proceedings_of_the_Royal_Society Proceedings of the Royal Society], Series A, Vol. 294, No. 1437, [https://stacks.stanford.edu/file/druid:yf330xx7624/yf330xx7624.pdf pdf]
* [[James R. Slagle]], [[Philip Bursky]] ('''1968'''). ''[http://portal.acm.org/citation.cfm?id=321444 Experiments With a Multipurpose, Theorem-Proving Heuristic Program]''. [[ACM#Journal|Journal of the ACM]], Vol. 15, No. 1
* [[James R. Slagle]], [[John K. Dixon]] ('''1969'''). ''[http://portal.acm.org/citation.cfm?id=321510.321511 Experiments With Some Programs That Search Game Trees]''. [[ACM#Journal|Journal of the ACM]], Vol. 16, No. 2, [http://wiki.cs.pdx.edu/cs542-spring2011/nfp/abmin.pdf pdf], [http://wiki.cs.pdx.edu/wurzburg2009/nfp/abmin.pdf pdf]
* [[Larry Harris]] ('''1973'''). ''The bandwidth heuristic search''. [http://dblp.uni-trier.de/db/conf/ijcai/ijcai73.html 3. IJCAI 1973], [http://www.ijcai.org/Past%20Proceedings/IJCAI-73/PDF/004.pdf pdf]
* [[Gerhard Wolf]] ('''1973'''). ''[http://dl.acm.org/citation.cfm?id=805704 Implementation of a dynamic tree searching algorithm in a chess programme]''. [http://dl.acm.org/citation.cfm?id=800192&picked=prox Proceedings of the ACM annual conference]
* [[Larry Harris]] ('''1974'''). ''Heuristic Search under Conditions of Error''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 5, No. 3, pp. 217-234. ISSN 0004-3702. Also also published ('''1977''') under the title: ''The heuristic search: An alternative to the alpha-beta minimax procedure.'' [[Chess Skill in Man and Machine]] (ed. [[Peter W. Frey]]), pp. 157-166* [[Larry Harris]] ('''1975''') ''The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play''. [http://dblp.uni-trier.de/db/conf/ijcai/ijcai75.html 4. IJCAI 1975], 334-339. reprinted in [[Computer Chess Compendium]] by * [[David LevyToshihide Ibaraki]] (Editor'''1978'''). ''[https://link.springer.com/article/10.1007/BF00991818 Depth-m search in branch-and-bound algorithms]''. [https://link.springer.com/journal/10766 International Journal of Parallel Programming], Vol. 7, ppNo. 136 - 1424* [[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Mikhail Donskoy]] ('''1979'''). ''Algorithms of adaptive search''. [http://www.doc.ic.ac.uk/~shm/MI/mi9.html Machine Intelligence 9] (eds. [[Jean Hayes Michie]], [[Donald Michie]] and L.I. Mikulich), pp. 373-384. Ellis Horwood, Chichester.* [[George Stockman]] ('''1979'''). ''A Minimax Algorithm Better than Alpha-Beta?'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 12, No. 2* [[John Gaschnig]] ('''1979'''). ''[https://dl.acm.org/citation.cfm?id=909244 Performance Measurement and Analysis of Certain Search Algorithms]''. Ph.D. thesis, pp[[Carnegie Mellon University]], [http://reports-archive. 179adm.cs.cmu.edu/anon/scan/CMU-CS-196. ISSN 000479-3702124.pdf pdf]
==1980 ...==
* [[Judea Pearl]] ('''1981'''). ''Heuristic search theory: A survey of recent results''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai81.html IJCAI-81], [http://ijcai.org/Past%20Proceedings/IJCAI-81-VOL%201/PDF/100.pdf pdf]
* [[Judea Pearl]] ('''1982'''). ''[http://portal.acm.org/citation.cfm?id=358616&dl=ACM&coll=DL&CFID=27355608&CFTOKEN=40935826 The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality]''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8
* [[Murray Campbell]], [[Tony Marsland]] ('''1983'''). ''A Comparison of Minimax Tree Search Algorithms''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 20, No. 4, pp. 347-367. ISSN 0004-3702, [http://webdocs.cs.ualberta.ca/~tony/OldPapers/TR82-3.pdf pdf]
* [[Andrew L. Reibman]], [[Bruce W. Ballard]] ('''1983'''). ''[http://www.aaai.org/Library/AAAI/1983/aaai83-084.php Non-Minimax Search Strategies for Use against Fallible Opponents]''. Proceedings of [[AAAI]] 83
* [[Nanda Srimani]] ('''1985'''). ''A New Algorithm (PS*) for Searching Game Trees''. Master's thesis, [[University of Alberta]]
* [[Toshihide Ibaraki]] ('''1986'''). ''Generalization of Alpha-Beta and SSS* Search Procedures.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 29, pp. 73-117. ISSN 0004-3702.
* [[Tony Marsland]], [[Nanda Srimani]] ('''1986'''). ''Phased State Search''. [http://www.informatik.uni-trier.de/~ley/db/conf/fjcc/fjcc86.html#MarslandS86 Fall Joint Computer Conference], [http://webdocs.cs.ualberta.ca/~tony/OldPapers/fjcc.1986.pdf pdf]
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Ronald L. Rivest]] ('''1987'''). ''Game Tree Searching by Min/Max Approximation''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence ], Vol. 34, No. 1, [http://people.csail.mit.edu/rivest/Rivest-GameTreeSearchingByMinMaxApproximation.pdf pdf 1995]* [[Bruce Abramson]] ('''1989'''). ''Control Strategies for Two-Player Games.'' ACM Computing Surveys , Vol. 21(, No. 2): 137-161, [http://www.theinformationist.com/pdf/constrat.pdf/ pdf]
* [[Stuart Russell]], [[Eric Wefald]] ('''1989'''). ''[http://portal.acm.org/citation.cfm?id=1623807 On optimal game-tree search using rational metareasoning].'' In Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, Detroit, MI: Morgan Kaufmann, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79.9229&rep=rep1&type=pdf pdf]
* [[Liwu Li]] ('''1989'''). ''[https://doi.org/10.7939/R3VX06F26 Probabilistic Analysis of Search]''. Ph.D. thesis, [[University of Alberta]], advisor [[Tony Marsland]]
* [[Wolfgang Nagl]] ('''1989'''). ''Best-Move Proving: A Fast Game Tree Searching Program''. [[1st Computer Olympiad#Workshop|Heuristic Programming in AI 1]]
==1990 ...==
* [[Toshihide Ibaraki]], [[Naoki Katoh]] ('''1990'''). ''[https://link.springer.com/article/10.1007/BF01531075 Searching Minimax Game Trees Under Memory Space Constraint]''. [https://link.springer.com/journal/10472 Annals of Mathematics and Artificial Intelligence], Vol. 1, Nos. 1-4
* [[Victor Allis]], [[Maarten van der Meulen]], [[Jaap van den Herik]] ('''1991'''). ''Proof-Number Search.'' Technical Reports in Computer Science, CS 91-01. Department of Computer Science, [[Maastricht University|University of Limburg]]
* [[Tony Marsland]] ('''1992'''). ''Computer Chess and Search.'' Encyclopedia of Artificial Intelligence (2nd ed.) (ed. S.C. Shapiro) John Wiley & Sons, Inc. [http://webdocs.cs.ualberta.ca/~tony/RecentPapers/encyc.mac-1991.pdf pdf] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7df61a100528f201 Excellent Computer-Chess Overview Paper Found!] by [[Ernst A. Heinz]], [[Computer Chess Forums|rgcc]], March 6, 1997</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=221364 Great article for people who wants to write a chess engine] by [[Miguel A. Ballicora]], [[CCC]], April 03, 2002</ref>
* [[Thomas Lincke]] ('''2002'''). ''Exploring the Computational Limits of Large Exhaustive Search Problems''. Ph.D thesis, [[ETH Zurich]], [http://e-collection.library.ethz.ch/eserv/eth:25905/eth-25905-02.pdf pdf] » [[Awari]], [[Repetitions]] <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=2093#p17469 Re: Aquarium IDEA, repetitions, and minimax over cycles] by [[Ronald de Man|syzygy]], [[Computer Chess Forums|OpenChess Forum]], September 22, 2012</ref>
* [[Steven Walczak]] ('''2003'''). ''[http://portal.acm.org/citation.cfm?id=776752.776792&coll=DL&dl=GUIDE&CFID=34101495&CFTOKEN=18614940 Knowledge-Based Search in Competitive Domains]''. IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 3
* [[Arie de Bruin]], [[Wim Pijls]] ('''2003'''). ''[https://repub.eur.nl/pub/459 Trends in game tree search]''. [https://en.wikipedia.org/wiki/Erasmus_University_Rotterdam Erasmus University, Rotterdam]
* [[David Rasmussen]] ('''2004'''). ''Parallel Chess Searching and Bitboards.'' Masters thesis, [http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/3267/ps/imm3267.ps ps]
* [[Yan Radovilsky]], [[Solomon Eyal Shimony]] ('''2004'''). ''Generalized Model for Rational Game Tree Search''. [httphttps://dblp.uni-trier.de/db/conf/smc/smc2004-2.html SMC 2004], [https://www.cs.bgu.ac.il/%7Eyanr~yanr/Publications/smc04.pdf pdf]<ref>[http://www.talkchess.com/forum/viewtopic.php?t=57560&start=14 Re: Interesting ideas] by [[Karlo Balla|Karlo Bala Jr.]], [[CCC]], September 09, 2015</ref>
* [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2004'''). ''Pre-Searching''. [[ICGA Journal#27_4|ICGA Journal, Vol. 27, No. 4]]
* [[Markian Hlynka]], [[Jonathan Schaeffer]] ('''2005'''). ''[http://link.springer.com/chapter/10.1007/11922155_3 Automatic Generation of Search Engines]''. [[Advances in Computer Games 11]]
=Forum Posts=
==1999==
* [https://www.stmintz.com/ccc/index.php?id=47379 Some crazy ideas] by Gareth McCaughan, [[CCC]], March 29, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=112586 About search algorithms and heuristics] by [[José Carlos Martínez Galán|José Carlos]], [[CCC]], May 26, 2000
* [http://www.talkchess.com/forum/viewtopic.php?t=64390 search efficiency] by [[Marco Pampaloni]], [[CCC]], June 23, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=65403 comparing between search or evaluation] by [[Uri Blass]], [[CCC]], October 09, 2017 » [[Evaluation]]
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74170 Tactical search] by [[Alvaro Cardoso]], [[CCC]], June 13, 2020 » [[Tactics]]
=External Links=
* [https://en.wikipedia.org/wiki/Breadth-first_search Breadth-first search from Wikipedia]
* [https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Dijkstra's algorithm from Wikipedia]
* [http://www.t-t.dk/go/cg2000/code20.html Lambda-search Java-code (version 2.0)] by [[Thomas Thomsen]]
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iv-basic-search-r1171 Chess Programming Part IV: Basic Search] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], Ausgust 2000
* [https://sites.google.com/site/hispanicchessengines/programs--interface---engines/engine Engine - Hispanic Chess Engines | The search function] by [[Pedro Castro]]
* [[:Category:Miroslav Vitouš|Miroslav Vitouš]] - [https://de.wikipedia.org/wiki/Infinite_Search Infinite Search] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[:Category:Jack DeJohnette|Jack DeJohnette]] ([https://en.wikipedia.org/wiki/Joe_Chambers Joe Chambers] track 6), [[:Category:John McLaughlin|John McLaughlin]], [[:Category:Herbie Hancock|Herbie Hancock]], [[:Category:Joe Henderson|Joe Henderson]]: {{#evu:https://www.youtube.com/watch?v=41RgdUoGZ98-OdIEbFwQEs|alignment=left|valignment=top}}
=References=
