Неопределенным интегралом яростно извивался монстр под ударами царевых уравнений и повергался, рассыпанный в несчетное множество неизвестных, и восставал вновь, возведенный в высшую степень, а царь поражал его дифференциалами, да так, что лишь клочья функциональных операторов летели в разные стороны…
(С.Лем, «Кибериада»)
В августовском номере журнала мы с вами разобрали устройство несложной компьютерной стратегии. Однако в ней не хватало одного существенного элемента: искусственного интеллекта. В нее можно было играть только с живым противником.
Настал черед восполнить этот пробел.
Не стану повторять заново все рекомендации о том, как устанавливать пакет, что для него необходимо и так далее - все это вы можете прочесть в наших предыдущих статьях, которые, как и сам ЛКИ-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 (в случае простого движения ее значение не важно).
ОбъявленияConst acMove = 0; acAttack = 1; acHeal = 2; acCharge = 3; acCast = 4; Type
TObeliskAction = record AcType : integer; // Тип действия AcMvFirst : boolean; // Cперва движение, потом действие? AcX, AcY : integer; // Координаты места движения AcTarg : integer; // Номер объекта-цели (если есть) end;
TObeliskWorld = class(TLKIGameWorld) ... GameActions: array[0..MaxUnit-1] of TObeliskAction; NumActions : integer; procedure AI; procedure Fulfil; end; TObeliskObject = class(TLKIGameObject) ... function Appraise(Act : TObeliskAction) : integer; end; |
На врезке "Объявления" вы видите те добавки, которые мы внесем в раздел объявлений. Мы определяем 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 as TObeliskObject].Side = 1 then begin Units[NumActions] := Objects as TObeliskObject; inc(NumActions] end; // Формируем список действий for i := 0 to NumActions-1 do begin M := -1; Obj := Units; // Создаем действия движения 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) = M then begin AMax := A; M := N end; end; // Теперь то же для порядка движение-действие if (O.Dist(ix,iy)=1) or (O.Dist(ix,iy) = M then begin AMax := A; M := N end; end; end; // Здесь идут дополнительные действия // для мага и рыцаря - мы их пропустим end; // Заносим оптимальное значение в список GameActions := 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 as TObeliskObject; // Проверяем на соседство с обелиском if (O.Code = 0) and (Dist(O) |
| 921 Прочтений • [Занятие пятое: Электронный стратег] [15.08.2012] [Комментариев: 0] |
Добавил:  Vova |
| Похожие статьи | ||||
| Название | Добавил | Добавлено | ||
| • Занятие пятое: Электронный стратег | Vova |
15.08.2012 | ||
