________________ _____ ________ __ \ | o/ o\ (_____) o\ __ |__| \ | / \| o| \ |__| __ \ / | \ | | / __ |__| \___/\_________/_____|________/ |__| = N E T W O R K S = ---------------------------------------------- = AI applied to games by NT rev1.4 20/11/2K1 = ---------------------------------------------- http://void.box.sk One of the first games was chess. Studying those games lead to developing a lot of ways to process the best move and the possible moves. Now you can play chess in a higher level of difficulty since those programs are getting more 'inteligence'. 'Go', 'Chess', 'Shogi' are games where two players participate, alternatingly, and they don't have any element of luck. A simple example of those games is tic- tac-toe. In it participates two players, who alternatingly make marks in a tray of 3x3. If the marks made by one of the two players is a string, horizontal, vertical or diagonal direction, this player is the winner. An example is shown below of starting a game : _|_|_ _|_|_ _|_|_ x|_|_ x|_|_ x|_|x x|_|x x|x|x _|_|_ _|x|_ _|x|o _|x|o _|x|o _|x|o _|x|o _|x|o | | | | | | | | | |o | |o o| |o o| |o Start (1) (2) (3) (4) (5) (6) x wins The tic-tac-toe game finishes when one player wins or when all the spaces will have been filled (what it would be equivalent to tie up to). Let's name the players A and the B, the main purpose of A will be the victory for himself, being the secondary purpose drawing the game. Thus, in this example, it will be more convenient to give a description of the final state of the problem that to specify it concretely. The state of the game can be expressed by the positions of the marks in the tray and specifying who's going to play. It is easy to see, looking the position in the tray, who is going to play, but this is not applied necessarily in the case of games as Go or Shogi. You will have to also notice in the case of the ' Shogi ' the captured parts, and in the case of the Go, the number of captured rocks, they must be included when the state of the game will be specified. The total number of possible combinations of plays, in tic-tac-toe is lesser of 9! (9!=362880). However in the majority of the games for adults, more than 10^100 possible cases exist, for that it is impossible to examine all of them. The move to play has, therefore, as general rule, of being determined using one any normalized form of evaluation. *** Status description Already an explanation on what was given we understand for problem state, but is equally important to consider as one such state will have to be described. The state of 'puzzle-8', for example, consists of the array of parts. This can be made by computer in some ways, from which will have to choose the description that more to adjust itself to the resolution of the problem. Let us assume that the method we selected for the description of the state of 'puzzle-8' consists on specifying the positions of each one of the parts. For each one of them, numbered 1 the 8, we store the line numbers and column of the position of the part. Such description has, really, a correspondence of one-to-one in relation to the position of the parts, representing the good state. However, it is very inconvenient for the resolution of the problem. In first place, it is not easy to know which parts can be moved. For moreover, one becomes difficult to have a good ideia of the pattern of the tray. As alternative description, let us consider an array of 3x3. The array elements will represent spaces in the tray, to which will be attributed the numerical value of 0, in case that a part in this space does not exist; or, if it exist a part in this space, it will be attributed the number of the part. This description is very similar to the state itself and is also easy to see which the parts that can be moved, and where they can lead. It is obvious that this description is more adjusted than the previous one. We will now approach the problem of the labyrinth, argued in the previous text. In this in case that, the problem is the position of the person. For example, when the person arrives at the interception (2, 4), (2, 4) it is the description of the state. Since the passage of the map, initially given, don't change, it is not necessary to describe of each time the state changes. It is not obligator that the description of the state corresponds exactly to the real state. Let us see a simple problem, that involves tablets. Such as shows below in this figure, the purpose is to build a tower on a base, using tablets. _ (*) |A| _ |_| |A| => |B| |_| _ |_| |C| |B| |C| __|_|_|_|__ __|_|__ Start Final State In this case, the position of the tablets in three-dimensional space is not very important; the problem is related between the base (TABLE) and the other tablets. If we to express the relationship for ON(u, v), such that the u object is on v, and represent the base with TABLE, the above figure can be represented in the following way : ON(A,C) ON(A,B) ON(B, TABLE) => ON(B,C) ON(C, TABLE) ON(C, TABLE) Such description of states is not a necessary representation of the positions of the tablets; but, if this operation had to be executed through one robot equipped with an eye, would be enough to specify the following steps : 1. Place A on the base; 2. Place B on C; 3. Place A on B. Thus, a description of the problem state in terms of a set of relations ON(u, v) will be enough. This example illustrates the fact of the key of the resolution of problems to be in the formularization of a description of the essential states for the resolution of problems. An operator modifies the definitive state of problem for another state of problem. Thus, an operator could be considered as a function, whose domain (input) and reach (output) are the set of states. Some forms exist to define the share of an operator, one of which consist of expressing, under the resultant form of a table, states output of all the possible states input. Example : one operator which produces the logic add (OR), from two logic vars x and y (that can be true or false), can be defined by the outputs that gives to the four possible inputs. Meanwhile, using such table isn't the best way, when the input and output stats grow. Usually one operator is defined as a process that converts a description from state data in the description to another state. The input state from one operator must satisfy some conditions, called 'preconditions'. If you have some operatores, each one of them will have their own preconditions. Let's take the puzzle-8 as a simple example. As you can see in the figure above it uses eight pieces and a 3x3 square. The purpose of the game is to reach the arrival state moving pieces, from the start state. The pieces can be moved up, down, left and right if there is an empty space. The problem state changes everytime you move a piece. The movement of one piece is the operator of this problem. ___ ___ ___ ___ ___ ___ | | 8 | 3 | | 1 | 2 | 3 | |___|___|___| |___|___|___| | 2 | 6 | 4 | ____\ | 8 | | 4 | |___|___|___| ____ > |___|___|___| | 1 | 7 | 5 | / | 7 | 6 | 5 | |___|___|___| |___|___|___| PUZZLE-8 We can define those four operators (this is about one indirect definition of the operators) : 1. Moving one piece up; 2. Moving one piece down; 3. Moving one piece to the left; 4. Moving one piece to the right; The preconditions will be : 1. The space above the piece is empty; 2. The space under the piece is empty; 3. The space at the left of the piece is empty; 4. The space at the right of the piece is empty; Since examining all pieces would take too many time, to verify if they satisfy all preconditions, before examining the operators preconditions we'll have to specify wich piece will move. We can define the operators and the preconditions as follow, if we consider the movement of one piece as being the same of the movement of empty space. Operators Preconditions 1. Move empty space up. 1. There is one space above. 2. Moving empty space down. 2. There is one space under. 3. Moving empty space to the left. 3. There is one space at left. 4. Moving empty space to the right. 4. There is one space at right. This is a better definition because it allows to easely view the preconditions. As the operators change the state, the state of the problem is determined, evidently, by the way operators are defined. Let's ilustrate those two operators : 1. Remove x; 2. Put x on y; Will have those two preconditions : 1. x is a tablet and there is nothing on it; 2. x has been removed and is is true that y is the base or there is nothing on y. To define that, the description of the states in the tablets example isn't enough. First let's write the relation with the x tablet such holding x. We introduce now CLEAR (x) to indicate that there is nothing on x, because if we have many tablets the process will be longer. The previous example (*) will now be as : ON (A, C) ON (A, B) ON (B, TABLE) ON (B, C) ON (C, TABLE) => ON (C, TABLE) CLEAR (A) CLEAR (A) CLEAR (B) The preconditions of the operators will be : 1. (x != TABLE) v CLEAR (x) 2. HOLD (x) v {y=TABLE v CLEAR (y)} Let's take a look to some code ! I choosed BASIC because it will be easy to anyone to translate it to C, C++, Pascal, ASM, etc... 10 REM ************************************************* 11 REM *** Program : Tic-Tac-Toe *** 12 REM *** Author : NT ^ L33tz/PT-Scripters/Void *** 13 REM *** Date : 04/1986 *** 20 REM ************************************************* 30 DIM I(4),J(4):T=0:CLS 40 FOR J=1 TO 3:FOR I=0 TO 2:PLOT 200+I*80,460-J*80:DRAWR 80,0:DRAWR 0,-80:DRAWR -80,0:DRAWR 0,80 50 LOCATE 14+I*5,J*5-2:PRINT RIGHT$(STR$(I*3+J),1):NEXT:NEXT:GOTO 200 60 IF T=9 THEN GOTO 760 70 LOCATE 1,20:PRINT CHR$(7);CHR$(18);"Enter a number :"; 80 A=VAL(INKEY$):IF A<1 OR A>9 THEN 80 ELSE PRINT A 90 X=INT(A/3.5):Y=A-(X*3) 100 IF P=(X+1,Y)<>0 THEN GOTO 70 110 FOR I=1 TO 360 STEP 6:MOVE 240+X*80,420-Y*80:PLOTR 18*COS(I),18*SIN(I):NEXT 120 P(X+1,Y)=1:T=T+1 200 REM 205 REM --- Computer's turn --- 210 REM 220 IF P(2,2)=0 THEN X=2:Y=2:GOTO 430 230 ERASE I,J:DIM I(4),(4):P=1:GOSUB 500 240 FOR I=1 TO 4:IF I(I)=3 OR J(I)=3 THEN GOTO 700:NEXT 250 ERASE I,J:DIM I(4),(4):P=2:GOSUB 800 260 FOR I=1 TO 4:IF I(I)=2 OR J(I)=2 THEN 280:NEXT 270 P=1 280 ERASE I,J:DIM I(4),(4):X=0:Y=0:M=0:GOSUB 800 290 FOR I=1 TO 4 300 IF I(I)=3 OR J(I)=3 THEN 700 310 IF I(I)>=M THEN X=I:Y=0:M=I(I) 310 IF J(I)>=M THEN Y=I:X=0:M=J(I) 320 NEXT 330 IF T=9 THEN GOTO 720 340 IF P=1 AND M=2 THEN GOTO 360 350 P=P+1:IF P<3 THEN 500 ELSE P=2 360 IF X=4 THEN IF P(1,1)=0 THEN X=1:Y=1:GOTO 430 ELSE X=3:Y=3:GOTO 430 370 IF Y=4 THEN IF P(1,3)=0 THEN X=1:Y=3:GOTO 730 ELSE X=3:Y=1:GOTO 430 380 IF X=0 AND Y=0 THEN X=1 390 FOR I=1 TO 3 400 IF Y=0 AND P(X,I)=0 THEN Y=I 410 IF X=0 AND P(I,Y)=0 THEN X=I 420 NEXT 430 P(X,Y)=2 440 LOCATE 1,20:PRINT CHR$(7);CHR$(18);"I play :";:PRINT (X-1)*3+Y 450 PLOT 145+X*80,435-Y*80:DRAWR 35,0:DRAWR 0,-35:DRAWR -35,0:DRAWR 0,35 460 FOR I=1 TO 2000:NEXT 470 IF P=2 AND M=2 THEN 700 480 T=T+1:GOTO 330 500 REM 505 REM --- Check --- 510 REM 520 C=0:D=0:FOR I=1 TO 3:A=0:B=0:FOR J=1 TO 3 530 IF P(I,J)=P THEN I(I)=I(I)+1 540 IF P(I,J)<>0 THEN A=A+1 550 IF P(J,I)=P THEN J(I)=J(I)+1 560 IF P(J,I)<>0 THEN B=B+1 570 NEXT J 580 IF A=3 AND I(I)<>3 THEN I(I)=0 590 IF B=3 AND J(I)<>3 THEN J(I)=0 600 IF P(I,I)=P THEN I(4)=I(4)+1 610 IF P(I,I)<>0 THEN C=C+1 620 IF P(I,4-I)=P THEN J(4)=J(4)+1 630 IF P(I,4-I)<>0 THEN D=D+1 640 NEXT I 650 IF C=3 AND I(4)<>3 THEN I(4)=0 660 IF D=3 AND J(4)<>3 THEN J(4)=0 670 RETURN 700 REM 705 REM --- Game Over --- 710 REM 720 LOCATE 1,20:PRINT CHR$(18); 730 IF P=1 THEN PRINT "You WIN" 740 IF P=2 THEN PRINT "I WIN" 750 GOTO 770 760 LOCATE 1,20:PRINT CHR$(18);:PRINT "DRAW !" 770 FOR I=16 TO 0 STEP -1:PRINT CHR$(7);:FOR J=1 TO I*I+10:NEXT:NEXT 780 LINE INPUT A$:RUN 790 END 1000 REM -------------------------------------------------------------------- 1001 REM --- Var list : --- 1002 REM --- A Player's choice --- 1003 REM --- A, B, C, D # of pions already placed in line, row, diagonal --- 1004 REM --- A$ Last pressed key --- 1005 REM --- I Used in loops FOR/NEXT --- 1006 REM --- I() # of pions in rows --- 1007 REM --- J Used in loops FOR/NEXT --- 1008 REM --- J() # of pions in lines --- 1009 REM --- M # of pions near box --- 1010 REM --- P P=1 (player) P=2 (CPU) --- 1011 REM --- P() pion position in array --- 1012 REM --- T # of pions already placed --- 1013 REM --- X and Y coordinates in the array --- 1014 REM -------------------------------------------------------------------- 2000 REM --- Program Structure --- 2001 REM --- 30-60 Setup and board display --- 2002 REM --- 60-120 Player's move (if T=9 then the game is over, input --- 2003 REM --- move, 80 to 100 verify if it is possible to move, --- 2004 REM --- 110 prints pion) --- 2005 REM --- 220-480 CPU move (220 to 240 check if player wins using the --- 2006 REM --- check routine (500) to count the # of pions in each --- 2007 REM --- line, row or diagonal, 250 to 320 the same above for --- 2008 REM --- the CPU »» »»» To be continued... (c) NT / 2001 - for the VoiD Networks Team - void.box.sk