Experimental Studies Of Human Decision-Making And Its Simulation By Situation Control Technique

EX.PERDIEir.UL srtJDIES Or HOlUB DECISIOB-IUXING AND ITS SDIULA.TIOII BY SITU.ATIOII COifrROL TECHBIQUll: ( 011 THE B.A.SIS Or A CHESS ENDGAME)

Ruslan Einulla ogly HajieY Republican Information and Computing Centre, llinistry of Health of the .Azerbaijan SSR Block 3165, 370122 Baku, U.s.s.R ·

describe the process of establishi.ng re­ lations, the process of comprehending a position, which precedes and deteraines the foraation of a variant. It can be concluded that the use of a l.a.Dguage describing the process of establishiDg relations will enable one to get OYer some difficulties of chess prog:rew1 ng and to lay down the ways of coaputerisi.Dg endgaae probl·s.

It is apparent that the use of new laaguages describing activity, the lan­ guages which are capable of describing the process of establiSbing relations, should bring about serious cb&Dges in the total structure of the theorr which toms the basis for chess progr-1ng.

Thus, one of the basic notions in chess progr8JIIIIing is calculation depth. ID cybernetics by depth is generally aeant the nuaber of moves of any ches.an coD­ trolled by the prograa. .A.s indicated by the eTideoce obtained 1 the depth of analysing a position oy aan is det81'1lined by the presence of a syst· in the tol.'ll&­ tion of a position in the course of estab­ lishing relations between the pieces. ID other words, central to a traditional understanding of a depth in cybernetics is a graph whose vertices are successiTe­ ly altered situations while the depth of analysis in buaan activity is deterained by a graph whose vertices are fomed by the pieces of a particular position ana the edges by the relations between these pieces.

Hence, troa the correlation between the principles of exl.sting chess progr-­ ming and real activity in the solution of endgaae probl·s, the consequence derives that the development of a chess prograa which is capable of successfUlly solving endgaae probl·s is related to the con­ struction of a language which would enable us to describe- the process of establishing relations and toming gene­ ralised notions. It is only languages of this kind that can produce perceptible results in such a large space as is a

chess endgame.

The ~ew method of progr8111ling should permit of forming the solution variant DOt only for a definite predetel"'lined uuabe:r ot moves. The nuaber of moves in the variant should cb&Dge with the structure

and properties of each new position.

The anal~sis of experiiD.ental re~lts

showed that of' all e:dsting methods tor

.Abstract

The paper exaaines the simulation of the basic mechaniSIIIls of the chess endgame problea solution by man. The experimental results of a psychological investigation into the mechaniaa of structurisatlon,ge­ neralization, and goal formation of a si­ tuation have been presented and a seai - otic system of formation of generalised imi.tation models haTe been discussed which toms the basis for hmu.n decision­ making.

The analysis of the literature on the simulation of chess game haTe led to a conclusion that various chess prograas were considered by their originators as a theory or aodel of real activity of hwaan chess-player. In this connection, to clarify the nature of the difficulties in simulating chess gaae is to clari~ to what extent chess programs are actually in compliance with a chess player's real activity they are to sillul.ate.

The majority of prograa designers who st.ulated the activity of a chess j~ayer considered this activity as pass­ through a labyrinth haTing a certain tial stage (area,graph vertex) and the labytinth point which is to be reached.

If the activity is understood as above, it is of prime iaportance to find the ways 'of reducing the voluae of the chess labyrinth. .A. special probl· presents it self - the probl· of redicing

the tasks of the tree of chess game.

This limitation of chess prograaaing is esf~;ially clear when one approaches the t 1 stage of the game - the endgame. .A.n optiaum endgame suggests, to a greater extent than the other game stages,a cal­ culation for many moves ahead. It is this circumstance that makes ineffective, in respect to endgame, the majority of existing programs designed for compute­ rizing a chess game. Limited possibilities ot the depth of analysis and the tact that the plann1 ng in these progr81ls does not exceed several moves ahead has led to a conclusion that the probl·s of chess endgaae cannot be solved with existing

means of prograDIIling.

.A. correlation between the principles ot progr8JIIID.ing and the results of analytda ot human activity shows that the basic difficulty of the progr81Uling lies in that the aTailable means of math.atical description of activity fail to adequately describing mental activity, the situation control of big systems developed b1 D.A. Pospelov and Yu.I.Klykov (U.s.s.R.) is in the closest agreement with endgame solu­ tion process. An attempt was now made to employ this method for simulating h'Wilan activity when solving chess endgame problems.

The practical use of situation control in chess is connected with the development of a system of semiotical models through the use of which a genera­ lised model of chess game solution can be formed.

By the language of situation macro­ description in a chess endgaae problea is meant a semiotical systaa comprising an aggregate of three basic sets 1 X is a set of base notions; R is a set of base relations; and G is a set Qf formation rules for derivative notions and rela - tiona. Base notions include a set of natural l~e units (words, expressions. sentences 1 ,etc.) used tor the decription (designat on) of the chess endgame problem objects tor which it is not necessary to disclose the contents in order to solve the problem. These notions area o o

0 X~=piece;Xa=field;~ing;X4 -kn1ght; 0 0 0 X 5 =black-field bishop; X~ engaged; x,,=vacant

0 , , D , · r,~ LJ1 1 X2 ;= tJ~,, etc.

The language has about 100 notions of this type.

The set of base notions has a hierarchic structure, there are notions ot zero order and those of higher orders (derivatives). According to (4),the notion of the ith order (i=0.1 ······ n) is the characteristic ot . the class of a problem element. Base notions have the greatest volume. Reduction of the notion volumes occurs when the notion is included into another class. The rule of identical trans­ formation ot, notio.ns is fJ s,.m,etric sub­ stitution& X:;:~ 't,.x:j ~.a.Xcl(" . .. 'tfi .XJ

When simulating chess endgame, the base scope of knowledge is formed accord­ ing to this rule.

£ f 0 ,_.., .x, =~,.x, ~.~x3 2':rJ\(~)f,2,.J ~ ..X f ~ .x· · ..X-t = ~~ :.t :J ~ ~.:r.XcK)f-2.-' .x; = 't:,.x,' C?,.x; ~.r.X.'f'8J~.e.3 "white king" "black king" "white black­ field bishop",e~

A correct definition of a notion enable one to expand it into elementary components. Por example, thetxpansion of

the notion "white lUng" isa .x:.:. ~., (~,.X,o ~,.x;) 't,J.X; 'ls..X ;K. )1,2,.3 where .x.J = z,.x; ~,.X/ = white piece 0 0 0 0 X1 :piece; Xi =white; XJ =king; X (K)t,a,~ = movement of the king.

The rules of moving the chessmen are realized within the software system in the block "determination of potential relations". The block "detel'lllination of potential relations" is used to determine the relations arising in the process of considering the position in terms of its ~cs.

Por the model, this block is, to some extent, an analog of a "mental look" which is inherent in un analysing a problematic situation. Dlle to its perfor­ mance, the position under analysis appears as a set of ordered triplets <X,RmX"'>,where Xt and X,/ are the elements of situational position and Rm. is a beam of potential relations determined tor these elements.

Base relations include a set of matural l.angu.age units denoting static and situational links established between situational objects when solving the proble~~. They are binary relations such as 2,, ~~, 'l3 etc, which mean&

.Xi "<1, .K_t· i.e. .X,· is an element of~- class; .x._ ~.t..YK i.e · .X,· is on .X K ;

.Xi "t.1.X'J i.e · .Xi has a name .X9- , etc.

Base static relations feature per­ manent links between the elEIIIlents of the problem, the links being independent of the situation in which these elements are.

In contrast to static relations, situational relations link the eleaents not permanently but only in a particular situation.

Thus, if the white king at a given moment is on the e1 field and the black king is on the e4 field the specified information is entered ln the descriptive lists tor the given pieces and the rela­ tions of properties make is possible to describe each of the objects (chessaen) in terms otZ.X- codes.

Xt = Z,.X! ~.,.X.Jo ~.&X;o Z.,-..X(K )~.z~ .t v' .Xo,., o "' o .Y6 8 -= i!, ..... :t ~., 6 c.:z .X69 c.s.Xc~Jt,:J,.3

By this means any piece being on any square at a given aoment can be described in terms of z.x - codes.

The set G is given as a population ot generating procedures denoted as gene­ rative grammars which are employed . for formalizing structurization mechanisas ot generalisation and extrapolation of the situations.

Pour types of generative gr8111J1lars are used in a semiotic system& correlation categorial, transformation and commandlns grammars which are correspondingly intended for:

1 )ennumerating the multitude of micro si­ tuations of a chess endgame;

• 2)toming a set of generalized situation structures in the course of the solu­ tion of a chess endgame problem;

3)presetting the process of runctioning of a probl· solution aodel on the given time intervals;

4)enoumerating the set of solutions gene­ rated by the model.

Let us now describe the above gr8JIIIl81' in an abridged and interpreted fora for a chess endgue which was offered in a psy­ chological experiment to two groups of people with markedly different level of chess qualification. Both psychological and more detailed results of the computer experiment will be discussed in the paper.

A message has arrived froa the envi­ roDlllent at the input of the "Input" pro­ grall at a discrete aoaent of tiae& ·object - piece, nalle - king, colour - white, square- e1;# ,object - piece, name - white-field bishop, colour - black, square - d2; # #object - piece, name - pawn, colour - white, square- h2;# #Object - piece, name - king, colour - black, square - e4;# *>bject - piece, name - knight, colour - white, square - f?; # ~bject - place, name - black-field bishop, colour -black, square - f8;# ~bject - piece, name - black-field bishop, colour - black, square - b8 ...

The specified information is recored in the descriptive lists for the given figures.

.X~ =: 't1.X: 'l.J.J; 'tA.X:o ls.K ~K)t,Z,.J .xJ,= "t, .x;, -e~ .x; 'e.A.x;, t5'.xr6)1,2,~ xlso = 'e,.X,' 't_,.x; ~.Kh- ~5'.Xfp)l,2,3 ~ = r., .X,i 't.J .x; 'l.~.X}s 'l~ .x;,..J ~Z..J 4,:; t,.x: 'tJ.x; "f.t.X:~ 't.~.X(,.-;a.jl,.l,.J .n;, = r,..xj rJ.x; t.t .x;~ t~-.x;tJ) (,2,.3 XIIJ = 't,.x; rJ.x; "~.t .x,~$ ~5' .xa;t,2,-'

All interrelations between the objects (pieces) are analysed in the blocks "Analyser" and "Determination of potential relations" by observing the list of objects involved in S(ti) and their descriptive lists.

An array of elementary syntapata and 'l.X -chains is then constructed which foras the basis for the further deaision­ mak~ model. At the output of the "Ana­ lyser block is foraed an array of syntag­ aatic chains describing the pieces of different classes in terms of the presence of common features in all descriptions.

Possible relations between different classes of chessmen are determined in the block "determination of potential rela­ tions".

If we assume now that each piece of any situation may be potentially linked with other pieces by a set of relations, the correlation rules can be considered as singling out essential relations between pieces.

lll data formed into arrays of syntagaatic chains enter the "Oorrelator" block.

The prograa ·ploys the array of correlation grammar rules the left ~ of each rule coaprising llmitations of the features while the right part is a commanding syntagma, i.e. the direction as to what relation (derivative) connects the pieces under study if the above 11111tations are iaplemented.

The critical condition for the for­ mation of derivative notions is the verity of predicates by the aid of ·which a variety of ·relations between the situ­ ational elements are eatablished.

By analysing the information ted to the computer, we can tind the class ot situations comprising the initial situa­ tion. The vertices of the classifier specify the maxillua general part accord­ ing to which correlation grammar rules are derived. The route of each piece is deterained by the "Determination of po­ tential relation" block and is included into the left part of the correlation gr811Dlar.

There is a aaxilmll ot 1?.5 correla­ tion gr81111lar rules for every endgaae with a definite nuaber of pieces (in this case 7 pieces) irrespective of whether Black and White aove first. A UJd.aua ot six relations can be established between every two pieces by these rules.

Let us discuss soae gr8JIIIIl8rs in our position with the white moving first& 25. ¥ xt X:,_ (x,~ 2 X: ,A.X:/1- :z xt) (3 ..x~ r xf-)) ["Xf~~,K:.,.(X;)II{Kj"t1..K;:,).J~ . .::>X;!: 'Y.t,.X~ /1 x;,. 't .. u, .Y: which means& "White King, potenti~ in two half-aoves, attacks the black tefielABishoj"· ~ ..t .t. ~ I) 4 ¥.x,t x~~ rx,, 2.X:fA-A1~x~X:Jx,.,J {.%f)_ rx: r~x~ r.x:)/I(.X/ t~_x:r..))~ ::;) x;;; "t,M" ...t':~ A .Xf~: "t.J~ .Xfc. "White King, potentially in 3 half-aoves, defends the white Pawn". · 94 · .lf.XJ""~ .xt- (.X}M ;;;z_xjr /IXf,·:a.X;}(:l.Kj,Jf.Xf}) [:Xf 't6 .X_,{ (.Xj)A {x/'l~ .X:!t.}J => ~ .X;.,. "l.t.t .X:;. /\ .X;;. "'(. .. u, .X j hf.

'~lack black-field Bishop, potentially in 2half-moves,attacks the white ling", etc. ~~1= be a potentially attacking piece in

~~= be a potentially attacked piece in

't.1s-· be a potentially defending piece in 3 half-moves, etc.

2 half-moves 2 half-moves

About 20 derivative relations of this kind were found in designing the model. The other relations in the rules

~,=be on ··· ,~= to have the right to move, etc.

.&.t any moment of time before moving a piece, 14 to 15 correlation grammar rules are sufficient to define the situ­ ation, construct the lllicrostructures and display them as syntagmatic chains. With 1?5 correlation gr8llllllar rules, the number ot syntagmatic chains was ~1, the chains taking the toma

The predicates of applicability of correlation rules in forming situational structures are formed in the course of education with the help of notion genera­ lization rules. The use of a pseudophysi­ cal situation-describing language repre­ senting actual relations between the pieces anables the situations to be clas­ sified on the basis of their structural generality.

The term "structural generality" as used in forming a generalized model of a chess endgame is defined as a determi­ nation of identical relations between the pieces in different changing specific conditions. Thus, the given position cab be assigned to a particular class and one or another approach can be employed to describe it.

To illustrate, if two totally different positions of the same pieces such as

1.1hite Nf1 2.White Na2 Black B e?,B c4,K h6 Black B b8,B d~, K e?

are considered, a generalized notion · .t, - - J. .t. - .~ LOot /i ~ (X.J~ ~ ~f6 Xt; 4 )A (.XJ.c "l.JI T..J&-"fM)/1 II ( v:t - - v.t. ) /\.JIC "t,N "tJI ..o;.t,/ o

is established between the pieces which is independent of both the position of pieces and dimensions of the chessboard (number ot fields in the chessboard). The .most important condition here is the recogni­ tion of indentical relations in a set of different positions.

The psychological esperimental results have corroborated an important fact that the higher the qualification of a chess-player, the taster he can discover these relation and find the optimum solution variant.

When formed, the generalized notion structure enters the "Decision-making"

block which, in turn, verifies that the structure is introduced into the lett part of decision-making ru.l.es. In this condition is satisfied, a decision is made in the right of the rules.

The following rule can be applied tor the above example&

that is ''Knight attacks black King and black black-field Bishop in three halt­ moves".

There are about 50 rules of this kind in the language of the generaliza­ tion of situations.

.lt an initial stage of education, these rules proved to be essential since they included, among other t~s, such important chel6 notions as "fork , "pin",etc · .l model of the extrapolation ot situations is formed from the aodels of description and generalization of situ - at ions.

The solution of the problem with the aid of the extl'apolation model is effected as follows: a situation is held on the input of the extrapolation aodel;situation class is deteratned; an action is selected which is consistent with the class and transformation of situations is accomP­ lished. The above procedure is repeated tor a new situation, etc.

An extrapolation tree is constructed in a general case. The best branch is selected on the basis of the specified criterion. One ot the basic criteria in constructing the decision-making model is the detection of the routes of activiza­ tion and safety of one's own chessmen in the course of extrapolation and also the routes of minimizing the mobility of the opposite nUIIlber' s chessmen. This process is effected in the block "Optimization of collllllaDding decisions". The condition tor a halt is the assigument of the extrapola­ tion result to a specified class.

It can be seen that the endgame problems under study are constructed by a model based on a semiotic language which contains the means to simulate the process tor the formation, generalization and extrapolation of the situations.

It is hoped that the correlations between psychological experiments and the evidence being currently obtained by a Kinsk-~2 electronic computer will permit the proposed method to be successf'lllly realized in working chess problems.