Всем привет! В этой статье я хочу кратко изложить ключевые моменты своей стратегии в ходе прошедшего соревнования по программированию искусственного интеллекта Russian AI Cup.

Немного о Russian AI Cup

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

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

Правила можно найти здесь.

Немного обо мне

Мой профиль – Leos.

Я принимал участие в подобном мероприятии второй раз.

Первый опыт был в 2015 году – Russian AI Cup 2015, CodeRacing. Тогда все, чего я добился – это попадание во второй раунд. И на этом все могло закончиться и никакой истории не было бы, но однажды на Хабре наткнулся на статью одного из призеров, которая в корне изменила мое представление о том, что надо было делать. С того момента я ждал следующей возможности принять участия в подобном евенте.

2016 год пришлось пропустить – армия.

В этом соревновании я начал участвовать практически с самого запуска открытого бета-теста.

Стратегия

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

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

Второй стратегией стали маленькие бутербродики (большой бутер разбивал на 10 групп). Истребители по-прежнему действовали самостоятельно.
Вот несколько примеров, как она работала против разных стратегей противников в первом раунде:
У противника несколько групп: russianaicup.ru/game/view/106992
У противника бутерброд: russianaicup.ru/game/view/124483

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

Но недостатки оказались существеннее:

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

Третьей стратегией стало использование 5 групп, как есть. Наверное, это самая оптимальная стратегия разбиения войск, поскольку большинство участников финала к этому и пришли.

Очередность хода

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

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

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

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

Выбор приоритетных групп на основе разности потенциалов

Потенциалы рассчитывал для всех своих групп.

Перебирал 64 разных направления. Сначала формула:


где – потенциал группы в центре,
– потенциал в k-ой точке,
– количество тиков, необходимых для того, чтобы добраться до k-ой точки.

Собственно, – это относительная разность потенциалов. Её я рассчитывал для каждого направления. Точки – это просто некоторые точки на этом направлении удаленные на заданное расстояние.

По этой же формуле я рассчитывал относительную разность потенциалов для текущего направления движения – .

Самой приоритетной считал группу с максимальной разностью .

Расчет потенциалов

Основной упор я сделал именно на подбор потенциалов. По сути здесь должно быть много математики, но я напишу только суть:

Было 3 вида потенциалов:

• Сильно убывающий (задавался экспонентой)
• Средне убывающий (задавался )
• Слабо убывающий (задавался )

Было 4 объекта генерирующих потенциалы:

1) Границы карты

Сильно убывающий, отталкивающий потенциал, чтобы не загоняться в угол, не врезаться в края карты.

2) Союзные юниты

• Сильно убывающий, отталкивающий потенциал, для групп, которые могут столкнуться.
• ARRV генерировали средне убывающий, притягивающий потенциал, для отхила воздушных групп.
• TANK и ARRV генерировали средне убывающий, притягивающий потенциал для FIGHTER.
• IFV генерировали средне убывающий, притягивающий потенциал, для HELICOPTER.

Здесь два последних потенциала были добавлены с введением тумана войны, чтобы воздушные войска по умолчанию прикрывали наземные.

3) Вражеские юниты

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

4) Сооружения

Слабо убывающий потенциал, про коэффициент для которого я напишу подробнее.

Захват сооружений

Я рассчитывал коэффициенты от каждого сооружения для всех своих групп. Акцент сделал на следующие вещи:

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

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

Производство техники

Тип производимой техники определялся с помощью симулятора сражения.

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

Симулятор сражения

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

В сражении принимают участие 2 группы. Считаю их полное здоровье и урон с учетом всех особенностей (земля/воздух, тип техники, отхил ARRV).
После этого запускаю итеративный процесс. Урон на каждой итерации пропорционален текущему здоровью. Здоровье на каждой итерации убывает на величину урона противника.
Количество итераций в последней версии было 10.

В целом работало неплохо и в проигрышные стычки мои юниты не лезли.

Кластеризация

Естественно нужно было определять группы противника. Здесь я сделал простой алгоритм в качестве заглушки, который до конца со мной и остался.

Разбивал область на тайлы 8х8, и, если в соседних тайлах есть вражеские юниты на расстоянии меньше 9, то объединял их в одну группу.

Аппроксимация групп противника

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

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

Туман войны

Ничего особенного с введением тумана войны придумывать не стал. Запоминал позиции противника, добавил дополнительные потенциалы, чтобы воздушные войска прикрывали наземные.

Визуализатор

С визулизатором сильно заморачиваться не стал. Отрисовывал только потенциальные поля. И при анализе игр использовал его совместно с локал раннером.

Добавлю несколько примеров, чтобы были картинки.



Здесь жирное зеленное пятно — это мои вертолеты, и потенциальное поле построено для них.

Синий цвет соответствует положительным потенциалам, красный — отрицательным, черный на красном фоне — очень большим по модулю отрицательным.

Справа-снизу три наземные группы противника, которые притягивают мои вертолеты. В центре истребители противника, которых мои вертолеты боятся. Большое черное пятно — мои истребители, с которыми нельзя сталкиваться.



Ещё один пример, в котором действующее лицо — мои IFV. Здесь все группы противника, а также два справа являются положительными зарядами.

Черные пятна соответствуют местам, в которые нежелательно перемещаться из-за столкновений со своими группами. Левое нижнее сооружение не оказывает никакого воздействия, так как группа ARRV уже выдвинулась его захватывать.

Оба примера взяты из этого боя — russianaicup.ru/game/view/310222, 730 и 1800 тики соответственно.

Код

Вот ссылка на мой репозиторий.
Писал на Java. Качество кода – какое есть, когда писал я не предполагал, что его кто-то увидит. Ну и я не джавист, курсы по Java проходил как раз одновременно с аи капом.

И все?

Итого: много костылей и заглушек, никаких заумных алгоритмов.

Получилось совсем без эмоций и суховато, но надеюсь кто-нибудь найдет для себя что-нибудь полезное.

P.S. Чуть не забыл, всех с Новым Годом! :)

Update: Исправил формулы, чтобы были видны на мобильном телефоне.