Из журнала ZX Format #5, Санкт-Петербург, 12.12.1996 ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ В КОМПЬЮТЕРНЫХ ИГРАХ. (С) Стас Вихров 1996. -------------------------------- Сегодня я хочу поговорить об искусственном интеллекте (ИИ) в компьютерных играх. К сожалению за последние 10 лет в этой об- ласти мало что изменилось. В иг- рах развивается графика, звук, всевозможные эффекты, но ИИ ос- тается по прежнему крайне не развитым. Даже, по-моему, чем лучше оформление игры тем, обыч- но, у нее слабее интеллект. Обычно игры строятся на про- тивоборстве игрока и программы. Например, игрок управляет чело- вечком, танком, автомобилем или чем-либо еще, а программа напа- дает на игрока всевозможными об- ъектами. В играх такого типа часто интеллект абсолютно от- сутствует, все нападающие объек- ты появляются в одних и тех же местах и двигаются по заранее запрограммированой траектории, в лучшем случае пушки стреляют случайным образом. Прохождение таких игр сводится к запомина- нию, что где вылетит и куда по- летит. Игры такого типа, с пол- ным отсутствием интеллекта, сос- тавляют основу ПО для 8-ми бит- ных игровых приставок. Думаю примеры таких игр приводить не надо. Иногда в таких играх на- чальное положение нападающих об- ъектов задается случайным обра- зом, но это еще не интеллект, так как движение нападающих не связано с действиями игрока. Первые признаки ИИ наблюдают- ся в играх типа КЛАД,EAGLES NEST и подобных, там нападающие дви- гаются следующим образом: зная координаты игрока они двигаются влево или вправо, пытаясь срав- нять свою горизонтальную коорди- нату с горизонтальной координа- той игрока, после того как коор- динаты сравняются или дальнейшее продвижение в этом направлении станет невозможным, они начинают сравнивать свои вертикальные ко- ординаты с коорд. игрока, если это невозможно, то нападающий объект останавливается. Более хитрый ИИ в таких играх, как LO- DE RUNNER, PACMAN. Также часто используется алгоритм, когда на- падающий объект пытается прибли- зиться к координатам игрока, на которых он был несколько ходов назад. Создатели стратегических игр, за редким исключением, пы- таются заменить интеллект прог- раммы силой. Типичным примером таких игр может быть игра ZULU WAR: В ней вся стратегия заклю- чается в том, что все зулусы толпами прут на генерала, только иногда, если рядом окажется ка- кой-нибудь полк, нападают на не- го. Но обыграть компьютер не просто, так как на каждого сол- дата приходится по десять зулу- сов. Но наибольший интерес с точки зрения ИИ представляют игры, в которых силы игрока и компьютера равны: это могут быть карточные игры, шахматы, некоторые страте- гические игры и большинство нас- тольных игр. Все такие игры мож- но разделить на два вида: игры, где существует формула или прос- тые провила, по которым можно определить ход и игры, в которых нет или еще не найдены такие правила. В качестве примера пер- вого вида игр можно привести иг- ру "21 спичка"-в ней всегда вы- игрывает второй игрок, если при- держивается следующего правила: если первый игрок берет 1 спич- ку, то надо брать 2 спички, а если первый игрок берет 2 спич- ки, то надо брать 1 спичку. Зная это правило можно составить программу, которая всегда будет выигрывать. Но таких игр немного и все они достаточно примитивны. Кроме того логические игры можно разделить на игры, в кото- рых есть элемент случайности и игры, в которых все зависит только от игрока. Элемент слу- чайности обычно достигается за счет бросания кубика или, ска- жем, за счет того, что не из- вестна позиция противника. Клас- сическим примером игр, где при- сутствует элемент случайности могут быть практически все кар- точные игры, где неизвестен по- рядок карт в колоде и карт про- тивника. Рассмотрим для примера прос- тые карточные игры, например, очко. Кратко напомню правила:- каждая карта имеет достоинстрво от 3 до 11. Цель игрока набрать от 16 до 21 очка, чем больше тем лучше, если игрок набирает больше 21, то он проигрывает. В начале игры каждому игроку выда- ется по 2 карты и он может, если хочет, взять еще несколько карт из колоды. Для примеров я буду использовать BASIC с элементами некоторого алгоритмического язы- ка. Вам я тоже советую для раз- работки своих алгоритмов ис- пользовать BASIC по следующим причинам: легко искать ошибки, везде можно вставить оператор PRINT и следить за промежуточны- ми результатами, текст программы достаточно нагляден, алгоритм можно разрабатывать по частям, кроме того, если при составлении использовать только целые и не больше 255 числа, то такой алго- ритм легко перевести на AS- SEMBLER или откомпилировать це- лочисленым компилятором бейсика. Переводить алгоритм на ASSEMBLER следует только после полной от- ладки. Самый простой алгоритм, кото- рый реализует игру "очко" выгля- дит следующим образом. 10 LET A=ПОДСЧЕТ ОЧКОВ 20 IF A<18 THEN БРАТЬ КАРТУ:GO TO 10 Как вы уже догадались, ПОДСЧЕТ ОЧКОВ это функция, кото- рая считает сумму достоинств карт, находящихся на руках у компьютера, а БРАТЬ КАРТУ -это процедура, которая осуществляет взятие карты из колоды. Но если игрок догадается по какому пра- вилу играет компьютер, он будет часто выигрывать. Заменим константу переменной величиной. 10 LET M=16+INT(RND*3) 20 LET A=ПОДСЧЕТ ОЧКОВ 30 IF A3 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 ;подпрограмма 2005 IF A(X1, Y1)=0 ;определяет THEN RETURN ;первую пустую клет- ;ку в X1 ом столбце. 2010 LET Y1=Y1+1:IF Y1=8 THEN RETURN 2015 GO TO 2005 Это медленная, но зато самая точная процедура для рассчета силы позиции. Ее можно сделать быстрее, заменив, например, строку 1030 на IF A(X, Y)<>C THEN GOTO 1300, но в этом случае понизится точность. Далее выполняем перебор всех ходов, для начала на 2 полухода. Для каждого варианта считаем си- лу позиции относительно каждого цвета. Результаты вычислений по- мещаем в массив В(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 Строки 110, 120 и 140, 150 смотрят за тем, чтобы не устано- вить фишку в заполненный стол- бец. Строка 125 устанавливает, а 220, 230 уберает фишку первого цвета, аналогочно строки 160, 190, 200 для второго цвета. Строки 170, 180 заполняют массив В(7, 7, 2) силами перебранных позиций для каждого цвета. После выполнения этой прог- раммы в массиве В(7, 7, 2) есть вся информация для определения лучшего хода, ее остается только обработать. Организуем массив C(7), в него будем помещать при- оритеты каждого хода. Макси- мальный приоритет будет 1, а ми- нимальный 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)0 THEN GO TO 220 180 IF A(X1-1,Y1)=2 THEN LET A(X1,Y1)=2: LET N=N+1 190 IF A(X1+1,Y1)=2 THEN LET A(X1,Y1)=2: LET N=N+1 200 IF A(X1,Y1-1)=2 THEN LET A(X1,Y1)=2: LET N=N+1 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 ОБНОВИТЬ ЭКРАН: ОБНОВИТЬ МАССИВ 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.Найти в массиве наибольшее число и при- нять за "лучший ход" первую координату этого числа. 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 1 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 1 NEXT A3 120 ИЗВЛЕКАЕМ ПОЗИЦИЮ ИЗ МАССИВА Б2 121 NEXT A2 130 ИЗВЛЕКАЕМ ПОЗИЦИЮ ИЗ МАССИВА Б1 131 NEXT A1 На данный момент мы получили массив А(N,N,N,N), который содержит силы всех возможных позиций на глубину 4 полухода начиная от данной. 200 ПРОГРАММА ОБРАБОТКИ МАССИВА И ОПРЕДЕЛЯЮЩАЯ ЛУЧШИЙ ХОД. По такому принципу, с некоторыми отли- чиями, строится большинство программ ис- пользующих ИИ; эти отличия в основном заключаются в различных способах сэконо- мить память или время рассчета, например, за счет неполного перебора позиций. ( продолжение следует ) _________________________________________