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

Анонс и первые впечатления

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

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

Начало работы

Итак, изначально нам были доступны 5 видов войск по 100 единиц: танки — мощный, но медленный юнит, БМП – более мобильный юнит, подходящий для уничтожения авиации, БРЭМ – ремонтные машины, беззащитные к атакам врага, вертолеты – мощное оружие против танков, но крайне уязвимые перед истребителями и истребители – быстрые, но опасные только для вертолетов. Среди доступных действий было выделение, снятие выделения, добавление в группу и исключение из нее, а также вращения и сжатие. Для стратегии было доступно лишь 12 действий в 60 тиков.

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

Чтобы хоть как-то начать, я слегка модифицировала быстрый старт (Smart guy), предоставленный организаторами. Стартовая стратегия представляла собой следующее: раз в 300 тиков для каждого вида техники получали центр формации по усредненным координатам всех юнитов, выбирался один предпочитаемый тип техники-цели, группа выделялась и получала вектор направления в сторону цели. БРЭМ направлялись просто в центр карты.

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

К этому моменту в песочнице были популярны стратегии вида «торнадо» — техника всех видов стягивалась к одному центру и закручивалась для уплотнения. А затем появилась более совершенная техника, которую участники окрестили «бутербродом» — войска уже смешивались не абы как, а чередующимися ровными рядами. В результате получался очень мощный строй, так как разнородная техника прикрывала друг друга, а БРЭМ устраняла повреждения. Такие «бутерброды» в считанные тики поглощали «торнадо», не говоря уж о моих бестолковых однородных отрядах. Такой поворот меня весьма огорчил. Сражаться с «бутербродами» отдельными отрядами казалось было бесполезно, а играть в «пятнашки» со стартовым случайным расположением отрядов и хардкодить формирование «бутерброда» мне совсем не хотелось. В результате я снова на пару дней забросила стратегию.

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

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

• Кластеризация с параметрами eps=17 и minPts=5 (минимальное расстояние на котором точки считаются соседями и минимальное количество соседей для точки, при котором точка может быть включена в кластер).
• В результате работы кластеризации получался набор кластеров, а также шум — точки, которые не получилось включить в кластер по заданным параметрам. Шум кластеризировался еще раз, но с minPts=2 для обнаружения мелких групп.
• После второго прохода также оставался шум — единичные юниты. Их я уже просто добавляла каждого в свой кластер.
• Найденные кластеры помещались в группы — объекты, которые по мере добавления единиц техники вычисляли собственный центр массы, а также координаты прямоугольника, в который была вписана группа для ее выделения.

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

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


Кластеры, раскрашенные в разные цвета

На мой взгляд, управление группами получилось довольно удачным. Группы могли сколько угодно рваться или объединяться — новые формации тут же получали управление без каких-либо дополнительных усилий с моей стороны. Даже коллизии разнородных групп через какое-то время успешно разрешались самостоятельно.

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

delayedMoves.add(move -> {
    move.setAction(ActionType.CLEAR_AND_SELECT);
    move.setRight(world.getWidth());
    move.setBottom(world.getHeight());
    move.setVehicleType(vehicleType);
});
delayedMoves.add(move -> {
    move.setAction(ActionType.MOVE);
    move.setX(targetX - x);
    move.setY(targetY - y);
});

Было это не очень удобно, поэтому пришлось разработать систему работы с действиями. Создание команды на движение у меня получилось таким:

Action.moveTo(group, targetX, targetY);

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

Работой с действиями занимался ActionManager. На раннем этапе он представлял собой очередь с приоритетом, куда каждый тик, с доступным действием помещались команды для каждой из групп. Менеджер удалял команды исчезнувших групп, заменял старые цели в очереди на более актуальные. Также для каждой группы хранилось последнее выполненное действие и, если вновь поступающее действие имело схожий угол направления и близкую цель со старым действием, новое действие в очередь не добавлялось. Предполагалось, что это поможет сэкономить доступные ходы. Этот менеджер вышел довольно примитивным; сложные цепочки команд или отложенные действия он выполнять не умел. Поэтому в дальнейшем более сложные действия приходилось обрабатывать на более высоком уровне.

Итак, у меня было 1100 строк кода, кластеризация, группы, удобное управление, менеджеры и… логика Smart guy и совершенное непонимание, что со всем этим делать.

Потенциальные поля

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

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

Нужная информация нашлась в этой диссертации. В этой работе в числе прочего рассматриваются различные модели предсказания результатов исхода битв в RTS. В эксперименте авторов лучшие результаты показала Target-Selection Lanchester’s Square Law Model, давшая 94.45%± 0.34 верных предсказаний. Такой результат меня вполне устраивал, к тому же расчеты примерно совпадали с моей «бумажной» симуляцией. По сравнению с реальной игровой ситуацией модель была упрощением, так как не учитывала плотности формации, дальности стрельбы, кулдаунов и т. п., но я посчитала, что на начальном этапе этим можно пренебречь. На самом же деле этот расчет так остался основным и неизменным до конца соревнования. Думаю, что эта удачная находка является одним из ключевых элементов моей стратегии.

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

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


расчетное поле истребителей, притягиваемых вражескими вертолетами справа (красный сильнее желтого)

Для расчета наилучшего направления движения группы использовалась сетка размерностью 16х16. Насколько близко просчитывать влияние? С одной стороны, для экономии действий хотелось, чтобы выбиралось как можно более дальняя точка назначения, но с другой, если выбирать клетку с наибольшим потенциалом на относительно дальнем расстоянии, то возрастает вероятность того, что путь к лучшей клетке будет проходить через вредные для нас клетки. Я решила рассчитывать значения зарядов на три клетки в каждую сторону от центра группы. Заряд для вражеской группы задавался расчетной разностью убитых юнитов, так что группа, при сражении с которой потери моих войск рассчитывались большими, чем у противника, генерировала отрицательный заряд.
Убывание заряда считалось по закону:

$$

где score — рассчитанная разность очков; dist — расстояние в размерности сетки. При этом, положительный заряд оказывал влияние на любой дистанции, а отрицательный заряд имел ограниченное дистанцией атаки и радиусом групп влияние. Отрицательные поля ограниченного влияния также генерировали края карты и собственные группы для избежания коллизий. Изначально значения зарядов из всех источников суммировались.

Эта версия имела массу недостатков — группы слипались (из-за чего я отказалась от деления групп на 4 части, как я думала временно), размазывались по стенам (границам игрового мира) или наоборот так боялись стен, что не могли добить одиночных вражеских юнитов. Но, наконец-то, за 4 дня до начала первого раунда, у меня получилась стратегия, которая стабильно побеждала Smart guy!

Ядерный удар

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

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

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

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

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

Не смотря на то, что к началу 1 раунда бот показывал стабильный рост в песочнице, я была не очень в нем уверена и серьезно опасалась, что во второй раунд мне не пройти. Тем не менее, в раунде бот показал себя хорошо, получив 92.9% побед и заняв 35 место. Не последнюю роль тут сыграл рандом, так как топовых соперников почти не было, но все же я уверилась, что двигаюсь в правильном направлении.

Подготовка ко 2 раунду

Из-за различий скоростей на местности группы при движении растягивались и разрывались. Чтобы это исправить, я, как и многие, добавила периодическое сжатие. Также поправила неприятное поведение — один единственный оторвавшийся от группы юнит начинал её сильно отталкивать, сбивая с нужного пути. Решив, что так как от единичных юнитов мало пользы, то лучше для групп одного типа вместо отталкивания сделать притягивание для случая, если одна из групп меньше 10 юнитов либо же в два раза меньше другой. Заряд был равен численности большей группы. Теперь потеряшки быстро приклеивались к основной группе.

Расчет зарядов от центров групп работал не очень хорошо, так как группы могли быть очень разных форм, а мне хотелось получить большую точность, чтобы лучше искать слабые места в «торнадо» и «бутербродах». Для того, чтобы привести поле к форме отряда, группа дополнительно разбивалась на ячейки 16х16. Теперь заряд рассчитывался не от центра, а от ближайшей ячейки группы.

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

Заметила, что иногда в борьбе с «бутербродами» группы оценивают ситуацию слишком оптимистично. Например, вертолеты привлекала легкая и богатая добыча в виде БРЭМ и танков, которая перевешивала негативное влияние от замешанных там же БМП. В итоге довольно часто мои группы бесстрашно бросались прямо в центр «бутерброда», существенно увеличивая счет соперника. Предположу, что обычно такие проблемы решаются балансом коэффициентов, но я сделала проще: если ячейка испытывала только положительные влияния от групп противника, то учитывалось только максимальное из них, а при наличии отрицательного влияния всегда брался минимум. В результате мои группы перестали «сгорать», но это не слишком помогло, так как теперь они кружили вокруг плотного «бутерброда», не находя в нем слабых мест, пока он методично бомбил мои отряды. В отличие от «бутерброда» они не имели возможности лечиться, так как мои БРЭМ не участвовали в боях, а обычно отсиживались в углу. «Бутерброду» же бомбы не причиняли много вреда, так как, во-первых, он мог вылечиться, а во-вторых, мой удар всегда бил в центр группы так, что за пару ударов он прожигал в ней дыру и продолжал бить в ту же точку, не нанося противнику повреждений. Пришлось срочно дорабатывать удар для поиска точки с максимальным повреждением, снова используя учет распределения юнитов в группе по ячейкам. Но борьбе с хорошо сделанными «бутербродами» это не сильно помогло. Я пробовала держать войска дальше, чтобы уберечь от бомб, пробовала подводить ближе, для более агрессивных атак, но все равно игроки с плотными формациями такие как azt-yur и Savidiy меня в основном побеждали. В конце-концов, посмотрев, что даже уже ставший к тому моменту лидером, GreenTea иногда проигрывает игры без зданий плотным формациям, я решила бросить борьбу с «бутербродами» и заняться играми по правилам второго раунда.


Картина рассчитанных потенциалов для группы танков (слева вверху). Негативные поля (синие) перекрывают позитивные (красные)

Для захвата зданий я просто добавила в расчет полей притяжение к зданиям. Сразу стало ясно, что заряды привязанные к очкам себя не оправдывают, так как гораздо выгоднее получить 100 очков, просто немного постояв на здании, чем гоняться по всей карте за группой противника, рискуя потерять свои войска. Поэтому фабрике назначался заряд 250, а контрольному центру — 150 очков. Также, чтобы сделать здания еще более привлекательными, затухание поля было сделано более мягким — points * (Math.pow(0.9, dist)). Распределение зданий между группами было сделано самым примитивным образом — если в некотором радиусе здания находилась дружественная группа, более близкая к цели, то это здание исключалось из целей текущей группы. Но уже такой простой захват зданий даже без строительства давал отличный перевес по очкам в играх с «бутербродами» которые были медлительны и неповоротливы и не могли быстро захватывать здания.

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

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



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

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

• строить истребители, если их осталось меньше 10;
• если у соперника заметно больше танков, то строить либо вертолеты, если у противника нет истребителей, либо тоже танки;
• в любых непонятных случаях строить БМП;

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

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

Подготовка к финалу и финал

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

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

В процессе этих доработок я заметила, что действия по группам выполняются гораздо чаще, чем по идее должны были. Оказалось, что экономия действий не работала наверное со времен добавления ПП. После исправлений танки стали получать действия раз в 250 тиков и более. Заодно для экономии расчетное поле ПП было увеличено с 3 до 4 клеток.

Только на финишной прямой у меня дошли руки работы с авиацией. Все это время вертолеты у меня гибли в самом начале боя, что было очень плохо, так как сохраненные вертолеты иногда могли решить исход всей игры. Чтобы спасти вертолеты на поле добавлялся сильный заряд, находящийся в точке за ближайшей к вертолетам группой БМП. Благодаря этому вертолеты успешно прятались за БМП от противника «бегая» вокруг них. В дополнение к этому сделала, чтобы приоритетной целью для вертолетов были танки (а не БРЭМ), а для истребителей — вертолеты (а не истребители). Так как на старте игр в тумане авиация не имела ударных целей, истребители направлялись сопровождать танки, а вертолеты — БМП.


Также дорабатывалась работа с фабриками. Например, при захвате теперь учитывалось, может ли группа-захватчик справиться с вражескими группами поблизости; добавила притяжения своим фабрикам, частично захваченными врагом. Сделала размер строящихся групп меньше, а также зависящим от ситуации на поле. Строительство воздушных юнитов теперь могло прекращаться досрочно, если фабрике грозила опасность.

За два дня до финала я обнаружила ужасную и глупую ошибку — оказывается, при ограничении действий, я перепутала кулдаун на бросок бомбы с общим кулдауном на действия. Из-за этого вместо разрешенных 12 действий у меня всегда использовалось только 7. Как мне кажется, после исправления этой ошибки игра бота заметно улучшилась.

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

Учитывать новые юниты было довольно просто — надо было всего лишь следить за типом и прогрессом строительства на фабрике. А вот учитывать погибших юнитов было гораздо сложнее. Проблема заключалась в том, что и для убитых, и для ушедших в туман юнитов приходила совершенно одинаковая информация с durability = 0. Для того, чтобы понять, мог ли юнит погибнуть, я проверяла, были ли в некотором радиусе способные нанести урон группы, и были ли в этих группах юниты, находящиеся в примерном радиусе удара. Также, если на прошлом тике был выполнен ядерный удар, проверялось, был ли потенциальный погибший в его радиусе. В результате вышел довольно неплохой учет, например, в одной из игр на тике 10000 рассчитанное и реальное количество были такими:

ARRV: 20 FIGHTER: 32 HELICOPTER: 3 IFV: 346 TANK: 99
ARRV: 19 FIGHTER: 32 HELICOPTER: 1 IFV: 327 TANK: 99

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

Накануне финала бот вошел в первую тройку в песочнице. При этом сильно проигрывал GreenTea, Leos, mixei4, нестабильно играл с tyamgin, Adler и Milanin. Поэтому, хотя очевидно, бот и претендовал на место в 10, на сильно большее я не рассчитывала. Однако, после первой половины финала бот занял 4 место, так что появился некоторый стимул по его улучшению в перерыве. Некоторое время я сомневалась, ведь при равенстве очков преимущество имеет тот, кто отправил стратегию раньше, а очки ботов на местах 2-6 были очень близкими. Но, так как при просмотре игр были обнаружены явные ошибки и неоптимальности, решено было изменения все же внести.

Помимо исправления мелких багов было сделано следующее:

• истребители были выведены вперед танков, а вертолеты — за БМП, так как иначе первые ядерные удары получали обе группы
• так как я заметила, что мои группы часто бросали фабрики беззащитными перед приближающимся к фабрике противником, заряд для вражеских групп, угрожающих моим зданиям, был увеличен в 10 раз. Это заставило мои группы оборонять свои здания чаще.
• увеличила необходимое количество наземной техники, в случае отсутствия которой строительство авиации было запрещено со 100 до 200
• повысила приоритет строительству танков — если раньше они начинали строиться при 20% превышении их количества у соперника, то теперь достаточно было любого превышения
• кроме этого стало ясно, что увеличение размера поля было ошибкой — из-за этого группы чаще стали страдать от коллизий, поэтому для наземных юнитов поле было снова уменьшено до 3.

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

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

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

Спасибо, что дочитали до конца. Как видите, история моего бота показывает, что даже относительно простые подходы могут быть довольно эффективными. До встречи на Russian AI Cup в 2018 году! Приходите, будет интересно!