Небольшая история про участие в одном из 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
