Editing Combinatorial search (section)

== Lookahead ==
Lookahead is an important component of combinatorial search, which specifies, roughly, how deeply the [[graph (data structure)|graph]] representing the problem is explored. The need for a specific limit on lookahead comes from the large problem graphs in many applications, such as [[computer chess]] and [[computer Go]]. A naive [[breadth-first search]] of these graphs would quickly consume all the memory of any modern computer. By setting a specific lookahead limit, the algorithm's time can be carefully controlled; its time [[exponential growth|increases exponentially]] as the lookahead limit increases.

More sophisticated search techniques such as [[alpha–beta pruning]] are able to eliminate entire subtrees of the search tree from consideration. When these techniques are used, lookahead is not a precisely defined quantity, but instead either the maximum depth searched or some type of average.