Хабрахабр

Mini AI Cup #3: Пишем топового бота

Участники много спорили о том, что будет работать и что не будет, высказывались и проверялись идеи от простых if’ов до обучения нейросетей, но топовые места заняли ребята с, так называемой, "симуляцией". В начале осени завершился конкурс по написанию ботов Mini AI Cup #3 (aka Mad Cars), в котором участникам необходимо было сражаться на машинках. Давайте попробуем разобраться с тем, что это такое, сравним решения за 1ое, 3е и 4ое места и порассуждаем на тему других возможных решений.

Статья была написана в соавторстве с Алексеем Дичковским (Commandos) и Владимиром Киселевым (Valdemar).

Для тех, кому хочется просто почитать про решения победителей, советую сразу начинать с пункта "Симуляция".

Если за 600 игровых тиков никто не побеждает, карта начинает погружаться в кучу мусора, которая также может нажать на кнопку. В этот раз механика мира сильно походила на мобильную игру Drive Ahead: игрокам давалась машина с расположенной на ней кнопкой; задача — нажать кнопку врага быстрее, чем это сделает он. Каждому игроку давалось по 5 жизней, игра шла от 5 до 9 раундов, пока у кого-то не заканчивались жизни. Другими словами, нужно беречь свою кнопку от врагов, окружающего мира и кучи мусора (жизненно, да). Всего было 6 разных карт и 3 вида автомобилей — итого 18 различных комбинаций. Каждый раунд проходил на случайной карте и машинках, одинаковых для обоих участников.

Тик — это один ход, как в шахматах. Каждый раунд разбит на тики. Бывают соревнования, где все ходят по очереди, либо можно делать действие только раз в несколько ходов и выделять юнитов рамкой.
Каждый тик боту приходит состояние мира и дается возможность совершить 3 действия: ВЛЕВО, СТОП, ВПРАВО. Разница только в том, что ходят оба игрока одновременно. После того, как оба соперника выбрали действие, запускается симуляция игрового мира, считается новое состояние и отсылается игрокам. Эти действия заставляют ехать машинку в каком-то из направлений, а если при этом она не касается колесами земли, то и придают небольшое вращение всему кузову (немного аркадной физики). Все просто, но есть нюансы. В случае, если кому-то нажали на кнопку, то раунд завершается и запускается следующий.

А игры финала посмотреть тут. Более полные правила можно найти тут.

Чуть позже еще вернемся к тому, что значит "быть лучше", а пока разберемся с тем, как бороться с главной проблемой — огромным количеством вариантов действий: на старте у нас есть одно начальное состояние, затем каждая машинка может двигаться тремя разными способами, что дает нам 9 разных комбинаций для двух машинок, к 1500 ходу это будет уже 9^1500 различных комбинаций… Что чуть больше, чем хотелось бы, если мы планируем успеть перебрать их за время существования Вселенной. Большинство соревнований по написанию ботов очень похожи: есть конечное число тиков (тут для одного раунда примерно 1500 максимум), есть конечное число возможных действий, нужно выбирать такую последовательность действий, чтобы быть лучше, чем твои противники.

Это не какой-то алгоритм, а просто воссоздание правил игры с достаточной или полной точностью, чтобы можно было перебирать решения. Тут мы и подошли к тому, что такое симуляция. Для этого будет использоваться алгоритм поиска — в дереве состояний игры мы ищем наилучшее для нас. Разумеется, мы будем перебирать не все решения, а только часть из них. Лучше всего ознакомиться с тем, какие решения писали участники прошлых соревнований по ИИ. Алгоритмов достаточно много (от минимакса до MCTS), каждый имеет свои нюансы. Много ссылочек для этого есть в специальном репозитории. Это даст базовое понимание, в каких условиях алгоритмы работают, а в каких не очень.

При выборе алгоритма следует учитывать:

  • ограничение времени на 1 тик (тут я сильно просчитался в этом году, но смог остаться на 3м месте);
  • количество игроков. Например, если игроков трое, то будет сложно использовать минимакс;
  • точность симуляции, т.к. это может позволить переиспользовать старые вычисления;
  • "ветвистость" дерева состояний (можно ли просчитать все возможные состояния хотя бы на 10 ходов вперед);
  • здравый смысл — не стоит начинать писать MCTS, если соревнование длится 4 часа.

За это время бот должен был считать данные, принять решение и отправить команду для движения. В данном соревновании на 1 тик давалось около 10-13мс (2 минуты на всю игру). Перебирать все состояния не получится. Этого хватало, чтобы просимулировать порядка 500-1000 ходов. И как бы просто это не звучало, это не сильно далеко от решения победителя. Самый простой алгоритм поиска может выглядеть как сравнение трех вариантов движения: "50 тиков едем влево", "50 тиков едем вправо", "50 тиков жмем стоп".

мы считаем только на 50 ходов вперед, что в большинстве случаев не досчитывает до конца игры, то нам нужна функция оценки, которая скажет, насколько хорошо и плохо состояние мира для нас. Т.к. Например, в конкурсе Russian AI Cup 2014 года были гоночки, но победить можно было и приехав последним, если набрать больше бонусных очков. Чаще всего она построена на эвристиках и понимании, что важно для победы. Оценка может быть посчитана только для последнего состояния симуляции (через 50 тиков) или как сумма оценок промежуточных состояний. Значит и функция оценки должна стимулировать сбор очков одновременно с быстрым движением по трассе. Т.к. Часто оценка "затухает" по времени, чтобы больше влияли состояния, которые произойдут раньше. Также этот прием заставляет бота быстрее выполнять поставленные задачи, а не откладывать все на потом. мы не можем наверняка предсказать врага, то и будущие варианты имеют меньшую вероятность случиться, не будем на них сильно полагаться. Но стоит отметить и то, что бот будет меньше рисковать ради последующей выгоды.

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

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

Но, просматривая свои бои, можно заметить, что в определенных ситуациях он ведет себя странно. Если реализовать все вышеописанные шаги, то, скорее всего, получится весьма неплохой бот, особенно если удастся подобрать хорошую функцию оценки. Тут на помощь приходят костыли и if'ы. Исправить функцию оценки под эти ситуации может быть сложно, либо велик риск сломать другую логику. Лично я очень не люблю эту часть, но уже не раз замечал, что именно костыли в финале могут влиять на расположение мест в первой десятке, а значит один ненаписанный if может стоить вам призового места (мое сердечко болит, когда я пишу эти слова, я тоже люблю красивые алгоритмы и решения). Да, последние дни соревнования часто сводятся к написанию костылей и if’ов, чтобы исправить недочеты в каких-то конкретных условиях.

Есть хорошая статья с архитектурами ИИ на эвристиках. Q: Можно ли обойтись совсем без симуляции?
A: Да, можно использовать решения на эвристиках (деревья принятия решений, куча if'ов и т.п.).

Например, тут некоторые сочетания карт и машин можно было жестко закодировать if'ами и всегда побеждать (или ничья). Q: Насколько использование симуляции лучше подходов на эвристиках?
A: Все зависит от задачи. В данном конкурсе, когда ты переворачиваешь другую машинку, то решения на симуляциях ставили свое колесо на колесо врага, что отключало флаг "в воздухе", а значит враг не мог применять вращение кузова и повернуться обратно на колеса. Однако часто симуляция находит решения, до которых сложно додуматься самому, либо сложно реализовать эвристиками. Но решение не задумывалось о смысле этого, оно просто находило варианты, где враг быстрее упадет на крышу и нажмет свою кнопку.

Хоть нейросети и не нуждаются в симуляции, т.к. Q: Нейронные сети и RL?
A: Как бы это не было популярно, в соревнованиях ботов такие решения редко показывают себя хорошо. Лично я верю, что у них есть потенциал. могут просто выдавать действие исходя из входных параметров текущего состояния, им все еще нужно как-то обучаться, а для этого часто приходится писать симулятор, чтобы гонять игры тысячами локально. Быть может ими можно решать часть задачи, либо использовать в условиях очень ограниченного времени на ответ.

Например, не просто ехать вперед, а каким-то процентом мощности. Примечание
По поводу конечного числа возможных действий стоит уточнить, что иногда разрешено "плавно" регулировать какой-то параметр. Чаще всего хватает всего двух: "полностью включено" и "полностью выключено". В этом случае "конечности" числа выводов легко добиться просто используя несколько значений, например, 0%, 25%, 50%, 75% и 100%.

Ожидания организаторов были в том, что он старый, проверенный временем и имеет много врапперов, чтобы каждый мог включить его в свое решение... В данном соревновании использовали готовый движок chipmunk physics.

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

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

ты знаешь, что борьба идет за алгоритм решения, а не "кто больше просчитает ходов"). За исключением пары участников, которые смогли залезть во внутренности chipmunk’а и оптимизировать копирование его состояния, остальные имели примерно равную по производительности симуляцию (что делало соревнование немного более интересным, т.к.

Описание алгоритмов будет вестись от лица его автора. С этого пункта начинается раздельное описание решений.

Владимир Киселев (Valdemar) 4 место

Алгоритм выглядит следующим образом: Для поиска по пространству решений был использован случайный поиск (Monte Carlo).

  1. Инициализируем геном — последовательность действий (влево, вправо, стоп) на 60 тиков — случайными данными.
  2. Берем лучший найденный геном
  3. Случайным образом меняем одно из действий
  4. При помощи функции оценки получаем число — показатель того, насколько хорош новый геном
  5. Если получилось более удачное решение, то обновляем лучшее решение
  6. Повторяем заново с п.2

То есть за 1 тик успеваем пройти полный цикл около 20ти раз. Мой симулятор выдавал ~100k симуляций мира за 1 секунду, учитывая что на тик есть в среднем ~12мс, получаем 1200 действий на тик.

Поэтому была реализована идея с “растягиванием” действий: вместо генома из 60 ходов будем оперировать цепочкой из 12 “растянутых” ходов — считаем, что каждое действие длится 5 тиков подряд.
Плюс: Повышение качества мутаций за счет уменьшения длины генома, также симуляция может быть запущена раз в 5 тиков и проверить 100 геномов вместо 20ти (для избежания падений по лимиту времени, в итоге остановился на 70).
Минус: растягивание действий может приводить к не оптимальным решениям (например качание на бампере, вместо стабильной стойки) Для поиска оптимального решения такого количества итераций явно не хватало.

Следует отметить приемы, которые позволили значительно улучшить качество работы алгоритма:

  • Случайную инициализацию проводим только на первом тике, все остальное время переиспользуем лучшее найденное решение со сдвигом на 1 ход (действие на 2й тик смещается на 1й и т.д., в конец добавляется случайное действие). Это значительно улучшает качество поиска, поскольку иначе алгоритм "забывает", что собирался делать на прошлом тике и бессмысленно дергается в разные стороны.
  • В начале хода делаем более интенсивные изменения (меняем геном 2 или 3 раза вместо одного) в надежде выйти из локального максимума (подобие температуры в методе имитации отжига).
    Интенсивность была подобрана вручную: первые 30 итераций делаем 3 мутации, следующие 10 по 2, потом по 1.
  • Очень важное значение имеет предсказание действий противника. В ущерб времени на поиск собственного решения запускаем случайный поиск со стороны противника, на 20 итераций, потом 50 для себя, используя информацию об оптимальных ходах противника.
    Лучшее решение противника также переиспользуется на следующем ходу со смещением. При этом во время поиска решения врага, в качестве моих предполагаемых действий используется геном с прошлого хода.

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

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

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

А вот при растягивании одного действия на 5 тиков смысла, кажется, становится больше.
Ещё мне не нравится сама идея — берём лучший набор и пытаемся править где-то у него в начале. Commandos:
Менять по пару действий при таком кол-ве симуляций выглядит не очень осмысленно, ведь за одно действие изменений происходит очень мало. Мне кажется нелогичным, что изменение первых тиков оставят последующие хотя бы относительно адекватными.

Александр Киселев (mortido) 3 место

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

Закодируем решение массивом из 40 чисел, где -1, 0 и 1 соответствуют движению ВЛЕВО, СТОП и ВПРАВО.

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

Оказалось, что лучше всегда тратить 20-30мс, чем сначала 11, а под конец 60 Valdemar:
Интересно, что у меня эта фишка ухудшила игру.

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

Сам поиск решения был одинаковый и для себя и для соперника:

  1. Берем решение с прошлого хода и сдвигаем на 1 ход (который мы уже сделали)
  2. Докидываем в популяцию случайных решений, пока не заполним ее всю
  3. Симулируем все решения и выставляем фитнесс с помощью функции оценки. Лучшее запоминаем.
  4. Пока есть время для расчетов
    1. Хинт, всегда добавлять в популяцию 1 мутацию текущего лучшего решения, запомнить его, если оно лучше
    2. Пока есть место в новой популяции и не превышено время для расчетов (можно выйти на полу заполненной популяции)
      1. Берем двух разных особей и оставляем с лучшим фитнесом — мама
      2. Берем двух разных особей и оставляем с лучшим фитнесом — папа (не должен совпадать с мамой)
      3. Скрещиваем их
      4. Мутируем, если RND < Вероятность Мутации
      5. Симулируем решение и запоминаем его, если оно лучшее

Первый ход в ней и отправляется как действие бота. В результате нам вернется последовательность действий, которая считается оптимальной. количество симуляций, которые можно сделать за тик, было очень небольшое (в т.ч. К сожалению, в моем плане был серьезный недостаток, т.к. Это делало алгоритм больше похожим на случайный поиск или симуляцию отжига (т.к. и из-за долгой оценочной функции), то на сервере соревнования 4 пункт выполнялся всего 1 раз, а для врага и вовсе не выполнялся полностью. Менять что-то было уже поздно, да и 3е место удержать удалось. мы успевали мутировать 1 раз решение с прошлого хода).

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

В итоговой версии генерация случайных решений происходила отрезками, что исключало "дрыгающиеся" на одном месте решения:

  1. Выбиралась случайная команда
  2. Для всей длины решения (40 ходов)
    1. Записываем текущую команду в ячейку
    2. С вероятностью 10% меняем текущую команду на случайную

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

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

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

Кажется на следующем ходу от врага будут найдены контрмеры, как и контрмеры на контрмеры… Но это актуально только в случае, если у нас много больше времени для рассчётов. Commandos:
Про ограничение времени — с нашим кол-вом симуляций я про генетику даже не задумывался бы.
И мне всё же очень не нравится цикличность — выбрали лучшее для врага, затем выбрали лучшее для себя. Хотя в нашем случае хорошо было найти хоть что-то. Можем случайно получить "дрыгающиеся на одном месте решения”.

Алексей Дичковский (Commandos) 1 место

Выбирал худший для себя исход.
Для себя симулировал на глубину x в одном направлении, потом на глубину y в другом (итого 3 * 3 варианта). Для противника всегда симулировал движение во всех трёх направлениях для каждой своей ветки симуляции. Позже для него был добавлен полный перебор последних двух моих действий. Чуть позже добавился набор статических x/y, которые чередовались из тика в тик, что дало хороший буст.
Итого в базовой реализации у меня было (3 * x + 9 * y) * 3 тиков симуляций, а также симуляции лучшего варианта с прошлого хода — 3 * (x + y).

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

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

Т.о. Для ещё большего ускорения после симуляции бейзлайна симулируем наши действия в первую очередь с таким действием противника, которое дало нам наихудший результат. против одного действия соперника) на практике выходило, что в большинстве случаев дерево симулируется ровно 1 раз (т.е.

Видимо дьявол в деталях. Valdemar:
Удивлен, что перебор возможных направлений с глубиной 2 дал такой хороший результат. Идея с лесом деревьев с разными параметрами очень интересная, похожего раньше не встречал.

Перебираются разные варианты, выглядит как хорошее распределение времени на вычисления. mortido:
Здорово! Не уверен, что глубины 2 хватит в других соревнованиях, где за 40-60 тиков можно выполнить более сложный план действий. Выглядит простым в реализации. Также нравится, что для каждого своего хода проверяется до 3х разных ходов противника.
x + y == const ?

Когда x+y != const, то даже аккуратно нормированная по количеству ходов оценка ни к чему хорошему не приводила. В итоге да. И из-за этого получалось хуже. При опасности бот выбирал дерево покороче, что логично.

Владимир Киселев (Valdemar) 4 место

Значения, получаемые от симулятора (угол наклона машины, скорость, расстояние и т.д.) переводились в диапазон [0.. Сразу стоит сказать, что в моей оценочной активно использовалась нормализация. Например были реализованы сценарии типа: старайся ехать побыстрее, но только если угол наклона не слишком большой.
Не берусь судить насколько эта фишка повлияла на успех стратегии в целом, но точно можно сказать, что она помогла во время отладки: в лог выводились составные слагаемые оценочной, что позволяло быстро понять почему бот ведет себя определенным образом. 1].
Это позволило удобно компоновать различные показатели и добиться тонкой настройки поведения.

Итак, в оценочной учитывались:

  • угол наклона машины — нормализовался диапазон от 70 до 180 градусов (здесь и далее: значения не входящие в диапазон обрезаются до соответствующей границы).
    Для обычной багги также давался дополнительный бонус, если враг наклонен и находится в воздухе.
  • расстояния между центрами машин в диапазоне 0..500
  • угловая скорость — диапазон [2pi, pi/4] отображался в [0, 1]
  • близость к кнопке — по формуле учитывается расстояние, угол между точкой и центром кнопки (чтобы поощрять нацеливание в центр), угол машины (бонус не дается, если мы приближаемся со стороны днища, потому что оттуда кнопку все равно не нажать)
  • определение тарана — случай, когда мы едем в сторону противника, он повернут к нам днищем, и наш капот нацелен на точку чуть ниже его переднего колеса.
    Бонус особенно хорош для обычных багги, позволяет определять, когда мы можем с разгона перевернуть противника.
  • скорость — до определенной степени поощряем движение. Позволяет не стоять на месте и в целом играть активнее.
  • разность между минимальной по Y координатой кнопок — актуально при приближении дедлайна.
  • большой штраф если мы проиграли и большой бонус за победу

Угол наклона, близость к кнопке и таран считались 2 раза для меня и противника и давали либо бонус либо штраф, соответственно.

Все составляющие умножались на различные коэффициенты в зависимости от типа машины.

В случае обычной багги пара карт были учтены вручную:

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

я делал много запросов к движку, а они оказались очень медленными. mortido:
Быстрее чем у меня, т.к.

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

Александр Киселев (mortido) 3 место

Эти запросы позволяли находить разные расстояния до ближайших объектов или пересечения объекта и луча. Большую часть параметров для оценочной функции я брал, используя запросы к физическому движку chipmunk. Многие компоненты оценочной функции пришлось исключить перед финалом. Хотя движок и оптимизировал их, используя свои внутренние структуры и кэши, большое количество обращений к нему, в конечном счете, сильно затормозило симуляцию.

Изначально я делал одну оценочную функцию и только после написания скрипта для сбора статистики боёв я разделил ее на 3 части и наговнокодил добавил несколько фиксов.

Вот часть компонентов, которые я смог вспомнить на данный момент (не думаю, что точное указание принципиально важно, главное основная идея):

  • штраф за смерть. Он самый большой и после нее симуляция дальше не идет, просто считается, что мы умираем в каждом последующем тике (так бот будет стараться отложить смерть на потом, чтобы суммарный штраф был меньше);
  • бонус за убийство врага, симуляция продолжается дальше — это помогает с промахами по кнопке врага, когда неправильно предсказано его движение; основная причина таких промахов в том, что мы используем только 1 поведение врага;
  • бонус за скорость;
  • разность высот нижних точек кнопки (чем ближе к дедлайну матча, тем сильнее);
  • расстояние от кнопки до любого препятствия (мне со знаком “+”, противнику со знаком “-”);
    -расстояние от кнопки до противника (мне со знаком “+”, противнику со знаком “-”); немного спорный параметр, он позволял позиционировать машину так, чтобы свою кнопку держать в безопасности, но это часто ставило машину на дыбы и ее переворачивали;
    лучи под 30 градусов от плоскости кнопки, чтобы смотреть расстояние по ним до карты, это немного помогало не переворачиваться (но это не точно);
  • остальные хаки, в основном для защиты от переворотов и правильного позиционирования.

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

Можно попасть в ситуацию, когда бот будет думать “сейчас я постою, но через тик начну разгоняться, чтобы получить побольше бонус” и так несколько тиков подряд, пока внезапно не изменится обстановка (противник сделал непредсказуемый ход и т.д.) и ситуация станет сильно хуже. Valdemar:
Идея давать больший коэффициент ближе к концу достаточно зыбкая.

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

Идею про повышение бонуса за высоту машинки под конец симуляции можно было бы попробовать, может и “взлетела” бы. Commandos:
Не очень понятно, зачем продолжать симуляцию, если враг “умер”… Возможно это костыль для автобусного дедлайна?

Алексей Дичковский (Commandos) 1 место

игры машинку, с которой могут происходит самые разные ситуации. Основная функция оценки делалась под SquaredWheelsBuggy, как под самую интересную с т.з. Оценочная функция для простого Buggy отличалась только тем, что в неё был добавлен бонус за касание колеса соперника, чтобы противник не мог влиять на свою угловую скорость (и часто в такой ситуации просто беспомощно падал на крышу/кнопку).
Кратко:

  1. штраф за смерть;
  2. штраф за угол относительно земли; если мы имеем большую скорость и движемся вверх — коэффициент, с которым работал этот штраф, менялся от 1 до 0; т.о. при быстром наборе высоты угол машинки не учитывался;
  3. штраф за угол относительно соперника. Не очень то хотелось находиться кнопкой к сопернику; также этот угол считался со сдвигом положения соперника на 10 тиков вперёд при текущих скоростях (поэтому машинка чуть раньше заканчивала задавать бесполезный угол в надежде защититься от соперника);
  4. штраф за близость колёс и некоторых контрольных точек соперника до моей кнопки (своя оптимизированная реализация без запросов к движку игру, не учитывала квадратность колёс);
  5. бонус за скорость машинки (считал, что лучше побегать по карте в надежде на ошибку соперника);
  6. небольшой штраф за расстояние до соперника — чуть-чуть чаще двигались к сопернику, чем от него;
  7. штраф/бонус за разницу высот с соперником; в основном точкой отсчёта считался центр масс, для автобуса в более новой реализации — нижняя точка кнопки; новая реализация оценочной для автобуса отличалась слабо и играла не на всех картах.

В пункте 2 для соперника не учитывался “коэффициент набора высоты”. Пункты 1-5 считались зеркально для меня и соперника, с разным знаком.

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

mortido:
Интересная идея с углом к противнику, учитывая его положение через 10 тиков.

Владимир Киселев (Valdemar) 4 место

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

На откуп ифам были отданы:

  • Стойка на бампере для автобуса. Поскольку растягивание действий давало небольшие раскачивания, которые иногда приводили к поражению от линии дедлайна.
  • Движение в стойке для автобуса — актуально для карты с ямой, путем колебаний с разной амплитудой можно было ездить на бампере и как минимум гарантировать ничью на этой карте.
  • Хардкод начальных тиков. Актуально для багги на карте “остров с ямой” и для автобуса на большинстве карт.
    При помощи визуализатора были вычислены действия, которые позволяли стратегиям на ифах занимать оптимальное положение, после чего эти действия были бессовестно скопированы к себе.
    Такой подход является хрупким и работает только если противник не будет к нам приближаться и толкать, но на этот случай включалась симуляция, поэтому в сумме работало достаточно хорошо.

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

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

Заткнуть дыры там, где льётся от решения, покрывающего большую часть ситуаций… Я всё же больше старался положить скрипты на оценочную функцию, но это занимало порядком времени, а результат был местами странный. Commandos:
Суровая реальность if’ов.

Александр Киселев (mortido) 3 место

Это писалось с большой болью в сердце и попытками всячески замаскировать костыли под какую-нибудь логику.

Каждая для своей машинки. Первым делом были разделены 3 оценочные функции. Для “Буханки”, которой выгоднее было не сражаться и просто забраться повыше и стоять в оборонительной позе была написана своя функция. Две из них были практически одинаковыми и отличались коэффициентами. Туда шли даже потенциальные поля для пары карт, которые позволяли ей заезжать на высоту, либо запрыгивать на холмик.

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

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

Идея добавлять аналог потикового хардкода в поиск видится совсем неправильной. Valdemar:
Про потенциальные поля интересно, даже не думал их использовать. А то, что генетический алгоритм не смог найти хорошие ходы совсем неудивительно — на поиск этих ходов участники с эвристиками потратили несколько дней или даже недель. Если мы говорим про принципиальность и эстетическую “красоту” решения, то такой подход еще хуже явных if’ов.

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

Хотя я тоже много времени убил на то, чтобы сделать желаемое через оценочную, но по итогу она была не очень осмысленной и потиковый хардкод был бы проще и надёжней. Commandos:
В данном случае… Если хочешь, чтобы что-то было сделано — сделай это сам, а не проси оценочную сделать так, как ты хочешь.

Алексей Дичковский (Commandos) 1 место

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

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

Для этого сочетания машинки/карты обычная функция оценки отключалась до момента, пока моя стратегия не решит, что соперник не пошёл в атаку (находится слишком близко). Также из хорошо отработавших хардкодов была езда на заднем бампере на карте island hole для buggy. Также похожая, и тоже не идеальная имплементация была на той же карте, но уже для автобуса. Если же такая ситуация имела место — включалась стандартная функция оценки. Иногда физика срабатывала так, что багги просто улетал в космос, функция оценки это находила и считала, что так будет лучше. А для SquaredWheelBuggy на этой карте был предусмотрен штраф за слишком высокую скорость вверх. Скорость большая, мы выше соперника… А вот до момента, когда мы в любом случае умрём, досчитать не хватало дальности симуляции.

На одной карте (Pill map, Bus) старт вообще был сделан потиковым хардкодом и не показывался до самого последнего дня соревнования во избежание копирования, которое было нетрудно сделать в этом соревновании (по итогу на таком сочетании карты/машинки имею 100% побед).

Скрипт мог отрабатывать как корректно, так и не очень (во всех примерах первый раунд), но мне он очень нравился. Также для автобуса была очень удачно заскриптована карта pill hubble map. Ну и статистика говорит в его пользу.

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

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

Хардкод выглядит ужасно, но при этом невероятно эффективен. Valdemar:
Специфика игры такова, что хардкод действий на некоторых картах позволяет играть идеально — как минимум добиться ничьи при помощи пары условий.

mortido:
Хорошо залатал дыры в стратегии, пока я пытался написать “идеальную” оценочную функцию.

Создание симулятора требовало много усилий и опытные участники начинали высказывать мнения, что ничего интересного мы не увидим. Valdemar:
Начало контеста было довольно скучным. Этакие “фанатики”, которые после рабочего дня за компьютером, приходят домой и дорабатывают бота в ущерб домашним делам и, иногда, сну 🙂
Впечатления великолепные, спасибо mailru за то, что они организуют такие конкурсы. Затем начались вечера (и даже немного ночи) постоянных доработок и стало гораздо веселее.
Я участвую в таких соревнованиях ради эмоций и удовольствия от общения в кругу таких же любителей игрового ИИ.

Или когда тебе кидают реплей, где твой бот убил 3 союзников по команде, а ты делаешь вид, что это случайно… хотя это было немного другое соревнование. mortido:
Соревнования ботов для меня всегда приносят кучу эмоций: когда ты смотришь как твой бот начинает побеждать всех и ты полночи просто смотришь бои, а потом утром приходят крутые ребята и ломают ему лицо… Очень нравятся моменты, где твоя стратегия начинает находить решения, до которых ты бы не додумался (например как тут с колесом и переворотом).

И, пожалуй, немного не так, как стоило. Commandos:
Как-то странно я провёл это соревнование, слишком рано начал впиливать костыли. Но по итогу это сказалось на оценочной функции — она была не сильно продуманная, за что я чуть не поплатился.
Интеграция с чипманком убивала — дотошное копирование движка из питона в С++. Хотя с другой стороны… Костылями тут очень много погоды и сделалось. После написания симулятора долго не мог решить, с какой стороны подойти к написанию бота. На этот раз это была половина успеха. Потом увидел в топ 1 мортидо

и пошёл ломать его боту лицо и решил написать хоть что-нибудь.

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

Ru Group за организацию конкурса. Отдельное спасибо Дмитрию и Mail.

Исходники Valdemar
Исходники mortido
Кладезь статей по теме

Пачка гифок, которые остались после соревнования

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть