Всем привет.
Астрологи объявили неделю Речь пойдет о соревновании Russian AI Cup 2017, а точнее о написанном мною боте. Участвую в данном конкурсе уже 6-й год подряд — ещё начиная с танчиков. Некоторые могу знать меня по участию в ML Boot Camp и HighLoad Cup.
Место занял (опять) не первое, но есть о чём написать на хабр. Статья, прежде всего, может быть интересна участникам этого года, или тем, кто захочет подчерпнуть какие-то идеи к следующему подобному конкурсу, или просто для тех, кто знаком с тематикой конкурса Russian AI Cup.
Не буду повторять правила игры. Кто с ними знаком — тот знаком, а кто не знаком — может посмотреть парочку игр лидеров. Ссылка на мой профиль.
Тема этого года изначально не очень понравилась, но заранее было решено, что я буду участвовать. Стоило отправить первую версию, как интерес резко проснулся, и начали появляться хоть какие-то идеи. Поэтому кто засомневается участвовать или нет в следующем году, советую отправить самую дуболомную стратегию. Мнение может сильно измениться.
Сложность управления отпугнула многих участников, и тем более новичков. Количество участников рекордно малое. А большинство тех, кто в топе первых трех недель, с очевидно неперспективными тактиками. Но мне всё это только на руку.
Сил на конкурс тратится очень много. Выкладываю 100% своего свободного времени. Но и этого оказывается недостаточно.
Лирическое отступление завершилось, перейду к описанию своей стратегии.
Штатного технического визуализатора в local runner недостаточно. Чтобы рисовать отладочную информацию, необходимо написать свой, либо воспользоваться чьими-то наработками. В первый же день я занялся адаптацией своего прошлогоднего простенького визуализатора на Windows Forms под новые правила.
В нём есть минимум нужного функционала: всё то, что умеет штатный визуализатор, а также анимация выделения, передвижения по вектору, захвата зданий, и прочие мелочи.
Короткое видео как это выглядит:
Как я писал выше, чтобы прочувствовать API, и чтобы начали появляться идеи, нужно написать хоть какую-нибудь стратегию. Идущий напролом и неповоротливый «торнадо» — отличная стратегия, чтобы тестировать все последующие версии, аккуратно «подстригающие» отряды противника.
По опыту прошлых Russian AI Cup, необходимой составляющей успешной стратегии являлся перебор ходов + точная симуляция игрового мира. Больше всего сбило с толку то, что не был виден четкий план развития стратегии, как это было в прошлых годах. Ставка была сделана на хороший микроконтроль, а тактику уже можно потом придумать, подсмотрев что делают соперники. Пока там всё устаканивается, нужно написать ядро, которое не будет сильно меняться, и куда можно будет наращивать новый функционал.
Архитектура кода очень простая. Есть объект типа MyVehicle – обёртка над классом Model.Vehicle, и объект песочницы (Sandbox). Последний, фактически, — это God object. Ему можно давать любые команды – все те же самые, что и Model.Move, а также симулировать мир на несколько тиков вперед.
Принятие решения основано на глобальной оценочной функции. Есть одна единственная функция (функция опасности), оценивающая состояние мира, и возвращающая действительное число. За 1 ход мы стремимся изменить состояние мира, чтобы это число было как можно меньше.
Эту же идею я использовал в предыдущем соревновании CodeWizards. Т.к. волшебник был всего один (то есть пространство двумерное), можно было отрисовать значение функции в виде градиентной шкалы (ссылка на прошлогоднее видео). Здесь же, 500 юнитов (пространство многомерное) с одной общей функцией, пришлось обойтись без визуализации.
Позже будет более подробно о том, как я эту функцию вычислял.
Теперь нужно перебрать различные ходы. Итоговый вариант — это перебрать для каждого отряда следующие ходы:
Этого списка оказалось достаточно, чтобы покрыть всё разнообразие действий.
Состоит из суммы следующих величин (с коэффициентами, которые подбирались долго и нудно):
Все пункты выше считаются для каждого юнита индивидуально, независимо от принадлежности к какому-либо отряду.
Это всё факторы ближнего боя. Далее самое сложное. Как заставить отряды двигаться к врагу? К ближайшему, или самому мясистому? Как заставить отряды убегать от врага, прятать вертолеты за БТРами? Как заставить отряды двигаться захватывать здания? Как заставить лететь лечиться?
Здесь понадобится информация о разбиении на группы. А также кластеризация юнитов противника (только из-за того, что дебажить 5-7 групп удобнее, чем 500).
В общем всё это имеет один жирный плюс, и один жирный минус. Без костылей можно добавлять новые пункты: ядерка, здания, лечение. Коэффициенты нужно постоянно подгонять: чинить под одни ситуации, но ломать на других.
Для достижения высокой производительности симулятора необходима структура данных, позволяющая быстро проверять окружности на коллизии, и находить соседей в окрестности боя.
Незадолго до начала конкурса, я следил за активностью в github-репозиториях разработчиков конкурса. В репозитории codeforces-commons был добавлен файл QuadTree.java, и уже тогда появились первые догадки, что конкурс будет с большим количеством юнитов. Только после того как приступил к реализации своего симулятора, я вспомнил про эту структуру, и начал её использовать. Ведь она же и используется в local runner. В приведенной реализации не хватало методов удаления точки, изменения координаты точки (удалить и заново добавить – неэффективно), клонирование дерева. Пришлось самому их добавить.
Проверка юнитов на коллизии – самая затратная операция в моем коде, и я с трудом укладывался в ограничение по времени.
Менеджер команд? Очередь с приоритетами для отрядов? Отложенные и отменяемые команды? Всего этого нет. Как было описано выше, все решения принимаются только на основе текущей ситуации, и зная последний приказ для каждого юнита. Доступные действия размазаны по 60 тикам равномерно по принципу TickIndex % 10 == 0. Вычисления слишком затратны, чтобы делать из каждый тик.
Несколько вечеров ушло на то, чтобы как-то с пользой приспособить юниты типа Arrv. Я решил их замешать с Tank и Ifv в шахматном порядке. Построение неоптимальное, но пока сойдёт.
К началу первого раунда я стабильно побеждал многих лидеров. Невольно приходилось затачивать себя под соперников типа «бутерброд», хоть и понимая, что для финала они не годятся. Ориентировался главным образом на ud1 и GreenTea – у них стратегии больше были похожи на мою.
Ко второму раунду предстояло научиться захватывать здания и управлять производством. Замешивание отрядов Arrv пришлось выкинуть. Оно занимало слишком много времени – в среднем 900 тиков. Даже с потенциальной оптимизацией в 2 раза это всё равно много, и затею пришлось бросить.
Стартовые отряды Arrv, Tank, Ifv, а также свежепостроенные, разбегались захватывать здания, чтобы минимизировать суммарную длину пути. Это стандартная задача о назначении, решаемая венгерским алгоритмом. Больше алгоритм выбора здания не менялся. Стоило добавить учет типов техники противника, но это не казалось приоритетной фичей.
Проблема производительности вышла не первый план. Количество юнитов на карте увеличилось, количество групп тоже, а значит и количество всевозможных ходов.
Около недели я потратил на оптимизации. Пришлось оптимизировать в ущерб точности. Вместо того, чтобы симулировать действия на всей карте, я делал симуляцию в окрестности каждой группы отдельно, а потом склеивал результаты.
Во избежание всяческих конфузов с ядерными бомбами, я отключал эти оптимизации, когда на карте есть хотя бы одна бомба.
Пришлось пойти дальше, и отключить проверки на коллизии, когда группы движутся по прямой, или крутятся.
Ну и последнее — перебирать все 12 направлений для Move бессмысленно, если вокруг нету врагов.
А нет, не последнее. Группы с четными номерами ходят по четным ходам, с нечетными — по нечетным. Только что построенные (aka бомжи) — каждый 3-й ход. Исключения есть для выделенных отрядов, и в режиме ядерной бомбы, а также в начале игры (< 3000 тиков).
В финале необходимо было контролировать количество вражеских юнитов, и где примерно они находятся. Для каждого юнита по Id запоминалось где последний раз он был виден. Есть 3 массива:
Обычный массив видимой техники (visible)
Массив проверенной невидимой техники (checked). Известно где последний раз был виден каждый Id, но точно известно, что его там уже нет.
Массив непроверенной невидимой техники (unchecked). Это значит, что предстоит разведать эту территорию на предмет наличия врага.
Заполнение массивов происходит следующим образом:
Радиус видимости достаточно большой, чтобы точно определить убит юнит, или пропал из видимости. Исключение составляет уничтожение ядерным ударом, но это очень редкий случай. Поэтому «мертвых душ» почти не оставалось.
С быстрой проверкой на видимость отлично справлялся тот же QuadTree, тем более что это нужно делать 1 раз за тик.
Это, пожалуй, всё, что было сделано для поддержки игры в тумане войны.
Таймлимиты я так и не поборол, моя программа по-прежнему с некоторыми соперниками на некоторых картах не укладывается в 220 секунд. Но, тем не менее, успевает обеспечить преимущество по очкам перед падением.
Немного не повезло в финале — занял в итоге 4-е место, а в песочнице 2-е. В следующий раз будем сильнее.
Всем спасибо. До встречи в Russian AI Cup 2018, а с кем-то, может быть, и раньше.
Код
Место занял (опять) не первое, но есть о чём написать на хабр. Статья, прежде всего, может быть интересна участникам этого года, или тем, кто захочет подчерпнуть какие-то идеи к следующему подобному конкурсу, или просто для тех, кто знаком с тематикой конкурса Russian AI Cup.
Не буду повторять правила игры. Кто с ними знаком — тот знаком, а кто не знаком — может посмотреть парочку игр лидеров. Ссылка на мой профиль.
Тема этого года изначально не очень понравилась, но заранее было решено, что я буду участвовать. Стоило отправить первую версию, как интерес резко проснулся, и начали появляться хоть какие-то идеи. Поэтому кто засомневается участвовать или нет в следующем году, советую отправить самую дуболомную стратегию. Мнение может сильно измениться.
Сложность управления отпугнула многих участников, и тем более новичков. Количество участников рекордно малое. А большинство тех, кто в топе первых трех недель, с очевидно неперспективными тактиками. Но мне всё это только на руку.
Сил на конкурс тратится очень много. Выкладываю 100% своего свободного времени. Но и этого оказывается недостаточно.
Лирическое отступление завершилось, перейду к описанию своей стратегии.
Визуализатор
Штатного технического визуализатора в local runner недостаточно. Чтобы рисовать отладочную информацию, необходимо написать свой, либо воспользоваться чьими-то наработками. В первый же день я занялся адаптацией своего прошлогоднего простенького визуализатора на Windows Forms под новые правила.
В нём есть минимум нужного функционала: всё то, что умеет штатный визуализатор, а также анимация выделения, передвижения по вектору, захвата зданий, и прочие мелочи.
Короткое видео как это выглядит:
Первая версия
Как я писал выше, чтобы прочувствовать API, и чтобы начали появляться идеи, нужно написать хоть какую-нибудь стратегию. Идущий напролом и неповоротливый «торнадо» — отличная стратегия, чтобы тестировать все последующие версии, аккуратно «подстригающие» отряды противника.
Пришло время писать основную стратегию.
По опыту прошлых Russian AI Cup, необходимой составляющей успешной стратегии являлся перебор ходов + точная симуляция игрового мира. Больше всего сбило с толку то, что не был виден четкий план развития стратегии, как это было в прошлых годах. Ставка была сделана на хороший микроконтроль, а тактику уже можно потом придумать, подсмотрев что делают соперники. Пока там всё устаканивается, нужно написать ядро, которое не будет сильно меняться, и куда можно будет наращивать новый функционал.
Архитектура кода очень простая. Есть объект типа MyVehicle – обёртка над классом Model.Vehicle, и объект песочницы (Sandbox). Последний, фактически, — это God object. Ему можно давать любые команды – все те же самые, что и Model.Move, а также симулировать мир на несколько тиков вперед.
Принятие решения основано на глобальной оценочной функции. Есть одна единственная функция (функция опасности), оценивающая состояние мира, и возвращающая действительное число. За 1 ход мы стремимся изменить состояние мира, чтобы это число было как можно меньше.
Эту же идею я использовал в предыдущем соревновании CodeWizards. Т.к. волшебник был всего один (то есть пространство двумерное), можно было отрисовать значение функции в виде градиентной шкалы (ссылка на прошлогоднее видео). Здесь же, 500 юнитов (пространство многомерное) с одной общей функцией, пришлось обойтись без визуализации.
Позже будет более подробно о том, как я эту функцию вычислял.
Теперь нужно перебрать различные ходы. Итоговый вариант — это перебрать для каждого отряда следующие ходы:
- Ничего не делать. Никакие приказы не отдаются, все продолжают двигаться в тех же направлениях.
- Scale к центру отряда.
- Scale от центра взрыва ядерной бомбы, если она есть. С разными Factor.
- Rotate на ±45°.
- Для наземной техники Move в сторону захвата строения.
- Для вертолетов Move в сторону БТРов для укрытия от самолетов.
- Для воздушной техники Move в сторону Arrv для лечения.
- Move в 12-ти направлениях на достаточно большое расстояние (скажем, в четверть карты).
Этого списка оказалось достаточно, чтобы покрыть всё разнообразие действий.
Вычисление функции опасности.
Состоит из суммы следующих величин (с коэффициентами, которые подбирались долго и нудно):
- Суммарное количество здоровья своей техники. Здесь также учитывался скрытый пул здоровья, которые пополняли Arrv, чтобы техника имела стремление лечиться.
- Суммарное количество здоровья техники противника.
- Количество убитой техники.
- Количество убитой техники противника.
- Потенциальный урон от ядерных ударов. То есть как будто бы ядерная бомба взорвется не через n тиков, а прямо сейчас.
- Количество очков захвата зданий.
- Потенциальный урон. Здесь получилось что-то типа штрафа (экспоненциально затухающего) за нахождение в зоне поражения, или около неё. А именно, для каждого юнита посчитано (какой урон ему могут нанести за 0 тиков) + (какой урон ему могут нанести за 1 тик) / 2 + (какой урон ему могут нанести за 2 тика) / 4 + …. Всё это без учета cooldown, чтобы бояться отдыхающих противников, а не ломиться на них напролом.
Все пункты выше считаются для каждого юнита индивидуально, независимо от принадлежности к какому-либо отряду.
- Штраф за коллизию отрядов. За коллизию отрядов, или «почти» коллизию. Штраф на столько большой, что было выгоднее пустить часть отряда на пушечное мясо, чем уйти в пересечение с другим отрядом.
Это всё факторы ближнего боя. Далее самое сложное. Как заставить отряды двигаться к врагу? К ближайшему, или самому мясистому? Как заставить отряды убегать от врага, прятать вертолеты за БТРами? Как заставить отряды двигаться захватывать здания? Как заставить лететь лечиться?
Здесь понадобится информация о разбиении на группы. А также кластеризация юнитов противника (только из-за того, что дебажить 5-7 групп удобнее, чем 500).
- Притягивающие/отталкивающие поля противника. Двойной цикл по моим отрядам, отрядам противника … одно из самых слабых и многострадальных мест моей стратегии … в общем здесь функция, зависящая только от типов отрядов и их размеров (смешанные отряды – большая редкость, поэтому считаем, что их нет). Если, например, у меня 50 самолетов, у противника 50 вертолетов, то значение функции очень большое положительное. Если 50 танков против 50 танков, то небольшое положительное. Если 50 вертолетов против 50 самолетов, то большое отрицательное. Если 50 вертолетов против 1 самолета, то маленькое отрицательное (внезапно! 50 вертолетов не полетят к 1 самолету).
Это всё дело умножается на экспоненциально затухающую функцию от расстояния между группами. Чем больше расстояние – тем меньше влияние на общую сумму. Нет смысла бежать к цели на противоположный угол карты, лучше пойти к кому-нибудь другому поближе.
Также всё это умножается на сумму плотностей отрядов, а именно (сумма площадей)^0.25. Чтобы сильно размазанные отряды сжимались с помощью SCALE. - Притягивающие поля к строениям. Здесь та же самая схема. О том, как распределялись строения по группам чуть ниже.
- Притягивающие поля вертолетов к БТР. Зависит от количества самолетов на карте, от расстояния до ближайшего, расстояния до ближайшего «пункта прикрытия».
- Притягивающие поля Arrv. Авиация в режиме простоя, или, когда поблизости есть Arrv, могли ими воспользоваться. Чем больше потеря здоровья, и чем ближе Arrv, тем сильнее притягивающее поле.
В общем всё это имеет один жирный плюс, и один жирный минус. Без костылей можно добавлять новые пункты: ядерка, здания, лечение. Коэффициенты нужно постоянно подгонять: чинить под одни ситуации, но ломать на других.
Симуляция
Для достижения высокой производительности симулятора необходима структура данных, позволяющая быстро проверять окружности на коллизии, и находить соседей в окрестности боя.
Незадолго до начала конкурса, я следил за активностью в github-репозиториях разработчиков конкурса. В репозитории codeforces-commons был добавлен файл QuadTree.java, и уже тогда появились первые догадки, что конкурс будет с большим количеством юнитов. Только после того как приступил к реализации своего симулятора, я вспомнил про эту структуру, и начал её использовать. Ведь она же и используется в local runner. В приведенной реализации не хватало методов удаления точки, изменения координаты точки (удалить и заново добавить – неэффективно), клонирование дерева. Пришлось самому их добавить.
Проверка юнитов на коллизии – самая затратная операция в моем коде, и я с трудом укладывался в ограничение по времени.
Менеджер команд
Менеджер команд? Очередь с приоритетами для отрядов? Отложенные и отменяемые команды? Всего этого нет. Как было описано выше, все решения принимаются только на основе текущей ситуации, и зная последний приказ для каждого юнита. Доступные действия размазаны по 60 тикам равномерно по принципу TickIndex % 10 == 0. Вычисления слишком затратны, чтобы делать из каждый тик.
Раунд 1
Несколько вечеров ушло на то, чтобы как-то с пользой приспособить юниты типа Arrv. Я решил их замешать с Tank и Ifv в шахматном порядке. Построение неоптимальное, но пока сойдёт.
Гифка
К началу первого раунда я стабильно побеждал многих лидеров. Невольно приходилось затачивать себя под соперников типа «бутерброд», хоть и понимая, что для финала они не годятся. Ориентировался главным образом на ud1 и GreenTea – у них стратегии больше были похожи на мою.
Подготовка к раунду 2.
Ко второму раунду предстояло научиться захватывать здания и управлять производством. Замешивание отрядов Arrv пришлось выкинуть. Оно занимало слишком много времени – в среднем 900 тиков. Даже с потенциальной оптимизацией в 2 раза это всё равно много, и затею пришлось бросить.
Стартовые отряды Arrv, Tank, Ifv, а также свежепостроенные, разбегались захватывать здания, чтобы минимизировать суммарную длину пути. Это стандартная задача о назначении, решаемая венгерским алгоритмом. Больше алгоритм выбора здания не менялся. Стоило добавить учет типов техники противника, но это не казалось приоритетной фичей.
Проблема производительности вышла не первый план. Количество юнитов на карте увеличилось, количество групп тоже, а значит и количество всевозможных ходов.
Около недели я потратил на оптимизации. Пришлось оптимизировать в ущерб точности. Вместо того, чтобы симулировать действия на всей карте, я делал симуляцию в окрестности каждой группы отдельно, а потом склеивал результаты.
Во избежание всяческих конфузов с ядерными бомбами, я отключал эти оптимизации, когда на карте есть хотя бы одна бомба.
Пришлось пойти дальше, и отключить проверки на коллизии, когда группы движутся по прямой, или крутятся.
Ну и последнее — перебирать все 12 направлений для Move бессмысленно, если вокруг нету врагов.
А нет, не последнее. Группы с четными номерами ходят по четным ходам, с нечетными — по нечетным. Только что построенные (aka бомжи) — каждый 3-й ход. Исключения есть для выделенных отрядов, и в режиме ядерной бомбы, а также в начале игры (< 3000 тиков).
Подготовка к финалу
В финале необходимо было контролировать количество вражеских юнитов, и где примерно они находятся. Для каждого юнита по Id запоминалось где последний раз он был виден. Есть 3 массива:
Обычный массив видимой техники (visible)
Массив проверенной невидимой техники (checked). Известно где последний раз был виден каждый Id, но точно известно, что его там уже нет.
Массив непроверенной невидимой техники (unchecked). Это значит, что предстоит разведать эту территорию на предмет наличия врага.
Заполнение массивов происходит следующим образом:
- В начале игры заполняем unchecked симметрично своим юнитам. Это даёт хоть какой-то начальный ориентир. Закономерности в Id найти не удалось, но это не проблема, можно генерировать их лениво по первому появлению.
Как это выглядит
- В начале каждого тика перекладываем из unchecked в checked, если точка стала видимой, а также из visible в unchecked, если юнит пропал из области видимости. Если юнит остался в зоне видимости, но его Durability стало равно 0, то значит он убит.
- Игровой симулятор проставляет Id в порядке появления новой техники. Есть вся информация, чтобы точно определить где и когда появится новый юнит, с каким Id, и какого типа. Коллизии, когда в один тик появляются несколько юнитов достаточно редки.
Радиус видимости достаточно большой, чтобы точно определить убит юнит, или пропал из видимости. Исключение составляет уничтожение ядерным ударом, но это очень редкий случай. Поэтому «мертвых душ» почти не оставалось.
С быстрой проверкой на видимость отлично справлялся тот же QuadTree, тем более что это нужно делать 1 раз за тик.
Это, пожалуй, всё, что было сделано для поддержки игры в тумане войны.
Таймлимиты я так и не поборол, моя программа по-прежнему с некоторыми соперниками на некоторых картах не укладывается в 220 секунд. Но, тем не менее, успевает обеспечить преимущество по очкам перед падением.
Немного не повезло в финале — занял в итоге 4-е место, а в песочнице 2-е. В следующий раз будем сильнее.
Всем спасибо. До встречи в Russian AI Cup 2018, а с кем-то, может быть, и раньше.
Код