Difference between revisions of "Best-First"

From Chessprogramming wiki
Jump to: navigation, search
Line 83: Line 83:
 
* [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]
 
* [[: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
 
* [[: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
: {{#evu:https://www.youtube.com/watch?v=Bpb_9UE12Gs|alignment=left|valignment=top}}
+
: 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=Bpb_9UE12Gs|alignment=left|valignment=top}}
  
 
=References=  
 
=References=  

Revision as of 19:56, 30 December 2020

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 ...

Forum Posts

External Links

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

References

Up one Level