A Study of Search Methods: The Effect of Constraint Satisfaction and Adventurousness

Abstrac;t

This msearch addresses how constraint satisfiJction interacts with the search mode, and how the ratio of breadth of effort to depth of effort can be controlied. Four search paradigrns, each the best of its kind for non -adversary problems, are investigated. One is depth-first, and the others best-first. Al! rnethods except one highly informed best -first search use the same knowlcdge, and each of thcse methods is tested with and without the use of a constraint satisfaction procedure on sets of progressively more diflicult problems.

A Study of Sea rch Methods: The Effect of Const raint Satisfaction and Adventu rousness

Hans Berliner Gordon Goetsch

Computer Science Department Carnegie-Mellon University Pittsburgh, PA. 15213

knowledge, but the use of heuristic knowledge is minimal. ln contrast, a pure best-first :::earch relies exclusively on its heuristic knowledge with all the search control decisions being based on that knowledge.

As expected, the most informed search does bctter than the less informed as the problems get more difficult. Constraint satisfaclion is found to have a pronouncedly greater effect when coupled with the most informed algorithm. Large performance increments over A · can be produced by the use of a coefficient associated with the h term, and this algorithm produces solutions that are only 5% worse than optimal. This is a known phenomenon; however, the range of this coefficient is very narrow. We term this coefficient, which controls the ratio of depth of effort to breadth of effort, the a(iventurousness coefficient. Th~ less tractable a problern the greater the adventurousness should be. We present evidence to support this.

lntroduction

Heuristics are employed when the domain space being explored is too !arge to search exhaustively. A heuristic increases the likelihood of making a correct choice, but cannot prevent the making of an incorrect choice. The knowledge embodied by the heuristics is needed to reduce the cost of the search, but is insufficient to alleviate the need to search . The basic problems associated with heuristic search are: the desire to follow "successful" branches, while leaving less successful ones for later, and, when to quit pursuing a branch as its estimatcd merit declines.

Both problems are addresscd by any search paradigm; however, the secend problern can be effectively dealt with by a constraint satisfaction procedure that eliminates states that can no Iongerbe solved. Brute force methods solve problems by searching to the maximum penetration allowed in the time available. As the problems get more di!ficult, the utility of such methods decreases. Thus depth-first searci1es are alten augmented with techniques such as branch-and-bound and minimal move ordering We wished to study the interaction between heuristics, search techniques, and constraint satisfaction. Supe1 puzz, a solitaire puzzle that can benefit from constraint satisfaction techniques, was chosen as our problern domain. We selectcd four search algorithms as being the best exemplars of their class for solving non-adversary problems, and devised a constraint satisfaction procedure. We then investigated the degree of degradation fcr each search algorithm as the problems became more dilficult, and the interaction of constraint satisfaction with each technique.

The Domain

The domain chosen for this study was Superpuzz, an extremely difficult solitaire puzzle. The rules of Superpuzz are as follows:

Superpuzz is played with 24· cards, 6 (numbered 0 to 5) in each of 4 suits. To start a problern deal the cards in a raster of 6 wide by 4 deep. Then remove the "0" denomination cards, leaving "holes" . Legal moves consist of moving a card into a hole, thus creating a hole at its former location. The card that is moved into a hole must be of the same suit as the card to the left of the hole, and be one higher in denomination.

No card can be moved to the right of the last card in a suit, nor to the right of a hole. II a hole is on the left edge, any 1 may be moved there. The game is won when all the cards have been placed in ascending order by suit, with one suit in the first 5 places of each row as demonstrated by Figure 1 B. There is no requirement to have particular suits in particular rows. The game is lost when there are no Ionger any legal moves. These are the rules for 4x6 Superpuzz; it is also possible to play harder versions adjusting the rules for 4x7 and 4x8 formats.

Figures 1 A and 1 B show an initial and terminal position respectively. A solution to the initial position can be found at the end of this article. The rnost challenging aspect of Superpuzz is deterrnininq which ace to rnove into a hole on the left·edge. tv1aking the proper ace rnove is often ·non·intuitive, which rnakes the dornain interesting and results in prograrns that outperform weil practiced hurnans.

The Search Paradigms

Initial studies determined the following search algorithrns were the be:;t exemplars of their class:

1. A depth·first search (DF) using the branch and bound, and iterative deepening [5] techniques. Iterative deepening has recently been proved to dominate simple depth-first search when the depth of the solution is unknown [3]. The constant of iteration used was 2. The bound is the number of misplaced cards (N) in the present configuration. II the present configuration is at depth D, it is impossible to reach a solution at a depth less than D + N.
2. The A · search [4]. A · expands the Irantier nbde with the minimal function f, where f = g + h = D + N.
3. A best.lirst search (BF1) that uses the simple evaluation function f = /L N + D, where IL· the adventurousness coefficient which we discuss later, was equal to 1.8.
4. A best-first search (BF2) with a highly informed evaluation function !hat would encourage the developrnent of good "positional" formations that could be transforrned into wins.

A hash table containing the generated nodes plays a key role in three ways. ln the best-first searches, it becomes the representation of the tree. The hash encoding detects identical states, so that the same subtree will be searched only once. The hash encoding also detects cycles. ln the depth-first search, the hash table only performs the two latter functions.

Two evaluation functions were required. These are 1) A misplaced card counter, and 2) A position goodness function. These functions are described in detail in [2]. The misplaced card tunction is used in all the search prograrns, while the goodness function is used only in BF2.

The Constraint Satisfaction Method

Any state of a dornain is eilher solvable or unsolvable. We define the sct of totally solvable dornains tobethosein which all states accessible from a solvable state are solved or solvable. ln such dom:'lins any operator applied to any state preserves the solvability of the new state. Frequent!y, for each operator there exists a reverse operator that can re-establish the previous state. This type of problem is represented by puzzlessuch as the 15-Pm:zle and Rubik's Cube. An alternate condition is !hat the permissible operations clo not allow Iranstorrnation to an unsolvable state.

Set against the class of totally solvable problerns is the dass of partially solvable problems in which not every state of the domain can be solved, and the set of operations allow unsolvaule states to be reached from solvable states. For totally solvable dorn3ins the only !hing of interest is tt1e speed of the solution process and the quality of the soluti::m. For partially solvable problems, each instance may have to be classified a:; solvable or unsolvable.

Constraint satisfaction is the term used for the set of algorithms that can determine when a subtree cannot contain a solution. We wanted to study the role of constraint satisfaction on a difficult, partially solvable problern as the difficulty of the problern varied. This was the reason Superpuz:z was selected, as standard puzzles such as the 15-Puzzle are totaily solvable, and others such as Instant lnsanity are not very difficult for a computer.

8oth totally and partially solvable problems can use heuristic knowledge in order to speed up the search for a solution. Heuristic knowledge can be used to choose the order of applying operators and to evaluate the new states. However, totally solvable problems need no process to identify subtrees in which no solution can exist because, ipso facto, such subtrees cannot exist.

The constraint satislaction function developed for this problern [2] is as follows: Once all the aces are in place. the final destination of every card can be determined. Cards not at their final destination must be moved. We only examine cards that are to the left of their destination since thcy are typically the hardest to move. lf such a card is unmovable, the problern instance is unsolvable. The constraint satisfaction procedure is able to reject about 50% of all configurations presented to it du ring a search as being unsolvable. Constraint satisfaction is applied only alter all the aces are in place. since identifying deadlocked positions ear!icr was unproductive. lt is ab!e to deal with situations where not only individual cards, but whole trains of cards must be rnoved. Trains arise frequently as the result of putting a card behind its predecessor. Thc problem of determining whether a train can be moved is very difficult, and a number of finesses were used which are described in the above cited reference.

Results

Each of the four search algorithrns was tested with and without deadlock detection on the sarne 100 randomly genented instances of 4x6, 4x7 and 4x8 puz:zles. The programs were to determine if each problern was solvable (and give a satisficing solution) or unsolvable. Testing method details are given in [2].

Table 1 shows the average solution length, the average number of nodes per solution, the average time to complete, and the number intractable for the eight programs for each of the three problern widths. As expected, effort in all categories varies with problern difficulty. lt should be noted that the A ·, BF1, and DF algorithms all use the same knowledge, A · and DF for bounding purposes and BF1 as a simple measure of goodness, yet the BF1 algorithm requires fewer resources (nodes and time). Whilc BF1 produces solutions comparable to A* and DF on smaller problems, it clearly outperforms the other two algorithms on the 4x8 problern set. The most knowledgeable search (BF2) clearly outperforms the others in all criteria, except solution length. Although BF2 is only slightly superior among the 4x6 algorithms, it has achieved an overwhelming dominance by the time the 4x8 puzzles are considered.

Table 2: Performance Ratios

Table 2 shows the ratio of increase in resources for each algorithm type as the problern width increases. The data show that, in general, the more informed the algorithm is, the less the degradation in performance as the problern gets more difficult. This is an expected result; the trees grown by the most informed algorithm grow at a lower exponential rate than those grown more brute-force-like algorithms. The BF2 search has the most information. The next, BF1 has had its coefficient tuned so it is more responsive to its sole performance measure (misplaced cards) than the remaining algorithms, A * and DF which have the least information.

Table 3: Ratio of Elfort with and without Deadlock Detection

Table 3 shows the performance ratio of a search method with deadlock detection, to the same method without deadlock detection. Ratios less than 1.0 indicate improvements, otherwise the additional work was not beneficial. As expected the deadlock detection improves performance on the nodes measure in all categories. The deadlock detection did not always n::sult in a timu savings. Deadlock detection reduces the number of intractable problems, especially for the BF2 search. BF2 makes best use of the constraint satisfaction process. This is an important result which we discuss in the next section.

Discussion and Conclusions

Superpuzz is a much more difficult than standard puzzles. Further, the difficulty of the game varies with the width of the puzzle. ln this study we examine the 4x6, 4x7 and 4x8 games. Although the branching factor in each of these remains the same, the solution depth and percent of unsolvable problems increases significantly with increases of width.

The solution process can be thought of as occurring in two pllases. ln phase one, the cornbinatoric power of search attempts to see wlletller it is possible to obtain a position where all four aces are in place. Wllen this llas occurred, the deadlock detection algorit11m is invoked, which can reject about 50% of all positions it encounters. Phase two is invoked for positions !hat pass the deadlock test. Here by relatively small searches, the solution is eilher found er rejected . Wllen no solution is found in the sub-tree, phase one again obtains control.

Given !hat the combination of ceadlock detection and very srnall searches in phase two is very efficient, certnin ideas emerge. II the position is solvable, then it is advantageaus to reach phase two as quickly as possible. The BF2 search does this most effectively. lt is not at all unusual to have the first all-aces- in -place configuration discovered by the BF2 search be solvable, whereupon the solution proceeds immediately. ln those cases where this does not happen, the first dozen or so attempts do usually yield a solvable phase two. Only in cases where the solution is very contrived, or where there is no solution, is the BF2 procedure outperformed by others, in the case where there is no solution, all phase two positions must be explored and the procedure that reaches these with the minirnum amount of effort is the most effective. From this it can be seen !hat sorne knowledge of what percentage of problems is solvable is instrumental in deciding on a search paradigm. ln this research, the BF2 evaluation function is expensive to compute, as is traversing the tree. But, while the BF2 search is only marginally superior in the width 6 puzzle, it becomes completely dominant by the time the width is increased to 8.

Let us consider why one search paradigm is better than another. A · and DF are really quite similar. They probe to new depths in a breadth-first style !hat takes advantage of certain efficiencies. A · knows about effort remaining and builds a permanent copy of the tree, which it continues to expand at the best leaf nodes. DF also knows about effort remaining and g'i:IS its power from great efficiency in space and time. However, neither is able to venture very far on a probe down a branch unless it is continuously having success (reducing the number of misplaced cards) . Any Iaiiure to improve this measure would immediately force the A · search to try another branch. Because the DF search has an iteration constant of 2, two non-successful moves can occur in expanding a branch before returning. Since the criterion for success is rather simplistic, and it is very likely that any solution will require a number of non-constructive or backward-appearing steps, it is unlikely that eilher search will be able to make significant torward progress through such territory. Inslead they plow steadily torward until the treacherous lerritory is overcome by a/1 highly evaluated branches, and then pursue one to a successful conclusion.

Now consider the BF1 search po:radigm. The evaluation function for ßF1 is I = 11 N + 0 . The constant ,... is the adventu rousness coefficient ; for this program,... = 1.8. in BF1 the value of a clescendant nocle eilher decreases by .8 units in case the number of misplaced cards is reduced , or is increased by 1.0. This allows the descendant node to put some distance between it and its competitors when it is able to take a Iew constructive steps intermixed with some \hat do not appear so constructive. The essential point is that a branch does not have to produce "progress" on every move. The degree of such adventurousness is what the constant 1.8 controls, and for the given domain and evaluation function it appears tobe best.

Best·first search disciplines exist that have a reluctance to abandon a branch until it is judged a constant amount worse than tlle current best branch. The adventurousness coefficient allows the number of non-intuitive moves included in a branch to be a linear function of the number of "good" moves. This appears to be a better construction.

The BF2 search is even more adventurous (though it not clear how to obtain its adventurousness other than by empirical obser·1ation) since it can gain numerous points in heuristic value by placing a card into what is considered an advantageaus location. This allows it to penetrate deeply in certain branches that it "likes" while leaving others behind. This additional knowledge appears to pay off. in performance.

in some cases the evaluation function will Iead the search up a blind alley. Hereis where constraint satisfaction helps the most: it can disenchant the search causing it to Iook elsewhere. This happens for all of the searches, but is most effective in BF2 because the other searches arenot as adventurous.

in any search paradigm, once a node is known to be deadlocked, its successors will never be expanded. However, these savings can only be realized once such a sub-tree is reached. This is where adventurousness is important. lf situations where constraint satisfaction procedures can be applied occur only alter almost all important branches have been pushed to the same depth, then the savings will not be very great. Here, the most adventurous search has a big advantage (see Table 3) since it allows selectively approaching the point where constraint satisfaction can be applied.

II the above notiuns of adventurousness are correct, then the iess tractable the domain , the higher the adventurousness should be. We tested this hypothesis by re·running the BF1 (deadlock) alyurithm on all the 4x8 problems with ,... = 2.4. This resulted in tl1e average nodes perproblern being reduced by 15%, andin the number of intractable problems being reduced from 9 to 5. We i n t~nd to investigate this scaling of adventurousness further in future studies.

ln any domain the heuristic function must evaluate the desirability of the moves available. The decision of whether to abandon a branch in a best-first search or continue it is basic to the efliciency of tlle search. The adventurousness coeflicient for any domain/function combination, determines the degree to which the past history of the branch influences this decision. lt is not necessary to "succeed" on every move in a branch in order to continue it. lnstead a. success gradient (the adventurousness coefficient) must be maintained. This tends to producc consistent, plan-like behavior.

··· * * ························.·····

A minimal solution to Figure 1A is: (read left to right; names of moving cards only, except for aces where the row is also given).

C2 81 (Z) 04 03 04 C1 (Y) C2 01 (X) C3 32 H2 84 C4 02 85 C5 H4 83 01 (W) H1 (X) 84 02 H2 85 03 04 05 H5

Acknowledgements

We wish to acknowledge the efforts of T. Anantharaman, 8 . Pearlmutter, and H. Printz who were the first to use constraint satistaction in 8uperpuzz, and K. Goldberg whose graphic support aided in understanding the performance of the scarch.