Разработка ИИ, новости и собственные пробы Опции

[Ахинея]

Russian AI Cup — соревнование по программированию искусственного интеллекта

Недавно мы столкнулись с вот этой статьей и два дня пролетели как в тумане

Russian AI Cup — это новая инициатива команды разработки проекта Одноклассники в рамках соревнований IT-направленности. В этом чемпионате участники состязаются в умении писать искусственный интеллект на примере игровых стратегий. Организаторами являются ООО «Одноклассники» и национальный исследовательский Саратовский государственный университет. (вы сейчас спросите, а че сюда саратовский гос примазался? а все легко - отбор на 1/4 ЧМ по программированию проходит именно там, и создание искусственного интеллекта для танков - это традиционная разминка данного этапа ЧМ, их фича, так сказать. 1/2 проходит в Питере, а финал в Китае(хз где, т.к. туда мне так и не удалось прорваться)).

Чемпионат первого Russian AI Cup называется CodeTanks. Вам предстоит программировать искусственный интеллект для танков. Ваши стратегии будут сражаться между собой в Песочнице и чемпионате. Вы можете использовать любой из языков программирования: С++, Java, C#, Python или Pascal. Песочница уже открыта. Удачи!

К участию в соревновании приглашаются как начинающие программисты — студенты и школьники, так и профессионалы. Не требуются никакие специальные знания, достаточно базовых навыков программирования.
Расписание чемпионата
Песочница: с 29 октября по 2 декабря открыта для всех желающих
Раунд 1: 10–11 ноября
Раунд 2: 17–18 ноября
Финал: 24–25 ноября

Мы пишем на яве, в целом, программиские знания там особо не нужны... Нужна креативность мышления и логика... Ща у нас уже 17 версия и че-то пока все печально...

[Пастор]

ПЕРЕПОСТ
Небольшая история про участие в одном из 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 алгоритмов то уже прошел! Плюс в этом же посте они изменяют среду существования танков, и их боевые характеристики, что конечно же вызывает шквал, как положительных так и отрицательных эмоций у участников…

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