История второго места в Mini AI Cup 4: Paper IO

Меня зовут Волков Игорь. Я работаю в консалтинговой компании на позициях Java разработчика, архитектора, руководителя команды, технического менеджера. Разные роли в зависимости от текущих потребностей проекта. Обратил внимание на конкурсы от mail.ru давно, но активно поучаствовать получилось только на Paper IO.

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

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

Алгоритм стратегии

Высокоуровневый алгоритм стратегии можно представить следующими 6 пунктами:

1. Прочитать состояние мира
2. Преобразовать объекты сообщения в рабочие объекты
3. Сформировать набор прямоугольных маршрутов
4. Оценить каждый из сформированных маршрутов
5. Выбрать лучший маршрут
6. Отправить команду

Этот алгоритм так и не изменился по ходу соревнования. Модифицировались лишь способ формирования маршрутов бота и их оценка.

Класс SimpleStrategy содержит начальную версию стратегии, а класс BestStrategy улучшенная версия, которая и заняла 2 место в соревновании.

Чтение состояния мира

Состояние мира передается в виде JSON объекта через STDIN. Увидел в pom.xml, что можно воспользоваться библиотекой Gson и задача чтения состояния мира существенно упростилась. При помощи библиотеки Gson десериализовал JSON строку, прочитанную из стандартного потока ввода, в экземпляр класса Message. Код находится в Main.java (строки 44-49).

Создание рабочих объектов

Использовать транспортные объекты в основном коде программы как правило не очень удобно и архитектурно неверно. Например, организаторы в силу тех или иных причин могут изменить формат сообщений. Поэтому, надо преобразовать транспортные объекты в рабочие, которые и будут использоваться в основном коде программы. Классы Player и PlayerState сохраняют состояние бота, а утилитный класс MessagePlayer2PlayerConverter помогает создать эти классы на основе данных из транспортного сообщения. Класс Bonus содержит информацию о бонусе клетки игрового поля. Код создания рабочих объектов находится в Main.java (строки 61-74).

Формирование маршрутов

В первых версиях стратегии (SimpleStrategy) путь задавался при помощи классов MovePlanWithScore и Move. Move задает направление движения и на сколько клеток в этом направлении бот должен двигаться, а MovePlanWithScore содержит маршрут, заданный массивом Move, и оценку этого маршрута. Массив мог содержать от одного до четырех объектов Move. Несмотря на то что рассматриваются только прямоугольные маршруты с не больше чем тремя поворотами, по факту маршрут бота получается в виде ломанной линии. Это достигается за счет выбора нового лучшего прямоугольного маршрута на каждом ходу. Функция генерации маршрутов, реализованная в виде вложенных циклов формирует список из MovePlanWithScore для его последующей оценки.

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

В поздних версиях стратегии BestStrategy стал применять дерево маршрутов. Класс MoveNode отражает узел этого дерева. Дерево полностью формируется на старте стратегии. Обратите внимание на метод init класса MoveNode. Он очень похож на генерацию маршрутов из класса SimpleStrategy. Принципиально, рассматриваемый маршрут мало чем отличается от первой версии.

Формирование маршрутов, думаю, можно было бы еще чуть улучшить, добавив еще один поворот. Но времени на оптимизацию не хватило.

Оценка маршрута

Где бы не находился бот, для него всегда выбирался лучший маршрут заканчивающийся на своей территории. Для оценки маршрута ввел два показателя: score и risk. Score – примерно отражает количество набранных очков на один тик пути, а risk – количество тиков, которых не хватает для завершения пути (например, из-за того что соперник может схватить за хвост). Risk появился не сразу. В первой версии, если бот вдруг обнаруживал на середине пути что он не успевает завершить маршрут – «сходил с ума», так как все опасные пути для него были одинаково плохими. Из всех рассматриваемых маршрутов выбирается самый «безопасный» с максимальным количеством очков на один тик пути.

Для оценки безопасности маршрута я рассчитываю матрицу достижимости: для каждой клетки игрового поля нахожу тик, на котором в ней может оказаться бот соперника. Сначала только тик, а позже добавил расчет длины хвоста. Бонусы, которые можно подобрать по пути, также не учитывались в первых версиях стратегии. Класс TimeMatrixBuilder рассчитывает матрицы тиков и длин хвоста ботов соперников. Далее эти матрица используются для оценки риска. Если мой бот находится на своей территории в момент расчета очередного хода — опасным маршрутам присваивается максимальный уровень риска, если бот был уже в пути на чужой или нейтральной территории риск оценивается как разница тиков завершения пути (бот пришел на свою территорию) и тика когда ему может грозить опасность (например, чужой бот может наступить на хвост).

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

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

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

Показатели обсчета клетки игрового поля

1. Тик, на котором бот соперника сможет занять клетку (тик хватания за хвост)
2. Тик, на котором бот соперника сможет войти в клетку
3. Длина хвоста при входе в клетку
4. Тик, на котором бот соперника сможет выйти из клетки
5. Длина хвоста при выходе из клетки
6. Тик, на котором клетка может быть захвачена ботом соперника
7. Тик, на котором клетка может быть целью для захвата территории
8. Тик, на котором по клетке может быть нанесен удар пилой

Глубина аналитики ограничена 10 ходами. Думаю, можно было добиться большей глубины, отказавшись от обсчета отдельных соперников или ввести плавающую глубину, но времени на оптимизацию не хватило. В дополнение к AnalyticsBuilder стал использовать SimpleTickMatrixBuilder если не хватало глубины просчета AnalyticsBuilder. Результаты аналитики используются в BestStrategy.

Функция оценки тоже немного улучшилась:

1. Стал учитывать бонусы: штраф за взятие бонуса замедления и поощрение за взятие бонусов ускорения и пилы. В результате бот стал успешно избегать плохих бонусов и подбирал попутные хорошие.
2. Стал учитывать столкновение головами. Добавил немного очков за победное столкновение. Чем дальше возможное столкновение, тем меньше очков.
3. Чтобы понизить вероятность окружения добавил немного очков за взятие граничных клеток соперника.
4. Понизил ценность пустых клеток на границе: чем дальше от центра, тем меньше ценность. Наблюдая за боями финала, пришел к выводу что за сам факт захвата пустой клетки вообще не надо было начислять очков. Ценность пустой клетки должна зависеть от близости к большим скоплениям клеток противника. К сожалению, в финале уже нельзя было править стратегию.
5. Добавил очков за окружение головы бота соперника. Не уверен, что это как-то помогло. Может быть, с самыми простыми стратегиями.
6. Добавил очков даже за безрезультативное хватание за хвост (бот соперника успевал захватить территорию на том же тике в котором мой бот наступал ему на хвост). Точно не уверен, но думаю, что это мешало ботам соперника захватывать чужую территорию и им приходилось чаще возвращаться на свою.
7. В случае обнаружения возможной гибели от захвата сильно увеличивал стоимость граничных клеток территории соперника.

Отладка стратегии

Первые версии стратегии содержали большое количество опечаток и ошибок: видимо, результат ночного программирования. Например, в классе Cell совершенно неверно считал индекс: вместо this.index = x * Game.sizeY + y было this.index = x * Game.width + y. Сначала пытался полагаться только на тесты, но интуиция подсказала что без визуализации и без проигрывания ранее сыгранных матчей сложно будет находить ошибки в коде и анализировать причины принятия ошибочных решений. В результате появился визуализатор DebugWindow, в котором можно просмотреть пошагово ранее сыгранные игры, а также запустить отладку на нужном тике. Не очень красивый, написанный на скорую руку код, но он мне сильно помог при отладке. Например, сразу была обнаружена ошибка с неверным расчетом индекса ячейки. Многие участники конкурса выводили отладочную информацию в консоль, но мне показалось этого недостаточно.

Оптимизация

Чтобы не тратить время на создание объектов и работу GC, некоторые объекты постарался создать заранее. Это клетки игрового поля (класс Cell). Дополнительно для каждой клетки определил соседей. Заранее создал дерево возможных путей (класс MoveNode).

Предполагал, что придется симулировать множество сценариев, а в процессе будет портится текущее состояние и его надо будет каждый раз восстанавливать. Поэтому для хранения состояния мира постарался использовать как можно более упакованные структуры. Для хранения занятой территории — BitSet (класс PlayerTerritory). Каждая клетка игрового поля пронумерована, а номер клетки соответствовал номеру бита в BitSet. Для хранения хвоста использовал BitSet совместно с ArrayDeque (класс PlayerTail).

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

Нереализованные идеи

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

Учет будущей гибели соперника. Иногда случалось так, что бот захватывает территорию соперника, а соперник неожиданно погибает. Обидно, так как в результате захватываешь только пустые клетки.

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

Рекомендации и благодарности

Рекомендую всем разработчикам активно принимать участие в конкурсах AI Cups. Это развивает мышление и помогает через игру узнать новые алгоритмы. А как показал мой опыт, для занятия призового места достаточно немного усердия и даже простой и не очень оптимальный код может принести результат.

Большое спасибо организаторам. Несмотря на некоторые технические проблемы, конкурс получился интересным. С нетерпением жду следующих!