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 ^{[1]} , 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, as applied for instance in IDA*.

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:

Judea Pearl (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishers Co., Reading, MA. ISBN 0-201-05594-5.

Aske Plaat, Jonathan Schaeffer, Wim Pijls, Arie de Bruin (1995). Best-First Fixed Depth Game Tree Search in Practice. Proceedings of International Joint Conference on Artificial Intelligence (IJCAI-95), Vol. 1, pp. 273-279. Montreal, Quebec, Canada. ps

Richard Korf, Max Chickering (1996). Best-first minimax search. Artificial Intelligence. Vol. 84, No 1-2, pp. 223-239. ISSN 0004-3702. 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

Home * Search * Best-FirstBest-First Searchis 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^{[1]}, 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, as applied for instance in IDA*.

^{[2]}## Table of 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:## See also

## Publications

## 1980 ...

1984).Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Publishers Co., Reading, MA. ISBN 0-201-05594-5.1985).Is Best First Search Really Best?Technical Report TR 85-16, Department of Computer Science, University of Alberta.1986).Selective Search versus Brute Force.ICCA Journal, Vol. 9, No. 31989).Fast Recursive Formulations for Best-First Search that allow Controlled use of Memory. IJCAI 1989, pdf## 1990 ...

1990).Breadth-First and Depth-First Search.§3.2.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley1993).Linear-Space Best-First Search.Artificial Intelligence, Vol. 62, No. 1, pdf1993).Best-first Minimax Search: First Results.AAAI'931993).Depth-first vs. best-first search: New results. AAAI'931994).The Principle of Pressure in Chess. TAINN 19941995).Best-First Fixed Depth Game Tree Search in Practice.Proceedings of International Joint Conference on Artificial Intelligence (IJCAI-95), Vol. 1, pp. 273-279. Montreal, Quebec, Canada. ps1996).Best-first minimax search.Artificial Intelligence. Vol. 84, No 1-2, pp. 223-239. ISSN 0004-3702. pdf1996).Best-First Fixed-Depth Minimax Algorithms.Artificial Intelligence, Vol. 87, Nos. 1-2, pp. 255-293. ISSN 0004-3702, pdf1999).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).A Least-Certainty Heuristic for Selective Search. CG 2000, pdf » LCF2002).Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees. IEICE transactions on information and systems## Forum Posts

## External Links

## References

## What links here?

Up one Level