Some Theoretical Results Concerning Automated Game-Playing

1. Introduction.

When computers have been used to play games such as chess, checkers etc., explicit use of evaluation functions (mdBt frequently linear in form) has usually been made. They have also featured in the solution of non-game problems 1 · In other cases a decision rule for playing games (and solving problems) has been used, but it is shown in § 3 how decision rules are in many cases, equivalent to the use of suitable EF's (from now on the abbreviation EF will be used for evaluation function). EF s have been used in many circumstances and in vary­ ing ways and lie at the heart of programming machines to play games and solve problems, and their importance was stressed as early as 1950 by Shannon 2 · However, on the whole they have been introduced for specific applications and their meaning and properties neglected other than that a position or state with a higher value is likely to be a better one.

It is the purpose of this paper to introduce a formal framework inlflich a general study of EF's can be made. The full length version of this paper 3 shows how this framework can be used when studying existing techniques and how it is potentially useful for intro­ ducing new techniques. In this paper the basic concepts of EF's are presented and then a single application is chosen for further consideration, namely the study of when a players actual play can be represented by an EF. The main results are given in Theorems 3.1.3,

3.1.4 and 3.2.2.

2. Basic Properties of Evaluation Functions.

A game usually consists of a set of definite states together with transitions between them. Consequently it is natural to represent a game by means of a directed grapht (X, fl) whose vertices correspond to the states or positions and whose arcs correspond to the possible transitions or moves. However, it may be of importance to consider the development of a game (or the nature of the solution path in problem-solving) in which case the more usual formulation in terms of a (rooted) tree (V, T) is likely to be advantageous. (V, T) can be obtained from (X, f1) by starting at the root (the start position) andtgrowing' the tree according to the successor mapping except that a vertex is never identified with a previously considered one. (X, r> will be used when the discussion concerns graphs (and For game graphs (X, r) satisfying X t1 (\ x- :::0 ¢. "'}.'* can be extended as follows:

t For graph-theoretic concepts see Bergelt-.

~ formed in this will be called the m1n1max extension of A and will be denoted by A':..,.. In the case of game trees the above procedure is just the familiar minimax rule. However, with the above formulation, it is easily seen that the minimax extension can be formed for any game graph satisfying X 11 n x"'= ¢>. (Boffey' gives a fuller discussion of the class of graphs over which the minimax rule is applicable).

From now on it will satisfy the condition stated. be assumed that all graphs XMI\ X...,=p unless otherwise

Although, in principle, such backing-up can always be performed over a game graph this is not, in general, practically feasible. For example Good'1 estimates that there are about 10# possible chess positions and so the associated game graph will have to·& vertices. In such cases estimates of the values of positions encountered may be considered. These lead, in principle, to a function f: X -+R (where R is the set of real numbers) such that f in some sense

approximates 'Jt ........

Definition .2.1.2. An evaluation function (abbreviated EF) over a game graph (X, r ) is a single valued

function f : X -+ R.

If f(x) > f(y) then x is said to be better than y (under f).

The merits of a particular EF will depend upon the way it is to be used. If it is suspected that the EF is a good approximation to A. ':a. (in a sense to be 1111de more precise below) and the opponent is a 'minimax like' player then it is natural to use the strategy}.,. where

Definition 2.1.3. ~. is that strategy which leads to a move xy* being made from position x where

Ties for y* are broken by some subsidiary rule.

Definition 2.1.4. EF's f and g are locally equivalent if

where x,ye.rw for some w~X. f is locally perfect if it is locally equivalent to 'A'!,. ....

Theorem 2.1. 2. Using strategy Ao locally equivalent EF's lead to the same play, provided the same subsid­ iary rule is used to split ties. A locally perfect EF leads to optimal (minimax) play.

2,2. Probabilistic evaluation functions.

The above discussion is relevant to the situation in which a player always chooses the same move from a given position. However, in practice this will generally not be the case, a player's move depending partly on his assessment of his opponents ability and temperament, partly on his frame of mind at the time of the game and partly on other factors such as a draw in the last round of a tournament being sufficient to secure first place. A player will also vary his play simply for the sake of variety. Although the definition of a game could be extended to incorporate 'environ­ mental' factors this will not be attempted here. Instead a model is chosen which will allow players to use variable strategies with the actual choices of moves being governed by probability distributions. Such a model provides a generalization of the usual concept of automated game-playing and will be discussed further in S3,2.

It is now appropriate to relax the constraint that each position should have a single value associated with it, and to replace this by the condition that each position has a probability distribution attached to it.

Definition 2.2.1. A probabilistic evaluation function (PEF) over a game graph (X, r) is a bounded function p: X x R -+R, with pcx,.,.)?O,

and p(x, r) = 0 outside some finite range r 1 ( x) ~ r ~ r~ ( x).

p(x, r)dr can be interpreted as the probability that the value of x, now denoted by v(x),, lies in the range r ~ v(x), ~ r + dr. When required v(x)r is obtained by selecting, at random, a number from the distribution p(x, ), Now just as for EF's, a PEF is meaningless unless a strategy for its use is specified. We shall only consider strategy A:, the analogue of v& ··

Definition 2 · .2.2. A: is that strategy which leads to a move xy* being made from position x where

Notice how the successor position ~: can vary from game to game due to the v(y)p are stochastic variables. y* selected by the fact that

§ 3.2 is devoted to a study of how to represent actual play. PEF's can be used

3. Decision Rules.

Game graphs are usually very large and game trees tend to be even larger. It is therefore (as noted in .§2) not in general feasible to consider the whole of (X, f1) in order to derive values of ~~,.. Consider for example the case where (X, r) is a tree with a constant branching factor b and constant depth D (ie. every path from the root of the tree to a leaf contains D arcs), Then the final set F will contain lP elements and more than bi> vertices will have to be considered in order to obtain ~,.(S). On the other hand a dec is ion rule, which can be applied at any vertex, need only be applied D times during the course of a single game. Thus for a single game the ratio of the amounts of computation required by the two approaches is less than k X D : tJ> where k is a measure of the effort involved in a single application of the decision rule, It follows that the decision rule requires much less computational effort to apply if k is not too large.

Sometimes a decision rule may be implicit, as is the case for example when one is observing the play of a master (whether directly or from written records) with a view to improving ones own play. In this situation it is relevant to pose the following question:- how can the underlying decision rule as exemplified by the masters observed choices of moves be characterized, and under what circumstances can such a decision rule be represented by an EF (with strategy .AD)· Although the masters play is likely to be observed over only a small subset of all possible positions, the more constrained problem of es tahl isiting the existence of an EF tn represent a decision rule over the whole of (X, r) will he tackled.

:L1. Representing the dec;ision rule of a constant player.

A master wlll in general not always play the same move fror~ a given positinn (for example a chess player who l.ikes to open p-K4 is likely to vary his play l>y sometimes opening P~~4 or P~~B4 etc.). Such play wlll l>e termed variable play and is treated in § 3. 2. In this section it will he assuJnect that at a given positloa a player will always mal<e the same move.

Definittnn 3.1.1. A (constant) <lecis .ion ~or preference fuuct ion for !.!A-'{ .is a single valued function CT"n: X -X with <JM (x)€ f'x. x - <T"n (x) is MAX's preferrect move fro1~ x .

A preference function a;:, for M1N can he defined in an ana logou .. <; way.

Definition 3.1.2. [f a;; and <lin ~tre preference func tions for MAX and MIN res;>eet iva ly then cr = <an · o-..,) is terrred a (coastaat) preference nair on (X, r ).

Definition 3.1 .3. [f u,vEi X and c:r is R preference pair oa (X, r ) , then u ~ v i! a ad only if there ox is ts an olelTIP.nt t E: X such tllRt

Definition 3.1.4. An EF f over (X, r) reproduces a preference pair cr (with respect to strategy OJ 0 ) if

If u ~ v thea u may be said to he directly nreferre<l to v. However for constant play and repres­ entation of a preference pair by an EF it is necessary to consider indirect prefereaees and this motivates the following definition.

Defiait ion :1.1. 5. If pair on (X, r) then u,v 1: X >; and t:r is a preference v if and only if there w 0 , w 1 , · . ·. , W:s = v such that u is a Sefll.lOJlOO 11

A preference pair induces an ordering on the set X. Howe ·~er, since not all pRirs of vortices will he co1npared it is found that it i3 sufficient for the orderin~ to he r>artial as is shown hy the following two theorems .

Theorem :1.1 .1. caven a partial nrtler relation Q over a finite set Y then there exists a manping "f: Y - H suc h thn t

Theorem :1.1.2. There exists an m' f.,.. over (x,r> which renroduces the preference n."lir a'" if and only .if ;:.; is a partial order relation on X. (u '?>; v is equivalentto (utv or u=v)).

Proof. The necessity is clear.

The sufficiency follows from Theorem 3.1.1. hy taking Q to he the relation ;:.; and f.,. to he the function y.

Corollary. If <r is a preference pa ir over a tree (V, T) then there always ex .is ts an EF fa- which re produ.:es o-.

proof. For a tree the relation ?>; reduces to ;:..,.. and is always a partial order relation.

The above result is appropriate to the case in which the strategy .)., is being used. However, s tra teg ies involving lookahead are frequently used and so we turn to the problem of finding an EF f"" so that f",iT reproduces the preference pair cr .

Theorem :~.1 . 3. If cr is a preference (V, T) then there exists an EF 1'"' that 1;: reproduces <r for each d pair over a tree over (V, T) such > 0.

proof. Two functions

associated with cr are defined by

?r is now defined l>y

and clearly reproduces cr. " In order to prove that f.,. has the des ired properties we first show that for all xE V,

where s = 0 if x CO V 11 and proof will be given, in wh ich hypothesis that the equations when k = r. if x f:V ..... An inductive H.,. denotes the (A) above are true

It will now X & V"', then be shown that implies H .. ~, ·· If

and similar reasoning shows that f'~ ... ,(x) = f""(x) if x € v"'. By using similar arguments it is also readily shown that f';....,(x) = f'cr(x) + (-1 )s and hence H"t"+l follows if H.,.. is true. 1t is concluded that H.,.. is true for all r > o.

f"" reproduces <:r and hence f'':i must also reprod­ uce a- if d is even. If d is odd ?:;: and 1r differ by a constant over v"" and by a different constant over v"' and so f'l reproduces er since f"" does. The fact that ?4 and f.,. difier hy dif f erent constants over v" and V"' is immaterial since an element of v 11 is never compared with an element of v,...

1t has thus been established that there exists an EF 1"4"over (V,T) such that ?; reproduces cr for all d :::_ 0.

For a game graph (X, r> the situation is more comnlex since the condition that ~· be a partial order relation is no longer sufficient and 'higher order consistency relations' are required. However, if

T For any EF g, g<l will denote the d-th derived EF. (that is the EF obtained by hacking-up, using the minimax rule, over a lookahead tree of depth d).

the definition (~') given in tim proof of Theorem 3.1 .3 results in ?.,. being definect urmmhiguously over X then ?~ renroctuces <r' over (X, I"').

Suppose <f" is a preference pair on a graph (X, r' ) and let )'t'" ;>C a 'X'\ th from vertex x to vertex y and c,r be (the number of arcs of 7t" corresponding to preferrect ''"w"s for }141\;( J,tin'l-'' the nu1nber of arcs of"'}(' corres,ond iag to nreferr"rl ,,,ova.<; ;,y MIN) then a definition of consist.,ncy can be given as follows.

llefinitton :1.1 . .;. :tor any pair of <T is ~consistent if c~. = '?r, paths ll',~n- 1 with the same endpoints.

Theorem 3.1.4. Lf <r is a :tnlly consistent preference pair on (X, T') then there exists ail B~' f.,. over (X, r) such that t~ reproduces 0" for all d > O.

£roof. [linea <r is fully consistent it is that definition (F) of Theoretn :i.1.:l with V leads to an unambiguous ctefin.ition for rest of the nroof closely follows that of easily seen X replacing 1'.,. . The Theorem 3.1.3.

It may be notect that the conctit .ion that is esse .tt .ial fnr tlt.is proo:f. x"',..x"'::.p

:1.2 Henresenting the ctecis .ion rn.le of a variable player.

As d tscussect in § 2. 2 a player tends in practice to vary it is play, and so attention is now concentrated on studying :10w variable play can be simulated by the use of PIU''s. First, variable play needs to be formal­ ized and the following definition is presented.

Definition 3. 2.1. A (variable) preference function for MAX is a single ....,a lued function -c'n: X H x f' xi'l - I where I is the' unit intervn 1

and

-cJ.x, u) can he thout:ht of as the probability that, when in position x, MAX will choose to move to positio·l u. A variable preference f·mction T,. for MIN can be <lef .ined ia an analogous way.

ilef ini t ion :J. 2. ~. If T"' and "Cm are var iahle preference functions for MAX and M.m respectively then "t = (-c,.,"C.,.) is terlllP.d a (variable) preference nair on (X, f"' ).

Definition 3.2.:1. A pi>F p'C renroctuces a variable preference pa.ir -c if

where Jr(x, u) denotes tl1e probability that, using p", the move x ... u. will he selected.

'fheorem :1. 2.1. ~·or each preference pair "C on a tree (V, T) there exists a pE~' p~ which reproduces -c .

proof. Let xEVM and Tx = fu,, ....... , u,J. Then assumine the form of pY Cut, ), the distribution attache<! to u,, has i'Jeen decided unon it remains only to specify the means

such that

The )4; will be found hy us.iag an inductive process. Let 11 11 be the itypothes is ·chat )"; , i = 1 , .·. , s can be fow1ct such that

B4 is easily satisfied hy setting ?-J, j > k to be sufficiently small, and by using continuity arguments it is clear that H~ is true. It remains to be shown that H" implies Hk.r .

Let p 1 be chosen so that B1 is satisfied and let }'~= ~· The combination of the distributions p~(u,, ) and p~(u:&, ) is a new distribution, p* say, which satisfies the conditions of Definition 2.2.1, and so by Hk,)"J=rJ(,), i = 3, .... ,k+1 ean be chosen such that

Ilef ining

then, J> ('1) > 0 for sufficiently ?('?) < 0 for sufficiently large clearly a continuous function of ~ there exists a value '?*of '? such that is small '7 and p. Since !P is it follows that that y;>( r> 0,

?r(x, u 1 ) - ,r(x, u 1 ) and s inca the relations -c'l'1 (x, u 1 ) - "tM(x, u2.) (D) (C) are maintained throu~hout

From (D) and (E) it follows that

and this together with (C) establishes the truth of

u ...... It follows that H~ is true, all k > o.

A similar result holds for positions Y -c;.v"' and so there axis ts a pEF P" which reproduces -.;

Theorem 3. 2. 2. For eac h variable preference pair 't: over a tree (V, T) there exists 11 pEF '!\'" such that fll t reproduces -c for all d > 0.

~· The proof will proceed inductively. H.,.. is the hypothesis that there exists a PEF 'f;-c such that p~ reproctuces "t: for all 0 ~ d !:. m, then by Theorem 3.2.1. H 0 is true and it remains to proof that H 111 implies H111· 1 ·

Let rx = fu,' ..... ' u,], u .. = r"'·'ut and p be a PEF satisfying H..._ · Then, if the transformation

is applied, pi also satisfies H,.. p~ .. ,(z, r) differs from P,..,(z, r) for each u;., but for no other positions. The ~ can now be chosen (in a way similar to that used in the proof of Theorem 3. 2. I) so that

where 'JC 1 (x, ut) is the being selected when using nosit.i.ons x<.V.., follows result follows. probability of move x~~\ p 1 · A similar statement for by analogy, and hence the

In the above two theorems the restrictions placed upon the distributions attached to the vertices of the tree were weak, and in practice it would probably be reasonable to restrict oneself to the rectangular

t ~'ol denotes the d -th derived pEF of ~.

distrihntions

For g1w10 graphs (X, J"1) which are not trees the situation is much more complex. It is not even clear as to what constitutes a sufficient condition for the existence of a pgF which will roproctuco a preference pair though it seems that it is heavily dependent on the geometry of the graph.

4. Summary.

Evaluation functions and the more general probab­ ilistic evaluation funct.ions wore introduced in § 2. A single anplication of these concepts, to the renrese.ltution of decision rules, was then considered in detatl. It was found that, to a large extent , the use of an EF or pJo;F is equivalent to the use of a decisio>l rule.

Hefereaces.

1. Sandewall, B. J. (19159) A Planning problem Solver based on Lookahead in :aochas tic Game Trees, J. ACM 1..2, 364..;~2.
2. Shaanon, C. (1950) pro1~ramrning a Computer for Playing Chess, Phil. Mag. ? -tli :>er. ;!!_, 256-75.
3. BofJey, T. B. Evaluation Functions - to be suh1nitte<1 shortly.
4. Berge, C. (1962) The Theory of Graphs, Methuen.
5. von Ne111nann, J. ell MorgenHtern, 0. (1947) Theory of Games and gconomic Heluw iour, princeton Univ. press.
6. (G) lloffoy, T. H. (197:1) Applying the Minimax Hula over Graphs which are not Trees -unpublished.
7. Good, I. J. (1967) A lo'ive-Yoar plan for Automatic Chess, Machine lntolligence !., gdinburgh University press.