Эта статья об участии в чемпионате по написанию игрового искусственного интеллекта Russian AI Cup

Дисклеймер, пока все не разбежались

Хоть в финале я и был 16-м, статья описывает бота, удерживавшего 5-е место в общем зачете песочницы на момент её остановки.

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

Вступление

Меня зовут Андрей Рыбалка (вдруг Вы — робот и не смогли распознать текст на картинке выше), я уже восьмой год подряд участвую в Russian AI Cup. Это чемпионат для программистов по написанию игрового искусственного интеллекта. Задачей является написание бота, который будет играть в игру против ботов, написанных другими участниками.

Короче говоря,

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

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

А пока...

О задаче

Постараюсь описать покороче. Более подробное описание есть в статье GreenTea, занявшего 4-е место. Вообще, задача этого года предполагала стратегию в реальном времени (RTS) в космическом сеттинге. Но космический арт получился неудачным, юниты были практически неотличимы друг от друга визуально, поэтому все переключали визуализатор в упрощённый режим, который Вы видели на картинке в начале статьи, и забывали о космических кораблях как о страшном сне. А в упрощённом режиме на квадратиках юнитов были нарисованы меч, лук и молоток, поэтому все воспринимали игру именно в средневековом сеттинге. Так же поступлю и я в этой статье.

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

Есть юниты-рабочие, они же строители, они же добытчики, они же ремонтники, Есть юниты ближнего боя — мечники. Они, по факту, в этом чемпионате практически не использовались. И есть юниты дальнего боя — лучники. Именно их все строили и далее, описывая бои, я подразумеваю именно бои лучников.

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

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

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

Рабочие добывают ресурсы, на эти ресурсы мы покупаем новых рабочих, либо строим здания, либо строим армию. Зданий в игре всего 4 типа: база рабочих, база мечников, база лучников и дом. Первые три умеют производить юниты соответствующих типов. То есть, чтобы начать строить лучников, нужно в начале построить их базу. Дома нужны для того, чтобы увеличивать лимит юнитов, которых можно произвести. Каждый дом позволяет купить 5 дополнительных юнитов.

Стоимость покупки юнитов растёт на $1 за каждого уже существующего юнита этого типа. Таким образом, первый рабочий стоит $10, второй — $11 и т.д. Поэтому, если строить слишком много юнитов, в какой-то момент каждый последующий получается непомерно дорогим и это тоже нужно контролировать.

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

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

Этапы

Чемпионат состоит из двух раундов и финала. В каждом раунде правила несколько меняются.

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

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

• Правила финала повторяют правила второго раунда, но играем 1 на 1. Выглядит примерно так:

Техническая часть

Стратегия состоит из следующих основных модулей:

1. Подготовка
2. Экономика
3. Строительство и ремонт
4. Сбор ресурсов
5. Производство юнитов
6. Бой
7. Перемещение по миру (поиск пути; отправка юнитов к различным целям; контроль карты)

О них и поговорим подробнее.

В поисках грааля

Я, традиционно, писал на Java. Так что таймауты — мой вечный попутчик на этом чемпионате. Но в этот раз почему-то ситуация с таймаутами была гораздо плачевнее, чем в предыдущие годы. По словам организаторов, они не меняли инфраструктуру, поэтому я не знаю, чем объяснить случившееся, но я ловил таймауты даже при минимуме вычислений. Локально стратегия летает, а на сервере — превышает лимит в 40 секунд процессорного времени на игру. В попытках бороться с этим, я добавил логирование суммарного реального времени и был, мягко говоря, удивлён, увидев, что локально на домашнем ПК, моя стратегия тратит суммарно на все вычисления 3 секунды на всю игру, и при этом не укладывается на сервере в отведённые 40 сек. Дебагер показал, что более 90% всего времени сжирает VM джавы, с стратегии остаются лишь оставшиеся жалкие 7-10%. Я начал бить тревогу. И выяснилось, что примерно ту же самую картину видят все, кто пишет на Java или Kotlin.

Поскольку я не джавист и совершенно не разбираюсь в настройке VM, я пытался скооперироваться с теми, кто что-нибудь в этом понимает. К примеру, в воскресенье между 1 и 2 раундом мы просидели несколько часов в скайпе с победителем этого года, Commandos-ом (который давно плюнул на эти проблемы и перешёл на C++), пытаясь добиться вменяемого быстродействия. Настройкой VM, получилось ускорить примерно вдвое, но этого тоже было слишком мало.

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

Решение нашёл участник под ником karloid, писавший на котлине. Он предложил собирать нативный PE файл средствами GraalVM.

Грааль, как и полагается граалю, сотворил чудо. Собранный exe файл у меня тратил в 5 раз меньше процессорного времени. Ещё спустя пару дней организаторы добавили поддержку GraalVM в тестирующей системе. В общем, только с того момента у меня началось полноценное участие. К сожалению, на тот момент прошло уже 2.5 недели, а это больше половины чемпионата, и оставалось всего пару дней до старта второго раунда. В общей сложности, на протяжении всего чемпионата, примерно треть всего времени ушла на всевозможные оптимизации, а не на написание стратегии. А учитывая, что на поднятие с 16 на 5 место понадобилось суммарно 10-12 часов программирования, я именно с этими проблемами связываю не самый хороший результат финала. В общем, имеем что имеем, дарёному коню в зубы не смотрят, да и поскольку решение теперь известно, я полагаю, в следующий раз Грааль будет доступен изначально.

0. Подготовка

В начале происходят некоторые предпросчёты и обновления состояния. В основном, тут всё скучно. Приведу несколько наиболее интересных моментов:

Обновление мира

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

Контролируемые области

Изначально, вспомнив статью xathis о Google Ants, я подумал, что здесь вычисление линий фронта и движение к ним также может быть весьма действенным и это было одной из первых реализованных фич.

Вычислялось элементарно — пускаем поиск в ширину (далее, BFS) от всех видимых боевых юнитов. Если очередная просматриваемая клетка ещё не обработана ранее, отмечаем, что именно этот юнит её контролирует. Когда область, контролируемые моими юнитами, сталкивается с областью, контролируемой противником, это и считается линией фронта.

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

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

Линия из квадратиков некрасивого цвета — это и есть линия фронта.

Слоты для добычи ресурсов

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

Карта проходимости

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

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

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

1. Экономика

Здесь особо нечего описывать. Жуткие эвристические формулы из кучи составляющих. Общая суть такова:

• Если нужно, строим базу лучников. Есть несколько условий, когда провоцируют её строительство — у нас уже есть определенное количество рабочих, либо враг собрал $350+ денег (т.е. вот-вот начнёт строить базу), либо достигнут 220-й тик.
• Если осталось меньше X юнитов до лимита, строим дома. X = 5 до тех пор, пока количество рабочих < 15, затем X = 10 (т.е. можно строить 2 дома одновременно)
• Если мы активно дерёмся, строим армию

• Если нет, производим рабочих, если ещё не упёрлись в текущий лимит. Лимит вычисляем так:

  
  

  double scale = Game.duel_mode ? 0.2 : (Game.fog_of_war ? 0.25 : 0.1);
  boolean builders_limit_not_reached = num_builders < Math.max(Game.duel_mode ? 60 : 50, World.food_slots.size() * scale);

  
  

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

  
  

2. Строительство и ремонт

Строительство домов и баз работает по-разному.

База лучников

В дуэли, как только будут построены 20 рабочих, группа из 6 юнитов бежит по направлению к центру карты, до тех пор, пока клетка [35, 35] не будет разведана, если только раньше не выполнится какое-то из условий срочного строительства базы. Затем они пытаются построить базу в координатах, приближенных к клетке [30, 30]. Я видел, что у большинства других участников на строительство базы выделяется 10+ рабочих, но мои тесты показывали наилучший результат именно при количестве 6. Также, я почти в самом начале резервирую какое-то место для базы лучников возле базы рабочих, на тот случай, если карта окажется "закрытой" и со свободным местом будут проблемы. Чтобы не пришлось строить базу лучников где-то на фланге, ибо это сильно снижает возможность оборонять второй фланг и в большинстве случаев ведёт к поражению.

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

Дома

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

Далее, я проверяю, не заблокирует ли дом единственный проход между двумя областями карты. Для этого я не придумал ничего лучше, чем выбирать по свободной клетке слева и справа от дома и искать между ними путь A*-ом, считая область, где я планирую строить, занятой. Затем беру пару клеток сверху и снизу и делаю то же самое. Если оба пути найдены, можно строить. У этого подхода есть недостатки. К примеру, если в упор к дому будет "карман", то я не смогу найти из него путь и дом построен не будет, даже если на самом деле он ничего не блокирует. Всё это можно было легко исправить, но были более срочные задачи, так что руки так и не дошли.

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

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

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

Турели

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

3. Сбор ресурсов

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

1. Собираем все слоты для добычи ресурсов в список (на картинке отмечены желтыми крестиками).

   
   

   

   
   

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

   
   

3. Из каждого слота параллельно инициируем отдельный BFS. Отдельный потому, что нам нужно найти не одно паросочетание слот-рабочий, а множество, поэтому для каждого слота будут свои открытый и закрытый списки.

   
   

4. Итерируем по количеству шагов от 1 до 20 (моя максимальная дистанция поиска).

   
   

5. Для каждого шага, для каждого слота, обрабатываем все клетки открытого списка, которые находятся на удалении, совпадающем с шагом.

   
   

6. Если в очередной клетке находится свободный рабочий, назначаем его в текущий слот.

   
   

7. Для тех рабочих, которые после окончания этого алгоритма остались незадействоанными, просто ищем ближайшие свободные слоты и идём к ним. Когда расстояние станет <= 20, его подхватит вышеописанный алгоритм.

   
   

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

Кроме того, если вокруг рабочего есть более одного ресурса, он добывает тот из них, который имеет меньше всего граничащих слотов

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

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

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

На картинке оранжевыми квадратиками показана опасная область. Как видно, несколько строителей (зелёно-жёлтые юниты), оказавшись внутри опасной области, бросают свои слоты и бегут добывать в более безопасное место. Оранжевая линия показывает путь одного из рабочих к новому слоту в обход опасных клеток.

А вот само вычисление опасных клеток было немножко интереснее.

1. Отмечаем все клетки в радиусе поражения вражеских юнитов как опасные.
2. Для вражеских лучников, вычисляем все клетки, куда они могут дойти за количество тиков, равное радиусу поражения, и добавляем их в открытый и закрытый списки. Т.е. для лучников — все клетки, до которых он доходит ровно за 5 шагов. Ниже объясню, зачем это надо.
3. Добавляем в эти же списки позиции всех моих войск.
4. Пускаем BFS из всех клеток в открытом списке. Рассматриваем только клетки в радиусе 7 единиц от юнитов. В свойство каждой просмотренной клетки я записываю, была ли она достигнута из моей клетки или из вражеской.

Таким образом, в радиусе семи клеток от каждого вражеского лучника, я оценивал, может ли враг атаковать эту клетку раньше, чем в неё подойдут мои войска. При этом, врагу достаточно было оказаться на расстоянии выстрела от клетки, а моим лучникам нужно было её занять. Т.е. у вражеских лучников была "фора" в 5 ходов. Именно поэтому во 2-м пункте я добавлял в список клетки, достижимые ими за 5 ходов, в то время, как для моих войск я добавлял только их реальные позиции. Расстояние в 7 клеток было получено путём тестирования. При значениях больше мои рабочие погибали гораздо реже, но и еды добывали меньше. При 7 клетках коэффициент побед был наивысшим.

Ещё рабочие могли было ремонтировать (лечить) других юнитов. Мало кто из участников активно использовал эту возможность. У меня, как и у многих других, лечение было случайным. То есть если раненый юнит проходил мимо рабочего, рабочий его лечил, но специально ни врачи к пациентам ни пациенты к врачам не ходили. Лечил я только на протяжении одного тика, с 5 ХП до 6 (при максимуме в 10). Так что поваляться на больничном у них особой возможности не было. Я не видел смысла тратить 5 тиков на полное восстановление ХП лучника, который, будучи вылеченным, умрёт с двух выстрелов (выстрел снимает 5 ХП), если можно было вылечивать всего 1 ХП за 1 тик с точно таким же исходом: лучник умрёт с двух выстрелов.

4. Производство юнитов

Тут мало что можно рассказать. Войска строю в клетке, ближайшей к врагу. С рабочими тоже всё просто. Если в пределах двух клеток от базы есть строящееся здание, произвожу рабочего в смежном слоте, если нет — строю поближе к слоту с едой (BFS от всех слотов еды пока не наткнусь на слот вокруг базы)

5. Бой

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

Боёвку я переписывал три раза, но до финала (включительно) всё равно работала первая версия, ибо остальные показывали худший результат. Первая версия — минимакс с альфа-бета отсечением.

Юниты делятся на группы. В финале работало следующее разбиение:

1. Сортирую своих юнитов по количеству противников в радиусе 5, затем 6, затем 7
2. Создаю бой и добавляю в него первого из отсортированных юнитов, затем рекурсивно всех его врагов, всех врагов его врагов и т.д., пока есть кого добавлять
3. Если моих юнитов в бою уже 5, больше в этот бой не добавляю. То же самое с противниками.

Таким образом, максимально возможный бой — 5х5. Если дерется больше юнитов — значит будет несколько боёв. Поскольку при переборе уменьшение количества ходов даже для одного юнита на один значительно снижает общее количество комбинацией, имели место быть некоторые оптимизации:

• Юниты на расстоянии 7 клеток от врага не идут в клетки на 8
• Генерация всех возможных ходов для моих и вражеских юнитов была достаточно дорогой операцией, и в раздумьях о том, как её оптимизировать, пришёл в голову следующий ход конём: я понял, что моя команда никогда не подходит в упор к вражеской команде (не считая варианта с мечниками, которых по факту практически не использовали). А потому, каким бы ни был ход моей команды, он никак не влияет на возможные ходы врага. Это позволило генерировать вражеские ходы только один раз за тик и затем тянуть их из кеша.
• Юниты не умеют меняться местами и два юнита не могут идти в одну и ту же клетку.

В оценочной функции я пытаюсь прикинуть, сколько будет убитых и раненых в обеих командах. Затем, на основании этих цифр, оценивал, выгодно ли мне атаковать. И вот множество тестов показали, что наилучший вариант заключается в том, чтобы нападать когда количество моих юнитов в бою меньше либо равно количеству юнитов противника. Короче говоря, при оценке я умножал оценку силы моей армии на коэффициент 0.99 если моих юнитов больше и на 1.01 в противном случае. Почему именно так могу лишь предполагать.

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

1. Сортирую своих юнитов по количеству противников в радиусе 5, затем 6, затем 7
2. Беру первого юнита из отсортированного списка, рекурсивно добавляю вместе с ним в бой всех своих юнитов на расстоянии 3. Затем обхожу всех моих юнитов в этом бою и добавляю в него всех врагов на расстоянии <= 7

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

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

1. Сортирую своих юнитов по количеству противников в радиусе 5, затем 6, затем 7
2. Те, у кого уже есть противники в радиусе 5, никуда не ходят и просто стреляют
3. Обхожу моих юнитов в отсортированном списке
4. Для каждого, считаю общее количество врагов в зонах 6 и 7 клеток
5. Беру ближайшего к нему врага и считаю количество моих юнитов только в зоне 6 клеток
6. Если число из пункта 5 больше числа из пункта 4, юнит считается атакующим.
7. Если меньше — убегаем, если равное количество — стоим на месте.

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

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

Юнит "C" имеет только одну цель в радиусе выстрела — "3", в то время, как юниты "A" и "B" имеют по 2 цели. Если бы юниты "A" и "B" стреляли в цель "3", выстрел юнита "C" не принёс бы никакой пользы. Поэтому у меня первым стреляет юнит "C", ибо у него всего одна возможная цель, а затем "A" и "B" решают, куда стрелять им, чтобы максимизировать потери противника.

6. Перемещение по миру

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

Охота на вражеских рабочих

1. Разбиваю всех видимых вражеских рабочих на группы (в цикле, если рабочий находится в пределах 5 единиц он какой-нибудь группы, добавляю его в неё и пересчитываю её центр. Иначе, добавляю в новую группу)
2. Считаю score каждой группы: по 3 очка за каждого юнита, который добывает еду, и по 1 очку за остальных
3. Сортирую по убыванию score и уже привычным движением руки, добавляю их в открытый и закрытый списки.
4. BFS-ом ищу ближайшего свободного лучника.
5. Скачу пугать и убивать.

К моему удивлению, одним из самых значимых изменений после окончания чемпионата, которое подняло меня с 8-10 мест места на 4-5, было изменение одной единственной константы, которая заставила охотников при поиске пути бояться вражеских солдатов.
Причём это было в последний день, за несколько часов до остановки песочницы, и локальные тесты показали улучшение всего на 30%, так что я даже сомневался, релизить ли, чтобы не потерять имеющуюся позицию. Дело в том, что в этом году у меня на протяжении всего чемпионата постоянно случалось такое, что новая версия локально выигрывала от 65% до 95% игр, а будучи залитой на сайт, против других играла так же, как предыдущая, или хуже. Вообще практически все мои релизные версии выигрывали не менее 2/3 игр против предыдущей. А тут всего-лишь 30%. В общем, я рискнул и риск оправдался.

Round 1 Opening

Алгоритм начала первого раунда. Одна из немногих вещей, где поведение реализовано хардкодом. Само поведение подсмотрено у GreenTea. Суть в том, что в игре по правилам 1-го раунда (без тумана войны), у нас изначально есть 1 лучник и 1 мечник. Их обоих я сразу направляю в атаку на базу врага справа от меня. При этом, они по возможности стараются избегать встречи с вражескими юнитами. До тех пор, пока их миссия выполнима, базу врага они тоже не атакуют, ибо в этом нет особого смысла, их наверняка убьют раньше. Их задача состоит в распугивании или убийстве вражеской фауны в лице рабочих. Это приводит к просадке в экономике в начальной фазе игры, что с большой вероятностью приводит к проигрышу.

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

Это единственный случай, когда я вообще строю мечников. Более того, базу мечников я даже не ремонтирую.

Защита базы

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

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

Обход по флангам

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

Для этой задачи я пускал 3 луча из точки [79, 79] (это угол на базе противника) влево и столько же вниз, с поворотом в 9 градусов между ними. И отправлял по одному лучнику вдоль каждого луча. Точнее, луч бился на сегменты и юнит стремился к дальнему от вражеской базы сегменту. Если этот сегмент недавно был посещён, юнит шёл к следующему и таким образом продвигался к вражеской базе по флангу.

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

Перемещение по карте

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

Итак, перемещение:

1. Инициализирую ПП. По сути это просто двумерный массив чисел, хранящий потенциалы каждой клетки. Из-за моих проблем с быстродействием до того момента, когда был найден грааль, я использовал сетку размером в 2 клетки. Позже ресурсов уже хватало и на нормальную сетку, но весь остальной код на тот момент уже полагался именно на этот размер, а времени переписывать уже не было. Короче говоря, на переправе коней не меняют. Поэтому, до самого конца у меня так и используется сетка 40х40 поверх поля 80х80.
2. Расставляем эмиттеры. Т.е. точки, которые излучают положительный или отрицательный потенциал в определенной области. Все эмиттеры были линейными. Угадайте, почему. Правильно — быстродействие! Считать квадратные корни или возводить в иные степени — дорогое удовольствие. С граалем я уже мог себе это позволить, но это нарушило бы всю хрупкую экосистему и пришлось бы искать новый баланс.
   Эмиттеров было достаточно много. Вот несколько основных:
   
   • Отталкивающее поле радиусом в несколько клеток в позиции каждого лучника. Я изначально решил, что мои юниты будут разбредаться по всей карте, чтобы во-первых, минимизировать туман войны и во-вторых, я стремился к тому, чтобы в любой точке карты, где срочно понадобятся дополнительные юниты, кто-нибудь оказался поблизости.
   • Притягивающие поля на вражеских юнитах и зданиях, на моих турелях, на моих строящихся зданиях
   • Отталкивающее поле в точке [0, 0], чтобы при прочих равных, юниты не толпились на базе
   • Кроме того, как я уже упоминал выше, здесь также работал алгоритм с лучами, только из точки [0, 0]. Я запускал 6 лучей по флангам и ставил эмиттеры в тех местах, где эти лучи пересекались с линией фронта (с некоторым сдвигом вперёд). это заставляло юнитов стремиться в позиции между моими рабочими и вражеской армией.

Блеклые зелёные окружности показывают притягивающие эмиттеры. Красные диски — это эмиттеры на лучах. После начала строительства боевых юнитов, эмиттеров становилось намного больше:

Блеклые красные — это эмиттеры с отрицательным потенциалом.

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

То есть из каждого юнита я поиском в ширину делал 25 шагов и затем рассматривал все пройдённые клетки. Потенциал каждой клетки относительно юнита считался как сумма_потенциалов_всех_пройденных_клеток + потенциал_в_целевой_клетке * (25 - количество_сделанных_шагов). То есть я "дошагивал" все оставшиеся ходы в конечной клетке, для того, чтобы я затем смог полноценно сравнивать все эти пути, имея цифры одного порядка. Ну и как несложно догадаться, я выбирал клетку с наивысшим относительным потенциалом и шёл к ней.

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

После того, как очередной юнит определился, куда он идёт, я делал ещё одну важную вещь — помещал отталкивающий эмиттер в конечной точке его пути. Те самые красные окружности на скриншоте выше. Это нужно было для того, чтобы все юниты не бежали в одну точку с наивысшим потенциалом, ибо для каждого последующего юнита потенциал этой точки снижался. Одна эта строка кода заставляла юнитов более-менее равномерно разбредаться по карте.

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

Поиск пути

Банальный A* со штрафами. Штрафы давались за прохождение через юнитов, через места, где планируется стройка, большой штраф давался за проход в зоне поражения вражескими турелями. За прохождение через ресурсы давался штраф, равный количеству ходов, которые потребуются, чтобы прорубить через них проход. И так далее. Некоторые из этих штрафов применялись или игнорировались в зависимости от аргументов. К примеру, рабочие сильно штрафовались за прохождение через зону стрельбы вражеских лучников, а войска — нет.

Также, юниты умели толкать рабочих. Тут есть два варианта:

• Рабочий толкает рабочего: При поиске пути для рабочего, я накладывал маленький штраф за прохождение через клетку, "забитую" другим рабочим. Штрафа хватало только на то, чтобы при выборе между двумя одинаковыми по длине путями, выбрать тот, где нет рабочих. В остальном же, при поиске пути, клетка с рабочим считалась пустой. Когда рабочий должен был на текущем ходу шагнуть в клетку, занятую другим рабочим, он сдвигался вперёд, вдоль пути, толкая паровозиком всех остальных рабочих перед собой до первой свободной клетки.

  
  

  

  
  

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

  
  

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

  
  

Тестирование

Тесты я гонял на 3-х компьютерах. В этом году даже не пришлось считать, является ли результат статистически значимым, ибо игры считались достаточно быстро, так что гонять их можно было много, и при этом, практически каждая моя следующая версия выигрывала у предыдущей 2/3 игр или больше, при количестве сыгранных игр не менее 500. Т.е. результат был заведомо статистически значим и без вычислений. При этом, как я уже упоминал выше, в этом году постоянно получалось так, что моя новая версия, без шансов обыгрывающая предыдущую, но против других противников играет лишь немногим лучше (если повезёт), а то и хуже (если нет). Апогеем стала версия, которая в локальных тестах выиграла у предыдущей со счётом 480:20, но после релиза показала нулевое преимущество против других участников.

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

Подбор констант, коих было много, осуществлялся скриптом на python. Он брал значения из командной строки и для каждого набора создавал некоторое количество игр (обычно 200) против той же версии с дефолтными константами. Что-то типа такого:

python search.py run —p1 test.exe —p2 prev.exe —count 200 —teams 2 —nthreads 3 —level Finals —params "CMD_MAX_DIST_FROM_BASE_TO_COUNTER:50/100|ENEMY_UNIT_ATTRACTION:100/300|FRIENDLY_PUSH_OFF_MULT:2.5/7.5" —output tests_v42-r3-1

Конкретно эта строка создала бы 6 сетов по 200 игр в 3 потока в режиме дуэли. Первый сет игр был бы со значением CMD_MAX_DIST_FROM_BASE_TO_COUNTER = 50, второй — CMD_MAX_DIST_FROM_BASE_TO_COUNTER = 100 и т.д. Можно было передавать и несколько констант за один раз. Сами тестируемые значения я обычно проверял парами — брал значение заметно больше текущего и заметно меньше. В примере выше, дефолтное значение константы CMD_MAX_DIST_FROM_BASE_TO_COUNTER было 75, поэтому я тестировал значения 50 и 100.

Визуализация

Как и все предыдущие годы, я использовал свой самописный визуализатор. Тем, кто читал мои предыдущие статьи он уже знаком. Вот традиционное видео:

Заключение

На этом у меня всё. Спасибо организаторам за очередной крутой контест. Задача этого года, как по мне, была одной из самых интересных.
Ждём новых чемпионатов!