Танковые маневры на Russian AI Cup

Небольшая история про участие в одном из IT-конкурсов Mail.ru group.

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

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

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

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

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

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

    size_t selected_tank = all_tanks.size();     for(size_t i = 0; i < all_tanks.size(); ++i) {              // перебираем танк из списка         Tank tank = all_tanks[i];         if (!tank.teammate() && tank.crew_health()) {           // в свои танки стрелять не будем :) и в убитые тоже             double angle_to_enemy = fabs(self.GetTurretAngleTo(tank)); // найдем модуль угла от башни до танка             if (angle_to_enemy < min_angle_to_enemy) {          // выберем минимум                 min_angle_to_enemy = angle_to_enemy;                 selected_tank = i;             }         }     } 

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

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

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

          if (self.GetDistanceTo(all_tanks[selected_tank]) < MIN_DISTANCE_FOR_PREMIUM_AMMO || self.premium_shell_count() > 2 || all_tanks[selected_tank].crew_health() < 35 || all_tanks[selected_tank].hull_durability() < 35 ){                move.set_fire_type(PREMIUM_PREFERRED); // если угол невелик, то выстрелим           }           else{                move.set_fire_type(REGULAR_FIRE); // если угол невелик, то выстрелим           } 

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

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

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

       if( self.GetDistanceTo(640,400) < 50 || last_tick_stright_move + 60 < world.tick() && all_shels.size()){          move.set_left_track_power(1.0);         // если угол не больше 30 градусов          move.set_right_track_power(1.0);        // поедем максимально быстро вперед           if( last_tick_stright_move + 80 < world.tick()){                last_tick_stright_move = world.tick();                counter_tick_straight_move++;           }         } else if (angle_to_center > MIN_ANGLE) {         // если угол сильно положительный,          move.set_left_track_power(1*mod_l);      // то будем разворачиваться,          move.set_right_track_power(0.5*mod_r);        // поставив противоположные силы гусеницам.        } else if (angle_to_center < -MIN_ANGLE) {  // если угол сильно отрицательный,          move.set_left_track_power(0.5*mod_l);         // будем разворачиваться          move.set_right_track_power(1*mod_r);     // в противоположную сторону.        } else {          move.set_left_track_power(1.0*mod_l);         // если угол не больше 30 градусов          move.set_right_track_power(1.0*mod_r);        // поедем максимально быстро вперед           counter_tick_straight_move++;           if(counter_tick_straight_move > 30){                last_tick_stright_move = world.tick();                counter_tick_straight_move=0;           }        } 

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

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

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

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

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

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

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

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

Публикуется по просьбе shulyakovskiy