ZX Format #05 11 декабря 1996

Программирование

Programmers - artificial intelligence in computer games.

ARTIFICIAL INTELLIGENCE

     In computer games.

music by DNK
(C) Stas Vikhrov 1996.



   Today I want to talk about
artificial intelligence (AI) in
computer games. Unfortunately
During the last 10 years in this area, little has changed. The 
games developed graphics, sound, all sorts of effects, but the 
AI ​​is still not very developed. Even, in my opinion, than

better design of the game so, usually, it is weaker than the 
intellect. 

   Usually games are built on confrontation and the player 
program. For example, the player controls a little man, a tank 
car or anything else, and the program attacking players all 
sorts of objects. In games of this type Intelligence is often 
completely absent, all the attackers objects appear in the same 
places and move to a predefined programmed trajectory,

best gun shoot
randomly. Passage
such games is reduced to the memorization of that which will 
fly and where to fly. Games of this type, with a complete lack 
of intelligence, the foundation software for 8-bit game 
consoles. Think Examples of such games do not give a

necessary. Sometimes in these games starting position forwards 
objects given randomly, but it's not intelligence, because the 
attackers did not associated with the actions of the player.


   The first signs of AI observed in games like GOLD, EAGLES 
NEST and the like, where the attackers are moving as follows: 
knowing coordinates of the player they are moving

left or right, trying to equalize its horizontal coordinate 
horizontal coordinate with the player, after the coordinates 
will be equal or further progress in this direction

becomes impossible, they begin
compare their vertical coordinates coord. player if
this is not possible, the attacker
object stops. More
cunning AI in games like LODE RUNNER, PACMAN. Also often
algorithm is used when an attacker tries to get closer to the 
object coordinates of the player's which he was a few moves

ago.

    The creators of strategic
games, with rare exception, are trying to replace the 
intelligence of the program force. A typical example such games 
may be playing ZULU WAR: In her whole strategy is that all the 
Zulus crowds rod in general, only

Sometimes, if there be any regiment, attack him. But to beat 
the computer does not simply because for every soldier has ten 
Zulus. 

   But the greatest interest
of AI represent games
which forces the player and computer
equal: it may be card
games, chess, some strategic game, and most board games. All 
these games can be divided into two categories: games, where 
there is a formula or simple Provo, which can be determine the 
course and play, in which not or have not yet found such

rules. As an example of the first kind of games can bring the 
game "21 matches", there is always the second player wins if 
the following rules: if the first player takes 1 match, then we 
must take two matches, but if the first player takes two 
matches, we have to take a match. Knowing This rule can be 
composed program, which will always be

win. But these games a little bit
and they are all rather primitive.

   Besides logic games
can be divided into games where there is an element of 
randomness and games in which everything depends

only on the player. Element of chance is usually achieved
by throwing dice or, say, due to the fact that it is not known 
enemy positions. A classic example of games where there is an 
element of randomness may be virtually all card games, where 
the unknown order of the cards in the deck and the cards of the 
opponent. 

   Consider for example a simple card games, such as
point. Briefly recall the rules: each card has dostoinstrvo
from 3 to 11. The purpose of the player to collect
from 16 to 21 points, the more the
better if the player is gaining
more than 21, then he loses. In
Each player is given 2 cards and it can, if
wants to take a few more cards
from the deck. For example, I will
use the BASIC language with elements
some algorithmic language. I also advise you to develop their 
algorithms using BASIC on the following reasons: it is easy to 
find errors everywhere you can insert an operator

PRINT and keep track of intermediate results, program text
fairly obvious, the algorithm
can develop in parts
In addition, if compiling
Use only whole and not
more than 255 numbers, then this algorithm can easily be 
translated into ASSEMBLER or compile integer BASIC compiler. 
Transfer algorithm ASSEMBLER should be only after a full debug.


   The most simple algorithm, which implements the game of 
"Asshole" is as follows. 

10 LET A = SCORING
20 IF A <18 THEN TAKE THE CARD: GO
TO 10


   As you may have guessed,
SCORING is a function that considers the amount of merit
cards that are in the hands of
computer and take a card is
procedure, which carries
take a card from the deck. But if
player to guess what rule is the computer, it will
often win. Replace
constant variable.

10 LET M = 16 + INT (RND * 3)
20 LET A = SCORING
30 IF A <M THEN TAKE THE CARD: GO TO
20


   This algorithm will be playing
stronger, well, if not stronger,
then at least more cunning.

  How else to enhance the algorithm?
Here we must recall that the algorithm
written for a computer and what to do
such cases, people.

10 LET A = PODACHET POINTS
20 IF A + NEXTCARD <22 THEN TAKE
CARD: GO TO 10

 where NEXTCARD function that
calculates the dignity of the next card in the deck. In addition
You can even take into account the number of
glasses, which already has an opponent.

10 LET A = SCORING: LET
B = SCORING THE ENEMY
20 IF A  3 THEN GO TO
1050

1040 FOR B = 0 TO 3: IF A (X, Y + B) = D
THEN LET S = 0: GO TO 1050
1045 IF A (X, Y + B) = C THEN LET
S = S +1

1047 NEXT B
1050 IF S> SM THEN LET SM = S
1060 LET S = 0: IF X> 4 THEN GO TO
1100

1065 FOR B = 0 TO 3: IF A (X + B, Y) = D
THEN LET S = 0: GO TO 1100

1070 IF A (X + B, Y) = C THEN LET
S = S +1: NEXT B

1080 LET X1 = X + B: GO SUB 2000: IF
Y1 <> Y THEN LET S = 0: GO TO 1100

1090 NEXT B
1100 IF S> SM THEN LET SM = S

1110 LET S = 0: IF X> 4 OR Y> 3 THEN
GO TO 1200

1120 FOR B = 0 TO 3: IF A (X + B,
Y + B) = D THEN S = 0: GO TO 1200

1130 IF A (X + B, Y + B) = C THEN LET
S = S +1: NEXT B

1140 LET X1 = X + B: GO SUB 2000: IF
Y1 <> Y + B THEN LET S = 0: GOTO1200
1150 NEXT B

1200 IF S> SM THEN LET SM = S

1210 LET S = 0: IF X <4 OR Y> 3 THEN
GO TO 1300

1220 FOR B = 0 TO 3: IF A (X-B,
Y + B) = D THEN S = 0: GOTO 1300

1230 IF A (X-B, Y + B) = C THEN LET
S = S +1: NEXT B

1240 LET X1 = X-B: GO SUB 2000: IF
Y1 <> Y + B THEN LET S = 0: GOTO1300

1250 NEXT B

1300 IF S> SM THEN LET SM = S

1310 NEXT Y

1320 NEXT X

1330 RETURN

2000 LET Y1 = 1; routine

2005 IF A (X1, Y1) = 0 defines
THEN RETURN; the first blank cell
            ; Ku in X1 th column.
2010 LET Y1 = Y1 +1: IF Y1 = 8 THEN
RETURN

2015 GO TO 2005


   This is a slow, but most
the exact procedure for calculating
power position. It can be done
faster, replacing, for example,
line at 1030 IF A (X, Y) <> C
THEN GOTO 1300, but in this case
drop precision.

   Then perform the search of all
moves to start a 2 ply.
For each option, consider the position of power with respect to 
each color. The results of calculations put it in an array (7, 
7, 2). 

100 FOR M = 1 TO 7
110 LET X1 = M: GO SUB 2000
120 IF Y1 = 8 THEN FOR B = 1 TO
7: LET B (M, B, 1) = 5: NEXT B: GOTO
240
125 LET A (M, Y1) = 1
130 FOR N = 1 TO 7
140 LET X1 = N: GO SUB 2000
150 IF Y1 = 8 THEN GO TO 210
160 LET A (N, Y1) = 2
170 LET C = 1: GO SUB 1000: LET B (M,
N, 1) = SM
180 LET C = 2: GO SUB 1000: LET B (M,
N, 2) = SM
190 LET X1 = N: GO SUB 2000
200 LET A (N, Y1-1) = 0
210 NEXT N
220 LET X1 = M: GO SUB 2000
230 LET A, (M, Y1-1) = 0
240 NEXT M


   Lines 110, 120, 140, 150
look for in order not to install a chip in the completed 
column. Line 125 sets, and 220, 230 Uberall chip first

color analogochno line 160,
190, 200 for the second color.
Lines 170, 180 fill the array
In (7, 7, 2) by iterated
positions for each color.

   After you run this program in an array (7, 7, 2) is
all information to determine
best move, it only remains
process. We organize an array of
C (7), it will put the priorities of each move. Highest 
priority is 1 and the minimum 200. 

300 DIM C (7)
310 FOR B = 1 TO 7: IF B (B, 1, 1) = 4
THEN LET D (B) = 1
320 NEXT B
330 FOR M = 1 TO 7
340 FOR N = 1 TO 7
350 IF C (M) = 0 THEN IF B (M, N,
2) = 4 THEN LET C (M) = 199
360 NEXT N: NEXT M
370 FOR B = 1 TO 7: IF B (B, 1, 1) = 5
THEN LET C (B) = 200
380 NEXT B
383 FOR B = 1 TO 7: IF C (B) <> 0
THEN GO TO 398
385 LET X = 0: FOR M = 1 TO 7: IF B (B,
M, 1) = 3 THEN LET X = X +1
390 NEXT M
395 IF X = 7 THEN LET C (B) = 2
398 NEXT B
400 FOR B = 1 TO 7
410 IF C (B) <> 0 THEN GO TO 510
415 LET X = 0: LET Y = 0
420 FOR M = 1 TO 7
430 LET X1 = B (B, M, 1): LET
Y1 = B (B, M, 2)
440 IF X1 = 3 THEN LET X1 = 10
450 IF Y1 = 3 THEN LET Y1 = 10
460 IF X1 = 2 THEN LET X1 = 4
470 IF Y1 = 2 THEN LET Y1 = 4
480 LET X = X + X1: LET Y = Y + Y1
490 NEXT M
500 LET C (B) = X-Y +100
510 NEXT B
520 LET BEST = 0: LET X = 200
530 FOR B = 1 TO 7
540 IF C (B) 
that ... to home?
Probably he had accidentally clicked on
some secret switch
since opened squeaky
closet door, revealing for a
staircase leading to the hopeless darkness of the cave. The 
first thing that said Dorothy, descending

down, it was stolen by Toto.
Seeing him, Dorothy from all
Heart kissed Robin, and hurried to his four-footed
other. After a while Dorothy she said:
"Well, it's time to see the Wizard
Emerald City. Bye! - And
quickly ran away.
But Robin and others friends were at a loss about what to 
become of the same train ticket, bought at the railway station. 

   Whatever it was, the only place in this part of the forest,
where they were not, was the house of Grandma's Blood Cap.
- Something I'm afraid to go -
said Robin tremulous quiet
voice. - If you beat the granddaughter
crowbar Wolf, one can imagine
imagine what it is capable of
grandmother.
- Hey, Robin, you also have
white flag - said the little
John - so its something Grandma should
notice. You look, and not with a crowbar
You will beat it, and pan, for example.
- Thanks, reassured - retorted Robin, but still took the white
flag in his hands, and went to the house. As
Ironically, he was still alive.
Walls of the house were riddled with bullets, hanging down 
shutters, window frames were shot to pieces,

windows was not in sight. Through
crack in the wall on the street leaning out a large anti-
gun. In a wheelchair sitting
Grandmother, wrapped with grenades and
large-caliber ammunition.
- You're lucky that I saw
white flag - giggled Grandmother
and sipped a hefty swallow from
bottles filled with pure
alcohol.
- The only way I realized that you do not
electrician, who came off
electricity for nonpayment.
She opened her chair, pulled up to the window and pulled out 
from the pack "Belomor" cigarette.

- By the way, rumor has it - the beginning
She lit a match - that Moriarty returned to Cher ... - There 
was an explosion. When the smoke cleared, nothing could be 
found. Do not have survived even the chair.

- Moriarty? - With horror in his voice
Nazir said.
- It's time we visit the Harn -
said Robin.
# No sooner said than done. Road
passed through a magical place
- Circle of Druids. A lot of things said about him. Some have 
argued that it is an evil place, others - that

good. Rate as had Robin. In the center of the Circle of Druids
rose sosiskopodobny obelisk on top of which stood
mystical ancient and no longer working coffee maker. So nothing
without waiting for the obelisk to be
perhaps because of them not
it was the druids, the company moved
further.

   Parking EnSiPi was empty.
Randomly scattered around the room
machines for ticket sales is not
worked, and fluorescent lamps that are protected from 
encroachment Vandals, sly twinkle.

The floor was clean and waited for the used tickets. There was 
silence. - No one here, - has noticed

Will.
- It's obvious - said Robin.

   Nearby is the toilet.
On the wall was read the inscription: "Pay Toilet. 10 pence - 
15 minutes and no more!" - Wait for me here, - said

Robin, dropped in the slot 10 pence,
opened the door and entered. But! This
was not an ordinary toilet. This was
WC-teleportator went into that Robin dematerialized and
a few seconds later materialized again. Like all
was in place, and Robin came out in a totally unfamiliar
place. Whether the toilet was working properly, then there was 
still any reason, but through the window to return the coins 
fell spent desyatipensovik. - It may be still be able to go 
somewhere to get - thought Robin but materialized again, he

realized that he had fallen back there,
where there was parking nearby EnSiPi. Having gone a few times 
here and there, to Robin finally realized that more to get 
anywhere using the toilet will not succeed. Had to walk.


   Suddenly, the woods come alive. Fierce
the type of trees teamed
some unknown way,
caught near standing
humble woodcutter and dragged
into the bushes. Muffled screams were heard from there and 
quickly subsided. 

   Soon they reached the cottage Harney. Opposite him stood
Another barn was empty. Cottage was two stories.
He was surrounded by a lot of fun
small bushes, and inviting to approach them, but none
did not do this, mindful of the woodcutter. Still trying to get 
inside the cottage success is not unsuccessful.

- It would be nice to find the owner,
maybe he will hold us
inside - suggested Nazir.
- Harn? Well let's go find him.
Going a little further, travelers once again saw the barn.
That something was not empty.
Inside lay an empty packet
inscription "Megavzryv. Strong laxative.
- Goldilocks obviously could not shove here package - suggested
Robin. - So she is innocent.
And now let us return to our sheep, I mean, I wanted to say
to the Three Bears.
And the whole company hurried to the above ba ... bears.
Suddenly, Little John stopped.
- What is it? - Asked Robin.
- Look ahead Harn, - he answered.
- Nothing, now count up the hose and talk to him. Perhaps
even learn something.
- Good day, Harn.
- Hi, idio ... I mean, you idiot, I did not recognize you
immediately. Hi, Robin.
- Harn, you accidentally do not know
what happens in the woods?
- You ask me, well known for his loud affairs Mori ... I wanted 
to say, the sea of ​​questions you ask me about any nonsense, 
Robin. - Do you know whether Harn, a lot of things

happened recently.
How are you things with an alibi?
- Uh, you know, Robin, my
the forest was not there when it all happened - Harn noticeably 
nervous. - Well, Harn, I must go.

- Go, go, that is, so far! -
Harn said with obvious relief.
- I do not understand how, hopefully,
and you, - said Robin, when they
moved away.
- All of these tucked Harn, or
I suspect that Moriarty, who managed to somehow
cheat and substitute Harney. I would
though now called Lestrade.
But he immediately pulled me with
searches in the cottage Harney, and then
I do not have time to the Three Bears.

   Well, the house where they cook
take heroic death Goldilocks. She stood on a stool
with a noose around his neck, and the Bears already
preparing to send its first
voyage to another world.
- Stop! - Cried Robin, and
everyone looked at him.
Then he got a package from the
laxative, showed him three
Bears and said, in what
circumstances he found it.
Soon Goldilocks was sent home and the Bears themselves are gone
the corner and never returned.
- It's time to call Lestrade, - said Robin, taking out his 
wireless phone. 

   Soon the police broke into the
Cottage Harney, and with it
got there and Robin.
- Well, - said Inspector Robin,
- I think you would be better to look around and then come to 
me with answers to questions. And do not stop

as the obelisk.

   The first floor is
kitchen, dining room and veranda. From
All the three rooms most interest was food. She
was fitted to the last
art. Black mikrodrayvovaya stove, preparing the usual
sorokavosmikilobaytny dinner for
nine seconds, quietly humming in the
one corner, while the dishwasher EmEsIks quite noisy rustling 
in the other. 

   The second floor was
bedroom Harney, in its southern wall
There was a door. Robin opened it, and
from the mist, mysterious lights rastsvechennogo, fell to
floor tightly bound figure Harney.
- Moriarty took my place and began to corrupt the entire forest 
- slurred and mumbled quickly

this Harn. All attempts
pull it down ended
failed, so Robin had to go himself.
- Well, what does it all mean? -
asked Lestrade.
- It's elementary, Lestrade -
said Robin.
- Moriarty stole Harney.
- Well done - said
Lestrade, after Harn
was unleashed.

   Thus, the incident was over.
However, it is also true that Moriarty later escaped and 
disappeared from forest. Maryann arrived, and then

She and the rest went into a tavern to meet all
their desire remained unsatisfied for
throughout this epic. So ended the episode in the life of Robin
Sherlokskogo.