[Из песочницы] История 30 места в финале Russian AI Cup 201521.12.2015 11:33

Введение

В этом году в Russian AI Cup надо было запрограммировать бота для управления машинкой (а в финале даже двумя!), и я решил впервые поучаствовать, так как тема показалась близкой и родной: фанат гонок, периодически езжу катать в картинг (хоть и без выдающихся результатов), вечера часто провожу, катаясь по виртуальным Гавайям в Test Drive Unlimited или Nurburgring в GTR Evolution.

Высокого места я в итоге не занял (30 место в финале, песочницу закончил на 48 месте), но небольшое время между вторым раундом и финалом был в топ-10 песочницы. Также, судя по форуму соревнования, набор костылей решений как у меня больше никто не использовал, так что если желаете узнать подробностей — добро пожаловать под кат. Наиболее интересная часть в посте, пожалуй, про поиск оптимальной траектории.
Подробное описание конкурса можно почитать на сайте, но коротко суть можно передать следующим образом:

• Имеется карта, разбитая на тайлы разных типов (прямая, поворот, Т-образный перекрёсток, перекрёсток, пустой тайл).
• Имеется 4 машинки. Одной из них (в финале — двумя из них) управляет игрок. Каждый тик сервера боту-стратегии, управляющему машинкой, передаётся информация о мире, а стратегия должна ответить, какие действия она желает совершить. Возможных действий не так уж и много: изменить мощность двигателя, повернуть руль, выстрелить снарядами, разлить лужу масла, включить нитро, нажать тормоз
• Для завершения гонки необходимо проехать через все контрольные точки-тайлы в определённом порядке (фактически, проехать два круга трассы). Координаты точек известны, путь каждый строит самостоятельно. В первых двух раундах соревнования известна вся карта, в финале же игрок видит только небольшую окрестность около своих автомобилей.
• На трассе случайным образом разбросаны бонусы: если на них наехать, то, в зависимости от типа бонуса, можно пополнить количество снарядов для стрельбы, количество масла для создания сложностей соперникам, заряды нитро-ускорения, починить машинку, или получить дополнительные 100 очков.
• Игрок получает очки за прохождение контрольных точек, за повреждения соперников, за подбор бонусных очков, а также получает дополнительные 512/256/128/64 очка за финиш на ½/¾ месте соответственно.
• После окончания игры участники упорядочиваются по количеству баллов. Кто больше набрал — тот и победитель, всё просто. Из-за бонусов и очков за повреждения соперников далеко не всегда побеждает тот, кто пришёл на финиш раньше: например, достаточно подобрать всего один бонус на 100 очков, и уже обогнать игрока, финишировавшего третьим.

Принятие решений стратегией можно разбить на несколько относительно независимых частей:

• Поиск пути
• Просчёт оптимальной траектории по выбранному пути
• Управление машинкой для следования траектории
• Стрельба
• Использование масла
• Использование нитро-ускорения

Поиск пути

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

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

В результате раздумий было решено попробовать метод, который меня пугал своей сутью, но оказался достаточно эффективным: полный перебор.

В начале строятся (почти) все возможные пути (последовательности подряд идущих тайлов, начинающиеся из текущего), общей длиной N, где N пришлось выбрать равным 11, чтобы уложиться в ограничения по времени работы стратегии. Уточню, что такое «почти»: пути строятся в предположении, что в одном и том же тайле не требуется быть дважды, если с предыдущего посещения не была пройдена ни одна контрольная точка. Таким образом, если на этапе построения очередного возможно пути оказывается, что тайл уже есть в пути, то построение текущего пути прекращается и начинается построение следующего.

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

• За каждые два поворота в одну сторону подряд наложить штраф 30 баллов. Повороты на 180 градусов штрафуются, т.к. у машинки очень большой радиус поворота и в крутой поворот сложно вписаться, особенно если соперники активно «помогают».
• За каждые два подряд идущих тайла, по которым нужно двигаться прямо, добавить 10 баллов. Всё просто: ехать прямо проще, чем поворачивать.
• За каждые два чередующихся типа поворотов (поворот налево, а сразу за ним поворот направо, или наоборот), добавить 12 баллов (движение по диагоналям тайлов происходит быстро, поэтому такие пути достаточно выгодны).
• Если необходимо развернуться, наложить штраф 150 баллов.
• Если на предполагаемой траектории следования по тайлам содержится бонус, добавить соответствующее типу бонуса количество баллов. Если бонус — 100 очков, то добавить 55 баллов; аптечка (при этом у машинки меньше 50% очков здоровья) — 25, заряд нитро — 35, масло — 15, снаряды — 15.
• Добавить 10*cos (a) баллов к пути, где a — угол между направлением движения машинки и центром первого тайла в пути следования. За счёт этого машинка реже передумывает на полпути, что ей резко нужно повернуть и врезается в стенку.
• Если первые 5 тайлов пути совпадают с путём, рассчитанным в предыдущий раз, то добавить 10 баллов. Идея заключается в том же, что и у предыдущего пункта: не менять резко путь.
• Если считается путь в момент старта, то путям, идущим прямо 3 и более клеток начисляется бонус в 10 очков. Если бы не было других машинок, то этого пункта бы не потребовалось, однако на многих картах можно сколь угодно сильно хотеть повернуть сразу налево/направо, но коварные соперники мешают просто самим фактом своего существования.

Для расчёта бонусов за повороты/прямые и штрафов за крутые повороты также учитываются последние 4 посещённых тайла.

Раскрою, что имеется в виду под «на предполагаемой траектории». Для каждого тайла пути, кроме того, в котором сейчас находится машинка, вычисляется угол, на который происходит поворот (0, ±90, 180 градусов). Если по тайлу происходит движение прямо, то потенциально подбираемыми считаются бонусы, расположенные на расстоянии 250 от оси движения. Если на тайле происходит поворот, то потенциально подбираемыми считаются бонусы, расположенные на расстоянии 200 < r < 500 от центра поворота (угла тайла). Чтобы было понятнее, привожу картинку; серым цветом закрашены участки выбранного пути, в которых бонус считается потенциально подбираемым (отладчик позволяет рисовать только окружности, поэтому не обращайте внимания на лишние части красных кругов). Как можно видеть, участки даже не совпадают на границах тайлов, но для примерной оценки можно ли подобрать бонус или нет, такой метод подходит.

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

В финале не известна вся трасса, и видны только тайлы на расстоянии 2 от каждой из машинок игрока, а так же все ранее виденные тайлы. Модифицировать алгоритм практически не пришлось: добавился перерасчёт расстояний волновым алгоритмом, когда открывается новый тайл, а также считалось, что по неизвестному тайлу можно проехать в любом направлении.

Просчёт траектории

Отлично, путь получен, как теперь по нему проехать, как построить оптимальную траекторию? Обратимся к Google с запросом Racing line AI… или ещё каким-то похожим… и получим не очень много. Есть одно видео на Youtube, есть упоминание статьи в книге Game AI Pro 2: Collected Wisdom of Game AI Professionals, и исходные коды бота к игре TORCS с упоминанием алгоритма K1999. Ещё немного усилий, и удалось найти диск, прилагающийся к упомянутой книге, на котором лежат исходники к статьям, хотя саму статью я найти так и не смог. Беглый просмотр того, что имеется, позволил прийти к выводу, что процесс построения траектории во всех трёх случаях — итеративный. Берём за основу хоть что-нибудь, а потом сглаживаем и оптимизируем, и так N раз.

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

Полученное приближение надо как-то сгладить. Было решено воспользоваться подходом, описанным в видео и исходниках к статье: считать траекторию последовательностью шарниров, соединённых пружинами. Между каждой парой последовательно идущих точек создаётся «пружина», с жесткостью k, и длина которой в спокойном состоянии считается равной расстоянию между точками. Скорость каждой точки траектории изначально равна нулю.

Теперь на каждой итерации оптимизации рассматриваются каждые три последовательные точки траектории A, B, C. Если угол ABC не равен 180 градусам, то «шарнир» в точке B стремится распрямиться, и к точкам A, B, C прикладываются соответствующие силы. Также к точке B прикладываются силы, стремящиеся привести пружины AB и BC к начальной длине. Силы упругости вычисляются по закону Гука: F=kx, где x — разница в длине между текущей и начальной длиной. На картинке приведены силы, которые прикладываются к точкам; предполагается, что пружина AB удлинена, а пружина BC сжата. Силы, стремящиеся распрямить шарнир (Fab, Fba, Fbc, Fcb) пропорциональны углу ABC и длине соответствующего отрезка. Силы упругости пружин прикладываются только к точке B, так как силы упругости для точек A и C учитываются при обработке предыдущей и следующей тройки точек траектории соответственно.

После расчёта сил для каждой точки просчитывается её скорость по тривиальной формуле V = 0,9 * Vprev + F, где Vprev — скорость после предыдущей итерации, а F — сумма всех сил, действующих на точку. Коэффициент 0,9 добавлен, чтобы процесс быстрее сходился. Для каждой точки определяются её новое местоположение по формуле Pos = Pos + V. Если новое местоположение оказывается за пределами трассы, оно сбрасывается на предыдущее значение, а скорость уменьшается в два раза.

После нескольких таких итераций получается что-то похожее на оптимальную траекторию движения. На картинке черной линией обозначена изначальная траектория, а красной — после 500 итераций оптимизации.

Однако оптимальная траектория оптимальной траекторией, но и бонусы как-то подбирать надо. Был опробован один вариант, который и остался в итоге. Через половину итераций оптимизации однократно происходит следующее:

1. Для каждого бонуса, лежащего в тайлах пути, ищется ближайшая точка траектории.
2. Если расстояние от точки траектории до бонуса меньше 250, то точка перемещается на место бонуса, а её масса повышается в несколько десятков раз.
3. Оптимизация продолжается.

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

У описанного подхода к построению траектории есть несколько проблем:

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

   

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

   

2. Процесс вычислительно очень затратен: судя по профилировщику, бот примерно 80% времени тратит именно на расчёт траектории, так как используется большое количество операций с плавающей точкой (особенно на вычисление угла и взятие корня).
3. Процесс не всегда стабилен, и траектория, просчитанная на следующем тике может отличаться от предыдущей. Обычно это происходит из-за неудобно расположенных бонусов: на одном тике их брать удобно, на следующем уже нет, и траектория может из-за этого резко меняться, а машинка начинает тормозить и метаться налево/направо.
4. К сожалению, из-за лени и недостатка времени не удалось избавиться от одного бага, который приводил к такой траектории в некоторых случаях:

   

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

Управление движением

После просчёта траектории нужно как-то по ней проехать. Это, пожалуй, самая просто реализованная часть моего бота, и удивительно, что ЭТО вообще работает.

Бот не контролирует мощность двигателя и всегда давит педаль газа в пол, а руль направляет на первую точку просчитанной траектории.

Для решения тормозить или нет используется школьная физика класс примерно за 7. Для ближайших 4–5 точек (количество зависит от текущей скорости движения автомобиля) считается радиус кривизны траектории. В качестве приближения радиуса кривизны берётся радиус окружности, описанной около трёх последовательных точек траектории. После этого скорость автомобиля возводится в квадрат и делится на минимальный из полученных 4–5 радиусов. В результате получается центростремительное ускорение, с которым необходимо двигаться, чтобы проехать по этой траектории, для чего, в свою очередь необходимо, чтобы сила трения (сцепления с дорогой) позволяла это сделать. Если считать максимально возможную силу трения постоянной (что, насколько я понимаю, не совсем правда, но я не изучал подробно физику движения), то если центростремительное ускорение превосходит некоторую величину (строго говоря, mu*g, где mu — коэффициент трения, а g — ускорение свободного падения), то проехать по такой траектории с текущей скоростью не получится, и нужно жать на тормоз, что бот и делает, если величина подсчитанного ускорения превышает 0,37.

Стрельба

Стрельба реализована очень просто: бот считает, что будет в ближайшие n тиков в случае выстрела, если предположить что все машинки едут с постоянной скоростью. Если в один из тиков расстояние от снаряда до соперника оказывается меньше 50, то бот стреляет. Стрельба производится только если расчётное пройденное снарядом расстояние не превышает 2000. Также первые 300 тиков после начала бот стреляет только в случае, если у машинки соперника меньше 30% здоровья, так как за убийство дают дополнительные 100 очков, а в начале заезда часто происходит ситуация, когда одна машинка вырывается вперёд, соперники разряжаются в неё, и у неё остаётся мало очков здоровья.

Масло

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

Нитро

Для использования нитро используются подсчитанные для торможения радиусы кривизны траектории. Если минимальный радиус кривизны на ближайшие 9 точек траектории больше 4000 (т.е. траектория заведомо не содержит крутых поворотов), то бот включает нитро.

Заключение

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

Хочу выразить благодарность организаторам соревнования за бессонные ночи и интересно проведённое время, коллегам на работе и друзьям, которые мотивировали на участие и не давали бросить, когда уже очень хотелось, а также участнику http://russianaicup.ru/profile/JustAMan за удобный интерфейс для рисования в Local Runner.

P.S.: Ждём подробного рассказа от победителя, он обещал!

© Habrahabr.ru