Search

**[[Home]] * Search**
|| [[image:AufderSuche.jpg link="http://www.tenners.de/schachbilderwelten/html/galerie.html"]] ||~   || Because having a perfect [[Evaluation|evaluation]] is impossible, chess programs must rely on some type of **Search** in order to play reasonably.

Searching involves looking ahead at different [[Moves|move]] sequences and evaluating the [[Chess Position|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]]. ||
|| [[Arts#Besser|Bernd Besser]], Auf der Suche <ref>[[http://www.tenners.de/schachbilderwelten/html/galerie.html|Schach Bilder Welten - Bernd Besser - Galerie]]</ref> ||~   ||^   ||
[[toc]]
=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]]
[[image:negaSearch_JRP-2012.jpg align="right" caption="negaSearch function at the heart of every chess program" link="John Roland Penner"]]
==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>[[http://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>[[http://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 ...==
* [[http://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.stmintz.com/ccc/index.php?id=172496|Search algorithms and effeciency]] by Kim Roper Jensen, [[CCC]], May 30, 2001
* [[http://www.stmintz.com/ccc/index.php?id=201686|Search algorithms in chess programs]] by [[Russell Reagan]], [[CCC]], December 12, 2001
* [[http://www.stmintz.com/ccc/index.php?id=325977|Search algorithms]] by [[Jan Renze Steenhuisen|Renze Steenhuisen]], [[CCC]], November 06, 2003
* [[http://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]]
> [[media type="youtube" key="41RgdUoGZ98"]]

=References= 
<references />
**[[Home|Up one level]]**