25,161
edits
Changes
Created page with "'''Home * Search''' border|right|thumb|link=http://schachbilderwelten.tenners.de/html/auf_der_suche.html|[[Arts#Besser|Bernd Besser, Au..."
'''[[Main Page|Home]] * Search'''
[[FILE:AufderSuche.jpg|border|right|thumb|link=http://schachbilderwelten.tenners.de/html/auf_der_suche.html|[[Arts#Besser|Bernd Besser]], Auf der Suche <ref>[http://schachbilderwelten.tenners.de/html/galerie.html Schach Bilder Welten - Bernd Besser - Galerie]</ref> ]]
Because finding or guessing a [[Best Move|good move]] in a [[Chess Position|chess position]] is hard to achieve statically, [[Engines|chess programs]] rely on some type of '''Search''' in order to play reasonably. Searching involves looking ahead at different [[Moves|move]] sequences and evaluating the positions after [[Make Move|making the moves]]. Formally, searching a two-player [https://en.wikipedia.org/wiki/Zero-sum_%28game_theory%29 zero-sum] board game with [https://en.wikipedia.org/wiki/Perfect_information perfect information] implies [https://en.wikipedia.org/wiki/Tree_traversal traversing] and min-maxing a [https://en.wikipedia.org/wiki/Tree_%28data_structure%29 tree-like data-structure] by various [https://en.wikipedia.org/wiki/Search_algorithm search algorithms].
=Shannon's Types=
[[Claude Shannon]] categorized searches into two types <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> :
* [[Type A Strategy|Type A]] - a [[Brute-Force|brute-force search]] looking at every variation to a given [[Depth|depth]]
* [[Type B Strategy|Type B]] - a [[Selectivity|selective search]] looking at "important" branches only
Inspired by the experiments of [[Adriaan de Groot]] <ref>[[Adriaan de Groot]] ('''1946'''). ''Het denken van den Schaker, een experimenteel-psychologische studie''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_Amsterdam University of Amsterdam]; N.V. Noord-Hollandse Uitgevers Maatschappij, [https://en.wikipedia.org/wiki/Amsterdam Amsterdam]. Translated with the help of [[George Baylor]], with additions (in '''1965''') as ''Thought and Choice in Chess''. Mouton Publishers, The Hague. ISBN 90-279-7914-6. ([http://www.amazon.com/gp/reader/9027979146/ref=sib_dp_pt#reader-link amazon])</ref> , Shannon and early programmers favored Type B strategy. Type B searches use some type of static heuristics in order to only look at branches that look important - with some risk to oversee some serious tactics not covered by the plausible move selector. Type B was most popular until the 1970's, when Type A programs had enough processing power and more efficient brute force algorithms to become stronger. Today most programs are closer to Type A, but have some characteristics of a Type B as mentioned in [[Selectivity|selectivity]].
=The Search Tree=
The [[Search Tree|search tree]] as subset of the [[Search Space|search space]] is a [https://en.wikipedia.org/wiki/Graph_%28mathematics%29#Directed_graph directed graph] of [[Node|nodes]], the alternating white and black to move [[Chess Position|chess positions]] - and edges connecting two nodes, representing the [[Moves|moves]] of either side. The [[Root|root]] of the search-tree is the position we like to evaluate to find the [[best move]]. Because of [[Transposition|transpositions]] due to different move sequences, nodes inside the tree may occur from various ancestors - even within a different number of moves. The search tree contains various cycles, since both sides may [[Repetitions|repeat]] a former position with the minimum of two reversible moves each, or four [[Ply|plies]]. Cycles are usually eliminated and not searched twice, which results in searching a [https://en.wikipedia.org/wiki/Directed_acyclic_graph directed acyclic graph] (DAG).
* [[Search Space]]
* [[Search Tree]]
* [[Root]]
* [[Node]]
* [[Conspiracy Numbers]]
* [[Move List]]
* [[Principal Variation]]
* [[Graph History Interaction]]
* [[Path-Dependency]]
* [[Repetitions]]
* [[Transposition]]
* [[Score]]
=Search Algorithms=
Most chess-programs use a variation of the [[Alpha-Beta|alpha-beta]] algorithm to search the tree in a [[Depth-First|depth-first]] manner to attain an order of magnitude performance improvement over a pure [[Minimax|minimax]] algorithm. Although <span style="font-size: 13px; line-height: 1.5;">[[Move Ordering|move ordering]] doesnt affect the performance of a pure mini-max search (as all branches and nodes are searched) — it becomes crucial for the performance of alpha beta search and enhancements such as [[Principal Variation Search|PVS]], [[NegaScout]] and [[MTD(f)]]. [[Hans Berliner|Hans Berliner's]] chess-program [[HiTech]] and [[Ulf Lorenz|Ulf Lorenz's]] program [[P.ConNerS]] used [[Best-First|best-first]] approaches quite successfully.</span>
==Depth-First Search==
[[Depth-First]] search starts at the root and explores as far as possible along each branch before backtracking. Memory requirements are moderate, since only one path from the root to one leaf is kept in memory. The giga bytes of [[Memory#RAM|RAM]] in recent computers is utilized by a [[Transposition Table|transposition table]]. Minimax and Negamax are mentioned for educational reasons as the prototypes for the more advanced algorithms. They otherwise have no practical relevance in software, except traversing a minimax tree inside a [[Perft|perft]] framework for [[Engine Testing|testing]] the [[Move generation|move generator]]. Depth-first algorithms are generally embedded inside an [[Iterative Deepening|iterative deepening]] framework for [[Time Management|time control]] and [[Move Ordering|move ordering]] issues.
* [[Minimax]]
* [[Negamax]]
* [[Alpha-Beta]]
==Alpha-Beta Enhancements==
===Obligatory===
* [[Transposition Table]]
* [[Iterative Deepening]]
* [[Aspiration Windows]]
===Selectivity===
* [[Quiescence Search]]
* [[Selectivity]]
* [[Mate Search]]
===Scout and Friends===
* [[Scout]]
* [[NegaScout]]
* [[Principal Variation Search]]
===Alpha-Beta goes Best-First===
* [[NegaC*]]
* [[MTD(f)]]
* [[Alpha-Beta Conspiracy Search]]
==Best-First Search==
[[Best-First]] approaches build a search-tree by visiting the most promising nodes first.
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]]
* [[Conspiracy Number Search]]
* [[MCαβ]]
* [[Monte-Carlo Tree Search]]
* [[Proof-number search]]
* [[SSS* and Dual*]]
* [[UCT]]
=Opponent Model=
* [[Opponent Model Search]]
=Parallel Search=
* [[Parallel Search]]
* [[Parallel Controlled Conspiracy Number Search]] as used by [[Ulf Lorenz|Ulf Lorenz's]] program [[P.ConNerS]]
=Using Time=
* [[Pondering]]
* [[Time Management]]
=Related Issues=
* [[Depth]]
* [[Horizon Effect]]
* [[Iterative Search]]
* [[Move Ordering]]
* [[Search Explosion]]
* [[Search Instability]]
* [[Search Pathology]]
* [[Search Statistics]]
* [[Search with Random Leaf Values]]
* [[James R. Slagle#TheoremProving|Theorem-Proving and M & N procedure]]
=See also=
* [[Backtracking]]
* [[History|History of Computer Chess]]
* [[Knowledge]]
: [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]]
=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
* [[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]
==1970 ...==
* [[James R. Slagle]], [[John K. Dixon]] ('''1970'''). ''[http://portal.acm.org/citation.cfm?id=362052.362054 Experiments with the M & N Tree-Searching Program]''. [[ACM#Communications|Communications of the ACM]], Vol. 13, No. 3, pp. 147-154.
* [[James R. Slagle]], [[Richard C. T. Lee]] ('''1971'''). ''[http://portal.acm.org/citation.cfm?id=362515.362562 Application of game tree searching techniques to sequential pattern recognition]''. [[ACM#Communications|Communications of the ACM]], Vol. 14, No. 2
* [[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''. Artificial Intelligence, Vol. 5, No. 3, pp. 217-234. ISSN 0004-3702. 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 Levy]] (Editor), pp. 136 - 142
* [[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?'' Artificial Intelligence, Vol. 12, No. 2, pp. 179-196. ISSN 0004-3702.
==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''. Artificial Intelligence Vol. 34, 1, [http://people.csail.mit.edu/rivest/Rivest-GameTreeSearchingByMinMaxApproximation.pdf pdf 1995]
* [[Bruce Abramson]] ('''1989'''). ''Control Strategies for Two-Player Games.'' ACM Computing Surveys 21(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]]
==1990 ...==
* [[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>
* [[Eric B. Baum]] ('''1992'''). ''On Optimal Game Tree Propagation for Imperfect Players''. [[AAAI|AAAI-92]], [http://www.aaai.org/Papers/AAAI/1992/AAAI92-078.pdf pdf]
* [[Claude G. Diderich]] ('''1993'''). ''[http://portal.acm.org/citation.cfm?id=165007 A Bibliography on Minimax Trees]''. [[ACM#SIG|ACM SIGACT News]], Vol. 24, No. 4
* [[Deniz Yuret]] ('''1994'''). ''[https://scholar.google.com/citations?view_op=view_citation&hl=en&user=EJurXJ4AAAAJ&cstart=40&citation_for_view=EJurXJ4AAAAJ:TQgYirikUcIC The Principle of Pressure in Chess]''. TAINN 1994
* [[Hans Berliner]], [[Chris McConnell]] ('''1995'''). ''B* Probability Based Search.'' [[Carnegie Mellon University]] Computer Science research report, Pittsburgh, PA, [http://www.cs.cmu.edu/afs/cs.cmu.edu/user/ccm/www/papers/BStar.ps postscript]
* [[Claude G. Diderich]], [[Marc Gengler]] ('''1995'''). ''[http://link.springer.com/chapter/10.1007/978-1-4613-3557-3_2 A Survey on Minimax Trees and Associated Algorithms]''. ''[http://link.springer.com/book/10.1007/978-1-4613-3557-3 Minimax and Its Applications]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Kluwer Academic Publishers]
* [[Eric B. Baum]], [[Warren D. Smith]] ('''1995'''). ''Best Play for Imperfect Players and Game Tree Search''. Part 1 - Theory
* [[Eric B. Baum]], [[Warren D. Smith]] ('''1995'''). ''Best Play for Imperfect Players and Game Tree Search''. with pseudocode appendix by [[Charles Garrett]], [http://scorevoting.net/WarrenSmithPages/homepage/bpip1.ps ps]
* [[Warren D. Smith]], [[Eric B. Baum]], [[Charles Garrett]], [[Rico Tudor]] ('''1995'''). ''Best Play for Imperfect Players and Game Tree Search''. Part 2 - Experiments, [http://scorevoting.net/WarrenSmithPages/homepage/bpip2.ps ps]
* [[Andy Walker|Andrew N. Walker]] ('''1996'''). ''Hybrid Heuristic Search''. [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]]
* [[Ingo Althöfer]] ('''1997'''). ''On the k-best Mode in Computer Chess: Measuring the Similarity of Move Proposals.'' [[ICGA Journal#20_3|ICCA Journal, Vol. 20, No. 3]]
* [[Eric B. Baum]], [[Warren D. Smith]] ('''1997'''). ''A Bayesian Approach to Relevance in Game Playing''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 97, [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.7961 CiteSeerX]
* [[Donald Knuth|Donald E. Knuth]] ('''1998'''). ''[http://www-cs-faculty.stanford.edu/%7Eknuth/taocp.html The Art Of Computer Programming] Vol 3. Sorting and Searching, Second Edition'', Addison-Wesley
* [[Wim Pijls]], [[Arie de Bruin]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_12 Game Tree Algorithms and Solution Trees]''. [[CG 1998]]
==2000 ...==
* [[Paul E. Utgoff]], [[Richard P. Cochran]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_1 A Least-Certainty Heuristic for Selective Search]''. [[CG 2000]], [http://people.cs.umass.edu/~utgoff/papers/springer-lcf.pdf pdf] » [[Richard P. Cochran#LCF|LCF]]
* [[Thomas Thomsen]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_2 Lambda-Search in Game Trees - with Application to Go]''. [[CG 2000]] also published in [[ICGA Journal#23_4|ICGA Journal, Vol. 23, No. 4]], winning the 2001 [[ICGA Journal#JournalAward|ICGA Journal Award]], [http://www.t-t.dk/publications/lambda_icga.pdf preprint as pdf] » [[Lambda-Search]]
* [[Todd W. Neller]] ('''2000'''). ''Simulation-Based Search for Hybrid System Control and Analysis''. Ph.D. thesis, [[Stanford University]], advisor [[Richard Fikes]], [http://cs.gettysburg.edu/~tneller/papers/neller-dissertation.pdf pdf]
* [[Martin Müller]] ('''2001, 2002'''). ''Proof-Set Search''. Technical Report TR 01-09, [[University of Alberta]], [[CG 2002]], [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.9972 CiteSeerX] <ref>[https://www.stmintz.com/ccc/index.php?id=233322 Re: A new(?) technique to recognize draws] by [[Dan Andersson]], June 01, 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
* [[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''. [http://www.cs.bgu.ac.il/%7Eyanr/Publications/smc04.pdf pdf]
* [[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]]
* [[Ulf Lorenz]] ('''2006'''). ''A new Implementation of Error Analysis in Game Trees''. [[ICGA Journal#29_2|ICGA Journal, Vol. 29, No. 2]]
* [[Dmitry Batenkov]] ('''2006'''). ''Modern developments of Shannon’s Chess''. [http://www.wisdom.weizmann.ac.il/~dmitryb/writing/chess_report.pdf pdf]
* [[Pim Nijssen]] ('''2009'''). ''Using Intelligent Search Techniques to Play the Game Khet''. Master's Thesis, [[Maastricht University]], [http://www.personeel.unimaas.nl/pim.nijssen/pub/msc.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Khet_%28game%29 Khet (game) from Wikipedia]</ref>
* [[Claude G. Diderich]], [[Marc Gengler]] ('''2009'''). ''[http://link.springer.com/referenceworkentry/10.1007%2F978-0-387-74759-0_370 Minimax Game Tree Searching]''. [http://link.springer.com/book/10.1007/978-0-387-74759-0 Encyclopedia of Optimization], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[David Silver]] ('''2009'''). ''Reinforcement Learning and Simulation-Based Search''. Ph.D. thesis, [[University of Alberta]], [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/thesis.pdf pdf]
==2010 ...==
* [[Junichi Hashimoto]] ('''2011'''). ''A Study on Game-Independent Heuristics in Game-Tree Search''. Ph.D. thesis, [[JAIST]]
* [[Hung-Jui Chang]], [[Meng-Tsung Tsai]], [[Tsan-sheng Hsu]] ('''2011'''). ''Game Tree Search with Adaptive Resolution''. [[Advances in Computer Games 13]], [https://www.conftool.net/acg13/index.php/Chang-Game_Tree_Search_with_Adaptive_Resolution-145.pdf?page=downloadPaper&filename=Chang-Game_Tree_Search_with_Adaptive_Resolution-145.pdf&form_id=145&form_version=final pdf]
* [[Alexandru Godescu]] ('''2011'''). ''[http://arxiv.org/abs/1112.2149 Information and search in computer chess]''. <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=1736 Information and search in computer chess (Godescu)] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], December 12, 2011</ref>
* [[Pim Nijssen]], [[Mark Winands]] ('''2012'''). ''An Overview of Search Techniques in Multi-Player Games''. [[ECAI CGW 2012]]
* [[Abdallah Saffidine]], [[Tristan Cazenave]] ('''2012'''). ''A General Multi-Agent Modal Logic K Framework for Game Tree Search''. [[ECAI CGW 2012]]
* [[Akihiro Kishimoto]], [[Mark Winands]], [[Martin Müller]], [[Jahn-Takeshi Saito]] ('''2012'''). ''Game-Tree Search using Proof Numbers: The First Twenty Years''. [[ICGA Journal#35_3|ICGA Journal, Vol. 35, No. 3]]
* [[Kuo-Yuan Kao]], [[I-Chen Wu]], [[Yi-Chang Shan]], [[Shi-Jim Yen]] ('''2012'''). ''Selection Search for Mean and Temperature of Multi-branch Combinatorial Games''. [[ICGA Journal#35_3|ICGA Journal, Vol. 35, No. 3]]
* [[David Silver]], [[Richard Sutton]], [[Martin Müller|Martin Mueller]] ('''2013'''). ''Temporal-Difference Search in Computer Go''. Proceedings of the [http://icaps13.icaps-conference.org/technical-program/workshop-program/planning-and-learning/ ICAPS-13 Workshop on Planning and Learning], [http://webdocs.cs.ualberta.ca/~sutton/papers/SSM-ICAPS-13.pdf pdf]
* [[Jeff Rollason]] ('''2014'''). ''[http://www.aifactory.co.uk/newsletter/2014_01_interest_minimax.htm Interest Search - Another way to do Minimax]''. [[AI Factory]], Summer 2014
* [[Tom Holden]] ('''2014'''). ''Notes on an alternative approach to move choice in games such as Chess''. [http://www.tholden.org/wp-content/uploads/2014/11/Notes-on-an-alternative-approach-to-move-choice-in-games-such-as-Chess.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=54324 A new algorithm accounting for the uncertainty in eval funcs] by [[Tom Holden]], [[CCC]], November 12, 2014</ref>
==2015 ...==
* [[Jakub Pawlewicz]], [[Ryan Hayward]] ('''2015'''). ''Feature Strength and Parallelization of Sibling Conspiracy Number Search''. [[Advances in Computer Games 14]]
* [[Mohd Nor Akmal Khalid]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[https://www.researchgate.net/publication/281152992_Critical_Position_Identification_in_Games_and_Its_Application_to_Speculative_Play Critical Position Identification in Games and Its Application to Speculative Play]''. [http://www.scitepress.org/DigitalLibrary/ProceedingsDetails.aspx?ID=+mGlly8Sp00=&t=1 ICAART 2015]
* [[Mohd Nor Akmal Khalid]], [[E. Mei Ang]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-319-27947-3_6 Identifying Critical Positions Based on Conspiracy Numbers]''. [http://link.springer.com/book/10.1007/978-3-319-27947-3 Agents and Artificial Intelligence], [http://dblp.uni-trier.de/db/conf/icaart/icaart2015s.html#KhalidAYII15 ICAART 2015 - Revised Selected Papers]
* [[Ting-Han Wei]], [[Chao-Chin Liang]], [[I-Chen Wu]], [[Lung-Pin Chen]] ('''2015'''). ''Software Development Framework for Job-Level Algorithms''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]]
* [[Tobias Joppen]], [[Miriam Moneke]], [[Nils Schroder]], [[Christian Wirth]], [[Johannes Fürnkranz]] ('''2017'''). ''[http://ieeexplore.ieee.org/document/7970136/ Informed Hybrid Game Tree Search for General Video Game Playing]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. PP, No. 99
=Forum Posts=
==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
* [https://www.stmintz.com/ccc/index.php?id=172496 Search algorithms and effeciency] by Kim Roper Jensen, [[CCC]], May 30, 2001
* [https://www.stmintz.com/ccc/index.php?id=201686 Search algorithms in chess programs] by [[Russell Reagan]], [[CCC]], December 12, 2001
* [https://www.stmintz.com/ccc/index.php?id=325977 Search algorithms] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], November 06, 2003
* [https://www.stmintz.com/ccc/index.php?id=343686 Game tree search algorithms] by [[Russell Reagan]], [[CCC]], January 20, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6665 Search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007 » [[Fail-Soft]], [[Principal Variation Search]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6666 Even more search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007 » [[Root]], [[Iterative Deepening]]
* [http://www.hiarcs.net/forums/viewtopic.php?t=402 Search or Evaluation?] by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|Hiarcs Forum]], October 05, 2007 » [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]], [[Evaluation]]
: [http://www.hiarcs.net/forums/viewtopic.php?p=2944 Re: Search or Evaluation?] by [[Mark Uniacke]], [[Computer Chess Forums|Hiarcs Forum]], October 14, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=17921 Efficient algorithm for k-best mode?] by [[Gijsbert Wiesenekker]], [[CCC]], November 17, 2007
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=48733 Scaling at 2x nodes (or doubling time control).] by [[Kai Laskos]], [[CCC]], July 23, 2013 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Houdini]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48743 Is search irrelevant when computing ahead of very big trees?] by [[Fermin Serrano]], [[CCC]], July 24, 2013 » [[Knowledge]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49190 Improve the search or the evaluation?] by [[Jens Bæk Nielsen]], [[CCC]], August 31, 2013 » [[Evaluation]], [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49906 Slow Searchers?] by Michael Neish, [[CCC]], November 02, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=54324 A new algorithm accounting for the uncertainty in eval funcs] by [[Tom Holden]], [[CCC]], November 12, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55474 Search algorithm in it's simplest forum] by [[Mahmoud Uthman]], [[CCC]], February 25, 2015 » [[Alpha-Beta]], [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57092 Time assignment to children] by [[Matthew Lai]], [[CCC]], July 26, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57270 Some musings about search] by [[Ed Schroder]], [[CCC]], August 14, 2015 » [[Automated Tuning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60581 Search] by [[Laurie Tunnicliffe]], [[CCC]], June 24, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61348 Searching using slow eval with tactical verification] by [[Matthew Lai]], [[CCC]], September 06, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61358 Root search] by [[Laurie Tunnicliffe]], [[CCC]], September 08, 2016 » [[Root]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61784 Doubling of time control] by [[Andreas Strangmüller]], [[CCC]], October 21, 2016 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Komodo]]
* [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]]
=External Links=
* [https://en.wikipedia.org/wiki/Search_algorithm Search algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Combinatorial_search Combinatorial search from Wikipedia]
* [https://en.wikipedia.org/wiki/Depth-first_search Depth-first search from Wikipedia]
* [http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/depth_first_search.html Boost Graph Library: Depth-First Search]
* [https://en.wikipedia.org/wiki/Best-first_search Best-first search from Wikipedia]
: [https://en.wikipedia.org/wiki/A*_search_algorithm A* search algorithm from Wikipedia]
* [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://homepages.ius.edu/RWISMAN/C463/html/Chapter3.htm Chapter 3 Solving Problems by Searching] from [http://homepages.ius.edu/RWISMAN/C463/html/syllabus.htm C463 Artificial Intelligence Syllabus] by [http://homepages.ius.edu/RWISMAN/ Raymond F. Wisman]
* [http://chess.verhelst.org/1997/03/10/search/ Tree Search] by [[Paul Verhelst]]
* [http://www.chessbin.com/post/Move-Searching-Alpha-Beta.aspx Move Searching and Alpha Beta] by [[Adam Berent]]
* [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
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-v-advanced-search-r1197 Chess Programming Part V: Advanced Search] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], September 2000
* [https://sites.google.com/site/hispanicchessengines/programs--interface---engines/engine Engine - Hispanic Chess Engines | The search function] by [[Pedro Castro]]
* [[Videos#MiroslavVitous|Miroslav Vitouš]] - [https://de.wikipedia.org/wiki/Infinite_Search Infinite Search] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#JackDeJohnette|Jack DeJohnette]] ([https://en.wikipedia.org/wiki/Joe_Chambers Joe Chambers] track 6), [[Videos#JohnMcLaughlin|John McLaughlin]], [[Videos#HerbieHancock|Herbie Hancock]], [[Videos#JoeHenderson|Joe Henderson]]
: {{#evu:https://www.youtube.com/watch?v=41RgdUoGZ98|alignment=left|valignment=top}}
=References=
<references />
'''[[Main Page|Home]]'''
[[FILE:AufderSuche.jpg|border|right|thumb|link=http://schachbilderwelten.tenners.de/html/auf_der_suche.html|[[Arts#Besser|Bernd Besser]], Auf der Suche <ref>[http://schachbilderwelten.tenners.de/html/galerie.html Schach Bilder Welten - Bernd Besser - Galerie]</ref> ]]
Because finding or guessing a [[Best Move|good move]] in a [[Chess Position|chess position]] is hard to achieve statically, [[Engines|chess programs]] rely on some type of '''Search''' in order to play reasonably. Searching involves looking ahead at different [[Moves|move]] sequences and evaluating the positions after [[Make Move|making the moves]]. Formally, searching a two-player [https://en.wikipedia.org/wiki/Zero-sum_%28game_theory%29 zero-sum] board game with [https://en.wikipedia.org/wiki/Perfect_information perfect information] implies [https://en.wikipedia.org/wiki/Tree_traversal traversing] and min-maxing a [https://en.wikipedia.org/wiki/Tree_%28data_structure%29 tree-like data-structure] by various [https://en.wikipedia.org/wiki/Search_algorithm search algorithms].
=Shannon's Types=
[[Claude Shannon]] categorized searches into two types <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> :
* [[Type A Strategy|Type A]] - a [[Brute-Force|brute-force search]] looking at every variation to a given [[Depth|depth]]
* [[Type B Strategy|Type B]] - a [[Selectivity|selective search]] looking at "important" branches only
Inspired by the experiments of [[Adriaan de Groot]] <ref>[[Adriaan de Groot]] ('''1946'''). ''Het denken van den Schaker, een experimenteel-psychologische studie''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_Amsterdam University of Amsterdam]; N.V. Noord-Hollandse Uitgevers Maatschappij, [https://en.wikipedia.org/wiki/Amsterdam Amsterdam]. Translated with the help of [[George Baylor]], with additions (in '''1965''') as ''Thought and Choice in Chess''. Mouton Publishers, The Hague. ISBN 90-279-7914-6. ([http://www.amazon.com/gp/reader/9027979146/ref=sib_dp_pt#reader-link amazon])</ref> , Shannon and early programmers favored Type B strategy. Type B searches use some type of static heuristics in order to only look at branches that look important - with some risk to oversee some serious tactics not covered by the plausible move selector. Type B was most popular until the 1970's, when Type A programs had enough processing power and more efficient brute force algorithms to become stronger. Today most programs are closer to Type A, but have some characteristics of a Type B as mentioned in [[Selectivity|selectivity]].
=The Search Tree=
The [[Search Tree|search tree]] as subset of the [[Search Space|search space]] is a [https://en.wikipedia.org/wiki/Graph_%28mathematics%29#Directed_graph directed graph] of [[Node|nodes]], the alternating white and black to move [[Chess Position|chess positions]] - and edges connecting two nodes, representing the [[Moves|moves]] of either side. The [[Root|root]] of the search-tree is the position we like to evaluate to find the [[best move]]. Because of [[Transposition|transpositions]] due to different move sequences, nodes inside the tree may occur from various ancestors - even within a different number of moves. The search tree contains various cycles, since both sides may [[Repetitions|repeat]] a former position with the minimum of two reversible moves each, or four [[Ply|plies]]. Cycles are usually eliminated and not searched twice, which results in searching a [https://en.wikipedia.org/wiki/Directed_acyclic_graph directed acyclic graph] (DAG).
* [[Search Space]]
* [[Search Tree]]
* [[Root]]
* [[Node]]
* [[Conspiracy Numbers]]
* [[Move List]]
* [[Principal Variation]]
* [[Graph History Interaction]]
* [[Path-Dependency]]
* [[Repetitions]]
* [[Transposition]]
* [[Score]]
=Search Algorithms=
Most chess-programs use a variation of the [[Alpha-Beta|alpha-beta]] algorithm to search the tree in a [[Depth-First|depth-first]] manner to attain an order of magnitude performance improvement over a pure [[Minimax|minimax]] algorithm. Although <span style="font-size: 13px; line-height: 1.5;">[[Move Ordering|move ordering]] doesnt affect the performance of a pure mini-max search (as all branches and nodes are searched) — it becomes crucial for the performance of alpha beta search and enhancements such as [[Principal Variation Search|PVS]], [[NegaScout]] and [[MTD(f)]]. [[Hans Berliner|Hans Berliner's]] chess-program [[HiTech]] and [[Ulf Lorenz|Ulf Lorenz's]] program [[P.ConNerS]] used [[Best-First|best-first]] approaches quite successfully.</span>
==Depth-First Search==
[[Depth-First]] search starts at the root and explores as far as possible along each branch before backtracking. Memory requirements are moderate, since only one path from the root to one leaf is kept in memory. The giga bytes of [[Memory#RAM|RAM]] in recent computers is utilized by a [[Transposition Table|transposition table]]. Minimax and Negamax are mentioned for educational reasons as the prototypes for the more advanced algorithms. They otherwise have no practical relevance in software, except traversing a minimax tree inside a [[Perft|perft]] framework for [[Engine Testing|testing]] the [[Move generation|move generator]]. Depth-first algorithms are generally embedded inside an [[Iterative Deepening|iterative deepening]] framework for [[Time Management|time control]] and [[Move Ordering|move ordering]] issues.
* [[Minimax]]
* [[Negamax]]
* [[Alpha-Beta]]
==Alpha-Beta Enhancements==
===Obligatory===
* [[Transposition Table]]
* [[Iterative Deepening]]
* [[Aspiration Windows]]
===Selectivity===
* [[Quiescence Search]]
* [[Selectivity]]
* [[Mate Search]]
===Scout and Friends===
* [[Scout]]
* [[NegaScout]]
* [[Principal Variation Search]]
===Alpha-Beta goes Best-First===
* [[NegaC*]]
* [[MTD(f)]]
* [[Alpha-Beta Conspiracy Search]]
==Best-First Search==
[[Best-First]] approaches build a search-tree by visiting the most promising nodes first.
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]]
* [[Conspiracy Number Search]]
* [[MCαβ]]
* [[Monte-Carlo Tree Search]]
* [[Proof-number search]]
* [[SSS* and Dual*]]
* [[UCT]]
=Opponent Model=
* [[Opponent Model Search]]
=Parallel Search=
* [[Parallel Search]]
* [[Parallel Controlled Conspiracy Number Search]] as used by [[Ulf Lorenz|Ulf Lorenz's]] program [[P.ConNerS]]
=Using Time=
* [[Pondering]]
* [[Time Management]]
=Related Issues=
* [[Depth]]
* [[Horizon Effect]]
* [[Iterative Search]]
* [[Move Ordering]]
* [[Search Explosion]]
* [[Search Instability]]
* [[Search Pathology]]
* [[Search Statistics]]
* [[Search with Random Leaf Values]]
* [[James R. Slagle#TheoremProving|Theorem-Proving and M & N procedure]]
=See also=
* [[Backtracking]]
* [[History|History of Computer Chess]]
* [[Knowledge]]
: [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]]
=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
* [[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]
==1970 ...==
* [[James R. Slagle]], [[John K. Dixon]] ('''1970'''). ''[http://portal.acm.org/citation.cfm?id=362052.362054 Experiments with the M & N Tree-Searching Program]''. [[ACM#Communications|Communications of the ACM]], Vol. 13, No. 3, pp. 147-154.
* [[James R. Slagle]], [[Richard C. T. Lee]] ('''1971'''). ''[http://portal.acm.org/citation.cfm?id=362515.362562 Application of game tree searching techniques to sequential pattern recognition]''. [[ACM#Communications|Communications of the ACM]], Vol. 14, No. 2
* [[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''. Artificial Intelligence, Vol. 5, No. 3, pp. 217-234. ISSN 0004-3702. 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 Levy]] (Editor), pp. 136 - 142
* [[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?'' Artificial Intelligence, Vol. 12, No. 2, pp. 179-196. ISSN 0004-3702.
==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''. Artificial Intelligence Vol. 34, 1, [http://people.csail.mit.edu/rivest/Rivest-GameTreeSearchingByMinMaxApproximation.pdf pdf 1995]
* [[Bruce Abramson]] ('''1989'''). ''Control Strategies for Two-Player Games.'' ACM Computing Surveys 21(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]]
==1990 ...==
* [[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>
* [[Eric B. Baum]] ('''1992'''). ''On Optimal Game Tree Propagation for Imperfect Players''. [[AAAI|AAAI-92]], [http://www.aaai.org/Papers/AAAI/1992/AAAI92-078.pdf pdf]
* [[Claude G. Diderich]] ('''1993'''). ''[http://portal.acm.org/citation.cfm?id=165007 A Bibliography on Minimax Trees]''. [[ACM#SIG|ACM SIGACT News]], Vol. 24, No. 4
* [[Deniz Yuret]] ('''1994'''). ''[https://scholar.google.com/citations?view_op=view_citation&hl=en&user=EJurXJ4AAAAJ&cstart=40&citation_for_view=EJurXJ4AAAAJ:TQgYirikUcIC The Principle of Pressure in Chess]''. TAINN 1994
* [[Hans Berliner]], [[Chris McConnell]] ('''1995'''). ''B* Probability Based Search.'' [[Carnegie Mellon University]] Computer Science research report, Pittsburgh, PA, [http://www.cs.cmu.edu/afs/cs.cmu.edu/user/ccm/www/papers/BStar.ps postscript]
* [[Claude G. Diderich]], [[Marc Gengler]] ('''1995'''). ''[http://link.springer.com/chapter/10.1007/978-1-4613-3557-3_2 A Survey on Minimax Trees and Associated Algorithms]''. ''[http://link.springer.com/book/10.1007/978-1-4613-3557-3 Minimax and Its Applications]''. [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Kluwer Academic Publishers]
* [[Eric B. Baum]], [[Warren D. Smith]] ('''1995'''). ''Best Play for Imperfect Players and Game Tree Search''. Part 1 - Theory
* [[Eric B. Baum]], [[Warren D. Smith]] ('''1995'''). ''Best Play for Imperfect Players and Game Tree Search''. with pseudocode appendix by [[Charles Garrett]], [http://scorevoting.net/WarrenSmithPages/homepage/bpip1.ps ps]
* [[Warren D. Smith]], [[Eric B. Baum]], [[Charles Garrett]], [[Rico Tudor]] ('''1995'''). ''Best Play for Imperfect Players and Game Tree Search''. Part 2 - Experiments, [http://scorevoting.net/WarrenSmithPages/homepage/bpip2.ps ps]
* [[Andy Walker|Andrew N. Walker]] ('''1996'''). ''Hybrid Heuristic Search''. [[ICGA Journal#19_1|ICCA Journal, Vol. 19, No. 1]]
* [[Ingo Althöfer]] ('''1997'''). ''On the k-best Mode in Computer Chess: Measuring the Similarity of Move Proposals.'' [[ICGA Journal#20_3|ICCA Journal, Vol. 20, No. 3]]
* [[Eric B. Baum]], [[Warren D. Smith]] ('''1997'''). ''A Bayesian Approach to Relevance in Game Playing''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 97, [http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.7961 CiteSeerX]
* [[Donald Knuth|Donald E. Knuth]] ('''1998'''). ''[http://www-cs-faculty.stanford.edu/%7Eknuth/taocp.html The Art Of Computer Programming] Vol 3. Sorting and Searching, Second Edition'', Addison-Wesley
* [[Wim Pijls]], [[Arie de Bruin]] ('''1998'''). ''[http://link.springer.com/chapter/10.1007/3-540-48957-6_12 Game Tree Algorithms and Solution Trees]''. [[CG 1998]]
==2000 ...==
* [[Paul E. Utgoff]], [[Richard P. Cochran]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_1 A Least-Certainty Heuristic for Selective Search]''. [[CG 2000]], [http://people.cs.umass.edu/~utgoff/papers/springer-lcf.pdf pdf] » [[Richard P. Cochran#LCF|LCF]]
* [[Thomas Thomsen]] ('''2000'''). ''[http://link.springer.com/chapter/10.1007/3-540-45579-5_2 Lambda-Search in Game Trees - with Application to Go]''. [[CG 2000]] also published in [[ICGA Journal#23_4|ICGA Journal, Vol. 23, No. 4]], winning the 2001 [[ICGA Journal#JournalAward|ICGA Journal Award]], [http://www.t-t.dk/publications/lambda_icga.pdf preprint as pdf] » [[Lambda-Search]]
* [[Todd W. Neller]] ('''2000'''). ''Simulation-Based Search for Hybrid System Control and Analysis''. Ph.D. thesis, [[Stanford University]], advisor [[Richard Fikes]], [http://cs.gettysburg.edu/~tneller/papers/neller-dissertation.pdf pdf]
* [[Martin Müller]] ('''2001, 2002'''). ''Proof-Set Search''. Technical Report TR 01-09, [[University of Alberta]], [[CG 2002]], [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.9972 CiteSeerX] <ref>[https://www.stmintz.com/ccc/index.php?id=233322 Re: A new(?) technique to recognize draws] by [[Dan Andersson]], June 01, 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
* [[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''. [http://www.cs.bgu.ac.il/%7Eyanr/Publications/smc04.pdf pdf]
* [[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]]
* [[Ulf Lorenz]] ('''2006'''). ''A new Implementation of Error Analysis in Game Trees''. [[ICGA Journal#29_2|ICGA Journal, Vol. 29, No. 2]]
* [[Dmitry Batenkov]] ('''2006'''). ''Modern developments of Shannon’s Chess''. [http://www.wisdom.weizmann.ac.il/~dmitryb/writing/chess_report.pdf pdf]
* [[Pim Nijssen]] ('''2009'''). ''Using Intelligent Search Techniques to Play the Game Khet''. Master's Thesis, [[Maastricht University]], [http://www.personeel.unimaas.nl/pim.nijssen/pub/msc.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Khet_%28game%29 Khet (game) from Wikipedia]</ref>
* [[Claude G. Diderich]], [[Marc Gengler]] ('''2009'''). ''[http://link.springer.com/referenceworkentry/10.1007%2F978-0-387-74759-0_370 Minimax Game Tree Searching]''. [http://link.springer.com/book/10.1007/978-0-387-74759-0 Encyclopedia of Optimization], [https://en.wikipedia.org/wiki/Springer_Science%2BBusiness_Media Springer]
* [[David Silver]] ('''2009'''). ''Reinforcement Learning and Simulation-Based Search''. Ph.D. thesis, [[University of Alberta]], [http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Applications_files/thesis.pdf pdf]
==2010 ...==
* [[Junichi Hashimoto]] ('''2011'''). ''A Study on Game-Independent Heuristics in Game-Tree Search''. Ph.D. thesis, [[JAIST]]
* [[Hung-Jui Chang]], [[Meng-Tsung Tsai]], [[Tsan-sheng Hsu]] ('''2011'''). ''Game Tree Search with Adaptive Resolution''. [[Advances in Computer Games 13]], [https://www.conftool.net/acg13/index.php/Chang-Game_Tree_Search_with_Adaptive_Resolution-145.pdf?page=downloadPaper&filename=Chang-Game_Tree_Search_with_Adaptive_Resolution-145.pdf&form_id=145&form_version=final pdf]
* [[Alexandru Godescu]] ('''2011'''). ''[http://arxiv.org/abs/1112.2149 Information and search in computer chess]''. <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=1736 Information and search in computer chess (Godescu)] by [[Mark Watkins|BB+]], [[Computer Chess Forums|OpenChess Forum]], December 12, 2011</ref>
* [[Pim Nijssen]], [[Mark Winands]] ('''2012'''). ''An Overview of Search Techniques in Multi-Player Games''. [[ECAI CGW 2012]]
* [[Abdallah Saffidine]], [[Tristan Cazenave]] ('''2012'''). ''A General Multi-Agent Modal Logic K Framework for Game Tree Search''. [[ECAI CGW 2012]]
* [[Akihiro Kishimoto]], [[Mark Winands]], [[Martin Müller]], [[Jahn-Takeshi Saito]] ('''2012'''). ''Game-Tree Search using Proof Numbers: The First Twenty Years''. [[ICGA Journal#35_3|ICGA Journal, Vol. 35, No. 3]]
* [[Kuo-Yuan Kao]], [[I-Chen Wu]], [[Yi-Chang Shan]], [[Shi-Jim Yen]] ('''2012'''). ''Selection Search for Mean and Temperature of Multi-branch Combinatorial Games''. [[ICGA Journal#35_3|ICGA Journal, Vol. 35, No. 3]]
* [[David Silver]], [[Richard Sutton]], [[Martin Müller|Martin Mueller]] ('''2013'''). ''Temporal-Difference Search in Computer Go''. Proceedings of the [http://icaps13.icaps-conference.org/technical-program/workshop-program/planning-and-learning/ ICAPS-13 Workshop on Planning and Learning], [http://webdocs.cs.ualberta.ca/~sutton/papers/SSM-ICAPS-13.pdf pdf]
* [[Jeff Rollason]] ('''2014'''). ''[http://www.aifactory.co.uk/newsletter/2014_01_interest_minimax.htm Interest Search - Another way to do Minimax]''. [[AI Factory]], Summer 2014
* [[Tom Holden]] ('''2014'''). ''Notes on an alternative approach to move choice in games such as Chess''. [http://www.tholden.org/wp-content/uploads/2014/11/Notes-on-an-alternative-approach-to-move-choice-in-games-such-as-Chess.pdf pdf] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=54324 A new algorithm accounting for the uncertainty in eval funcs] by [[Tom Holden]], [[CCC]], November 12, 2014</ref>
==2015 ...==
* [[Jakub Pawlewicz]], [[Ryan Hayward]] ('''2015'''). ''Feature Strength and Parallelization of Sibling Conspiracy Number Search''. [[Advances in Computer Games 14]]
* [[Mohd Nor Akmal Khalid]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[https://www.researchgate.net/publication/281152992_Critical_Position_Identification_in_Games_and_Its_Application_to_Speculative_Play Critical Position Identification in Games and Its Application to Speculative Play]''. [http://www.scitepress.org/DigitalLibrary/ProceedingsDetails.aspx?ID=+mGlly8Sp00=&t=1 ICAART 2015]
* [[Mohd Nor Akmal Khalid]], [[E. Mei Ang]], [[Umi Kalsom Yusof]], [[Hiroyuki Iida]], [[Taichi Ishitobi]] ('''2015'''). ''[http://link.springer.com/chapter/10.1007%2F978-3-319-27947-3_6 Identifying Critical Positions Based on Conspiracy Numbers]''. [http://link.springer.com/book/10.1007/978-3-319-27947-3 Agents and Artificial Intelligence], [http://dblp.uni-trier.de/db/conf/icaart/icaart2015s.html#KhalidAYII15 ICAART 2015 - Revised Selected Papers]
* [[Ting-Han Wei]], [[Chao-Chin Liang]], [[I-Chen Wu]], [[Lung-Pin Chen]] ('''2015'''). ''Software Development Framework for Job-Level Algorithms''. [[ICGA Journal#38_3|ICGA Journal, Vol. 38, No. 3]]
* [[Tobias Joppen]], [[Miriam Moneke]], [[Nils Schroder]], [[Christian Wirth]], [[Johannes Fürnkranz]] ('''2017'''). ''[http://ieeexplore.ieee.org/document/7970136/ Informed Hybrid Game Tree Search for General Video Game Playing]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. PP, No. 99
=Forum Posts=
==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
* [https://www.stmintz.com/ccc/index.php?id=172496 Search algorithms and effeciency] by Kim Roper Jensen, [[CCC]], May 30, 2001
* [https://www.stmintz.com/ccc/index.php?id=201686 Search algorithms in chess programs] by [[Russell Reagan]], [[CCC]], December 12, 2001
* [https://www.stmintz.com/ccc/index.php?id=325977 Search algorithms] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], November 06, 2003
* [https://www.stmintz.com/ccc/index.php?id=343686 Game tree search algorithms] by [[Russell Reagan]], [[CCC]], January 20, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6665 Search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007 » [[Fail-Soft]], [[Principal Variation Search]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6666 Even more search questions] by [[Sven Schüle]], [[Computer Chess Forums|Winboard Forum]], July 17, 2007 » [[Root]], [[Iterative Deepening]]
* [http://www.hiarcs.net/forums/viewtopic.php?t=402 Search or Evaluation?] by [[Ed Schroder|Ed Schröder]], [[Computer Chess Forums|Hiarcs Forum]], October 05, 2007 » [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]], [[Evaluation]]
: [http://www.hiarcs.net/forums/viewtopic.php?p=2944 Re: Search or Evaluation?] by [[Mark Uniacke]], [[Computer Chess Forums|Hiarcs Forum]], October 14, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=17921 Efficient algorithm for k-best mode?] by [[Gijsbert Wiesenekker]], [[CCC]], November 17, 2007
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=48733 Scaling at 2x nodes (or doubling time control).] by [[Kai Laskos]], [[CCC]], July 23, 2013 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Houdini]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48743 Is search irrelevant when computing ahead of very big trees?] by [[Fermin Serrano]], [[CCC]], July 24, 2013 » [[Knowledge]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49190 Improve the search or the evaluation?] by [[Jens Bæk Nielsen]], [[CCC]], August 31, 2013 » [[Evaluation]], [[Knowledge#SearchVersusEvaluation|Search versus Evaluation]]
* [http://www.talkchess.com/forum/viewtopic.php?t=49906 Slow Searchers?] by Michael Neish, [[CCC]], November 02, 2013
* [http://www.talkchess.com/forum/viewtopic.php?t=54324 A new algorithm accounting for the uncertainty in eval funcs] by [[Tom Holden]], [[CCC]], November 12, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55474 Search algorithm in it's simplest forum] by [[Mahmoud Uthman]], [[CCC]], February 25, 2015 » [[Alpha-Beta]], [[Quiescence Search]]
* [http://www.talkchess.com/forum/viewtopic.php?t=57092 Time assignment to children] by [[Matthew Lai]], [[CCC]], July 26, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=57270 Some musings about search] by [[Ed Schroder]], [[CCC]], August 14, 2015 » [[Automated Tuning]]
* [http://www.talkchess.com/forum/viewtopic.php?t=60581 Search] by [[Laurie Tunnicliffe]], [[CCC]], June 24, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61348 Searching using slow eval with tactical verification] by [[Matthew Lai]], [[CCC]], September 06, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=61358 Root search] by [[Laurie Tunnicliffe]], [[CCC]], September 08, 2016 » [[Root]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61784 Doubling of time control] by [[Andreas Strangmüller]], [[CCC]], October 21, 2016 » [[Match Statistics#DoublingTC|Doubling TC]], [[Depth#DiminishingReturns|Diminishing Returns]], [[Playing Strength]], [[Komodo]]
* [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]]
=External Links=
* [https://en.wikipedia.org/wiki/Search_algorithm Search algorithm from Wikipedia]
* [https://en.wikipedia.org/wiki/Combinatorial_search Combinatorial search from Wikipedia]
* [https://en.wikipedia.org/wiki/Depth-first_search Depth-first search from Wikipedia]
* [http://www.boost.org/doc/libs/1_42_0/libs/graph/doc/depth_first_search.html Boost Graph Library: Depth-First Search]
* [https://en.wikipedia.org/wiki/Best-first_search Best-first search from Wikipedia]
: [https://en.wikipedia.org/wiki/A*_search_algorithm A* search algorithm from Wikipedia]
* [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://homepages.ius.edu/RWISMAN/C463/html/Chapter3.htm Chapter 3 Solving Problems by Searching] from [http://homepages.ius.edu/RWISMAN/C463/html/syllabus.htm C463 Artificial Intelligence Syllabus] by [http://homepages.ius.edu/RWISMAN/ Raymond F. Wisman]
* [http://chess.verhelst.org/1997/03/10/search/ Tree Search] by [[Paul Verhelst]]
* [http://www.chessbin.com/post/Move-Searching-Alpha-Beta.aspx Move Searching and Alpha Beta] by [[Adam Berent]]
* [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
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-v-advanced-search-r1197 Chess Programming Part V: Advanced Search] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], September 2000
* [https://sites.google.com/site/hispanicchessengines/programs--interface---engines/engine Engine - Hispanic Chess Engines | The search function] by [[Pedro Castro]]
* [[Videos#MiroslavVitous|Miroslav Vitouš]] - [https://de.wikipedia.org/wiki/Infinite_Search Infinite Search] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#JackDeJohnette|Jack DeJohnette]] ([https://en.wikipedia.org/wiki/Joe_Chambers Joe Chambers] track 6), [[Videos#JohnMcLaughlin|John McLaughlin]], [[Videos#HerbieHancock|Herbie Hancock]], [[Videos#JoeHenderson|Joe Henderson]]
: {{#evu:https://www.youtube.com/watch?v=41RgdUoGZ98|alignment=left|valignment=top}}
=References=
<references />
'''[[Main Page|Home]]'''
