Changes in Representation which Preserve Strategies in Games

CHANGES IN REPRESENTATION WHICH PRESERVE STRATEGIES IN GAMES

by

Ranan B. Banerji & George W, Ernst Professors, Engineering & Information Sciences Case Western Reserve University Cleveland, Ohio United States

ABSTRACT

One reason for changing the representation of a game is to make it similar to a previously solved one. As a definition of similarity, people have previously often proposed homomor­ phism-like structures, One such structure, the "s 0 -homomorphism", is defined and studied in this paper.

It is indicated t hat a useful winning stra­ tegy exists for any game in a general class called, "positional games", A set of sufficient conditions is derived which a game has to fulfill to have an s 0 -homomorphism with a positional game, The conditions are exemplified by applying it to a class of games shown by Newell to be representable as tic-tac-toe,

KEY WCRDS

Game -playing, problem-solving, strategies, ~omomorphisms , representation, artificial intel­ ligence,

1, Introd~ctio~

It has been known for some time that the ease with wr~ch a problem can be solved is t:ea·1ily dependent on the manner in which the problem is stated, To enable a serious study of this phenomenon, (which we shall call represen­ tation dependence), it is necessary to have a well-defined model of what a problem is, Three such models are available in the literature, Green[6], Amarel [1] and Ernst and Newell [5] . The latter two have been used to study repre­ sentation dependence , In the third one any problem i s considered to be that of proving a statement in a first order predicate calculus, It is our belief that the study of representation dependence is possible in this model also in terms of what is known as the extension of t~eories by definition (1 0 ).

Any of these existing models can thus be used for the study of representation dependence, Indeed, some day we may be able to consider the rela t ionship between the three models in terms of such a study. Meanwhile, studies on repre­ sentation dependence will have to continue separately along these three different avenues, This paper will use a formal variant of the "s tate space" model of GPS [5] and study certain issues of representation dependence,

The reason for changing the represent ation of a problem is not always to make the problem

"simpler" (although in the examples of Amarel [1) the problem space is shrunk). In many cases changing the representation of a problem in­ creases its search space, and yet makes the problem easier by allowing previously learned problem solving methods to be used in the problem. Polya [9] argues as follows: \olhep a person is given a problem if he notices sufficient similarities between the given pro­ blem and a problem which he knows how to solve, then he can solve the given problem in the same way that he solved the known problem, Iu gen­ eral, the two problems will have different abstract structures (in our case different state spaces), but they are sufficiently similar that the same strategies, heuris tics, etc., can be used on both.

As a definition of this similarity we pro­ pose different kinds of homomorphism-like relationships between two problems which pre­ serves certain strategies, heuristics, etc., for solving the problems. For instance, Amarel [1) has suggested that what is a single transfor­ mation in one problem may correspond t o a sequence of transformations in another problem. Other kinds of homomorphi sms have also been described in the literature. For example, there is a .... ell known similarity between the strategies for playing the games of s t aircase nim and nim, This similarity is a rather unusual homomor­ phism between the two games, This led some to develop general me thods to determine if a given game is homomorphic to nim, The resulting methods led to the discovery of a homomorphism between the eight pawns game and nim (and several other homomorphisms [2 ,JJ ) ,

Encouraged by these results, we decided to study the conditions under which a game could have a tic-tac-toe-like game as a homomorphi c image. Previous to this investigation, a gen­ eralized class of games, called posi tional games, had been s tudied by Koffman [7l, This class included such games as Go-Moku, Hex, Bridgit and t wo and three dimensional tic-tao­ toe, Koffman developed a game-independent learning technique which was effective f or any positional game, The development of methods for recognizing homomorphisms with positional games would enable wider application of Koffman's method for playing these games,

Another reason for studying homomorphisms with positional games is t o try to answer some of the questions raised by Simon [11 ] and by Newell [8). They claimed that the four games in Fig. 1 (one of which is tic-tac-toe) are "isomorphic" to one another in scme very non­ obvious ways. We found that a few of these games were not even obviously positional, although most of them were, Therefore, we felt that a deeper analysis of game structures was needed before homomorphisms with positional games could be studied,

During our inve stigati on, it also became evident that the homomorphisms one should be looking for are certainly not one-one maps or not e\·en maps. In fact, they turned out to be general rel ations between the game spaces under consideration. Moreover, we found that whether two games were homomorphic or not depended heavily on the starting position of the game. In the interest of axiomatic simplicity, the stat e space of a formalized game, often has many more s t ates than one needs for the purpose at hand. These illegal stat es often de not get mapped properly by homomorphisms. By restric­ ting one·s discussions only to states reached frou. a legal initial state, one can avoid this difficulty.

A f ormal definition of a game is given and discussed in the next section. Then we intro­ duce the homomorphism that will form the central theorem of the paper. Next, the idea of a wirJUng strategy is introduced, and it is shown tha t if a homomorphism exists between two games, t hen one can ccnstruct a winning strategy in one from a winning strategy in the other. In section 3 po ~itional games are discussed. A set of sufficient condi tions are developed f or a game to have a positional game as a homomorphic image.

In all of these sections, examples are given for all formal definitions f or motivation. Tte l ast sec t i on ccntains some concluding re­ marks.

2. A Homomorphism Between Games

In this section we define a homomorphism between games whi ch, in sor:e sense, preserves winr~ng strategies. However, first we mus t define games; this is the purpose of the firs t ~ubsec tion . Kext, the homomorphism is described and in the last subsection we prove that it preserves winning strategies.

2.1 Definition of a Game

A game G is a 5-tuple, (S , R, P, W, L). S is the set of game situa t i ons. R is the legal move relat i on . That is, sRt if and only if t is the result of making a legal move in the game situation s. P is the set of game situa­ tions in which the first player is on move. (We are assuming that the game is a two person game.) W is the set of winning positions and L is the set of losses.

We assume that any game satisfies the fol­ lowing set of postulates:

G1: Dom(R)(l(WUL) = r)

G2: L C P

G3: W(IP = ¢

GL.: sRt - ( s c P · t · P )

G1 indicates that there are no legal moves from a winning or losing position. G2 requires the first player to be on move when he loses; G3 requires the second player to te on move when the first pl ayer wins. Ncte that S-P is the set of situations in which the second player is on move. G4 indicates that there is strict alternation between pl ayers. Although these postu­ lates rul e out certain garr.es, they are satisfie: by the games described in this paper and many other games, also.

Race (see Fig. 1) fi ts this definition of a game quite nicely. Each game si tuation con­ sist s of three parts: the board; who is on move; and which tickets are unbought. P is the set of situations in which the firs t player is on move. R is the legal move relation . Each situation in W has one of the first player 's horses on the third rank; a situation in L has one of the second player's horses on the third rank.

The reader will note that it is not possitle to have a horse of both players on the third rank. Although such positions are elements of S (see discussions in Sec. 3), they can never be obtained due to G1. That is, after the first player moves a horse t o the third rank, he leaves the second player with a situation in whi ch there are no legal moves; thus, the seoon= player never has the oppor t.uni ty tc subsequently move one of his horses to the third rank also .

2.2 Definition of s 0 -morphism

Given two games G and G·, a s 0 -morphisrr., h, is a homomorphi srr.form game, G = ( S, ?., F, '.1, L \ to game G· = (S· , R·, P·, W·, L' ) . \J;.L.ke most homomorphisms, it is net a map b;t a rela:ion between Sand S·. In other wor ds, a sit·Jaticn in S may have several images in S·; h is only concerned with those situat ions in S that can te reached by applying a sequence of legal mo·1es to some s t arting si tua tion , s 0 · We define : t o be the set of situations that are reachable frorr. s 0 ; i.e., T~= ~(s0 ), wher~~ is the transitive closure of R (R = IURUR" UR3 ··· ) .

An s 0 -morphism, h, is a subse t of SxS· that satisfies the foll owing pos t ulates:

H1: scT&s·ch(s)&s·R·t·-3t(t · c h(t)& sR: )

H2: scT&sRt&s· ch( s ) -lt· (t 1 c h(t)&s ·R·t · )

H3: scT&s 1 ch(s)-(scW·s·cW· ) &(scL;;s· cL ')

H4: scT&s 1 ch(s)-(scP!!s 1 cP')

According tc H2, whenever there is an arc from s to t in G, there must also be an arc from every image of s to some image oft in G·. H1 is similar t c H2 except the roles of G and G· are reversed. H3 requires every image of a win (loss) to be a win (loss ); conversely every reachable situation that has an image which is a win (loss), must be a win ( loss ) . H4 requires the same player to be on move in a situaticn and its image.

An example will help clarify the properties of a s 9 -morphism. Race is s 0 -morphic to t i c- tee­ toe. \See Fig. 1.) Each tic-tac-toe square, i, corresponds to the ticket Mi w!"lere the t ic-tac-toe squares are assigned the fol l owing numbers:

2 9 4

7 5 3

6 1 8

h tic-tac-toc situation is an image of a race si:t.:ation when

1. each unbought ticket is an unmarked square and conversely;
2. ii, a tic~tac-toe square marked by a player corresponds to the ticket bought by a player owning a horse on the ticket,

Fig. 2 shows a race position and several of its tic-tac-toe images, The s 0 -morphism requires sqc;ares 7 and 3 to be unmarked; square 5 to be rr.arked with 0; and squares 2 and 6 to be marked X, For this race position, it is easy to see t~at all of the properties of an s -morphism are satisfied, In either of the tic-t~c-toe posi­ tions in Fig. 2, the second player may mark square 7 cr 3 wit~ an X, while the corresponding move cf bt.:ying ticket M7 and M3 is legal in the race si :c;aticn in Fig, 2, Thus, ~1 is satisfied, H2 i~ satisfied beca;.;se t".e second player buying a ucket ccrrespcnds to marking one cf the empty squares in the tic-tac-toe pcsiticns.

: c see that n3 is satisfied, note that each hcrse is affected by precisely three tickets ·hose correspondir.g squares consti t::te a winning line in tic-tac-tce. Thus, in order for a player tc '"i:1 at race , ::e rr.ust r.a·1e bought one of t!'lese sets cf :hree tickets. Fe r example, if the first player succeeds in moving horse d to the gcal rank, it follo~s that he has bought tickets, M2, 1-:7 and !16. Any image of such a win must have X's on sq::ares 2, 7 and 6 which is a win in tic-tac­ tce , h similar argument shows that the losses cf race ha·te images that are losses in tic-tac­ toe.

C':;·Jiot.:sly, :ii. is satisfie.:J because play is strictly alternating in both games.

2.3 ~efiniti on of a Scrategy

Given a game, G, a strategy, Q, is a partial rr.ap on P with S as its range with the proviso that ~(s) = t implies sRt. That is, given a playe::-' s mo·:e, the strategy determines the next situation for the player to go to.

Given a strategy, ~. and a situation s cP r.. , 1 ' a ·..:-sequence fc::- s1 is a sequence, s1, s 2 , ... , of situati:ns such that for all i, siRsi~: Moreover, for all odd i, si .,.1 = Q(si), and if sn is t:1e l ast element of the sequence, (i.e., the sequence is finite), then sn 4 dom(R). Intui­ ti7ely, each of the first player's moves in the sequence is dictated ty the strategy, Q, while the seccnd player's moves are arbitrary legal mo· ... es,

h . Q-sequence for s1 is called winning if for some finite n, sncw. It is easy to see that in such cases n is even,

A strategy is a winning strategy for s if every Q sequence for s is a wi~~ing sequence, It can. be . sho\./Tl ·o~ithout any difficulty that, if Q is a w~nn~ng strategy for a situation s, then it is a w~nn~ng strategy for any situat ion s. c F which occurs in a Q-sequence for s. Using tfie above defir~cions we ca~ now prove:

Theorem 1. If there is an s 0 -morphism, h, from game G, to game G 1 , and there is a winning strategy, Q, for s 1 T, then U:ere is a strategy Q', which is winning for each s' c h( s). Con- ' versely, if Q 1 is a winning strategy for s', then there is a strategy which is winning for every s such that s· c h(s) and s 1 T.

The proof of this theorem appears in Banerji & Ernst [4] and in Banerji [3). For the immed­ iate purposes of this paper, we shall now show how an s 0 -morphism exists between certain classes of games,

3. Twg Related Classes of Games

K~ffman [7] developed a powerful method for learning how to play any game in a class of games which he called positional games. If we had some way of recognizing when a game is essentially positional, we could use Koffman's method for playing the game. In tr.e first sub­ section we will define positional games and in the next subsection we will derive sufficient ccn~i:ions for a game to be s 0 -morphic to a pos~t~onal game. Theorem 1 shows that Koffman's method is useful on any game that is s 0 -morphic t c a positional game.

3,1 Definition of a Fositional Game

A positional game is defined by a 3- tuple, (N, A, B), where each element of A ar.d Bare subsets of N. Intuitively, one can view a positional game as being p:ayed on a board in which the set of squares is N. Ea~h player on his move occupies an unoccupied square. A and B are the sets of winr.ing pa~hs for ~he first and second players, respectively. If t!",e first player occupies all of the squares in a path in A, he wins. The second player wins upon occupying a path in B.

We will represent each situation by ((X, Y, #), m) where X is the set cf squares occupied by the first player; Y is the se t of squares occupied by the second player; # is the set of empty squares; and m is a 1 if the first player is on move, and 0 otherwise. Given any (N, A, B), we car. construct a game (S, R, P, w, L) which satisfies the following pc stula t es:

P1: ((X, Y,#),m) cWiffm=O &:3: a(acA& a~X)

P3: ((X,Y,#),m)cPiffm=1

P4: (( X 1 ,Y 1 ,# 1 ),m 1 )R((X 2 , Y 2 ,# 2 ), m 2 ) iff

((X 1 , Y 1 ,# 1 ),m 1 l+WUL and either

or i. :3:11( ntH 1 & x 2 = X 1 U [ n }&# 2 =ttj-[ n}&m 1 =1;i m 2

ii. :3:n(nc# 1 & Y 2 = Y 1 U[n}&# 2 =# 1 - [nl&m,=O;tm 2

It is easy to show that any (S, R, P, W, L) so constructed satisfies G1-G4.

PO gives the set of game situations. P1 and P2 relate the wins and losses t o A and 5, P3 indicates t hat the first player is on move when m=1. According to P4, the first player's move consists of moving an element of # to X, while the second player's move consists of moving an element of # to Y. P4 also forbids moves from a win or a loss.

Tic-tac-toe can be represented as a posi­ tional game. N is the set of nine squares on a tic-tac-toe board. A is the set of horizontal, vertical and diagonal lines, and B =A; i.e., the set of winning paths are the same for both players.

3,2 Definition of Reducible Games

Often a game can be described, conveniently, in terms of a set of properties, A chess posi­ tio~, for example, can be described by consider­ ing each square t o be a property whose value is the piece on the square (or empty}. A property then is a function which maps game situations into some set, e.g., chess pieces, Reducible games are described in terms of such properties.

A reducible game (S, R, P, W, L) is des­ cribed in terms of n such properties, f 1 , f 2 , ··· , f , and two classes, A and B, of subsets of these ~roperties. For any posi t ion inS each of then properties has a value of 0, 1, 2 or 3. The postulat es of a reducible game involve the set T of positions that are reachable from some starting position s 0 1S. Space does not allow us to give a complete f ormal definition of the postulates of a reducible game, Instead, we give a brief informal description of a reducible game and a detai l description of race, a typical reduci bl"e game .

The A and B of a reducible game are analo­ gous to the A and B of a positional game. Each element a1A is a winning set of properties in t he sense that a reachable position s is a win if f(s }=1 for each f1a. Similarly, a reachable position, s is a loss if f ( s}=2 for each f1b1E.

Each legal move from a reachable position, s, to a new position t (i ,e., sRt) changes the value of some property f fro~ 0 to non-zero. That is, there is an f such t hat f(s)=O and f(t)~O . In addition, once a property acquires a non-zero value it will remain non-zero for the remainder of the game, Due to these rules (and other rules described below} about the way that moves change the values of properties, a property can become inessential to the play of the game, An inessential property is one that can never contribute to a win (or a loss) because every winning (losing} set containing it contains at least one property whose value cannot be changed to a 1 (2). Moves affect the values of inessen­ tial properties in a different way than essential properties.

If a reachable position s is not a win nor a loss, and if f ( s)=O for some property, f, then there is a legal move from s to a new position t (i.e., sRt}. In tall of the essential pro­ perties have the same values as they had in s except for f whose value changes, i.e., ·f(t)fo . Iff is an inessential property of t, f(t)=3 . If f is an essential property of t, f (t)=1 if the player made the move (i.e., SIP ). If the opponent made the move and f i s essential for t, then f ( t)=2. In addition, al l of the inessen­ tial properties of t acquire a value of 3. Thus , we see that a single move may change the values of several properties.

An example, race, will help to clarify the above description of reducible games. One way to describe a race position is to tell the players who is on move, what ticke ts are still available for purchase, and how the horses stand, i.e., to whom, if any, each horse belongs and where it stands on the track, which horses are disqualified and which horses are unowned. Each situation, then, has three components , and we shall designate a situation by a triple (t , b, m) where m is the usual move indicator, 0 or 1. The first component , t, is the set cf unbough: tickets. The second component, b, is the board, i.e., an assignment to each horse of F1 , P2, P3, E1, E2, E3, UO or DQ. These values stand for "owned by the first player· and in pcsi tion 1, 2 or 3", "owned by the second player an~ i n posi­ tion 1, 2, or 3", "unowned" and "disqualified", respectively.

We may, at this point, make various con­ ventions about whether any combina tion of these three components would be allowed, Should we, for instance, accept a situation where no tickets are bought, two horses (one owned by each player) have already won, while three others are disqualified? The answer, we believe, is a matter of taste. In any case, it makes no difference in the final analysis, because as long as we take the proper initial situation as the one where all the tickets are unbought and all the horses are unowned, then the move rules restrict T to exclude all such nonsense states, since such states cannot be reached by any sequence of legal moves. This exemplifies the strong influence of the set T on all our discussions and explains why it plays such an important role in our definitions.

Continuing with the example, let posi tion (t 2 ,b 2 ,m 2 ) be a legal move from position (t 1 ,b 1 ,m, ). Then t2 contains all the tickets in t 1 except some specific ticket Mi. Also m 1 =0 if m 2 =1 and vice versa, b 2 is obtained from b 1 as follows: the ownership and the positi on of al l the horses are the same in b 1 and b 2 except for those whose columns contains an X in the Mi row of the move table in Fig. 1, For these horses, their values are advanced one step if they are unowned or belong to the player on move. That is, if m 2 =0, then a value of P1 becomes P2, P2 becomes P3 and UO becomes P1. If m 2 =1 then E1 becomes E2 etc, and UO becomes E1, If the horse belongs to the opponent of the player on move, it is disqualified, i.e,, if m 2 =0 then values of E1 and E2 become DQ and if m 2 =1 then P1 and P2 become DQ, Disqualified horses on the Mi list remain disqualified.

A situation (t,b,m) is winning if and only if there is some horse h with a value PJ in band m=1, Similarly (t,b,m)cL if and only if m=O and there is a horse whose value is EJ.

To see that this game is reducible, one sets up one function f i for each ticket Mi as follows, The value of fi (1<i<9) for a situation is 0 if and only if Mi is unbought, i.e., if Mi 1 t, If Mi is not in t, the value of f has to be sur­ mised from the values of the horse as given in b. If at least one horse appearing in the row of the ticket Mi has a value P1, P2 or PJ, the value of f. is 1, If at least one horse on the row of Mi fias a value E1, E2 or EJ, the value of f. is 2, (If the game is played legally from a stkrting state where all the tickets are on the table and all the horses are unowned, then these two rules will never contradict one another). If all horses in the row Mi are dis­ ~ualified, then f. has the value J for the state,

It is clear 1 that if any winning situation is reached from the usual starting situation, then the table shows that there should be exactly three tickets belonging to the winning player w".ich !"las the winni!'.g horse's name on it, So chere is a set of f·s sue!"! that all their values are 1 at that situation. Thus one can isolate a class of sets of the f's such that a situation is a win if and only if all the members of some se t in this class has the value 1, :tis shows that the wins and losses of a race are specified in the same way as the wins and losses of a reducible game.

To see hew the move rules of race fit the above description of reducible games, let the value of f be 0 fer some situation, From what has gone above it is clear that in this case Mi will be an unbought ticket, If this is a reach­ able situation which is neither a win nor a loss, then the player on move can buy this ticket, If al l the horses on this ticket are either dis- . qualified or belong to the opponent, then after buying this ticket all the horses on it will be jisqualified and the value of the ticket for the ~ew state will be J. Otherwise the value of f will be determined by the identity of the player, which in turn, will be reflected by the owner­ ships of the horses in the next position, As far as all the other tickets are concerned, the un­ bought ones will remain unbought, and the others will either retain their values (since horses do not change hands, nor do the tickdts beArir.g the horses names) or some tickets take on the value J if their horses get disqualified by t he purchase.

J,J A Homomorphism

In this section we define a relation h between positional and reducible games, Theorem 2 proves that this relation is an s 0 -morphism, Cur reason for doing this is that we have power­ ful methods for playing positional games, Since s 0 -morphisms preserve winning strategies, we can now apply these same methods to reducible games, Given G, i.e., given n functions, f for 1 ~ i ~ n and the subsets A and B construct a positional game G· defined by the triple (N, A, B) where N = [1, 2, ··· , n}. Now construct h C SxS· as follows: For each s 1 S, the element­ s· =((X, Y, II), m) will be related to s (i.e,, s' ch(s)) if and only if

1. m=1 if s c P; else m=O.
2. Every such that fj(s) = 1 is in X,
3. (J) Every j such that fj(s) =2 is in Y.
4. ( 4) j c II if and only if f . ( s) = 0.
5. J (5) If f.(s)=J and j cpcAUB, then there is an iJand akin p such that i eX and k cY.

The intent of (1)-(4) is clear. (5) indicates that if fj is inessential then so is "square· j in the positional game. A square is essen­ tial when all winning and losing paths con­ taining it, contain a square occupied by the player and a square occupied by the opponer.t.

We now can prove:

Theorem 2, Given a s -reducible game G, a pos­ itional game, G·, def~ned by (N, A, B) , and a relation h that satisfied {1)- ( 5), his a s -morphism from G to G·.

0 The proof of this theorem, t ogether with the formal definition of a reducible game is given in Banerji and Ernst [4) and in Banerji [3 ).

It is worthwhile pointing out here that our invocation of theorem 2 above has establisred race only as homomorphic to a positional game and not necessarily to tic-tac-toe. The establishment of the isomorphism (i.e., a one­ one onto homomorphism) between the resulting positional game and tic-tac-toe will need a more detailed examination of the horse-ticket table. However, this is really unnecessary as far as the mechanical playing of the game is concerned. The Koffman technique mentioned earlier in section 1 is designed t o play any positional game of moderate size and hence the isomorphism with tic-tac-toe is a matter of human visual convenience only. For instance, the number scrabble game is clearly positional since each chip is either unowned or owned by one of the two players and so the partitioning vf the chips at each game situation is obvious, Hence a good positional game playing program could play the game whether the chips were considered arranged in a magic square or not. In this sense th~ jam game also is obviously positional so that whether it is tic-tac-toe or not is somewhat immaterial. With regard to race, it could also have been remarked that it is obviously positional since each situation partitions the set of tickets into three subsets­ unbought, owned by the first player and owned by the second player. If we do this then the board showing the position of the horses is a mere distraction. However, the way the Race game is described, the board appears as impor+~t as the tickets. Also, if the ·image of a race position in tic-tac-toe is to be determined, it has to be done, not in terms of the history of the game, but only in terms of the position ~t­ self. As we have remarked before, the position is adequately described in terms of the board 5D just the unbought tickets. An onlooker walking in at the middle of the game is at no disadvan­ tage if he does not know who bought which ticket in the past, Our method of formulation reflects this fact. It also points out how theorem 2 is capable of exhibiting the homomorphism even in this formulation. Our surmise is that theore11 2 would be able to recognize a positional game no matter how it is formulated, The examples in this paper have used only the games in Fig. 1, However, more complicated games of race (i.e,, more horses and tickets) would have three dimensional tic-tac-toe, Bridgit or other posi­ tional games as their images, We have used the race in Fig. 1 to keep the examples simple.

4· Concluding Remarks

Of the various ways in which one can change the representation of games, we have considered the case where the change takes the game to a homomorpr~c image. Of course, the kind of homomorphism considered in this paper (to wit, the s -homomorphism), is net the only kind of homom8rpr~sm that can be studied. The various examples studied by Amarel [1J and the graph homomorphism studied by Banerji [2], are examples of other kinds of homomorphisms. Whether all these can ultimately be unified to a general class of relations between representations or whether we will have to remain satisfied with a nurr.ber of special cases, remains to be seen,

It is our belief that some of the results in this paper, together with other work on homomorphisms, is a first step towards the a~tomati c change of representation, Theorem 1, for instance, could lead to the automatic veri­ ficati cn of a "hunch" that a given game may have a strategy similar to that ci' a previously known game. Given a repertoire of previously understood games, the theorem may lead to an exhaustive search for possible changes of representation .

Although much less general, theorem 2 lends greater strength to this search since it allows one to establish the fac t that a given game is homomorphic to one of a wide class of games (in this case the positional games), thus reducing the search space. If the search produces an affirmative answer, it also allows one to con­ struct a specific homomorphic image as opposed to searching for one.

Needless to say, such theorems do not obviate the need for heuristics, They merely add to our stock of applicable heuristics or render previously known heuristics more widely applic­ able. In the absence of a generally efficient problem solving technique (it is not hard to see "that given any such technique, a problem can be devised which renders it inefficient), one can at present only hope for a larger arsenal of applicable ideas.

ACKNOW1EDGE)1ENTS

This research was supported by the Nati onal Science Foundation under grant GJ-1135 and by the Air Force Office of Scientific Research under grant AFOSR-125-67 and AFOSR-71-2110 .