Так уж получилось, что этот чемпионат стал для меня первым, где я смог занять достойное место, за которое не стыдно, поэтому и статью решил тоже написать только сейчас. Путь, которым я шел к этому месту: 1192-е место на чемпионате 13-го года, 241-е на чемпионате 17-го года, 91-е на чемпионате 18-го года и, наконец, 16-е (и 5-е в песочнице) место на этом.
Общие мысли
Я считаю, что одной из основных причин относительно успешного выступления на RAIC стало изменение подхода к написанию своей стратегии.
Раньше я пытался сразу писать что-то большое и сложное, без промежуточных этапов, и первую версию удавалось залить только недели через две после начала чемпионата, а на прошлом так вообще не смог уложить во все отведенное время и первую версию удалось залить уже только после финала.
Все это приводило к тому, что пока другие участники могли тестировать свои стратегии на живую, у меня все еще не было готового решения, пусть и плохого. Поэтому, когда удавалось залить, то выяснялось, что выбранный подход не работает или работает плохо, а поскольку сил и времени было вложено немало, изменить его радикально не было возможности.
Поэтому я решил, что в этот раз поступлю иначе. Исходя из опыта прошлых участий я заметил, что стартовый бот, несмотря на всю его примитивность, написан достаточно рационально, и, развивая его, можно потихоньку добавлять и тестировать новые фичи, и сразу же проверять против стратегий других участников. Особенно меня попробовать такой подход убедила прошлогодняя статья участника T1024.
Также я для себя решил, что чем сложней подход, тем он менее эффективен в моих руках. Например, нет смысла использовать генетику там, где можно обойтись полным перебором, и если стоит выбор перебирать меньше вариантов, но все, или больше, но генетикой, лучше выбрать первый вариант. Плюс, из чтения статей Коммандоса, я сделал вывод, что специфические оптимизации под задачу всегда будут эффективней общего алгоритма.
Тем не менее, даже сейчас я опоздал дня на три или четыре, прежде чем мне удалось залить первую версию бота, в это время в песочнице уже вовсю воевали.
Что я делал в это время? Я писал симулятор, важность которого уяснил из прошлых чемпионатов. В отличие от прошлого года, где псевдокод симулятора был доступен сразу, в этот год всю механику пришлось вычитывать из документации. К счастью, в качестве компенсации игровая механика была достаточно не сложной и прямолинейной, так что особых проблем у меня не возникло.
Ранние версии
Итак, имея на руках готовый, хоть и кривой-сырой симулятор, первым делом я прикрутил увороты (функция Dodge). Поскольку я в этот раз решил действовать как можно проще, то и увороты были сделаны максимально простым способом — проверяем перемещение по девяти направлениям (4 осевых, 4 диагональных и стояние на месте) и смотрим, на каком из этих направлений юнит получит меньше всего урона.
Весь остальной функционал бота оставался практически полностью как у квикстарта. Целеуказание тоже было максимально примитивным — цепочка if-ов, которые выбирают наиболее подходящее действие для юнита: к врагу, от врага, к аптечке, к оружию и т.д.
Удивительно, но такой подход, постепенно усложняясь, но не меняя своей сути, позволил выбиться почти в самый топ перед первым раундом (однажды бот даже оказался на втором месте в песочнице) и в целом держаться где-то в районе первых десяти мест.
Тем не менее, вечно так продолжаться не могло, и бота надо было улучшать. Однако идей что и как можно улучшить не было, все попытки что-то изменить в стратегии приводили к тому, что она проигрывала старой версии. Вносились незначительные изменения, но не более того.
Отсутствие идей привело к тому, что в раундах 1 и 2 я занял 29 и 19 места соответственно, и хотя в финал я прошел, становилось понятно, что нужно что-то радикально менять. Именно перед финалом (и после финала) и было внесено наибольшее количество значимых изменений.
Уже где-то с середины чемпионата я пытался экспериментировать с более умным перемещением, но все попытки оказывались неудачными. Изначальной идеей было выбирать то направление, где разность из шанса попадания своего бота по противнику и противника по своему боту была максимальна. На этот эксперимент я потратил почти все отпущенное до финала время, с нулевым результатом.
Поэтому для финальных многоуровневых карт бот оказался совершенно неподготовленным. Цепочка из if-ов давала относительно неплохие результаты на одноуровневых картах из раундов 1 и 2, но оказалась неприспособленной к многоуровневым картам финала, системы навигации по сложным картам у меня тоже не было, так как на простых картах можно было обходиться перемещением из кода стартгая.
Баг в одной из первых версий — область взрыва ракеты считалась в два раза меньше реальной.
Прицеливание и стрельба
Всё управление стрельбой находится в функции AimHelper.
Всё описанное ниже подразумевает, что целью является ближайший к боту видимый вражеский юнит.
Видов оружия всего три, однако, каждое из них требует своего подхода. Из автомата лучше просто стрелять почаще, из пистолета лучше целиться, а из ракетницы важно выстрелить тогда и туда, чтобы нанести больше урона противнику, чем себе.
Изначально прицеливания как такового не было вообще, бот просто целился в центр юнита. Позднее было добавлено предсказание движения юнита в случае если он находится в неуправляемом полете (падает или летит с джампада). Для этого я просто симулировал движение юнита до тех пор, пока расстояние, которое может пролететь пуля за N тиков, не станет равным расстоянию до юнита.
При тестировании против стартового бота было замечена его очень неприятная привычка постоянно мелко подпрыгивать, и если бот целился всегда в центр врага, это приводило к тому, что прицел постоянно двигался и разброс очень быстро увеличивался до максимального. Для противодействия был добавлен код, который проверял, если шанс попадания с текущим углом прицеливания лучше или равен шансу попадания с новым углом прицела, то мы не меняем точку куда целимся и не увеличиваем разброс.
Со стрельбой было сложнее, одной из основных проблем стартового бота было то, что он не проверял, заденет ли он себя взрывом. Мне почему-то ракетница понравилась больше всего из всех трех типов оружия, и поэтому она стояла первым приоритетом. Нужно было научить бота не подрывать себя.
Была написана функция HitChance, которая делила сектор обстрела юнита на N лучей, и проверяла каждый луч на столкновение с целью. Так же при попадании проверялось AOE взрыва, если это ракетница. Шанс попадания = число попаданий лучом или взрывом/число лучей.
Это позволяло определить статический шанс попадания по себе и по врагу, но не учитывало, что враг и сам может активно уворачиваться. Были и другие проблемы, например функция не учитывала случайную стрельбу по минам.
Для борьбы с не очень хитрыми врагами этого было достаточно, но против топов, которые хорошо уворачиваются от пуль, функция не давала какого-то адекватного результата. Нужен был новый подход.
Функция HitPredict также делит конус обстрела на N лучей, но вместо рейкастинга используем симуляцию, где за раз выпускается одна пуля по одному из направлений и проверяется, может ли враг увернуться.
Для проверки уворотов используется так же функция Dodge, которую бот использовал для себя, но с очень сильно зарезанным временем симуляции и числом микротиков. Такой метод оценки получился достаточно точным, но слишком пессимистичным. Если использовать только его, то бот стреляет слишком редко.
В первом варианте функция возвращала только шанс попадания, от 0-1, позднее было добавлено вычисление усредненного значения HP у цели, а также шанса убить попаданием.
В итоге обе функции работали вместе. Функция HitPredict использовалась до четырех раз, по одному для каждого юнита. Результат вычисления каждой функции преобразовывался в скор, который показывал насколько выгодно/опасно стрелять прямо сейчас. Значения складывались. Если суммарное значение получалось меньше нуля, стрельба блокировалась. Для ракетницы же необходимо было, чтобы скор был больше нуля.
Стало возможно более уверенно стрелять в случаях, если союзник блокирует стрельбу или попадает в AOE ракетницы, можно выстрелить ему в спину зная, что союзник либо успеет увернуться, либо для нас просто выгодно выстрелить. Например, мы потеряем одного юнита, но заберем сразу двоих.
Для ракетницы подход также оказался эффективным, один выстрел в нужный момент гораздо эффективней двух выстрелов, когда шанс попасть равен нулю. В таком виде стрельба была в финале, и это позволило занять 16-е место.
Теперь фишки, которые были добавлены уже после финала.
Аккуратное прицеливание: если угол между текущим прицелом и желаемым не слишком большой, ведем прицел со скоростью сведения, чтобы не увеличивать разброс.
Угол сведения для пистолета: как ни странно, фишка очень простая, но не пришла в голову раньше. Запрет стрелять если фактор разброса (разброс / макс. разброс) больше 0.6 обеспечивал процент побед в режиме 1х1 в 3:1 против версии, которая стреляла по КД оружия. Уменьшение фактора до 0.3 обеспечивало такой же процент побед против версии с параметром 0.6. Таким образом, одна из простейших оптимизаций оказалась одной из самых эффективных.
Визуализация работы функции HitPredict, красным отмечены траектории, где попадание гарантировано.
Навигация
Вплоть до финала навигации не было от слова совсем. Использовался слегка улучшенный алгоритм от стартового бота, и этого в целом хватало.
Поэтому когда пошли сложные карты, боту пришлось очень нелегко. В срочном порядке было написан примитивный алгоритм поиска BFS, который искал путь без учета его физической достижимости, просто по тайлам. Для того чтобы бот мог пройти найденный путь использовались различные костыли. Работало все это очень криво, а иногда не работало совсем, но все же бот хоть как-то мог добраться до оружия и аптечек, а не прыгать на месте.
После финала навигация была значительно улучшена и, по моим наблюдениям, вела себя даже эффективней чем у многих участников с более качественными алгоритмами поиска пути.
Принцип работы: бот ищет наиболее удаленную на пути клетку в пределах квадрата 5х5, видимую из центра бота, и следует к этой точке.
Тем не менее, это до самого конца оставался невероятно костыльный код, который работал только на картах финала и фейлился на других, более сложных.
Зеленым отмечен путь найденных дийкстрой. Бот следует к точке отмеченной белым квадратом.
Перемещение и оценочная функция
До финала оценочной функции не было, вместо нее использовалась цепочка if-ов, которые в порядке приоритета задавали боту цели в соответствии с заданными условиями. Например, первым стоял поиск оружия, если у бота его нет, потом поиск аптечки, если мы ранены и т.д.
Это работало на простых картах, хотя и кривовато, потому что приоритеты менялись очень резко и не учитывали различные дополнительные факторы.
Поэтому была всё-таки написана функция оценки.
Основные параметры
- Здоровье юнита, самый большой бонус.
- Расстояние до противника. Если оно меньше чем нужно — штраф, иначе — бонус обратно пропорциональный расстоянию.
Базовое расстояние — пять единиц, было выбрано опытным путем. Это расстояние домножается на фактор (1 — перезарядка / макс. перезарядка), то есть чем больше времени остается у врага на перезарядку, тем ближе мы можем подойти. Это позволяет боту плавно менять дистанцию с врагом, но не подставляться, когда он уже снова может стрелять. - Штраф за неуправляемый полет. Средний штраф если у врага пистолет или автомат, большой, если у врага ракетница.
- Штраф если мы ниже врага, пропорциональный разнице высот, фиксированный бонус, если мы выше.
- Бонус за нахождение на лестнице или платформе.
- Штраф за нахождение близко к стене, если у врага есть ракетница.
- Огромный штраф если враг может задеть нас самоподрывом.
- Большой бонус, если мы можем задеть врага самоподрывом.
Последних двух параметров не было в финале.
Все эти бонусы рассчитываются для каждого тика, суммируются и итоговое значение усредняется. Кроме этого есть оценочные параметры, которые рассчитываются один раз для каждого направления.
- Бонус за движение в сторону ближайшего врага.
- Бонус за движение в сторону ближайшей аптечки. Чем меньше у нас здоровья, тем сильней бонус.
- Бонус за движение к ближайшему оружию, если у нас нет оружия, или за движение к оружию с более высоким приоритетом, чем у бота.
- Бонус за движение к лутбоксу-мине, если их у бота меньше двух.
- Бонус за движение к ближайшей для врага аптечке, если мы к этой аптечке ближе, чем враг.
Самый интересный бонус. Был добавлен уже после финала. Позволяет не пускать вражеского бота лечиться. По наблюдениям оказался достаточно эффективным.
Заметки
- Глубина симуляции — 30 тиков.
- Поведение вражеских ботов никак не симулируется. Игра очень динамичная и адекватно предсказать движение врага очень сложно и не особо нужно. Это могло быть полезным, чтобы избегать безумных суицидников, но это так и не было сделано.
- Чтобы избежать проблем с уклонением от пуль, если они есть на поле, симулируем с качеством 100 микротиков за тик (как в игре), иначе снижаем до 5.
- Можно заметить, что никакого коэффициента затухания не применяется. Возможно, это было ошибкой.
Старый вариант перемещения находится в MoveHelperOld, новый в MoveHelper.
Мой бот(справа) сторожит аптечку
Мины
Про мины нужно рассказать отдельно. Если изначально это был не слишком важный геймплейно элемент — предполагалось минировать ключевые точки. То после окончания бета-теста внезапно была добавлена способность мин взрываться, если их задела пуля или взрыв. Мало того, установить мину и подорвать ее, можно было в одном и том же тике.
То есть если потратить всего два тика, можно было забрать любого вражеского юнита вместе с собой. За нашу смерть враг получал 1000 очков, но мы за его смерть получали 1000 + его здоровье на момент подрыва. Если повторить это два раза, то можно было обеспечить себе победу с весьма высокой вероятностью.
Эксплойт оказался настолько сильным, что один участник, который в общем рейтинге находился где-то на 15-м месте, в финале неожиданно проскочил на 4-е, просто за счет грамотного камикадзе.
(Разница в том, что в общем рейтинге встречаются как простые, так и сложные карты. На простых картах суицид работает хуже.)
В финале стратегия хоть и использовала мины, но не использовала намеренный самоподрыв. После финала, когда шла борьба за дополнительные призы, был добавлен модуль TryPlantMine2, реализующий подрывника. Сначала из-за ошибок в коде модуль не был особо эффективен, но в последней версии удалось все пофиксить, и стратегия сразу же начала круто лезть вверх по рейтингу. Дошло до того, что она даже влетела в топ-3, хотя потом и несколько скатилась.
Принцип работы: если мы находимся в позиции, позволяющей поставить мину, и можем выстрелить не позже чем через пять тиков, симулируем три варианта: просто стреляем вниз, ставим одну мину и стреляем, две мины и стреляем. Для врагов и союзников симулируем движение с помощью той же функции Dodge, проверяя, не смогут ли они выскочить из зоны взрыва раньше, чем мы готовы подорваться (не уверен, насколько сильно это было нужно). Для каждого варианта проверяем, насколько он нам выгоден по очкам, если мы оказываемся в плюсе, то подрываемся (таким образом можно подрываться даже зная, что умрут двое наших юнитов и один вражеский, но мы все равно выиграем)
Влияние самоподрыва на рейтинг
Выводы
Простые решения зачастую могут оказаться эффективней более сложных, но у этого есть свой предел. С таким подходом можно добраться достаточно высоко, но затем попасть в ловушку, когда потенциал улучшения стратегии уже исчерпан, и без радикальных перемен повысить силу стратегии невозможно. На будущее следует подумать о каком-то промежуточном варианте.
Заключение
В целом этот чемпионат мне понравился, хотя я отношусь к нему предвзято, потому что это первый раз, когда мне удалось занять какое-то место. Тем не менее, даже не учитывая мои субъективные ощущения, в этом году многое было реализовано на более высоком уровне.
- Впервые можно было пообщаться в Telegram с человеком, который отвечает за техническую часть, и который достаточно оперативно отвечал на имеющиеся вопросы, за что ему большое спасибо.
- В первый раз в локалраннере присутствовал нормальный встроенный визуализатор. Раньше для вывода отладочной графики приходилось писать свой.
- Наконец-то вместо неудобной и глючной утилиты Repeater добавлена кнопка «Повторить игру» в локалраннере.
Из минусов, конечно же, громадный эксплойт с минами.
А я буду надеяться, что мои достижения на этом чемпионате не случайность и что мне удастся в следующий раз хотя бы сохранить место, а еще лучше занять повыше (мечтать не вредно).
Код бота можно посмотреть на гитхабе: github.com/silentnox/CodeSide
Автор: robo2k
