Как мы слили финал IT-Планеты по программированию

Не мы плохие, а багов много. Разработка искусственного интеллекта для игры “Хоккей” за ~7 часов.

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

Дело в том, что на интересующие нас вопросы мы получали максимум 6 слов, а потом сразу же слышали недовольства о багах, с которыми столкнулись участники. Только один человек написал:

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

Из заголовка статьи понятно, что мы ничего не выиграли. И да, именно “мы”. За конкурсные дни у меня появилось много хороших знакомых, в том числе и Анна (odrus), являющаяся соавтором данной статьи. Также в последний момент мы разговорились со Львом (zadamantiy) и с его разрешения описали участие в финале.

Лично я являюсь участником движения “A Complaint Free World”, но я перевешу свой браслет на другую руку и буду жаловаться, хоть и в шуточной форме, ведь, с другой стороны, таковы условия конкурса и нужно быть хорошим специалистом, чтобы выиграть в нём и совладать с недочётами! Никаких претензий у нас нет, наоборот — большое спасибо!

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

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

Введение

Несколько слов о нас

Илья

Ежегодный участник Russian AI Cup и Mini AI Cup с 2017 года. Также слежу за Codingame и Halite. Особых достижений пока не имею, но многому набрался от других. Для меня главное не участие, не победа, а выложиться на свои 100% и в конце сказать: «Я сделал всё, что мог, реализовал всё, что хотел, применил всё, что знал». Язык программирования Java не знаю. Для меня это уже обычная практика с конкурса на конкурс полностью изучать новый стек технологий.

Анна

Простой студент с небольшим опытом решения алгоритмических задач, но без особого опыта участия в олимпиадах и подобного рода контестах. Конкретно в IT-Планете решила поучаствовать, чтобы проверить свои знания и способности, получить опыт, пообщаться с интересными людьми. Изучала язык программирования Java в университете, но давно не имела практического опыта с ним.

Лев

Участвовал во всяких отборах ICPC, хакатонах вроде «Собери университет 20.35» и «Цифрового прорыва». Ну и по мелочи в каких-то университетских олимпиадах.
Соответственно, у нас университет обычно отправлял много участников на конкурс по sql, но в этом году его не было. Мне предложили поучаствовать в Java, пришлось в достаточно короткие сроки параллельно с сессией разбираться с новым для себя языком. В It-планете до этого не участвовал.

Описание конкурса

Общее положение

IT-Планета — это конкурс для студентов и молодых специалистов из IT-сферы, целью которого является выявление и поддержка способных ребят. Проходит ежегодно с 2007 года. Участие в нём — это шанс проявить себя.

Номинация “Программирование Java” помогает найти практическое применение знаниям, полученным в процессе обучения.

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

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

Международный финал очный. Необходимо было написать AI для игры “Хоккей с шайбой”. Давалось ~7 часов. Приблизительность из-за отсутствия “отмашки” старта и непонятности с обедом. Время было резиновым и аудитории не закрывались, но об этом ниже.

Задание

Задание было разработано специалистами ООО «СимбирСофт». Ниже представлено содержимое .pdf файла (с минимальными правками для статьи), который получил каждый участник.

Критерии оценки

Тоже взято из .pdf файла. Будет использоваться программный код только из класса Algoritm. Алгоритм каждого участника будет прогоняться против всех уровней сложности поочередно. По результатам прогона будут выставляться очки за результаты матча, а также будут начисляться баллы за реализованные возможности в алгоритме.

Основная часть

Подготовка к конкурсу

Илья

Изначально писали, что в финале будет “Промышленная разработка”. Я ожидал обычной работы с базой, разработки GUI. Приложение для учёта чего-либо, например. С горем пополам согласился на финал, ибо был не очень рад тому, что придётся делать. Однако 17 сентября приходит письмо с регламентом проведения финала, а там сообщается следующее: “Имеется компьютерная 2D-игра «Хоккей», в которой по некоторому алгоритму играют компьютерные боты. Необходимо на языке программирования Java реализовать алгоритм, по которому будут действовать персонажи участников“ (на сайте было написано, что задание может быть изменено). В моей голове сразу же вспомнился Russian AI Cup 2014 года. Я обрадовался и понял, что не зря согласился принять участие.

Первым же делом пошел в очередной раз читать статью победителя. В целом я помнил, что там было, но далеко не все моменты были ясны. Дальше отправился на сайт конкурса и прочитал правила. На этом остановился, ведь любая поправка в правилах может полностью изменить всю игру. Я не знал о том, сколько будет физики в их игре, не знал о том, как происходит удар и подбор шайбы и т.д. Игру могли очень сильно упростить, что даже углы не нужны будут. Поэтому я начал ждать…

Ждал и дождался! Днём 27 сентября приходит письмо о проведении вебинара! 28 сентября в 19:00. Это был идеальный день и время для меня. Однако… Однако за 4 часа до запланированного старта пришло еще одно письмо с переносом на 17:00! Письмо о переносе пришло за час до начала… Летел как мог и опоздал на минут 15 (не ожидал, что еще надо будет ставить Flash Player).

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

Записав всё самое ценное, я пошел общаться со знакомыми активными участниками RAIC’a. Привет и спасибо m0rtido, DragoonXen, oreshn1k. Обрисовав ситуацию, стало понятно, что надо хардкодить ифы и ни о каких симуляциях мира за такое время речи и не может идти. oreshn1k поделилась бомбезной книгой “Programming Game AI by Example”, в четвертой главе которой рассказывалось о дизайне AI для футбола. Мне так сильно понравилось написанное в книге, что я решил расписать для себя всю стратегию, которую собирался написать на конкурсе, и совершенно забыл об ограничении на время. То, что я собирался писать, не подходило для этого конкурса…

Моя проделанная бесполезная подготовка доступна на quire (аккуратно, там аж 168 задач. Местами с описанием). Бесполезная для данного конкурса, а в целом это отличная систематизация полученных знаний из книги. Там же я подумал над симуляцией шайбы, чтобы узнавать её месторасположение через некоторое время, над поиском подходящего угла для удара по воротам, логикой передачи шайбы между игроками и кучей всего интересного.

Выше я уже написал, что без понятия, как писать на ЯП Java, поэтому помимо стратегии я занялся изучением синтаксиса языка. В этом мне помог отличный сайт, которым я пользуюсь уже не первый раз — Learn X in Y minutes. Зайдя в IntelliJ IDEA я понял, что писать на ней точно так же, как и на C#.

Вот с такой подготовкой я поехал в Москву.

Анна

Когда узнала о теме финала, первым делом решила повторить геому. А чтобы все это проходило ещё и весело, делала все это с помощью Processing: смотрела примеры от разработчиков, связанные с движением, расчётом углов, скорости и ускорения, а потом практиковалась на своих небольших скетчах.

Время на то, чтобы освежить в памяти какие-то тонкости Джавы, я решила не тратить, потому что задача, как мне показалось, предполагала скорее навыки в написании стратегий и некотором знании математики. Поэтому я решила почитать статью победителя RAIC 2014. Статья была интересная, но не особо полезная конкретно для данного конкурса, потому что физика могла отличаться кардинальным образом, да и времени будет дано намного меньше.

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

В итоге непосредственно перед финалом у меня не было никакой заранее проработанной стратегии: сложно было что-то планировать, когда не раскрыты детали физики игры. Были мысли о том, на что стоит обратить внимание в первую очередь, какие вспомогательные методы написать сразу, но не более того. Я решила, что главное перед финалом — это отдохнуть, выспаться и прийти туда с хорошим настроением.

Лев

[Готовился] Около 16-20 часов. Соответственно, рассматривал геометрию, с которой я, к сожалению, не сильно в ладах. Заранее подготавливал формулы и расчёты, тестировал всё. Оценил область, из которой можно забить в ворота по условиям, данным организаторами на вебинаре, затем написал эмулятор некоторых действий и получил то, как будет выглядеть область при прямой симуляции ударов с разных точек и оптимальной стратегии вратаря. В итоге не пригодилось ровным счётом почти ничего и пришлось писать костыли на костылях.

Распределение времени

Илья

С распределением времени на конкурсах и олимпиадах у меня всегда были проблемы. Я наступил на грабли в третий раз. Еще после первого сказал, что никогда не допущу этого. Вновь засел над одной задачей, долго не переключался на другую.

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

Опомнился на обеде. Понимал, что половина конкурса прошла, а у меня работы на ещё часов 10 чтобы хоть что-то начало двигаться. Было принято решение оставить всё что есть и начать с самого начала. Это были увлекательные последние часы конкурса, когда я перестал грустить и хихикал с поведения своих ботов. Очень быстро начал переключаться с задачи на задачу. Не выходит там — перешел на другую, потом вернулся. Желание было только одно — забить хоть как-то, хоть что-то. Поэтому было напрочь забыто о чистоте кода и ООП, местами оставлены интересные комментарии.

Анна

Сначала я решила разобраться с тем, как вообще работают основные методы в игре: движение хоккеистов, захват шайбы, повороты и пасы. На это я потратила около часа. Также изучила предоставленные данные и методы, которые были у хоккеистов и шайбы. Затем я решила, что неплохо было бы научиться находить угол между двумя объектами (в частности, между хоккеистом и шайбой). С этим у меня возникли большие трудности: сначала я долго разбиралась с методом Math.atan2, а затем пыталась конвертировать полученные данные в систему углов разработчиков. Со всем этим я мучилась до обеда и была очень расстроена тем, что кучу времени потратила на одну небольшую задачу, хотя за это же время могла написать стратегию как минимум для первого уровня.

После обеда я решила более рационально распределять время. Быстренько дописала метод с определением угла, затем написала стратегию для первого уровня. Потом плавно перешла к стратегии для второго уровня, которую применила в итоге и для третьего. Собственно, этим и залипанием в то, как странно ведут себя мои хоккеисты, я занималась до окончания финала. Код получился ужасный, нечитабельный, с кучей if’ов и копипасты, но со своей задачей он более-менее справлялся: мои хоккеисты забивали шайбы.

Лев

За выданное время (7 часов, что безумно мало для такого конкурса), сделал простенький алгоритм, который смог стабильно выигрывать 1-2 уровни с разгромным счётом. А дальше, в зависимости от случайных событий с 3-им уровнем алгоритм выдавал счёт от 0-2 до 6-0. К сожалению, на четвёртый уровень посмотреть так и не удалось. При этом уверен, что за это время можно написать куда лучший вариант, но для этого надо понимать, как вообще какой-нибудь поворот-то работает, а тут организаторы водили плечами, мол, сами не понимаем, почему тут так.

Больше всего времени ушло на то, чтобы разобраться, как и что работает в проекте, особенно бесили не работающие .equals() и два поля .TypeOfPlayer и .PlayerType, возвращавшие абсолютно разные вещи. Ну и какие-то странные поведения игроков, которые организаторы толком не могли объяснить (а мы не знаем, почему ваш персонаж именно тут едет спиной вперёд при единственной данной команде, ну и уже упомянутые повороты :) ). Затем, в какой-то момент, выясняется, что в проекте есть константы для размеров разных игровых объектов и их позиции, что, казалось бы, должно было быть в справочном материале изначально, но нет, в итоге убил время на то, чтобы считать их вручную.

Наши косяки

Илья

• Мой главный косяк в ужасном распределении времени и безрезультатном написании лишних абстракций. Когда у тебя 7 часов — пиши плохой, неподдерживаемый код, если хочешь выиграть.
• Рофл с геомой. Я до сих пор не знаю, какой угол надо прибавить и как сервер обрабатывает его, поэтому на всякий тут % 360. Может 90 +, может 180, а может и все 270. Вообще не задумывался над этим и просто ставил как попало…

  double res = 180 / Math.PI * Math.acos((pp.x - tp.x) / pp.dist(tp));
  return (90 + (int) res) % 360;
  

• За минут 40 до конца конкурса я решил разобраться в дичи, которая происходила в поиске ближайшего игрока к шайбе. Дело оказалось в том, что мой метод squareDist класса Paint имел знак -, вместо + между квадратами разности координат (кстати, в таске на quire тоже -). И с таким багом я считал абсолютно все расстояния на протяжении нескольких часов…
• В самом начале конкурса я держал у себя в голове реализацию получения позиции шайбы в будущем. Для этого необходима её скорость. Как оказалось, из состояния мира ничего полезного нельзя достать вообще (считаю косяком организаторов, опираясь на то, что предоставляют другие конкурсы таких же форматов). Поэтому ту же скорость шайбы приходилось получать, исходя из её позиции в разные моменты игры. Я потратил очень много времени на отладку и не понимал, почему данные приходят так редко (обещали каждые 5мс). В общем, не удалось мне тогда довести просчёт до конца, но за ~час до окончания конкурса я заметил интересный кусок кода в своей стратегии, оставленный организаторами:

  try {
     Thread.sleep(1000);
  } catch (InterruptedException e) {
     e.printStackTrace();
  }
  

  Выставив значение 10, я получил очень частое обновление данных, раскомментировал участок кода, отвечающий за получение скорости, и всё заработало! Спустя минут 20 после этого краем уха услышал вопрос от участника к организаторам по поводу этого куска кода, а тот ему и объяснил, что это сделали специально для нас, чтобы легче было разрабатывать. В тот момент я улыбнулся, поняв, что не один я так поздно осознал это.

Анна

• Как и Илье, мне не удалось в самом начале грамотно распределить своё время: я потратила кучу времени на одну мелкую, хоть и полезную, задачу, а должна была учить хоккеистов забивать шайбы.
• Кучу времени убила из-за того, что забыла сигнатуру метода Math.atan2: сначала идет y, а потом x. Я делала всё наоборот.
• При написании метода, определяющего, нет ли вражеских хоккеистов на определённом отрезке пути, допустила пару ошибок, из-за которых хоккеисты иногда отказывались двигаться куда-либо.
• В целом восприняла конкурс недостаточно серьёзно. Можно было подготовиться более основательно и быть более старательной и внимательной на самом финале.

Лев

• Первые два часа в логах случайно итерировал оба раза по команде союзников, вместо второго раза по команде ботов.

Косяки организаторов

• Мало данных для комфортного написания сильных стратегий. Все, что нам дали, — это четыре метода для управления и позиции игроков на поле. Да, у шайбы был ещё её владелец. Из констант были доступны центр поля, зоны вратарей и ворот. Хоть на этом спасибо, но нам кажется, что следующий перечень значений был просто необходимым. Их получение мы просто костылили!
  1. Скорость игроков (у каждой роли была своя скорость), шайбы;
  2. Информация о замедлении шайбы;
  3. Стартовые позиции игроков;
  4. Размеры игроков, шайбы;

• На вебинаре разработчики прямым текстом говорили, что возможности получить исходный код сервера не будет. Про какие-то упаковщики речь шла, что .exe подсунут. Слово “обфускация” не мелькало, но намекали. А на деле получили мы .jar, который декомпилируется за пару секунд и становятся доступными не только константы и логика с физикой игры, которых не хватало участникам, но ещё и их исходный код бота 3 уровня, играющего против нас. К великому сожалению, сам это я заметил по приезду домой, а о декомпиляции услышал после конкурса от участников. Рассказывали, как кто-то это использовал во время финала. Если это и правда так, то очень неприятно. В такие моменты начинаешь жалеть, что правильный такой весь.
  

  Но в таком случае не очень честно (Александр Полищук boba-alex).

  Ну, молодцы что использовали, раз в правилах не было запрета, а обфускатором решили не проходить, значит это было частью олимпиады (Максим Пьянков maxzxwd).

  

• Хоккеисты могли исчезнуть в случайный момент времени с поля и не появиться до конца игры. Можно пропихнуть игрока в зону вратаря.

• При вызове метода move() хоккеист мог повернуться не в том направлении. Из-за этого могло получиться что-то вроде “лунной походки”.
  Видео

• Метод turn() разворачивает игроков заметно медленнее метода move() к определённой точке (происходит автоматический разворот в нужном направлении). Происходит такое, как правило, при коллизии с другим хоккеистом. Сравнение двух методов:

• Угол отражения оставляет желать лучшего. Огромная скорость после отскока от бортиков (видео замедленно в 4 раза). Незачёт шайбы, хоть она была в воротах.

  Для сравнения, пример паса под прямым углом, у которого всё хорошо со скоростью и замедление есть.

  Видео

• Нападающий вражеской команды стоял ближе к центру поля и сразу перехватывал шайбу в начале раунда (шайба не по центру текстуры поля тоже норма).
  
• Ограничение “вратарь может только доезжать до середины поля от ворот” распространяется только на нашу команды, для врагов такого правила нет.
• Для того, чтобы хоккеисты могли выполнять какие-либо действия, надо сначала к любому из них применить метод move();
• Организаторами в коде стратегии был оставлен таймаут, влияющий на частоту получения новых данных. Если просто удалить этот код, всё замирало. Многие не поняли его предназначение, а от организаторов не поступили объяснения. В правилах тоже эта часть кода не фигурировала. Многие на этом сели в лужу.
• У большого количества участников возникали проблемы со сборкой и изменением уровня стратегии (как оказалось, далеко не многие умели работать с maven’om).
• На вебинаре организаторы заявили, что Java будет использоваться 8 версии, однако в итоге для проекта нужна была минимум Java 11.
• Анна: после того, как села за рабочий компьютер, возникли проблемы с билдом из-за лишних пробелов в коде, который разбивали имя переменной. Не критично, но и не очень приятно.
• На некоторых компьютерах изначально не было ни файлов задания, ни интернета, а также зависимости подгружались долгое время.
• Участников было больше, чем ожидалось. Произошло это из-за каких-то доборов. Поэтому у человек ~13 были заминки с поиском компьютеров (некоторые доставали свои ноутбуки) и с нуля разворачивали проект.
• Обед не был жёстко регламентирован. Не давали определенного времени на трапезу, не закрывали аудитории. Голодающие получили дополнительный час на реализацию.
• Вверху, в описании конкурса, есть подзаголовок с критериями оценки. Проблема их в том, что там сказано о баллах, но не расписано, сколько и за что. В итоге получили непрозрачность и в целом непонимание того, что делать, чтобы выиграть.
  

  Наверное, было бы сложно сравнивать близких по уровню участников, так как не было чётких назначений баллов за фичи, был просто список. Участники могли реализовывать разные фичи, но из все равно надо было как-то сравнивать (Роман).

Заключение

Вывод

В целом, если перестать относиться к финалу слишком серьезно, было весело, интересно и очень залипательно. Да, пришлось тратить время не на написание стратегии, а чтобы справиться с багами разработчиков. Но когда приспосабливаешься и начинаешь играть по их правилам, начинаешь даже получать некоторое удовольствие от процесса. Конечно, хотелось бы, чтобы в дальнейшем разработчики более ответственно отнеслись к данной задаче и довели дело до конца, не предоставляя участникам финала сырой и недоработанный материал.
Также стоит отметить, что победители данного финала — большие молодцы: в таких непростых и неожиданных условиях они смогли собраться, разобраться во всем и выдать качественное решение. Респект таким пацанам.

Благодарности

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

Спасибо Анне (odrus), Льву (zadamantiy), Александру (boba-alex), Максиму (maxzxwd), Ивану, Роману, Анне, Донату, Александру.

Также хотелось бы поблагодарить организаторов самого конкурса IT-Планета, организаторов финала по конкурсу “Программирование: Java” SimbirSoft, а в особенности разработчика Эдуарда, который присутствовал на финале и помогал участникам с проблемами билда, мог прояснить неочевидные моменты в логике игры.

Спасибки за то, что конкурс вообще не кикнули, как сделали с сишарпом (Александр).

Идея финала была хорошая, отборочные туры тоже (Иван).

P.S.

Пока писали статью подъехали фоточки с конкурса и протоколы, а это значит, что теперь мы можем объявить свои места!

Больше всех кукарекал Илья — 28-32 место из 33
Анна — 16
Лев — 14

Спасибо, что дочитали аж до сюда!

Автор: Il`ya Semyonov

Источник