Halite II от Two Sigma оказался самым захватывающим соревнованием по программированию, в котором я когда-либо играл. Он обеспечивает онлайн-подбор игроков, чтобы наблюдать за битвой вашего кода с другими игроками по всему миру. Цель состоит в том, чтобы контролировать все планеты и уничтожать вражеских игроков. Для этого игроки должны собирать ресурсы с планет, чтобы создавать больше кораблей, которые можно использовать для атаки вражеских планет или кораблей. Если вы хотите узнать больше об игре, посетите сайт halite.io.

Во время соревнований AI мы достигли максимального ранга 8 и закончили сезон на 26, используя следующие стратегии. Некоторые из этих уловок были настолько умными, что мы почувствовали вдохновение поделиться ими.

Для начала самая важная стратегия - предотвратить столкновение дружественных кораблей. API Two Sigma намеренно не включал предотвращение столкновений при навигации к планетам, поэтому в стандартный API были внесены изменения. Чтобы определить, столкнутся ли два корабля, потребуется некоторый расчет. Основная идея состоит в том, чтобы придумать уравнение, которое находит расстояние между двумя кораблями как функцию времени (время эквивалентно поворотам, но в непрерывной форме).

Далее нам нужно выяснить, как ship1_x и ship2_y меняются со временем. Это можно сделать, зная скорость судов.

Теперь замените положение всех кораблей приведенным выше уравнением в соответствующих терминах.

Чтобы предсказать, столкнутся ли корабли, нам нужно определить, в какое время D будет минимум. Минимум D будет находиться в то время, когда два корабля находятся ближе всего. Для этого мы берем производную D по t (обороты / время). Мы делаем это, решая, когда t равно нулю.

t - время, когда корабли будут в ближайшей точке. Если расстояние меньше фактора фаджа (около 0,5 единицы), то произойдет столкновение корабля. Зная это, мы можем изменить угол нашего корабля, чтобы предотвратить столкновение.

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

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

Какая из планет имеет самый низкий приоритет в нашей очереди приоритетов, так это планета, на которую нападает корабль. Если планета заполнена, планета удаляется из списка приоритетов планет, или если вражеские корабли приближаются к дружественным пристыкованным кораблям, планета снова добавляется в список приоритетов планет. Это дает простой способ эффективно перемещать каждый корабль, чтобы ваши пришвартованные корабли были в безопасности, а планеты, выбранные вашими кораблями, были лучшими.

Определение боя или бегства - это когда ваши корабли должны атаковать или убегать. Это делается путем сложения всех ближайших вражеских кораблей и дружественных кораблей в предложенном радиусе. Разница между ближайшими врагами и ближайшим другом определяет, должен ли ваш корабль бежать или атаковать. Куда должен бежать ваш корабль? Наше решение - убежать на 180 градусов от среднего числа всех ближайших вражеских кораблей. Это было бы похоже на отлетание отрицательно заряженной частицы от набора других отрицательно заряженных частиц.

Это наш секрет того, как мы получили максимальный рейтинг 8 и закончили сезон на 26. А благодаря Two Sigma за создание Halite это был потрясающий опыт обучения!

P.S. Мы внештатные программисты, специализирующиеся на веб-приложениях для стартапов. Вы можете посетить нашу компанию aescru по адресу aescru.com. Мы всегда в поисках работы и следующего большого дела!

Авторы Джеймс Джонс и Бен Бернс.