Coders Strike Back Post-mortem

За последние несколько месяцев я потратил порядка 40 часов в выходные и по вечерам на то, чтобы написать бота способного пройти трассу Coders Strikes Back быстрее соперников. За эти 40 часов я умудрился набить порядочное количество шишек, выбраться в легендарную лигу и даже занять там пристойное, на мой взгляд, место. Данный пост — post mortem этого проекта.

Важная оговорка, бо́льшая часть пути была проделана с ботами на Python, но заключительные этапы были пройдены на C++. Не думаю, что дело в Python, скорее всего, я не заметил кучу ошибок в своем коде, которые было лень исправлять, но об этом ниже.

CodinGames

Для начала должен сказать пару слов о сайте, где происходит соревнование — CodinGames. Это сборник задач по программированию, оформленных в виде игр: где-то нужно решать головоломки, где-то обыгрывать AI, где-то состязаться с написанными другими людьми ботами. Таких задач и соревнований на сайте довольно много разного уровня, различной направленности. Объединяет их одно — они оформлены в виде игр, где «герой» или «герои» управляются программно.

По сути, все игры и загадки на сайте — замаскированные программистские задачки. Думаю бо́льшую часть из них можно в том или ином виде найти на сайтах типа HackerRank. Там они будут сформулированы более явно. В этом состоит главное преимущество CodinGames: тратить время на то, чтобы разобраться почему твой бот такой медленный гораздо приятнее и интереснее, чем разбираться из-за почему решение вылетает на 17-м тесте, а на 20-м падает по таймауту.

На мой взгляд, CodinGames и HackerRank решают немного разные задачи. HackerRank — это больше подготовка к традиционным интервью. Тут важнее научиться решению стандартных алгоритмических задач, сформулированных так, как их формулируют на интервью. Несмотря на то что никаких лимитов по времени на HackerRank нет, часто чувствую себя на нем как на интервью, как будто меня кто-то подгоняет («У вас всего час на решение этой задачи»).

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

Coders Strikes Back

Coders Strikes Back хорошо иллюстрирует разницу между HackerRank и CodinGames. В отличие от задач на HackerRank не существует одного правильного способа написать код для этого соревнования. По мере поисков вдохновения я выяснил, что хороших результатов добавились участники использующие разные подходы: от набора эвристик до нейронных сетей.

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

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

Золотая лига

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

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

Таким образом, у меня получился очень компактный бот, который тем не менее выдавал место в районе 300.

laps = int(input())
cp_count = int(input())
checkpoints = []
for i in range(cp_count):
    checkpoint_x, checkpoint_y = [int(j) for j in input().split()]
    checkpoints.append((checkpoint_x, checkpoint_y))

while(1):
    fp_x, fp_y, fp_vx, fp_vy, fp_angle, fp_next_cp_id = [int(j) for j in input().split()]
    sp_x, sp_y, sp_vx, sp_vy, sp_angle, sp_next_cp_id = [int(j) for j in input().split()]

    print(
        "{} {} {}".format(
            checkpoints[fp_next_cp_id][0] - 3*fp_vx,
            checkpoints[fp_next_cp_id][1] - 3*fp_vy,
            "BOOST"
        )
    )

    print(
        "{} {} {}".format(
            checkpoints[sp_next_cp_id][0] - 3*sp_vx,
            checkpoints[sp_next_cp_id][1] - 3*sp_vy,
            "BOOST"
        )
    )

    input().split()
    input().split()

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

• GENETIC ALGORITHMS IN CODERS STRIKE BACK GAME
• CODERS STRIKE BACK – PB4608’S AI (RANK: 3RD)
• Coders Strikes Back

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

К сожалению, реализация в лоб на питоне не позволяет составить достаточное количество планов. Мне удалось добиться генерации порядка 60 вариантов без риска таймаутов. Пожалуй, реализация с использованием NumPy дала бы более достойный результат. Но я пошел по пути меньшего сопротивления. К тому времени я уже немного устал от проекта и хотелось его завершить. Так что я вернулся к поиску подходящей заготовки.

Далеко ходить не пришлось. Отличный шаблон, написанный Романом Рингом (Roman Ring), нашелся минут за 20 https://github.com/Inoryy/csb-ai-starter. Совсем немного поколдовав с функцией оценки плана (благо заготовки и идеи на пробу я собрал еще на предыдущем этапе), я легко выскочил в легендарную лигу.

Легендарная лига или вместо заключения

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

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