Данный бот создан в ходе соревнования Halite3 и занял 72 место (bogdandm) (и 34 на момент, когда я бросил совернование в виду нехватки времени). Это было мое первое соревнование такого рода, которое дало возможность узнать массу новых приемов оптимизации и алгоритмов.
Многие решения были подобранны по наитию и не имеют ни какой математической базы под собой.
Официальные правила доступны по ссылке Halite3.
Игра происходит на квадратном закольцованном поле, которое состоит из клеток с ресурсами (галитом). Цель игры - добыть как можно ресурсов при помощи кораблей. Корабли строятся на верфи и тратят ресурсы для передвижения по клеткам (стоимость зависит от кол-ва ресурсов на клетке). Для того чтобы добытые ресурсы зачислились игроку, корабль должен вернуться на верфь или дропофф (специальная постройка). Если в радиусе 4х клеток от корабля находится 2+ вражеских корабля (корабль вдохновлен), то он получает двукратный бонус к добыче.
В целом всю задачу игры можно разделить на составляющие:
- Определение оптимальных клеток для добычи
- Поиск путей к этим клеткам
- Поиск оптимального пути для разгрузки
- Нахождение потенциальных мест для постройки дропоффов
- Стратегия постройки новых кораблей
- Избегание столкновений с вражескими кораблями и охота за полностью загруженными кораблями
Весь алгоритм построен на поле потенциалов, собирающемся из нескольких компонентов.
Каждый ход состоит из одних и тех же стадий (не считая стадии инициализации в начале игры):
-
Поиск позиции для дропоффа и привязка корабля для его постройки к этой позиции
-
Перемещение корабля из шага (1)
-
Высчитывание маски для поля потенциалов (глобальной)
-
Маска (1) для вражеских кораблей, включает в себя в штраф в малом радиусе и бонус радиусе вдохновения
-
Размытая отрицательная маска (2) союзных кораблей
-
Маска (3) усредненных по площади ресурсов (размытие по Гауссу)
-
Копия карты ресурсов с обрезанными минимумами (создавали лишний шум в конце игры, когда эффективней было стоять на месте, а не пытаться добыть 5-10 единиц ресурса)
-
-
Обход всех своих кораблей
-
Перемещение корабля домой при определенном объеме ресурсов. Путь искался алгоритмом A* с модификацией для избегания вражеских кораблей (считаются как клетки с очень высокой стоимостью перемещения)
-
Поиск цели для тарана в округе
-
Высчитывание маски для каждого корабля в отдельности
-
Штраф для клетки, являющейся целью (в т.ч. с предыдущего хода) другого корабля
-
Ценность ресурса уменьшается с расстоянием согласно формуле
расстояние ^ k, где1.0 < k < 2.0. Таким образом, при приближении к первоначальной клетке ценность некоторых клеток, находящихся по пути, будет перевешивать и корабль будет "расчищать" дорогу к большим скоплениям ресурсов, чтобы ему было проще возвратиться на базу -
Маска вражеских кораблей и вдохновения обрезается в радиусе больше заданного вокруг корабля, т.к. нет смысла учитывать корабли, которые переместятся быстрее, чем наш корабль достигнет цели
-
Все маски накладываются на карту ресурсов
-
Для клетки, на которой стоит корабль, применяется бонус добычи ресурсов
-
Найденная клетка с максимальным потенциалом становится целью данного корабля. Если потенциал меньше определенного предела, корабль движется в случайном направлении или стоит на месте.
-
-
-
Цели кораблей преобразуются в список их ходов
-
Получаем словарь
(корабль -> список направлений для движения) -
Пока можно безопасно двигать корабли двигаем их
-
Если можно поменять местами 2 корабля - меняем
-
Возвращаемся к шагу 2
-
-
Производим корабли при выполнении определенных условий
...
Разработка с самого начала велась в PyCharm. Он экономит огромное количество времени автодополнением и подсветкой ошибок. Кроме того как только я понял, что я в этом соревновании надолго, весь проект был перенесен в Git и, начиная с 5 версии бота, все версии имеют свои тэги в системе контроля версий. Это помогло несколько раз отследить, что я сломал в попытках улучшить эффективность.
Одной из важнейших частей для разработки был визуализатор при чем не реплеев, а реал-тайм, который подключался к классу бота (основной код бота написан в объектно-ориентированном стиле). Собственно работать с полями потенциалов и алгоритмами поиска путей без их визуализации почти не реально. По мере добавления новых слоев в поле потенциалов они выводились в визуализацию. Если добавить к этому возможность подключения дебаггера PyCharm'а с инспектором переменных, то большая часть ошибок отлавливалась за несколько минут. Визуализатор написан на pygame как самом простом и низкоуровневом решении.
Логгер использовался с самого начала и содержал набор информационных сообщений со всякими цифрами, но по мере разрастания логики лог стал не читаемым и где-то к середине соревнования сформировался единый стиль сообщений для логгера.
В составе starter-kit'а соревнования давался модуль hlt, содержащий io, модели данных и простейшую логику для перемещений. Он был основательно переписан, в частности были добавлены аннотации типов (надеюсь, что в сл. соревновании они будут из коробки) и расширен функционал части классов (например, в класс игровой карты добавлены поля с numpy-массивами для ускорения работы).
Все вычисления по максимуму переведены на numpy/scipy,
так как стандартных списков даже близко не хватило бы по производительности.
Все матрицы, которые не меняются во время игры, а только смещаются (например, круг вдохновения) создавались заранее
и смещались методом .roll.
Ещё одно решение, о котором я пожалел, что не использовал его сразу - конфиг с параметрами бота. Большая часть логики зависит от магических констант. И ближе к концу разработки их стало больше 20. А некоторые имело смысл менять в зависимости от размера карты или числа игроков. В итоге все это было перенесено в единый YAML-конфиг, содержащий значения по умолчанию и "костыльные" значения для разных карт.
Были написан скрипт анализа статистики локальных реплеев и использовался локальный матч-мэйкер на домашнем сервере для проверки мелких изменений и подгонки параметров. Кроме того была попытка применить генетические алгоритмы для оптимизации, но большая зашумленность, медленная скорость боев, нехватка вычислительных мощностей свела эту идею на нет.
В самом конце использовались Jupyter-блокноты для проверки некоторых чисто математических теорий и сбора статистики с сайта совернования.
Маска вдохновения и штрафа вокруг вражеских кораблей. Для поиска вдохновения используется наложение заранее созданных масок с последуюшей обрезкой максимумов/минимумов до необходимых значений. Это позволяет вычислять всю маску за один проход по кораблям.
Размытая отрицательная маска союзных кораблей
Размытые ресурсы
Поиск места для дропоффа
