Using Plans in Chess

1. Introduction

One of the central concerns of artificial Intelligence Is expressing knowledge and reasoning with it. Chess has been one of the most popular domains for AI research, yet brute force searching programs with little chen knowledge play better chess than programs with more chess knowledge. There Is still much to be learned about expressing and using the kind of knowledge Involved In playing chess. CHESS i.7 Is probably the best chess program, and Its authors make the following comments In (I 1]:

But rtJIJy is tltt program so devoid of cltess howltdgt1 Our probltm is tltat tltt programming tools wt art presently using are not adtquatt to tltt taslt. Too muclt worlt is needeil to encode tfte sizable bod' of howltdgt nttded to stgnijicantl1 improve tlte quality of play.

Human masters, whose play Is still much better than the best programs, aJ?r.ear to use a knowledge Intensive approach to chess (see (2] . The purpose of this research Is to investigate the Issues Involved In expressing and using pattern-oriented knowledge to analyze a chess position, to provide direction for the search, and to communicate useful results from the search. To reduce the amount of knowledge that must be encapsulated, the domain of the program has been limited to tactically sharp middle game positions. The phrase "tactically sharp" Is meant to Imply that success can be judged by the gain of a material rather than a positional advantage. The complexity of the middle game requires extensive search, providing a good testing ground for attempts to replace search with knowledge and to use knowledge to guide the search and communicate discoveries from one part of the tree to another.

Since, In our chosen domain, the attacking side can generally win material with correct /lay, the program uses different models for the offensive an defensive players. The offensive player uses a large amount of knowledge, suggests many esoteric attacks, and Invests much effort In making sure a plan Is likely to work before suggesting it. The defensive player uses less knowledge and effort, tries any defense that might work, and tries only obvious counter attacks. Trying every reasonable defense enables the of~nse to satisfy Itself that a line really does win. The size of the tree Is kept small because the offensive player often finds the best move Immediately.

For a knowledge based program to achieve master level performance, It seems essential that the knowledge base be amenable to modifications and additions. PARADISE provides for easy modification of and addition to Its knowledge base (without adversely affecting program performance), by having the knowledge base composed of largely independent production rules which are written In a straightforward Production-LAnguage (see ( 12)). The goal Is to build an expert knowledge base and to reason with It to discover plans and verify them with a small tree search. As long as this goal Is reached, the amount of execution time used Is not Important. When a desired level of performance Is reached, the program could be speeded up considerably by switching to a more efficient representation at the cost of transparency and ease of modification.

~\11/fi]A~.~~ 2. PxPch K-N3

~.1~.1 :~: ~k 4. R-IISch K-N3

5. R·ll6ch K-N4 ~~ ~~/~· -~ 0~ 6. R-N6ch K-RS

~~~&~=~~~ 8. RxNch K·R4

,,~//&~~~~ 7. R-K4ch N-BS

i ~~ ~r--~ ~~- , 9. P-N3

Figure 0 · white to move

Because It grows small trees, PARADISE can find deeper combinations than most chess programs. Figure 0 Is an example of such a combination from an actual master game. White can mate by sacrlficln& his queen and playing nine additional moves (against blacks line of longest resistance), the next to last move not being a check. Thus the search tree must go at least 19 ply deep to find this combination. This Ia considerably deeper than any other current chess program could probe In a reasonable amount of time, but PARADISE solves this problem after generating a search tree of 109 nodes, In 20 minutes of CPU time on a DEC KL-10.

2. Overview of PARADISE

PARADISE uses a knowledge base consisting of about 200 production rules to find the best move In chess positions. Every production has a pattern (I.e., a compte:<, Interrelated set of features) as Its condition. Each production can be viewed as searching for all Instances of Its condition pattern In the position. For each Instance found, the production may, as Its action, post concepts (described In the next section) In the data base for use by the system In Its reasoning processes. The data base can be considered as a global blackboard where productions write Information. The productions are built up by levels, with more primitive patterns (e.g., a pattern which matches legal moves) being used as building blocks for more complex patterns. A search tree (the major component of most chess programs) Is used to show that one move suggested by the pattern-based analysis Is In fact the best.

To offset the expense of searching for patterns in the position, problems must be solved with small search trees. In fact, PAR A DIS E can be v lewed as shifting some of Its search from the usual chess game tree to the problem of matching patterns. PARA DJSE shows that Its pattern-oriented knowledge base can be used In a variety of ways to significantly reduce the part of the game tree which needs to be searched. This reduction Is l·rge enough that a high level of expertise can be obtained without placing a depth limit (or any other artificial effort limit) on the search. The various ways in which the knowledge base Is used are brleny mentioned below.

Calculating primitives. PARADISE's knowledge base contains about twenty patterns (productions without actions) which are primitives used to describe a chess position. These patterns are matched once for each position. They range from matching legal moves to matching any move which can be made without Immediate Joss of material. The primitives are relatively complex and calculating them Is expensive.

Static analysis. Given a new position, PARADISE does an expensive static analysis which uses, on the average, 12 seconds of cpu time. This analysis uses a large number of productions In the knowledge base to look (or threats which may win material. It produces plans which should guide the search for several ply and should give Information which can be used to stop the search at reasonable points.

Produci ng plans. The knowledge base Is used to produce plans during static analysis and at other times. Through plans, PARADISE uses Its knowledge to understand a new position created during the search on the basis of positions previously analyzed along that line of play, thus avoiding a static analysis. Plans guide the search and a static analysis is only occasionally necessary In positions created during the search. Producing a plan Is not .as simple as suggesting a move, It involves generating a large amount of useful Information to help avoid static analyses along many different lines and to help detect success or failure o( the plan as it Is executed. (Examples are given later.)

Executing plans. The execution of a plan during the tree search requires using the knowledge base to solve goals specified In the plan. This use of the knowledge base could be viewed as a static analysis where the system's attention Is focused on a particular goal or aspect of the position. Such a focused analysis can be done at a fraction of the cost of a full analysis which examines all aspects of the position.

Generating defensive moves. PARADISE does static analyses and executes plans only for the offense (the side for which It Is trying to win material). To prove that an offensive plan succeeds, the search must show a winning line for all reasonable (I.e., any move which might be effective) defensive moves. Productions In the knowledge base are used to generate all the reasonable defenses.

Quiescence searches. When a node Is a candidate for termination of the search, PARADISE uses a quiescence search to determine Its value. This quiescence search may return Information which will cause the termination decision to be revoked. Productions In the knowledge base provide much of the knowledge used In PARADISE's quiescence search. Q..ulescence searches In PARADISE Investigate not only captures but forks, pins, multi-move mating sequences and other threats. Only one move Is Investigated at each node except when a defensive move fails.

Analysis of problem upon failure. When either the defense or offense has tried a move that failed, the search analyzes the Information backed up with the refutation In an attempt to solve the problem. The knowledge base Is used In this analysts to suggest plans which thwart the opponent's refutation. In this way PARADISE constructs new plans using the Information gained from searching an unsuccessful plan.

Answering questions. The search often requests certain kinds of Information about the current position. The knowledge base Is used to provide such Information. The most frequent requests ask If the position Is quiescent and If there are any obviously winning moves In the position.

The above list describes eight general functions the knowledge base performs for PARADISE. This paper explains how plans are produced and executed. The productions, the static analysis, the tree search, and mechanisms for communicating Information from one part of the tree to another are discussed In (12].

3. The Need for Concepts

To understand a chess position, a successful line of play must be found. Human masters understand concepts which cover many ply In order to find the best move. A knowledge based program must also have the ability to reason with concepts that are higher level than the legal moves In a chess position. The following position from [I J illustrates this.

In the above position, most computer chess programs would search the game tree as deep as their effort limit allowed and decide to play K-K3 which centralizes the king. They cannot search deep enough to discover that white can win since white's advantage would take more than 20 ply to show up in most evaluation functions used by computer programs. The point Is that the solver of the above problem uses conceptual reasoning to solve It, and the concepts must be higher level than the legal moves In a chess position. A human master would recognize the following features (among others) In the above position: the black king must stay near his KBI to prevent white's king bishop pawn from queening, the pawns form a blockade which the kings can't penetrate, and the kings can bypass this blockade only on the queen rook file.

For a knowledge based program to solve this problem, It must be able to express concepts at the level of conceptualization used above. The system must combine and reason with these concepts In unforseen ways. In the above example, the blockading concept would be used to develop the plan of moving the white king to the queen rook file In order to bypass the blockade, but If both black and white had pawns on their Q.Ni then the blockading concept would be used to decide that neither king can invade the other's territory. Expressing and using concepts is a major problem for a knowledge based chess program.

To clarify the problems Involved In using concepts to reason about chess, a comparison to a well-known "expert" system such as MYCIN Is helpful. The following phrase Is the action part of a typical MYCIN rule (from [3]): tAtn tAtrt ts suggestive evtdtnct (.'l) tl.at tAt tdtnttty of tAt organtsm ts bacttroidts. Such an action effectively adds to the plausibility score for some possible answer. This presupposes that any one writer of all the rules knows every possible solution since such rules will never create a diagnosis that has not been mentioned in the action part of some rule. Such an approach Is not satisfactory for the type of rea~oning needed In figure I.

Using actions similar to those used in MYCIN rules would be similar to a chess system where the action part of each rule was to add to the plausibility score of either I) one or more of the legal moves In the position, or 2) some prespecified object which could lead (through other rules) to recommending a legal move. Such a system would not be able to reason that a king must get past a pawn blockade to attack an opponent's pawn chain since objects cannot be prespeclfied (e.g., the extent of the blockade and whether or not the kings want to get around It must be determined dynamically). PARADISE must reason by linking concepts to create plans that are not implicit in the knowledge base, instead of filling In ,Prespecified slots. To compare actual production rules, MYCIN s actions mention the names of objects while PARADISE's actions involve many variables whose Instantiation Is not determined until execution of the action.

4. Knowledge Sources and Concepts

When a production In PARADISE matches, It may have an action part which posts various concepts in the data base. The program is able to express and use concepts by dividing its knowledge base Into various Knowledge Sources. Each Knowledge Source (KS) provides the knowledge necessary to understand and reason about a certain type of concept. In Its simplest form, a KS Is a group of productions which knows about some concept and a list of variables such that an Instantiation of the variables represents an Instance of this concept. For example, the SAFE KS In PARADISE has two variables, PI and SQ, and contains productions which know how to make the particular square SQ. safe for the piece PI. With this KS, the system can use the concept of a square being safe for a piece In Its reasoning, in the expression of plans, and In the communication of discoveries from the tree search. Such concepts are a level above the patterns recognized by the productions themselves.

When a concept has a corresponding KS, PARADISE will eventually treat each Instance of that concept which Is present In the data base as a subgoal and use the corresponding KS to solve the subgoal In an attemet to produce a plan to realize that Instance of the concept. (This may be done by creating other Instances of other concepts.) There may also be concepu that have no corresponding KS and are not treated as subgoals. Such concepts are inspected by patterns attempting to match and by the searching routines. When a concept or an Instance of a concept corresponds to a KS, It will sometimes be referred to as a goal or subgoal.

Concepts In the data base must contain all the Information that will be needed to execute other KSes and to guide the search (see [12]). Among other things, KSes usually expect Information on how likely a goal Is to succeed and on how threatening a goal Is (this Is useful in deciding If a sacrifice Is warranted). PARADISE stores Information about concepts on a list of attribute-value pairs, called an attribute list. For reasons discussed In [12], a particular concept Is expressed by giving Its name, an Instantiation of Its arguments, and a list of attribute lists (one for each reason the concept was suggested).

When a production accesses the values of attributes In a concept, It may not care which attribute list the values come from, or It may require that the values for each attribute come from the same list, or It may want the "best" (in some sense) value for each attribute whether the different . values come from the same list or not, or It may want values for one attribute to come from lists which have some particular value for another attribute. This accessing of the information In a concept Is so complex that it can be looked on as pattern matching In Itself. Thus the productions In a KS can be looked upon as matching patterns In the given chess position and matching patterns In different concepts.

Concepts and their accessing are quite complex. Intuitively, the productions In PARADISE are not making deductions, per se, but coming up with Ideas that may or may not be right. Thus there are no "facts" that have certain deduced vafues that can be reasoned with. The complexity of later ana~sls requires that a production essentially put down "why it thought of an Idea. In this way, other productions can decide if the Idea still looks right In light of what Is known at that time. Most production systems avoid this complexity because the firing of a production Is a deduction which adds a new piece of knowledge to the system. This piece of knowledge Is assumed rl&ht and the system Is not prepared to later decide that it wasn t right to make that deduction.

5. Plans

The goal of the static analysis process In PARADISE Is to produce plans. Plans seem to play an important role In the problem solving process of move selection for good human chess players. Alexander Kotov In [6] writes:

... tt is better to follo!IJ out a plan consistently even if it isn't tlte best one titan to play tuitltout a plan at all. Tltt lllorst tltlng Is to lllander about aimlessly. (p. 148)

Most computer chess programs certainly do not follow Kotov's advice. In a knowledge based program, the cost of processing the knowledge should be offset by a significantly smaller branching factor In the tree search. Plans help reduce the cost of processing knowledge by Immediately focusing the program's attention on the critical part of a new position created during the search, thus avoiding a complete re-analysis of this new position. Having plans also reduces the branching factor In the search by giving direction to the search. Consider, for example, that most programs may try the same poor move at every alternate depth In the tree, always re-discovering the same refutation. PARADISE can detect when a plan has been tried earlier along a line of play and avoid searching it again If nothing has changed to make It more attractive. Most programs also suffer because they intersperse moves which are Irrelevant to each other and work towards different goals. PARADISE avoids this by following a single Idea (Its plan) down the tree.

Plans In PARADISE can be considered as special instances of concepts since each plan has a list of attribute lists. Instead of a list of Instantiations for a set of variables (as in a concept), a plan has an expression in the Plan-Language. The Plan-Language expresses plans of action for the side about to move, called the offense. In general, the offense wants to have a reply ready for every defensive alternative. A plan cannot therefore be a linear sequence of goals or moves but must contain conditional branches depending on the opponent's reply. When the offense Is on move, a specific move or goal is provided by the plan. When the defense Is on move, a list of alternative sub-plans for the offense may be given. Each alternative begins with a template for matching the move made by the defense. Only alternatives whose template matches the move just made by the defense are tried In the search. PARADISE has the following templates which adequately describe defensive moves In terms of their effects on the purpose of the plan being executed (P and SQ. are variables which wi ll be Instantiated In an actual plan to particular pieces and squares, respectively): (P SQ) matches when the defense has moved the piece P to the square S~ (NIL SQ) matches when the defense has moved any piece to S~ (P NIL) matches when the defense has moved P (to any square), (ANYBUT P) matches when the defense has moved some piece other than P, and NIL matches any defensive move.

The plan for an offensive move can be one of two things: a particular move or a goal. A particular move Is simply the name of a plecl!! and a square. Such a plan causes PARADISE to Immediately make that move with no analysis of the position other than checking that the move Is legal. A goal Is simply the name of a KS followed by an Instantiation for each argument of the KS. When executing a goal, PARADISE will construct an Instance of the KS's concept In the data base by using the given Instantiations and the attribute lists of this plan as a whole. The KS will then be executed for this concept- Instance (goal). Any plan produced by this execution will replace the goal In the original plan and this modi fied plan will be used. This process expands and elaborates plans. If executing the KS does not produce a plan then the original plan has failed.

(((WN NS) (((BN N4) (SAFEMOVE WR 07) (((BK NIL) (SAFECAPTURE WR BR)) ((ANYBUT BK) (SAFECAPTURE WR BK)))) ((BN N4)(CHECKHOVE WR 07)(8K NIL)(SAFECAPTURE WR 80)))~ ((THREAT (PLUS (EKCHVAL WN NS)(fORK WR BK BR))l(LlKELY 0 ) ((THREAT (PLUS (EKCHVAL WN NS) (EKCH WR BQ))) LIKELY 0) ) Figure 2 a plan produced by PARADISE (white to move)

Figure 2 shows a problem and one of the plans PARADISE's ~tatt; analysis produces for it. ("WN" means white knight, N5 means the square N5, etc. It should be obvious to which white rook "WR" refers.) The last two lines of the plan are attribute lists. The first five lines are the Plan-Language expression for the plan which can be read as follows:

Play N-N'. If black capturts tAt knigAt witll Ais kntgllt, attempt to safely move tile rook on Ql to Q7. Tlten, if black moves ltis king anywAert try to safely capture tAt black rook on R7, and If black moves any piece otlter tAan !tis king, try to safely capture tlte king tuitll tlte rook. A second alternative after black captures tlte knlgltt Is to attempt to safely move tlte rook on Ql to Q1lllttlt clteck. Tlten, If black moves !tis king anywllm tr' to safely capture tlte black queen lllitA tlte rook.

SAFEMOVE, SAFECAPTURE, and CHECKMOVE are all KSes in PARADISE. After playing N-N5 and NxN for black In the tree search, PARADISE will execute either the CHECK MOVE goal or the SAFEMOVE goal. Executing the SAFEMOVE goal executes the SAFEMOVE KS which knows about safely moving a piece to a square. This KS will see that R-Q.7 Is safe and produce this as the continuation of the original plan, causing the system to play R-Q.7 with no further analysis. If for some reason R-Q.7 was not safe then the SAFEMOVE KS will try to make Q.? safe for the rook (by posting a SA FE concept). If some plan Is found, the original plan will be "expanded" by replacing the SAFEMOVE goal with the newly found plan. In general, the newly found plan will contain (SAFEMOVE WR Q.7) though It may come after a sacrificial decoy or some other tactic. If posting the SAFE concept does not produce a plan, then the SAFEMOVE goal has failed, and the alternative CHECKMOVE goal will be tried. If It also falls, a complete analysis of the position must be done. If black. had answered N-N5 with a king move, It would not match the template (BN N4) and a complete analysis of the position would be undertaken without attempting to make Q.7 safe for the rook.

A detailed description of the static analysis process in PARADISE Is given In [12). PARADISE suggests the plan in figure 2 for two different reasons. One of these two ways of suggesting this plan Is briefly traced below. The system begins by posting a THREAT concept since the THREAT KS has productions which look for threats. One production recognizes the white rook could skewer the black king and rook from Q,.7 so It posts a MOVE concept which says the white rook would be well placed on Q). A production in the MOVE KS, that recognizes that R-Q..? Is unsafe, matches and posts a SAFE concept for making Q..? safe for the white rook. While executing the SAFE KS, one production notices that the black knight blocks the white queen's protection of Q..?, and posts a DECOY goal. The DECOY KS has a production which posts a FORCE goal suggesting N-N5 as a move to decoy black's knight. The plan In figure 2 has been built up at this point, although more KSes are executed (to check for effects) before the final plan Is posted.

6. Discussion of plane in PARADISE

By use of conditionals, a plan can handle a number of possible situations which may arise. The most Important feature of the Plan-Language Is that offensive plans are upressed In terms of the KSes. This has many advantages. Relevant productions are Immediately and directly accessed when a new position Is reached. The system has one set of concepts It understands (the KSes) and does not need to use a different language for plans and static analysis. The system has been designed to make the writing of productions and thus the forming of KSes reasonable to do. Thus the range of plans that can be expressed Is not fixed by the Plan-Language. By forming new KSes, the range of expressible plans may be Increased without any new coding (in the search routines or anywhere else) to understand the new plans. This Is Important since the usefulness of the knowledge base Is limited by Its ability to communicate what it knows (e.g., through plans).

Given a number of plans to execute, the tree search must make decisions about which plan to search first, when to forsake one plan and try another, when to be satisfied with the results of a search, and other such things. To make such decisions, It must have Information about what a plan expects to gain and why. Such Information was avaUable to the productions which matched to produce the plan and must be communicated In the attribute lists of the plan so as to provide many different types of access to this knowledge. Unlike most search-based chess programs, PARADISE must use Its Information about a plan at other nodes In the tree since It executes a plan without analyzing the newly created positions.

To use the information about plans in an effective manner, PARADISE divides a plan's effects Into four different categories which are kept separately (I.e., their Yalues are not combined In any way). These four categories are: THREAT which describes what a plan threatens to actively win, SAVE which describes counterthreats of the opponent a plan actively prevents, LOSS which describes counterthreats of the opponent not defended against and functions the first piece to move In a plan will give up by abandoning Its current location (thus providing new threats for the opponent), and LIKELY which describes the likelihood that a plan will succeed. These four categories have emerged during the development of PARA DIS E. Experience seems to indicate the system must have at least these four dimensions along which to evaluate plans In order to adequately guide the tree search.

Since the values for these categories must evaluate correctly at different nodes In the tree, they cannot be Integers. Instead they (except LIKELY) are expressions In the Threat-Language ([ 12)) which can describe threats In a sophisticated manner. These expressions are evaluated in the context of the current position and may return different values for different positions. The value of LIKELY is an Integer which represents the number of unforced moves the defense has before the offense can accomplish its plan. The most likely plans to succeed (e.g., the plan In figure 2) have a LIKELY of zero (every move Is forcing).

The system must quickly recognize when a plan Is not working and abandon It before effort Is wasted Investigating poor lines. On the other hand, It Is expensive to completely analyze a position, so the system wants to use Its plan as long as possible. To achieve a balance, plans must adequately express the purpose they Intend to achieve. Productions must carefully formulate their Plan-Language expressions at the right level of detail using appropriate goals and descriptions of defensive moves. When executing a pla.n, the system will retrieve a goal or move from the plan to apply to a new position. Care must be taken to ensure that this move or goal is reasonable In the new position. For example, a plan which specifies that any check be played may lack detail and cause many poor checks to be Investigated. On the other hand, if the plan specifies an actual move to attack the king, It may be too detailed since this move may no longer check the king In the new position (again a poor line Is Investigated). Plans should express their purpose by describing how the king should be attacked.

A plan should handle as many replies as possible without causing a re-analysis, but It . should avoid suggesting poor moves. The templates for describing defensive moves in the Plan-Language and the various KSes have been developed to allow PARADISE's plans to accurately express their purpose. The results have been quite satisfying: the productions In PARADISE now create plans which rarely suggest poor moves but which can still be used for as many ply as a human might use his original Idea.

7. Using Plane to Guide the Search

Figure 3 depicts a position from [8) and shows the plan PARADISE suggests as best after a static analysis. To show how such plans are used to guide the search, PARADISE's search for this position Is sketched below.

The search commences execution of this plan by playing Q.xPch and producing a new board position. The defense suggests both legal moves, K xQ. and K-B I, but tries KxQ. first. Since this move matches the (BK RZ) template In the plan, PARADISE has ((CHEW10VE IIR RS) (BK NIL) (ATTACKP BK)) as Its best plan at ply 3 of the search. Execution of the CnECKMOVE KS produces ((IIR RS) (BK NIL) (ATTACKP BK)) as a plan which causes R-R5ch to be played. Black plays his only legal move at ply 1, K-N I, which matches the (BK NIL) template In the plan. Thus PARADISE arrives at ply 5 with (ATTACKP BK) as Its plan. Executing the ATTACKP KS posts many concepts, Including MOVE and SAFE concepts, and (( liN N6) ((NIL (SAFEMOVE IIR RB)) (NIL (SAFEHOVE liN K7))) Is produced as the best plan In this position. After playing N-N6, the position in figure 1ls reached.

Productions which know about defending against R-R8 suggest (88 R6)(BB 02)(88 N2)(8R 84)(8R 83)(BR Bl) . Black plays BxP first in an effort to save the bishop from the ensuing skewer. At this point the plan branches. Since both branches begin with a null template, they both match any black move at ply 6. Thus PARADISE has two plans at ply 7: (SAFEMOVE IIR RB) and (SAFEHOVE liN K7). Before executing a plan for the offense, PARADISE executes the Q.UIESCENCE KS which looks for obviously winning moves. Here R-R8 Is suggested by the Q.UIESCENCE KS which causes the (SAfE MOVE WR RB) plan to be executed Immediately. PARADISE plays R-R8, finds that black Is mated, and returns to ply 6 knowing that black's BxP leads to mate. All this has been accomplished without a static analysis; the original plan has guided the search.

At ply 6, black uses KSes to refute the mating line. No new moves are found since all reasonable defenses have already been suggested. PARADISE has a causality facility which determines the possible effects a move might have on a line of play. Using the tree generated for the mating line, the causality facility looks for effects a proposed move might have (such as blocking a square which a sliding piece moved over, vacating an escape square for the king, protecting a piece which was attacked, etc.). The causality facility recognizes that neither B-Q.2 nor B-N2 can affect the mating line found for BxP so they are rejected without searching. Black plays R-B{ next, the causality facility having recognized that this move opens a flight square for the black king. Again PARADISE has both (SAFEMOVE IIR R8) and (SAHMOVE liN K7) as plans at ply 7. Both SAFEMOVE goals would succeed, but R-R8 has a higher recommendation and is played farst . Black plays has only legal move at ply 8, K-B2. PARADISE no longer has a plan at ply 9. Before trying a static analysis, It executes the Q.UIESCENCE KS In an attempt to find an obviously winning move. R-KB8 Is suggested and PARADISE Immediately plays this move without doing a static analysis. This is mate so PARADISE returns to ply 6 to look for other defenses. Both R-B3 and R-BI are tried and both are quickly refuted by playing R-R8 from the SAFEMOVE goal of the original plan, K-B2, and R-KB8 from the Q.UIESCENCE KS. The search then returns to ply 2 and tries K-B I In answer to Q.xPch. The template In the original plan does not match K-B I so there Is no plan at ply 3. However, the Q.UIESCENCE KS quickly suggests Q.-R8 and PARADISE returns from the search convinced that Q.xPch will mate.

PARADISE's plans are not always so accurate but space prevents presentation of a longer search. The above analysas uses about 130 seconds of cpu time on a DEC K L- I 0. It goes to a depth of 9 ply while creating only 21 nodes In the tree. Because of the guidance provided by the original plan, no static analysis was performed except on the original position. By coml'arlson, the TECH2 program (an Improved version of TECH [5)) at a depth setting of 6 discovers that It can win material with Q.xPch although the horizon effect hides the mate from it. For this analysis, TECH2 uses 210 seconds of cpu time and creates 'f39,159 nodes by making legal moves (It also makes and retracts 511,768 illegal moves).

8. Measuring PARADISE'· performance

To aid In evaluating performance, PARADISE was tested on positions In [8). This book contains tactically sharp positions from master games which are representative of tactical problems of reasonable difficulty. PARADISE's knowledge base was developed by writing productions which would enable the program to solve, In a reasonable manner, fifteen chosen positions from among the first 100 In [8]. The 85 positions not chosen were not considered during this development. This development process produced one version of the program, called PARADJSE-0. Six positions were then picked at random from the remaining 85 and accurate records were kept on the work Involved In getting the program to solve these reasonably. The version of the program which solves all 21 positions Is called PARADISE.

PARADISE's performance on a problem Is classified Into one of three categories: I) problem solved as Is (possibly with a minor bug fix), 2) problem not solvable without a change to the program or a major change to the knowledge base, or 3) problem solvable with a small addition to the knowledge base. Category 3 helps measure the modifiability of the knowledge base. It Is meant to Include solutions which require no changes whatsoever to the program and only a small addition to the knowledge base. Small means that it takes less than 20 minutes total of human time to Identify the problem and write or modify one production which will enable PARADISE, with no other changes, to solve the problem In a reasonable way (I.e., no ad hoc solutions).

Of the six positions chosen at random, two were In category I, three were In category 3, and one was in category 2. This latter one Inspired the only program changes between PARADISE-0 and PARADISE. These results speak well for the modifiability of the knowledge base, but shed little light on the generality of the program. To better test generali ty, PARADISE has been tested on the first 100 positions. These positions are divided Into 5 groups of 20 and Reinfeld claims an Increase In difficulty with increase In group number. (Eaght endgame positions were eliminated, so the groups actually have 18, 19, 18, 20, and 17 positions.) PARADISE Is considered to solve only the problems In category I, wh ile PARADISE-2 solves both category I and 3 problems. PARADISE would become PARADISE-2 simply by leaving In the productions written to solve problems in category 3. The following table shows what percentage of these problems can be solved by PARADISE, PARADISE-2, CAPS [1], TECH [5], CHESS 4.4 [II] running on a CDC 6100, and a human rated as class A [ 1 ]. PARADISE was limited to 15 minutes of cpu time per problem while the other programs were limited to 5 minutes.

PARADISE PARADISE-2 CAPS TECH C-4.4 HUMAN

There were 20 problems In category 3 In the first 100, but only 13 productions were written to solve them. In two instances, an already existing production was modified. In five Instances the same production solved 2 different category 3 ~roble~s. Th1s Is a strong Indication that the productions bemg_ wratten are fairly general and not tailored to the . specifiC. problem. PARADISE already exhibits more generality In thiS domam than programs like TECH and CAPS. The figures for PARA DISE-2 show that these problems do not push the limits of the expresslblllty of the production language nor the ablhty of the program to control the tree search. These results Indicate that the generality of PARADISE .is reasonable and that the modifiability of the knowledge base ts excellent.

It should be noted that PARADISE uses considerably more cpu time and produces trees with considerably fewer nodes than either of the other programs. The following statistics were complied for the 89 problems which PARADISE-2 solved In these 92. PARADISE averaged five and one-half minutes of cpu time per problem (it ranged from 19 seconds to 1958 seconds). and generated an average of 38 nodes per problem (ranging from 3 nodes to 215). On the average, PARADISE spent 53~ of its time calculating primitives. There were an average of 3.7 static analyses done per problem, and less than 9~ of the nodes generated had static analyses done on them. This shows that the plans do a good job of guiding the search.

9. Comparison to Plane In Robot Problem Solving

Plans are used In many domains of AI research, especially robot problem solving. A BSTRIPS [9], NOAH [10], and BUILD [4] are examples of planning systems In robot problem solving environments. Plans In these systems are very different from those In chess so a summary of these differences Is more appropriate than a detailed comparison. These differen~es are explained In greater detail in [ 12]. Robot plannmg Is frequently done In abstracted spaces which hav~ been defined, and which omit details. Such an approach IS much mqre difficult in chess, at least with mankind's current understanding of the game. It Is not clear how to define abstracted spaces. Small details are very important In chess and cannot be readily Ignored.

In the robot planning systems, the effects of an action are well defined. The program can easily and quickly determine the exact state of the world after an action. In chess, moves (actions) may subtly affect everything on the board. Chess plans cannot make many assumptions about the state of the world In the future, but must describe the expected features of new states In the plan Itself and then test for these features while executing the plan.

In most robot planning systems, tests for having achieved the goal or the preconditions of an action are trivial and give well defined answers. In chess, there may be only very subtle differences between a position where a particular action Is good and positions where the same action Is wrong. It Is also hard to know when a goal has been achieved, since there Is always a chance of obtaining a larger advantage. (except when the opponent has been checkmated). Thus an chess It Is necessary for the plan to provide a considerable amount of information to help in the making of these decisions. This Is done In PARADISE through the attribute lists In plans.

The number of things PARADISE can consider doing at any point In a plan Is about an order of magnitude larger than the number of things most robot problem solvers usually contend with. There are an average of about 38 legal moves in a chess position (see [2]). When planning farther in the future than just the first action, the chess planner has many more choices than the 38 legal moves, The inability to make assumptions about future states often prevents mentioning actual moves In a plan. Instead a description of the intent is needed, and the number of such descriptions Is much larger than the number of legal moves that might be made. A robot usually has a much smaller number of possible actions, so the two types of plans explode at very different rates.

The robot planners have the flavor of establishing a sequence from a small number of well-understood operations until the correct order Is found, while chess planners have more a navor of "creating" the correct plan from the many possibilities. For this reason, a system which produces good chess plans needs a large amount of knowledge and non-trivial reasoning processes to produce plans. Plans In PARADISE differ from those In robot problem solvers by specifying powerful knowledge to be applied in new situations. Plans essentially giv.e PARADISE a perspective to use when analyzing a new position.

10. Comparison to Plans in Chess

Pltrat's program [7], which solves chess combinations, Is the most important example of the use of plans In chess. The language Pltrat uses for expressing plans has four statements with the move statement and modification statement being the most important. The move statement specifies that the piece on one particular square should move to another particular square. It may also be specified that the move must be a capture. The modification statement describes a modification to be made to a particular square. This can be one of four things: removal of a friend, removal of an enemy, moving a friend to the square, or getting an enemy to move to the square.

Plans In PARADISE provide much more nexiblllty In expression than Pltrat's move statement. In PARADISE, types of moves other than captures can be specified (e.g., safe moves). Also, particular squares do not need to be named In PARADISE since it can use a variety of goals to express the plan. The Important square to move to may change depending on the opponent's move so It Is not always possible to specify such a square In advance. Pitrat's modification statement Is a goal which the system tries to accomplish. These modifications are too simple to express the purposes behind their suggestion. For example, the system may want to decoy the black queen to make a square that it protects safe for white. Pltrat woul~ express this goal as removing an enemy from the black queens location which does not express the purpose of the plan. It will work well for the winning combination but will also allow many wrong moves since the queen may be decoyed to a square from which she can still protect the square tn question. PARADISE would specify that the black queen must be decoyed to make the particular square safe, and only decoys which remove the black queen's protection would be considered. PARADISE attempts to express the purpose of each plan while Pltrat's plans express side effects that will happen If the purpose Is accomplished (e.g., a square becoming vacant). Unfortunately, the same side effects may also happen when the purpose Is not accomplished, causing the system to waste effort searching poor lines.

Plans in PARADISE have two more major advantages over the plans In Pltrat's system. First, PARADISE has conditionals which allow specification of different plans for different replies by the opponent. The advantages of this are obvious: the system can Immediately try the correct . plan Instead of searching an Inappropriate plan and backtracktng to correct itself. Second, PARADISE's plan language Is modifiable. Simply by writing new productions, new goals and concepts can be created for expressing plans and the system will automatically understand these new plans. This property ts necessary for any system that wishes to extend Its domain or Incrementally Increase Its expertise. Significant addtt1ons to Pltrat's plan language would seem to require a major programming effort.

It should be noted that Pitrat's program processes nodes much faster than PARADISE and therefore can handle larger trees. It may be the case that programs will obtain better performance by using larger trees and less sophisticated plans, but the use of knowledge Is only starting to be investigated by programs such as PARADISE and It is too early to draw conclusions.

11. Summary

PARADISE exhibits expert performance on positions it has the knowledge to understand, showing that a knowledge based approach can solve some problems that the best search based programs cannot solve because the solutions are too deep. The knowledge base Is organized Into KSes which provide concepts for PARADISE to use In Its ·reasoning processes. These concepts are at a higher level than the Ideas produced by simply matching patterns. PARADISE's knowledge base Is amenable to modification. Production rules (and therefore KSes) can be quickly written and Inserted In the knowledge base to Improve system performance without adverse affects.

The concepts provided by the KSes are used to. create plans during static analysis. The concepts commumcate enough Information that they can be rejected after being posted. The same concepts are used to express plans for guiding the search, and the KSes execute the plans during the search. By communicating plans down the tree, PARADISE . can understand new positions on the basts of Jts analysis of previous positions. By having particular ~oals In mind when looking at a new position, the system qu1ckly focuses on the relevant part of the data base and avoids using all its patterns. Plans In PARADISE express their purpose fa1rly well, Without betng too general or too specific. Because of the successful communication of knowledge through plans, PARADISE Is able to solve a number of chess combinations with small trees and without a depth limit on its search.

One of the major bsues In creating concepts Is their generality. If the concepts are too general then too many details are lost, and the system does not have the necessary facts to do certain reasoning. If not general enough, the system leans toward the extreme of needing a production for every pomble chess position. The concepts in PARADISE have been constructed to be as general as possible without sacrlflctng expert-level performance to the loss of detail. The tradeoff of generality and specificity In concepts Is closely related to the tradeoff of search and knowledge. With much spectftc knowledge the use of knowledge becomes expensive, but fewer mistakes need to be corrected In the search. With more general knowledge, analysts Is cheaper but more time must be spent correcting mistakes in the search. PARADISE uses a mix of search and knowledge which Involves more knowledge and less search than previous programs which Include chess middle games In their domain. This type of research should strive for generality within the confines of Its commitment to knowledge-based expert performance.