company_banner

Мой бот для Russian AI Cup 2019



    Так уж получилось, что этот чемпионат стал для меня первым, где я смог занять достойное место, за которое не стыдно, поэтому и статью решил тоже написать только сейчас. Путь, которым я шел к этому месту: 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. Здоровье юнита, самый большой бонус.
    2. Расстояние до противника. Если оно меньше чем нужно — штраф, иначе — бонус обратно пропорциональный расстоянию.
      Базовое расстояние — пять единиц, было выбрано опытным путем. Это расстояние домножается на фактор (1 — перезарядка / макс. перезарядка), то есть чем больше времени остается у врага на перезарядку, тем ближе мы можем подойти. Это позволяет боту плавно менять дистанцию с врагом, но не подставляться, когда он уже снова может стрелять.
    3. Штраф за неуправляемый полет. Средний штраф если у врага пистолет или автомат, большой, если у врага ракетница.
    4. Штраф если мы ниже врага, пропорциональный разнице высот, фиксированный бонус, если мы выше.
    5. Бонус за нахождение на лестнице или платформе.
    6. Штраф за нахождение близко к стене, если у врага есть ракетница.
    7. Огромный штраф если враг может задеть нас самоподрывом.
    8. Большой бонус, если мы можем задеть врага самоподрывом.


    Последних двух параметров не было в финале.

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

    1. Бонус за движение в сторону ближайшего врага.
    2. Бонус за движение в сторону ближайшей аптечки. Чем меньше у нас здоровья, тем сильней бонус.
    3. Бонус за движение к ближайшему оружию, если у нас нет оружия, или за движение к оружию с более высоким приоритетом, чем у бота.
    4. Бонус за движение к лутбоксу-мине, если их у бота меньше двух.
    5. Бонус за движение к ближайшей для врага аптечке, если мы к этой аптечке ближе, чем враг.
      Самый интересный бонус. Был добавлен уже после финала. Позволяет не пускать вражеского бота лечиться. По наблюдениям оказался достаточно эффективным.

    Заметки

    • Глубина симуляции — 30 тиков.
    • Поведение вражеских ботов никак не симулируется. Игра очень динамичная и адекватно предсказать движение врага очень сложно и не особо нужно. Это могло быть полезным, чтобы избегать безумных суицидников, но это так и не было сделано.
    • Чтобы избежать проблем с уклонением от пуль, если они есть на поле, симулируем с качеством 100 микротиков за тик (как в игре), иначе снижаем до 5.
    • Можно заметить, что никакого коэффициента затухания не применяется. Возможно, это было ошибкой.

    Старый вариант перемещения находится в MoveHelperOld, новый в MoveHelper.


    Мой бот(справа) сторожит аптечку

    Мины


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

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

    Эксплойт оказался настолько сильным, что один участник, который в общем рейтинге находился где-то на 15-м месте, в финале неожиданно проскочил на 4-е, просто за счет грамотного камикадзе.

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

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

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


    Влияние самоподрыва на рейтинг

    Выводы


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

    Заключение


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

    • Впервые можно было пообщаться в Telegram с человеком, который отвечает за техническую часть, и который достаточно оперативно отвечал на имеющиеся вопросы, за что ему большое спасибо.
    • В первый раз в локалраннере присутствовал нормальный встроенный визуализатор. Раньше для вывода отладочной графики приходилось писать свой.
    • Наконец-то вместо неудобной и глючной утилиты Repeater добавлена кнопка «Повторить игру» в локалраннере.


    Из минусов, конечно же, громадный эксплойт с минами.

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

    Код бота можно посмотреть на гитхабе: github.com/silentnox/CodeSide
    Mail.ru Group
    Строим Интернет

    Комментарии 14

      0

      Читаю уже вторую статью в которой упоминается симулятор.
      Можете, пожалуйста, поподробнее разъяснить почему это так важно? Я пользовался batch mode предоставленного локального раннера чтобы тестировать стратегии друг с другом и, в целом, остался доволен. Что я упускаю?

        0
        Симулятор это копия игровой механики встроенная в ИИ, можно задать начальные условия и посмотреть что получится через N тиков. Это позволяет перебирать и анализировать возможные действия.
        Без симулятора приходится действовать только эвристикой, а это значительно менее эффективно.
          0

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


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

            0
            Помоему последние лет пять выигрывают стратегии с симуляцией, так что надо смериться и изучать =)
              0
              Можете ссылку на ваш профиль на сайте чемпионата дать? Хочу посмотреть как ваш бот играет.
              И еще из вашего описания я не до конца понял как вы строите граф возможных положений, хочется подробней про это услышать.

              Насчет симуляции: для принятия правильного решения боту нужна оценка возможных действий, симулятор дает точный прогноз, все остальные методы дают приблизительный. Точней прогноз — эффективней действия. Тем не менее, всё зависит от задачи. Чем сложней игровая механика, тем сложней для нее написать эвристику и тем эффективней симуляция.
              Для проверки симулятора я с помощью отладочной отрисовки выводил путь полученный моим симулятором и проверял, совпадает ли он с путем которым движется бот в раннере.
                0
                Профиль:
                russianaicup.ru/profile/uf.darxy

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

                Затем я строю граф из начальной позиции игрока. При этом граф направленный и вершины различаются не только координатами, но и внутренним состоянием игрока.
                Попытаюсь объяснить на примере:
                Допустим у нас есть клетка с инексом [18,20], которая находится над поверхностью. В ней игрок может оказаться либо подпрыгнув с поверхности, либо падая сверху.
                Соответственно эта клетка будет отражаться в несколько разных верщин графа:
                • [x:18, y:20, fallingState:y, jumpingStateCancellabe:n] — юнит пролетает клетку падая
                • [x:18, y:20, fallingState:n, jumpingStateCancellabe:y] — юнит пролетает клетку прыгая

                Допустим, есть JumpPad неподалеку. Тогда мы получим еще одну вершину графа:
                • [x:18, y:20, fallingState:n, jumpingStateCancellabe:n] — юнит пролетает клетку, прыгнув с джамппада

                Ребра между вершинами графа означают возможно ли перейти из одного состояния в другое. Например из вершины [x:18, y:20, fallingState:n, jumpingStateCancellabe:y] можно перейти в вершину [x:18, y:20, fallingState:y, jumpingStateCancellabe:n] если остановить прыжок и начать падать.
                Затем я присваиваю каждой вершине вес. Например, для клеток с аптечками присваивается положительный вес, для клеток в которых ожидается пуля/взрыв — вес отрицательный. Также вершины графа с большим количеством степеней свободы получают положительный вес. Учитывается и положение относительно вражеских/дружественных юнитов в зависимости от оружий и здоровья. Затем дейкствой ищу наилучший путь.

                Насчет симулятора:
                симулятор дает точный прогноз только на определенное количество тиков (ресурс же ограничен). Т.е. если надо посчитать положение на 50 тиков вперед, нужно провести 50 расчетов, что дает o(n). В случае с простым геометрическим расчетом посчитать можно любой момент времени за константу. Кроме того, симулятор дает точный прогноз только в случае если вы уверены, что он совпадает на 100% с игровой механикой. Таким образом, что в случае симуляции, что в случае геометрического расчета вопрос сводится к валидации результата.
                В этом году игровая механика, на мой взгляд, была довольно простая, т.е. движение пуль легко просчитывалось геометрически, а все остальное недетерминировано, т.е. толку от любой симуляции мало.

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

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

                    0
                    Вопрос, опять же, в глубине поиска. Да, я могу с помощью симулятора посмотреть, что будет на следующем тике при всех возможных вариантах действий бота. Но так уж ли это важно? Чтобы бот имел какую-либо долгосрочную стратегию, нужно либо перебирать все варианты действий на n тиков вперед (что ресурсозатратно), либо все равно прибегать к эвристикам.

                    В случаях, когда тактическое преимущество критично, да, наверно это имеет како-то смысл. Но не очень понятно, в каком месте провести границу между честной симуляцией и аппроксимацией.
          0
          Спасибо за статью.
          Почему выбор ЯП пал на c++, а не тот же питон? Есть ли какие-то подводные камни, если использовать питон на соревновании?
            0
            Во-первых я просто люблю С++, а во вторых питон очень медленный, из за этого на нем сильно не разгуляешься в плане перебора.
            0
            Прикольная статья, успехов автору на новом чемпионате
              0
              Спасибо
              0
              Статья интересная, но больше похоже на Machine Learning, чем Bot Programming ;)
              Какие ещё бывают чемпионаты по данной дисциплине?

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

            Самое читаемое