Many seach problems, both combinatorial and AI, can be usefully and elegantly abstracted in terms of a constrained AND/OR tree.

An AND/OR tree is a tree (or, just as frequently, a DAG)
whose internal nodes are labelled either "AND" or
"OR". A *valuation* of an AND/OR tree is an assignment of "TRUE"
or "FALSE" to each of the leaves. Given a tree T and a valuation over
the leaves of T, the values of the internal nodes and of T are defined
recursively in the obvious way:

- An OR node is TRUE if at least one of its children is TRUE.
- An AND node is TRUE if all of its children are TRUE.

The above is an * unconstrained * AND/OR tree. Also common are
* constrained * AND/OR trees, in which the leaves
labelled "TRUE" must satisfy some kind of constraint. A * solution
* to a constrained AND/OR tree is a valuation that satisfies the
constraint and gives the tree the value "TRUE".

A number of different forms of problems over constrained AND/OR trees appear:

- Satisfaction. Given: the tree and the constraint. Problem: Find a valuation that solves the tree. Examples include the SAT problem, and Hamiltonian cycle,
- Optimization. Given: the tree, the constraint, and an objective (real-valued) function over valuations. Problem: find the "best" solution to the tree; that is, the solution that maximizes the objective function. Examples include Vertex cover and Set cover
- Evaluation. Given: The tree and the valuation, both implicitly (that is, a procedure to generate the tree, and a procedure to evaluate leaves). Problem: Determine the value of the tree. Game tree evaluation is a problem of this form.
- Validation. Given: The tree and the valuation, both implicitly. Problem: Find a minimal set of internal nodes that suffice to establish that the tree has value "TRUE". Examples include Horn clause logic, parsing planning.

As we shall see, constraints come in all sizes, shapes, and flavors. We will not attempt to develop here a formal language of constraints; rather, we will just describe each constraint in English. Thus, our aim here is to develop a way of thinking about problems, more than a full-blown formalism.

An AND-OR tree is similar to the idea, in computation theory, of an alternating Turing machine, in the same sense that a non-deterministic algorithm is similar to a non-deterministic Turing machine.

We begin for simplicity with a few combinatorial problems (as it happens, four NP-complete problems). These all involve three-level AND/OR trees, where the root is an AND node; its children are OR nodes; and their children are the leaves. The tree is given explicitly; it is just a rewording of the problem.

(P or Q or not R) and (not P or R or not S) and (P or not Q or S)

We now turn to AI problems. The trees here are often given implicitly rather than explicitly. It is thus important to generate as little of the tree as possible.

The problem is, given a set of axioms in Horn clause form and a goal, show that the goal can be proven from the axioms.

An OR node is a goal to be proven. A goal G has one downward arc for each rule R whose head resolves with G. This leads to an AND node. The children in the AND node are the literals in the tail of R. Thus, a rule is satified if all its subgoals are satisfied (the AND node); a goal is satisfied if it is established by one of its rules (the OR node). The leaves are unit clauses, with no tail, labelled TRUE, and subgoals with no matching rules, labelled FALSE . The constraint is that the variable bindings must be consistent. The figure below show the AND/OR tree corresponding to the following Prolog rule set with the goal "common_ancestor(Z,edward,mary)"

Axioms: /* Z is a common ancestor of X and Y */ R1: common_ancestor(Z,X,Y) :- ancestor(Z,X), ancestor(Z,Y). /* Usual recursive definition of ancestor, going upward. */ R2: ancestor(A,A). R3: ancestor(A,C) :- parent(B,C), ancestor(A,B). /* Mini family tree */ R4: parent(catherine,mary). R5: parent(henry,mary). R6: parent(jane,edward). R7: parent(henry,edward).

S -> NP VP NP -> pronoun NP -> noun VP -> VG VP -> VG NP VG -> verb VG -> modal verb pronoun -> "I" noun -> "fish" modal -> "can" verb -> "can" verb -> "fish"Let N be the number of words in P (3 in our example) An OR node is a pair of a non-terminal T with a subinterval I of [1 .. N]. In our example, one OR node would be the pair < VP, [2..3]>, where [2..3] represents the substring "can fish". The children of the OR node are AND nodes. Each such AND node consists of a pairing of the right-hand side of a production from T together with a corresponding partition of I.

For example, the pair < VP, [2..3]> has two children:

- the list of one pair [< VG,[2..3]>];
- the list of two pairs [< VG,[2..2]>, < NP,[3..3]>].

- the list of two pairs [< NP,[1..2]>, < VP,[3..3]>];
- the list of two pairs [< NP,[1..1]>, < VP,[2..3]>];

solve-ANDOR (in T : OR node; out L : set of OR nodes and leaves) G : OR node; C : AND node or leaf begin L := { T }; repeat until L contains only leaves pick an OR-node G in L and delete it from L; choose a child C of G; add the children of C to L; if it can be determined that there is no valuation consistent with the constraint in which all the nodes of L are TRUE then fail; end repeat; return L; end.

The keywords "pick", "choose" and "fail" are defined as in (Russell and Norvig, 1995, p. 855). That is, "pick" is a choice which may be made arbitrarily, but only one choice need be considered in the state space search. "Choose" is a non-deterministic choice; all sequential combinations of choices are considered through some search technique, and a path of choices that leads to success must be found. "Fail" marks an unsuccessful path of choices.

The state space being searched here may be defined as follows: A state is a set L of OR nodes and leaves. The start state is the singleton set of the root of the tree. The operators on set L are to remove an OR-node G from L, to choose a child C of G and to add its children to L. L is a goal state if it contains only leaves, and if there is a consistent valuation in which all the leaves in L have value TRUE. The search can be pruned if it can be determined that L cannot be extended to a complete valuation that satisfies the constraint. Note that the way in which "pick" is carried out determines the state space; the way in which "choose" is done determines the form of the search through the state space.

For example, consider the problem of finding a valuation satisfying the boolean formula

((P and (Q or R)) or ((not P) and (not Q or R)) or ((not Q) and (not R))) and ((not P or Q) and (P or not Q)) or not R) andThe figures below show the corresponding AND/OR tree, and part of a possible state space in which the set L is implemented as a stack.

((not P and not Q) or R)

How the condition "V cannot be extended to a complete valuation satisfying the constraint" is to be effectuated depends on the nature of the constraint, the cleverness of the programmer, and the trade-off between the cost of performing a complex check here and the gain from pruning the search. Obviously, there is in general no simple way to compute necessary and sufficient conditions for this pruning; if there were, then the problem would be easily solved. Some general categories of pruning rules can be described:

- If the constraint on the leaves is the conjunction of many small constraints, then as soon as one can be completely evaluated to FALSE; then the valuation has failed. For example, in SAT, the constraint is that every atom and its negation have opposite signs. If this fails over valuation V for a single atom, then clearly no extension of V will fix the problem.
- A constraint may require that an objective function F applied to V be no more than some value M. If F is a monotonically increasing function of the leaves marked TRUE in V, then as soon as a partial valuation violates this, it may be pruned. For instance, one may modify the Vertex Cover problem to be a satisfaction problem by asking for a vertex cover of no more than M vertices. Then as soon as V has marked more than M vertices as TRUE, it may be pruned.

Similar non-deterministic algorithms can be written for the optimization, evaluation, and validation problems.

Prolog style search can be implemented by (a) implementing S as a FIFO stack; (b) adding the children of C at the front of S in order from left to right; (c) exploring the choices of C in a depth-first search from left to right among the children of G. Other search protocols can be implemented by modifying the way in which the "pick" and "choose" are carried out.