Halite 3 bot

Данный бот создан в ходе соревнования Halite3 и занял 72 место (bogdandm) (и 34 на момент, когда я бросил совернование в виду нехватки времени). Это было мое первое соревнование такого рода, которое дало возможность узнать массу новых приемов оптимизации и алгоритмов.

Многие решения были подобранны по наитию и не имеют ни какой математической базы под собой.

Краткие правила соревнования

Официальные правила доступны по ссылке Halite3.

Игра происходит на квадратном закольцованном поле, которое состоит из клеток с ресурсами (галитом). Цель игры - добыть как можно ресурсов при помощи кораблей. Корабли строятся на верфи и тратят ресурсы для передвижения по клеткам (стоимость зависит от кол-ва ресурсов на клетке). Для того чтобы добытые ресурсы зачислились игроку, корабль должен вернуться на верфь или дропофф (специальная постройка). Если в радиусе 4х клеток от корабля находится 2+ вражеских корабля (корабль вдохновлен), то он получает двукратный бонус к добыче.

Алгоритм

Общая идея

В целом всю задачу игры можно разделить на составляющие:

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

Весь алгоритм построен на поле потенциалов, собирающемся из нескольких компонентов.

Основной цикл

Каждый ход состоит из одних и тех же стадий (не считая стадии инициализации в начале игры):

1. Поиск позиции для дропоффа и привязка корабля для его постройки к этой позиции

2. Перемещение корабля из шага (1)

3. Высчитывание маски для поля потенциалов (глобальной)

   • Маска (1) для вражеских кораблей, включает в себя в штраф в малом радиусе и бонус радиусе вдохновения

   • Размытая отрицательная маска (2) союзных кораблей

   • Маска (3) усредненных по площади ресурсов (размытие по Гауссу)

   • Копия карты ресурсов с обрезанными минимумами (создавали лишний шум в конце игры, когда эффективней было стоять на месте, а не пытаться добыть 5-10 единиц ресурса)

4. Обход всех своих кораблей

   1. Перемещение корабля домой при определенном объеме ресурсов. Путь искался алгоритмом A* с модификацией для избегания вражеских кораблей (считаются как клетки с очень высокой стоимостью перемещения)

   2. Поиск цели для тарана в округе

   3. Высчитывание маски для каждого корабля в отдельности

      • Штраф для клетки, являющейся целью (в т.ч. с предыдущего хода) другого корабля

      • Ценность ресурса уменьшается с расстоянием согласно формуле расстояние ^ k, где 1.0 < k < 2.0. Таким образом, при приближении к первоначальной клетке ценность некоторых клеток, находящихся по пути, будет перевешивать и корабль будет "расчищать" дорогу к большим скоплениям ресурсов, чтобы ему было проще возвратиться на базу

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

      • Все маски накладываются на карту ресурсов

      • Для клетки, на которой стоит корабль, применяется бонус добычи ресурсов

      • Найденная клетка с максимальным потенциалом становится целью данного корабля. Если потенциал меньше определенного предела, корабль движется в случайном направлении или стоит на месте.

5. Цели кораблей преобразуются в список их ходов

   1. Получаем словарь (корабль -> список направлений для движения)

   2. Пока можно безопасно двигать корабли двигаем их

   3. Если можно поменять местами 2 корабля - меняем

   4. Возвращаемся к шагу 2

6. Производим корабли при выполнении определенных условий

Поиск мест для дропоффов

...

Процесс разработки и различные решения

Разработка с самого начала велась в PyCharm. Он экономит огромное количество времени автодополнением и подсветкой ошибок. Кроме того как только я понял, что я в этом соревновании надолго, весь проект был перенесен в Git и, начиная с 5 версии бота, все версии имеют свои тэги в системе контроля версий. Это помогло несколько раз отследить, что я сломал в попытках улучшить эффективность.

Одной из важнейших частей для разработки был визуализатор при чем не реплеев, а реал-тайм, который подключался к классу бота (основной код бота написан в объектно-ориентированном стиле). Собственно работать с полями потенциалов и алгоритмами поиска путей без их визуализации почти не реально. По мере добавления новых слоев в поле потенциалов они выводились в визуализацию. Если добавить к этому возможность подключения дебаггера PyCharm'а с инспектором переменных, то большая часть ошибок отлавливалась за несколько минут. Визуализатор написан на pygame как самом простом и низкоуровневом решении.

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

В составе starter-kit'а соревнования давался модуль hlt, содержащий io, модели данных и простейшую логику для перемещений. Он был основательно переписан, в частности были добавлены аннотации типов (надеюсь, что в сл. соревновании они будут из коробки) и расширен функционал части классов (например, в класс игровой карты добавлены поля с numpy-массивами для ускорения работы).

Все вычисления по максимуму переведены на numpy/scipy, так как стандартных списков даже близко не хватило бы по производительности. Все матрицы, которые не меняются во время игры, а только смещаются (например, круг вдохновения) создавались заранее и смещались методом .roll.

Ещё одно решение, о котором я пожалел, что не использовал его сразу - конфиг с параметрами бота. Большая часть логики зависит от магических констант. И ближе к концу разработки их стало больше 20. А некоторые имело смысл менять в зависимости от размера карты или числа игроков. В итоге все это было перенесено в единый YAML-конфиг, содержащий значения по умолчанию и "костыльные" значения для разных карт.

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

В самом конце использовались Jupyter-блокноты для проверки некоторых чисто математических теорий и сбора статистики с сайта совернования.

Картинки

Mask 1

Маска вдохновения и штрафа вокруг вражеских кораблей. Для поиска вдохновения используется наложение заранее созданных масок с последуюшей обрезкой максимумов/минимумов до необходимых значений. Это позволяет вычислять всю маску за один проход по кораблям.

Mask 2

Размытая отрицательная маска союзных кораблей

Mask 3

Размытые ресурсы

Dropoff 1

Поиск места для дропоффа