--- title: "An Application of Decision Analysis to Strategy-Making in Game Playing" authors: - "Yahachiro Tsukamoto" - "Koichi Yamada" - "Toshiro Terano" doi: "" url: "https://ijcai.org/proceedings/1979/199" pdf: "https://ijcai.org/proceedings/1979/0199.pdf" venue: "Proceedings of the Sixth International Joint Conference on Artificial Intelligence" year: 1979 pages: "" track: "" keywords: --- # An Application of Decision Analysis to Strategy-Making in Game Playing Yahachiro Tsukamoto, Koichi Yamada, Toshiro Terano *Proceedings of the Sixth International Joint Conference on Artificial Intelligence*. ## Abstract This paper presents a game playing model of Score -F our that is a kind of alignment game similar to three dimensional tic-tac-toe. The present model aims at winnin g a game most ef ficiently. The pricipal proposal is an adoption of Deci s ion Analysi s, a widespread method of systems analysis, instead of Minimax Procedure. This paper includes a static evaluation on the state of game, a brief illustration of Decision Analysis, a method of strategy -makin g and an outline of a game playing machine. Based on the results from th e experiments conducted with human players, we assert that Decision Analysis i s a good method to make strategies which enable us to take advantage of the oppo nent's mi sta kes and it is shown that the risk caused by abandonment of the conventional assumption that the opponent selects the best move is averted by th e introduction of a learnin g system. ## Full text ## 1. INTRODUCTION 'fherc are many papers as for game playing model which :;atlsfics the following conditions . 1. l'lay :;tarts from a situation which is not advantat;eous to e ither player. 2. ;'. 'l'hc interest of game playing is just "to win a game" and there is no more. Lf a 1;arne is played under the above conditions, it would be valid that a player adopts the asswnption that the opponent selects the best of all let;ul moves in every situation, for he sometimes loses a game by making little of his opponent 's skill. In this sense Minimax Pro­ cedure [l] on the basis of the above assumption is acle<!Uute for strat ep;y-making when we need not dare to run a risk. However games are not always played under such conditions. For example, there are sometimes occasions when the interest of e;ame playinp; i s "to win a game mort: efficiently" rather than "to win a e;ame". More efficient winning mean::; winnine; with fewer moves in some t;ames or with capturing more pieces of t.lte opponent in other 1;ames, [.;enerally speakinp; , <>v··t·wil<'lmi.n,; one. ln tlti:; case it l>ecomes .iHJIIlii·L:~nL !'or· a ]llaycr· Lo make more efficient !ftuv":;, wit i.dt enal>le him to take advantage of hi s oppom·nt ':; mistakes. Tn other words, the con­ ventional a:;:;umption is too passive for winning a t;amc efficiently. Similarly efficient moves :..;hould be played in occasions when a heavy handicap ls imposed. Decision Analysis [2] is effective for strategy­ making in a game playing model where we are aiming at an efficient winning . In this method we can take into account the probabilities of its opponent 's mistakes. In this study, it i s assumed that the opponent plays a move of the best three among all the possible moves even though he is an unskillful player. Then the key point of this method is the determination of the judgemental probabili­ ties assigned to these three moves. We intro­ duce an index representing the opponent's skill. It should be noted that there may be a risk caused by underestimation of the oppponent 's skill or inefficiency by overestimation. This problem, however, is resolved by introducing a learning system which improves the initial value of the index step by st ep by evaluating the opponent's moves. We are applying the above method to strategy­ making in Score-Four game and Scor e-Four Playing Machine, which is a system playing with a human player, is constructed. ## 2. DJ·;~;crnP'l'TON OF SCORE-FOUR GAME Score-Four is an aligrunent game played by two persons; one uses black balls (simply called Blacks) and the other white balls (called Whites) as their pieces. The game is played on a board with sixteen st icks which penetrate the balls through their small hole. (See Fig.l) 0ince each stick is capable of acceptin~ four balls , the board has 64 points on which players put them. Each point is denoted by a pair of number, (m, n), where m and n mean a stick number and a horizontal plane number respective­ ly , and 1 ~ m < 16, 1 < n ~ 4. Fig.l Board of Score-Four ![Image](https://ijcai.org/proceedings/1979/fulltext/199/image_000000_e621a1e6fd8a2f0c81b14ada0ce556aa4f358d01790eda34a008f43d1a344ef3.png) Play starts with the first move of the player who has Blacks (called Player Black) and then each plays a move by turns . Players, however, can not put their balls on arbitrary points, that is, they are allowed to make a move on (m, n) only if n is eqaulto 1 or (m, n-1) is occupied. Guch a point is called legal. In Fi g .l, for exampl e , (16, 3) is a legal point and (16, 4) is an illegal one. The game is won when a player forms a string of his four balls i n any line, either horizontally, vertically or di agonally. If it is not won within 64 moves, i t ends in a draw. Now, we present some important properties of the v,ame , which will help us to look for factors to evaluate a board s ituation. 1. The game is played on a three-dimensional board. 2. 2 . The game ends within 64 moves. 3. The number of legal moves in a board situation is equal to or smaller than 16. 4. The number of lines in which it is possible to form a string of four balls is 76. ## 3. METHOD OF EVALUA'riNG BOARD SITUA'riONS A s ituation of the board may be determined with the consideration on all the possible states of 76 lines . Therefore we adopt them as the fundamental factors to evaluate a board situa­ t i on. Each line is in one of the following ei ght types of states . Let Ctj (j = 1, ... , 8) be an index for evaluating a line in j - th st ate. STATE I (Four) : There is a string of four Blacks (Whites). We fix the index, Ctt = 150. S'T'ATE II (Active-Three) : 'T'hree point:> arc occupied by Blacks (White[;) and the rern~drH'r i ~: unoccupied and legal . Tf player Hlack (Whl t,, , ) makes the next move an<l he cn.n win n f~arnr· l>,V forming "Four", then Ct2 = '(0 , otherwi:w It? = JO . (See Fig . 2 , a) STATE III (Sleeping- Three) Blacks (Whites) occupy three points in the line and the remainer is unoccupied and illegal. a 3 = 18. (Fig . 2, b) STATE IV (Active-Two) : There are two points occupied by Blacks (Whites) and two vacant anu legal points. a 4 = 4. (Fig. 2 , c) g. T-formation (2) h. V-formation ![Image](https://ijcai.org/proceedings/1979/fulltext/199/image_000001_ba9c9bbfa68f66c24aadb36ca3a86642522842eddd294b648e1ef877377f1425.png) Fig.2 Factors to Evaluate a Board Situation STATE V (Half-Active-Two) : There are two Blacks (Whites) and two vacant points; one is legal and the other is illegal. At his next turn, Player Black (White) can form "Sleeping­ Three". a.s = 5. (Fig.2, d) STATE VI (Sleeping-Two) : There are two Blacks (Whites) and two unoccupied and illegal points. Player Black (White) can not form "Active-Three" nor "Sleeping-Three" at his next turn. a. 6 = 8. (Fig.2, e) STATE VII : There is only a Black (White) and the others are unoccupied. a.7 = 1. STATE VIII : Both Blacks and Whites exist or there is no ball in the line. a.s = 0. Now we show the two important patterns on which games are won. 1. One forms two or more "Active-Three" with a move. He can surely win the game at his next move. This pattern is called "T-forma­ tion". (See Fig.2, f, g). 2. 2 . One player forms "Active-Three" where the only one vacant point is just under the vacant of his "Sleeping-Three". He can win the game at his next move. We call it "¥-formation" which is shown in Fig.2, h. So , as an additional factor, we consider whether or not there exists T- or ¥-formation and let a.g=50. Let us now show how to evaluate each factor as stated above. Let ui (i = 1,2, ·.. , 76) and v be the evaluations of i-th line and T- or ¥­ formation, respectively. Then, where Then, static evaluation, U, of a board situation is defined as the sum of ui ( i = 1, · · ·, 76) and v as : ## 4. STRATEGY-MAKING BY DECISION ANALYSIS First, we make a brief explanation of Decision Analysis. When one intends to make his deci sion about a certain problem by using Decision Analysis, he must generate the deci sion tree as shown in Fig.3. It represents a chronological arrangement of choices controlled by him and chance. The tree graph is composed of chance points, strategies selected by him, events depen­ dent on chance and utilities . In the above, it is only at decision points that decision maker can decide which path he goes to. The main procedures of Decision Analysis are "folding back" at decision points and "averaging out" at chance points. In Fig.3, folding back at c 1 is the procedure to assign the maximun of u 1 and u2 to c 1 and averaging out at C2 means to assign the expected value of u 3 and u4 to c2 . After he accomplishes the procedures at every points, he only has to select the. strategy leading to the point where the expected utility is the largest. Fig.3 Decision Tree ![Image](https://ijcai.org/proceedings/1979/fulltext/199/image_000002_b21817a64d6945d675f3a1b3e023755b2bd54fa9553fd3fc58d050a76574a526.png) In game playing a player can not predict the opponent's next move precisely. He can consider at best the probabilities in terms of judgemen­ tal probability. Therefore we may take the opponent's next move as an event dependent on chance. Now let us show a way to calculate the judge­ mental probabilities, Pi, that the opponent plays the i-th best move, mi. Suppose there are n legal moves at his turn. Then, first, the judgemental probabilities must satisfy the following equation It is a natural assumption that the judgemental probabilities depend on the opponent's skill, because skillfil player is likely to play the best move at a high probability and on the other hand beginner frequently plays a worse move. Let by fi be denoted an index for evaluating i-th best move where f1 ~ f 2 ~ · · · ~ fn . Then the degree o"f the opponent's skill may be roughly represented as follows; where f means the expected value of the evalua­ tion of the opponent's next move. Furthermore, the concept of entropy is utilized to estimate the judgemental probabilities. Entropy in information theory (3] implies a degree of "uncertainty" or "randomness" of events. If we choose Pi (i=l,···,n) so as to maxmize the entropy, they are the most reasona­ ble judgemental probabilities. It is because the maximization of uncertainty implies the safest or most temperate estimation. Entropy, H, is defined as: By maximizing H subject to Eqs. (4) and (5), we obtain: where Here , let us assume that the opponent plays only one of the best three moves m1, m2 and m3. Then, from Eqs. (4), (5) arid (7) we readily obtain the following equation: where x=P2/P1 and K= (fl-f3)/(f1 -f2). If Eq.(8) has zero or positive real solution, judgemental probabilities are expressed as follows. (See APPENDIX I) Since it is not guaranteed that Eq.(8) has zero or a positive real solution, we show ways deter­ mine f 1 , f 2 , r 3 and f and examine the solvabili­ ty. First, consider the case where K = 2. In this case one may find that f1, f2 and f 3 are an arithmetical progression and that P 1 , P2 and P3 are a geometrical one. Moreover, except f or tne case where f = f3, Eq.(8) comes to be a quadratic one which has two real solutions - one of them is either positive or zero and the other is negative - because we are assuming that the opponent plays one of the best three moves, that is, Therefore, if f takes on and one, it is estimated and f 3 = 0. Then in the we obtain that P 1 = P 2 = 0 ( 5) and (7). any value between zero that f 1 =1.~, f 2 = 0 .5 case where f = f 3 = 0 , and P3 = 1 from Eqs. ( 4 ), However it seems to be more natural than the above to consider that evaluation, fi, for i-th move, mi, is intimately related to the board situation, S, or to its evaluation, U(S), after mi is played. This idea is appreciated by recalling that the facts that we sometimes find both the extreme cases where m 1 and m 2 have little differnt evaluations and where a player loses because he has played m2 instead of m 1 . Let Si be a board situation after a move, mi, is played. Then, we define fi by using U(Si)-s given in Eq.(3) as follows; where s 1 and Sn mean the boa:rd situations after the best move and the worst one are played, respectively. In general, it is impo~s.ible to solve Eq. (8) analytically. But if f taKes any value between f 3 and 1, it is easily solved by using a compu­ ter. (See APPENDIX II) On the occasion when f <f3, Eq.(8) does not have any positive solution. It is, however, so risky to make little\_of the opponent's skill that we consider as if f = f3 from the view point of safety playing. Now it is necessary to consider how to estimat e f. Since it is given without any reliable foundation at the beginning of games, it should be improved during the game. In this study we adopt the next equation for this purpose. Let fk and fk be the evaluation of the move, mk, played by the ~pponent at hi s k-th turn an~ the estimation of f at the moment just after m is played, respectively. where S i s a constant parameter which takes on a value between zero and one. The above i s the major algorithm to be installed by r>FT'M standing for Gcore-Four Playing Machine. I n i>FT'M, the depth of lookahead is considered to be only two steps but it is almost enough on usual occasions, and since the static evaluation function takes into account T- and V-formations which guarantee a winning several moves ahead, the actual depth corresponds to four steps or more in the critical moment. The further details on GFPM will be presented at oral presentation. ## 5. EXPERIMENTS : SFPM V.S. HUMAN PLAYERS The experiments are conducted to investigate the advantages of the method presented above. Experimental results of game playing with human players are shown in Table 1. The number of the subjects is fifteen and each plays several games under different conditions. Average nunber (A.N.) of moves required for SFPM's winning implies the index of \_g)ficiency of winning . As for conditions, f is the initial estimation of the opponent's skill. The condi­ tions that ro = 1.0 and ro = 0.5 mean the over­ estimati~ and underestimation respectively, because f of every subject took a value bet­ ween 0.65 and 0.93 at the end of a game. Fig.4 sho~ a typical example of the fluctua­ tions of f observed during a game. Table 1. Results of Experiments. | Experi- ment Number | Conditions B | fO | Results of Games | A.N. | |-----------------------|----------------|------|------------------------|--------| | I | 0 | 1.0 | 7 wins and 1 defeat | 43 | | II | 0 | 0.8 | 5 wins and 3 defeats | 28 | | III | 0 | 0.5 | [ 4 wins and 4 defeats | 35 | | IV | 0.05 | 1.0 | 6 wins and 2 defeats | 39 | | v | 0.05 | 0.8 | 5 wins and 3 defeats | 29 | | vr | 0.05 | 0.5 | 6 wins and 2 defeats | 26 | ![Image](https://ijcai.org/proceedings/1979/fulltext/199/image_000003_b623d4eaaee37d61c83bc6ed91afeded2313005b1087e5ab73fe265a01016d3f.png) Human player in this example belongs to middle class and he lost in the three experiments shown in Fig.4, but he won in Experiment III at the 34th move. Next it is shown how ~PM plays a move in accor­ dance with fK. When f is high, that is, SFPM regards its opponent ·as a skillful player, it inclines to form "Sleeping-Two" and "Sleeping­ Three" rather than "Active-Two", "Half-Active­ Two" and "Active-Three". This tendency i s usually found in games played by skillful players. The tactics are adequate to game playing with skillful players for the following reasons. 1. Skillful players seldom miss blocking their opponent's "Active-Three". 2. To form "Sleepin-Two" or "Sleeping-Three" makes the opponent disadvantLgeous gradually because they restrict the opponent's selection of moves. 3. "Sleeping-Three" is a necessary preliminary for T- and V-formations. (Refer to Fig.2) The tactics are, however, not efficient to defeat a beginner or an unskillful player in the sense that many moves are required to win a game, because they are the protracting tactics. On the other hand, when fk is small, SFPM inclines to form "Active-Two", "Half-Active­ Two" and "Active-Three" rather than "Sleeping -Two" and "Sleeping-Three". These tactics are effective for game playing with unskillful players who sometimes miss blocking the oppo~ nent's "Active-Three". However they are too simple to win when the opponent is skillful. We can say from the experimental results that the figures in Experiment IV, V and VI are much improved in comparison with Experiments I, II and III. The strategy-making in Experiment I is the same as the one by Minmax Procedure. It should be noticed that, in order that ~he use of Decision Analysis works well, it is necessary that the opponent's skill is known rather precisely. ## 6. CONCLUSIONS In this paper we have presented a game-playing­ machine which employs Decision Analysis as a substitutional method for Minmax Procedure. A game-playing-machine controlled by Minmax Procedure can not cope with the game playing in which efficiency of winning is make much of, while it works very well if it aims at only winning, in more strict words, minimizing the risk of losing. Decision Analysis is a good method to decide strategies which enable a game playing machine to take advantage of its oppo­ nent's mistakes -not playing the best move- and t o win a game efficiently, while the good effi­ ciency is obtained at the expense of increase in the risk. However, such a risk is capable of be ing averted to passable extent by estimating t he opponent's skill correctly and assuming that he plays a move of the best three in any board situation. Learning system yields the high rate of winning and the good efficiency even though the opponent's skill is misestimsted at the beginning of a game. Besides, we may conclude that Decision Analysis is also useful for many other games which do not satisfy the conditions stated in INTRODUCTION. Finally we suggest that the opponent's move selection is usually influenced by not only his skill but also his various biases; some players may incline to make such moves that are very offensive or very defensive [4]. If we take t he bias into consideration in order to deter­ mine the judgemental probabilities, Decision Analys is must be a more useful method of str ategy-making in game playing. ## ACKNOWLEDGEMENTS The authors wish to ttmnk Dr. M. Sugeno and Mr. S. Kainuma for their perceptive comments and suggestions. ## APPENDIX I Let us transform Eq.(7), then we obtain: Since x=P2/P1 , we can re-write it as: Therefore which directly leads to Eq.(9). ## APPENDIX II Let us denote Eq. (8) by F(x) = 0. Therefore Eq.(8) has only a real solution within the interval, [O,oo) and we can obtain the judgemental probabilities from Eq.(9). 2. If f = f 3 and f 3 < f2 < f1 = 1, then we obtain P1 = P2 = 0, and P 3 = 1 from Eqs . ( l;), (5) and (7). 3. If f3~f~f1:::1, and fi=fi+l (i=l,2), then we can calculate the judgemental probabilities from Eqs.(4) and (5). ## References 1. N.J.Nilsson, "Problem-Solving Methods in Artificial Intelligence", McGraw-Hill Book Co. 1971. 2. H.Raiffa, "Decision Analysis, Introductory Lectures on Choices under Uncertainty", Addison-Wesley Pab. 1970. 3. H.Sato, "Information 'l'he ory"(in .Tapunese), Shoka-bo, 1974. 4. M.Eisenstadt and Y.Kareev, "Toward a Model of Human Game Playing", Department of Psychology, University of California, San Diego.