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 ПРОГРАММА ОБРАБОТКИ МАССИВА И ОПРЕДЕЛЯЮЩАЯ ЛУЧШИЙ ХОД. По такому принципу, с некоторыми отли- чиями, строится большинство программ ис- пользующих ИИ; эти отличия в основном заключаются в различных способах сэконо- мить память или время рассчета, например, за счет неполного перебора позиций. ( продолжение следует ) _______________________________
Другие статьи номера:
Похожие статьи:
В этот день... 11 октября