Depth-First

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Depth-First

Depth-First Node order [1]

Depth-First refers to node traversal algorithms of tree like data structures like search trees. Depth-first examines child nodes before siblings and can easily implemented with recursion using a stack of nodes. It therefor has moderate memory requirements, since only one path from the root to a leaf is kept in memory, which grows proportional with search depth.

Depth-Limited Search

Breadth-First Node order [2]

The depth-limited search, to make the depth-first search find a solution within the depth limit, is the most common search algorithm in computer chess, as described in minimax, alpha-beta and its enhancements. Iterative deepening is a state space search strategy in which a depth-limited search is run repeatedly, with a cumulative node order effectively breadth-first.

See also

Publications

1984 ...

1990 ...

2000 ...

2010 ...

External Links

References

  1. Depth-first search from Wikipedia
  2. Breadth-first search from Wikipedia
  3. quoted by Hans Berliner, Gordon Goetsch (1985). A Study of Search Methods : The Effect of Constraint Satisfaction and Adventurousness. pdf
  4. Paper is mentioned by Richard Korf at Judea Pearl Symposium, 2010
  5. Dovetailing (computer science) from Wikipedia

Up one Level