[Из песочницы] История 3 места Russian AI Cup 2017
Всем привет! В этой статье я хочу кратко изложить ключевые моменты своей стратегии в ходе прошедшего соревнования по программированию искусственного интеллекта 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 разных направления. Сначала формула:
$$display$$RRPD = \frac{max (P_k — P_c)}{dT}$$display$$
где $inline$P_c$inline$ — потенциал группы в центре,
$inline$P_k$inline$ — потенциал в k-ой точке,
$inline$dT$inline$ — количество тиков, необходимых для того, чтобы добраться до k-ой точки.
Собственно, RPDD — это относительная разность потенциалов. Её я рассчитывал для каждого направления. Точки $inline$P_k$inline$ — это просто некоторые точки на этом направлении удаленные на заданное расстояние.
По этой же формуле я рассчитывал относительную разность потенциалов для текущего направления движения — RDPD.
Самой приоритетной считал группу с максимальной разностью RPDD — RDPD.
Расчет потенциалов
Основной упор я сделал именно на подбор потенциалов. По сути здесь должно быть много математики, но я напишу только суть:
Было 3 вида потенциалов:
- Сильно убывающий (задавался экспонентой)
- Средне убывающий (задавался 1/r^2)
- Слабо убывающий (задавался 1/r)
Было 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. Чуть не забыл, всех с Новым Годом! :)
