Танковые маневры на 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
Поделиться публикацией

Похожие публикации

Комментарии 85
    0
    Во второй раунд проходят первые 45 мест в песочнице, без учета уже попавших в него из первого раунда.
    Еще 34 часа есть, чтобы в них попасть.
      +1
      Да, это так, но выложили они этот коммент в момент когда я писал статью.
      0
      А от пуль по какому алгоритму уворачиваетесь?
        0
        Анализирую 2 угла:
        — между центральной линией проходящей через танк и пулей
        — центральной линией пули и моим танком

        В зависимости от знака полученного при разности этих углов выстраиваю свой путь
          0
          Согласно их правилам, такое вот обсуждение квалифицируют по пункту:
          3. Права и обязанности сторон
          3.2 Участник конкурса обязан:
          3.2.6 Выполнять Конкурсное задание самостоятельно без привлечения третьих лиц.

          за что, собственно забанили мой аккаунт так как код был похож на код другого игрока… Негодовал, но… Обыдно, если честно, я на 3й день был на 25 месте в рейтинге, хотя потом скатился до 300, в результате «улучшений» =(
            +1
            Да в ходе улучшений и я не раз натыкался на то, что стратегия становилась хуже и хуже. А банить только за то, что похож код я не поддерживаю.
              –1
              Чтобы плохие изменения не коснулись основного аккаунта, я создал второй :) В результате эта сволочь влезла в топ 900 и не смогла оттуда вылезти до окончания соревнований даже при выставлении тупой стратегии (стоять и не стрелять) -> бан.

              Но идею банить за то, что код похож я поддерживаю. Вот почему запрещено вернуться из бана со своей стратегией с 1 аккаунтом и попробовать попасть в топ 45 для меня загадка.
                0
                Полностью поддерживаю, за такое можно банить. Это мухлёж чистой воды.
                А вот когда реально не за, что банят людей за похожесть алгоритма — это обидно.

                А вот секрет состоит в том, что надо залить плохую стратегию и поставить галочку изменчивость, тогда резко пойдешь вниз. Ну а если тебя не смогли и при этом высадить из топ 900, то тогда и банить незачем — это значит, что ни кому не интересно играть.
                  0
                  Это было перед первым раундом — тогда галочки не было.
                  На самом деле в моем случае нужно было на мыло написать, чтобы второй аккаунт убрали. Но я почему-то понадеялся, что аккант успеет выйти за пределы топ 900.
                    0
                    За похожесть алгоритма никого не банили. Большинство банов была сделана автоматизировано скриптом на основании посимвольного совпадения исходных текстов стратегий. На избранные подозрительные случаи указали участники в комментариях, все такие стратегии были просмотрены вручную и забанены только при очевидном совпадении кода (с точностью до мелких исправлений). Конечно, пустые стратегии и копирующие официальный QuickStart не банились, так как совпадение кодов в данном случае ничего не доказывает.

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

                      Что опять доказывает нежелание сделать все справедливо.
                0
                Банили за идентичный код и код, очевидно полученный методом ctrl-c ctrl-v с мелкими правками. Например, участник 0xy был в самом деле забанен — код, посимвольно совпадающий с Вашим, был найден еще у 8 пользователей.
                  0
                  С моим у 8-ми? Это уже интересно, а можно в личку список таких аккаунтов? Или вы сейчас про 0xy?
                    0
                    Это ответ пользователю 0xy. Вы можете написать на support@russianaicup.ru, побайтные совпадения с кодами участника Nikolas тоже имеются.
            0
            У меня хорошо заработало уворачивание, когда стал поворачивать танк перпендикулярно ближайшему врагу, дуло которого направлено в область рядом со мной. По моим наблюдениям, топы делают аналогично.
            +3
            И я тут же быстренько метнулся создавать новый аккаунт, куда залил свой алгоритм


            А вы, видимо, до чтения правил не дошли, потому что там есть пункт о запрете создания нескольких аккаунтов.
              0
              Это было не для того, что бы выиграть, а для того, что бы проверить правильность моего предположения, по поводу рейтингования.
                +1
                В любом случае, правила есть правила, и нарушать их по каким-либо причинам не очень хорошо
                  +6
                  т.е. делать заведомо неправильную систему рейтингования хорошо? Ну и в общем сами же организаторы меня на это подтолкнули ;)
                    +1
                    Если бы кроме вас и организаторов никого не было, то ок. Но вы, вполне возможно, кого-то незаслуженно вытолкнули из топ-900 своими действиями.
                    Организаторы, кстати, всячески отлавливали дубли аккаунтов. Вам просто повезло.
                      0
                      Да ни кого я не выталкивал.
                      1. В топ 900 я НЕ вошел!
                      2. После проведения эксперимента в дубль была загружена тупая логика которая ни куда не вышла.

                      А продолжаю я работать со своим основным аккаунтом. Так, что не переживайте. И по поводу повезло/не повезло. Я играю не ради призов, а ради интереса, в самом начале поста написал про то, что это была мечта поиграть, а не мечта выиграть.
                        0
                        Ээ… ну пардон, упустил из виду, что в топ-900 вы не вошли. Но правила нарушать все равно не стоит.
                        Про повезло: я имел в виду, что вам повезло, что вашего дубля не засекли, т.к. администрация активно их выискивала и банила оба аккаунта.
                      0
                      Вообще, я тоже изначально с такой системой был не очень согласен. Самому пришлось долго подниматься. Но правила для всех одинаковые.
                        0
                        эло рейтинг рассчитан на тех, кто внимательно анализирует задачу, испытывает решение на своих тестах и вконце концов посылает оптимальное решение.

                        Похожая система на всяческих студенческих олимпиадах — побеждают те, кто сделал меньше попыток и сдал раньше.
                          0
                          Вы все правильно говорите, но все равно рано или поздно стратегия дойдет до такого рейтинга, какого она уровня. Некоторые видят проблему в том, что это долго происходит. В том числе и я, поднимавшийся с одной стратегией 5 дней, потому что сначала послал что-то не очень хорошее. В каждом бою мой рейтинг поднимался на 5-10. Это очень долго.
                            0
                            Только, учитывая что система создает в песочнице 18-20 боев за сутки, «рано» дойти до рейтинга своего уровня не получится, скорее будет «поздно».
                            0
                            В рамках студенческих олимпиад — это наверно адекватно. А в рамках таких соревнований нет, более того, если это не было озвучено.
                              0
                              тут как бы испытать решение можно было только в бою. Локальный запускатор тестирует только с 2 танками. А заливать на сайт и каждый час откатывать — это то еще удовольствие, тем более что никак пометить последнюю боевую стратегию нельзя
                                0
                                Поддерживаю!
                                Комментарий к залитой стратегии уж точно бы не помешал и галочка активной стратегии тоже.
                      0
                      Вы знаете, я его искал, этот пункт, когда занимался тем же самым, а именно хотел проверить как работает рейтинг. И прочитав их большую пдф-ку так и не нашел там этого пункта. Администрация сказала, что вывешивала это на главной. Когда регистрировался, тоже не видел, потом заходил только в профили танков.

                      В итоге, конечно, забанили. Хоть было обидно. Так как один аккаунт дополз до 500, другой был на 300 с чем-то на момент начала первого раунда. Но правила есть правила, и то, что я не увидел пункта в них — моя ошибка.

                      Но обидно, вудь было интересно участвовать. :)
                      0
                      Несколько дней назад пытался на этом сайте зарегистрироваться — безуспешно. Пишут, мол, какая-то ошибка, свяжитесь с нами. Попытался найти контакты — нигде нет. Весьма саркастичные сообщения. Задал вопрос в блоге Mail.Ru Group — молчат. Что ж, не судьба.
                        0
                        Да и ты не первый, кто на это жалуется. Регистрация действительно работала отвратно :(
                        +2
                        Пост не понравился.
                        А у меня танк пытается заехать «в бок к противнику», высчитывает врага по совокупности критериев, умеет двигаться жопой и так далее (до фига вроде всего умеет, но результат конечный не намного лучше — russianaicup.ru/profile/recompileme ). Что обидно — в топ 900 1 из танков таки вошел (да я тоже жухлил с мультиаккаунтами) но в 1 раунде закономерно вылетел(

                        Было бы здорово прочитать про прогнозирование области в которую попадет снаряд, про умный пасфайндинг, уворачивание. Я таки погряз в грешной геометрии, atan2 всяких, и не смог понять как просчитать пересечется ли пуля с моим танком, например, и как определить куда двигаться. Да и дедлайн по проекту — вынудили забить на конкурс. Поэтому выкладываю свой говнокод — может поможет кому-ть: pastebin.com/fwTYp59W
                        Было бы интересно услышать критику и примеры кода от таких же сдавшихся
                          0
                          Спасибо за критику. После завершения соревнований, я выложу, как именно я прогнозирую попадание полу в мой танк, в танк противника, выбор направления движения и все гипотизы которые отпали в ходе улучшений и разработок.

                          Так же если бы вы внимательнее читали, то танк на след. день после окончания 1 раунда вошел в топ 900 и поднялся довольно высоко. мне нехватило 1 боя, что бы попасть в топ 900.
                            +1
                            Вот когда выложите — тогда это будет очень интересный пост. Пока же это пост о том, как я не вошел в топ 900.
                              0
                              Ну собственно, да! Я писал именно про то, как и почему я не вошел в топ 900.
                            0
                            Ну я вон прогнозировал тупо проверкой пересечения прямой пули с отрезками танка. Взял только размер танка с запасом (квадрат больше реального)
                            Для путей юзал uniform cost search (A* смысла не увидел делать, а ucs и так учитывает «опасность» waypoint'ов когда прокладывает маршрут)
                            Для сглаживания маршрута сделал притягивание точки к двум соседним и её предыдущему положению градиентным спуском. А вообще есть пачка алгоритмов по path smoothing.
                            С опасностью зоны много мудрил, но, в конце концов все удалил и сделал тупо среднее арифметическое расстояний до танков + большой штраф тем зонам, где уже есть танки. Таким образом танк выбирает позицию чтоб не попасть под перекрестный огонь.
                            Выстрелы тоже с учетом скорости моей, противника и моей угловой скорости.

                            До obstacle/collision avoidance не добрался. Оно, вроде, не очень и критично тут. Хотя запилить танку «усики», проверять их пересечение с другими танками и, исходя из этого, корректировать скорость гусеницы не сложно. Ray casting/tracing называется, вроде.

                            Что-то такое, вкратце. До 102 места дошел без всякий пасфайндингов, потом доулучшался до 500. На данный момент идет вверх график, но уже хз какое реальное место. Раунд 2 стартанул.

                            Я пока не вылетел… осталось пару дней подождать :D
                            Но свой код постить не буду даже под дулом пистолета. Такую гремучую смесь дефолтного ооп и моей процедурщины на питоне2 выставлять стыдно..) Да и чёрта с два там кто-то что-то поймет.
                            0
                            Забив в гугол www.google.ru/webhp?q=GetTurretAngleTo можно найти много интересного, например вот такого:

                            public static class WorldExt {
                                    public static IEnumerable<Tank> EnemyTanks(this World world) {
                                    // if non-NightmareZ's live tanks exists...
                                    if (world.Tanks.Any(tank => !tank.IsTeammate && !tank.PlayerName.Contains("NightmareZ") &&tank.CrewHealth > 0 && tank.HullDurability > 0)) {
                                    // if non-kirjushyk's live tanks exists...
                                    if (world.Tanks.Where(x => !x.PlayerName.Contains("NightmareZ")).Any(tank =>!tank.IsTeammate && !tank.PlayerName.Contains("kirjushyk") && tank.CrewHealth > 0 && tank.HullDurability> 0))
                            


                            Судя по всему, чей-то бот, который не стреляет в своих и служит для поддержки. Источник pastebin.com/exw7ryF1
                              0
                              несмотря на кажущуюся парадоксальность — если запустить например 5 ботов с одной стратегией — рано или поздно они встретятся в одном бою — так как рейтинг у них примерно одинаковый. Так что такая тактика вполне оправдана хотя и нарушает правила
                                –1
                                Такие аккаунты должны баниться, а тут игроки прошли в первый рануд и продолжают играть. Видать свои люди…
                                  +4
                                  Правила не нарушает. Правилами никак не регламентировано в кого стрелять, а в кого нет.

                                  PS Я сам участвовал. Прошел во второй раунд. Подобных условий не делал (нет исключений по имени игрока). Забил из за изменений в правилах посреди соревнования.
                                  russianaicup.ru/profile/beat
                                    0
                                    Эй, мужик! Я за тебя болел!
                                    (не сарказм — просто из того же института и ник знакомый :))
                                      0
                                      О, спасибо! Очень приятно.
                                        0
                                        Давай, возвращайся! Посмотрим кто кого: выпускники vs студенты. Преподаватели уже выбыли к сожалению :)
                                          0
                                          А кто из наших преподов участвовал?
                                            0
                                            Пока знаю только одного — себя :)
                                            Преподаю второй год как раз интеллектуальные системы. Меня забанили, так что теперь только болею за студентов своих и всех кто из института нашего.
                                              0
                                              Почему забанили?
                                              Можно ссылку на профиль на russianaicup.ru/?
                                                0
                                                Проводил тестирование стратегии на отдельном аккаунте, чтобы в рейтинге не проседать. Ссылка вам ничего не даст russianaicup.ru/profile/xcam. Лучший результат — 40 место в рейтинге. Могу выложить последнюю стратегию на новый акк и, пока меня еще раз не забанили, проведем бой :)
                                                  0
                                                  Предлагаю в личку.
                                  0
                                  по ссылке выше такой код — var expected = new Point(tank.X + tank.SpeedX * time, tank.Y + tank.SpeedY * time);
                                  здесь же не учитывается направление движения и грешный квадрант! Черт, у этой проблемы должно быть изящное решение
                                      0
                                      они договорились не стрелять друг в друга вот здесь www.gamedev.ru/flame/forum/?id=168476
                                      +3
                                      Эээ, то есть я правильно понял, вы решили рассказать как не попали в 900 луших стратегий, и скрываете новую стратегию, так как она «прям ну ваще», кто скопирует-займет первое место? Извините, судя по первой стратегии и тому, что реализовано, меня терзают сомнения в состоятельности такого утверждения. Тогда бы уж ждали окончания турнира, чтобы опубликовать, что-то более интересное чем слегка доработанный код из базовой стратегии.
                                        –2
                                        По окончании соревнования обязательно поделюсь своими мыслями по реализации алгоритма. Конечно же для профессиональных игроков спортивно-компьютерных игр это наверно забавно будет читать, но для любителей будет интересно, путь пройден не маленький и результат есть, так, что тема есть.

                                        P.S. А ваши смутные сомнения пусть и дальше вас терзают. Нет предела совершенству.
                                        +1
                                        Серфя интернеты наткнулся на старый добрый habrawars.appspot.com/ =) Вот даже встал вопрос, а чой-то эту штуку забросили? Может хабр свой турнир замутит?
                                          0
                                          тоже прикольно, жаль что маленький выбор языков и нет возможности работать в офлайне
                                            0
                                            Ты решил теперь во всех конкурсах участвовать? :)
                                          0
                                          а я изначально замудрил сложную систему c делением на сектора(quadtree), расчет весов каждого сектора. но все-равно не получалось пройти в топ-900 поначалу, т.к. танк вечно попадал между 2-3 соперниками и его быстро «выклевывали» из игры. дуэлился он неплохо(уворот от пуль и выстрел с упреждением сделал практически сразу) но вот в таком душматче проигрывал. в итоге заменил эту систему секторов на логику: заехать в самом начале в угол, затем по возможности ездить за бонусами(там была систему учитывающая выгоду бонуса в зависимости от хп и расстояния до него) и конечно же уворачивать от пуль. в итоге пролез на 450(рекорд для меня) место в песочнице. сейчас уже забросил, т.к. в раунд 2 не прошел
                                            +1
                                            А у меня цель определяется примерно следующим алгоритмом:
                                            1) есть список зон дистанций с весом например от 0 до 100 вес равено 0, от 100 до 180 вес равен 1 и тд
                                            2) есть список зон углов например от 0 до 5 градусов вес равно 0, от 5 до 10 вес равен 1 и тд
                                            3) есть танк «подранок» (мало жизни и/или брони) то вес -10, иначе 0
                                            4)…

                                            Потом складываем все веса с небольшими условиями и коэффициентами; сортируем все танки противника по полученным весам. Танк с наименьшим весом будет более выгодной целью.

                                            PS Вообще могу пост написать о своей стратегии (http://russianaicup.ru/profile/beat). СтОит или нет? Заминусуют?!
                                              0
                                              ну у меня примерно также было, только вес сектора складывался из расстояния до него, угла поворота, сколько на него нацелено других танков и т.д. само собой потом по весам сортировались сектора, танки, бонусы. но почему-то не взлетело с секторами. не знаю, может где-то допустил ошибку. я думаю стоит написать, 126 место это довольно-таки неплохо. интересно ж будет послушать
                                                0
                                                Вообще-то я стабильно держался в районе 55 места в песочнице, как-то даже побывал в ТОП 50, в 1 раунде занял 82 место. А сейчас 126 место из-за того, что я прекратил доработки бота. Причиной является мое недовольство изменениями в правилах и в системе начисления рейтинга прямо посреди соревнования.
                                                  0
                                                  :) Очень знакомо, так же поделил поле на сектора, и начислял очки каждому сектору в зависимости от многих параметром, бонус, танки, препятствия, расстояние, необходимый угол поворота до зоны, пролетающие пули и прочее. То ж результат не самый крутой, лучшее что было в начале дошел до 120-130 мест, а потом к первому раунду уже был где в 300-400, первый раунд не прошел, ну и прекратил глобальную доработку. По мелочи добавляю моменты, хотел глобально переделать стратегию, когда вышла новость о дополнительных 45 участниках во второй раунд, но по времени не получилось засесть. Первый раз участвую в подобных турнирах, раньше только робокод щупал минут 30.
                                                  0
                                                  По поводу поста интересная идея. Я тоже после соревнований хочу описать свою стратегию, ее минусы и плюсы. Можно было бы скооперироваться и написать один пост с обзором 2-х стратегий )
                                                    0
                                                    кстати как определялась коллизии между танком и пулей? я заменял танк на окружность с радиусом меньшего размера танка * 0.5 и пересекал с отрезком. не точно но в большинстве случаев работало нормально. иногда бывали случаи когда можно было выстрелить, но выстрела не происходило. хотел заменить на проверку прямоугольника и отрезка, но показалось что большого профита это бы не дало и решил оставить по-прежнему.
                                                      0
                                                      В основе лежит следующий алгоритм.
                                                      Я получал прямоугольную область которую занимает танк (по его координатам, размерам и углу относительно оси ординат). У прямоугольника высчитывал диагонали.
                                                      Далее строил линию полета пули и смотрел, пересекается ли она с диагоналями прямоугольника.
                                                        0
                                                        Но по диагоналям вы можете определить лишь факт попадания (сам так изначально делал).
                                                        Если проверять пересечение луча (если увеличить размеры танка на размер снаряда, то, я думаю, вырождение прямоугольника снаряда до точки — уместно) и четырех прямых, составляющих прямоугольник объекта, то можно получить точку столкновения, а по ней время до столкновения.
                                                          0
                                                          Я делал по-другому. Чтобы учесть размеры снаряда, я для каждого из углов прямоугольника проверял пересечение линии полета пули и окружности с центром в углу прямоугольника и радиусом равным половине меньшей стороны пули.

                                                          То есть чтобы проверить пересекает ли линия выстрел танк противника, нужно было сделать 6 проверок: 2 пересечения с диагоналями танка + 4 пересечения с углами танка (окружностями).
                                                            0
                                                            По-моему, четыре проверки пересечения луча и отрезка прямой выполняются быстрее и точнее, чем ваш вариант. Впрочем, дело ваше.
                                                              0
                                                              Да, но мне не хотелось увиличивать размеры прямоугольника (на половину меньшей стороны пули), так как прямоугольники (а так же углы и диагонали) для танков расчитываются один раз за тик в самом начале метода Move, а используются они не только для проверки помех для выстрела, но и для, например, расчета стрельбы с упреждением.
                                                  +3
                                                  Первый алгоритм который я придумал

                                                  Я, конечно, дико извиняюсь, но эти банальные несколько строчек приведены в разделе «Быстрый старт».
                                                    0
                                                    «угол между прямой проходящей, через центр одного объекта и прямой соединяющей центры объектов угол между которыми надо высчитать» — вот ну совсем не понял, что имелось в виду
                                                      0
                                                      да, описано действительно непонятно. имелось ввиду есть две функции: получить угол поворота башни и угол поворота самого танка. все углы вычислялись относительно отрезка, соединяющего два танка.
                                                        0
                                                        Угол можно найти только между 2 прямыми. Одна прямая это прямая проходящая через центр танка и параллельно его длинной стороне. Вторая прямая это прямая соединяющая центры объектов. А угол считается от первой прямой ко второй и находиться в пределах от минус 180 до 180 градусов.
                                                          0
                                                          зачем мне это объяснять?! :) я пытался попроще объяснить человеку, который api танков не видел
                                                            0
                                                            вы все конечно правильно написали. но я думаю как я описал «попроще» и так понятно. не? по крайней мере в API было описание такое, вроде все поняли что имелось ввиду
                                                              0
                                                              Да наверно так понятнее, особенно когда есть возможность проверить внутри среды.

                                                              Но мне более приятно читать про угол, когда указаны обе прямые между которыми он построен. Особенно учитывая, что играет роль еще и направление этого угла (расположение отрезков относительно друг друга).

                                                              P.S. Промежуток от -180 градусов до 180 градусов
                                                        0
                                                        Ну вообще было — бы интересней создавать алгоритмы для управления небольшими отрядами танков =)
                                                          0
                                                          Собственно 2 раунд заключается в том, что у каждого из 3 игроков по 2 танка в комманде. В финале по 3 танка у 2-х игроков
                                                            0
                                                            Эх жаль я не успел :( так хотелось. Пропустить такое веселье :(
                                                              0
                                                              Вы ничего не пропустили. Песочница доступна для всех желающих и на текущий момент поддерживает два вида боев: 6 участников по 1 танку и 3 участника по 2 танка.
                                                          0
                                                          В самом деле в Песочнице рейтинг изменяется не мгновенно. Как Вы правильно заметили результаты боев зависят не только от качества стратегий, но и от фактора удачи, который нивелируется при многократных боях. В частности, инертность рейтинга в Песочнице позволяет ему в большей степени отражать силы противников, чем если бы он был сильно подвержен кратковременным победам или поражениям. Как и сообщалось, из-за большего количество участников нами была поднята планка прохождения в Раунд 1 с 600 до 900 участников. Посмотрев историю видно, что даже крайне неоптимальные стратегии, занимающие 1500 место из 1850 на момент окончания Раунда 1 имели отставание от 900-го места всего 280 баллов. За победу в бою давалось 10-20 баллов, т.е. при значительном превосходстве стратегии хватало примерно двух суток (скинем на неудачу) на поднятие в Топ-900. Вот примеры трех участников из середины последней проходной страницы (на местах 850, 851, 852): russianaicup.ru/profile/ilya.korovin, russianaicup.ru/profile/vergili88, russianaicup.ru/profile/dark_ai. Хорошо видно, что на рывок в баллов 200 им в самом деле надо было примерно двое суток (смотрим в районе 7-10 числа). Дальнейшее их участник в чемпионате показывает, что их стратегии в самом деле оказались во второй половине результатов Раунда 1, то есть это скорее типичные примеры заметных улучшений, чем запоздалые лидеры Чемпионата. Заметим, что не случайно Песочница была открыта почти две недели до Раунда 1.

                                                          Касательно галочки увеличения изменчивости рейтинга – ее необходимость была обусловлена 45 вайлд-кард местами из Песочницы в Раунд 2. Таким образом были существенно поддержаны участники, которые не прошли в Раунд 1 по каким-то причинам, но были готовы побороться за место в Раунде 2. Идея с вайлд-кардами была подсказана в комментариях и большинству показалась удачной. В условиях сжатого срока (примерно 5 дней) между раундами надо было предоставить дополнительный механизм ускоренного изменения рейтинга, так как существующий мог не позволить сильным стратегиям правильно оценить их в столь сжатые сроки.

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

                                                          Маловероятно (и мы не слышали о таких случаях), что эти и другие фиксы правил повлияли существенным образом на алгоритмы стратегий, они не изменили цели игры, API или что-то еще. Изменение параметров двух невостребованных типов танков как и планировалось не привело к массовому их использованию в Раунде 2, а лишь несколько увеличило вариативность стратегий к Финалу. Будут ли эти типы танков востребованы – непонятно, но абсолютно точно до настоящего момента эти изменения не оказали каких-то существенных влияний на игру.

                                                          Небольшие улучшения правил, неприводящие к существенным катаклизмам, результат того, что жюри прислушивается к фидбеку участников и делает возможное, чтобы сделать игру интересней и правильней. Кстати, формально, право изменения правил закреплено в соглашении и объявлении о конкурсе.
                                                            0
                                                            Да, вы всё верно говорите.

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

                                                            Анализируя несколько аккаунтов в преддверии начала первого раунда я увидел, что многие могли бы пройти в топ 900 со своими стратегиями, но в какой то момент «забили» т.к. не стали разбираться почему так медленно их алгоритм идёт вверх.
                                                            Так же на вопросы о скорости роста и падения рейтинга на вашем сайте внятных ответов на тот момент не было: вот тут есть много обсуждений, где прямо говорили о том, что без создания нового аккаунта в топ 900 не пройти.

                                                            И тут мне не очень понятен выход из этой ситуации. Почему то сразу после первого раунда организаторы то ли понимают, то ли прогибаются под давлением комментариев и вводят тот самый флажок изменчивости рейтинга, который спасает всех тех кто затерялся в низах рейтинга из-за того, что не смог за короткий срок набрать необходимое кол-во балов. Но они не учитывают всех тех, кто осознав глупость подсчета рейтинга ушел раньше. Так же организаторы ставят под сомнение большую часть алгоритмов которые прошли в первый раунд, но дают только 45 мест из песочницы, как бы тоже не очень логично, если уж все по правилам и строго, то так надо было идти и до конца, ни каких 45 мест, ни какой изменчивости. Ну или соглашаться с там, что да рейтинг выбран не правильно и организовать еще один раунд типа 1.2 в который бы отобрали еще раз 900 лучших и по результатам песочницы и потом уже отобрать 300 лучших из лучших, которых в конечно итоге пустить во второй раунд, думаю результаты в раунде 1.2 многих бы удивили.

                                                            Ну и по хорошему, можно было бы держать всех в курсе мыслей по вводу галочки. Не все же такие нехорошие, как я. Большинство ведь понимают, что правила нарушать нельзя и расстраиваются, что им не предоставили возможность нормально показать на, что их стратегии способны. А еще многие такие, как я решили выбиться вопреки правилам, но их забанили как читеров, без всяких разбирательств. Хотя не факт, что они были именно злобными читерами пытающимися занять все первые места вытеснив других потенциальных победителей.

                                                            Ну и конечно баны без предупреждений и разбирательств очень похож на репрессии со стороны тоталитарного правительства. И как писали выше 1 извинившийся — это примерно 100 человек которые умышленно нарушали правила и покорно согласились с баном, а все остальные? У них кто то спросил зачем они это делали? Фидбек у них собрали? Об этом ни слова ни кто не говорил. Говорили только про апелляцию банов, но дабы ей было воспользоваться невозможно то банили за 30-40 минут до начала раундов зато статистика апелляций чистая была, опять можно сказать, что всего 1 человек написал, за исключением всех тех, кто опустили руки т.к. соревнования то уже начались и апеллировать смысла нет.

                                                            Так, что все было бы хорошо, если бы не все так плохо.
                                                              +1
                                                              Сразу хорошую стратегию выкладывать было не обязательно. Примеры выше показывают, что люди проходили в топ-900 с места около в середине второй тысячи из 1850. Их стратегии обладали совсем невысоким рейтингом незадолго до начала Раунда 1 и существенным количеством сыгранных боев.

                                                              Статистика посещаемости показывает, что интерес аудитории только рос к Раунду 1. Вероятно, отдельные отчаявшиеся люди и были. Но я не уверен, что по графикам можно точно сделать вывод, что люди забили. Тем более не очевидны причины. Внятным ответом здесь являются скорее примеры — история показала, что люди проходили в Раунд 1, улучшая так себе стратегии незадолго до раунда. Кстати, в том же обсуждении приводились расчеты, подтверждающие положение дел russianaicup.ru/p/sandbox#comment-984

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

                                                              Стабильность результатов при тестировании раундов очень неплохая (внутренние тестирования это подтверждают). Мы очень постарались сделать так, чтобы во время тестирования прошло максимальное количество боев. Получилось примерно достичь планки 200 боев в час, что очень неплохо. Ваше предложение с раундами 1.2 значительней меняет сетку и меняет расписание чемпионата, а это крайне нежелательно.
                                                              Утвержденный вариант 600 -> 900 + 45 не менял значительно сетку и расписание и давал участникам еще неделю на доработку, что не выглядит даже более удачным решением, чем предложили Вы.

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

                                                              В целом, спасибо за фидбек. Мы очень стараемся сделать интересное соревнование, было написано много кода. Полагаю, с накоплением опыта многие грабли исчезнут. Надо понимать, что такое соревнование проводилось впервые (например, тот же рейтинг на синтетических данных и без взгляда изнутри с точки зрения одного из 2000 участников тестируется с трудом), а соревнование нетипичное.
                                                                –3
                                                                Многабукаф. Коммент претендует на отдельный топик.
                                                                Основную мысль понял так.

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

                                                                А по поводу написать и жирных букв я уже писал, что ни разу не видел этого. И еще раз повторю, что сообщение о том, что у меня 2 аккаунта я написал на хабре и через 10 мин после поста откликнулся один из организаторов, который прокомментировал пост и ни слова не сказал, про то, что надо удалить второй аккаунт о, чем вы очень сильно просите прямо на главной странице! Перестаньте это уже игнорировать! Была бы заинтересованность все по нормальному разрулить нашли бы выход.

                                                                P.S. Организаторам всегда нужно быть более терпеливыми и рассудительными, чем участникам.

                                                          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                          Самое читаемое