Всем привет! Хочу рассказать про историю своей победы в ежегодном соревновании по написанию игровых ботов Russian AI Cup, в 2017. В финале бот выиграл 98% игр, что, как оказалось, наивысший результат по финалам среди всех годов проведения чемпионата. Также занял 1-е место в песочнице по завершению её работы, в пике переходя за 4000 очков рейтинга.
Эта статья может быть интересна участникам, болельщикам и просто интересующимся тематикой AI и написанием игровых ботов. Надеюсь вы сможете почерпнуть для себя что-то новое. В свою очередь и мне бы хотелось почитать статьи от участников, сравнить подходы и ход мыслей.
О задаче этого года уже было подробно написано тут. Вкратце: это война большим количеством юнитов разных типов: танки, бтр, ремонтные машины, истребители, вертолеты. Изначально дается 500 единиц техники, но можно захватывать заводы и производить новую технику без ограничений. Эта тематика меня сразу заинтересовала, т.к. раньше любил играть в стратежки вроде Dune (еще на приставке Sega), Red Alert, Star Craft 1 & 2.
Выступаю не первый год, и не только в Russian AI Cup-е, под ником GreenTea. Может быть кто-то по помнит меня по ants.aichallenge.org, отчет.
О подходе в этом году. Подход был серьезный, можно даже сказать профессиональный :)
В этом году было больше всего жалоб от людей, что мол “очень сложно”. Управление тяжелое. Надо написать много вспомогательного кода, чтобы научить бота делать даже простейшие вещи — это так. Например, не было такой штуки как автоматический поиск пути для юнитов. Так, чтобы указал конечную точку для движения, и больше не думать, а юниты сами объедут все препятствия. Такого не было. Юниты двигаются по прямой натыкаются на других юнитов и стоят… Борьба с застряваниями — это была постоянная боль.
Далее, возможные команды боту имитируют действия, которые выполняет человек, играя в стратегию. А именно: выделение юнитов в прямоугольную рамку, послать выделенных юнитов через атаку, назначить / выделить группу и тд. Плюс к этому, количество действий жестко лимитировано. Выполнять действия в таком виде гораздо сложнее, чем напрямую назначать команды каждому отдельному юниту. Это привело к тому, что очень многие участники не вышли ни во что более сложнее, чем просто собрать всех юнитов в одну кучу, перемешать хорошенько и отправить на ближайшего врага. Позднее это эволюционировало в создание очень аккуратно построенной фаланги (в народе — бутерброд), которая медленно ползла на врага и сделать что-либо с ней очень сложно. Но суть осталась та же. В RTS это называется death ball, т.е. шар юнитов который убивает все на своем пути. Организаторы даже ввели возможность нанесения ядерного удара, чтобы таким бутербродам жилось не так легко — ведь в куче юниты более уязвимы. Но, как оказалось, “правильный” бутерброд не особо боится ядерных ударов, потому что ремонтные машинки успевают его “вылечить”.
Но хотелось бы выступить в защиту организаторов. Мне тематика данного года понравилась больше всего, по сравнению с предыдущими годами. Просто она дает очень большой простор для творчества. Судите сами: 500+ юнитов пяти разных уникальных типов, возможность их делить и комбинировать различные формации. Также отдельное спасибо за упрощенную физику, отсутствие таких понятий как ускорение, поворот юнитов — все это ненужная шелуха которая добавляет сложности и рутины на ровном месте, мешая сконцентрироваться на собственно стратегиях.
Однако, богатство возможностей предоставляемых игрой, это тоже дополнительная сложность. Помню, как первые несколько дней после прочтения правил, в голове была полная неразбериха. Как подступить к задаче? Только спустя какое-то время, в подсознании начало что-то выстраиваться.
Изначально было понятно, что бутерброд — это гиблое дело, потому что при введении зданий, которые надо захватывать, он просто не успеет собраться и что либо захватить. Поэтому начал с разбиения на группы. Решил что в каждой у меня будет по 25 юнитов. Итого 20 штук. Почему такой размер? Это дает хорошую мобильность, трудно нанести большой ущерб ядерной бомбой. Также 25 юнитов по размеру хорошо вписываются в игровую клетку (поле было 32 на 32 клетки). Чуть позднее истребители были объединены в одну пачку 100 юнитов, т.к. в таком виде они имеют наибольшую ударную мощь, и в то же время практически не бояться ядерных ударов.
Далее учим группы двигаться. Важно чтобы при движении они не натыкались друг на друга. Решил аппроксимировать группу кругом, который содержит всех юнитов. А именно кругом, потому что коллизии для кругов считать проще всего. Коллизии можно считать 2мя способами:
Теперь вопрос куда двигаться. Для этого применяем метод потенциальных полей (ПП), суть которого заключается в том, что хорошие позиции должны притягивать группу, а плохие — наоборот отталкивать. Размер анализируемой клетки по методу ПП я взял 32 на 32, потому что в неё хорошо помещается группа размером 25 юнитов а также на клетки такого же размера разделяется карта погоды и ландшафта. Далее вопрос как же оценить, позицию, стоит ли в неё идти или нет?
Ниже приведу все параметры, которые я учитывал при оценке клетки на момент финала:
На скрине выше визуализация ПП для бтр (оранжевого цвета), которая уже была написана после финалов. В этом году я как то совсем обошелся без визуализации. Константы для формул прикидывал в уме, проверял в дебагере, и оно как-то сходу все заработало.
Вообще процесс улучшения бота был таким:
Чтобы игра в локал раннере не длилась вечно важно чтобы бот думал быстро. Поэтому всевозможные кэши и профайлер должны стать вашими друзьями.
Хорошо, потенциальные поля у нас есть. Далее вопрос в том, в каком порядке двигаться? Действия ведь ограничены. Какая группа должна походить первой? Расчет такой:
Наибольший приоритет имеет группа с максимальным scoreDiff.
Таким образом, если мы уже ранее назначили группе идти в клетку с максимумом очков и она туда идет, то её scoreDiff будет равен 0, и приказывать идти туда повторно не надо, что и логично. Также очки пропорциональны количеству юнитов, а значит — чем больше группа, тем выше окажется её приоритет действий.
Несколько слов о боевой системе. Она довольно примитивно симулирует исход битвы, с заданным количеством единиц техники с обеих сторон. Причем если допустим имеется 2 танка с процентом прочности 0.5 оба, то симулятор боя просто суммирует все HP и считает что это 1 целый танк. Бой длится по раундам. Каждый раунд атакует каждая из сторон, и повреждения вычитаются. Причем если в группе соперника имеется несколько типов юнитов, то стреляет по каждому типу по очереди. Бой заканчивается, когда нанесенный урон обеих сторон равен 0, что происходит например когда одна из групп убивает другую, или с одной стороны остались танки, а с другой истребители, и они не могут атаковать друг друга. Как можно заметить, система довольно не точная, но зато очень быстрая, и в большинстве случаев довольно адекватно предсказывает исход боя. Для симулятора боя писал юнит тесты. Кстати очень грубый тест производительности показывает, что бой, где с одной стороны 25 танков и 25 ремонтных машинок, а с другой 25 танков, просчитывается 100000 раз за 519 мс, или 19 просчетов за 1 мс, что довольно неплохо. Попытки хоть немного увеличить точность данной системы привели к непомерному увеличению времени вычисления, и я на это дело забил.
При оценке боя в клетке берется радиус боя равный 2 радиусам группы. С одной стороны — все мое что есть в радиусе + юниты группы, с другой стороны — все что есть у противника радиусе боя. И скармливается это все симулятору боя. На выходе получаем структуру с информацией: урон минус потери, количество юнитов с обеих сторон после боя, конечный раунд.
Кроме исхода боя в оцениваемой клетке также учитывался маршрут перехода к этой клетке по прямой линии. Если этот маршрут опасно близко подходит к клеткам с врагами, то симулятор боя запускается и для них, а результат суммируется по всему пути.
Причем чтобы бот действовал в бою более осторожно, и атаковал только наверняка, неудачный исход боя — отрицательные очки, умножались на 10. И только после 10000-го тика, если бот видит что побеждает, то включается специальный агрессивных режим, при котором наоборот поощряется именно убийство врага, а защита сводится к минимуму.
Вначале бот функционировал только на ПП. Первым звоночком, что они не совсем справляются в некоторых ситуациях было то, что вертолеты плохо убегают от истребителей. Может конечно это особенность моей реализации, но я думаю из-за быстрого движения истребителей, действовать вертолетами тоже надо очень быстро и точно, заблаговременно прячась за бмп. Пришлось добавить пару костылей в ПП чтобы это поправить.
С появлением строений, а особенно фабрик, которые с огромной скоростью производят юнитов, стало понятно, что ПП откровенно не справляются с быстрым и оптимальным захватом. А фабрики нужно захватывать без промедлений, тк. скорость производства юнитов очень большая, и захватив их пораньше можно буквально давить превосходящим числом.
ПП еще плохи тем, что надо подбирать всякие формулы и магические константы так, чтобы все работало. Все поля в итоге суммируются, а значит влияют друг на друга. Добавив мощное поле на захват фабрик, это могло привести к тому что юниты будут стремиться захватить даже несмотря на опасность, что совершенно не подходит.
Очень просто все сломать, неаккуратно подправив какой нибудь коэффициент. Гораздо проще казалось написать некую отдельную стратегию, которая бы отвечала за захват фабрик, и имела бы глобально больший приоритет чем ПП.
Далее было несколько дней размышлений — выдумывания некой новой архитектуры. Хотелось чтобы она позволяла красиво, без костылей, без нагромождения кода встраивать все что не вписывается в ПП. Помню как ходил около часа по квартире кругами, и перебирал в голове разные способы организации кода.
Итак, было:
Пачка if-ов
ПП
Пачка if-ов
Стало:
Стратегия 1
Стратегия 2
…
Стратегия N
Каждая стратегия наследуется от класса BattleStrategy, имеет тип enum BattleStrategyType, должна реализовать метод abstract boolean apply(Move move);
Все стратегии существуют в 1 экземпляре, содержаться в списке и вызываются последовательно, от более к менее приоритетным. Если метод apply вернул true, значит стратегия сделала ход, и дальше по списку стратегии не рассматриваем. Если же false — значит текущая стратегия не считает необходимым применяться на данном тике, и можно попробовать следующую. Далее привожу весь список стратегий на момент финала, от более к менее приоритетным.
AvoidNuclearStrike — уклонение от ядерных ударов.
CreateGroups — создание групп из свободных юнитов на фабриках, при срабатывании определенных условий.
CreateScouts — создание истребителей разведчиков, которые могут выполнять функции наводчика ядерной бомбы.
DoNuclearStrike — нанесение ядерного удара.
FactoryProduction — заказ производства юнитов нужного типа на фабрике.
JoinGroups — объединение 2 групп в одну если общее количество групп слишком возросло.
Pack — уплотнение юнитов в группе, так чтобы её радиус уменьшился, это делает бой более эффективным.
TurnToEnemy — повернуть группу широкой частью к противнику.
JoinCollidedGroups — соединение групп, которые случайно врезались друг в друга и запутались.
CoptersStrategy — стратегия убегания вертолетов за бмп в случае опасности от вражеских истребителей.
FightersStrategy — стратегия погони истребителями за вражескими вертолетами, а также защиты танков и ремонтных машинок от вертолетов.
FactoryDefence — защита фабрик от захвата, когда враг приближается к ним слишком близко.
FacilityCapture — захват фабрик, с возможностью переназначения целей захвата если ситуация на поле боя меняется
KillProduction — уничтожение беззащитных вражеских юнитов, которые производятся на фабрике.
PotentialField — То самое старое ПП, которое практически не поменялось с момента 1го раунда. Как видите, является наименее приоритетной стратегией.
Ну а пока писались все эти стратегии, перед вторым раундом, я со спокойствием наблюдал, как мой бот, мелкими группам без проблем разносит оппонентов в режиме “со строениями”. И казалось, что никто даже и близко ничего не может противопоставить и в таком же виде оно дойдет до финала. Пока не появился ud1. Он не разделял отряды так мелко, а использовал всего 5 штук, по 100 на каждый тип юнита. Помню как в серии боев со мной — победил все. Я был в шоке. Как же так, начал разбираться. Оказалось что организаторы подрезали скорость захвата фабрик, и мои маленькие группы слишком медленно их захватывали. Переделал стратегию захвата фабрик чтобы одновременно могло захватывать сразу 2 группы, и ситуация против ud1 вроде на время нормализовалась. Но через несколько дней опять двадцать пять! После внимательного изучения повторов пришел к выводу, что мои группы слишком бояться его больших групп, постоянно отступают, сдают уже захваченные фабрики, а перехватить его фабрики тоже не хватает силенок, потому что там уже успевают построится танки… Буквально в тот же вечер принял решение не делить так мелко. И сделал из танков, бмп и ремонтных машинок 3 большие пачки по 100 юнитов. Изначально меня останавливала от такого шага боязнь что большие группы будут сильно уязвимы для ядерного удара. Но, как показала практика, захват и удержание фабрик на начальном этапе — больше влияет на исход боя. Плюс на фабриках тоже начал строить танки, как более универсальный юнит. Вертолеты хоть и мощнее против земли, но медленнее строятся и слишком уязвимы от истребителей. Тесты с прошлой версией своего бота показали полную доминацию новой версии.
Параллельно с написанием стратегий, я постепенно улучшал архитектуру. Одно из нововведений — это сохранение информации о текущем выполнении стратегии внутри объекта группы. Например, при захвате фабрики туда можно сохранить на какую фабрику направляемся. Но самое полезное, что я сохраняю там — это триггер стратегии.
Метод isShouldApply() вызывается стратегией у всех групп, которые в данный момент выполняют данную стратегию, и которые имеют триггеры. Если isShouldApply() возвращает true, то вызывается apply. Если и apply возвращает true, то значит стратегия совершила свой ход из триггера, и ход завершается. Если после выполнения apply триггер не поменялся, то он удаляется. Триггер может из apply() вернуть false и служить чисто в качестве выключателя стратегии для группы, при наступлении некоего условия, чтобы она снова могла рассматриваться менее приоритетными стратегиями. Это все позволяет выполнять сложные цепочки действий, нанизывая триггеры как бусы. Например совершить движение группой — это не так просто, вначале надо удостоверится что она выбрана.
Метод selectAndCallTrigger(), который повсеместно используется, проверяет выбрана ли группа. Если да, до триггер выполняется сразу, а если нет то действие CLEAR_AND_SELECT выполняется на этом тике, а переданный триггер на следующем, когда придет время сделать ход, и управление дойдет до этой стратегии. Если после выделения группы более приоритетная стратегия перехватывает управление и тоже совершает выделение уже другой группы, то триггер SelectGroupActionStrategyTrigger текущей стратегии удаляется, но случается такое не очень часто. Это лишь простейший пример. В объединении групп например используется 3 вложенных триггера. Преимущество этого подхода в том, что вся логика относящаяся к стратегии расположена в одном отдельном файле, нет кучи if-ов и выглядит как последовательность действий разделенная условиями в isShouldApply(). И как результат — позволяет очень быстро колбасить новые стратегии, не ломая и не затрагивая остальные.
Недостаток данной архитектуры в том, что все стратегии имеют жестко заданный неизменный приоритет, хотя приоритет в некоторых ситуациях не так уж очевиден. Например, что важнее, защищать свою фабрику, или атаковать вражескую? У меня защита в приоритете, но может оказаться так, что группа, которая должна использоваться для защиты, гораздо быстрее произведет захват. Для этой ситуации пришлось написать костыль позволяющий заглядывать из стратегии защиты в стратегию захвата, и не трогать захват если он более перспективный. Но в целом, данная ситуация скорее исключение.
Чтобы не попасть на опасного противника выполняя маневры в стратегиях, и не врезаться в своих, использовалась часть вычислений, которые писались еще для ПП. Например повсеместно использовалась такая функция:
Идем к примеру захватывать фабрику, и каждый ход проверяем все группы, которые двигаются, используя триггер — “путь к цели свободен и безопасен?” Если нет — то завершаем стратегию для группы.
После введения тумана войны, практически не переделывал бота. Добавил только запоминание позиций вражеских юнитов, где видел их раньше. У истребителей разведчиков добавил дополнительный приоритет “просветить” клетки со скрытыми вражескими юнитами. Если разведка показала, что в клетке больше нет скрытых юнитов — то полностью убираем их, как будто их убили.
Другие хитрости
Для того, чтобы бот сразу не тратил все действия, а потом не провисал без команд, было сделано, чтобы отведенные действия тратились равномерно в течении 60 тиков.
Когда у противника остается 100 тиков для следующего ядерного удара, каждое следующее действие выполняем на 1 тик позже чем могли бы. Это помогает “зарезервировать” некоторое количество действий перед ядерным ударом чтобы развести юнитов в стороны.
Движение на ход противнику. Если ПП приказывает идти в клетку, и в ней есть юниты противника, которых группа может атаковать, то движение совершается не в центр клетки. По среднему вектору движения юнитов противника и расстоянию до них прогнозируется точка по ходу его движения, в которой можно их перехватить. И группа отправляется сразу в эту откорректированную точку.
В бою важно чтобы юниты стояли как можно более плотно прижаты друг к другу, без пустот. Это дает более сконцентрированный огонь. Погода и ландшафт влияют на скорость юнитов, и если ничего не предпринимать плотная начальная формация группы постепенно распадается, вытягивается… Чтобы определить плотность, можно поделить площадь круга содержащего группу, на суммарную площадь юнитов. Результат до 3 — я считал терпимым. От 3 до 5 — разреженно. Больше 5 — сильно разрежена.
Можно бороться с этим двумя способами:
При выборе захвата зданий, приоритет по очкам отдается фабрикам. Как мне показалось — командные центры не оказывают слишком большого влияния на бой. Причем боевые наземные юниты имеют еще больший приоритет по захвату фабрик. Таким образом, если допустим возле места старта имеется несколько командных центров, а ближе к центру имеется несколько фабрик, то танки и бмп поедут сразу захватывать фабрики, более уязвимые ремонтники — останутся захватывать командные центры и приедут позже.
Каждый ход стратегия захвата зданий строит некий “оптимальный” план захвата. “Оптимальный” в кавычках, потому что это очень грубая и приблизительная оптимальность, и совершенствовать её можно было бы еще долго. Потом стратегия сверяет с текущим выполнением, в порядке по убыванию приоритетности захвата. Если обнаруживается отклонение от “оптимального” плана — то выполнение тут же корректируется. Таким образом стратегия захвата чутко реагирует на изменяющуюся на поле боя ситуацию.
При захвате вражеский фабрик, группа захвата становятся прижимаясь к углу, где появляются произведенные вражеские юниты. Это не позволяет новой технике накапливаться.
Вообще новые юниты, пока они еще не собрались в группу, представляют собой удобную мишень. Поэтому есть отдельная стратегия по убийству таких свободных юнитов. Суть её заключается в том чтобы стать группой на линии производства. Очень удобно свободные истребители выставлять таким вот образом, блокируя противнику производство его истребителей и вертолетов.
Чего не хватает данному боту чтобы достичь совершенства?
Нет синхронных атак несколькими группами. Допустим, если у меня есть 2 группы по 30 танков, а у противника между ними 1 группировка в 40 танков, то они каждая по отдельности будут бояться. А в идеале должны были бы одновременно напасть с разных сторон. Казалось бы довольно очевидное для человека рациональное поведение, но так и не сообразил как это проще запрограммировать. Слишком много на этот маневр времени тратить не хотел, поэтому откладывал на потом, но так руки и не дошли.
Недостаточно оптимальный захват фабрик. По сути у меня жадный алгоритм. Можно было бы свести до чего то типа незамкнутой задачи коммивояжера, и находить план захвата всех фабрик, а не только самых ближайших. Но это бы дало какое то улучшение только на картах где фабрик много, а это не такой уж частый случай, поэтому не стал заморачиваться.
Плохое микро в бою за счет примитивного анализатора боя. Это было наглядно продемонстрировано ботом Milanin, который в плане миро выше всех на 2 головы. Он, управляя фалангами из 20 танков и 20 ремонтных машинок, умудряется иногда без потерь перестрелять превосходящие силы, умело двигаясь и вращая эти фаланги танками в сторону противника. К сожалению у Milanin-а очень медленный начальных захват карты из-за сборки тех самых смешанных фаланг. Поэтому даже не самый топовый бот может его задавить чисто количеством юнитов, произведенных на более быстро захваченных фабриках.
Заключение
В итоге у меня получился на мой взгляд довольно крепко сбитый бот, с отсутствием откровенно слабых мест. Когда смотрю повторы, не замечаю слишком критичных ошибок. Чего-то сверх гениального в нем нет. До начала финалов не был уверен что выиграю, т.к. в тестовых играх с другими топами, такими как Adler, oreshnik, Milanin — результаты были нестабильными. Но, как оказалось, очень неожиданно для меня самого — первое место с большим отрывом.
Исходный код бота доступен тут.
Эта статья может быть интересна участникам, болельщикам и просто интересующимся тематикой AI и написанием игровых ботов. Надеюсь вы сможете почерпнуть для себя что-то новое. В свою очередь и мне бы хотелось почитать статьи от участников, сравнить подходы и ход мыслей.
О задаче этого года уже было подробно написано тут. Вкратце: это война большим количеством юнитов разных типов: танки, бтр, ремонтные машины, истребители, вертолеты. Изначально дается 500 единиц техники, но можно захватывать заводы и производить новую технику без ограничений. Эта тематика меня сразу заинтересовала, т.к. раньше любил играть в стратежки вроде Dune (еще на приставке Sega), Red Alert, Star Craft 1 & 2.
Выступаю не первый год, и не только в Russian AI Cup-е, под ником GreenTea. Может быть кто-то по помнит меня по ants.aichallenge.org, отчет.
О подходе в этом году. Подход был серьезный, можно даже сказать профессиональный :)
- Не проморгать начало, лучше начать сразу с беты.
- Использовать наработки с прошлых чемпионатов: это всякие утилитные классы вроде точки, вектора, отрезка, всякие самописные математические функции.
- Настроить локально среду для тестирования бота.
- Взять отпуск на пару недель чемпионата, чтобы максимально погрузиться в процесс.
- Много работать, жертвовать практически всем свободным временем. Это хадкор да, но что поделать.
В этом году было больше всего жалоб от людей, что мол “очень сложно”. Управление тяжелое. Надо написать много вспомогательного кода, чтобы научить бота делать даже простейшие вещи — это так. Например, не было такой штуки как автоматический поиск пути для юнитов. Так, чтобы указал конечную точку для движения, и больше не думать, а юниты сами объедут все препятствия. Такого не было. Юниты двигаются по прямой натыкаются на других юнитов и стоят… Борьба с застряваниями — это была постоянная боль.
Далее, возможные команды боту имитируют действия, которые выполняет человек, играя в стратегию. А именно: выделение юнитов в прямоугольную рамку, послать выделенных юнитов через атаку, назначить / выделить группу и тд. Плюс к этому, количество действий жестко лимитировано. Выполнять действия в таком виде гораздо сложнее, чем напрямую назначать команды каждому отдельному юниту. Это привело к тому, что очень многие участники не вышли ни во что более сложнее, чем просто собрать всех юнитов в одну кучу, перемешать хорошенько и отправить на ближайшего врага. Позднее это эволюционировало в создание очень аккуратно построенной фаланги (в народе — бутерброд), которая медленно ползла на врага и сделать что-либо с ней очень сложно. Но суть осталась та же. В RTS это называется death ball, т.е. шар юнитов который убивает все на своем пути. Организаторы даже ввели возможность нанесения ядерного удара, чтобы таким бутербродам жилось не так легко — ведь в куче юниты более уязвимы. Но, как оказалось, “правильный” бутерброд не особо боится ядерных ударов, потому что ремонтные машинки успевают его “вылечить”.
Но хотелось бы выступить в защиту организаторов. Мне тематика данного года понравилась больше всего, по сравнению с предыдущими годами. Просто она дает очень большой простор для творчества. Судите сами: 500+ юнитов пяти разных уникальных типов, возможность их делить и комбинировать различные формации. Также отдельное спасибо за упрощенную физику, отсутствие таких понятий как ускорение, поворот юнитов — все это ненужная шелуха которая добавляет сложности и рутины на ровном месте, мешая сконцентрироваться на собственно стратегиях.
Однако, богатство возможностей предоставляемых игрой, это тоже дополнительная сложность. Помню, как первые несколько дней после прочтения правил, в голове была полная неразбериха. Как подступить к задаче? Только спустя какое-то время, в подсознании начало что-то выстраиваться.
Изначально было понятно, что бутерброд — это гиблое дело, потому что при введении зданий, которые надо захватывать, он просто не успеет собраться и что либо захватить. Поэтому начал с разбиения на группы. Решил что в каждой у меня будет по 25 юнитов. Итого 20 штук. Почему такой размер? Это дает хорошую мобильность, трудно нанести большой ущерб ядерной бомбой. Также 25 юнитов по размеру хорошо вписываются в игровую клетку (поле было 32 на 32 клетки). Чуть позднее истребители были объединены в одну пачку 100 юнитов, т.к. в таком виде они имеют наибольшую ударную мощь, и в то же время практически не бояться ядерных ударов.
Далее учим группы двигаться. Важно чтобы при движении они не натыкались друг на друга. Решил аппроксимировать группу кругом, который содержит всех юнитов. А именно кругом, потому что коллизии для кругов считать проще всего. Коллизии можно считать 2мя способами:
- Геометрически, сравнивая на сколько сближаются отрезки пути при движении групп. С этого способа я начал.
- Симуляцией: с некоторым шагом имитируем движение всех групп, и проверяем не столкнулись ли они. Этот способ лучше, т.к. учитывает динамику движения. Правда, чтобы симуляция не тормозила, пришлось использовать шаг в 30 тиков.
Теперь вопрос куда двигаться. Для этого применяем метод потенциальных полей (ПП), суть которого заключается в том, что хорошие позиции должны притягивать группу, а плохие — наоборот отталкивать. Размер анализируемой клетки по методу ПП я взял 32 на 32, потому что в неё хорошо помещается группа размером 25 юнитов а также на клетки такого же размера разделяется карта погоды и ландшафта. Далее вопрос как же оценить, позицию, стоит ли в неё идти или нет?
Ниже приведу все параметры, которые я учитывал при оценке клетки на момент финала:
- Позиция на поле: хорошо быть ближе к центру, плохо на краях и очень плохо в углах.
- Тип местности и погода: эти параметры влияют на характеристики юнитов, поэтому избегаем плохой погоды и трудно проходимой местности.
- Расстояние до других групп: не подходить слишком близко во избежание коллизий. При обнаружении коллизии — выписываем максимальный штраф.
- Бой с врагом: могу ли в данной клетке уничтожить противника, или он уничтожит меня?
- Захват фабрик: насколько близко клетка находится к зданию, которое можно захватить.
- Разведка: сколько клеток могу увидеть находясь в данной, учитывая как давно их не видел.
- [для воздушных юнитов] Починка: подлететь к машинкам ремонта и починить повреждения — это хорошо.
- [для ремонтных машинок] Починка: подъехать к битым летающим юнитам.
- [для истребителя наводчика ядерки] Подлететь к самой большой куче врагов и наводить на неё ядерный удар.
На скрине выше визуализация ПП для бтр (оранжевого цвета), которая уже была написана после финалов. В этом году я как то совсем обошелся без визуализации. Константы для формул прикидывал в уме, проверял в дебагере, и оно как-то сходу все заработало.
Вообще процесс улучшения бота был таким:
- Внимательно смотрим на игры бота на сайте или локально, и находим места, где бот действует нерационально. Если таких мест много, записываем, чтобы не забыть.
- При выборе реализации улучшения, стараемся рассмотреть несколько способов, и выбираем тот, который скажем так “наименее костыльный”.
- Работаем над улучшением и сверяем с предыдущей версией бота, до тех пор, пока новая версия не будет стабильно чаще побеждать. Для проверки стабильности брал штук 20 разных карт, прогонял в localrunner-е и подсчитывал количество побед новой версии. Все бои просматривал, чтобы воочию убедиться что улучшение работает как надо.
- Делаем коммит и сохраняем новую версию как последнюю, с которой будем тестировать. Заливаем то что получилось на сайт.
- Если во время локально просмотра боя находится бага, то из-за фиксированного seed и отсутствия рандома в движке её сразу можно воспроизвести, продебажить и починить. Кстати, ни разу не использовал утилиту repeater для поиска багов.
Чтобы игра в локал раннере не длилась вечно важно чтобы бот думал быстро. Поэтому всевозможные кэши и профайлер должны стать вашими друзьями.
Хорошо, потенциальные поля у нас есть. Далее вопрос в том, в каком порядке двигаться? Действия ведь ограничены. Какая группа должна походить первой? Расчет такой:
- Сканируем все клетки в неком радиусе от группы и находим клетку с наибольшим количеством очков bestScore.
- Вычисляем количество очков currentScore клетки, куда данная группа уже направляется (если она двигается), или текущей клетки (если стоит на месте).
- scoreDiff = bestScore — currentScore
Наибольший приоритет имеет группа с максимальным scoreDiff.
Таким образом, если мы уже ранее назначили группе идти в клетку с максимумом очков и она туда идет, то её scoreDiff будет равен 0, и приказывать идти туда повторно не надо, что и логично. Также очки пропорциональны количеству юнитов, а значит — чем больше группа, тем выше окажется её приоритет действий.
Несколько слов о боевой системе. Она довольно примитивно симулирует исход битвы, с заданным количеством единиц техники с обеих сторон. Причем если допустим имеется 2 танка с процентом прочности 0.5 оба, то симулятор боя просто суммирует все HP и считает что это 1 целый танк. Бой длится по раундам. Каждый раунд атакует каждая из сторон, и повреждения вычитаются. Причем если в группе соперника имеется несколько типов юнитов, то стреляет по каждому типу по очереди. Бой заканчивается, когда нанесенный урон обеих сторон равен 0, что происходит например когда одна из групп убивает другую, или с одной стороны остались танки, а с другой истребители, и они не могут атаковать друг друга. Как можно заметить, система довольно не точная, но зато очень быстрая, и в большинстве случаев довольно адекватно предсказывает исход боя. Для симулятора боя писал юнит тесты. Кстати очень грубый тест производительности показывает, что бой, где с одной стороны 25 танков и 25 ремонтных машинок, а с другой 25 танков, просчитывается 100000 раз за 519 мс, или 19 просчетов за 1 мс, что довольно неплохо. Попытки хоть немного увеличить точность данной системы привели к непомерному увеличению времени вычисления, и я на это дело забил.
При оценке боя в клетке берется радиус боя равный 2 радиусам группы. С одной стороны — все мое что есть в радиусе + юниты группы, с другой стороны — все что есть у противника радиусе боя. И скармливается это все симулятору боя. На выходе получаем структуру с информацией: урон минус потери, количество юнитов с обеих сторон после боя, конечный раунд.
Кроме исхода боя в оцениваемой клетке также учитывался маршрут перехода к этой клетке по прямой линии. Если этот маршрут опасно близко подходит к клеткам с врагами, то симулятор боя запускается и для них, а результат суммируется по всему пути.
Причем чтобы бот действовал в бою более осторожно, и атаковал только наверняка, неудачный исход боя — отрицательные очки, умножались на 10. И только после 10000-го тика, если бот видит что побеждает, то включается специальный агрессивных режим, при котором наоборот поощряется именно убийство врага, а защита сводится к минимуму.
Вначале бот функционировал только на ПП. Первым звоночком, что они не совсем справляются в некоторых ситуациях было то, что вертолеты плохо убегают от истребителей. Может конечно это особенность моей реализации, но я думаю из-за быстрого движения истребителей, действовать вертолетами тоже надо очень быстро и точно, заблаговременно прячась за бмп. Пришлось добавить пару костылей в ПП чтобы это поправить.
С появлением строений, а особенно фабрик, которые с огромной скоростью производят юнитов, стало понятно, что ПП откровенно не справляются с быстрым и оптимальным захватом. А фабрики нужно захватывать без промедлений, тк. скорость производства юнитов очень большая, и захватив их пораньше можно буквально давить превосходящим числом.
ПП еще плохи тем, что надо подбирать всякие формулы и магические константы так, чтобы все работало. Все поля в итоге суммируются, а значит влияют друг на друга. Добавив мощное поле на захват фабрик, это могло привести к тому что юниты будут стремиться захватить даже несмотря на опасность, что совершенно не подходит.
Очень просто все сломать, неаккуратно подправив какой нибудь коэффициент. Гораздо проще казалось написать некую отдельную стратегию, которая бы отвечала за захват фабрик, и имела бы глобально больший приоритет чем ПП.
Далее было несколько дней размышлений — выдумывания некой новой архитектуры. Хотелось чтобы она позволяла красиво, без костылей, без нагромождения кода встраивать все что не вписывается в ПП. Помню как ходил около часа по квартире кругами, и перебирал в голове разные способы организации кода.
Итак, было:
Пачка if-ов
ПП
Пачка if-ов
Стало:
Стратегия 1
Стратегия 2
…
Стратегия N
Каждая стратегия наследуется от класса BattleStrategy, имеет тип enum BattleStrategyType, должна реализовать метод abstract boolean apply(Move move);
Все стратегии существуют в 1 экземпляре, содержаться в списке и вызываются последовательно, от более к менее приоритетным. Если метод apply вернул true, значит стратегия сделала ход, и дальше по списку стратегии не рассматриваем. Если же false — значит текущая стратегия не считает необходимым применяться на данном тике, и можно попробовать следующую. Далее привожу весь список стратегий на момент финала, от более к менее приоритетным.
AvoidNuclearStrike — уклонение от ядерных ударов.
CreateGroups — создание групп из свободных юнитов на фабриках, при срабатывании определенных условий.
CreateScouts — создание истребителей разведчиков, которые могут выполнять функции наводчика ядерной бомбы.
DoNuclearStrike — нанесение ядерного удара.
FactoryProduction — заказ производства юнитов нужного типа на фабрике.
JoinGroups — объединение 2 групп в одну если общее количество групп слишком возросло.
Pack — уплотнение юнитов в группе, так чтобы её радиус уменьшился, это делает бой более эффективным.
TurnToEnemy — повернуть группу широкой частью к противнику.
JoinCollidedGroups — соединение групп, которые случайно врезались друг в друга и запутались.
CoptersStrategy — стратегия убегания вертолетов за бмп в случае опасности от вражеских истребителей.
FightersStrategy — стратегия погони истребителями за вражескими вертолетами, а также защиты танков и ремонтных машинок от вертолетов.
FactoryDefence — защита фабрик от захвата, когда враг приближается к ним слишком близко.
FacilityCapture — захват фабрик, с возможностью переназначения целей захвата если ситуация на поле боя меняется
KillProduction — уничтожение беззащитных вражеских юнитов, которые производятся на фабрике.
PotentialField — То самое старое ПП, которое практически не поменялось с момента 1го раунда. Как видите, является наименее приоритетной стратегией.
Ну а пока писались все эти стратегии, перед вторым раундом, я со спокойствием наблюдал, как мой бот, мелкими группам без проблем разносит оппонентов в режиме “со строениями”. И казалось, что никто даже и близко ничего не может противопоставить и в таком же виде оно дойдет до финала. Пока не появился ud1. Он не разделял отряды так мелко, а использовал всего 5 штук, по 100 на каждый тип юнита. Помню как в серии боев со мной — победил все. Я был в шоке. Как же так, начал разбираться. Оказалось что организаторы подрезали скорость захвата фабрик, и мои маленькие группы слишком медленно их захватывали. Переделал стратегию захвата фабрик чтобы одновременно могло захватывать сразу 2 группы, и ситуация против ud1 вроде на время нормализовалась. Но через несколько дней опять двадцать пять! После внимательного изучения повторов пришел к выводу, что мои группы слишком бояться его больших групп, постоянно отступают, сдают уже захваченные фабрики, а перехватить его фабрики тоже не хватает силенок, потому что там уже успевают построится танки… Буквально в тот же вечер принял решение не делить так мелко. И сделал из танков, бмп и ремонтных машинок 3 большие пачки по 100 юнитов. Изначально меня останавливала от такого шага боязнь что большие группы будут сильно уязвимы для ядерного удара. Но, как показала практика, захват и удержание фабрик на начальном этапе — больше влияет на исход боя. Плюс на фабриках тоже начал строить танки, как более универсальный юнит. Вертолеты хоть и мощнее против земли, но медленнее строятся и слишком уязвимы от истребителей. Тесты с прошлой версией своего бота показали полную доминацию новой версии.
Параллельно с написанием стратегий, я постепенно улучшал архитектуру. Одно из нововведений — это сохранение информации о текущем выполнении стратегии внутри объекта группы. Например, при захвате фабрики туда можно сохранить на какую фабрику направляемся. Но самое полезное, что я сохраняю там — это триггер стратегии.
public interface GroupStrategyTrigger {
boolean isShouldApply();
boolean apply(Move move);
}Метод isShouldApply() вызывается стратегией у всех групп, которые в данный момент выполняют данную стратегию, и которые имеют триггеры. Если isShouldApply() возвращает true, то вызывается apply. Если и apply возвращает true, то значит стратегия совершила свой ход из триггера, и ход завершается. Если после выполнения apply триггер не поменялся, то он удаляется. Триггер может из apply() вернуть false и служить чисто в качестве выключателя стратегии для группы, при наступлении некоего условия, чтобы она снова могла рассматриваться менее приоритетными стратегиями. Это все позволяет выполнять сложные цепочки действий, нанизывая триггеры как бусы. Например совершить движение группой — это не так просто, вначале надо удостоверится что она выбрана.
selectAndCallTrigger(movedGroup, move, new SelectGroupActionStrategyTrigger() {
@Override
public boolean apply(Move move) {
performMoveAction(movedGroup, target, target, move);
}
});
Метод selectAndCallTrigger(), который повсеместно используется, проверяет выбрана ли группа. Если да, до триггер выполняется сразу, а если нет то действие CLEAR_AND_SELECT выполняется на этом тике, а переданный триггер на следующем, когда придет время сделать ход, и управление дойдет до этой стратегии. Если после выделения группы более приоритетная стратегия перехватывает управление и тоже совершает выделение уже другой группы, то триггер SelectGroupActionStrategyTrigger текущей стратегии удаляется, но случается такое не очень часто. Это лишь простейший пример. В объединении групп например используется 3 вложенных триггера. Преимущество этого подхода в том, что вся логика относящаяся к стратегии расположена в одном отдельном файле, нет кучи if-ов и выглядит как последовательность действий разделенная условиями в isShouldApply(). И как результат — позволяет очень быстро колбасить новые стратегии, не ломая и не затрагивая остальные.
Недостаток данной архитектуры в том, что все стратегии имеют жестко заданный неизменный приоритет, хотя приоритет в некоторых ситуациях не так уж очевиден. Например, что важнее, защищать свою фабрику, или атаковать вражескую? У меня защита в приоритете, но может оказаться так, что группа, которая должна использоваться для защиты, гораздо быстрее произведет захват. Для этой ситуации пришлось написать костыль позволяющий заглядывать из стратегии защиты в стратегию захвата, и не трогать захват если он более перспективный. Но в целом, данная ситуация скорее исключение.
Чтобы не попасть на опасного противника выполняя маневры в стратегиях, и не врезаться в своих, использовалась часть вычислений, которые писались еще для ПП. Например повсеместно использовалась такая функция:
public boolean isCanSafelyMoveToPoint(Group g, Point target) {
prepareCachesForGroup(g);
return !isHasCollisions(g, target) && !isGroupInDanger(g) && calcBattleScoreOnPath(g, target) >= 0;
}Идем к примеру захватывать фабрику, и каждый ход проверяем все группы, которые двигаются, используя триггер — “путь к цели свободен и безопасен?” Если нет — то завершаем стратегию для группы.
После введения тумана войны, практически не переделывал бота. Добавил только запоминание позиций вражеских юнитов, где видел их раньше. У истребителей разведчиков добавил дополнительный приоритет “просветить” клетки со скрытыми вражескими юнитами. Если разведка показала, что в клетке больше нет скрытых юнитов — то полностью убираем их, как будто их убили.
Другие хитрости
Для того, чтобы бот сразу не тратил все действия, а потом не провисал без команд, было сделано, чтобы отведенные действия тратились равномерно в течении 60 тиков.
Когда у противника остается 100 тиков для следующего ядерного удара, каждое следующее действие выполняем на 1 тик позже чем могли бы. Это помогает “зарезервировать” некоторое количество действий перед ядерным ударом чтобы развести юнитов в стороны.
Движение на ход противнику. Если ПП приказывает идти в клетку, и в ней есть юниты противника, которых группа может атаковать, то движение совершается не в центр клетки. По среднему вектору движения юнитов противника и расстоянию до них прогнозируется точка по ходу его движения, в которой можно их перехватить. И группа отправляется сразу в эту откорректированную точку.
В бою важно чтобы юниты стояли как можно более плотно прижаты друг к другу, без пустот. Это дает более сконцентрированный огонь. Погода и ландшафт влияют на скорость юнитов, и если ничего не предпринимать плотная начальная формация группы постепенно распадается, вытягивается… Чтобы определить плотность, можно поделить площадь круга содержащего группу, на суммарную площадь юнитов. Результат до 3 — я считал терпимым. От 3 до 5 — разреженно. Больше 5 — сильно разрежена.
Можно бороться с этим двумя способами:
- Периодически делать команду SCALE внутрь группы. Иногда он плохо срабатывает, потому что юниты выстраиваются в длинные колбаски которые блокируют движение.
Тогда после сжатия можно выполнить раскрутку вокруг центра группы, и потом снова сжатие. Так повторять несколько раз. Но и так не всегда помогает, т.к. юниты имеют свойство застревать даже при вращении.
- Изначально, пока группа сжата, всегда двигаться ею с минимальной скоростью на текущем пути движения. Т.е. например если путь истребителей пролегает только по клеткам ясной погоды — то скорость не ограничивается, если там есть хотя бы одна клетка с грозой, то сразу при движении выставляется скорость для грозовой погоды. При таком подходе группа почти гарантировано не распадется. Этот подход я использовал для воздушных юнитов. Но не для земли, т.к. для земли важна максимальная скорость, для быстрого захвата строений. Авиация же здания не захватывает и скорости у неё и так достаточно.
При выборе захвата зданий, приоритет по очкам отдается фабрикам. Как мне показалось — командные центры не оказывают слишком большого влияния на бой. Причем боевые наземные юниты имеют еще больший приоритет по захвату фабрик. Таким образом, если допустим возле места старта имеется несколько командных центров, а ближе к центру имеется несколько фабрик, то танки и бмп поедут сразу захватывать фабрики, более уязвимые ремонтники — останутся захватывать командные центры и приедут позже.
Каждый ход стратегия захвата зданий строит некий “оптимальный” план захвата. “Оптимальный” в кавычках, потому что это очень грубая и приблизительная оптимальность, и совершенствовать её можно было бы еще долго. Потом стратегия сверяет с текущим выполнением, в порядке по убыванию приоритетности захвата. Если обнаруживается отклонение от “оптимального” плана — то выполнение тут же корректируется. Таким образом стратегия захвата чутко реагирует на изменяющуюся на поле боя ситуацию.
При захвате вражеский фабрик, группа захвата становятся прижимаясь к углу, где появляются произведенные вражеские юниты. Это не позволяет новой технике накапливаться.
Вообще новые юниты, пока они еще не собрались в группу, представляют собой удобную мишень. Поэтому есть отдельная стратегия по убийству таких свободных юнитов. Суть её заключается в том чтобы стать группой на линии производства. Очень удобно свободные истребители выставлять таким вот образом, блокируя противнику производство его истребителей и вертолетов.
Чего не хватает данному боту чтобы достичь совершенства?
Нет синхронных атак несколькими группами. Допустим, если у меня есть 2 группы по 30 танков, а у противника между ними 1 группировка в 40 танков, то они каждая по отдельности будут бояться. А в идеале должны были бы одновременно напасть с разных сторон. Казалось бы довольно очевидное для человека рациональное поведение, но так и не сообразил как это проще запрограммировать. Слишком много на этот маневр времени тратить не хотел, поэтому откладывал на потом, но так руки и не дошли.
Недостаточно оптимальный захват фабрик. По сути у меня жадный алгоритм. Можно было бы свести до чего то типа незамкнутой задачи коммивояжера, и находить план захвата всех фабрик, а не только самых ближайших. Но это бы дало какое то улучшение только на картах где фабрик много, а это не такой уж частый случай, поэтому не стал заморачиваться.
Плохое микро в бою за счет примитивного анализатора боя. Это было наглядно продемонстрировано ботом Milanin, который в плане миро выше всех на 2 головы. Он, управляя фалангами из 20 танков и 20 ремонтных машинок, умудряется иногда без потерь перестрелять превосходящие силы, умело двигаясь и вращая эти фаланги танками в сторону противника. К сожалению у Milanin-а очень медленный начальных захват карты из-за сборки тех самых смешанных фаланг. Поэтому даже не самый топовый бот может его задавить чисто количеством юнитов, произведенных на более быстро захваченных фабриках.
Заключение
В итоге у меня получился на мой взгляд довольно крепко сбитый бот, с отсутствием откровенно слабых мест. Когда смотрю повторы, не замечаю слишком критичных ошибок. Чего-то сверх гениального в нем нет. До начала финалов не был уверен что выиграю, т.к. в тестовых играх с другими топами, такими как Adler, oreshnik, Milanin — результаты были нестабильными. Но, как оказалось, очень неожиданно для меня самого — первое место с большим отрывом.
Исходный код бота доступен тут.