A Hybrid SSS*/Alpha-Beta Algorithm for Parallel Search of Game Trees

ABSTRACT

This paper explores the issues that ar!se when SSS*-llke search algorithms are implemented in parallel. There is an important imp!icit assumpt!on regard!ng the OPEN Iist of sss· (and A*-like algorithms): those states wh!ch are guaranteed never to become part of an optimal solution are forced down !nto the OPEN Iist and never rise to the top for expansion. However, when multiple processors are introduced in a parallel version of sss·. these buried states become subject to expansion despite their provable suboptimality. If such states are not !dent!fied and purged, they may exert an enormaus drag on the parallel algorithm because cons!derable processor effort will be wasted. However , the pruning mechanisms of alpha-beta can be adapted by a parallel SSS*; the resulting algorithm HYBRID is su!table for searching game trees and general AND/ OR trees in parallel.

INTRODUCTION

A. The Alpha-Beta and SSS* Algorithms

The alpha-beta game tree search algorithm offers significant potential for search speedup by "pruning", or ignoring game tree branches that cannot affect the final m!nimax value of the root. The State Space Search algorithm, or SSS* (Stockman 1977), as originally presented, usually dom!nated alpha-beta by the " parallel" traversal of subtrees. Whereas alpha-beta was condemned to search strictly in a left-to-right fashion , sss· sent "probes" simultaneously into the tree, and, in a manner not unlike A* (Nilsson, 1980) , maintained an "open" Iist of partial solutions ordered by descending merits. However, SSS* could also be used to search general problem-reduction representations as well as simple game trees (Stockman and Kanal, 1983). Stockman's original SSS* underwent a few revisions, and the final version (Pearl, 1984) is admissible and always dominates alpha­ beta. (We shall henceforth assume that the reader is familiar with the next-state operator G of SSS* as weil as Iist notation for trees.)

B. Essential Components of SSS*

For later comparisons, we give a h!gh-level description of the sss· algorithm:

ALGORITHM SSS*

1. Place the start state (i.e., root) on the OPEN Iist.
2. lf OPEN is empty , exit with failure and halt.
3. Remave the top state S from OPEN.
4. ( 4) If S is final , i.e. , represents a complete solution then return S with success and halt.
5. Apply the next-state operator G to S and add G(S) to the OPEN Iist (possibly with changed merits).
6. Go to (2).

Additional detailed discussions of SSS* can be found in (Leifker and Kanal , 1985).

A HYBRID SSS* /ALPHA-BETA ALGORITHM FOR PARALLEL SEARCH OF GAME TREES

Danlei B. Leifker Laveen N. Kanal

Department of Computer Science University of Maryland College Park, Maryland 20742

Our goal is to Implement a form of SSS* in parallel, us!ng a generalized alpha-beta prun!ng process to exc!se suboptimal states from the OPEN Iist before any processor effort is wasted. This proposed algorithm, which we call HYBRID, is suitable for use in searching general AND/ OR trees as weil as game trees. S!nce any game tree can easily be transformed into an AND/ OR tree (with strictly alternating Ievels of AND-nodes and OR­ nodes), general AND/ OR trees are used in the discuss!on which follows, although, as in game trees, only top-down expansion of states will be cons!dered. Our concepts are unlike previous hybrid algorithms (Campbell and Marsland, 1983), in that there is a true coalescence of alpha-beta and sss·, not simply a juxta­ posit!on of the two in one program.

li INTRODUCTION OF P ARALLELISM

A. Where to Introduce Parallel!sm

The control part (or dr!ver) of SSS* !s relatively stra!ghtfor­ ward. A state !s removed from the top of OPEN and exam!ned. If it is final (i.e. , !ts root !s solved), it !s taken as the solut!on and the algorithm halts. If not, the "next-state" operator G is applled to the state and the result(s) placed back !nto the OPEN Iist. If the number of states in OPEN ever drops. to zero, the algor!thm halts with failure.

B . A First Poss!bil!ty

To Implement a form of non-partit!oned SSS* in parallel, multiple processors obv!ously must be !ntroduced somewhere. One of two possible locations !s shown in Figure 1, where only the top state from OPEN is removed at a time. The processors p ,, p 2· ... , PN then cooperate to expand this state through the next-state operator G and return the results back to OPEN. If G were a very complex operator having many disjoint tasks, this arrangement would probably be very attractive. The fundamen­ tal algorithm would not be changed, and it would still share in all the formal properties enjoyed by SSS*. The only difference would be that the actions of Operator G would be accelerated considerably.

This method of "operator parallellsm" must be rejected for the follow!ng reasons: (1) lt forces processors to assume special­ ized tasks, (2) It can create enormaus bottlenecks when work cannot be conveniently partitioned, and (3) it has the potential to cause enormaus congestion among the waiting processors because the tasks have been broken down into excessively primi­ tive components.

C. The Alternative

The alternative, shown in Figure 2, overcomes many of these pitfalls and is amenable to parallel processing by N proces­ sors, even when N is not specified until runtime. The basic approach is to permit each processor to access the OPEN Iist.

Each processor removes the next state from the top of the OPEN Iist, expands the state by itself, and returns the resulting state(s) back to OPEN. This is the method adopted by HYBRID. As one might expect, HYBRID is not simply a variation of sss· - it represents a new way of heuristic control using the operator G. Consequently, the formal properties of sss· do not necessarily hold for HYBRID. The remalnder of this section deflnes HYBRID formally and discusses the ramiflcations of allowing pro­ cessors to manipulate states from the interior of the OPEN Iist.

A special notatlon must be introduced to facilitate dis­ cussion of parallel algorithms. The construction

COBEGIN < statement-list > COEND

indicates concurrent executlon (Dijkstra, 1965} in that all State­ ments of < statement-list> are executed simultaneously. The notation is augmented here such that processors may be specifled explicitly by attaching thelr names as Iabels to Statements.

The HYBRID algorithm simply assigns each of the given N processors a copy of the sequential sss· program. Formally, the preliminary version can be deflned as:

Algorithm HYBRID

I* Preliminary version *I (1) Place the start state (i.e., root) on OPEN. (2) halt := FALSE; I* initialize *I (3} COBEGIN I* Each processor 1 through N begins identical and concurrent execution. Only the code for processor Pk (1 < = k < = N} is shown. *I Pk: BEGIN WHILE NOT halt DO IF the OPEN Iist is not empty THENBEGIN END; CO END Remove a state S from OPEN; If S is final THEN BEGIN halt := TRUE; return(S}; END ELSE BEGIN Expand S by operator G; Place results back on the OPEN Iist by descending merit; END; END;

The Boolean variable HALT serves as a global flag to initiate parallel processing and then to terminate it when a solution is found. Presumably the OPEN Iist and the HALT variable are contained ln shared memory and guarded by semaphores. More elaborate synchronization constructs could also be used (Hoare, 1972}, but these concerns will not be addressed here. The point to remernher is that processors must be in critical sections to change any data in shared memory, and that at most one proces­ sor can be in a critical section at a time.

III ANOMALrES OF THE HYBRID ALGORITHM

A. Two Problems with the Proposed HYBRID

The proposed version of HYBRID given in Section II is only preliminary because two interesting anomalies occur which must be investigated further: (1) There is no clearly deflned time to halt should HYBRID find no solution; and (2) The preliminary version of HYBRID is not admissible (i.e. , if HYBRID halts with a solution, that solution cannot be guaranteed to be optimal}.

B. The First Anomaly: When to Halt?

As deflned above, the algorithm is simply allowed to enter an infinite loop if no solution exists for the given tree. Although this is hardly desirable in a practical application, it does illus­ trate a problern that occurs whenever more than one processor is granted access to an OPEN Iist. Suppose that HYBRID is exe­ cuted on a given tree with two processors, Pi and p; , and that the OPEN Iist contains one start state when execution begins. Processor Pi will enter a critical section, remove the state from OPEN, exit the critical section, and begin generating its succes­ sors. Processor P; will then pursue a similar action, but it will find the OPEN Iist empty because Pi has not flnished expanding the state. If processor P; is sutnciently naive, it may conclude from the empty Iist that the given PRR has no solution and then may even attempt to force the entire algorithm to terminate with failure. Since this is clearly not the true state of the computa­ tion, HYBRID (as given above) merely instructs all processors to wait idly until (1) a "next" state arrives at the OPEN Iist for expansion, or (2) the global HALT condition is raised by the discovery of a true solution.

C. The Second Anomaly: Is HYBRID Admissible?

As N (the number of processors) increases, there is also in increase in the likelihood that the algorithm will halt with a non-optimal solution. To see this, recall that the check for ter­ mination is made when the state is removed from OPEN, not after it has been generated and about to be placed back onto OPEN. The inadmlssibility of HYBRID, then, although unex­ pected, is easlly demonstrated: as the number of processors increases, the total number of examined states increases, thus raising the probability that a non-optimal solved state hovering near the top of the OPEN Iist will be selected for expansion and identifled as a final solution. This does not occur in sequential sss·. for there the OPEN IIst ls kept strlctly sorted by merit, and only the top state ls examined at a time .

D. Correctlng the Allomalies

Both the anomalles may be easlly elimlnated. The ftrst anomaly ls corrected by haltlng only when the OPEN IIst is empty and all processors are !die; the second by malntalnlng a "tentative optimal merlt" (l.e ., a runnlng best solutlon found so far) , and halting only when all remalnlng states on OPEN are below this threshold. Unfortunately, even wlth these modlftcations, HYBRID as lt stands ls grossly lneiDclent because of the presence of provably suboptimal states on the OPEN IIst. This issue is discussed in Section IV.

IV PROVABLY SUBOPTIMAL STATES

A. EIDcient Use of Processor Elfort

Very often in the course of execution of SSS' the lnterior of the OPEN Iist may contaln states which are guaranteed not to be subsumed by any optimal solution. This never causes a prob­ lern in sequentlal SSS', for there only the top state ls examlned. However, conslderable processor effort will be wasted if any prc:r cessor ls permltted to fetch and expand any of these provably suboptimal states. It ls therefore clear that any eiDclent verslon of HYBRID requires a declsion procedure to "test" states as they are taken off the OPEN Iist. If the state ls provably subop­ timal, lt is discarded . lt is expanded only lf it has any potential of becoming an optimal solutlon.

B. Another Look at Alpha-Beta

The alpha-beta algorlthm, sultably generallzed, can be adapted for use in an eiDcient verslon of HYBRID. Although alpha-beta evaluates nodes in a strlct left-tc:rright fashion, the use of alpha values and beta values captures very neatly the con­ cept of suboptimallty. If these attrlbutes can be managed by HYBRID, they will provlde a quick decision procedure for ldentl­ fying provably suboptimal branches of the search tree . However, for mnemonic purposes, we shall use the names "ftoor" and "ceil­ ing" in place of "alpha value" and "beta value"; when dlscusslng the attributes of problern #k, it is convenient to wrlte "ftoor(k)" and "ceiling(k)". It should be emphasized that this notation is not a function in the mathematical sense, but is rather an attrl­ bute which can be accessed and changed.

C. Definitions

Formally, if node #n is terminal and solved with merit m, then ftoor(n) = celllng(n) = m. If terminal node #n has not yet been expanded, then ftoor(n) = 0.0 and celllng(n) = 1.0. If non-terminal node #n has AND successors, then ftoor(n) ls deftned as the minimum of its successors' ftoors, and celllng(n) ls deftned as the minimum of its successors' celllngs. If non­ terminal node #n has OR successors, then ftoor(n) ls deftned as the maximum of its successors' ftoors , and ceillng(n) is deftned as the maximum of its successors' cellings. For any given PRR hav­ ing nodes p 1 , .. . , p ·· we deftne the set Z of provably suboptimal nodes as follows:

1. Ir any node Pk has an ancestor P; such that P; is in Z, then Pk is in Z.
2. If any node Pk has an ancestor P; such that ftoor(p;) ls greater than celling(pk ), then Pk is in Z.
3. If any OR node Pk has an ancestor P; and sibling node Pi such that ftoor(pi) is greater than ftoor(pk ). and ftoor(pi) is greater than ceillng(p; ). then pk is in Z (a "don't-care" cutoff).

There is an important impllcit assumption regarding the deftnltion of z. Initially , Z ls empty and grows as the algorithm evaluates more and more terminal nodes. However, once a node becomes provably suboptlmal, it remalns provably suboptimal and ls removed from all additional conslderatlon. If thls were not the case, rule (3) above would glve rlse to nodes wlth only transient suboptlmality.

D. The Final Version of HYBRID

The eiDclent final verslon of HYBRID ls essentlally the same as corrected HYBRID at the end of Sectloil 111, wlth the exceptlon that as each processor ln HYBRID removes a state from OPEN, lt verlftes that no node ln the state ls a member of z. If there is such a node, the entlre state ls dlscarded and the processor returns to OPEN for another state.

V REMARKS

This ls only a high-level descrlptlon of the HYBRID con­ cept. The detalled mechanlsms for practlcal lmplementatlons and the design of appropriate data structures and algorithms to detect provably suboptimal states are current toplcs of our research.