Меня зовут Андрей Рыбалка, мне 32, я занимаюсь веб разработкой, а также, периодически участвую в различных чемпионатах по написанию игрового ИИ (обычно на Java). И я хотел бы рассказать о своих подходах к написанию бота для Russian AI Cup 2017. Решил описать и саму историю и техническую часть, но тем, кого интересует именно реализация, можно смело прокручивать до соответствующего подзаголовка.

Итак..

Общее описание

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

В этом году нужно было написать бота для Real-Time Strategy (RTS), который сражался в дуэльном режиме против ботов других участников.

Карта представляла собой квадратное поле размером 1024х1024. Территория была разделена на сектора размером 32х32. Каждый сектор мог содержать один из трёх типов местности — Равнина, Лес или Топь, а также, один из трёх типов погоды: Ясно, Облачно, Дождь.
Типы местности и типы погоды, по сути, выполняли одну и ту же функцию, только местность — для наземных войск, а погода — для воздушных. Функция заключалась в том, что они снижали (либо не снижали) скорость передвижения, дальность обзора и вероятность быть увиденным в данной клетке.

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

В игре было доступно 5 типов войск, делящиеся на 2 категории:

• Воздушные
  
  • Истребитель: быстрый юнит, который может атаковать только воздушные цели. Эффективен против вертолётов
  • Вертолёт: может атаковать как воздушные, так и наземные цели. Силён против танков, слаб против БМП и самолётов.
• Наземные
  
  • Танк: Основной юнит. Силён против всей наземной техники, слаб против вертолётов, не умеет атаковать истребители.
  • БМП: Слаб против танков, силён против воздуха
  • БРЭМ: Ремонтирует и наземные и воздушные юниты

В начале партии обоим игрокам давалось 500 юнитов: по 100 каждого типа. Выглядело это примерно так:

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

Немного о зданиях. Они были двух типов:

• Центр управления. Увеличивает лимит действий и уменьшает интервал между запусками тактическими ядерными ударами (ниже)
• Завод. Производит любую технику

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

Первый раунд

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

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

Когда организаторы увидели это, они добавили в игру ещё одну функцию — тактический ядерный удар. Любой юнит мог сбросить бомбу, наносящую большой урон, в любую точку в своём радиусе вимости. Но это не особо помогло, т.к. вызывать ядерный удар можно было достаточно редко и он не убивал здоровые юниты, а только значительно повреждал их. И, при грамотном "бутерброде", за время между двумя ударами БРЭМ-ы успевали полностью отремонтировать всю повреждённую технику.

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

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

Мои канапешки (жёлтые) против вражеского бутерброда. Технические подробности будут ниже.
Вот эта нехитрая стратегия дала 57-е место в первом раунде, этого было достаточно для прохождения дальше.

Второй раунд

Здесь в игре появились здания.

Вскоре после начала работы над ним, стало понятно, что нужно делать ставку на заводы. Причём, захватывать их надо быстро и строить нужно в первую очередь танки.
Пробовал также строить канапешки прямо на фабриках, но это не дало ожидаемого результата — чтобы сделать нормальную канапешку, это надо было ждать, пока произведутся 55-66 юнитов, а это слишком долго. Кроме того, мне, как в общем-то и почти всем остальным, пришлось отказаться от канапешек, ибо их сборка занимала слишком много времени и врага за это время успевал захватить заводы. Была мысль собирать их на ходу, параллельно захватывая заводы, но она была слишком сложной в реализации и при этом было непонятно, сработает ли, так что я от неё отказался. Вообще, мне от начала второго раунда и до самого конца не давало покоя то, что я, как, впрочем, и почти все остальные, практически не использую БРЭМ-ы по прямому назначению — для лечения. Они у меня лечили только воздушные юниты, которые могли просто зависнуть сверху и там оставаться там до выздоровления. А вот с наземными юнитами так не выходило, т.к. для этого нужно подъехать вплотную, что после первого же боя, либо движения по карте, становилось практически невозможным. Формация ломалась, а равномерно перемешивать две бесформенные толпы юнитов, пользуясь только выделением-рамочкой и сильно ограниченным числом действий, было нереально.

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

В общем, всё это дало мне 10-е место во втором раунде, и я прошёл в финал.

Финал

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

В самом финале я, после первой половины, был, кажется, на 13-м месте (точно не помню уже). Но в перерыве неплохо улучшил стратегию, так что во второй половине пошёл вверх. Но игр было достаточно мало, так что успел добраться только до 11-го места. Причём, набрал столько же очков, сколько участник на 10-м месте. Но в такой ситуации выигрывает тот, кто раньше залил стратегию, и это был не я. Причём, на момент начала второй половины финала, у меня было от него приличное отставание — в несколько десятков очков. Так что раз сравнялись, значит, видимо, моя стратегия была сильнее, и если бы была ещё одна волна игр, то, наверное, попал бы в топ10.

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

Финал песочницы

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

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

В общем, я на тот момент был на 5-м из 6 призовых мест и мне нужно было продержаться там ещё неделю, так что хоть я к тому времени и устал, решил всё же что-то ещё поулучшать, только в более спокойном темпе. В общем, моя стратегия хорошо играла в режиме со зданиями и в режиме с туманом войны, но была предельно слаба в игре без зданий, ибо я её в этом режиме вообще не тестировал с момента окончания первого раунда. А вот в играх со зданиями я выигрывал более 50% игр против ребят с 8,9,10 мест. Также, я выигрывал около половины игр у Milanin-а, державшегося на 3-м месте песочницы. И вот, за два дня до конца у меня случился статистический криз. А именно, предполагалось, что вероятность выпадения любого из трёх типов игр — 33.3%. то есть моя стратегия с вероятностью 66.6% должна была получать игру в формате, в котором она хорошо играет, что меня вполне устраивало. Так вот, за двое суток до финала у меня случилась серия игр, где из 20 последовательных игр 15 прошли в формате без зданий. 12 из них я проиграл. Статистическая вероятность этого около 0.0001, но у меня это, так или иначе, случилось и это очень сильно ударило по моему рейтингу. Примерно так:

Я свалился на 15-е место и уже думал, что не успею восстановиться. Но всё же чёрная полоса прекратилась, я пополз вверх и успел добраться до 11 места. Должен ли был ползти выше, или это и есть моя объективная позиция, на данный момент я не знаю, ибо на этом месте песочница остановилась, а вместе с ней и моя история участия А потому, перехожу к самому интересному.

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

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

Грубо говоря, строится сетка, которая накладывается на игровой мир. для каждой ячейки этой сетки считается её score, который равен суммарному bonus (полезность нахождения в этой ячейке) минус суммарный penalty (опасность). Бонус и пенальти "излучаются" эмиттерами. В отличие от прошлого года, в этот раз у меня в большинстве случаев они были линейными. То есть влияние эмиттера на точку падает линейно при удалении от неё. Только в паре других мест были иные варианты.

Каждый игровой тик выполнялись следующие действия:

Уклоняемся от ядерного удара

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

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

Обрабатываем действия в очереди

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

• Были добавлены действия MOVE_TO (Отправляющее группу в указанную точку, в отличие от стандартного MOVE, принимающего смещение, а не цель. Было полезно в случаях, когда на момент начала выполнения экшены мы не знали, где именно будет находиться группа), ROTATE_AROUND_CENTER, WAIT_FOR_IDLE, WAIT_TICKS.
• Была добавлена поддержка callback-ов. то есть можно было, скажем, выстраивать цепочку Выделить группу — Повернуть на указанный угол — Дождаться окончания поворота — Сжать — Дождаться окончания сжатия.

Разбиваем вражеские войска на группы

Для этого использовался алгоритм k-means. Я выбрал такой радиус, чтобы в случае, если у врага есть группа войск неправильной формы, она "распадалась" на несколько групп, чтобы мои войска в таком случае могли, скажем, бояться основной части, но не бояться атаковать "хвост".

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

Проверяем, есть ли необходимость совершить действие досрочно

Для того, чтобы не тратить все действия сразу, я исходил из того, чтобы совершать какое-то действие раз в N тиков. Правила давали 12 действий на 60 ходов, т.е. в среднем, одно в 5 ходов, но т.к. большая часть команд требовали минимум двух действий — выделить группу и сделать с ней что-то, то в качестве N были выбраны 10 тиков. Позже это число снизилось до 7. Так вот, на этом этапе у меня срабатывала такая фича: для каждой своей группы я брал ближайшую группу врага и проверял, двигается ли она по прежней траектории. Если фактическая позиция отличалась от предсказанной, я делал вывод, что группа получила новый приказ и инициировал досрочный ответ на этот приказ.

В целом, то, какая именно группа будет ходить, у меня определялось взвешенным random-ом. К примеру, более близкие к врагу группы получали бонус к весу. Также, бонус получали самолёты, догоняющие вражеские вертолёты, и наоборот, мои вертолёты, убегающие от вражеских самолётов, а, скажем, БРЭМ в большинстве случаев получали меньший приоритет.
В случае досрочного хода, группа также выбиралась случайно, но только из тех групп, для которых выполнилось описанное выше условие.

Раз в 50 тиков запускался коллектор бомжей

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

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

Проверяем, не следует ли нам запустить ядерку

Работало следующим образом:

Брал группу врагов, находил ближайшего моего более-менее здорового юнита. Строил отдельное ПП для ядерки вокруг группы врагов, в области, куда мой юнит может её "докинуть". каждая ячейка ПП получала бонус за всех врагов, которые в неё попадали. причем, бонус зависел от их здоровья. Я пробовал два противоположных подхода — приоритет на добивание раненых, и наоборот, приоритет на здоровых (исходя из предположения, что если ядерка может нанести 90% урона, то нет смысла сбрасывать её на юнитов с 10% здоровья). В итоге, остановился посередине — давал приоритет юнитам со здоровьем от 33% до 66%.

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

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

К слову, если до перезарядки ядерки врага оставалось менее 100 тиков, я старался оставлять 2 действия в резерве на улонения от ядерного удара.

Запускаем боевую симуляцию

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

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

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

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

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

Комбинирование и разрыв групп

Выполнялись 2 процесса:

• Если в группе стало менее 20 юнитов, и в некотором радиусе была другая однотипная группа, размером до 25 юнитов, они объединялись.

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

Перегруппировка

Достаточно глупо реализованная функция, которую так и не успел допилить. Она стремилась к тому, чтобы стянуть юниты в группе в плотную кучу. Делалось это так же, как у большинства — поворот + сжатие группы. Работало так себе.

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

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

Собственно, Потенциальные поля

Тут всё довольно тривиально. Размер ячейки — 8, сетка квадратная, с шириной несколько больше диаметра области видимости.

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

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

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

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

Для реализации всех "особых случаев", коих было много, у меня были дополнительные эмиттеры — POIs — Points of Interest. Вот несколько примеров использования:

• С их помощью я заставлял вертолёты держаться под прикрытием БМП, до тех пор, пока количество убитых вражеских самолётов не достигнет 75
• Если достигло, я переставлял POI (только для вертолётов) с группы БМП на группу моих танков, чтобы защищать их от вражеских вертолётов. Делал это в случае, если количество убитых вертолётов врага также ниже 75
• Отталкивал юниты от углов
• Старался держать БРЭМ подальше от центра
• Отправлял одиночный самолёт-бомбер облетать карту в случае, если местоположение вражеских танков ему неизвестно
• Отправлял авиацию лечиться к БРЭМ-ам. Излучение зависело от среднеего здоровья.

И так далее.

В заключение

Вот примерно так это всё, к моему удивлению, работало.

Надеюсь, кто-нибудь найдёт для себя что-то интересное в этой статье, несмотря на то, что это просто очередная статья типа "история 284-го места от Рождества Христова". Я вообще планировал писать только если окажусь в топ10, но, во-первых, по очкам я всё-таки разделил 10-е место в финале, и, во-вторых, меня об этом попросили другие участники.
Спасибо всем за внимание и большое спасибо организаторам.

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