First, graph-search needs to be transferred into some sort of tree search. There are several strategies dealing with the problem. For example, the procedure presented in Nilsson (1980) is one of the strategies. It generates an explicit graph G and a subset T of graph G called the search tree.

Second, since the branching factor is not a constant, and there is not only one solution path, the depth N at which the goal is located is generally unknown, etc. There is no threshold to be given in the graph-search algorithm. One of the formal algorithm may be given as follows.

Assume that T is a search tree of G, and has m 0-subtrees . The evaluation function (or ) defined in is chosen as the local statistic of each individual node in T. The global statistic of each 0-subtree is defined as follows:

Confidence probability γ(0<γ<1) and the width of confidence intervals are given. Algorithm SAA is performed on . Then we have intervals .

Assume that is the left most one in real axis. If does not intersect with , then choose , prune , and the search continues. If intersects with one of , letting and replacing the width of confidence intervals by , restart SAA,…

Similarly, perform SAA on i-subtrees, i=1,2,…

When N is unknown and T is an infinite tree, SAA might not terminate. In order to overcome the difficulty, an upper bound B, the estimate of depth N, may be chosen. If the search reaches the bound, then a new round of SA search starts.

On the other hand, in SAA, the chosen width of confidence intervals is , where , but is unknown beforehand generally. Thus, we may choose a monotonically decreasing series . At the beginning, is chosen as the width of confidence intervals, if (the left most one in i-subtrees) intersects with one of , then replace by and restart ASM test. In order to prevent the search from not being terminated, a lower bound may be chosen. When if still intersects with , the current search stops and a new round of SAA starts. Of course, at the beginning a proper should be chosen as the width of confidence intervals and perform SAA search, where is chosen according to previous experience and domain knowledge.

G is an AND/OR graph and is a sub-graph generated from G when search reaches a certain stage. is a sub-graph of and satisfies (1) contains starting node , (2) if an expanded AND node p is in , then all sub-nodes of p are in , (3) if an expanded OR node p is in , then just one of its sub-nodes is in , (4) there is no ‘UNSOLVABLE’ node in , (5) n is a node in . In this case, is called a solution base of G containing node n.

In GBF search, a graph evaluation function is used to judge the most promising solution base. Then the graph (base) is expanded according to node evaluation function .

Assume that is a solution base of G containing n. is a sub-graph of G rooted at n. is an expanded part of and has k nodes. For , let be a graph evaluation function of a solution base containing node q (Fig. 6.9). Thus, reflects some property of a set of solution graphs that potentially generated from .

, where F is a combination function of . Assume that is a unique optimal solution graph of G. For any solution base containing n, when expanding rooted at n in order to search , the observation from sub-graph of reflects the possibility of seeking out . Thus, observation can be used as the statistic of ASM test for discriminating the most promising solution base. Therefore, we have a corresponding statistic AND/OR graph search algorithm-SGBF.

Assume that G is a -game tree and has a unique optimal solution. Statistic satisfies a hypothesis similar to Hypothesis I. Using ASM as hypothesis testing method S, in the 2n-th level let the confidence probability be , the width of confidence intervals be , where is a constant, and the threshold be , where c is a constant and independent of n. If the complexity of SGBF is defined as the average number of frontier nodes tested by the algorithm (Pearl, 1984a, 1984b), then we have the following theorem.