Programmers - Artificial Intelligence. Continuation of a series of articles about "AI". General basis for finding the way to goal.

<b>Programmers</b> - Artificial Intelligence. Continuation of a series of articles about

Artificial Intelligence

     In computer games

        (Continued)

music by DNK
(C) vortices STAS 1996.
_______________________________


  Recently, while playing "SPACE CRUSADE", I discovered a 
strange detail: one of levels necessary to destroy airborne unit

chaos that marks time in one place
unclear goals, instead of trying to attack a squad player. Such
stupidity I do not understand: being able to use
modern weapons, not to guess
close to the enemy.

   That is the problem is reduced to writing
procedures that would determine the direction in which we must 
take a step that would closer to the desired object (to 
labirinata any difficulty). 

   Suppose we have an array A (100,100)
elements of which correspond to cells
maze: 1-wall, 0-empty, 2-cell to
which need to get (to play SP.CRUSIDE the cells from which we 
can make a shot at the enemy), a maze surrounded by a wall, for 
ease of travel You can only vertically and horizontally.


Input procedure - X, Y - current
   ing coordinates.

   Imprint - X, Y - coordinates

   after the move.

 100 IF A (X, Y) = 2 THEN RETURN
/ 105 IF A (X-1, Y) = 2 THEN LET X = X-1: RETURN
/ 110 IF A (X +1, Y) = 2 THEN LET X = X +1: RETURN
/ 120 IF A (X, Y-1) = 2 THEN LET Y = Y-1: RETURN
/ 130 IF A (X, Y +1) = 2 THEN LET Y = Y +1: RETURN
 140 LET N = 0
 150 FOR X1 = 2 TO 99
 160 FOR Y1 = 2 TO 99
 170 IF A (X1, Y1) <> 0 THEN GO TO 220
9180 IF A (X1-1, Y1) = 2 THEN LET A (X1, Y1) = 2: LET N = N +1
9190 IF A (X1 +1, Y1) = 2 THEN LET A (X1, Y1) = 2: LET N = N +1
9200 IF A (X1, Y1-1) = 2 THEN LET A (X1, Y1) = 2: LET N = N +1
9210 IF A (X1, Y1 +1) = 2 THEN LET A (X1, Y1) = 2: LET N = N +1
 220 NEXT Y1
 230 NEXT X1

   240 IF N = 0 THEN RETURN
 250 GO TO 100

This procedure works as follows:
Line 100 - 130 check the neighboring
by commando cells, and if they are equal to 2
a move is made in their direction,
Line 150 - 230 are responsible for "spreading" of deuces on the 
labyrinth, by value variable N is determined by how many pairs

were added during this cycle, if the twos are not
increased, it means that sprawl deuce at the bottom and get to
desired object paratrooper fail
(Line 240). (A similar procedure
can be done using recursion, but
then it will be slower to work and takes more memory for the 
stack). 

   For the game SP.CRUSADE can write a program displacement 
Chaos Marines: 


  05 LET HOD = 5

  10 to update the screen: UPDATE ARRAY
June 1920 IF A (X, Y) = 2 THEN SHOOT: DEVIATES: RETURN

  30 GO SUB 100

  40 LET HOD = HOD-1

   50 IF HOD> 0 THEN GO TO 10

  60 RETURN


  Of course for dynamic games this way is not suitable, but for 
strategic (After translation to assembler) performance is quite 
enough. 

But it was, so to speak, lyric
digression from the main themes raised in
the last issue of the magazine.

   Thus, we extract the basic building blocks for AI
games such as chess: First, in any
AI programs should be the formula for determining the position 
of force, the verification procedure compliance with the rules 
of the game, a program that iterates through all possible moves 
to the desired number of plies in depth and put the forces of 
all possible positions in an array, a program that provides 
processing of the array and the basis of danyh determining the 
best move. Particular attention should be paid formula for 
determining the position of force, it must be make the most 
accurate and rapid, so as if it will even and fast but not

accurate, it would not make sense to bust
moves to a greater depth (because
error formula will increase each ply), and eventually on the 
basis of such a formula will not be able to make strong AI. 
Preferable to a slow and exact formula, but with little depth

busting.

   Further, one of the most important moments
Made of AI - is the way in which
determined the best move based on the resulting array 
containing the data obtained with the brute positions. There 
may be many ways for each logic game. For example (for a 
starting position in the puzzle game), after iterate vesh 
possible positions for two ply in depth and calculate their 
forces from the using a formula fills the array A (n, n) (to 
reverse n = 64 = 8 * 8) in which the element A (x, y) contains 
a power position; position obtained after the move of "white" in

cell fields marked with x and stroke "black" in the field of 
the cell labeled y (it is clear that to reverse most of the 
elements array will be filled with zeros, because they do not

all possible moves in accordance with regulations). Select the 
"best move" from a given array in several ways (and for 
different ways to "best move" will usually be different).'s 
neskolno such ways:

, 1.Nayti in the array and take the largest number of "best 
move" the first coordinate Eetogo numbers.

2.Nayti in each column, the smallest number
(Zero is not taken into account) and make a "best
progress "number of the column where the smallest
the greatest number.
3. Taken as the "best move" the number of
column whose sum of elements of the greatest.

   As you can see ways to determine the best move you can think 
of quite a lot (for more than two-dimensional array of all even 
more difficult). And for different logic games are better and 
different ways, in zavismosti on the features of this game.

So I can only advise to compile their program a little more 
experimenting with different ways to determine the best course 
and choose the strongest. 

   We write a program of artificial intelligence in general. 
(The computer plays "White", the calculation is carried out at 
a depth of 4 ply) 


  10 DIM A (N, N, N, N); N-maximum number of moves
, 20, FOR A1 = 1 TO N; that can be done from a position
: 21 IF PROGRESS "white" on the cells A1 SOOTV.PRAVILAM NOT THEN

      GOTO 131

  22 SAVES position in the array B1

  23 We go "white" on the cells A1.


  30 FOR A2 = 1 TO N
<31 IF PROGRESS "Black" on the cells of A2 is not 
SOOTV.PRAVILAM THEN 

      GOTO 121

  32 SAVES position in the array B2

  33 We go "Black" on the cells of A2.


  40 FOR A3 = 1 TO N
<41 IF PROGRESS "white" on the cells A3 SOOTV.PRAVILAM THEN

      GOTO 111

  42 SAVES position in the array B3

  43 We go "white" on the cells A1.


  50 FOR A4 = 1 TO N
<51 IF PROGRESS "Black" on the cells A4 SOOTV.PRAVILAM NOT THEN

      GOTO 101

  52 SAVES position in the array B4

  53 We go "Black" on the cells of the A4.


  60 LET A (A1, A2, A3, A4) = POWER POSITIONS

 100 extracts the position SOLID B4
 101 NEXT A4

 110 extracts the position SOLID B3
 111 NEXT A3

 120 extracts the position SOLID B2
 121 NEXT A2

 130 extracts the position SOLID B1
 131 NEXT A1

At the moment we have an array of
A (N, N, N, N), which contains all the forces
possible positions on the depth of 4 ply
from this.

200 programs array handling and determines the best move.


  According to this principle, with some differences, most 
programs are constructed using artificial intelligence, these 
differences are mainly are in various ways to save memory or 
time of calculation, for example, due to incomplete enumeration 
of positions. 

 (To be continued)
_______________________________