Implementing Search Heuristics Using the AL1 Advice-Taking System

Implementing Search Heuristics Using the AL-1. Advice-Taking System

Ivan Bratko Faculty of Electrical Engineering and J. Stefan Institute· University of Ljubljana 61000 Ljubljana· Yugoslavia

The AL1 System <Advice Language 1> was developed as a vehicle for conveying expert knowledge· or advice· to a problem solver. Using chess end-games as an experimental problem domain· this paper concentrates on the question: How to implement chess heuristics using the mechanisms of AL1? The spirit of advice programming as a sort of "tree-search engineering" is illustrated by developing an AL1 piece-of-advice for solving an example problem from the king-knight vs. king-rook chess ending. Experiments indicate that an advice program for this ending· based on comparatively simple concepts· and the human chess master perform comparably.

t. INTRODUCTION

Two main themes motivated the development of the AL1 system <Advice Language 1 r.3,6J): <1> To obtain a linguistic vehicle for conveying expert knowledge· or advice. to a problem solver· and <2> to facilitate formal proving of the correctness of problem solving strategjes defined by this knowledge. The second of the above two aspects is r.onsidered in (1J while here· using chess end-games as an experimental problem domain· we concentrate on a quPstion of "advice programming": How t o implement chess heuristics using the mechanisms of AL1? AL1 as a language for describing strategies is an assertional language· as opposed to procedural languages. Characteristic principles and mechanisms employed in Ali are:

• the division of problem domain into s·.Jbdomains <separate "advice tables" handle separate subdomains>l
• production rulesi
• goals· subgoals <goals to be achieved· or maintained· as prescribed by a "piece-of-advice")i
• ~ onstraints on operators application ( "move-constraints" to eliminate meaningless moves from consideration in advance).

The approach used in our experiments is based on the use of benchmark problems and their solutions for the development of an AL1-like representatibn of appropriat~ heuristics. The use of an example problem typically results in the specification of advice· sufficient to solve the problem. The specification of such advice should be mainly based on the concepts already knowni new concepts are to be introduced only if practically necessary.

2. TREE-SEARCH ENGINEERING IN Alt: AN EXAMPLE

In this section we illustrate the spirit of "advice programming" by an example problem. i.e. a king-knight- king-rook chess position· together with its solution. As shown by Kopec and Niblett (5J correct play in the KNKR ending is much harder than commonly believed even by chess master's standards. The weaker side· i.e. the knight's side· has to fight for getting· or keeping, its pieces together in order to prevent the opponent's fundamental long-term threat which is: force the king and the knight to separate further and· when the knight is definitely cut-off from its king· attack the knight with both pieces and capture it.

Fig. 1 is a good example of what can happen. The natural move is Ke3 as it brings the Black king towards the knight and centralizes the king. But Kg3 is surprisingly the only move that saves the position. The tree in Fig. 1 illustrates a refutation strategy for Ke3. The depth of this refutation-tree is 20 ply· i.e. the depth at which the knight gets captured. How can we formulate advice in AL1 so that we avoid the 20 ply deep search which is prohibitive.

Two basic mechanisms control the starch in ALt: better-goals and holding-goals· both being predicates on board positions. The result of game-tree search in Ali is a "forcing-tree" <a concept introduced by Huberman (4J) which represents a detailed strategy for the achievement of better-goals while preserving holding-goals. More precisely: a forcing-tree is a subtree of the game-tree rooted in a current board position. All nodes of the forcing-tree· except the root node· satisfy a given holding-goall all terminal nodes satisfy a given better-goal· and no other . node satisfies the better-goal. For each nonterminal "them"-to-move node a forcing-tree contains all legal successor positionsi for each nonterminal "us"-to-move node a forcing-tree contains exactly one successor position. Thus the concept of forcing-tree corresponds to the concept of solution-tree in AND/OR trees !:e.g. 7J ·

The following simple concepts suffice to construct an advic~ which comparatively efficiently solves the problem of Fig. 1:

• our piece attacked <"our" is the weaker side's>i

- "knight-safety" which will be for the

present purpose defined as:

N-safety = distance between

their king and knight minus

distance between our king and knight

<distance is measured in king-moves)l

- N-losl-2p: we to move cannot prevent the

loss of the knight in the next two pliesl

- N-mobility: the number of safe squares

attainable by the knight in one move!

- N-in-corner: the knight in a corner of the

board.

A piece-of-advice that solves our problem of Fig. 1 can be stated as follows: Consider the legal moves in the current position in order of decreasing N-safety. Play the first one of those moves which guarantees that for the next 6 plies: <1> we do not gel mated·

• and· unless we can capture their rook·
• we do not lose the knight·
• after the first us-move· N-safety may deteriorate with respect to the current position only if it can be restored on the next move·
• the knight is never placed in a corner of the board.

For the sake of the search efficiency we add a better-goal which prescribes the investigation of "dangerous" opponent's moves only: attacking and knight­ constraining moves.

The translation of such a piece-of-advice i nto AL ·l is straightforward. In an actual implementation· the advice considered above was slightly generalized i n order to broaden its applicability.

An advice program for the KNKR ending C2J was developed along the above illustrated li nes . The program contains 16 p i eces-of-advice which are different comb i nations of the concepts· considered in the previous example· or similar ones.

Experimental testing of the program C2J and i ts behavioral comparison with the human chess master convincingly indicate t hat the program and the human master perform comparably. In fact· the program's performance was slightly better than the master's in these tests. When applying a pi e ce-of-advice· the program never s earched deeper than 6 ply· and typically ex amined a few hundred of nodes· up to about one thousand. The effective branching factor was thus between 2 and 3.

3. CONCLUDING REMARKS

Of interest are the following observations! (1) Advice· constructtd for solving s ome particular example problem· was usually applicable to many other problems i f only some effort was made to state the concepts used in the advice in a general f orm. An example is in Fig. 2.

• <2> Experience obtained in these experments indicates that, when constructing such knowledge based pr ograms· it is very important to ketp t he structure of the knowledge neat. This al s o facilitates formal correctness proofs for strategies· as investigated in CtJ .

( 3) Example of Fig. 1 shows how an au t omatic facility for learning from examples could be added to the AL1 systtm in a straightforward manner. In this con text· the task of learning from an ex ample can be viewed as ont of searching for a compact s~ecification which e xt racts a proper forcing-tree from the g ame - t r ee. This facility has not been programmed! however· part of the KNKR adv i ce program was efficiently cons tructed by carrying out this process manually C3J.

Fig. 2: A position that can occur from the one in Fig. 1· Black to movt. The natural 1 ··· Kg4 fails to 2 Reb Ne8 3 Re6 Nc7 4 Re7 Na8 Cor Na6) 5 Rb7 and the knight is stalemated and lost in a few moves. The same advice as for the position in Fig. 1 finds here the only· study-like defence: 1 .·. Kh4! ·

ACKNOWLEDGEMENT

The author would like to thank professor D.Michie for his continous efforts in Advice Language research.