Information Acquisition in Minimal Window Search

1. Introduction

The use of minimal windows [1] provides an improvement to the alpha-beta tree-searching algorithm (AB) [2] . Minimal window search is based on the assumption that all subtrees are infe­ rior to the best subtree searched thus far, until proven otherwise. Having searched the first branch with a full window [a,ß], all remaining branches are searched with a minimal window [a,a+ 1], where a represents the best minimax value found so far . If the value returned is indeed s a, then our assumption was correct and the sub­ tree is inferior. Otherwisc, this su btree is superior and usually rnust be re-searched with a wider win­ dow.

The re-search idea originally appeared in Pearl 's Scout algorithm [3). Subsequently, there have been two generalizations, Principal Variation Search [4] and NegaScout [5]. Figure 1 shows the NegaScout (NS) algorithm for searching a tree of width w and depth d. If a node p is terminal, Evaluate(p) returns its value. For interior nodes Gencrate(p) determines the w branches from p: Those branches whose minimal window search produces a better minimax value of v usually must be re-searched . Only when a < v < ß, and the remaining depth of search is greater than 2, is a re-search with a window [v,ß] necessary.

t Current address: Universitaet Hamburg, Fachbereich Informatik, Schlueterstr.70, D-2000 Harnburg 13, West­ Germany.

tt Research reported here was supported in part through Canadian NSERC grants A7902 and E5722.

This paper introduces two new algorithms. These use information acquired frorn the original search of a subtree to minimize the cost of a possi­ ble re-search . lnformed NegaScout (INS) uses all available information to generate the smallest possible trees, but does so with increased storage overhead. Partially. Informed NegaScout (PNS) is a compromise between NS and INS. The performance of NS, PNS, and INS is compared with AB and SSS* [6, 7] . INS searches trees of size comparable to those traversed by SSS*, but does so with lower overheads.

2. Information Acquisition

When the initial search of a subtree is per­ formed, the values returned by each of the descen­ dants is rnaintained in a tree-like clata structure . This information can be used to minimize the cost of any necessary re-search, otherwise it is dis­ carded .

FUNCTION NS (p : POS; a, ß, depth : INTEGER) : INTEGER; VAR 1, v, a, b : INTEGER; succ array [1 .. w] of POS; BEG IN IF depth = 0 THEN { Terminal node? } RETURN (Evaluate (p)); succ := Generate (p); { Generate succ . } a .- -oo; b - ß; FOR 1 .- 1 TO w DO BEGIN v := -NS (succ[1), -b, -MAX(a, a), depth-1); IF v > a THEN { Re-search needed? } IF 1 1 OR v S a OR v 2: ß OR depth S 2 THEN { v 1s accurate enough } a := v ELSE { Re-search requ1red } a := -NS (succ[i), -ß, -v, depth-1); IF a 2: ß THEN RETURN (a); { ß cut-off} b := MAX (a, a) + 1; {Minimal window} END; RETURN (a); END;

Information gathered from the initial search of the subtree is used on a re-search to allow two new types of cut-offs. Figure 2 illustrates the ignore left cut-off. In Figure 2a, the subtree has been searched with a minimal-window of [100,101]. The descendant B returned a value of 105 causing a normal beta cut-off. If at some future point it is necessary to re-search this subtree, descendant A need not be looked at again since it has already been showri tobe inferior toB, Figure 2b.

Figure 3 illustrates the prove best cut-off. At these nodes, a beta cut-off has not occurred and all descendants have been examined. Each of the values retutned is an upper bound on the subtree's true value, Figure 3a. If a re-search is necessary on this subtree, there are three things that can be clone to · minimize tree size. First of all, the branches can be re-ordered according to their values from the initial search. By sorting the branches in descending order of value, the branch with the highest upper bound (and therefore with the highest probability of being the root of the best subtree) is searched first, Figure 3b.

Secondly, since the initial value for each sub­ tree represents an upper bound, the re-search can be clone with a narrow window instead of a minimal-window. By doing this, no re-searches of re-searches can ever occur.

Finally, if the search of a subtree returns a true value that is greater than the upper bound of any of the other descendants, then those descen­ dants can be discarded without any further work. For example, in Figure 3b, if move Bis re-searched and returns a true value of 88, then moves A, and C need not be searched again, since their values can never exceed that of B ..

lt turnsout that ignore left cut-offs are just a special case of prove best cut-offs. Branches pro­ ven inferior can be treated as having value -co and the rest of the branches as having a +co value. Retrieving this information and performing a stable sort creates the prove best condition. The cut-offs are treated differently because in an actual implementation the ignore left cut-offs require less storage to maintain the necessary information, e.g. only the num her i of the best descendant thus far need be saved. On a re-search, descendants 1 through i-1 are ignored and the remainder searched. At prove best nodes, the values for all descendants must be saved .

3. Algorithms

NegaScout can be enhanced to use informa­ tion from the initial search of a subtree to aid in any re-searches. Every time a node is visited, a record is kept of the results obtained from search­ ing each descendant subtree . Either a beta cut-off occurs, and ignore left information is available for a re-search, or all descendants are examined, and prove best information is available. In both cases, this information can be linked tagether to form a map of the subtree just searched. If a re-search is necessary, the map data can be used to ac hieve ignore left and prove best cut-offs that are not pos­ sible in NegaScout. lnformed NegaScout (INS), see Appendix, does exactly this for all nodes in a tree.

The storage overhead in saving all this inforld;' J mation is proportional to ~ · w' entries, which is i-1 less than for SSS*. Nevertheless this may be too m uch, even if one reclaims storage whenever possi­ ble . As an alternative, Partially Informed NegaScout (PNS) has been implemented, provid­ ing a compromise between the complete informa­ tion of INS and the zero information of NS. One can devise many different compromise algorithms; our version of PNS only retains information about prove beßt cut-offs near the root of each subtree and maintains the principal variation, the path to the terminal node that the initial search considered best. This algorithm tries to provide many of the benefits of INS without the storage overhead .

An important point to note is that the infor­ mation used by INS is not a hash table or a tran­ sposition table [4]. Whereas transposition tables are most useful in directed graphs, the methods described here are applicable to any tree structure and do not depend on the properties of the appli­ cation.

4. Results

Figures 4 and 5 illustrate some results compar­ ing AB, NS, PNS, INS, and SSS* . The number of leaves searched by each algorithm is normalized to the size of the minimal game tree [2]. Each data point represents an average over 20 runs. Random trees, where each descendent has an equal proba­ bility of being best, and strongly ordered trees [4], where the first descendent has a 60% probability of being the best, were searched by all algorithms. In Figure 5, data at depths 7 and 8 are not avail­ able for SSS* and INS , because of memory con­ straints.

The graphs provided, as weil as results for other widths not reported here, show that the curves oscillate, with SSS* varying the least . The oscillation is normal and occurs because the for­ mula for the minimal tree size depends on whether the tree is of even or odd depth. SSS* fluctuates least since it is a best first search algorithmt; the other algorithms are (partly) directional. For even search depths SSS* visits fewer nodes than INS, but for odd search depths INS is usually better, because INS postpones node expansion until it is proven that the principal variation lies in this part of the tree. Of course, minimal window techniques are favored in strongly ordered trees, since re­ searches are less probable. Here even a modest amount of information is enough to allow PNS to outperform SSS* at odd depths.

Nodes visited is not the only consideration when comparing tree searching algorithms. SSS* and INS have significant overheads when com­ pared to AB and NS . Obviously, any timing results are implementation dependent. Our experience isthat a call to INS is, on the average, about twice as expensive as a call to AB, NS , or PNS, and that SSS* is 10 times slower than INS . Whether this overhead is significant or not depends on the application .

5. Conclusions

INS has been shown to be competitive with SSS* in terms of leaf nodes searched. However the data structure to support INS is more efficient. Not only is it slightly smaller, but it can be pro­ cessed in one ten th the time required by SSS *. Perhaps more importantly, by storing the information acquired during the minimal window search in a hash table, rather than as a map of the re-search tree, the memory needs can be reduced to the space available. The cost for use of such reduced memory is increased search overhead, but the search time is bounded below by NS.

PNS represents a good compromise, yielding significant reductions in tree size with little time and space overhead. In our experience, PNS is the preferred algorithm for !arge trees , especially under conditions of weil ordered interior nodes .

The results reported here show the relative properties of the algorithms. Experiments are continuing to obtain a better measure of the stan­ dard deviation . Current work includes empirical performance analyses of these algorithms in prac­ tical game playing programs.

t Sometimes the best first data misleads SSS* so that it expands more nodes than NS!