Пришло мне письмо: «Приглашаем на Russian AI Cup и CodeTanks!». Давно уже хотелось поучаствовать, пошел регистрироваться. Форма на удивление была несложной, а вот полученное письмо не обрадовало ((((

В этот день всё закончилось на регистрации, т.к. времени было 0:27, а утром на работу. Решил на выходных посидеть поизучать и написать алгоритм.

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

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

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

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


Алгоритм такой был не супер хорош, но уже показал неплохие результаты.

Все было бы хорошо, если была бы стабильность в играх, но как видно по графику — то первые, то последние места.

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

Эти изменения положительных результатов не дали, наоборот результаты стали хуже.

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

И в зависимости от того в какой четверти я нахожусь применять определенные правила для выезда из углов и отъезда от краёв.



Тем самым победил проблему с тем, что бы танк у краёв не тратил много времени на разворот.

(на графике падение — это 1 оптимизация, а после него взлёт это вторая)

Опять небольшой анализ. И стало понятно, что от краёв то я уворачиваюсь, но пока это делаю ни на что другое не реагирую. И тут возникла кардинально новая идея. Забыть про старый алгоритм и написать новый, секреты которого я опубликую после окончания соревнования, но графики готов показать сейчас.

Последний рост, как раз связан с заливкой новой стратегии. Из 14 игр была 1 игра в которой я занял 4 место, 2 игры, в которых я занял 3 место, 1 игра в которой я занял 2 место и 10 игр в которых я стал лидером, но к моему разочарованию я понял, что в выбранном алгоритме рейтингования игроков есть просчет. И тут с написания алгоритмов я
перешёл на изучение выбранной системы рейтингов. Из документации выяснилось, что они используют систему рейтингов Эло, побежал читать.
Ага оказывается эта система используется для расчёта относительной силы игроков в играх, в которых участвуют двое, например шахматы. Копаем глубже, цитаты не буду приводить — многабукаф. Но смысл заключается в том, что эта система не учитывает резко изменившуюся спортивную форму игрока в конкретный момент, а это значит, что резко улучшив алгоритм управления танком вы все равно будете топтаться около ближайших соперников, а учитывая, что рейтинг увеличивается при том, что танк набирает больше, чем спрогнозировала система, а прогноз у системы всегда будет максимальным т.к. все противники по силе находятся рядом, то и рейтинг сильно расти не будет.

Самое обидное то, что это я прочитал за пару часов до начала первого раунда соревнований, а в него из песочницы проходило всего 900 алгоритмов. И я тут же быстренько метнулся создавать новый аккаунт, куда залил свой алгоритм, но не хватило 1 боя!, что бы попасть в проходные 900 мест.

При этом как всегда администрация, на посты в их блог ничего толкового не отвечала. И спустя 3 дня, в тот момент когда я писал эту статью, они выпускают обновления к своей системе рейтингования! Где они признают мягко скажем, несовершенство выбранной системы:
Что это меняет для участника? Как было замечено, если вы провели множество боев с плохой стратегией, то даже послав новую очень крутую стратегию, то сразу больших плюсов в рейтинг вы не получите и вам придется постепенно возвращаться в число лучших игроков, что, на самом деле, происходит достаточно медленно. Новая функция позволит вам увеличить разброс изменений рейтинга.

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

В выводе стоит поблагодарить организаторов за то, что они предоставили шанс поучаствовать в хороших соревнованиях, и обматерить тех, кто выбирал систему рейтингования игроков. Однако сделав скидку на то, кто является организатором, то на таких не ругаются, а просто относятся с пониманием. Так что просто спасибо.