Changes

Jump to: navigation, search

Search

718 bytes added, 23:58, 9 March 2019
no edit summary
'''[[Main Page|Home]] * Search'''
[[FILE:AufderSuche.jpg|border|right|thumb|link=http://schachbilderwelten.tenners.de/html/auf_der_suche.html|[[Arts#:Category:Bernd 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].
=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|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]]
==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 generationGeneration|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]]
They usually have huge memory requirements, since they keep an exponentially growing search space in memory.
* [[B*]] as used by [[Hans Berliner|Hans Berliner's]] chess-program [[HiTech]]
* [[Best-First Minimax Search]]
* [[Conspiracy Number Search]]
* [[MCαβ]]
* [[Monte-Carlo Tree Search]]
* [[Proof-number searchNumber Search]]
* [[SSS* and Dual*]]
* [[UCT]]
* [[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 LevyToshihide Ibaraki]] (Editor'''1978'''). ''[https://link.springer.com/article/10.1007/BF00991818 Depth-m search in branch-and-bound algorithms]''. [https://link.springer.com/journal/10766 International Journal of Parallel Programming], ppVol. 136 - 1427, No. 4* [[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 ...==
* [[Liwu Li]] ('''1989'''). ''[https://doi.org/10.7939/R3VX06F26 Probabilistic Analysis of Search]''. Ph.D. thesis, [[University of Alberta]], advisor [[Tony Marsland]]
==1990 ...==
* [[Toshihide Ibaraki]], [[Naoki Katoh]] ('''1990'''). ''[https://link.springer.com/article/10.1007/BF01531075 Searching Minimax Game Trees Under Memory Space Constraint]''. [https://link.springer.com/journal/10472 Annals of Mathematics and Artificial Intelligence], Vol. 1, Nos. 1-4
* [[Victor Allis]], [[Maarten van der Meulen]], [[Jaap van den Herik]] ('''1991'''). ''Proof-Number Search.'' Technical Reports in Computer Science, CS 91-01. Department of Computer Science, [[Maastricht University|University of Limburg]]
* [[Tony Marsland]] ('''1992'''). ''Computer Chess and Search.'' Encyclopedia of Artificial Intelligence (2nd ed.) (ed. S.C. Shapiro) John Wiley & Sons, Inc. [http://webdocs.cs.ualberta.ca/~tony/RecentPapers/encyc.mac-1991.pdf pdf] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7df61a100528f201 Excellent Computer-Chess Overview Paper Found!] by [[Ernst A. Heinz]], [[Computer Chess Forums|rgcc]], March 6, 1997</ref> <ref>[https://www.stmintz.com/ccc/index.php?id=221364 Great article for people who wants to write a chess engine] by [[Miguel A. Ballicora]], [[CCC]], April 03, 2002</ref>
* [[Thomas Lincke]] ('''2002'''). ''Exploring the Computational Limits of Large Exhaustive Search Problems''. Ph.D thesis, [[ETH Zurich]], [http://e-collection.library.ethz.ch/eserv/eth:25905/eth-25905-02.pdf pdf] » [[Awari]], [[Repetitions]] <ref>[http://www.open-chess.org/viewtopic.php?f=5&t=2093#p17469 Re: Aquarium IDEA, repetitions, and minimax over cycles] by [[Ronald de Man|syzygy]], [[Computer Chess Forums|OpenChess Forum]], September 22, 2012</ref>
* [[Steven Walczak]] ('''2003'''). ''[http://portal.acm.org/citation.cfm?id=776752.776792&coll=DL&dl=GUIDE&CFID=34101495&CFTOKEN=18614940 Knowledge-Based Search in Competitive Domains]''. IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 3
* [[Arie de Bruin]], [[Wim Pijls]] ('''2003'''). ''[https://repub.eur.nl/pub/459 Trends in game tree search]''. [https://en.wikipedia.org/wiki/Erasmus_University_Rotterdam Erasmus University, Rotterdam]
* [[David Rasmussen]] ('''2004'''). ''Parallel Chess Searching and Bitboards.'' Masters thesis, [http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/3267/ps/imm3267.ps ps]
* [[Yan Radovilsky]], [[Solomon Eyal Shimony]] ('''2004'''). ''Generalized Model for Rational Game Tree Search''. [http://www.cs.bgu.ac.il/%7Eyanr/Publications/smc04.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>
* [[Christopher D. Rosin]] ('''2014'''). ''Game playing''. [https://en.wikipedia.org/wiki/Wiley_Interdisciplinary_Reviews:_Cognitive_Science WIREs Cognitive Science], Vol. 5, [http://www.chrisrosin.com/Rosin-Game-Playing-submitted-ver.pdf pdf preprint]
==2015 ...==
* [[Jakub Pawlewicz]], [[Ryan Hayward]] ('''2015'''). ''Feature Strength and Parallelization of Sibling Conspiracy Number Search''. [[Advances in Computer Games 14]]
* [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:Category:Miroslav Vitouš|Miroslav Vitouš]] - [https://de.wikipedia.org/wiki/Infinite_Search Infinite Search] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video : [[Videos#JackDeJohnette:Category:Jack DeJohnette|Jack DeJohnette]] ([https://en.wikipedia.org/wiki/Joe_Chambers Joe Chambers] track 6), [[Videos#JohnMcLaughlin:Category:John McLaughlin|John McLaughlin]], [[Videos#HerbieHancock:Category:Herbie Hancock|Herbie Hancock]], [[Videos#JoeHenderson:Category:Joe Henderson|Joe Henderson]]
: {{#evu:https://www.youtube.com/watch?v=41RgdUoGZ98|alignment=left|valignment=top}}
<references />
'''[[Main Page|HomeUp one Level]]'''[[Category:Bernd Besser]][[Category:Jack DeJohnette]][[Category:Herbie Hancock]][[Category:Joe Henderson]][[Category:John McLaughlin]][[Category:Miroslav Vitouš]]

Navigation menu