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)
_______________________________
