- PVSM.RU - https://www.pvsm.ru -
Меня зовут Волков Игорь. Я работаю в консалтинговой компании на позициях Java разработчика, архитектора, руководителя команды, технического менеджера. Разные роли в зависимости от текущих потребностей проекта. Обратил внимание на конкурсы от mail.ru давно, но активно поучаствовать получилось только на Paper IO.
В этот раз организаторы предложили реализовать стратегию управления ботом по мотивам популярной игры. Подробнее с правилами можно ознакомиться здесь [1]. Код моей стратегии можно найти здесь [2], а примеры игр на сайте чемпионата [3].
В самом начале конкурса, как мне показалось, самой часто всплывающей идей реализации было использование MCTS [4]. Поэтому потратил немного времени на эксперименты с этим алгоритмом. Так и не придумав как же можно его эффективно использовать для решения поставленной задачи, решил начать с генерации множества прямоугольных маршрутов (с двумя, а потом с тремя поворотами) и их последующей оценкой.
Высокоуровневый алгоритм стратегии можно представить следующими 6 пунктами:
Этот алгоритм так и не изменился по ходу соревнования. Модифицировались лишь способ формирования маршрутов бота и их оценка.
Класс SimpleStrategy [5] содержит начальную версию стратегии, а класс BestStrategy [6] улучшенная версия, которая и заняла 2 место в соревновании.
Состояние мира передается в виде JSON [7] объекта через STDIN [8]. Увидел в pom.xml [9], что можно воспользоваться библиотекой Gson [10] и задача чтения состояния мира существенно упростилась. При помощи библиотеки Gson [10] десериализовал JSON [7] строку, прочитанную из стандартного потока ввода, в экземпляр класса Message [11]. Код находится в Main.java (строки 44-49) [12].
Использовать транспортные объекты в основном коде программы как правило не очень удобно и архитектурно неверно. Например, организаторы в силу тех или иных причин могут изменить формат сообщений. Поэтому, надо преобразовать транспортные объекты в рабочие, которые и будут использоваться в основном коде программы. Классы Player [13] и PlayerState [14] сохраняют состояние бота, а утилитный класс MessagePlayer2PlayerConverter [15] помогает создать эти классы на основе данных из транспортного сообщения. Класс Bonus [16] содержит информацию о бонусе клетки игрового поля. Код создания рабочих объектов находится в Main.java (строки 61-74) [17].
В первых версиях стратегии (SimpleStrategy [5]) путь задавался при помощи классов MovePlanWithScore [18] и Move [19]. Move [19] задает направление движения и на сколько клеток в этом направлении бот должен двигаться, а MovePlanWithScore [18] содержит маршрут, заданный массивом Move [19], и оценку этого маршрута. Массив мог содержать от одного до четырех объектов Move [19]. Несмотря на то что рассматриваются только прямоугольные маршруты с не больше чем тремя поворотами, по факту маршрут бота получается в виде ломанной линии. Это достигается за счет выбора нового лучшего прямоугольного маршрута на каждом ходу. Функция генерации маршрутов [20], реализованная в виде вложенных циклов формирует список из MovePlanWithScore [18] для его последующей оценки.
Такое формирование траекторий движения бота было не очень эффективным с точки зрения производительности последующей оценки, так как приходилось по нескольку раз обсчитывать одни и те же траектории, но было очень полезным для осмысления механики игры.
В поздних версиях стратегии BestStrategy [6] стал применять дерево маршрутов. Класс MoveNode [21] отражает узел этого дерева. Дерево полностью формируется на старте стратегии. Обратите внимание на метод init класса MoveNode [22]. Он очень похож на генерацию маршрутов из класса SimpleStrategy [5]. Принципиально, рассматриваемый маршрут мало чем отличается от первой версии.
Формирование маршрутов, думаю, можно было бы еще чуть улучшить, добавив еще один поворот. Но времени на оптимизацию не хватило.
Где бы не находился бот, для него всегда выбирался лучший маршрут заканчивающийся на своей территории. Для оценки маршрута ввел два показателя: score и risk. Score – примерно отражает количество набранных очков на один тик пути, а risk – количество тиков, которых не хватает для завершения пути (например, из-за того что соперник может схватить за хвост). Risk появился не сразу. В первой версии, если бот вдруг обнаруживал на середине пути что он не успевает завершить маршрут – «сходил с ума», так как все опасные пути для него были одинаково плохими. Из всех рассматриваемых маршрутов выбирается самый «безопасный» с максимальным количеством очков на один тик пути.
Для оценки безопасности маршрута я рассчитываю матрицу достижимости: для каждой клетки игрового поля нахожу тик, на котором в ней может оказаться бот соперника. Сначала только тик, а позже добавил расчет длины хвоста. Бонусы, которые можно подобрать по пути, также не учитывались в первых версиях стратегии. Класс TimeMatrixBuilder [23] рассчитывает матрицы тиков и длин хвоста ботов соперников. Далее эти матрица используются для оценки риска. Если мой бот находится на своей территории в момент расчета очередного хода — опасным маршрутам присваивается максимальный уровень риска, если бот был уже в пути на чужой или нейтральной территории риск оценивается как разница тиков завершения пути (бот пришел на свою территорию) и тика когда ему может грозить опасность (например, чужой бот может наступить на хвост).
В первых версиях стратегии score считался только на основе захваченной территории и немного учитывались бонусы. Для нахождения захваченных клеток использую рекурсивный алгоритм [24]. Многие участники конкурса жаловались на странность и чрезмерную вычислительную сложность алгоритма, который использовался организаторами в Local Runner [25]. Предположу, что это было сделано намеренно, чтобы не давать участникам конкурса готовых решений.
Странно, но несмотря на примитивность первых версий стратегии, она показал себя достаточно хорошо: 10 место в песочнице. Правда, в предфинальном раунде стал быстро опускаться вниз: другие участники улучшали свои стратегии.
Мой бот часто погибал. В первую очередь из-за того, что строился маршрут к территории, которая захватывалась ботами соперников. Путь неожиданно удлинялся и моего бота ловили за хвост. Часто погибал из-за неверного предсказания длины хвоста и скорости бота соперника. Например, бот соперника взявший замедление представлял опасность, так как при приближенном расчете стратегия полагала, что он должен был бы уже выйти из клетки, а он все еще был там. Для борьбы с этими проблемами стал рассчитывать большее количество показателей для каждой клетки игрового поля (классы AnalyticsBuilder [26] и CellDetails [27]).
Показатели обсчета клетки игрового поля
Глубина аналитики ограничена 10 ходами. Думаю, можно было добиться большей глубины, отказавшись от обсчета отдельных соперников или ввести плавающую глубину, но времени на оптимизацию не хватило. В дополнение к AnalyticsBuilder [26] стал использовать SimpleTickMatrixBuilder [28] если не хватало глубины просчета AnalyticsBuilder [26]. Результаты аналитики используются в BestStrategy [6].
Функция оценки тоже немного улучшилась:
Первые версии стратегии содержали большое количество опечаток и ошибок: видимо, результат ночного программирования. Например, в классе Cell [29] совершенно неверно считал индекс: вместо this.index = x * Game.sizeY + y
было this.index = x * Game.width + y
. Сначала пытался полагаться только на тесты, но интуиция подсказала что без визуализации и без проигрывания ранее сыгранных матчей сложно будет находить ошибки в коде и анализировать причины принятия ошибочных решений. В результате появился визуализатор DebugWindow [30], в котором можно просмотреть пошагово ранее сыгранные игры, а также запустить отладку на нужном тике. Не очень красивый, написанный на скорую руку код, но он мне сильно помог при отладке. Например, сразу была обнаружена ошибка с неверным расчетом индекса ячейки. Многие участники конкурса выводили отладочную информацию в консоль, но мне показалось этого недостаточно.
Чтобы не тратить время на создание объектов и работу GC, некоторые объекты постарался создать заранее. Это клетки игрового поля (класс Cell [29]). Дополнительно для каждой клетки определил соседей. Заранее создал дерево возможных путей (класс MoveNode [21]).
Предполагал, что придется симулировать множество сценариев, а в процессе будет портится текущее состояние и его надо будет каждый раз восстанавливать. Поэтому для хранения состояния мира постарался использовать как можно более упакованные структуры. Для хранения занятой территории — BitSet (класс PlayerTerritory [31]). Каждая клетка игрового поля пронумерована, а номер клетки соответствовал номеру бита в BitSet. Для хранения хвоста использовал BitSet совместно с ArrayDeque (класс PlayerTail [32]).
Правда я так и не дошел до проигрывания различных сценариев из-за нехватки времени. А так как основная функция расчета пути стала рекурсивной и все состояние можно было хранить на стеке — последние оптимизации мне не очень пригодились.
При оценке риска маршрута моего бота я учитывал каждого соперника независимо. На самом деле каждый из соперников тоже боится погибнуть. Поэтому, стоило бы это учитывать в оценке риска. По крайней мере, это точно надо было учитывать в финальных играх.
Учет будущей гибели соперника. Иногда случалось так, что бот захватывает территорию соперника, а соперник неожиданно погибает. Обидно, так как в результате захватываешь только пустые клетки.
Учет пустых клеток, которые будут захвачены в ближайшем будущем в функции оценки.
Рекомендую всем разработчикам активно принимать участие в конкурсах AI Cups. Это развивает
Большое спасибо организаторам. Несмотря на некоторые технические проблемы, конкурс получился интересным. С нетерпением жду следующих!
Автор: Игорь Волков
Источник [34]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/java/329350
Ссылки в тексте:
[1] здесь: https://github.com/MailRuChamps/miniaicups/tree/master/paperio
[2] здесь: https://github.com/volk1674/paperio
[3] сайте чемпионата: https://aicups.ru/profile/2692/
[4] MCTS: https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
[5] SimpleStrategy: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/SimpleStrategy.java
[6] BestStrategy: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/BestStrategy.java
[7] JSON: https://ru.wikipedia.org/wiki/JSON
[8] STDIN: https://en.wikipedia.org/wiki/Standard_streams
[9] pom.xml: https://github.com/MailRuChamps/miniaicups/blob/master/paperio/dockers/java1.8/pom.xml
[10] Gson: https://en.wikipedia.org/wiki/Gson
[11] Message: https://github.com/volk1674/paperio/blob/master/src/main/java/message/Message.java
[12] Main.java (строки 44-49): https://github.com/volk1674/paperio/blob/aa54558e19bd468791fa35211092158268dbb777/src/main/java/Main.java#L44-L49
[13] Player: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/Player.java
[14] PlayerState: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/PlayerState.java
[15] MessagePlayer2PlayerConverter: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/utils/MessagePlayer2PlayerConverter.java
[16] Bonus: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/Bonus.java
[17] Main.java (строки 61-74): https://github.com/volk1674/paperio/blob/aa54558e19bd468791fa35211092158268dbb777/src/main/java/Main.java#L61-L74
[18] MovePlanWithScore: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/MovePlanWithScore.java
[19] Move: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/Move.java
[20] Функция генерации маршрутов: https://github.com/volk1674/paperio/blob/aa54558e19bd468791fa35211092158268dbb777/src/main/java/strategy/SimpleStrategy.java#L243-L261
[21] MoveNode: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/MoveNode.java
[22] init класса MoveNode: https://github.com/volk1674/paperio/blob/aa54558e19bd468791fa35211092158268dbb777/src/main/java/strategy/MoveNode.java#L71-L96
[23] TimeMatrixBuilder: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/TimeMatrixBuilder.java
[24] рекурсивный алгоритм: https://github.com/volk1674/paperio/blob/aa54558e19bd468791fa35211092158268dbb777/src/main/java/strategy/Game.java#L108-L142
[25] Local Runner: https://github.com/MailRuChamps/miniaicups/tree/master/paperio#3-%D0%BE%D1%81%D0%BE%D0%B1%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D0%B8-%D0%B7%D0%B0%D0%BF%D1%83%D1%81%D0%BA%D0%B0-local-runner
[26] AnalyticsBuilder: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/AnalyticsBuilder.java
[27] CellDetails: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/CellDetails.java
[28] SimpleTickMatrixBuilder: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/SimpleTickMatrixBuilder.java
[29] Cell: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/Cell.java
[30] DebugWindow: https://github.com/volk1674/paperio/blob/master/src/main/java/debug/DebugWindow.java
[31] PlayerTerritory: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/PlayerTerritory.java
[32] PlayerTail: https://github.com/volk1674/paperio/blob/master/src/main/java/strategy/model/PlayerTail.java
[33] мышление: http://www.braintools.ru
[34] Источник: https://habr.com/ru/post/466597/?utm_source=habrahabr&utm_medium=rss&utm_campaign=466597
Нажмите здесь для печати.