Gamedev
Denis Anohin
4352

Разработка искусственного интеллекта из искусственного идиота в пошаговой тактической игре

В тактических играх ИИ очень важен. Если ИИ видится как «искусственный идиот», то игру может спасти потрясающий мультиплеер, сюжет, атмосфера и графика (это неточно). Решение очевидное: делай хороший ИИ, в чём тут могут быть проблемы?

В закладки
Аудио

В деталях. Ниже описаны мои шаги по конструированию сильного ИИ с характером. Не супер сильного [1], но способного быстро отработать локально в прожорливом браузере любого средне-слабого ПК. Мною применён подход экспертных систем с использованием набора эвристик и мутаций. Описаны 15 шагов постепенного преображения ИИ, каждый из шагов можно пощупать.

Краткое описание

В подопытной браузерной игре ИИ основан на генерации множества возможных состояний — результатов выполнения текущего хода. (Из-за игровой специфики и удобства эти результирующие состояния в статье называются то сценариями хода, то стратегиями ИИ — в зависимости от контекста). Затем сценарии хода подвергаются мутациям. По полученным сценариям вычисляются оценки «успешности». Самая успешная и выполняется компьютерным игроком.
Например, генерируются три стратегии:

  • Бежать оголтело всем вперед и атаковать всех, кто подвернётся под руку. Очки итогового состояния: 37000 баллов.
  • Атаковать лучниками с безопасного расстояния, а остальные прячутся по углам. 45000 баллов.
  • Всем отступить, сгруппироваться и попрятаться от врагов. Если можно при этом ранить какого-нибудь врага с безопасного расстояния, то атаковать. 18000 баллов.
  • В этом случае будет выбрана 2-я стратегия.

Ну вроде всё стандартно.
Не совсем.Вся мякотка в том, как генерируются сценарии и как вычисляется коэффициент ценности сценария. Налажаешь в одном из них, и результат тебя опечалит.

Правила игры

У игрока и у ИИ изначально по углам выдаются по 6 одинаковых юнитов. Каждая команда ходит по очереди всеми юнитами сразу. Варианты хода каждого юнита:

  • пропустить ход;
  • передвинуться и пропустить;
  • передвинуться и атаковать (можно и иногда нужно атаковать своих).

Игровое поле и состав команды генерируется процедурно (то есть случайно, но с проверками на проходимость и приемлемую «тактичность»).
Типы юнитов:

  • Боец F, юнит ближнего боя с самой большой живучестью, уроном и мобильностью. Эдакий танк+дамагер.
  • Лучник A, самый низкий урон, зато атака на расстоянии 1-7 по прямой линии.
  • Колдун W, умирает с одного удара бойца, зато атака на расстоянии 1-5 по прямой линии насквозь по всем юнитам.

Игровое поле всегда размером 10*10.Возможные поля на карте:

  • Земля — не накладывает никаких ограничений.
  • Стена — через неё нельзя ни прострелить, ни пройти.
  • Вода — через неё нельзя пройти, но через неё может стрелять лучник (огненный маг не может).

Игра полностью детерминирована, то есть в ней нет элемента случайности (шанс попадания 100%, никаких критических уронов и т.п.). Также это игра с полной информацией, то есть соперники всё знают о состоянии войск друг друга в любой момент времени. Как в шашках.
ИИ сильнее мясного игрока, но у последнего на первом уровне есть фора в виде одного юнита. На 3-ем у игрока наоборот хандикап в одного юнита и победить гораздо сложнее (у меня около 15% побед на этом этапе). Затем идёт более рандомная версия Игра+.

Изначально был разработан другой план игры в виде «качелей» как в турнирной таблице, но в конце разработки я отказался от него, как от слабомотивирующего. Смысл был в том, что если какая-то команда проигрывает, то на следующей карте ей даётся +1 юнит, и так максимум до 10 против 6. Если и потом команда умудрялась проиграть, то её юнитам увеличивались характеристики.

Игра разработана на нативном javascript: на div-ах и css-стилях, и это было самое неудачное решение из возможных [2]. Это браузерная игра. Движок не использовался. Единственная цель проекта — создать сильного компьютерного игрока «с характером» и возможностью изменения этого характера (расчетливые киборги, агрессивные орки, коварные эльфы, глупые зомби).
Для уменьшения «компьютерного стиля» у противника были применены некоторые хитрости:

  • Игрок после своего хода не ждёт, пока ИИ подумает над своим ходом. Враг «сразу» начинает делать свои передвижения (в действительности это иллюзия).
  • Компьютерный игрок управляет юнитами тоже с помощью своего курсора (и это тоже иллюзия, курсор просто летает одновременно с анимациями юнитов).
  • ИИ умеет использовать коварные приманки, чтобы навязать бой (тут всё по-честному).

И что тут сложного?

Сперва может показаться, что тут все просто: можно просто перебрать все варианты всех ходов и выбрать наилучший. Но очень скоро становится очевидным, что всё очень даже непросто.Полный перебор невозможен из-за эффекта комбинаторного взрыва [3], который заключается в том, что по мере роста числа проверяемых элементов в сценариях сложность вычислений растет по экспоненте. Далее опишу, что это значит в моей конкретной игре.
Во-первых, т.к. на каждом ходу юниты команды ходят все сразу, то возможна разная их очередность. А при 6 юнитах в команде таких комбинаций становится 720 (1*2*3*4*5*6). Если юнитов будет больше, то комбинаций будет вообще огромное количество (при 7 — 5040, при 8 — 40320...). Если не учитывать максимального исхода, то игрок рискует распробовать удовольствие в ожидании очередного хода на 5-10 минут (а если он упорный, то задержка дорастёт и до миллионов лет, не каждый вытерпит). Именно из-за этой характеристики мой ИИ в начале боя менее эффективен, чем в конце. Ведь ближе к концу половина команды уже погибла.

Во-вторых, каждый юнит может передвинуться в разные точки карты. Бойцы с дальностью передвижения 4 могут походить на 1-41 разных позиций. У магов и лучников с их передвижением в 3 возможное число ходов равно 1-25. Например, состав команды может быть: 4 бойца, 1 маг и 1 лучник. Итого разных комбинаций ходов по данному пункту мы получаем: 41*41*41*41*25*25 = 1766100625. В действительности из-за взаимных пересечений и непроходимой местности комбинаций будет меньше, но в редкой ситуации «разбегания по карте» число комбинаций будет приближаться к этому числу.
В-третьих, каждый юнит после передвижения может пропустить ход или атаковать в одном из 4 направлений. То есть имеем по 5 возможных завершающих действий на юнита. Всего комбинаций: 5^6 = 15625.
Итого комбинаций: 720 * 1766100625 * 15625 = 19868632031250000.

И в каждой валидной комбинации надо будет рассчитать баллы результирующего состояния. В оценочную функцию входят: эмуляция передвижений, атака, нанесение урона, гибель юнитов и подсчёт оставшихся хитпоинтов у выживших. Конечно, число комбинаций завышено, т.к. в реальных условиях вариативность будет уменьшаться за счёт границ и препятствий на карте, однако это всё равно будет неподъёмное число комбинаций. А всё это происходит ведь в обычном браузере.

Как же сделано?

Чтобы решить подобную задачу, был использован эвристический подход, обобщённый алгоритм которого можно описать так:

  • Сгенерировать разные сценарии на основе заранее прописанных стратегий (~20 штук).
  • Пока есть время, проводить мутации сценариев, оставляя наиболее выгодные.
  • В конце выбрать сценарий с наибольшей оценкой.
  • Осуществить первый ход юнита из сценария, но остальными не ходить. Начать анимацию первого хода, и пока показывается анимация, продолжить улучшать сценарии для оставшихся юнитов.
  • Повторить для оставшихся юнитов с пункта 1.

Эвристический метод — это метод, который может сработать (по Макконнеллу [4]). Подробнее и строже в Википедии [5].

Ключевые моменты в этом алгоритме: генерация сценариев, мутации и правильная оценка выгодности состояния. В каждом из этих пунктов используются свои собственные локальные эвристики. Тем не менее, там где можно, использовались алгоритмы с гарантированным оптимальным результатом, например, А* для поиска пути [6].
Использованный мною эволюционный подход нельзя назвать полноценным генетическим [7], т.к. от него я использовал только мутации и выживание «сильнейшего», а коэффициенты влияния отдельных эвристик настраивал вручную. Алгоритмов формирования популяций и скрещиваний не применялось. После мутации выживает только один: либо мутант, либо родитель.

Нейронные сети [8] мною не использовались из-за особенностей задачи. Во-первых, из-за сложности их успешной реализации в условиях постоянно меняющейся среды (появление новых механик, навыков, способностей). Во-вторых, из-за сложности в их контролируемой персонализации (если захочется сделать два поведения: стремительного Суворова и осторожного Кутузова [9]).

Эволюция искусственного идиота в искусственный интеллект

0) Сначала у ИИ были введены только 3 стратегии со случайными ходами. {Сложность игры #0}. Оценка состояния была просто случайным числом. И так как ИИ не единственный элемент разработки, мне пришлось довольно долгое время мириться с поведением сумасшедших рыбок.
1) Затем в расчёты оценки стратегии были добавлены проверки оставшихся юнитов и их жизней у ИИ и у игрока. {Сложность игры #10}. За мертвого юнита команде начислялось 0 баллов. За полностью здорового Х баллов (например, 100 000 за бойца F, 70 000 за лучника A, 85 000 за колдуна W). За раненого начислялись 50% от основной ценности, а оставшиеся 50% пропорционально оставшимся жизням от максимальных. Благодаря этому ИИ было выгоднее добивать врагов, а если он мог только ранить, то он выбирал противников с меньшим числом жизней — более уязвимых.
Случайные ходы стали более осмысленными — ИИ иногда давал сдачи.
2) Затем была добавлена более осмысленная стартовая стратегия:
max_agro — все солдаты бежали максимально ближе к врагам и старались нанести как можно больше урона. {Сложность игры #20}. Одна стратегия использовала изначальный порядок ходов юнита, вторая ходила ими в обратном порядке.
ИИ стал вести себя так, как ведёт себя самый примитивный искусственный идиот в тактических играх. И довольно часто именно такой ИИ в тактических играх и используется. Он популярен из-за своей надежности и простоты. Такой даже может победить — но очень редко.
Именно на это похоже поведение ИИ в провальной игре Master of Monsters – Disciples of Gaia, из-за чего в неё банально скучно играть [10].

3) Дальше были добавлены стратегии, учитывающие возможный урон от врагов при передвижениях, и выбирающие те ходы, которые приводили к наименьшей опасности — желательно нулевой. {Сложность игры #30}. И ИИ сразу же стал сверх трусливым, избегающим любой близости с противником — лучше уж сбежать, чем атаковать и ранить, ведь противник может дать большей сдачи!
Поэтому в оценке состояний стал тоже учитываться возможный урон врагу. Штрафные баллы от потенциального урона от врагов стали вычисляться с уменьшающим коэффициентом 0.20 (коэффициент постоянно перенастраивался). Это заставляло ИИ при выборе между атакой или бегством избирать агрессивный вариант, поскольку он приносил в 5 раз больше баллов, чем бегство. Но ИИ всё равно надолго остался трусливым, ведь чтобы попасть в такую ситуацию выбора, враг уже должен быть в досягаемости, а сам ИИ при таких оценках никогда не подставит себя первым под удар. То есть не пойдёт на сближение. Конечно, игрок будет чувствовать себя обманутым, ведь у ИИ бесконечный запас терпения и он может убегать от опасности вечно, вынуждая игрока к агрессии.
Следует отметить, что подобные вычисления возможного урона очень длительны без использования кэша. Один полный просчёт стратегии без оптимизаций изначально занимал 700 миллисекунд. А у меня ведь ограничение на весь ход одним юнитом ~4000 мс! После оптимизаций и отработавших кэшей это время уменьшается до 20 миллисекунд при очень похожих стратегиях (к сожалению кэш невозможно просчитать весь заранее из-за эффекта комбинаторного взрыва, поэтому 20 мс достигаются не всегда).
Поэтому когда я внедрял технологию расчета с прогнозированием на несколько ходов вперёд, то время расчетов для глубины только в 2 хода (врага и ИИ) занимало уже +700 миллисекунд. В этом случае применяют оптимизацию с отсечением «слабых» веток. Если для этого пользоваться хоты бы примитивной стратегией max_agro, то увеличение времени было +30 миллисекунд и кэширование эту разницу почти не уменьшало (т.к. позиция на карте была совершенно новой).
В итоге я делал 5 разных заходов к разработке этого подхода, но в конце концов полностью отказался от него, т.к. мутации с эвристиками давали результат лучше и быстрее.
4) Следующие стратегии были направлены на расширение изначального разнообразия стратегий:
far_attack_and_hide — юниты стараются атаковать как можно дальше от противника, а если не атакуют, то прячутся от любой атаки.
close_group_flee — юниты отступают подальше от боя и группируются как можно ближе друг к другу. Если можно при этом безопасно атаковать врага — атаковать.{Сложность игры #40}.
Это улучшило процесс самого боя, но начало боя все равно было всегда невыгодно для ИИ: он постоянно отступал, но его можно было выманить на атаку и спугнуть так, чтобы группа ИИ разделилась на несколько мелких групп, которые можно было уничтожить по отдельности.
5) Затем настало время мутаций. {Сложность игры #50}.

Алгоритм мутаций был очень простой:

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

При этом стратегии аутсайдеры не удалялись, а также участвовали в мутациях, т.к. всегда была заметная вероятность очень успешной серии мутаций.
Сначала был реализован самый примитивный тип мутации: от 1 до 3 движений заменялись на случайные, порядок ходов оставался прежним. За одну итерацию расчетов в среднем на каждую стратегию создавалось ~5-15 мутаций. При этом в среднем каждая пятая мутация была более выгодной и заменяла стратегию родителя.
6) Эвристика приманки. {Сложность игры #60}.

Эта эвристика повторяла ту тактику, с помощью которой я выманивал ИИ на атаку одним юнитом, чтобы перебить его по одному. Этому трюку удалось научить и ИИ.
Для этого в функции вычисления баллов за состояние стратегии проверяется, соответствует ли текущее состояние ситуации приманки:

  • Только один солдат ИИ может быть атакован;
  • Только один враг может атаковать вылезшего юнита;
  • Юнит компьютерного игрока после этой атаки обязательно должен выжить;
  • Как минимум двое юнитов компьютера смогут атаковать в ответ. Чем больше таких наказывающих юнитов, тем больше баллов за эвристику.

Эффект оказался отличным: игроку становится легче начинать бой самому. При этом чаще всего игроку всё равно выгоднее «повестись» на эту приманку, так как после ответной атаки он сможет навалиться на ИИ всем своим отрядом (это если он разумно сгруппируется предварительно). А там уже всё решат грамотные локальные тактические решения.

7) Потом мне стало бросаться в глаза, что бойцы ИИ постоянно разбегаются как тараканы. {Сложность игры #70}. Также солдаты могли забиться в угол или зайти в тесные тоннели, в которых ИИ сильно терял в своей эффективности перебора возможных атак.Поэтому в оценочную функцию были добавлены эвристики оценки расстояний между юнитами и рельефа карты со следующими предположениями:

  • Чем ближе союзники друг к другу «в среднем» — тем лучше (юниты реже стали разбегаться по разным частям карты).
  • Чем ближе солдаты ИИ к в солдатам врага «в среднем» — тем лучше (мне нужен был наступательный ИИ).
  • Чем больше максимальное расстояние между любой парой союзников, тем хуже. При этом расстояние в 4 не штрафуется, а всё что больше — штрафуется по экспоненте (это прекратило вытягивание солдат в уязвимые шеренги).
  • Если солдат ИИ не может добежать и атаковать врага как минимум за 2 хода, то его надо штрафовать (это заставляет его наступать, но не подставляться самому под атаку).
  • Если в радиусе 2 шага от солдата слишком много блокирующих позиций, то штрафовать его (реже стали забегать в тоннели).
  • Если солдат находится на границе карты, то штрафовать его еще сильнее. В результате этого маневренность ИИ сильно повысилась, т.к. из открытой местности юнит может добежать в гораздо большее число позиций, чем из угла или тоннеля.

8) Затем пришло время расширения стратегий. {Сложность игры #80}. Я не мог добавить полный перебор возможного порядка ходов юнитов, но я мог сделать перебор их ходов по типам: боец, лучник, колдун. Поэтому появились стратегии последовательности ходов, вида W_A_F: сначала ходят все колдуны, потом все лучники, потом все бойцы.
Таким образом добавилось 6 новых стратегий: W_A_F, W_F_A, A_W_F, A_F_W, F_A_W, F_W_A. Они не решили всех проблем, но заметно улучшили качество игры.

9) У меня были мутации, но толку от них было мало. {Сложность игры #90}. В основном они улучшали слабые стратегии, а удачные улучшались редко. Поэтому мутации были доработаны и каждый раз срабатывал один из случайных типов мутации:

  • От 1 до 3 движений заменялись на случайные, порядок ходов оставался прежним (старый способ);
  • Поменять местами порядок ходов двух случайных юнитов. Действия их оставить прежними, даже если они не оптимальны. Если ход повторить невозможно, то он пересоздаётся случайно одной из обычных стратегий до валидного состояния;
  • Поменять местами порядок ходов двух случайных юнитов и пересчитать их ходы заново. Все поломавшиеся ходы у последующих юнитов чинятся случайными обычными стратегиями.

Ввод этих мутаций стал серьёзно компенсировать невозможность полного перебора всех комбинаций ходов юнитов. Хотя из-за своей случайности он не даёт никаких гарантий, что удачный ход будет найден за имеющееся ограниченное время.

10) Затем были добавлены еще полуслучайные стратегии. {Сложность игры #100}. Порядок ходов генерировался случайно, а сами ходы выбирались по следующим принципам (по уменьшению их важности):

  • нанести максимальный урон;
  • получить как можно меньший урон в ответ;
  • стать как можно ближе к врагам.

Заметного улучшения тут я не увидел, но проект уже перешел в ту стадию, когда каждое улучшение приводит к менее заметным воспроизводимым эффектам.

11) Мне надоели вопиющие ошибки ИИ, когда он при атаке своим колдуном сильно задевал моих солдат, но при этом ранил своих союзников. {Сложность игры #110}. Хотя перед этим он вообще-то мог походить ими и убрать их с линии огня. Поэтому была создана жёстко сгенерированная стратегия с ручными проверками:

  • если есть колдун, то найти место, откуда он нанесет максимальный урон;
  • если в этом месте или по пути удара есть союзники — запомнить их;
  • сначала ходят все союзники, которых запомнили, и они не могут становиться на зарезервированные колдуном позиции (то есть освобождают дорогу);
  • ходит колдун;
  • ходят оставшиеся юниты.

Стратегия легко описывается на словах, но заморочно для её программирования.

12) Иногда юниты "убегали в кусты" прямо перед началом боевых действий. {Сложность игры #120}. В результате этого, когда начинался обмен атаками, то один или даже два юнита могли оказаться слишком далеко от военных действий и не помогали союзникам. Если это случалось, то я почти гарантированно выигрывал у ИИ. Если не случалось, то я чаще проигрывал. Избавлялся от этого я вводом новой эвристики по оценке результирующих баллов у стратегии. Для каждого юнита проводилась проверка:

1. Если юнит в этот ход атаковал, то он получал +1500 баллов.
2. Если не атаковал, то подсчитывались позиции, с которых враги смогут наносить урон союзникам. Продолжать подсчет, если таких позиций будет больше 0 (N > 0).
2.1. Если юнит не может достать и ударить ни по одной позиции (n = 0), то он получает штраф -1000 баллов.
2.2. Если юнит может достать до всех позиций, то он получает +1200 баллов.
2.3. Если юнит может атаковать до некоторых позиций, то он получает +(n/N)*1000 баллов.Это позволило сильно улучшить «сплоченность» юнитов ИИ. К сожалению, начали появляться случаи «одного дезертира», когда в проигрышной ситуации один из раненых юнитов предпочитал прятаться за спинами своих товарищей вместо того, чтобы внести свою лепту, атаковав врага. Это нелепо выглядело, когда у компьютера остаётся всего 2 юнита, а у игрока 3 или даже больше. Дополнительная исправляющая эвристика представляет собой следующее правило:

IF ("у ИИ меньше юнитов, чем у противника" AND "у ИИ не больше 3 юнитов") THEN "за каждого дезертира начислить сценарию штрафные баллы"

13) Под конец ввода стратегий их набралось уже под 25 штук. {Сложность игры #130}.
Мутировать каждую из них стало уж слишком накладно. Поэтому было принято решение удалять самые неудачные и оставлять только 8 штук. С самого начала я не хотел использовать этот подход в расчете на то, что мутация аутсайдеров может привести к неожиданному отличному результату, вместо простого хорошего. Ввод данной обработки в итоге привел к улучшению игры ИИ.

14) Примерно в начале была ещё интересная доработка. Изначально оценка ценности сценария вычислялась как разница сумм баллов:

Итоговые_баллы = Баллы_ИИ - Баллы_игрока

Но спустя несколько улучшений я вспомнил, что это не самое лучшее решение, т.к. тогда для ИИ будут одинаковыми ситуации «2 солдата против 1 одного солдата» и «4 солдата против 3 солдат». Поэтому баллы стали вычисляться как отношение:

Итоговые_баллы = Баллы_ИИ / Баллы_игрока

Изменение небольшое, а результат очень серьезный. Без доработки цена ошибки при повышенном риске всегда была одинакова. После доработки ИИ стал меньше безалаберно рисковать к концу сражения, и это заметно усилило его.
Хочу отметить, что все эти доработки вводились постепенно хоть и в указанном порядке, но многие из них улучшались, перерабатывались и исправлялись от багов в более хаотическом порядке. Реальных итераций было больше 100 штук.
Вот как играет финальный ИИ {Сложность игры #9999}:

ИИ ходит сразу, а не тратит время на раздумья

Для ускорения самих вычислений активно использовались оптимизации алгоритмов в виде разбиений вложенных циклов на последовательные циклы (уменьшение сложности) и внедрение нескольких массивов с кэшированными предварительными вычислениями (и последующей оптимизации еще этих самых кэшей). По моим прикидкам дальнейшие оптимизации смогли бы мне обеспечить еще двойной (или даже больший) прирост к скорости, но это бы привело к неоправданному росту временных затрат и дальнейшей ещё большей потери читаемости кода.

Основная технология быстрого хода — это предварительные вычисления во время простоя. Этот метод заключается в том, чтобы разбить процесс хода на 2 части: сами вычисления и показ анимаций результатов вычислений:

  • вычисления хода первого юнита начинаются сразу же после хода игрока, пока еще вылетает окошко, что сейчас начнётся ход противника. А это целых 4 секунды, которые игроком не воспринимаются пустым ожиданием;
  • вычисления второго и последующего ходов начинаются тогда, когда только начинается анимация хода прошлого юнита (то есть когда курсор ИИ только начинается своё движение). А время всех анимаций уже 4.5 секунды. Хотя правильнее это назвать не вычислением следующего хода, а улучшением уже выработанной прошлой стратегии и поиска новой, т.к. на каждой итерации рассчитываются ходы всей команды;
  • при анимации ходов ИИ к двигающимся юнитам летает курсор ИИ, который притворяется, что он по ним кликает. Курсор летает максимально быстро, но чтобы оставалась комфортность слежения за ним. Более того, добавление курсора не только позволило увеличить запас времени вычислений с 2 секунд до 4.5, но и сделал просмотр хода компьютера более комфортным для человека;
  • время хода игрока тоже не теряется впустую. Пока игрок думает, то вычислений почти никаких не производится, поэтому в это время усиленно просчитываются возможные кэши для будущего хода компьютерного оппонента.

Чтобы всё это не лагало в браузере и работало с достаточно стабильным FPS, расчёты производятся асинхронно воркером (Web workers) [11].
Этим я хотел избавиться от раздражающего окошка ожидания «Компьютер ходит». Такая неприятная плашка есть во многих хороших играх, например, в Xenonauts [12]. Я считаю, что мне удалось справиться с этой проблемой.

Таким образом, ИИ тратит на обдумывание своего хода всегда одинаковое время — независимо от его сложности. Очень любопытная особенность этого подхода в том, что чем сильнее у игрока компьютер, тем большее число мутаций ИИ успеет перебрать, а значит будет тем сильнее, чем мощнее компьютер игрока. Я сначала убрал данный эффект с помощью фиксации времени хода и предварительного подсчета скорости работы компьютера. Однако потом я убрал эту фиксацию, т.к. владельцам мощных компьютеров это позволит сразиться со «своим» компьютером, а не усреднённым.

Каков результат и в чём недостатки

Таким образом, получившийся компьютерный противник умеет достойно сражаться и хорошо пользуется любыми оплошностями игрока, а своих делает не слишком много. Тем не менее, я, зная все особенности его работы, хоть и с напряжением, но побеждаю его почти всегда (при равных условиях). А хотелось бы наоборот: чтобы даже зная о его особенностях, почти всегда ему проигрывать. ИИ далёк от идеала, поскольку используемый мною набор эвристик приводит к синергетическому наложению «ошибок моего восприятия» друг на друга. Вот эти ошибки:

  • Несовершенство и неполнота моей собственной стратегии, я не знаю всех наилучших стратегий, и поэтому не могу их обозначить и внедрить в игру.
  • Потеря эффективности (которая итак не идеальна) выработанных рабочих эвристик при переносе их на программный код. Например, моя человеческая эвристика «Юниты держатся рядом, но не слишком близко, чтобы избегать двойного урона от магов и не застрять в узких проходах». Эта эвристика помогает мне побеждать ИИ, но при обучении ею моего компьютерного оппонента, мне приходится качественное описание переводить в алгоритмическое с количественными оценками, и тут возможна потеря данных.
  • Взаимные конфликты между эвристиками. Когда эвристик слишком много, они постепенно начинают накладываться друг на друга. В результате этого может произойти неожиданное усиление из-за скрытого двойного учёта или частичного дублирования. Либо какая-то эвристика перестанет на что-либо влиять, т.к. её вклад полностью перекрывается большими коэффициентами конкурирующей.
  • Жесткие временные ограничения и пошаговые улучшения выбранных стратегий приводят к тому, что первый ход всегда будет менее продуман. Это значит, что один неудачный первый ход может заблокировать очевидные более эффективные ходы остальных юнитов команды. Это выражается в том, что первый боец F вместо отхода может криво атаковать противника и потом его союзнику волшебнику W придётся ранить своего, чтобы добить противника.

Полноценные генетические алгоритмы вместо «подбора на глазок» скорее всего позволили бы подобрать более оптимальные коэффициенты в эвристиках. Но это уже задача для будущих полноценных проектов — не хочется надолго застревать с прототипом. Текущим ИИ я вполне доволен: он расчётливый, немного коварный, достаточно агрессивный и не позволит игроку победить себя в сухую (в действительности чрезвычайно редко позволит).

Дополнительные возможности

Подобный способ реализации позволяет добиться дополнительных бонусов в игровой разработке (во многом с точки зрения разработчика и его горящих сроков):

  • Появление новых механик в игре не разрушит силу компьютерного игрока, хотя и будет постепенно его ослаблять по сравнению с игроком. Это ослабление может компенсироваться вводом дополнительных эвристик. Чтобы это не приводило к прогрессирующим расходам ресурсов, применять эти новые эвристики можно только при наличии этих новых механик в текущем сражении.
  • Действительно интеллектуальные уровни сложности. Сейчас в основном уровень сложности определяет то, какие бонусы компьютерный игрок получит в качестве ресурсов (больше золота на старте или бонус в добыче) или как сильно его солдаты будут бить (+50% к урону). Это работает, но можно ведь сделать ИИ чуть менее умным просто постепенным отключением некоторых эвристик по мере уменьшения сложности.
  • В продолжении 2-го пункта можно создавать и разные расы/фракции компьютерных противников: у орков работают только агрессивные стратегии; у толп зомби только примитивные «бежать вперед и атаковать»; а у киборгов использовать всю мощь ИИ. Благодаря этому игроку перед нападением придётся оценивать не только числа у противников, но и их интеллектуальность.

Всё это многообещающе звучит, но следует помнить, что все это красиво на бумаге, а в реальной игре это может просто не сработать, оказаться неинтересным или даже незаметным для игрока. Но это хороший повод для экспериментов.

Где пощупать

Вы можете протестировать силу этого ИИ в браузерке «AI tactical rumble. Test subject» бесплатно на площадках типа itch.io [13]. GET параметр ai (значения от 0 до 140 с шагом 10) позволит снизить сложность ИИ.
По моим ожиданиям победить ИИ на равных условиях Вам будет очень и очень сложно. Даже после привыкания к правилам игры. Я рекомендую рассматривать данную игру, как прототип, каковым она по сути и является (музыки, звуков и цены в ней нет).
Пожалуйста, оставляйте своё мнение в комментариях об интересности ИИ, советы и критику о возможной реализации ИИ с помощью различных методов обучения. Если Вам вдруг стали интересны другие мои изыскания, пожалуйста, рассмотрите возможность подписки здесь на мой аккаунт.

Список литературы

Материал опубликован пользователем.
Нажмите кнопку «Написать», чтобы поделиться мнением или рассказать о своём проекте.

Написать
{ "author_name": "Denis Anohin", "author_type": "self", "tags": ["9999","90","80","70","60","50","40","30","20","130","120","110","100","10"], "comments": 67, "likes": 136, "favorites": 347, "is_advertisement": false, "subsite_label": "gamedev", "id": 91889, "is_wide": false, "is_ugc": true, "date": "Wed, 08 Jan 2020 18:28:28 +0300", "is_special": false }
0
67 комментариев
Популярные
По порядку
Написать комментарий...
14

Наконец-то что-то стоящее в 2020

Ответить
7

Long story оооочень большой труд

Ответить
7

Спасибо. Несколько затянуто получилось (и от этого скучновато), но поможет примерно оценить, сколько времени может занимать разработка даже самого простого ИИ.

Ответить

Центральный историк

Denis
3

На Хабре тоже ваш текст?

Ответить
3

Пропустил ходов 10, но комп так и не стал атаковать. Вообще, я понимаю, что это скорее всего оптимальные ходы, чтобы никаким ходом не подставляться, но есть опасность что играть так будет скучно.

Напоминает Lords of the Realm II :)
Играл очень давно, но помню, что там в самом начале битвы комп окружал своих лучников крестьянами, и они типа стояли и ждали чтоб я напал. Ага, щас. Я же тоже не дурачок.

Ответить
0

Обычно комп старается выманить игрока, подставляя под удар одного своего юнита.

Ответить
2

Можно было бы добавить в правила элемент, который сделал бы затягивание невыгодным, добавить смысл битвы. Например занятие центра карты давало бы бонусы защиты или реген хп, появление случайных бонусов тоже ближе к центру карты, чтобы их захват провоцировал борьбу. Ведь по факту - не воевать это и есть лучшая стратегия, а вы искусственно заставляете ИИ воевать ни за что. А так статья понравилась, сам недавно писал шахматный ИИ, но там все примитивно)

Ответить
0

Тут уже вопрос скорее в том, как подавать такую игру. Возможно, не везде в играх, где АИ кажется тупым, он прямо тупой, может быть ему просто запрещено затягивать игру.

У меня вот так выглядит поле после 10 ходов. Может, какой-то юнит и подставлялся, пока они ходили, но мне это было не заметно.

Ответить
0

Как сделать не тупой ии. Нужно под видом вражеского ии стравливать двух живых игроков :3

Ответить
0

Так вот почему у меня получалось расстреливать врагов по одному без получения ответного урона. Думаю комп одидает что будет нападение файтерами, а не арчерами и визардами

Ответить
0

Игра полностью детерминирована, то есть в ней нет элемента случайности (шанс попадания 100%, никаких критических уронов и т.п.). Также это игра с полной информацией, то есть соперники всё знают о состоянии войск друг друга в любой момент времени. Как в шашках.

так в чем проблема ? Алгоритмы используй те же что и в шахматах — мощь ии будет определяется длиной прогнозируемых ходов , на примере тех же шахмат алгоритмы прогнозирования хода давно уже все вычислили и разобрали

Ответить
7

Вы, кажется, забыли написать, что это очень просто и делается за пару вечеров.

Ответить
1

Делается долго , в железе , а алгоритмы просты — изобретать велосипеды конечно  весело — но данные вопросы были разобраны математиками очень подробно еще в 1950 х . 

Ответить

Далекий историк

Голубев
1

Только вот шахматные программы помимо этого опираются на мощный аналитический аппарат изучающих шахматы, на базы дебютов, миттельшпилей и эндшпилей, на шаблоны игры известных шахматистов. Откуда всему взяться у этой игры?

Ответить
1

От ии в играх требуется "Красиво проиграть" 

Это потом уже можно пилить Deep Mind - с этими эндшпилями и выбором идеального старта.

В самом простом случае в пошаговой игре  Алгоритмы поведения - интеллекта и его "Характер" задается выставлением коэффициентов на приобритение / потерю - Фигур. И на коэффициенты множителей от координат.
Условный берсеркер - предпочтет ходы которые позволят занять центр карты, и будет атаковать игрока - не считаясь с потерями.
А условный трус - жаться по краям и выбирать те ходы которые видут к минимуму потерь. 

Ответить
2

Собственно — суть в том что интеллект ии — определяется длиной прогнозируемого хода — и и выбирает ту линейку ходов (на конце своего прогноза ходов) которая принесёт максимум очков и минимум потерь . В тех же шахматах — максимум — это мат — ликвидация короля — а ценность других юнитов — мериться в условных пешках : офицер : 3 пешки, конь : 3,5 , ладья : 5 фигур , ферзь 9 пешек. А сама пешка тем ценнее чем ближе к становлению ферзем .

соотвественно чем выше Настройки интеллекта тем более длинный диапазон ходов сможет насчитать . 
Новичок : длина видимой дистанции 1—3 хода. Среднячок 5—10 , профессионал : 20+  цифры условные — но такие же алгоритмы можно применять и к другим пошаговым играм — где ход должен выбираться из тех условий которые принесут минимум потерь и дают максимум урона по вражеским фигурам  . 

Ответить
0

Глубина 5-10+ это очень долгая задача. Поле ведь не одинаковое, а каждый раз новое.

Ответить
1

Принципиальной  разницы нет c точки зрения математики — мешают пройти свои / чужие фигуры или свойства рельефа . 

К тому же поле — наверняка заедается одно  на старте битвы — вот с этого момента и и должен обсчитывать ходы . 

Ответить
0

Ну так скрипт и делает. Может я структуру для хранения данных выбирал неправильную, т.к. для хранения больших расчетов не хватит оперативной памяти. Безусловно, я понимаю, что мой велосипед не так оптимизирован, как мог бы.

Ответить
2

Да ничего страшного , удачи вам . Но освежить знания по алгоритмам работы с шахматами все же стоит , если цель именно игра с открытой информацией — и детерминированным циклом ходов , таких статей куча :  https://habr.com/ru/company/skillbox/blog/437524/

Ответить
0

Громадное спасибо.

Ответить
2

Отличный пост! 

Сам пытался что-то сделать на JS в канвасе. Но канвас как-то не пошел. Дальше отрисовки разных графиков и генерации синусоид, дело у меня как то не пошло.

Ответить
1

Для канваса чаще используют дополнительные движки/библиотеки. Например, pixi js хороша. У меня еще проще - без канваса, на дивах.

Ответить
0

Кстати да, я в итоге на дивах морской бой с компом сделал. 

Вышло очень быстро, и выглядело хорошо.
Жаль, я его в гит не закинул, а потом случайно папку удалил =(

Смотрел разные движки, но pixi js  не видел. Спасибо, мб дойдут руки в выходные.

Ответить
2

Огромное спасибо за подробную статью! Как себя ведет ИИ мне очень понравилось.

1. Сколько в итоге вышло кода? Хотя бы примерно в строках.
2. Можете, пожалуйста, привести примеры других подобных игр с сильным ИИ?

Ответить
1

1. ~8500 строк кода

2. Они, конечно, есть, но с ходу вспомнить не могу. В Conquest of Elysium 3 / 4 хорош (хотя больше в стратегическом плане, в тактических столкновениях его можно успешно блокировать единичками).

Ответить
1

Поделись инсайдом: сколько все это времени заняло? 

Ответить
2

Все работы, связанные с разработкой и публикацией: 252 часа. Сам в шоке от такого числа.

Ответить
2

41 рабочий день (по 6 часов) - норма для среднего размера фичи в мобильном геймдеве. 

Ответить
0

Тоже верно, но это скорее для уже крупных проектов.

Ответить

Добровольный яд

1

Текст промотал, не для моих жидких мозгов, но гифка с геймплеем понравилась. 

Планируете графоний к прототипу прикрутить или это просто эксперимент?

Ответить
2

Нет - это законченный прототип.

Но планирую в будущем сделать игру с подобным подходом.

Ответить

Добровольный яд

Denis
1

Сижу залипаю в прототип, отличная штука вышла, имхо с должной полировкой из этой концепции может выйти что-то не хуже Into the Breach.

Я бы с удовольствием порисовал бы бесплатно для такой игры. Правда я ни в пиксельарт не умею, ни в анимацию, если делать растр как в DD. 
Но если заинтересует, пишите (можно в вк, можно на почту fed0tfedotich@gmail.com), могу концепты как минимум накидать.

Ответить
0

Написал, почту можно прятать из коммента.

Ответить

Добровольный яд

Denis
0

Да она у меня все равно в открытом доступе, рабочая, со спамом вроде бы гугл справляется.

Ответить
1

С буквами прикольно, трупы врагов составляют слово, игрок получает очки

Ответить

Добровольный яд

Denis
0

Слушай, а какой сейчас у тебя в прототипе размер клеток и навскидку насколько их можно увеличить, чтобы игра в окошке нормально игралась без масштабирования на большинстве распространенных разрешений?
 
Я так понимаю если за минимум взять ноутбуковские 1366х768, то больше чем 70х70 клетку не сделать?
А то решил я тут наскетчить мокапчик графики для твоего прототипа в духе карточных игр вроде БерсеркОнлайн.

Ответить
0

Зависит от девайса для запуска. 

Для ПК сойдет и разрешение 64*64, а для мобильных и 70*70 будет мелковатым.

Ответить

Добровольный яд

Denis
1

Ну просто для меня все что меньше хотя бы 200х200 уже в категории пиксельарт, но я понимаю что без масштабирования или прокрутки поля боя это на маленькие мониторы не влезет, поэтому и спросил.

Ответить
0

Минимальный комфортный размер клеток в смартфонах, например, в игре Hoplite. Все, что ниже - уже приводит к постоянным промахам. Большепальцевые люди наверное вообще бесятся от этого.

Ответить
1

Я, наверное, тупой, но не понял, как закончить ход. Можно прикрутить хоткей на пробел?

Ответить
1

Хорошего GUI не завез, т.к. это просто прототип.

Ход заканчивается автоматически, если походить всеми своими юнитами (у которых остались голубые кружки вместо серых).
Чтобы пропустить ход, нужно нажать на своего юнита несколько раз.
Можно завалить своих союзников.

Ответить
2

Ну сделай как в Героях конец хода на пробеле, пап. Мне то интересно, как комп ходит, а не как я.

Ответить
0

Надо два раза нажать на всех своих юнитов. Кнопка конца хода нужна, да.

Ответить
0

Либо я тоже не понял, где она.

Ответить
0

Все правильно - её нет (хотя с ней было бы лучше)

Ответить

Безопасный Артем

1

Прикольно, но выиграть не получается: и я, и ИИ — полные сцыкло, так что не хотим подставлять своих юнитов и вечно прячемся по укрытиям :(

Ответить
1

Есть выигрышная стратегия - подставить одного своего юнита под один возможный удар, максимум два. 

ИИ нападёт и станет уязвим для уничтожения.

Ответить
1

Очень крутая штука. Первый уровень с второй попытки прошёл. Второй с 4-ой вроде и третий эксперементальный со второй. Иногда бесило что враги слишком прячутся, но в остальном хорошо. Не заметил чтобы они совершали глупые ошибки и очень разумно ходят чтобы все смогли атаковать и прикрыться.

"GET параметр ai (значения от 0 до 140 с шагом 10) позволит снизить сложность ИИ" - вот это не понял, где вводить?

Ответить
1

GET параметр вводить в адресной строке браузера (это своего рода читы). 

Можно и не вводить, а просто переходить по ссылкам {сложность ...}, которые я разместил по ходу статьи.

Ответить
1

Вроде проходится левой пяткой. 

Иногда вместо того что бы напасть и подороже продать юнитов - пытаются отступить и игрок получает возможность - догнать и поколотить вражеских юнитов - даже если у них преимущество по численности

Ответить
1

". Тем не менее, там где можно, использовались алгоритмы с гарантированным оптимальным результатом, например, А* для поиска пути"

Я прошу прощения, но если я правильно помню, то A*, вообще говоря, оптимальный путь не гарантирует, всё зависит от эвристической функции. Или я где-то ошибаюсь?

Ответить
1

Это "быстрый поиск пути" не гарантирует оптимальный путь. А* гарантирует оптимальный, поэтому его чаще всего и используют (есть ещё прыжковый алгоритм, во многом основанный на А*, но это уже посложнее будет). Тем он и лучше алгоритма Дийкстры (хотя для поля 4*4 можно и его использовать).

По ссылке на редблоб есть интерактивные примеры срабатывания алгоритмов.

Ответить
1

Полезная статья. Спасибо!

Ответить
1

Статья отличная, правда я не все прочитал) Вернусь когда решу проапгрейдить ИИ в своей игре

Ответить
0

Благодарю. Для этого можно использовать кнопку "Подписаться"

Ответить
1

Если тут есть представитель Decovir Entertainment: возьмите этого парня к себе, а то в вашей Craft The World всё очень плохо с ИИ.

Ответить
1

Мощно
Действительно стоящий лонгрид по огромной проделанной работе

Ответить
0

странно,что я читаю данную статью на дтф -)

Ответить
0

чтобы ии выигрывал, нужно перебирать ходы по порядку все варианты а не случайно при этом на каждый ход соперника запоминается лучший ход из всех вариантов тогда ии будет выигрывать, а чтобы выиграть ии нужно на каждый лучший ход выбранный по процентам ии делать такой ход который из всех вариантов ходов ии имел бы хоть один выигрышный ход на каждом ходе из всех вариантов хоть один ведущий к выигрышу 100%, т.е ии выбирает больший процент ходов ведущие к выигрышу, а чтобы победить ии нужно выбрать хоть 1 ход но 100% ведущий к выигрышу на каждом пути

Ответить

Прямой эфир

{ "jsPath": "/static/build/dtf.ru/specials/DeliveryCheats/js/all.min.js?v=05.02.2020", "cssPath": "/static/build/dtf.ru/specials/DeliveryCheats/styles/all.min.css?v=05.02.2020", "fontsPath": "https://fonts.googleapis.com/css?family=Roboto+Mono:400,700,700i&subset=cyrillic" }