On the Structure Of An Important Class Of Exhaustive Problems And On Ways Of Search Reduction For Them

Introduction

In most problems of artificial inte­ llegence an exhaustive search is an im­ portant (we think, main) method of choos­ ing a solution among certain alternatives. The central problem, which arrises here is the problem of search reduction without prejudice to the quality of solution. A search reduction is called absolute if the search graph is certainely lessened, and it is called heuristic if reduction of the search graph depends on the good luck. (We do not consider here search reduction techniques which may lead to the loss of solution, although they are sometimes also called heuristic). The subject of the theory of exhaustive search (considered as part of the artificial in­ telligence theory) should be, naturally, heuristic search reductions. In this con­ nection the following problems arrise: the problem of formalisation, the problem of inventing a search reduction method, (heuristic by itself) the problem of ana­ lysis of a reduction method. A analysis consists apparently of the following parts: an applicability domain, unique­ ness results (under such and such condi­ tions no other method exists), results on optimal effect, examples of the absence In those problems restrictions were used to strengthen application of method and do lead to any innovation in it.

1. Notations, assumptions, definitions

We go over now to a formal descript­ ion of the problem and of the results. All trees to be met in the talk are fin­ ite, directed and have the unique root. If T is a tree, Vo =V.. ('T') denotes its root, V(T) (reap. E(T)) denotes the set of ver­ tices (resp. edges) of T, End T denotes the set of end vertices. For V{ V('T') 'T'(v) is the tree "having" at V , EN( V ) is the set of edges exitting from V , N(v) is the set of end vertices of e E EN(V). For y._,~~V(T),(\11,\'z] denotes the (directed) path from Vt. to V 1 · Suppose we are given a map i..: V(T) ...... [!} . Set V+-: i.-.L (+), V-: i.- 1 {-). Suppose further we are given a completely ordered set ]) such that for aey ])' ~ D , illf J)'t:.l) and sup b'E D are defined (e.g. D = IAu{+oc:a}u{-ooJ). For di,d..zeD we set -(-d. 1) = dJ. , and we assume that -dt ~ -cJ.. 2 is equivalent to di > J..a · The letter lf denotes always a evaluation function f : End T- D and r denotes a transition function F: E (T)x x J) --+ J) · 6 denotes the set of pairs (F, f) such that F is monotone non-dec­ reasing with its second argument and F(e xD ) = D, V'e~E~ For (F ,f)~~ the function lfF,I :V('r) ... D is defined inducti­ vely by 'PF.., (v") :: I tv) , V ~ EN]) 7' ;

'fr;,f ~V) = itv)~'D<Vt i.("' F(t;v;W'J, lff'.f(wl) Vf: V('r) -END 'r. A functions' family l_ c A is called too wide if the follo­ wing holdo. Suppose an algorithm A is given (with value-set D x D), which for airy v f V("r)and for airy subtree 7;. c: T and for aey (F, f) E!. computes sup and inf of 'fr- # (V) over all (F t , fi)E: ~ rt. 11'1 which coincide with (F, f) on T1. Our condition has a form

(gl) V (fi', /) E L. 'tf'T;c.T VvL) y,fV(T) with

E(Tv. n'7'1) = t& ,v;: ~Cvc. ~)for t.. ".i , for any ' choice of ~~E:[A('fl,F, I. v..f,H(7l , F.f. v.(J there exists (F;, ,1 1 ) E Z. such that ( ~ ./) /1' 1 "' =(1',/)j'Tl and 'f\.J 1 W.:)==d, If any interval [dl . dz.l , Gtt. t d.t is infinite, <9l ) may be replaced (as far as our aims are concerned) by a more weak assumption of absence in ~ of rela­ tions of the equality of inequality type: (92) V ( fi}) fL. v r.L c:.T V'vL, .. , v,., ~ V ('r) E(Tv.nTt)=-ft,V;.t[Vo,Vjl for c.~j for aey function p: '])'" ... D for 8lJ3 sign 0 taken from the set ~ = ~ for any d. f D there exists (F 1 , f 1 .) f: . I:. such that (F 1 ,f 1 ) /1'J. = = (F, f) /'T't andj('frl,+llvt), ,'fr;~,,h("'f,.,))¢ Li1 d An exhaustive search working on l c: fl a rule of walking around T. Explicitly: it is a computable :function 'if: IN x Z. - - V(T') B.lch that 'i(F})El , V n F:/N one has r.(nrt,f',!)f ¥ N(11(i-,f',/)) ~~ n A search reduction or cut-off of the search 1T is a computable function A. :Job~- i±i~ such that Vtlf:N , Vllt.l)l:1. V(~.IJf:~ such that (F 1 f 1 )/u 'Ji(i.,F,/):: ' ' Lin = ( f', /) IU, 7i(t..,f,/) . V (F2 · iz)f:l. such that (F".z,lt)/T'-7'ii(,,fi',/) = (Ft.ft. )} lr-'T'r.cn,Fi./) one has implication ~ (n ,J',I)=-1. =* Cf,., ,lltV..) = 'f,.-LpL (V..) · Given cut-off o one constructs the new search .rr, !1\' (also exhaustive) which walks around less vertices: if o (n fi' ')=-l then J'h ' J,. for all i;~n such that Ji(i.,fi,J)t?},.<n.f",l) we set T.'( t., 11}) = Ji ln , F'}) · Repetitions may be afterwards excluded.

2. Results on cl.-fe method

The ot-~ method is applied to the problem of computing 'fF.P (V 0 ) · This problem is solved by exhaustive search. Suppose we are given a tree T, a family ~ c.6 on which we are working, an exhaus­ tive search (a way of walking around T) 11 and an algorithm A with properties described above. To construct a cut-off called 04-fl method, we construct at first for (F, f)~L the set T{n)=V 7i(t. , F.I) t..$n Then we construct a system of Bounds f ' ~A ( T( n) , r;, l,v f j on functions of L. Then we construct the set V&& ( T(n), ~) equal to the union of trees T\ over those v f V(T) for which there exi.s~s Wf [V 0 ,W] such that F(liN,V] ,1'-<w,cr))~ ~ g-qw)(w) · At last we put Ye.!. tn, F", 1)=-! <::? ~ tn,F:/) ~Vas (T<n), 8) To construct an A one uses restrictions on functions from 2. and explicit com­ putations of 'fro, 1 in certain vertices. Theorem 1. If !.. is too wide then the only search reduction for an exhaustive search 5I working on T.. is .Pe.a 1T (in the sence that all other search reductions are wearser in the obvious sense).

This theorem in a slightly different form is contained already in [1] .

Without going into technicalities let us note another result which can be either deduced from Theorem 1 or proved independently. Under assumption that the number of edges in min and max-vertices is aproximately equal, the number of end vertices in the optimal search tree is not less than {""tENDTf' ·

Simple examples of restrictions on L : a) the sum of values of 'ff,/ (V) V ( F, /) t ~ over some fixed set of vertices (e.g. over vertices of the given level) is bounded by a given element; b) the problem of traveling salesman: v·= V(T) :l> = Rv{toa}u f-oo} a function c; V(f') .... ]) (the transport fares) is given, c~oV)~o, such that !f(rv; w] , d. ) = d + q W) Then restriction follows from the evident

relations

f:"([Vo ,VJ ,If,.-,, lV)) : [_ ClW') + fF, f (V) ~ f. Clw) wt(lf0 ,1fj w~(Vo,V]

). Structures

Theorem 1 shows (as we have mentioned in the Introduction)that new methods of search reduction should be sought for families !, distinguished by nontrivial relations.

As an model which (in a reasonable approach) includes all non-trivial rest­ rictions known to us we propose the fvllowing schema: Let 14 be a set, possibly endowed with a structure of pl. rtially ordered set or some other suitable struc­ ture. Suppose that a map (structure map) tS' : E(T) _., M is given. Requiring of F and f a "good" behaviour with respect to 6 and structure on 14, we shall get a non-trivial restrictions on I. . A tra­ velling salesman problem is an example. We came now to a detailed description of an example of conditions on 5 8.llli of ways of its application to search reduc­ tion.

These conditions have naturally arrisen in aDalysis of exhaustion of var­ iants in a chess programm ( c.l. [ 1] ) · For chess 6(e), e E- E(T) , is a move from initial position of edge to its final position, considereq on the empty board and containing a indication of which piece was captured; M is the set of all moves on an empty board with capture in­

dications.

One has in this case /V (T) / ~ 10 100 I M/ (./olf · 6' and M are analogously def­ ined for checkers and card plays with

cards being open. +

- Suppose that V and V are interlaced in V(T), i.e. L(W)·-LlV) for wf:: N(v) · Suppose further that M = M+ u ,.- and that for WH./~) one has tS'(lY, 'NJ)EM+~i.tV)=+ · Let us write i.(m):+ for m~M~and ~(tn\=­ otherwise. The set of non-empty paths [v,w7 V,'W~V(7') is denoted Paths T. Seq M denotes the set of ordered sequences of elements from M (possibly with repetitions) whose signs alternate. Seg M is endowed with the natural structure of a tree and we shall consider Seq M with this struc­ ture. Then 5 induces the map 6 : Paths T -Seq M or, the same, the map '6: T­ Seq M. Suppose that 5 -.1 is unambiguous on edges e E EN (v), \1 VE V('r) (i.e. e cz.' f: f fo,/(t.r) <He} = 6( e· > ~ e = e · ) ·

Then for v~ V(T'), s~Seq M one denotes by V+ s the unique vertex w~ V(Ty) such that 6(L:v;wl)=s(if, of course, ~ E: 6 (Paths 'T'v ) ) · Let us introduce on Seq M

operation + by: m :. ms. +- ml. if m is obta­

ined by writing down rnz. after m!and if fmtf is even. We shall write also m=m,.·mz. if mi.=mlL+ .. m1.:. m :m 1 t +m m · ;[. m· f J,. J U't ' &. ~ ,., if in the latter sum all lengths, 'except poss ibly last, are even.

4. Relation of influence

Suppose that on the tree Seq M a rela­ tion of influence fs given and that a relation of influence of elements from Seq M on elements of M is given. Suppose that relation of influence satisfies the following conditions (where m m ' ~ M ,.. I <' ,...., ) ' ;> , S , ~i... S ~ Seq M :

Axiom of symmetry of influence:

• s influences .s'..:> s' influences .s · Axioms of extension of influence:
• m ~ s and s' influences m ~ s' influen­
• mE S => 5 influences m ces s ·

Axioms of the transfer of influence:

• 5 influences s' and s=s1·s~:;.at least one s~ influences 5 1 ·
• 5 influences m and 5-= st. · .S.z. ::::» either some 5.,. influences m or .si. influences S.z. ·
• S influences S' and 5=-SL·Sz. :::> either some s" influences .s' or sJ. influen­ ces Sz.

This relation of influence is extended with the help of 6 to relation of influence in the Paths T and to influence of elements of Paths T on elements of M. For this extension some additional axioms

are ~o hold ~here v: ViT') ,w1 ,wl. .w5 ~ V(Tv)

6 [V,w 1 ]: G [v, W1]e G'[V,Wz] Axioms connecting admissibility of moves and influence: a) j mE M"lV) mt6(£N(wJ),i.:i ,2 mf- 6\ENvw?>)) ~ i.M ~ [v ,w,.1 influences [v,Wz.] b)'3m(:M mt ti(ENCY)) . m ~ o(EN(w.l) t. = 1 ,3 mt' 6 ( EN(w.t)) =nv.wJ.J influences either [v,WJ or m c) 3mE:M- i.tv)mt6 (£N(w's.)}, i-m;~'YeBeee rnto(EN(vo/\)) ~ [v,w,..l-t-m lnfluef)c.es [V,Wzl

5. Method of geometrical relations

Let T 1 be a subtree in Tv. vE: V(T 1 ). Suppose that we are given an algorithm B (for games B is the choice of the best move) which constructs for anyvE V(T) and an:! subtree T 1 c T a vertex Wf: N(V ) such that 'P~<f""-(v) =fikv;wl,'fr.,I.'Tl(w)). (Subscript T 1 in ~ denotes that computation of this ~ involves edges and vertices only from '7l ) · Let us define for T 1 two subtrees 8 f(?l), S .. (T 1 ) is defined inductively beg­ inning from the root by conditions: vt V(S\7i)J; 'iuf: y'M(S""('Jl)) [N(Lt,S+('Tr)): = "'f8(u. . ?I)f];Vu~ V-'"'ts(T~))[tJ(u , S""~)) : =N(u.. ,'7D]

Analogically s- (~) is defined induc­ tively by conditions: v~ V(S - ('1'1 )) Vu.tvtcv>(~) [N (u,&-tT 1 )f..: /V(u..~)J \lu.EV-i.tV)(~) [N (u..S-(7;_)) : :if>(u,'r.,)j] If~ cTv. ?;,cT...,,"WEV"M(T} we set &CT1 , '71)-= c (& -<T.t.))n 6 (&·(r"' ))E Se<f, H If T 1 , T 2 are subtrees in T, P f: Paths T, mE: M , we say that T 1 influences m (r_esp. P ) if there exists P 1 E' Paths S (7't.) such that fl influences ;n (reap. P ). We say that T 1 i~luences T 2 if there exist P._ E: Paths b ('r;) ~=i,2 such that P1 influences P. l

Let us now distinguish some special subtrees. Set O(w,v)str(EN(w))\.6(EN(V) ,

L ( ~'-" = {mE 6 ( EN(~): [V:wi influences mj . w~ Tv- · Subtree TL c '1'v is called testing if o(EN(W,~)h ~ 0(-w,v)vl..(w,V) for WE yt.CVI (7's.) and EN(W , 7't)=EN(~ for W(o v-i.IV)('T's.) .l!'urther, subtree 'T'z. c'rw, wt yt.tVJ (Tv) is called parallel to T.~. c 7'11 if N(u, ~)= = N(u..) for u" v-t.(W)('!I) and N(u. T )::: =~-l(_D(u . w)uN(V'+ tr(C.w. u.]).~) 1 3 for u~ vqw) (Tz) · Suppose now that we are given a function at. :M _.1Ru1 .. oo1ut-..o~

Suppose that r: (e d.)= d.. , Ve ~ E (7') and put S(vo> = c 5 (¥): z.~~ 1 ae (C5'le)) I C!E L. ve,V Suppose that a condition of majoration holds: SLV) > %rw> ~ '~'I (V) > ., 1 (w) .!!:.G. for chess $(If) may be taken to be material balance).

'fheorem 2. Let T 1 c T,. , T 1 be testing subtree, WtVi(V'l('T',.) · If T 1 does not in­ flueDCe [V'.W/, 5 lW) ~ 5tv) and v~ V18 l~) then wtVM(7'~) for subtree ~c"rw which

is parallel to T 1 .

This theorem menas, in terms of search, that if at t;he completion of search over T 1 we have entablished that T 1 c\'&&(.,) then, in conditions of Theorem 2 the search over T 2 is superfluous and

T 2 can be cut-off.

Let us describe one more result using notions introduced above. Let ~ be a fixed search computing If t:.l (V0 ) · Let J;(n,fi}) .; u, I.;A(1'(n,F./),u)", et £N(u.) Let us assume, to fix setting, that IAtV+. Put l<o =¢. T. = T, , G 0 =EN(u). Def'in/~ch t E G .. -l inductivily (for I = 1, 2, · · · ) subtree 'r..e c Tu and a set K<.· (u . e) in the following m:~.nner: L( t Vt'r.:,e) ,EN(u,\o~.)=- = e ,Vvt:V-(7\,1 ) [EN(v, T. ,e.) = =EN (vt l"VtV-.(7\ ,e )-u [e'EEAI(r.r,T, ,e)¢> ¢:? ( 6' {e') t 6' ( l<,_l t u .e >)n ( 6'(e ') i 6' (EN (u..)) n n(i(!iA,vl)influences CS(e'))J ;

G.; ={e '._Gi.- 1 : 'fF6r , (u.)f8) ,r, ... ~ k; (I.(, e) =[e'E G, :~ .e· influences T; .e y · Set at last Te ; lim -r:.e ; (7 = &m �~

'fheorem 3. Let G' c G- and r,· be a search over subtree Tv c 'ru such that ~(1/,li, /)n�'=~. Suppose ;([u.vJ) and 'T'r, do not influence ~ , V€ E &' · If' ¥'w·(\T) $ & then Y'r.· (V) $.& Where r.·· is a search such that

Er.N ('nr· 11 Tr.·) 'Er.· (7'r.·nTr,·) c Gr'

The following method of search reduction is based on Theorem 3. Determine for a vertex lA E V (1') subset G. Edges ef G will not be taken into search while the current path from u does not influence

T,.

Besides in the moment of return in a vertex one should check whether ?r,· in­ fluences Te or not. If it influences one should include e into search. In the contrary case Theorem 3 permits one to consider the search from the vertex under

condideration as finished. It should be noted that different edges are rejected independently.