graph TB
   s["(1,2)"] -- right -->  r["(2,2)"] -- right --> rr["(3,2) obstacle"]
   style rr fill:red
   r -- down --> rd["(2,3)"] -- right --> rdr["(3,3)"] -- right --> rdrr["(4,3)"] -- right --> rdrrr["(5,3) off map"]
   style rdrrr fill:red
   rdrr -- down --> rdrrd["(4,4)"]
   style rdrrd fill:green
   rdr -- down --> rdrd["(3,4) obstacle"]
   style rdrd fill:red
   rd -- down --> rdd["(2,4)"] -- right --> rddr["(3,4) obstacle"]
   style rddr fill:red
   rdd -- down --> rddd["(2,5) off map"]
   style rddd fill:red
   s -- down --> d["(1,3)"] -- right --> dr["(2,3)"]
   dr["(2,3)"] -- right --> drr["(3,3)"] -- right --> drrr["(4,3)"] -- right --> drrrr["(5,3) off map"]
   style drrrr fill:red
   drrr -- down --> drrrd["(4,4)"]
   style drrrd fill:green
   drr -- down --> drrd["(3,4) obstacle"]
   style drrd fill:red
   dr -- down --> drd["(2,4)"] -- right --> drdr["(3,4) obstacle"]
   style drdr fill:red
   drd -- down --> drdd["(2,5) off map"]
   style drdd fill:red
   d -- down --> dd["(1,4)"] -- right --> ddr["(2,4)"] -- right --> ddrr["(3,4) obstacle"]
   style ddrr fill:red
   dd -- down --> ddd["(1,5) off map"]
   style ddd fill:red
   ddr -- down --> ddrd["(2,5) off map"]
   style ddrd fill:red

Obviously real silicon is not clairvoyant.  Neither are quantum computers.  So if the system is going to find a successful path through a choice tree, it's going to have to do tree search.

If you're reading this chapter, then you've probably taken a data structures course and studied depth-first and breadth-first search, and probably Dijkstra's algorithm.  If you've taken an introductory AI course, you've probably also studied heuristic search algorithms like A* and beam search.  Any of these could be used in principle, although to use Dijsktra or heuristic search the programmer would need to specify some cost or heuristic function to optimize.

Depth-first search

In practice however, most systems, such as Prolog, use depth-first search.  And although breadth-first has the same asymptotic complexity (i.e. they're both worst-case linear time and space), in practice DFS is usually faster and uses less space.

Another name for depth-first search of a choice tree is backtracking.

Infinite recursion

The disadvantage of DFS compared to the other search methods is that if the tree has any infinite paths – which would correspond to infinite loops or infinite recursions – then it can get lost in them and never investigate the other paths.  This is the reason most nondeterministic languages look not for a random path like NDScript, but for the leftmost path in the tree.  That lets the programmer steer the system around infinite recursions, for example, by making sure the system tries base cases before recursive cases.  NDScript lets you do this too, by saying choose first rather than choose.

Let's talk some more about solution choice.