25,161
edits
Changes
Created page with "'''Home * Search * Best-First''' FILE:Breadth-first-tree.svg|border|right|thumb|Breadth-First Node order <ref>[https://en.wikipedia.org/wiki/Breadth-first..."
'''[[Main Page|Home]] * [[Search]] * Best-First'''
[[FILE:Breadth-first-tree.svg|border|right|thumb|Breadth-First Node order <ref>[https://en.wikipedia.org/wiki/Breadth-first_search Breadth-first search from Wikipedia]</ref> ]]
'''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]], as applied for instance in [https://en.wikipedia.org/wiki/IDA* IDA*].
=Two-Player=
Following best-first algorithms were invented and implemented for computer chess programs as well for other two-player [https://en.wikipedia.org/wiki/Zero-sum_(game_theory) zero-sum] board [[Games|game]] players with [https://en.wikipedia.org/wiki/Perfect_information perfect information]:
* [[SSS* and Dual*]]
* [[B*]]
* [[Conspiracy Number Search]]
* [[Richard P. Cochran#LCF|LCF]]
* [[Monte-Carlo Tree Search]]
* [[Proof-Number Search]]
* [[UCT]]
=See also=
* [[Depth-First]]
* [[MTD(f)]]
* [[NegaC*]]
* [[Perft#15|Perft(15)]]
* [[Priority Queue]]
* [[Queue]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|SSS* and Dual* as MT]]
=Publications=
==1980 ...==
* [[Judea Pearl]] ('''1984'''). ''Heuristics: Intelligent Search Strategies for Computer Problem Solving''. Addison-Wesley
* [[Alexander Reinefeld]], [[Tony Marsland]], [[Jonathan Schaeffer]] ('''1985'''). ''Is Best First Search Really Best?'' Technical Report TR 85-16, Department of Computer Science, [[University of Alberta]].
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Anup K. Sen]], [[Amitava Bagchi]] ('''1989'''). ''Fast Recursive Formulations for Best-First Search that allow Controlled use of Memory''. [[Conferences#IJCAI|IJCAI 1989]], [http://www.ijcai.org/Past%20Proceedings/IJCAI-89-VOL1/PDF/047.pdf pdf]
==1990 ...==
* [[Steven Skiena]] ('''1990'''). ''Breadth-First and Depth-First Search.'' §3.2.5 in [http://www.amazon.com/exec/obidos/ASIN/0521806860/ref=nosim/weisstein-20 Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica], Addison-Wesley
* [[Richard Korf]] ('''1993'''). ''Linear-Space Best-First Search.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 62, No. 1, [http://www.aaai.org/Papers/AAAI/1992/AAAI92-082.pdf pdf]
* [[Richard Korf]], [[Max Chickering]] ('''1993'''). ''[http://www.aaai.org/Library/Symposia/Fall/1993/fs93-02-006.php Best-first Minimax Search: First Results].'' [http://www.aaai.org/Conferences/AAAI/aaai93.php AAAI'93]
* [[Mathematician#WZhang|Weixiong Zhang]], [[Richard Korf]] ('''1993'''). ''[http://dl.acm.org/citation.cfm?id=1867385 Depth-first vs. best-first search: New results]''. [http://www.aaai.org/Conferences/AAAI/aaai93.php 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'''). ''Best-First Fixed Depth Game Tree Search in Practice.'' [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai95.html IJCAI-95], Vol. 1, [https://www.ijcai.org/Proceedings/95-1/Papers/036.pdf pdf]
* [[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 ...==
* [[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]]
* [[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 ...==
* [[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
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=40384 Breadth-first search: revisiting] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], September 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=44165 Help with Best-First Select-Formula] by [[Srdja Matovic]], [[CCC]], June 23, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=64983&start=9 Re: Perft(15): comparison of estimates with Ankan's result] by [[Ankan Banerjee]], [[CCC]], August 26, 2017 » [[Perft#15|Perft(15)]]
=External Links=
* [https://en.wikipedia.org/wiki/Best-first_search Best-first search from Wikipedia]
* [[Videos#GunterHampel|Gunter Hampel]] Group + [[Videos#JeanneLee|Jeanne Lee]] - [https://www.discogs.com/de/Gunter-Hampel-Group-Jeanne-Lee-Gunter-Hampel-Group-Jeanne-Lee/release/2679253 The Capacity of this Room] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [https://de.wikipedia.org/wiki/Arjen_Gorter Arjen Gorter], [[Videos#WillemBreuker|Willem Breuker]], [[Videos#PierreCourbois|Pierre Courbois]], [[Videos#GunterHampel|Gunter Hampel]], [[Videos#JeanneLee|Jeanne Lee]]
: {{#evu:https://www.youtube.com/watch?v=jfAFeVVo_8Y|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one Level]]'''
[[FILE:Breadth-first-tree.svg|border|right|thumb|Breadth-First Node order <ref>[https://en.wikipedia.org/wiki/Breadth-first_search Breadth-first search from Wikipedia]</ref> ]]
'''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]], as applied for instance in [https://en.wikipedia.org/wiki/IDA* IDA*].
=Two-Player=
Following best-first algorithms were invented and implemented for computer chess programs as well for other two-player [https://en.wikipedia.org/wiki/Zero-sum_(game_theory) zero-sum] board [[Games|game]] players with [https://en.wikipedia.org/wiki/Perfect_information perfect information]:
* [[SSS* and Dual*]]
* [[B*]]
* [[Conspiracy Number Search]]
* [[Richard P. Cochran#LCF|LCF]]
* [[Monte-Carlo Tree Search]]
* [[Proof-Number Search]]
* [[UCT]]
=See also=
* [[Depth-First]]
* [[MTD(f)]]
* [[NegaC*]]
* [[Perft#15|Perft(15)]]
* [[Priority Queue]]
* [[Queue]]
* [[SSS* and Dual*#SSStarandDualStarAsMT|SSS* and Dual* as MT]]
=Publications=
==1980 ...==
* [[Judea Pearl]] ('''1984'''). ''Heuristics: Intelligent Search Strategies for Computer Problem Solving''. Addison-Wesley
* [[Alexander Reinefeld]], [[Tony Marsland]], [[Jonathan Schaeffer]] ('''1985'''). ''Is Best First Search Really Best?'' Technical Report TR 85-16, Department of Computer Science, [[University of Alberta]].
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
* [[Anup K. Sen]], [[Amitava Bagchi]] ('''1989'''). ''Fast Recursive Formulations for Best-First Search that allow Controlled use of Memory''. [[Conferences#IJCAI|IJCAI 1989]], [http://www.ijcai.org/Past%20Proceedings/IJCAI-89-VOL1/PDF/047.pdf pdf]
==1990 ...==
* [[Steven Skiena]] ('''1990'''). ''Breadth-First and Depth-First Search.'' §3.2.5 in [http://www.amazon.com/exec/obidos/ASIN/0521806860/ref=nosim/weisstein-20 Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica], Addison-Wesley
* [[Richard Korf]] ('''1993'''). ''Linear-Space Best-First Search.'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 62, No. 1, [http://www.aaai.org/Papers/AAAI/1992/AAAI92-082.pdf pdf]
* [[Richard Korf]], [[Max Chickering]] ('''1993'''). ''[http://www.aaai.org/Library/Symposia/Fall/1993/fs93-02-006.php Best-first Minimax Search: First Results].'' [http://www.aaai.org/Conferences/AAAI/aaai93.php AAAI'93]
* [[Mathematician#WZhang|Weixiong Zhang]], [[Richard Korf]] ('''1993'''). ''[http://dl.acm.org/citation.cfm?id=1867385 Depth-first vs. best-first search: New results]''. [http://www.aaai.org/Conferences/AAAI/aaai93.php 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'''). ''Best-First Fixed Depth Game Tree Search in Practice.'' [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai95.html IJCAI-95], Vol. 1, [https://www.ijcai.org/Proceedings/95-1/Papers/036.pdf pdf]
* [[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 ...==
* [[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]]
* [[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 ...==
* [[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
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=40384 Breadth-first search: revisiting] by [[Sergei Markoff|Sergei S. Markoff]], [[CCC]], September 13, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=44165 Help with Best-First Select-Formula] by [[Srdja Matovic]], [[CCC]], June 23, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=64983&start=9 Re: Perft(15): comparison of estimates with Ankan's result] by [[Ankan Banerjee]], [[CCC]], August 26, 2017 » [[Perft#15|Perft(15)]]
=External Links=
* [https://en.wikipedia.org/wiki/Best-first_search Best-first search from Wikipedia]
* [[Videos#GunterHampel|Gunter Hampel]] Group + [[Videos#JeanneLee|Jeanne Lee]] - [https://www.discogs.com/de/Gunter-Hampel-Group-Jeanne-Lee-Gunter-Hampel-Group-Jeanne-Lee/release/2679253 The Capacity of this Room] (1969), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [https://de.wikipedia.org/wiki/Arjen_Gorter Arjen Gorter], [[Videos#WillemBreuker|Willem Breuker]], [[Videos#PierreCourbois|Pierre Courbois]], [[Videos#GunterHampel|Gunter Hampel]], [[Videos#JeanneLee|Jeanne Lee]]
: {{#evu:https://www.youtube.com/watch?v=jfAFeVVo_8Y|alignment=left|valignment=top}}
=References=
<references />
'''[[Search|Up one Level]]'''
