Привет всем, меня зовут Андрей Токарев, и снова я бы хотел поделиться опытом участия и победой в Russian AI Cup.

Если кто не знает, Russian AI Cup (далее РАИК) это чемпионат по программированию искусственного интеллекта, где мы (точнее наша программа) должны управлять одним или несколькими персонажами (юнитами), которые соревнуются между собой. В этом году игра представляла собой 2-х мерный платформер, напоминающая компьютерные игры начала 90-х, а юниты являлись вооруженными человечками, которые должны были убивать таких же человечков противника. Более детально об этом можно почитать в анонсе



В этот раз заседания не было когда пришла повестка о начале РАИК-а, так что перейдем сразу к сути.

Первый взгляд

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

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

Старт

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

Симуляция

Теперь приступаем к самому любимому занятию всех участников РАИК-а: пишем симуляцию! Почитав чат чемпионата, стало понятно, что писать точную симуляцию — дело гиблое. Так что на точность я сразу забил. Получилось, как получилось, даже при простом отскоке от потолка было расхождение в пределах тика. Можно было, конечно, повозится несколько дней и значительно поднять точность, но, во-первых, неизвестно какой от этого был бы профит. Во вторых я был слишком нетерпелив, и как всегда хотелось как можно быстрее увидеть результат. Так что я решил приступить к написанию самой стратегии, а свою кривую симуляцию, подумал я, поправлю потом, в случае надобности. Задним числом должен сказать, что, возможно, я был неправ.
Стоило бы сразу довести симуляцию до нормального состояния, а так приходилось до конца чемпионата вносить туда правки, и все равно она так и осталась кривой.

Основа стратегии

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

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

Выбор цели был довольно прост: пока нет оружия, идем к оружию, если оружие есть, идем к врагу, а если «здоровья» мало, идем к аптечке. В случае аптечек и оружия те объекты, что ближе к противнику в качестве цели исключались. Приоритет по оружию у меня почему-то сначала был на автомате.

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

Отправляемся на фронт, и первые улучшения

Глядя на бои, было видно, что если у противника нормальный уворот, то попасть в него с дальней дистанции практически невозможно. Это пустая трата пуль. Так что я добавил простое условие на стрельбу: стрелять, только если враг ближе 7-и метров. Кроме того, если расстояние очень большое, то стоит перезарядиться, даже если в обойме не хватает всего одной пули. Эти простые два условия довольно много прибавили.

Эта была первая версия, которую я отправил. В тот же день я понял, что пистолет выгоднее автомата. Плюс добавил в ОФ еще расстояние до противника, в случае если выстрел не скоро. Таким образом, при перезарядке он пытался держать дистанцию.

Старт был довольно успешный. Уже не помню, как высоко стратегия успела подняться в рейтинге до сброса (где-то в районе первой тройки-пятерки), а после сброса уверенно пошла вверх.

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

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

Тестирование

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

Допустим, мы запустили тест и после 40 игр видим, счет 27:13 в пользу новой. Все, мы нашли Грааль, останавливаем тест и принимаем изменения. На самом деле даже при равных силах есть примерно 2% вероятности такого расклада.

Другой пример, запускаем 100 игр и принимаем изменения, если счет 55:45 или больший. С вероятностью 2.8% так может сыграть версия, которая в действительности должна проигрывать с таким же счетом. Пару процентов ошибки может показаться не очень большим, но если 90% наших изменений неудачны, то это значит, что каждое 4-е принятое изменение будет неудачным. Так что, даже 100 игр, еще так себе тест, ну а меньше — вообще ни о чем.

Конечно, запускать по несколько сот игр, может занять неприлично много времени. Тут есть разные варианты, можно запускать тесты на ночь, гонять в фоновом режиме, арендовать серверное время, или делать стратегию быстрой :) У меня первые версии работали в среднем, где-то, по 5 сек. на игру, так что с этим повезло.

Если стратегия медленная, то можно локально гонять урезанные версии — меньше переборов, меньше микро-тиков, например. Я этим пользовался в футболе (предыдущий РАИК), проблем замечено не было. Возможно, качество где-то и теряется, но, во всяком случае, это выгодней, чем проверять изменения на 20-и играх.

Улучшения

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

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

Учимся стрелять по-взрослому

Объективно нужно стрелять в то направление, где мат. ожидание урона самое высокое. Понятно, что аналитически это не вычислить, а там где математика не помогает, как мы знаем, приходит на помощь симуляция. Стреляем во все возможные направления и пытаемся противника увернуть от каждой пули по отдельности. К каждой пуле приписываем минимальное значение урона, которое она точно нанесет. В случае обычной пули это либо 0, либо ее урон, а в случае ракеты есть 3 варианта.

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



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

После этого каких-то очень значительных изменений вплоть до последнего дня, когда ввёл самоподрыв, не было. Добавил штраф, если не осталось прыжка на момент, когда противник выстрелит, поскольку падая, увернутся сложней. Попытался предсказывать путь врага к аптечке, если у него мало жизней и таким образом, чуть улучшил контроль над ними. Сам же начал бегать за аптечками от 60% здоровья, вместо 50%. Прибавил расстояние между своими в ОФ, чтобы друг другу не мешали, и базукой сразу двоих не подбили. Под конец добавил агрессивный мод на случай, если ситуация долго не меняется и я проигрываю по очкам, а то мои иногда застревали.

Результаты

Как я уже говорил, довольно быстро добрался до первого места в рейтинге. За исключением коротких промежутков времени я там продержался до конца. В раундах ситуация была чуть хуже: 4-е место в первом, 3-е во втором. Это говорило о том что я хорошо играл против сильных игроков, но не достаточно стабильно против слабых. Это довольно наглядно демонстрирует одна из игр 2-го раунда, где идущий тогда на самом последнем месте kostya200300 обыграл меня под 0!

Самоподрыв

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

Финал

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

В перерыве я доробатывал ковырял самоподрыв — кое-что было исправлено (оказалось, на верхушке лестницы нельзя ставить мины), добавил кое какие контрмеры против подрыва. И чинил симуляцию, так как до сих пор мои цеплялись за угол.

Начало второй части заключительного раунда было для меня удачным, отрыв стал потихоньку расти и достиг на максимуме около 20-и очков. Я даже немного расслабился и вместо того чтобы каждые 3 минуты обновлять страницу результатов начал играть в шахматы на телефоне. Когда снова посмотрел, отрыв уже был около 7-и очков и потом быстро докатился до 1-го. Интересно, что там дают за 2-е место? 1 час до конца, снова есть отрыв. 30 минут, разрыв катастрофически сокращается. 10 минут – всего 3 очка! Одна минута… кажется, победа! Ваня проиграл мне всего 3 очка. Это в пределах случайного разброса. Остальные отстали на 50 очков и более.

О забавных багах

Уже после финала заметил, что в некоторых играх мои юниты ведут себя странно — не избегают пуль когда, казалось, могли бы, и даже, как будто, специально их ловят. Выяснилось, что во время перерыва в финале я внес ошибку — когда определялось, может ли противник подорвать меня, нужно было посчитать, кто из моих находится в радиусе взрыва. Здесь я перепутал координаты своего и чужого юнита и ошибочно предполагал, что взрыв произойдет там, где нахожусь я, и таким образом гарантированно попаду в радиус взрыва. Реальный же взрыв считался уже из правильной точки, таким образом, в симуляции враг мог само подорваться вдали от меня. Обычно это просто добавляло большую константу в оценку, но ни на что особо не влияло. Однако, если у противника не хватало мин чтобы меня подорвать, то оказывалось, что мне выгодно словить пулю, чтобы у противника уже хватало мин, и я получил ту самую добавку в оценку. Возможно, сказалась невыспанность, или выпитая банка пива, но на самом деле ошибки всегда случаются.

Заключение

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