ZX Format #06 29 июля 1997

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

Программистам - Искуственный интеллект. Продолжение цикла статей об "AI". Общие основы нахождения пути к цели.

ИСКУСТВЕННЫЙ ИНТЕЛЛЕКТ
     В КОМПЬЮТЕРНЫХ ИГРАХ
        (продолжение)

music by DNK
(С) ВИХРОВ СТАС 1996.
_______________________________

  Недавно, играя в "SPACE CRUSADE", я об-
наружил  странную  деталь:  на  одном  из
уровней надо уничтожить отряд десантников
хаоса,  который топчется на одном месте с
непонятными целями, вместо того чтобы по-
пытаться  напасть  на отряд игрока. Такая
тупость мне не понятна: умея пользоваться
современными видами оружия, не догадаться
приблизится к противнику.
   То  есть  задача  сводится к написанию
процедуры которая определяла бы направле-
ние  в  котором  надо сделать шаг, что бы
приблизится  к нужному объекту (для лаби-
рината любой сложности).
   Пусть  у  нас  есть  массив A(100,100)
элементы  которого  соответствуют клеткам
лабиринта:  1-стена, 0-пусто, 2-клетки до
которых нужно добраться (для игры SP.CRU-
SIDE  это  клетки, с которых можно произ-
вести  выстрел  по  противнику), лабиринт
окружён стеной, для простоты перемещаться
можно только вертикально и горизонтально.

Входные данные процедуры - X,Y - теку-
   щие координаты.
   Выходные  данные  -  X,Y  - координаты
   после перемещения.

 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
9 180 IF A(X1-1,Y1)=2 THEN LET A(X1,Y1)=2: LET N=N+1 
9 190 IF A(X1+1,Y1)=2 THEN LET A(X1,Y1)=2: LET N=N+1 
9 200 IF A(X1,Y1-1)=2 THEN LET A(X1,Y1)=2: LET N=N+1 
9 210 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

Эта  процедура действует следующим об-
разом:
строки  100  - 130 проверяют соседние
от  десантника клетки, и если они равны 2
то делается ход в их сторону,
строки 150 - 230 отвечают за "распол-
зание"  двоек  по  лабиринту; по значению
переменной  N определяется, сколько двоек
прибавилось за данный цикл, если двоек не
прибавилось, то это означает, что распол-
заться двойкам уже некуда, и добраться до
нужного  объекта  десантнику  не  удастся
(строка  240).  (  Аналогичную  процедуру
можно  сделать  и  с помощью рекурсии, но
тогда она будет медленнее работать, и за-
 нимать больше памяти в стеке ).
   Для игры SP.CRUSADE можно написать та-
кую программу перемещения десантника хао-
са:

  05 LET HOD=5 
  10 ОБНОВИТЬ ЭКРАН: ОБНОВИТЬ МАССИВ
6  20 IF A(X,Y)=2 THEN СТРЕЛЯТЬ: ОТСТУПАТЬ : RETURN
  30 GO SUB 100 
  40 LET HOD=HOD-1
   50 IF HOD>0 THEN GO TO 10 
  60 RETURN 

  Конечно для динамических игр такой спо-
соб  не  подходит,  но для стратегических
(после  перевода  на  ассемблер)  быстро-
действия вполне хватает.

Но  это  было,  так сказать,лирическое
отступление  от основной темы, поднятой в
прошлом номере журнала.
   Итак,  выделим  основные  блоки ИИ для
игр шахматного типа: Прежде всего в любой
программе  ИИ должна быть формула опреде-
ления  силы  позиции,  процедура проверки
соответствия хода правилам игры, програм-
ма, обеспечивающая перебор всех возможных
ходов  на  нужное  количество полуходов в
глубину и  помещающая силы всех возможных
позиций в массив, программа которая обес-
печивает  обработку  данного массива и на
основе полученых даных  определяющая луч-
ший  ход. Особое внимание следует уделить
формуле определения силы позиции, её надо
сделать максимально точной и быстрой, так
как  если  она будет хоть и быстрой но не
точной, то не будет смысла делать перебор
ходов  на  большую  глубину  ( потому что
ошибка формулы будет увеличиваться с каж-
дым  полуходом ), и в итоге на основе та-
кой  формулы  не удастся сделать сильного
ИИ.  Предпочтительнее сделать медленную и
точную  формулу,  но с небольшой глубиной
перебора.
   Далее  один  из  самых важных моментов
при  создании ИИ - это способ по которому
определяется  лучший  ход исходя из полу-
ченного массива, содержащего данные,полу-
ченые  при  переборе  позиций.  Тут может
быть  много  способов для каждой логичес-
кой  игры.  Например  (для  некоторой на-
чальной позиции в логической игре), после
перебора  весх  возможных  позиций на два
полухода  в глубину и вычисления их сил с
помощью  некоторой формулы заполняем мас-
сив А(n,n) (для реверси n=64=8*8) в кото-
ром элемент А(x,y) содержит силу позиции;
позиция  получена  после  хода  "белых" в
клетку  поля, обозначенную x и хода "чер-
ных"  в  клетку  поля обозначенную y (яс-
но,что  для реверси большинство элементов
массива будет заполнено нулями,так как не
все  возможные  ходы соответствуют прави-
лам).Выбирать  "лучший  ход"  из  данного
массива можно несколькими способами (при-
чем  для  разных  способов  "лучший  ход"
обычно  будет разным).Вот нескольно таких
способов:
,1.Найти в массиве наибольшее число и при-
нять  за  "лучший  ход" первую координату
Eэтого числа.
2.Найти в каждом столбце наименьшее число
(ноль  не учитывать) и принять за "лучший
ход"  номер  того столбца, где наименьшее
число наибольше.
3. Принять  за  "лучший  ход"  номер того
столбца  у  которого сумма элементов наи-
большая.
   Как  видите, способов определения луч-
шего хода придумать можно достаточно мно-
го  (для более чем двумерного массива всё
ещё  сложней). Причем для разных логичес-
ких  игр лучше подходят и разные способы,
в зависмости от особенностей данной игры.
Поэтому я могу лишь посоветовать при сос-
тавлении  своих програм побольше экспери-
ментировать с разными способами определе-
ния лучшего хода и выбрать самый сильный.
   Запишем программу искуственного интел-
лекта  в  общем  виде.  (компьютер играет
"белыми", расчет ведется на глубину 4 по-
лухода)

  10 DIM A(N,N,N,N) ;N-максимально возможное количество ходов
;  20 FOR  A1=1 TO N ; которые можно сделать из 1 позиции
;  21 IF ХОД "БЕЛЫХ" НА КЛЕТКУ А1 НЕ СООТВ.ПРАВИЛАМ THEN
      GOTO 131
  22 СОХРАНЯЕМ ПОЗИЦИЮ В МАССИВЕ Б1 
  23 ХОДИМ "БЕЛЫМИ" НА КЛЕТКУ А1. 

  30 FOR A2=1 TO N
<  31 IF ХОД "ЧЕРНЫХ" НА КЛЕТКУ А2 НЕ СООТВ.ПРАВИЛАМ THEN
      GOTO 121  
  32 СОХРАНЯЕМ ПОЗИЦИЮ В МАССИВЕ Б2 
  33 ХОДИМ "ЧЕРНЫМИ" НА КЛЕТКУ А2.

  40 FOR A3=1 TO N
<  41 IF ХОД "БЕЛЫХ" НА КЛЕТКУ А3 НЕ СООТВ.ПРАВИЛАМ THEN 
      GOTO 111
  42 СОХРАНЯЕМ ПОЗИЦИЮ В МАССИВЕ Б3 
  43 ХОДИМ "БЕЛЫМИ" НА КЛЕТКУ А1. 

  50 FOR A4=1 TO N
<  51 IF ХОД "ЧЕРНЫХ" НА КЛЕТКУ А4 НЕ СООТВ.ПРАВИЛАМ THEN
      GOTO 101
  52 СОХРАНЯЕМ ПОЗИЦИЮ В МАССИВЕ Б4 
  53 ХОДИМ "ЧЕРНЫМИ" НА КЛЕТКУ А4.

  60 LET A(A1,A2,A3,A4)=СИЛА ПОЗИЦИИ

 100 ИЗВЛЕКАЕМ ПОЗИЦИЮ ИЗ МАССИВА Б4
 101 NEXT A4

 110 ИЗВЛЕКАЕМ ПОЗИЦИЮ ИЗ МАССИВА Б3
 111 NEXT A3

 120 ИЗВЛЕКАЕМ ПОЗИЦИЮ ИЗ МАССИВА Б2
 121 NEXT A2

 130 ИЗВЛЕКАЕМ ПОЗИЦИЮ ИЗ МАССИВА Б1
 131 NEXT A1

На  данный  момент  мы получили массив
А(N,N,N,N), который  содержит  силы  всех
возможных  позиций  на глубину 4 полухода
начиная от данной.

200 ПРОГРАММА ОБРАБОТКИ МАССИВА И ОПРЕДЕЛЯЮЩАЯ ЛУЧШИЙ ХОД.

  По  такому принципу, с некоторыми отли-
чиями,  строится большинство программ ис-
пользующих  ИИ;  эти  отличия  в основном
заключаются  в различных способах сэконо-
мить память или время рассчета, например,
за счет неполного перебора позиций.

 ( продолжение следует ) 
_______________________________