Computer Game Playing

Objectives

Historically, programs that" u-;e big search have been distinctly superior to those that rely more on knowledge than search. We wish to discuss here why this is, and what can be done to produce more successful program~ in the AI mold, i.e. using knowledge to guide actions, rather than discovering useful actions as the result of search.

PANEL ON COMPUTER GAME PLAYING

Chaired by

Hans Berliner Carnegie-Mellon University Pittburgh, Pa. 15213

problem space. Also all problems can be solved by enough knowledge, by merely having all pertinent information available for every node in the problem space; provided it is available and there is enough space to store it. Tasks that can be solved by either of these methods are considered not to be interesting.

SEARCH AND KNOWLEDGE 1

Hans Berliner Carnegie-Mellon University Pittsburgh, Pa. 15213

To search without knowledge when a complete search is not possibl.e does not make sense. To apply partial knowledge without search has not been very successful in games such as chess. Turing achieved only mediocre play with his (hand-simulated) chess program Turochamp [Tur53], and other attempts since then have not realized much improvement.

Thus interesting problems appear to require a combination of search and knowledge. However, there are many possible methods, both for controlling the search and for organizing the knowledge. Knowledge must be able to detect interim advantages. In non-terminal states such interim advantages can be considered indicators of how the game may go in the future.

A search with such knowledge will be able to find leaf nodes at the limit of its searching capability which maximize its understanding of the universe. However, such a search only understands "ends"; it does not understand "means". Thus if it reaches a leaf node in a search to an arbitrary depth, it does not understand how it achieved its present success (or lack of it). This creates additional problems when a greater success can be achieved in another branch by the same means, but at a slightly greater depth. This is the Horizon Effect [Ber73].

II. Some Tractable Search Techniques

It is convenient here to distinguish goal-directed searches which develop and prune nodes based on properties of a node (rather than the terminal value of its branch), and "mindless" techniques which search all of a predefined search space to find the optimal path, basing decisions solely on the value of terminal nodes. To date the latter techniques have been eminently more successful in game-playing. This is no doubt due to the tremendous amount of knowledge that is required

I This work was supported by the Advanced Research Projects Agency of the Office of the Secretary of Defense (contract F44620-73-C-0074) and is monitored by the Air Force Office of Scientific Research,

Abstract

We discuss some important properties of various search techniques, and some properties that knowledge must have in order to support adequate game playing behavior.

I. Some Points on the Continuum

It seems that everything in game-playing (and possibly in all of AI) u.ltimately comes down to knowledge and search. This is really another case of a space/time tradeoff. All state-space problems can be solved by searching, if there were enough time to do a complete search of the to adequately guide a goal-directed search in a large domain. We now discuss advantages and limitations of each approach.

A. Techniques that search a uniform space

It is now rather clear that the old controversy of depth-first vs. breadth- first search (if it was ever really controversial) has been resolved in favor of a new technique called depth-first search with iterative deepening. This technique was discovered independently by Slate & Atkin [Sia77) of the Northwestern Universi ty chess group, and James Gillogly, then at Carnegie-Mellon Uni versity. The technique searches depth-first fashion to depth N, and reports its results. The search is then il erealed to depth N+l, using information gained in the earlier searches. This information allows the guiding of the search so as to produce a better ordering of alternatives, whi ch makes the alpha-bela mechani sm more effective. Thi s makes an iterated depth-n search cheaper than a depth-n search without the signposts (so to speak). These results indicate that search to one additional ply maintains much of the relative value structure of the branches, at least in a domain such as chess and almost certainly for any domain having structure. Thi s technique is al so very effective in allocating time to a search as the lime for one additinal iteration can be well estimated from the previously iterations. Thus this technique which combines the best features of depth.:first alpha-bela (efficiency) and breadth-first (uniform coverage) appears v astl y superior to any olhe.r technique that searches a uniform space.

B. Techniques that Search Selectively

Selective search techniques are generally classified as best-first searches. It is very probably that the reason that these techniques have not been very successful is that at every node it is necessary to apply knowledge to decide how to continue the search. The decision can range from stopping, to jumping to another branch of the tree, to selectively expanding the current node. The knowledge. that could be used for such purposes is extensive, and it appears quite likely that no one has thus far been able to accumulate a data base of sufficient size and detail in any complex domain. However, it appears likely that there is another reason too; one-pass evaluation which we take up in section V. Of the present techniques, Harris' bandwidth search (an adaptation of the A* procedure) appears very effective [Har74).

I have recently invented a new procedure called the B* tree search procedure which combines the best facets of best-first searching with branch and bound [Ber77). This procedure requires that an optimistic and pessimistic value be assigned to every node at the time it is generated. When the most optimistic (as seen from the opponent's side) successor of node N is better for the side on move at node N than the previously estimated pessimistic value, then this pessimistic value is adjusted to correspond with the most optimistic value of the opponent. In the same way the optimistic value at node N must be adjusted if the pessimistic value of the most pessimistic successor to node N (as seen by the opponent) is worse than the previously estimated optimistic value. In thi s way values are backed up from newly expanded nodes. To find the next node to expand, it is only necessary to trace the most optimistic (for both sides) p<~lh through the tree and expand that node, although other search strategies are possible: The search terminates when it can be shown that the pessimist ic value of a successor node to the root is at least as good as the best optimistic value of the remaining successors to the root.

DIAGRAM 1

In Diagram 1, we illustrate a simple search with 8*. The upper part shows an initial tree configuration, and the lower shows the tree upon completion of the search. Nodes in boxes have MAX to play; nodes in circles have MIN to play. The numbers inside the node symbols indicate the order in which nodes were expanded. The pair in brackets are the optimistic and pessimistic values at a node (updated by being crossed out). The search terminates because the pessimistic- value of the right-most descendant of the root is no worse than the optimistic value of any other descendant.

This search is guaranteed to converge as long as the estimates are consistent (though not necessarily correct). We believe that this algorithm will never expand more nodes than any other procedure having access to the same information. Thus it should be the best of the AND/OR tree searching procedures. It can be trivi.ally demonstrated that in its OR/OR form, it can never do worse than the A* [Nil70) procedure which is supposed . to be optimal. However, in all these procedures there are serious difficulties in finding reasonable functions for computing the bounding values.

C. Mechanism within the Search

We consider that the actual tree search procedure is strongly subordinate to the ability to reject searching of sub- trees based on the semantics of the search. This t y pe of pruning is supported by mechanisms that collect information (other than terminal values) during the sea.rch and back this up as the search progresses. Decisions are then made, based on the backed-up information, which allow pruning of large sub-trees.

The first of these mechanisms to appear was the Causality Facility [Ber74) in my chess program CAPS-II. This facility collected descriptions from nodes when backing up in a tree search. When it reached a node where the side on move was not satisfied with the b11cked up value of the search (measured against a global expectation level), that side set in motion the causality f acilily which examined the backed. up descri ption (called the refutation description). Current vers ions of the causality facility are able to determine whether or not the problem described by the refutation descri ption was caused by the current move at this node. If so, a lemma is posited which describes the partial position (out of "the current position) which makes the refutation description possible. Lemmas are also posited about winning moves. Whenever a move is suggested at some future point in the search, the lemma file is first examined to determine if a lemma exists about this move and if the partial board description matches. If so, the result of the move is assumed known and the search can be foregone. A similar system has been described by Adelson-Vel sky, el. al. [Ade75).

If the move in quest ion did not cause the current problem, then we know it to have existed when the current node was reached. Thus the backed up refutation description, describes this problem. The causality facility has mechanisms for generating the set of all moves (counter-causal moves) that can do something about the refutation description. This can save a tremendous amount of effort in ad hoc searching to find a solution. Sometimes the counter-causal set is empty so it is .known that the problem cannot be solved at this node and the search must back up further. Sometimes a proposed counter -causal move leads to another problem description which is also not caused by the move. Then it is known that there is more than one problem to solve at the current node, and any suggested move must be .on the li st of counter-causal moves for each such problem, a fact which radically reduces further search.

Another technique was recently demonstrated by Pitrat [Pit77). He used plans to guide the search. Plans were formulated to satisfy goals of winning ai least a certain amount of material. If such a plan failed, the reason for its failure was analyzed, and a plan for overcoming this difficulty was inserted into the appropriate place in the original plan. The description of the plan was pushed down the tree as the search progressed and only moves in accordance with the plan (as modified) were admitted to the search. This method was shown to develop small trees and solve many interesting chess problems.

The essence of techniques of thi s type is that a potential move is analyzed with respect to a speci fic purpose. If the move fails, then information is returned which can be used to improve the selectivity of the remaining search. It appears to this writer that these techniques are ripe for i!pplication to other areas, e.g. theorem proving, planning I echniques ..

Ill. Problems with certain Search Techniques

At times search is a very powerful technique, achieving things that humans may have difficulty in replicating, e.g. Samuel's checker program [Sam63l, Dendra! [Buc69), and CHESS 4.5 [Sia77). However, certain artifacts appear to be associated with some well known search techniques.

·Any procedure which changes the mode of search (including termination) at an arbitrary depth creates the conditions necessary for the Horizon Effect [Ber73). Thus searches to fixed depths must reconcile themselves to the possibility that the program will try to push unavoidable consequences over its search horizon, by conceding lesser (but avoidable) ones.

Techniques that search a large uniform space usually try to get the maximum value for each CPU . second of evaluation. This is because there are many nodes to be evaluated and a few extra microseconds per node may add an intolerable amount of lime to the whole search. Therefore ev<~luation must be lean. If a tree contains two or three reachable good nodes, the path to one of these will be selected depending upon very arbitrary factors. This is fine when all these nodes are very favorable. However, in delicate situations it would be highly de sir able to isolate the competing nodes and apply additional knowledge to them in an effort to find which is really best.

The minimax alpha-beta procedure is undoubtedly the most efficient of all known search procedures. However, a minimax procedure does very poorly at defending losing positions. In such cases, it will almost always choose the p<~th which postpones the opponent's win the longest. However, this is seldom the best way. In bad to hopeless situ<~tions it appears necessary to have an opponent model, no matter how primitive, and select moves based on the hope that the opponent is fallible and will thus not always find the best way. Thus, for instance, it would be emminenlly reasonable for a program to avoid losing a rook in an otherwise even position, at the cost of the opponent finding a difficult mate in five moves. However, any program using the minimax approach and discovering the opponent's mating possibility will defend against it and leave the rook to its fate. Further, in near equal positions it is sometimes wise to take small risks in the hope of gaining an advantage. This, too, is impossible with the minimax model.

IV. Knowledge Organization

When the search does not go to terminal nodes as leaf nodes. In goal directed searches knowledge is also needed to make guiding decisions, if any kind of

defined by the domain, knowledge is needed to evaluate · means-ends methods are used.

The results of Samuei[Sam63, Sam67) have always been inter preted to mean that a linear polynomial cannot adequately span a large domain such as checkers. However, recently Slate & Atkin [Sia77] have had great success with their chess program CHESS 4.5. This program uses essentially one evaluation function for the whole domain. The coefficients of the terms are desi~ned so that they change very slowly over the domain, and thus provide a sort of rolling landscape in the evaluation space. With this type of design, the program appears to always find something construc.tive to. do. It seldom gels stuck on a hill, since there is always a somewhat higher hill within searching distance from the present one.

However , it is not difficult to show that it is impossible to evaluate all states in a state-space correctly with a single (reasonable) function. In chess, for instance, there are positions where changing the location of one man by one square, or changing whose I urn it is, can make the difference between a win, loss, or draw. For many of these positions, even expert players will require some time to fully comprehend the va.lue of the situation. Therefore, the single function approach appears to have definite limitations, and it may be necessary to partition the state -space and make evaluation functions which are expert in certain state - classes only.

Such expert functions could show their worth when branches lead to leaf nodes representing very different kinds of positions. Consider Figure 1.

White can win by playing QxP because the K&P ending is won. But if the Black king were one square nearer to the center of the board, the K&P ending is a draw. Therefore, QxP is only effective now, and it is inconceivable that White can win any other way. In the single function ilpproach, it is almost inevitable that Q vs. R+P will be considered better than the materially even K&P ending. It would be simple to design functions which would judge both positions as superior for White. However, for the state-class approach to succeed it is necessary for the K&P endgame function to recognize · that endgame as a win. Otherwise, this opportunity will be missed. This shows that at times it is necessary to have excellent goodness ordering across state-class boundaries. However, merely recognizing the goodness of a position may not be sufficient. Consider Figure 2.

White to play

White has a winning position and can play K-83, K-K3, or K-K4, all of which retain the win. However, if he chooses either of the first two alternatives, he will be back in the current position in another three ply. This is an instance of the "make-progress" problem which can frequently be resol ved by the search, which notices that no progress has been made. However, in more complicated examples, thi s may not suffice. Notice that if in Figure 2 the White king were at QB2 then it would be sufficient to recognize the position resulting from K-83 as a win flcr.mur. t!.r.rc n.rt! 110 real .r.ornpclitnr$ to i1. Thus the make-progress is,; ue can be separate from the goodness issue. The make - progress issue was fir st treated by Huberman [Hub66) by having predi cates which recog(lized nearness to a mate in simple winning chess endgames. However, the problem exists both in winning positions and also in positions that are not clearly won, but where a path toward progress exists. Another issue is "how to put up resistance", which arises in bad or losing positions. This is not quite the inverse of make-progress, because while there may be a guarantee of progress in superior positions, it is up to the losing side to find the method of resistance which requires the most knowledge (or calculation) from the superio.r side.

To investigate the above knowledge issues, we have for some time now been investigating backgammon, a game which due to its non-deterministic nature has a branching factor of about 800 at each node. Thus full width searches in this environment (as in GO) are not sensible. Our program achieved the ability to di scriminate generally favorable and unfavorable factor s together with appropriate coefficients for a single evaluation polynomial. This design reached a high beginner level, but there were great problems in having it understand more by merely adding more terms and luning coefficients. In searching · programs, some of these problems are subordinated by the search, since the program does not have to know about "means" up to the search depth, and any position potential up to that depth also does not have We have now implemented several slate-classes which allow a great deal of context to be brought to bear on ;my evaluation. In some cases evaluation is iterative, so that additional knowledge is only invoked when competiti ve moves exist. These steps have caused a great jump in -performance of the program; however, it is still too ear ly to evaluate the whole approach.

V. A modest Proposal

All these problems appear to be due to the fact that game play ing programs indulge in one - pass evaluation of all nodes, i.e. the amount of knowledge that can be applied to a node has been predetermined. It is thus an efficient mnount of ~,nowledge, since applying all that is known would not be cost-effective most of the lime. While this is fine for picking out the correct branch when there are no real competitors, this does not work when sr.veral nodes are very close in value or when there are other factors such as creating opportunities for opponent error. (Much of thi s was already pointed out in [New55]). Here a mulli -s l age process which weighs the pros and cons of each competitor for best node is required. It would seem that an ideal framework in which to do this searcl~ is the B* algorithm. What is known about a node will increase as nodes in its sub-tree are expanded. Fur ther, the amount of knowledge being applied can be a function of the degree of competitiveness between nodes. A first attempt at this type of problem solving mechanism is reported in [Per77).