25,161
edits
Changes
no edit summary
'''Best-First Search''' is a [https://en.wikipedia.org/wiki/State_space_search state space search] to traverse [[Node|nodes]] of tree-like data structures (i. e. [[Search Tree|search trees]]) in [https://en.wikipedia.org/wiki/Breadth-first_search breadth-first] manner. It is usually implemented with a [[Priority Queue|priority queue]] instead of the [[Queue|FIFO]] of breadth-first <ref>[http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/breadth_first_search.html Boost Graph Library: Breadth-First Search]</ref> , to expand the most promising node of one level first. Best-first turns a uninformed breadth-first into an informed search. Since all nodes of one level must be saved until their child nodes at the next level have been generated, the space complexity and memory requirement is proportional to the number of nodes at the deepest level.
Best-first algorithms like [https://en.wikipedia.org/wiki/A*_search_algorithm A*] are used for path finding in [https://en.wikipedia.org/wiki/Combinatorial_search combinatorial search] and [https://en.wikipedia.org/wiki/Puzzle puzzles]. [[Iterative Deepening|Iterative deepening]] is a technique to turn [[Depth-First|depth-first searches]] into best-first with the advantage space grows [https://en.wikipedia.org/wiki/Linear_growth linear] rather than [https://en.wikipedia.org/wiki/Exponential_growth exponential] with increasing [[Depth|search depth]]<ref>[[Richard Korf#JudeaPearl|Richard Korf Video]] at [[Judea Pearl#Symposium|Judea Pearl Symposium]], 2010</ref>, as applied for instance in [https://en.wikipedia.org/wiki/IDA* IDA*].
=Two-Player=
* [[B*]]
* [[Bandwidth Search]]
* [[Best-First Minimax Search]]
* [[Conspiracy Number Search]]
* [[Ari Weinstein#FSSS-Minimax|FSSS-Minimax]]
* [[UCT]]
=Some Chess Programs=
* [[Centaur]]
* [[HiTech|HiTech B*]]
* [[Leela Chess Zero]]
* [[Rocinante]]
* [[Mathematician#WZhang|Weixiong Zhang]], [[Richard Korf]] ('''1993'''). ''[http://dl.acm.org/citation.cfm?id=1867385 Depth-first vs. best-first search: New results]''. [[Conferences#AAAI-93|AAAI-93]]
* [[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
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1995, 2015'''). ''Best-First Fixed Depth Game Tree Search in Practice.'' [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai95.html [Conferences#IJCAI1995|IJCAI-95], Vol. 1], [https://www.ijcaiarxiv.org/Proceedingsabs/95-1/Papers/0361505.01603 arXiv:1505.pdf pdf01603]
* [[Richard Korf]], [[Max Chickering]] ('''1996'''). ''[https://www.microsoft.com/en-us/research/publication/best-first-minimax-search/ Best-first minimax search]''. [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 84, Nos 1-2
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1996'''). ''Best-First Fixed-Depth Minimax Algorithms.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_(journal) Artificial Intelligence], Vol. 87, Nos. 1-2, [http://www.ldc.usb.ve/%7Ebonet/courses/ci5437/papers/mtd.pdf pdf]
* [[Ayumu Nagai]], [[Hiroshi Imai]] ('''1999'''). ''Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees''. Proceedings of the Korea-Japan Joint Workshop on Algorithms and Computation
==2000 ...==
* [[Ayumu Nagai]], [[Hiroshi Imai]] ('''2002'''). ''[http://ci.nii.ac.jp/naid/110006376599 Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees]''. [http://ci.nii.ac.jp/vol_issue/nels/AA10826272/ISS0000408668_en.html IEICE transactions on information and systems]
==2010 ...==
* [[Akihiro Kishimoto]], [[Alex Fukunaga]], [[Adi Botea]] ('''2012'''). ''Evaluation of a Simple, Scalable, Parallel Best-First Search Strategy''. [https://arxiv.org/abs/1201.3204 arXiv:1201.3204]
* [[Ari Weinstein]], [[Michael L. Littman]], [[Sergiu Goschin]] ('''2013'''). ''[http://proceedings.mlr.press/v24/weinstein12a.html Rollout-based Game-tree Search Outprunes Traditional Alpha-beta]''. [http://proceedings.mlr.press/ PMLR], Vol. 24 » [[Ari Weinstein#FSSS-Minimax|FSSS-Minimax]]
* [[Jr-Chang Chen]], [[I-Chen Wu]], [[Wen-Jie Tseng]], [[Bo-Han Lin]], [[Chia-Hui Chang]] ('''2015'''). ''[https://ir.nctu.edu.tw/handle/11536/124541 Job-Level Alpha-Beta Search]''. [[IEEE#TOCIAIGAMES|IEEE Transactions on Computational Intelligence and AI in Games]], Vol. 7, No. 1
* [[Tom Everitt]], [[Marcus Hutter]] ('''2015'''). ''Analytical Results on the BFS vs. DFS Algorithm Selection Problem. Part I: Tree Search''. Australasian Conference on Artificial Intelligence, [https://pdfs.semanticscholar.org/1b4b/c878b2d068214e39b258ee250e5b8889e84c.pdf pdf]
* [[Tom Everitt]], [[Marcus Hutter]] ('''2015'''). ''Analytical Results on the BFS vs. DFS Algorithm Selection Problem: Part II: Graph Search''. Australasian Conference on Artificial Intelligence
* [[Alex Fukunaga]], [[Adi Botea]], [[Yuu Jinnai]], [[Akihiro Kishimoto]] ('''2017'''). ''A Survey of Parallel A*''. [https://arxiv.org/abs/1708.05296 arXiv:1708.05296]
==2020 ...==
* [[Quentin Cohen-Solal]] ('''2021'''). ''Completeness of Unbounded Best-First Game Algorithms''. [https://arxiv.org/abs/2109.09468 arXiv:2109.09468]
=Forum Posts=
=External Links=
* [https://en.wikipedia.org/wiki/Best-first_search Best-first search from Wikipedia]
* [[:Category:Gunter HampelIan Carr|Gunter HampelIan Carr]] Group + & [[:Category:Jeanne LeeNucleus|Jeanne LeeNucleus]] - Sidewalk, live at the [https://wwwen.discogswikipedia.comorg/dewiki/Gunter-Hampel-Group-Jeanne-Lee-Gunter-Hampel-Group-Jeanne-Lee/release/2679253 The Capacity of this RoomBBC BBC 1980] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video: feat.: [[:Category:Allan Holdsworth|Allan Holdsworth]], [https://en.wikipedia.org/wiki/Brian_Smith_(musician) Brian Smith], [https://de.wikipedia.org/wiki/Arjen_Gorter Arjen GorterTim_Whitehead Tim Whitehead], [[https:Category:Willem Breuker|Willem Breuker]//de.wikipedia.org/wiki/Geoff_Castle Geoff Castle], [[https:Category:Pierre Courbois|Pierre Courbois]//en.wikipedia.org/wiki/Chucho_Merch%C3%A1n Chucho Merchán], [[https:Category:Gunter Hampel|Gunter Hampel]//de.wikipedia.org/wiki/Nic_France Nic France], [[https:Category:Jeanne Lee|Jeanne Lee]//www.allmusic.com/artist/chris-fletcher-mn0000384453/credits Chris Fletcher]: {{#evu:https://www.youtube.com/watch?v=jfAFeVVo_8YBpb_9UE12Gs|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one Level]]'''
[[Category:Willem BreukerNucleus]][[Category:Pierre CourboisIan Carr]][[Category:Gunter Hampel]][[Category:Jeanne LeeAllan Holdsworth]]
