Difference between revisions of "Best-First"

From Chessprogramming wiki
Jump to: navigation, search
 
(13 intermediate revisions by 2 users not shown)
Line 5: Line 5:
 
'''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 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*].  
+
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=  
 
=Two-Player=  
Line 11: Line 11:
 
* [[B*]]
 
* [[B*]]
 
* [[Bandwidth Search]]
 
* [[Bandwidth Search]]
 +
* [[Best-First Minimax Search]]
 
* [[Conspiracy Number Search]]
 
* [[Conspiracy Number Search]]
 
* [[Ari Weinstein#FSSS-Minimax|FSSS-Minimax]]
 
* [[Ari Weinstein#FSSS-Minimax|FSSS-Minimax]]
Line 20: Line 21:
 
* [[SSS* and Dual*]]
 
* [[SSS* and Dual*]]
 
* [[UCT]]
 
* [[UCT]]
 +
 +
=Some Chess Programs=
 +
* [[Centaur]]
 +
* [[HiTech|HiTech B*]]
 +
* [[Leela Chess Zero]]
 +
* [[Rocinante]]
  
 
=See also=  
 
=See also=  
Line 40: Line 47:
 
* [[Larry Harris]] ('''1977'''). ''The heuristic search: An alternative to the alpha-beta minimax procedure.'' [[Chess Skill in Man and Machine]]  
 
* [[Larry Harris]] ('''1977'''). ''The heuristic search: An alternative to the alpha-beta minimax procedure.'' [[Chess Skill in Man and Machine]]  
 
==1980 ...==  
 
==1980 ...==  
* [[Judea Pearl]] ('''1984'''). ''Heuristics: Intelligent Search Strategies for Computer Problem Solving''. Addison-Wesley
+
* [[Judea Pearl]] ('''1981'''). ''Heuristic search theory: A survey of recent results''. [[Conferences#IJCAI1981|IJCAI-81]], [http://ijcai.org/Past%20Proceedings/IJCAI-81-VOL%201/PDF/100.pdf pdf]
 +
* [[Judea Pearl]] ('''1984'''). ''Heuristics: Intelligent Search Strategies for Computer Problem Solving''. [https://en.wikipedia.org/wiki/Addison-Wesley 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]].
 
* [[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]]
 
* [[Hermann Kaindl]], [[Helmut Horacek]], [[Marcus Wagner]] ('''1986'''). ''Selective Search versus Brute Force.'' [[ICGA Journal#9_3|ICCA Journal, Vol. 9, No. 3]]
 +
* [[Richard Karp]], [[Yanjun Zhang]] ('''1988'''). ''[https://dl.acm.org/citation.cfm?id=62212.62240 A randomized parallel branch-and-bound procedure]''. [https://dblp.uni-trier.de/db/conf/stoc/stoc88.html STOC '88]
 
* [[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]
 
* [[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 ...==  
 
==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
+
* [[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], [https://en.wikipedia.org/wiki/Addison-Wesley Addison-Wesley]
 
* [[Nageshwara Rao Vempaty]], [[Vipin Kumar]], [[Richard Korf]]  ('''1991'''). ''Depth-First vs Best-First Search''. [[Conferences#AAAI-91|AAAI-91]], [https://www.aaai.org/Papers/AAAI/1991/AAAI91-067.pdf pdf]
 
* [[Nageshwara Rao Vempaty]], [[Vipin Kumar]], [[Richard Korf]]  ('''1991'''). ''Depth-First vs Best-First Search''. [[Conferences#AAAI-91|AAAI-91]], [https://www.aaai.org/Papers/AAAI/1991/AAAI91-067.pdf pdf]
 
* [[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]] ('''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]
Line 51: Line 60:
 
* [[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]]
 
* [[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
 
* [[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]
+
* [[Aske Plaat]], [[Jonathan Schaeffer]], [[Wim Pijls]], [[Arie de Bruin]] ('''1995, 2015'''). ''Best-First Fixed Depth Game Tree Search in Practice.'' [[Conferences#IJCAI1995|IJCAI-95]], [https://arxiv.org/abs/1505.01603 arXiv:1505.01603]
 
* [[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
 
* [[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]
+
* [[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
 
* [[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
 
* [[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 ...==  
 
==2000 ...==  
Line 59: Line 68:
 
* [[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]
 
* [[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 ...==
 
==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]]
 
* [[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
 
* [[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 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
 
* [[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=  
 
=Forum Posts=  
Line 71: Line 84:
 
=External Links=  
 
=External Links=  
 
* [https://en.wikipedia.org/wiki/Best-first_search Best-first search from Wikipedia]
 
* [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
+
* [[:Category:Ian Carr|Ian Carr]] & [[:Category:Nucleus|Nucleus]] - Sidewalk, live at the [https://en.wikipedia.org/wiki/BBC BBC 1980], [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]]
+
: feat.: [[:Category:Allan Holdsworth|Allan Holdsworth]], [https://en.wikipedia.org/wiki/Brian_Smith_(musician) Brian Smith], [https://de.wikipedia.org/wiki/Tim_Whitehead Tim Whitehead], [https://de.wikipedia.org/wiki/Geoff_Castle Geoff Castle], [https://en.wikipedia.org/wiki/Chucho_Merch%C3%A1n Chucho Merchán], [https://de.wikipedia.org/wiki/Nic_France Nic France], [https://www.allmusic.com/artist/chris-fletcher-mn0000384453/credits Chris Fletcher]
: {{#evu:https://www.youtube.com/watch?v=jfAFeVVo_8Y|alignment=left|valignment=top}}
+
: {{#evu:https://www.youtube.com/watch?v=Bpb_9UE12Gs|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Search|Up one Level]]'''
 
'''[[Search|Up one Level]]'''
 +
[[Category:Nucleus]]
 +
[[Category:Ian Carr]]
 +
[[Category:Allan Holdsworth]]

Latest revision as of 13:42, 18 November 2021

Home * Search * Best-First

Breadth-First Node order [1]

Best-First Search is a state space search to traverse nodes of tree-like data structures (i. e. search trees) in breadth-first manner. It is usually implemented with a priority queue instead of the FIFO of breadth-first [2] , 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 A* are used for path finding in combinatorial search and puzzles. Iterative deepening is a technique to turn depth-first searches into best-first with the advantage space grows linear rather than exponential with increasing search depth [3], as applied for instance in IDA*.

Two-Player

Following best-first algorithms were invented and implemented for computer chess programs as well for other two-player zero-sum board game players with perfect information:

Some Chess Programs

See also

Publications

1960 ...

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

2020 ...

Forum Posts

External Links

feat.: Allan Holdsworth, Brian Smith, Tim Whitehead, Geoff Castle, Chucho Merchán, Nic France, Chris Fletcher

References

Up one Level