Branch & Bound Formulation for Sequential and Parallel Game Tree Searching: Preliminary Results

Introduction

Viewing game trees as And/Or trees it can be shown [1) that search for the minimax value of a game tree is equivalent to searching for the maximum valued solution tree, where the value of a solution tree is defined to be the minimum of all its tip values. The algorithm, SSS*, based on State Space Search, was introduced by Stockman for computing the minimax value of game trees and shown to be better than Alpha-Beta. We formulate a general Branch & Bound procedure to find the .optimum solution tree in the space of all possible solution trees represented by a game tree and show that SSS* can be viewed as a particular practical implementation of the B&B pro­ cedure. We also indicate briefly how this formula­ tion applies to the definition and analysis of Alpha­

Beta and parallel SSS*.

A B&B procedure can be viewed as a technique for finding the optimum value (maximum or minimum) of a real valued function f, over a possibly infi­ nite domain S, without computing the value of the function for every member of the domain. The orig­ inal set is repeatedly decomposed (branch operation) into smaller and smaller sets. Lower and upper bounds of the function f for these sets are calcu­ lated. Assuming we are searching for the maximum, if the lower bound on f for a set X exceeds the up­ per bound for any other set Y, set Y can be ignored (bounding operation) since some member of set X will The algorithm terminates with the optimum solu­ tion tree because we start with the complete set of solution trees, divide it into smaller and smaller sets, and eliminate a set only if we are certain that the optimum tree does not lie in it. Termina­ tion occures when a singleton set having been com­ pletely explored (i.e., its upper bound is its true value) is chosen in step 2 as a set with the high­ est upperbound. At that point one can be certain that no other set has a solution tree better than the one chosen. The algorithm is bound to termi­ nate because we start with a finite set of finite size solution trees. In each iteration of the al­ gorithm we are either eliminating some set of solu­ tion trees from further consideration or evaluating some unevaluated tips of some solution trees.

* Tltis research was supported by NSF Grant ECS-7822159 to The Laboratory for Pattern Analysis.

The detailed presentation of SSS* in Stockman [1) is not as transparent as the above B&B formula­ tion but it can be easily seen that SSS* is equiva­ lent to the B&B procedure presented above. SSS* maintains a list of states of traversals (called OPEN), each representing a set of solution trees and the current upperbound associated with it. State expansion directly corresponds to branching, and purging of states from OPEN corresponds to elim­ inating the dominated sets of solution trees. Thus SSS* can be considered a practical implementation of the above B&B procedure. SSS* is of interest be­ cause it was proved by Stockman that it never ex­ plores a node that Alpha-Beta can ignore. For prac­ tical distributions of tip value assignments Stockman experimentally showed that SSS* explores strictly fewer game tree nodes than Alpha-Beta. We have shown that by defining a particular depth first strategy for selection in the above procedure, one gets the well known Alpha-Beta algorithm. With a different choice of select, branch and evaluate functions we can come up with the "SCOUT" algorithm proposed by J. Pearl [4). Several other competing algorithms also can be derived in this manner. The above Branch & Bound method provides a unified ap­ proach to formulating and analyzing various search a lgorithms for AND/OR trees.

An Asynchronous Parallel Procedure: Preliminaries

While performing set divisions (node expansions in SSS*) if the upperbounds of all sets (of solu­ tions trees) under consideration are reduced to some value U', then the B&B procedure will still find the true optimum solution tree if its value happens to be less than U'. However if the value of the opti­ mum tree is greater than or equal to U' then the algorithm will terminate with the value U'. Let BB(S,U') be the value returned by B&B if at some time before it terminates upperbounds of all sets are lowered to U'- and let U* be the value of the optimum tree. Then

U* < U' ===> BB(S,U') z U*;

U* >= U' ===> BB(S,U') = U'.

The validity of this statement can be easily proven by thinking of the act of lowering the upperbounds of the sets as adding an extra leaf node with value U' to all the solution trees under consideration. Since the optimum value of a solution tree is the minimum of all the values at the tips, this modification will keep the optimum value intact if it was already below u·.

It is easy to show that the number of tip nodes evaluated by B&B (or SSS*) is a mortotonically increasing function of the initial bound associated with the starting set of solution trees. The ini­ tial bound represents the guessed value of the op­ timal solution tree. The more accurate this guess, the more effective the dominance relation becomes. In Alpha-Beta, this corresponds to making more cutoffs when better alpha and beta bounds are known. Experiments have shown that if game tree node values are chosen independently from a uniform distribution between 0 and m, then the dependence of the number of nodes expanded on the initial bound is as shown in Figure 3. As long as the chosen bound is above the true minimax value, the smaller bound provides the correct minimax value at a significantly lower cost. This fact can be used in a seemingly very efficient asynchronous parallel procedure for searching game trees, which compares favorably with Baudet's parallel imple­ mentation of Alpha-Beta [5).

Parallel Implementation of SSS*

Let us assume that the minimax value of a game tree lies between -m and +m with uniform probabil­ ity. If we have just one processor we would start B&B with +m as the initial upper bound for the com­ plete set of solution trees. As branching and node expansion proceed, upper bounds for various gener­ ated subsets would become lower and lower. At ter­ mination we would find that the upper bound of a set (which has just one completely explored solu­ tion tree) becomes equal to its own optimum value and is higher than the upper bounds of all the

other sets.

With multiple processors we could start sev­ eral B&B procedures, one on each available proces­ sor, each with a different initial upper bound as shown in Figure 4. Any time a process lowers its current global upperbound it can be guaranteed that the minimax value is less than or equal to this lowered global upper bound. Thus in Fig. 4, if process 'n' manages to lower its upper bound we can guarantee that the minimax value lies between -m and Bn where Bn is the current global upper bound of process n. If process n is allowed to proceed it will terminate with the correct minimax value. (Note that in the beginning we could only guarantee that process 1, with the initial global upper bound of +m, would terminate with the correct optimum value). It is clear that processes 1 through n-1 can safely reduce their global upper bounds to some values below Bn and thus perform the look ahead function which was previously performed by proces­ ses 2 to n. Thus among the n processes at least one is guaranteed to find the optimum value and the others perform a look ahead function. At any time a process searching in a lower range finds that its global upper bound is correct, i.e. , it can be low­ ered, it can take over as 'master' and the other processes can perform the look ahead. These paral­ lel processes work independently and communicate only if the bounds are lowered. There.forc this parallel algorithm is well suited for implementation on asynchronous multiprocessors.