Неопределенным интегралом яростно извивался монстр под ударами царевых уравнений и повергался, рассыпанный в несчетное множество неизвестных, и восставал вновь, возведенный в высшую степень, а царь поражал его дифференциалами, да так, что лишь клочья функциональных операторов летели в разные стороны…
(С.Лем, «Кибериада»)
В августовском номере журнала мы с вами разобрали устройство несложной компьютерной стратегии. Однако в ней не хватало одного существенного элемента: искусственного интеллекта. В нее можно было играть только с живым противником.
Настал черед восполнить этот пробел.
Не стану повторять заново все рекомендации о том, как устанавливать пакет, что для него необходимо и так далее - все это вы можете прочесть в наших предыдущих статьях, которые, как и сам ЛКИ-Creator, находятся на компакт-диске журнала в разделе «Игра своими руками». Перейдем сразу к сути дела.
В отличие от предыдущих наших статей, здесь будет меньше готовых решений и больше вариантов для самостоятельного выбора. ИИ - слишком тонкий механизм, чтобы можно было решить задачу, скажем, «ИИ для стратегий» раз и навсегда. Однако, вопреки пессимистам, ничего такого уж немыслимо сложного в написании ИИ нет.
Каким бывает ИИ?
Есть много способов организовать ИИ компьютерных противников. Если почитать по этому поводу научно-популярную литературу, вы узнаете многое о нейронных сетях и других модных техниках. К сожалению, нейронные сети внедрялись всерьез лишь в очень немногих играх, и не сказать, чтобы эти игры как-то позитивно выделялись уровнем своего ИИ. Впрочем, в одной из последующих статей мы поговорим и о нетривиальных способах организации ИИ - в конце концов, кто сказал, что надо плестись позади прогресса?
Но на практике обычно применяются совсем другие методы.
Перебор с оценкой
Эту схему описывал еще Михаил Ботвинник. Мы перебираем все возможные варианты действий каждой боевой единицы, сохраняем все получившиеся позиции, после чего специальной функцией определяем "качество" позиции. Например, складываем стоимость всех бойцов у каждой стороны; если боец уничтожен, его цена не прибавляется к итогу, а если он ранен - то прибавляется не полностью. К тому же, стрелок, атакованный воином ближнего боя, получает минус к своей оценке (он вроде как уже не совсем жив…), и точно так же - боец без дальней атаки под огнем стрелка. Наконец, в нашем случае боец, занимающий обелиск, должен добавить к сумме значительное число за приближение к итоговой цели.
После подсчета сравниваем очки одной и другой стороны - и выясняем качество позиции. Выбираем лучшую.
Казалось бы, все просто. Но препятствие видно невооруженным глазом: слишком их много, этих позиций. Если каждый боец может сделать 10 вариантов хода (а это очень заниженная оценка!), а всего солдат у каждой стороны по 15 штук, получаем 1015 вариантов; есть опасность умереть от старости прежде, чем все обсчитается.
Это интересно: спектр вариантов тут может оказаться намного больше, чем в шахматах: ведь там каждый ход делается всего одной фигуров, а значит, всего вариантов хода - число фигур * число вариантов для фигуры, а у нас - число вариантов в степени количества фигур!
Самое популярное решение - в оценке хода отдельной фигуры, без учета действий остальных. Из всех ходов выбирается, скажем, два с наилучшим результатом - это даст в нашем случае 215 = 32768 позиций, что немало, но для современных компьютеров вполне "подъемно". А если вообще исключить влияние комбинаций и брать только "лучший" ход - получим один-единственный вариант!
Это интересно: дотошный читатель может заметить, что это не совсем правда: все-таки ходы мы по-прежнему перебираем все возможные, а значит, нам придется перебрать 10 * 15 = 150 вариантов (если каждая фигура может сделать только 10 различных ходов). Но и это очень скромно. Однако, если возможных ходов становится уж очень много (например, если поле не разбито по клеточкам - возникает чуть ли не бесконечный перебор), нам придется ограничить возможные варианты. Например, разрешить космическому кораблю движение только на расстояния, кратные 10…
Работает ли такая схема? О да. Но есть у нее и весьма серьезные недочеты.
Главный недостаток одноходового перебора - нет долгосрочного планирования. Например, если до врага достаточно далеко, наш ИИ может решить, что нет смысла двигаться - все равно одним ходом ничего ценного не сделать. И будут наши солдатики стоять, как три тополя на Плющихе…
Или вот, например, захват обелиска. Все бы ничего, да только у нас в игре их зачастую сторожат драконы. Чтобы занять обелиск, надо сперва подставиться под его удар, и только потом, возможно, взять его. А это значит, что на момент атаки наша "цена позиции" упадет (боец под ударом), а вражеская останется неизменной (дракон-то нейтрален). То есть, наш ИИ по доброй воле никогда не попытается штурмовать нейтральных монстров.
В ряде случаев нам поможет более тщательное написание функции оценки. Например, мы решаем, что, чем ближе наш мечник к противнику - тем больше он "стоит". И тут уж они, никуда не денутся, радостно поспешат на вражеский строй.
Если два бойца разных сторон стоят друг против друга, и один из них сильнее - он получает плюс к оценке, а противник - минус; если двое напали на одного - у них за это плюс; и сразу же появляется стремление бить в нужную точку…
Грамотным написанием функции оценки можно добиться очень многого. И не секрет, что похожим способом рассуждают и многие живые игроки.
Это интересно: иногда в функцию оценки добавляют небольшой случайный элемент, чтобы программа рассматривала вместе с основным не самые очевидные варианты.
Границы применимости
Метод одноходового перебора с оценкой работает замечательно, если карта невелика, а цели максимально просты (например, уничтожить противника). При соблюдении этих условий он достаточно точен, то есть выбирает варианты, близкие к оптимальным. Например, именно так традиционно делался ИИ для боя в Heroes of Might & Magic. Этому методу не требуется знание изначальной расстановки солдат, своих и вражеских, а также он мало зависит от действий противника; это его выгодно отличает от скриптов. Он неплохо учитывает даже самые богатые возможности и спецспособности бойцов.
Взаимодействие в группе здесь налажено «на четверочку с минусом»: нетрудно заставить бойцов, скажем, окружать врага или лечить друг друга, но намного сложнее заставить не путаться друг у друга под ногами или координировать свои действия по времени.
Метод, по всей вероятности, будет давать сбои, если:
хорошо развита возможность комбинации способностей. Скажем, один маг создает вокруг противника клетку, а другой тут же вызывает внутрь клетки опасного, но неуправляемого монстра. ИИ в лучшем случае выполнит это последовательно - в разные ходы;
на карте присутствуют необъятные просторы: тут возникает необходимость в стратегическом планировании маневра, а здесь ИИ не силен. Если он должен обороняться, еще ничего - можно запрограммировать ему пассивное поведение, но при активном маневре живой противник, скорее всего, управится с ним легко;
часть целей работает на далекое будущее: например, мы берем тех же Heroes of Might * Magic, но не сражение, а стратегический режим. ИИ будет очень трудно выбрать правильную последовательность сбора ресурсов, потому что он ничего не знает о том, что «будет и следующий ход», и о том, сколько дерева или золота потребуется нам к концу недели.
Многоходовый перебор
Первое, что обычно приходит в голову студенту, которому предлагают улучшить метод перебора - это сделать перебор многоходовым. То есть, обсчитать не один ход, а несколько подряд.
Очевидно, что такой путь требует, во-первых, чтобы ИИ думал не только за себя, а еще и за игрока «с той стороны».
Выбирать один-единственный вариант хода мы уже не можем: если все альтернативы мы отбросили сразу, что нам добавит обсчет следующего хода? Нам бы хотелось выбирать первый ход с учетом второго. А значит, надо оставить хотя бы несколько вариантов, скажем, 3-4.
Кроме того, есть опасность, что оставленные варианты будут очень похожи друг на друга, и действительно разных первых ходов в списке не окажется; надо добавить проверку на одинаковые ходы.
В общем, когда мы все это сосчитаем, станет ясно, что для нашей игрушки размышления над многоходовым перебором (даже если «много» - это всего лишь 2) приведут к триллионам вариантов. Это по плечу Deep Blue, но наш родимый РС лучше все-таки так не насиловать.
Значит ли это, что многоходовый перебор не имеет права на жизнь? Нет, конечно. Но действовать с ним надо предельно аккуратно. Отсекать из списка несколько десятков лучших позиций, так, чтобы они были как можно более разными. Это реальный путь, но не могу порекомендовать его начинающему программисту - слишком велики трудности.
Скрипты
Как известно любому прилежному читателю игровой прессы, один из самых популярных способов организовать ИИ - это скрипты, то есть попытка заранее запрограммировать действия своих бойцов.
Скрипт - это некая программа, написанная на специальном языке, команды которого соответствуют игровым возможностям. Вот пример задания для скрипта некоего кочевника из ролевой игры:
Если на кочевника никто не нападает, он с вероятностью 10% садится отдохнуть, иначе двигается к случайно выбранной точке на расстоянии 300 (если он видит бесхозного верблюда, то переключается на задачу «поймать верблюда», то есть приближается к нему и садится верхом; если ушел слишком далеко от дома - целью становится дом). Если же его атакуют, он дерется, коль скоро у него больше 20% хитов, иначе бежит в сторону, противоположную той, с которой на него нападают.
Это нетрудно выразить в коде, но для этого надо сперва придумать себе язык скриптов. В ЛКИ-Creator встраивается свой особый язык ЛКИ-Helmsman (конечно, не универсальный, но достаточно широкого применения). Полная его реализация будет завершена, видимо, к концу года, но часть возможностей вы получите в свое распоряжение в ближайшем будущем, вместе с рассказом о том, как ими пользоваться.
Тактический бой в скриптах обычно устраивается примерно так:
Атаковать самого сильного противника из тех, что есть в пределах досягаемости; если в этих пределах нет никого - выбрать противника, до которого можно добраться за наименьшее число ходов. Если рядом враги, которые сильнее меня в 2 и более раза (по стоимости) - отступать по наиболее свободному направлению.
Конечно, это все можно организовать намного более тонко; например, выбирать не "самого сильного", а, скажем "лучшего по соотношению d1 * d2", где d1 - это средний вред, который мы можем нанести ему, а d2 - средний вред, который наносит он нам. Другими словами, стреляем так, чтобы нанести как можно больше вреда как можно более опасному противнику. Эта механика уже учитывает уязвимость бойцов к оружию друг друга.
Границы применимости
Скрипты, в отличие от перебора, подходят для дальнего стратегического планирования. Ничто не мешает вам задать сколь угодно далекую цель и описать механизм ее достижения.
Количество потребных для скрипта системных ресурсов не так уж мало, но зато с ростом числа боевых единиц, управляемых скриптом, затраты ресурсов растут всего лишь линейно (100 бойцов требуют вдесятеро больше ресурсов, чем 10). А в случае перебора, где для каждого бойца оставляется по 2 варианта, разница будет такая, что цифры в строчке не поместятся.
Но есть у скриптов и слабости:
скрипты писать относительно просто, если известно хоть что-нибудь о своей армии и об армии противника (а по возможности - еще и о местности). Намного сложнее сделать скрипт для произвольного противника в произвольных обстоятельствах;
скрипты часто оказываются предсказуемы, и игроки, которые выучили их способ действия, начинают над ними просто глумиться. Так, например, игрок, который познал метод фехтования компьютерных противников в World of Pirates (см. руководство на страницах журнала), может смело идти воевать со значительно более сильным врагом;
они не очень устойчивы к нестандартным действиям противника, а при пассивном враге могут привести к статичной позиции вроде известного нам из истории "Стояния на реке Угре";
в тактике они порой оказываются менее разумны, чем простой перебор, потому что в густой толпе врагов не учитывают особенностей расположения противника.
В принципе, никто не запрещает сочетать их с перебором (на ближней дистанции включается другой механизм), но я не рекомендовал бы заниматься такими мичуринскими опытами, пока вы не освоитесь с обоими методами по отдельности.
Взаимодействие в группе - не самая сильная сторона скриптов, хотя обычно это не очень резко бросается в глаза. Однако поправить дело можно, если определить принадлежность каждой боевой единицы к той или иной группе и роль в ней. А скрипты писать по принципу: "Следуем за лидером, атакуем того же, что и он…"
Есть еще несколько интересных методов комбинации скриптов и перебора, основанных на таких достижениях информатики, как генетические алгоритмы и нейронные сети.
Подробно мы о них пока говорить не будем; а кому интересно, почему - может почитать статью из нашего февральского номера «Капризы нерожденного AI», которую мы для удобства поместили на компакт-диск.
Переборный ИИ для «Обелиска»
ИИ для нашей игры «Обелиск» можно написать, например, методом перебора. Карты не особо велики, так что все должно получиться.
Совет: сделайте карту поменьше, а также возьмите для начала не очень много бойцов с каждой стороны. Это очень упростит вам отладку; а ИИ - едва ли не самая сложная в отладке задача.
Для начала зададим тип TObeliskAction, который будет полностью описывать возможное действие бойца. Нам там понадобится код действия (например, 0 - движение, 1 - атака…), координаты точки, куда хотим действовать, и если цель - объект, то ее тоже стоит указать. Кроме того, для атаки, лечения и других действий нужно знать, что мы делаем прежде - двигаемся или совершаем действие; для этого послужит логическая переменная AcMvFirst (в случае простого движения ее значение не важно).
Объявления | На врезке "Объявления" вы видите те добавки, которые мы внесем в раздел объявлений. Мы определяем TObeliskAction, возможные коды действий задаем константами (это нужно затем, чтобы в процессе работы не путаться, какое число что означает. Всегда лучше пользоваться поименованными константами, чем прямым указанием числа) и добавляем в игровой мир TObeliskWorld список действий, а также процедуры AI (выбирающей действия) и Fulfil (выполняющей поставленные задачи). |
Процедура TObeliskWorld.AI
ИИprocedure TObeliskWorld.AI; var i, ix, iy, j, n, m : integer; A, AMax : TObeliskAction; Units : array[0..MaxUnit-1] of TObeliskObject; Obj, O : TObeliskObject; begin // Определяем войска своей стороны NumActions := 0; for i := 0 to NObj-1 do if (Objects[i] as TObeliskObject].Side = 1 then begin Units[NumActions] := Objects[i] as TObeliskObject; inc(NumActions] end; // Формируем список действий for i := 0 to NumActions-1 do begin M := -1; Obj := Units[i]; // Создаем действия движения for ix := 1 to Map.SizeX do for iy := 1 to Map.SizeY do // Добегаем? if Obj.HasWay(Map.Tile(ix, iy)) then begin A.AcX := ix; A.AcY := iy; // Сперва оценим просто движение, // без действия A.AcType := acMove; N := Obj.Appraise(A); if N >= M then begin AMax := A; M := N end; // Выбор объекта для атаки for j := 0 to NObj-1 do begin O := Objects[j] as TObeliskObject; if O.Side in [1,3] then continue; if (O.Dist(Obj)=1) or (Obj.Dist(O) <= Obj.Range then begin A.AcTarg := j; A.AcMvFirst := false; A.AcType := acAttack; N := Obj.Appraise(A); if N >= M then begin AMax := A; M := N end; end; // Теперь то же для порядка движение-действие if (O.Dist(ix,iy)=1) or (O.Dist(ix,iy) <= Obj.Range then begin A.AcTarg := j; A.AcMvFirst := true; A.AcType := acAttack; N := Obj.Appraise(A); if N >= M then begin AMax := A; M := N end; end; end; // Здесь идут дополнительные действия // для мага и рыцаря - мы их пропустим end; // Заносим оптимальное значение в список GameActions[i] := AMax; end; end; | Поглядим на врезку «ИИ». Там показана большая часть процедуры выбора хода. Смысл следующий. Поочередно для каждого объекта выбираем лучшее действие. Для этого присваиваем переменной M отрицательное значение (цена любого действия не меньше нуля) и перебираем все возможные действия; если значение найденного действия (определяется функцией Appraise) больше нуля, заменяем M на ее значение, а в переменной AMax сохраняем действие. Действия составляются так. Во внешней паре циклов определяются все клетки, на которые можно перешагнуть. Если можем - составляется и проверяется действие движения. Потом проверяется, можем ли мы атаковать каждый из объектов врага - с исходного и с нового поля. Составляются действия атаки перед и после хода. Для тех, у кого есть какие-то особые приемы, проверяется еще и их возможность. После того, как у нас все действия будут просчитаны, остается только запустить процедуру Fulfil, которая исполняет все действия из списка. Ее код мы не приводим, но он довольно прост: переместить все фигуры в нужные места и обсчитать атаки и заклинания. Самая творческая часть работы - это функция оценки, Appraise. На врезке «Оценка действия» - ее несложный вариант. |
Оценка действияfunction TObeliskObject.Appraise(Act : TObeliskAction) : integer; var i, dmg : integer; killed : boolean; O : TObeliskObject; begin Result := Hits; Killed := false; // Увеличим результат на вред, наносимый врагу if Act.AcType = acAttack then begin // Вычитаем защиту; повреждения меньше 0 не считаем dmg := Max(Damage -(World.Objects[Act.AcTarget] as TObeliskObject).Defence, 0); inc(Result, Dmg); // Увеличим еще результат, если атака добивает врага if dmg > World.Objects[Act.AcTarget].Hits then begin inc(Result, dmg); killed := true; end; end; // Теперь оценим новую позицию фигуры for i := 0 to World.NObj-1 do begin O := World.Objects[i] as TObeliskObject; // Проверяем на соседство с обелиском if (O.Code = 0) and (Dist(O)<=1) then inc(Result, 50) else if (O.Side = 0) and (O.Range<=Dist(O)) then begin // Убитый нам уже не угрожает if Killed and (Act.AcTarget = i) then continue; // Иначе уменьшаем цену действия на ожидаемый вред Dec(Result, Max(O.Damage - Defence, 0)); end; end; // Результат не может быть меньше 0 Result := Max(Result,0); end; | Здесь мы сперва увеличиваем цену действия на количество оставшихся у нас хитов; потом добавляем повреждения, нанесенные врагу (удваиваем, если враг при этом гибнет); потом проверяем, не подошли ли мы к обелиску, и если да, то делаем существенную прибавку; наконец, уменьшаем число за счет врагов, которые могут по нам бить. Уже эта схема дает приличные результаты. Хотя совершенно ясно, что ее можно еще многократно улучшить. Например:
|
По правде говоря, некоторые из этих изменений потребуют правки и в процедуре AI… но почему бы и нет? Поэкспериментируйте, и полученного опыта вам вполне хватит на ИИ для достаточно широкого класса игр.
До встречи через месяц!
Работа над ошибкамиНам регулярно присылают вопросы по поводу нашего пакета, замеченные ошибки, вопросы по неясностям в статьях и т.п. Мы же, в свою очередь, стараемся эти ошибки искоренить в коде, а неясности попробуем уничтожить на этой странице. Самых распространенных проблем - две… Ошибка при инициализации движкаУ многих возникает ошибка при запуске программы: Project raised exception Class EExternal with message 'Create windowed display: Generic Failure' Это означает, что вы попытались создать полноэкранное игровое окно с несоответствующими параметрами. Вам нужно либо проставить в true свойство Windowed движка (если вы задумывали оконное приложение), либо установить размеры окна так, чтобы они соответствовали одному из популярных разрешений (например, 1024 и 768), если в ваших планах фигурирует полноэкранное приложение. Иначе программа попытается открыть полный экран с параметрами вроде 723 * 456 точек и сходит с ума, пытаясь представить себе такое разрешение. Конфликт версий DelphiРазработка продукта сразу под три версии Delphi имеет свои недостатки: время от времени вылазит конфликт версий. Мы обычно его быстро разрешаем, но что делать, если он произошел у вас? Обычно он возникает при сообщении вроде Cannot pass a constant object as var parameter или попытке присвоить значение переменной, которую программа считает константой. Это бывает при использовании новых версий Delphi и типично при работе с любыми пакетами, ориентированными на более старшие версии. К счастью, исправить такую ошибку очень легко: найдите, где определяется переменная, из-за которой весь сыр-бор (щелкните по ней правой кнопкой мыши и выберите Find Declaration). Она наверняка определяется как-нибудь вроде Const a : integer = 24. Раньше именно так определяли переменные с начальным значением. Замените слово Const на Var - и все будет замечательно. Недостающие файлы и неотвеченные вопросыЕсли вдруг что-то неправильно распаковалось, чего-то не хватает и так далее - все бывает в этом мире - пишите нам. Мы постараемся прислать вам недостающий файл. Увы, был период, когда наш ящик барахлил, но вроде бы проблемы с ним исправились, так что, если мы не ответили на чей-то вопрос - просто пришлите его снова. |
Пишите нам…Все, кто хочет поделиться своими соображениями о пакете ЛКИ-Creator и этом цикле статей, сообщить о найденной ошибке, спросить совета или предложить какое-то усовершенствование - милости просим писать по адресу lkicreator@igromania.ru. Кто-нибудь из авторов пакета постарается ответить вам. Тем, кто считает, что пакет можно чем-то дополнить: во-первых, не забудьте, что на нашем диске сегодня еще не финальная версия пакета, а только та, в которой реализованы описанные в наших статьях функции. Возможно, что-то из ваших идей уже реализовано и ждет своей очереди (см. врезку «В будущих номерах»). И в любом случае: предлагая нам какую-то идею, попытайтесь обосновать, почему ваше предложение полезно сразу для многих игр, а не только для вашей конкретной. |
По вашим заявкам: консольЦелая группа читателей, к нашему удивлению, запросила о создании игровой консоли. Это нас немало удивило, но мы следуем пожеланиям трудящихся. В роли консоли выступит все тот же объект TLKIEdit - ведь, в сущности, что такое консоль, как не текстовая строка ввода? Как пользоваться этим объектом - вы прочтете в июльском выпуске ЛКИ (статья есть на CD этого номера). Добавить нам пришлось только одно - параметры ActivationMode и ActivationKey, которые теперь встроены в TLKIEdit. Первый может принимать значения: acNone (не включается клавишами), acShift, acCtrl, acAlt (включается при нажатых клавишах Shift, Ctrl, Alt соответственно). Ну, а в ActivationKey - символ, соответствующий клавише, которая должна включать консоль. Обратите внимание: acNone - это не признак того, что строка включается без Shift-Ctrl-Alt, а признак того, что она вообще не включается нестандартным способом. |