--- title: "Heuristic Search Theory: Survey of Recent Results" authors: - "Judea Pearl" doi: "" url: "https://ijcai.org/proceedings/1981/104" pdf: "https://ijcai.org/proceedings/1981/0104.pdf" venue: "Proceedings of the Seventh International Joint Conference on Artificial Intelligence" year: 1981 pages: "554-561" track: "Search" keywords: --- # Heuristic Search Theory: Survey of Recent Results Judea Pearl *Proceedings of the Seventh International Joint Conference on Artificial Intelligence*, pages 554-561. ## Abstract This paper summarizes recent analytical investigations of the mathematical properties of heuristics and their influence on the performance of common search techniques. The results are reported without proofs, together with discussions of motivations and interpretations. Highlights include the following: relations between the precision of the heuristic estimates and the average complexity of the search, comparisons of the average complexities of A* and BACKTRACKING, procedures for comparing and combining non-admissible heuristic functions, the influence of the weight ul [in f = (1-w)g + wh] on the complexity of A*, determination of the branching factors of alpha-beta and SSS*, and the effects of successor ordering on the complexity of alpha-beta and of search depth on the quality of decisions. ## Full text ## 1. 3 The Mean Complexity of .A* Under Distance­ Dependent Errors The quality of the heuristic estimates h(n) often improves with proximity to the goal state. This fact can be modeled by assuming that the typi­ cal magnitude of the errors h*(n)-h(n) increases proportionally to the distance h*(n), or that for all nodes in the tree, the relative errors Y(n) = [h*(n)-h(n)]/h*(n) are likely to be bounded away from zero. - Theorem 2: If, for every node in the tree, the probability that the relative error exceeds so~e fixed positive quantity e: is greater than 1/m, then the average complexity of A* is expo­ nential inN (Huyn et al., [8]). Theorem 2 implies that in order to avoid an exponential growth of E(Z), the magnitude of the typical errors in the tree should increase slower than linearly with the distance from the goal. Theorem 2 extends the results of Gaschnig [6] from the worst case to the average case analysis. Gaschnig has shown that if at all nodes off the solution path the relative errors stay at their max­ imal value above some fixed constant, then the com­ plexity of A* is exponential. Evidently, the expo­ nential explosion is not eliminated by diffusing the errors smoothly over a continuous interval. This result delineates the spectrum of the precision-complexity exchange by two points. On one extreme we have Pohl [5] and Gaschnig's [6] results stating that if the absolute errors h*(n)-h(n) are bounded by a fixed quantity, then A* is guaranteed a linear complexity. On the other extreme, Theorem 2 states that if these errors h*(n)-h(n) grow lin­ early with h*(n), A* exhibits an exponential com­ plexity. The following result quantifies the pre­ cision-complexity exchange over the interior of its spectrum, thus determining how accurate the estimates must be in order to guarantee a polynomial complexity. - Definition: A heuristic estimate h(·) is said to 1nduce a typical error of order t(n) if for all nodes in an m-ary tree there exist two fixed positive quantities e: and 6, and a normalizing function~(·), such that: and simultaneously: The first condition guarantees that the ¢­ normalized errors [h*(n)-h(n)]/~[h*(n)] remain bounded away from zero with sufficiently high prob­ ability. The second condition insists that the ~­ normalized error is likely to remain finite even when the distance to the goal increases indefinitely. The proportional errors treated in Theorem 2 above are represented bY. the special case ~(N) = N, whereas the absolute errors analyzed by Pohl corre­ spond to ~(N) = constant. Theorem 3: If the typical error induced by h(·) is of order ¢(N) and ~ ~(N)/N < ®, then the mean complexity of A* is given by: where c is a constant and G(N) is at most O(N2). Moreover, if only condition 1 (or 2) is known to hold, then the expression in (3) constitutes a lower or upper bound, respec­ tively (Pearl, (g]) . The exponential relationship exhibited in Theorem 3 implies that the precision-complexity exchange for A* is fairly "inelastic," requiring that highly precise heuristics be devised to con­ tain the search complexity within a reasonable growth rate. For example, Theorem 3 implies that if the typical distance-estimation error increases faster than logarithmically in the actual distance to the goal, then the mean complexity of A* grows faster than Nk for any finite k regardless of the shapes of the distribution functions. Thus, a nec­ essary and sufficient condition for maintaining a polynomial search complexity is that A* be guided by heuristics with logarithmic precision, that is, 4> ( n) = 0 ( 1 og N). ## 1.4 Comparison to BACKTRACKING and the Effect of Multiple Goals The BACKTRACKING search strategy [10] also employs an element of the best-first principle but the "best," lowest f, is chosen only among the set of newly generated nodes, not among all the nodes encountered in the past. Consequently, once BACK­ TRACKING decides to expand a node not lying on a solution path, the entire tree beneath that node must be irrevocably expanded down to a given depth bound before another path is tried. Thus, assuming that node ordering in BACKTRACKING is 90verned by the same heuristic function f(n) = g(n) + h{n) which guides A*, the complexity ZB depends on how often each node n on the solution path is assigned an estimate f(n) higher than its off-course siblings. Assuming further that the cp-normalized errors Y = [h*-h]/cp(h*) are identically distributed over all nodes, that P(Y=O) = B and lim cp(N)/N < ~. one obtains [9]: N-- implying that BACKTRACKING's complexity retains its exponential character in spite of any improve­ ment in heuristic precision. Whereas the parameters Fy(·), cp(.), characterizing the informedness of h(·), have a direct impact on the growth-rate of the com­ plexity of A* (see, for example, Theorem 3) they have only a tenuous influence upon the complexity of BACKTRACKING strategies via the multiplication constant (l-s2). Consequently, if an admissible distance-estimating heuristic is available, then A* is a more effective instrument for converting this information into appreciable savings in search time. One may wonder whether A* retains this effec­ tiveness when the search tree contains multiple goal states. Clearly the presence of sub-optimal solutions should cause some off-track nodes to obtain deceptively low h and would, therefore, increase the number of nodes expanded. An extreme model whereby all nodes at depth N+l are goal nodes while only one goal exists at depth N will give an idea of the magnitude of this effect. Under this condition the expected complexity of A* becomes [9]: N where ·(N) = L 1/cp(k) and G(N) is at most O(N2). Hence, A* k=O would retain its exponential com­ plexity regardless of the character of the precision function cp; its growth rate, however, still would be affected by cp. For example, when 4> = canst. ~i.e., bounded absolute errors), E(Z) becomes O[(m') ] where m' = mP(h*-h > 1); for cp(N) = N we obtain E(Z) = G(N) N-a [m(l-B)]N. Thus, although the pre­ sence of multiple solutions may significantly impair the ability of A* to benefit from improved precision, the complexity of A* remains more sensitive to error reduction than that of BACKTRACK­ ING. BACKTRACKING control strategies, on the other hand, have several advantages over A*. They are typically simpler to implement and, more signifi­ cantly, require much less storage. Whereas A* stores all expanded nodes in either OPEN or CLOSED lists, BACKTRACKING need only store nodes along a single path, and therefore has a storage complexity linear inN. Equation (4), though, reveals the price paid for this storage economy--an exponential time-complexity coupled with ineffective utilization of heuristic knowledge. Mixed search strategies combining the storage economy of BACKTRACKING with the time savings of A* warrant empirical and theo­ retical investigations. ## 2.0 THE COMPLEXITY OF NON-ADMISSIBLE HEURISTICS ## 2.1 Introduction Admissible search strategies are cursed with two basic defects: they spend a disproportionate amount of time investigating all equally meritorious alternative solutions, and they-limit the selection of heuristic functions to only those which never over-estimate the optimal completion cost. ~ literature on heuristic search contains many exam­ ples of non-admissible heuristics which empirically out-perform any known admissible heuristics and yet very frequently discover the optimal path. The aims of theoretical investigations in this area are to answer several basic and pressing ques­ tions which until now have been treated only .by lengthy simulations in a few, specific domains. When are non-admissible heuristics safe from a cat­ astrophic over-computation? How often are they likely to miss the optimal solution? When is one heuristic better than another? Is admissibility a virtue in cases where just any solution will do? How should one "debias" a given admissible heuris­ tic? How should one aggregate the estimates pro­ vided by several heuristic functions? The results reported in the following sections provide answers to some of these questions and pave the way to resolve others. ## 2.2 Conditions for Node Expansion The analysis of mean run time of admissible best-first algorithms is facilitated by the simpli­ city of the condition for expansion. We know that every node n in OPEN whose evaluation function satisfies f(n) < f*(root) must eventually be ex­ panded and conversely, that every node satisfying f(n) > f*(root) will not be expanded. In our standard model of an m-ary tree with one goal at depth N; these conditions amount to deciding whether f(n) is larger or smaller than N [8]. The expansion condition for non-admissible heuristics is complicated by the fact that f(n) may exceed N at several places along the solution path. This leads to the more general expansion condition for nodes in OPEN: where n~ n~ n~ ... n~ are nodes along the solution path and n~ is the deepest corrmon ancestor of G and n (see Figure 1): Figure 1 ![Image](https://ijcai.org/proceedings/1981/fulltext/104/image_000000_f8e1075bbdbd968f6049a7d419e873a8c54cf9e24d2e6ca9aed185ea01ff6d7a.png) The right-hand side of {6) is a random variable Lj whose distribution determines the probability of e~panding any node in subtree T·. The probabilistic analysis of comelexity is facil1tated by the follow­ ing theorem [llj which permits us to replace Lj with a deterministic quantity. Theorem 4: Let the ~-normalized errors Y - [h-h*]/~(h*) along the solution path be independent random variables all having a non­ zero over-estimation probability so that P[Y(n~) < y 1 ] > 0 for some Y 1 < 0 and all i. For sufficien~ly large j, the random variable Lj =max f(n . ) is almost sure to exceed the O~ i < j 1 quantity N- ~(j)y 1 · To put it bluntly, if anything can go wrong on the solution path, it almost surely will. Theorem 4 implies that if y is the maximal common over­ estimation error ~or all nodes along the solution path (i.e. , y = in f {y 1 J P [Y ( n~) < y 1 ] > 0 'd i} ), then we are sa~e in assuming t~at this maximal over-estimation indeed took place along the solu­ tion path and in substituting it in the expansion condition, which becomes: Theorem 4 makes this condition, normally invoked in worst case analysis, applicable to average case analysis as well. ## 2. 3 When is One Heuristic Better Than Another if Over-Estimations are Possible? If h1 and h2 are both admissible then the in­ equality h 1 < h 2 also implies that h2 is a closer approximation to h* and would naturally lead to a more efficient search. This simple criterion of choosing the highest cost estimates breaks down when over-estimations are encountered. Over­ estimations reduce the search complexity when they occur at off-track nodes and increase it when they take place along the solution path. The exact effect of over-estimations on the mean run time of A* depends on a delicate balance between these two forces. The following set of results are derived under the assumption that the relative errors Y(n) = [h*(n)-h(n)]/h*(n) are independent and iden­ tically distributed random variables. Letting H = h/h*, it is convenient to characterize the errors by the distribution function FH{x) = P([h/h*] ~ x). We will say that h1 is more efficient than h2 if the use of h1 results in a mean complexity lower or equal to that of h2. Definition: A random variable X is said to have an upper support r iff X ~ r and P(X ~ x) < 1 for all x < r. Theorem 5: Let hl(·) and h2(·) be two heuristic functions such that H1 = h1/h* and H2 = h2/h* possess the same upper support r. If FH (x) ~ FH (x) for all x ~ r, then H2 is more 1 2 efficient than H1. Theorem 5 generalizes the criterion of Theorem 1 to the non-admissible case simply by stating that the heuristic whose density is more concentrated around its upper support is the one to be preferred. It is a reasonable criterion in the admissible case where such concentration also means increased accu­ racy. It is somewhat surprising, though, in the non-admissible case where concentration around the upper support and accuracy may not go hand in hand. In Figure 2, for example, h1 is a more accurate heuristic since it assigns a greater weight to the neighborhood of the correct estimate h/h* = 1. Still, Theorem 5 proclaims h2 as the more efficient heuristic. Figure 2 ![Image](https://ijcai.org/proceedings/1981/fulltext/104/image_000001_28ddb3b101d9c062a7db59063c7a4404057cb71c23b3e7af447c1aad12974a8c.png) The next theorem establishes a preference between heuristics with different upper supports. Theorem 6: Given two heuristic functions h1( . ) and h2(·) such that H1 and H2 have the upper sup­ ports r 1 and r 2 (1 ~ r 1 < r2), respectively, if FH 1 (x[r1/r2Jl ~ FH?(x) for all x < r2, then h1 is str1ctly more efficient than h2. Figure 3 below illustrates this preference criterion graphically. The two dotted distribution functions represent heuristics inferior to hl be­ cause they lie above its stretched distribut1on FH 1 ([r1/rz]x). Note that hz can be stochastically gr~ater than h1 and still be inferior to it as il­ lustrated by the lower dotted curve. Simply stated, Theorem 6 implies that Hz is inferior to H1 if it is stochastically smaller than or equal to (r2;r1)Hl. Thus, once a heuristic h possesses an upper support which is greater than unity, all attempts to fur­ ther boost its value by using f = g + ah and a > l will only degrade its search performance. This has a far-reaching consequence for "debiasing" tech­ niques. When a heuristic h is known to underesti­ mate h* consistently, that is, when r < l, then the weighted combination f = (1-w)g + wh (w > l/2) may be used [12] to "debias" f and compensate for h's underestimation. Theorem 6 states that w should not be made too large; the mean complexity mono­ tonically increases with w once w is greater than 1/l+r. Figure 3 ![Image](https://ijcai.org/proceedings/1981/fulltext/104/image_000002_404d7d03dd74cb7263e20ff57f7c97c1961fb0d3b0c1e2b31a40f7b4befdf2c4.png) The quantity 1/l+r, of course, is the highest value of w which renders f admissible and, clearly, maintaining w below that limit is necessary if one wishes to guarantee that A* will not miss the opti­ mal solution. However, the preceding results demon­ strate that admissibility constraints are also bene­ ficial in cases where only one solution exists and performance is judged solely-by the effort required to discover it. Moreover, since admissible heuris­ tics always improve by increasing the weight of h (Theorem 1), we conclude that the admissibility limit w = l/l+r is optimal. Figure 4 demonstrates the effect of the weight w on the average complexity E(Zwl of A* for three cases: r = l/2 (h admissible with 50% underestima­ tion bias), r = l (h admissible and unbiased), and r = 2 (h non-admissible with 200% overestimation bias). The ordinate represents the growth rate logm E(Zwl normalized by that of exhaustive search w = 0. The three curves were computed with the assumption that the relative errors are distributed by the truncated exponential distribution: Variations in the underlying distribution will only change the amplitudes of these curves but not their essential characteristics. The optimality of the admissibility limit w = l/l+r is clearly demonstrated by the sharp dips of the curves at this point. Note that when w is made too high the aver­ age complexity of A* may exceed that of an exhaus­ tive search and may become unbounded for w = l . This is to be expected since reliance on h alone may cause A* to explore depths greater than N. Figure 4 ![Image](https://ijcai.org/proceedings/1981/fulltext/104/image_000003_714d344fd236be2f7ef80595b01f46316ed9fadc5a7b1ead2a82992a4079389f.png) These results lead to a very simple procedure of combining information from several heuristic sour«es, admissible as well as non-admissible. Given the set of estimates h1, hz, ... hk having upper supports r1, rz, rk· respectively, the combination rule: would yield a more efficient estimate than any of its constituents. The division by the upper support removes the bias from each constituent and renders it admissible, with r = 1; the "max" operator fur­ ther improves the estimate by rendering it larger than each of its constituents, while also maintain­ ; ng r = 1. Needless to state, these manipulations only diminish the growth rate of the mean search effort but cannot turn its complexity from exponential to polynomial. The exponential complexity implied by Theorem 2 remains valid for non-admissible heuris­ tics as long as the condition: is satisfied by all nodes for some positive con­ stant £. ## 3.0 GAME-SEARCHING ## 3.1 Introduction Game-sea.ching differs from shortest-path search in two essential ways. First, the solution desired is not a simple sequence of moves, a path, but a strategy, a subtree, which specifies the player's best response to every conceivable move of the opponent. Second, the quality of a given strat­ egy is determined solely by the properties of the terminal nodes it contains, not by the cost of the paths leading to these nodes. The theoretical results reported in this paper concern three main issues: establishing absolute limits on the complexity of game-searching proce­ dures, comparing performances of known procedures under various conditions, and evaluating the quality of a decision as a function of the search effort. The model most frequently used for evaluating the performance of game-searching methods consists of a uniform tree of depth d (d even} and degree n, where the terminal positions are assigned random values independently drawn from a common distribu­ tion F. We shall refer to such a tree as a (d, n, F)-tree. The expected number of terminal nodes examined during the search and its branching factor have become standard criteria for the com­ plexity of the search method. Definition: Let A be a deterministic algorithm which searches a (d, n, F)-tree to determine the minimax value of its root, and let IA(d, n, F) denote the expected number of ter­ minal positions examined by A. The quantity: ![Image](https://ijcai.org/proceedings/1981/fulltext/104/image_000004_791f12b1d46605d2948b141c76235bad2544b4ec9f22505350551a6cdcb435b8.png) is called the branching factor corresponding to the algorithm A. The results reported in this paper are direct con­ sequences of a somewhat sur~rising convergence prop­ erty of tall minimax trees Ll3] : Theorem 7: The root value of a (d, n, F)-tree with a continuous, strictly increasing terminal distribution F converges as d ~ oo (in probabil­ ity} to a unique predetermined value v* satis­ fying F(v*} = 1-~n· where ~n is the solution of xn+x-1 = 0. ## 3. 2 The Branching Factor of Alpha-Beta The Alpha-Beta (a-6} pruning algorithm is the most commonly used procedure in game-playing appli­ cations . Yet although the exponential growth of game-tree searching is slowed significantly by that algorithm, quantitative analyses of its effective­ ness have been frustrated for over a decade. One concern has been to determine whether the a-6 algo­ rithm is optimal over other game-searching procedures. Slagle and Dixon (1969} showed that the number of terminal nodes examined by a-6 must be at least nLd/2J + nld/21- 1 but m~y, in the worst case, reach the entire set of n terminal nodes [14]. The analys~s of expected performance using uniform trees with random terminal values had begun with Fuller, Gaschnig, and Gillogly [15] who obtained formulas by which the average number of terminal examinations, N 0 d· can be computed. Unfortunately, the formula would not facilitate asymptotic analysis; simulation studies led to the estimate~\_ 6 ~ (n}· 72 . Knuth and Moore [16] analyzed a less powerful but simpler version of the a-6 procedure by ignoring deep cut-offs. They showed that the branching factor of this simplied model is O(n/log n} and speculated that the inclusion of deep cut-offs would not alter this behavior substantially. A more recent study by Baudet [17] confirmed this conjecture by deriving an integral formula for Nn d· (deep cut-offs included}, from which the 6ranching factor can be estimated. In particular, Baudet shows that ~a-6 is bounded by ~n/1-~n s ~ \_6 s Mnl/2, where ~n is the positive root of xn+x-~ = 0 and Mn is the maxi­ mal value of the polynomial P(x} = [(1-xn}/(1-x}] x [1-(1-xn}n]/xn in the range 0 s x s 1. Pearl [13] has shown that both ~n/1-~n lower bounds the branch­ ing factor of every directional game-searching al­ gorithm, and that an algorithm exists (called SCOUT) which actually achieves this bound. Thus, the enig­ ma of whether a-6 is optimal remained contingent upon determining the exact magnitude of ata\_6 within the range delineated by Baudet. This enigma has been resolved [18] with the aid of Theorem 7 and the fact that if the terminal val­ ues of a (d, n, F)-tree are drawn from a character­ istic distribution ~(x}, then the distribution of every node in the tree would be identical in shape to ~(x} save for a scale factor depending on the node's level [19]. The result is summarized by the following theorem (Pearl [18]). Theorem 8: The branching factor of the a-6 proce­ dure for a continuous-valued uniform tree of degree n is given by: ![Image](https://ijcai.org/proceedings/1981/fulltext/104/image_000005_98ea34e8de0d704f73b489c47861de59ce31750b2af16ce9958b1e0f736cdba2.png) where ~n is the positive root of the equation xn+x-1 = 0. The asymptotic behavior of~-R is O(n/log n}, as predicted by Knuth's analysis [16]. However, for moderate values of n (n s 1000} ~ /1-~n !~ fitted much better by the formula ( .925} n .7 (see Figure 4 of reference [13]}, which vindicates the simulation results of Fuller et al. [15]. This approximation offers a more meaningful appreciation of the pruning power of the a-6 al~orithm. Rou?hly speaking, a fraction of only (.925)n·747fn ~ n- /4 of the legal moves will be explored by a-6. Alter­ natively, for a given search time allotment, the a-6 pruning allows the search depth to be increased by a factor log n/log df 11 \_ 6 z 4/3 over that of an exhaustive minimax searcn. The establishment of the precise value of ~a-6 for continuous-valued treesA together with a previ ­ ous result that '1t'a\_6 = nl/l for almost all discrete­ valued trees [13], completes the characterization of the asymptotic behavior of a-6. Moreover, the fact that Cn/1-~n lower-bounds the branching factor of any directional algorithm [13] renders a-6 as­ ymtotically optimal over this class of algorithms. However, the global optimality of a-6 has remained an unresolved issue until very recently. Naturally, the focus of attention has turned to non-directional algorithms, ra1s1ng the question whether any such algorithm exists which exhibits a branching factor lower than ~n/1- ~ n · ## 3.3 A Minimax Algorithm Better Than Alpha-Beta? Yes and No Stockman [20] has introduced a non-directional algorithm called SSS* which consistently examined fewer nodes than a-6 . Hopes were then raised that the superiority of Stockman's algorithm reflected an improved branching factor over that of a-B . A simple heuristic argument exists which re­ futes these hopes and indicates that SSS* and a-6 possess identical branching factors. It is based on the fact that when the terminal nodes are as­ signed only two values (say 1 and 0), SSS* becomes directional (identical to a-6) . Now, since the search of continuous games must be harder than the search of any bivalued games of the same structure, and since directional algorithms for bivalued games may require [13] a branching factor of ~n/1-~ , we conclude that SSS* would also exh i bit a branc~ing factor of at least ~n/1- ~ n · The weakness of this argument lies in the pos­ sibility that SSS* belongs to the rare class of algorithms whose performances improve with randomi­ zation, thus finding it easier to search continuous­ valued games. This weakness has motivated the eval­ uation of 9?sss· by direct methods using techniques similar to those of Baudet [17] and Pearl [18]. This evaluation has been completed recently [21] wi th a definite confirmation of the relation: ![Image](https://ijcai.org/proceedings/1981/fulltext/104/image_000006_27cde53e083971ebbe20a8dd4591ef3cf8413c5f88f66b17f60ce33b48137c55.png) Thus, the superiority of SSS* over a-6 is not re­ flected in their growth rates; the two algorithms can be regarded as asymptotically equivalent . The possible existence of some other algorithm with a branching factor superior to that of a-B has also been eliminated by a more recent result of Tarsi [22]. Considering a standard bivalued game­ tree in which the terminal nodes are assigned the values 1 and 0 with the probabilities ~nand 1-~n· respect i vely, Tarsi's result states that~ algo­ r i t hm which solves such a game-tree must, on the average, examine at least ( ~n/1- ~ n)d terminal posi ­ t ions . At the same time the task of solving any bival ued game-tree is equivalent to the task of veri fyi ng an inequality proposition regarding the mi nimax value of a continuous-valued game-tree [13] of identical structure, and, consequently, the for­ mer cannot be more com§lex than the latter. Thus, the quant i ty ( ~n/1- ~nl should also lower-bound the expec t ed number of nodes examined by any algorithm searching a continuous-valued game-tree. This, together wi t h (8), establishes the asymptotic opti­ mality of a~e over all game-searching algorithms, direct ional as well as non-directional. ## 3.4 When is Successor Ordering Beneficial? The analyses presented in the preceding two sections assumed that the order in which a-B selects nodes for expansion is completely arbitrary, say from left to right. In practice, the successors of each expanded node are first ordered according to their static evaluation function. Successors of MAX nodes are then expanded in a descending order of their evaluation function (their highest first) and those of MIN nodes in ascending order (their lowest first). It is normally assumed that such preorder­ ing increases substantially the number of cut-offs induced and results in a lower branching factor. Clearly, when the static evaluation function is well informed, correlating with the actual node val­ ue, such ordering will induce all possible cut-offs yielding Ji = nl/2. On the other hand, when the static evaluation is uninformed, the ordering is superfluous and yields 3i = (~n)/(1-~nl as in random ordering. The analysis of this section attempts to quantify the relation between the informedness of the static evaluation function and the branching factor induced by successor ordering. For simplicity, we treat bivalued n-ary trees with probability P = ~n that a terminal node obtains the value l . The information quality of the static evaluation function V can be characterized by two distribution functions: If we treat x as a variable parameter, then Fw can be regarded as a function of FL, or Fw = g(F~). g(z) is a monotonic, weakly increasing funct1on of z between the points (0,0) and (1,1). Totally uninformed V will be represented by g(z) = z , while "noiseless" V will be characterized by : The parameter which directly controls the branching factor is given by the integral: Theorem 9: The branching factor of a- B with succes­ sor ordering over a (d, n, ~n)-game tree is given by: Numerical computations of ap(s) show that, for all n, BV(S) is almost linear with S, gradually increas­ ing from its minimal value 3i = nll2 to its maximal value ~(S=l) = (~n)/(1-~nl· ## 3.5 When is Look-Ahead Beneficial? The basic rationale behind all game-searching methodologies is the belief that look-ahead followed by mi nimaxing improves the quality of decisions or, in other words, that the "back-up" evaluation func­ ti on has a greater discrimination power to distin­ guish between good and bad moves. Although no t heoretical model has supported this belief, it has become entrenched in the practice of game-playing and i ts foundation rarely challenged. Two heuristic arguments are usually advanced in support of look-ahead . The first invokes the notion of vi sibility, claiming that since the fate of the game i s more apparent near its end, nodes at deeper levels of the game-tree will be more accurately evaluated and choices based on such evaluation should be more reliable. The second alludes to the fact that whereas the static evaluation is computed on the basis of the properties of a single game pos i tion, the back-up value integrates the features of all the nodes lying on the search frontier, and so should be more informed . This latter argument essentially takes after a filtering model; the more samples, the less noise. A recent work of l~au [23] demonstrated that the fi ltering argument is utterly fallacious . In a large class of game-trees, reaching deeper consis­ t ently degrades the quality of a decision. This phenomenon, which Nau termed pathological, is not confined to the special game-trees considered by Nau but can be shown to be a common occurrence in the ensemble of games defined by the standard prob­ ab i listic model of (h, n, P)-trees. Assume that the evaluation function V computed at each terminal node of a (h, n, P= ~ nl-tree re­ flects the likelihood of that node being a WIN posi tion . The quality of such an estimate can be character i zed by the pair of distribution functions defi ned in (9). Given the pair Fw(x) and FL(x), one can compute the two conditional distributions of Vd· the mi nimax value of the root node: Fe(x) P[Vd ~ x given that the root is WIN] F~(x) P[Vd ~ x given that the root is LOSS] The analysis shows that, for ~verY. starting pair (Fw, FL)· the back-up pair (F , Fa) satisfies lim (F~ - Ffl = 0. This imp iesLthat as the search d~ depth increases, the minimax value of t he root node possesses the same statistics regardless of whether the root is in fact a WIN or a LOSS . Thus, the ability to discriminate between a WIN and a LOSS situation deteriorates by the min­ imax back-up procedure. To understand why the filtering argument fails in the case of game-trees, consider the task of est imating the value of an arbitrary function , y(x1, x2, ... xn) on the basis of the estimates x1, x2, . . . xn of i ts arguments. Knowing x1 . . . xn can improve the estimation of y if we integrate them accord i ng to strict statistical rules, as by form­ i ng the cond i tional expectation of y given i1 . . . in. Instead, the minimax procedure amounts to taking y(xl, x2, . . . xnl as an estimate for y-­ it computes the minimax value of the estimators rather than estimates the minimax. This point can be further illustrated by the following game-tree. Assume that the terminal val­ ues signify the probability that player 1 can force a WIN from these positions. Which move should be selected, towards A or towards B? The minimax eval­ uation procedure would assign to node A the va l ue . 3, to node B the value .2, and so would lead play­ er 1 to prefer A over B. On the other hand, if one computes the probabilities that nodes A or B are WIN (for player 1) on obta i ns: P(A is WIN) P(all A's successors are WIN) .3 x. 4= . 12 P(B in WIN) P(all B's successors are WIN) .9 x .2= . 18 ![Image](https://ijcai.org/proceedings/1981/fulltext/104/image_000007_9e960295bc9af386c983133fb69096a5f9d6bf8d416d606731730b40208723cb.png) Clearly, B is to be preferred. It is obvious from this example that if one wants to maximize the chances of choosing WIN positions, the minimax rule is inadequate and should be replaced by product­ propagation rules, nPi for MIN nodes and 1-~(1-Pi) for MAX nodes. If these propagation rules 1 are used, the phenomenon of pathology should be reduced, if not eliminated. However, the example also facilitates a line of defense in favor of the minimax rule. In prac­ tical game-playing, one is not concerned with main­ taining a WINNING position, winning regardless of what the opponent does, but simply with beating a fallible opponent. Such an opponent, if he shares our assessment of the terminal values, can be predicted to choose the left move from position B and the right move from position A. Therefore, on the basis of such a prediction, we have : P(player wins from A) .3 P(player wins from B) .2 which agrees with the minimax calculation . In sum­ mary, although the minimax rule is inadequate when playing against an omnipotent opponent, tacitly it contains a realistic model of a fallible opponent who shares the knowledge and limitations of player 1, and therefore should be effective against such opponents . This, perhaps, may account for the fact that pathology is not observed in practical game­ playi ng programs; the quality of play usually im­ proves with search depth. Another reason for the ahsence of pathology in practical game-playing could be that the evaluation functions become more accurate toward the end of the game, possessing increased visibility then, an ef­ fect not included in the preceding analysis. Nau [24] has recently demonstrated that pathological behavior occurs in a specific game despite an in­ crease in evaluation function accuracy. Determining the rate of improved accuracy necessary for combat­ ing pathology remains an open theoretical problem. ## References 1. Hart, P., N. Nilsson, and B. Raphael. "A For- mal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Trans. on Systems Science and Cybernetics, Vol. SSC-4, No. 2, July 1968, pp . 100-107. 2. Pohl, I. "First Results on the Effect of Error in Heuristic Search." In B. Meltzer and D. Michie (Eds.), Machine Intelligence 5, Edin- burgh: Edinburgh University Press, 1970. 3. Munyer, J. "Some Results on the Complexity of Heuristic Search in Graphs." Technical Report HP-76-2, Information Sciences Department, University of California, Santa Cruz, Septem- ber 1976. 4. Vanderbrug, G. "Problem Representation and Formal Properties of Heuristic Search." Infor- mation Sciences, Vol. ll, No. 4, 1976. 5. Pohl, I. "Practical and Theoretical Consider- ations in Heuristic Search Al9orithms." In E. Elcock and D. Michie (Eds.), Machine Intel- ligence 8, Chichester, England: Ellis Horwood Ltd . , 1977. 6. Gaschnig, J. "Performance Measurement and Analysis of Certain Search Algorithms." Ph.D. Dissertation, Department of Computer Science, Carnegie-Mellon University, 1979. 7. Gelperin, D. "On the Optimality of A*." Arti- ficial Intelligence, Vol. 8, No.1, 1977,-- pp. 69-76. 8. Huyn, N., R. Dechter, and J. Pearl. "Prob- abilistic Analysis of the Complexity of A*." Artificial Intelligence, Vol. 15, No. 3, 1980, pp. 241-254. 9. Pearl, J. "The Utility of Precision in Search Heuristics." UCLA-ENG-CSL-8065, Cognitive Systems Laboratory, University of California, Los Angeles, October 1980. 10. Nilsson, N. Principles of Artificial Intelli- gence. Palo Alto, CA: Tioga Publishing Com- pany, 1980. 11. Pearl, J. "The Complexity of Non-Admissible Search Heuristics." In preparation. 12. Pohl, I . "Heuristic Search Viewed as Path 562 13. Finding in a Graph." Artificial Intelligence, Vo 1 . 1 , 1970, pp. 193-204. 14. Pearl, J. "Asymptotic Properties of Minimax Trees and Game-Searching Procedures." Artifi- c i a 1 Intelligence, Vo 1 . 14, No. 2, 1980-,-- pp. ll3-138. 15. Slagle, J. R., and J. K. Dixon. "Experiments with Some Programs that Search Game Trees . " Journal of the ACM, Vol. 2, 1969, pp. 189-207. 16. Fuller, S. H., J. G. Gaschnig, and J. J. Gillogly. "An Analysis of the Alpha-Beta Pruning Algorithm." Department of Computer Science Report, Carnegie-Mellon University, 1973. 17. Knuth, D. E., and R. N. Moore. "An Analysis of Alpha-Beta Pruning." Artificial Intelli- gence, Vol. 6, 1975, pp. 293-326. 18. Baudet, G. M. "On the Branching Factor of the Alpha-Beta Pruning Algorithm." Artificial Intelligence, Vol. 10, 1978, pp. 173-199. 19. Pearl, J. "The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm." UCLA-ENG-CSL-8019, Cognitive Systems Labora- tory, University of California, Los Angeles, April 1980. To be published in Communications of the ACM. 20. Pearl, J. "A Space-Efficient On-Line Method of Comput1ng Quantile Estimates." UCLA-ENG- CSL-8018, Cognitive Systems Laboratory, Univer- sity of California, Los Angeles, December 1980. To be published in Journal of Algorithms . 21. Stockman, G. "A Minimax Algorithm Better Than Alpha-Beta?" Artificial Intelligence, Vol. 12, 1979, pp. 179-196. 22. Roizen, I., and J. Pearl. "A Minimax Algorithm Better Than Alpha-Beta?: Yes and No." In preparation. 23. Tarsi, M. "Optimal Searching of Some Game Trees." UCLA-ENG-CSL-8108, Cognitive Systems Laboratory, University of California, Los Ange 1 es, 11ay 1981 . 24. Nau, D. S. "Pathology on Game Trees: A Sum- mary of Results . " Proceedings of the first National Conference on Artificial Intelligence, August 1980, pp. 102-104. 25. Nau, D. S. "Pearl's Game is Pathological." Technical Report TR-999, Computer Science Department, University of Maryland, January 1981.