ZX Format #06
29 июля 1997

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

<b>Программистам</b> - Искуственный интеллект. Продолжение цикла статей об
ИСКУСТВЕННЫЙ ИНТЕЛЛЕКТ
     В КОМПЬЮТЕРНЫХ ИГРАХ
        (продолжение)

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 ПРОГРАММА ОБРАБОТКИ МАССИВА И ОПРЕДЕЛЯЮЩАЯ ЛУЧШИЙ ХОД.

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

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



Другие статьи номера:

Сегодня в номере - содержание журнала.

Авторы - авторы журнала ZX-Format No.6

От авторов - свершилось давно ожидаемое событие...

Игрушки - Последний утюг (новелла по игре 48 утюгов).

Игрушки - Приключения Винни Пуха. Часть вторая.

Игрушки - описание игры The Crypt (Castle Master 2).

Игрушки - описание редактора Адевентюр - PAW (часть 1).

Игрушки - описание редактора Адевентюр - PAW (часть 2).

Игрушки - описание редактора Адевентюр - PAW (часть 3).

Игрушки - описание редактора Адевентюр - PAW (часть 4).

Игрушки - описание редактора Адевентюр - PAW (часть 5).

Программистам - Beta Basic: продолжение разговора о бейсике (часть 2).

Программистам - General Sound: Руководство по программированию.

Программистам - MMD - драйвер. Описание структуры драйвера модема для терминальной программы MMD.

Программистам - AI от В.Медноногова. Подробное описание "волнового алгоритма" трассировки (автоматического рассчета оптимального) пути, с примером реализации на Basic.

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

Программистам - Тr-Dos для программистов. Макс Петров завершает свой рассказ о нетрадиционых методах работы с диском.

Программистам - обмен опытом: "3-colour". Описание эффекта "8-цветов на точку", хелп к вьюверу и сколько слов о конвертации картинок в формат "3-colour".

Программистам - обмен опытом: "3-colour". Несколько слов о конвертации картинок в формат RGB.

Программистам - обмен опытом: программирование мультиколорных эффектов.

IS-DOS - пользователям: как выполнить индивидуальную настройку системы IS-DOS на конкретную модель ZX Spectrum-совместимого компьютера и на выполнение Ваших задач.

IS-DOS - пользователям: как скопировать системный диск IS-DOS и остаться при этом в живых.

IS-DOS - программистам: краткий курс - программирование в среде IS-DOS.

IS-DOS - news: новые программы IS-DOS.

Железо - Краткий рассказ о возможностях процессора Z-180.

Железо - Multiviewer. Описание доработочки, позволяющей мерять скорость программ по бордюру без влезания в коды - легким нажатием кнопки.

Железо - о новом проекте фирмы Peters - "Sprinter". Новый Spectrum-совместимый компьютер нового поколения Speccy.

Железо - Мнение пользователя о скорпионовском контроллере IDE HDD - SMUC.

Железо - SuperSpectrum: об одном проекте Spectrum-совместимой машины. Её особенностью является совместимость с PC.

Железо - X-Trade FAQ. Ответы на наиболее часто задаваемые вопросы по GS и XTR-модему.

Премьера - Flash tracker. Описание 4-х канального редактора цифровой музыки, работающего с SoundDrive, от самого автора SoundDrive - Flash Inc.

Премьера - Описание последней версии универсальной терминальной программы, используемой в SpbZxNet.

Премьера - Mortal Kombat: что ждёт Вас в полной версии игры и некоторые коментарии к demo версии.

Премьера - XReversy: презентация новой игрушки, из популярного семейства "реши задачку - посмотри картинку".

Интервью - Интервью с одним из известнейших спектрумистов - Андреем Ларченко.

Здесь был ты - Рассказ "Абсолютная власть".

Здесь был ты - Рассказ "Дорога".

Здесь был ты - Повелитель зубов: пародия на одну популярную трилогию...

Почта - Обратная связь: ответное письмо Alex'а из Нижнего Тагила, выставленного в прошлом номере в "Уголок ламера".

Почта - Письма читателей: Андрей Яковлев, Денис Токарчук, Алексей Гаркулим, Александр Гордеев, Евгений Шумилов, Ниточкин Вадим, Михаил Ларкин.

Почта - бесплатная реклама и обьявления.

Разное - Страшилка.: Nemo рассуждает о месте PC и Spectrum'а в современной России.

Разное - Рецензия Nemo на книжку по цифровой схемотехнике. Для всех, кто хоть когда-нибудь испытывал желание включить паяльник и...

Разное - анкета: Результаты нашего социологического опроса спектрумистов.

Разное - Конкурс. Краткий отчет о наших конкурсах.

Разное - Проблемы рынка ПО: когда загнется Спектрум. Во всем ли виноваты Хакеры?

Разное - Перспективы ПО. Краткий обзор готовящегося к выходу ПО: Fast Tracker, Pro Sound Creator, Чёрный Ворон.

Разное - Перспективы ПО. Адвентюра From Beyond или "Извне".

Разное - мемуары о Питерской модемной сети для ZX Spectrum - SPbZXNet.

Amiga Club - Между нами, пользователями: сравнение характеристик Amiga 1200 с IBM PC.

Amiga Club - сравниваем производительность Амиг и PC. Насколько Амига актуальна в современных играх?


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Internet - Введение в Internet.
Графика - картинкa АNSI графики.
Кодинг - Искусственный интеллект (Началo cм. в N1).
Новости - Загадочная идея в MOVE #8.
Системки - Программы с поддержкой HDD, или "Linux" для Спектрума с винтом (или SD-картой).

В этот день...   11 октября