Difference between revisions of "Best-First"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
| 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= | ||
Revision as of 14:05, 24 November 2018
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*.
Contents
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:
- B*
- Bandwidth Search
- Conspiracy Number Search
- FSSS-Minimax
- LCF
- MCαβ
- Monte-Carlo Tree Search
- M & N Procedure
- Proof-Number Search
- SSS* and Dual*
- UCT
Chess Programs
See also
Publications
1960 ...
- 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
- Peter Hart, Nils Nilsson, Bertram Raphael (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, Vol. SSC-4, No. 2, pdf, introducing A*
1970 ...
- Larry Harris (1973). The bandwidth heuristic search. 3. IJCAI 1973, pdf
- Larry Harris (1974). Heuristic Search under Conditions of Error. Artificial Intelligence, Vol. 5, No. 3, also as (1977). The heuristic search: An alternative to the alpha-beta minimax procedure. Chess Skill in Man and Machine
- Larry Harris (1975). The Heuristic Search And The Game Of Chess - A Study Of Quiescence, Sacrifices, And Plan Oriented Play. 4. IJCAI 1975, reprinted (1988) in Computer Chess Compendium
- Larry Harris (1977). The heuristic search: An alternative to the alpha-beta minimax procedure. Chess Skill in Man and Machine
1980 ...
- Judea Pearl (1981). Heuristic search theory: A survey of recent results. IJCAI-81, pdf
- 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. ICCA Journal, Vol. 9, No. 3
- Richard Karp, Yanjun Zhang (1988). A randomized parallel branch-and-bound procedure. STOC '88
- Anup K. Sen, Amitava Bagchi (1989). Fast Recursive Formulations for Best-First Search that allow Controlled use of Memory. IJCAI 1989, pdf
1990 ...
- Steven Skiena (1990). Breadth-First and Depth-First Search. §3.2.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Addison-Wesley
- Nageshwara Rao Vempaty, Vipin Kumar, Richard Korf (1991). Depth-First vs Best-First Search. AAAI-91, pdf
- Richard Korf (1993). Linear-Space Best-First Search. Artificial Intelligence, Vol. 62, No. 1, pdf
- Richard Korf, Max Chickering (1993). Best-first Minimax Search: First Results. AAAI-93
- Weixiong Zhang, Richard Korf (1993). Depth-first vs. best-first search: New results. AAAI-93
- Deniz Yuret (1994). 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. IJCAI-95, Vol. 1, pdf
- Richard Korf, Max Chickering (1996). Best-first minimax search. Artificial Intelligence, Vol. 84, Nos 1-2
- Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1996). Best-First Fixed-Depth Minimax Algorithms. Artificial Intelligence, Vol. 87, Nos. 1-2, 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). A Least-Certainty Heuristic for Selective Search. CG 2000, pdf » LCF
- Ayumu Nagai, Hiroshi Imai (2002). Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees. IEICE transactions on information and systems
2010 ...
- Ari Weinstein, Michael L. Littman, Sergiu Goschin (2013). Rollout-based Game-tree Search Outprunes Traditional Alpha-beta. PMLR, Vol. 24 » FSSS-Minimax
- Jr-Chang Chen, I-Chen Wu, Wen-Jie Tseng, Bo-Han Lin, Chia-Hui Chang (2015). Job-Level Alpha-Beta Search. 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, 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
Forum Posts
- Breadth-first search: revisiting by Sergei S. Markoff, CCC, September 13, 2011
- Help with Best-First Select-Formula by Srdja Matovic, CCC, June 23, 2012
- Re: Perft(15): comparison of estimates with Ankan's result by Ankan Banerjee, CCC, August 26, 2017 » Perft(15)
External Links
- Best-first search from Wikipedia
- Gunter Hampel Group + Jeanne Lee - The Capacity of this Room (1969), YouTube Video
