- PVSM.RU - https://www.pvsm.ru -
Не мы плохие, а багов много. Разработка искусственного интеллекта для игры “Хоккей” за ~7 часов.
Изначально статья планировалась о стратегиях участников, о том, что они успели сделать за конкурсное время и рады ли проделанной работой, но, опросив финалистов восемь, стало ясно, что ничего не выйдет и надо срочно менять направление.
Дело в том, что на интересующие нас вопросы мы получали максимум 6 слов, а потом сразу же слышали недовольства о багах, с которыми столкнулись участники. Только один человек написал:
Не хочу писать ничего отрицательного, думаю, это некорректно, да и организаторам самим должно быть грустно. Поэтому скажу, что идея задания достаточно интересная, хотя лично мне не очень нравится такой формат соревнований (Анна Прозорова).
Из заголовка статьи понятно, что мы ничего не выиграли. И да, именно “мы”. За конкурсные дни у меня появилось много хороших знакомых, в том числе и Анна (odrus [1]), являющаяся соавтором данной статьи. Также в последний момент мы разговорились со Львом (zadamantiy [2]) и с его разрешения описали участие в финале.
Лично я являюсь участником движения “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 файла (с минимальными правками для статьи), который получил каждый участник.
Где-то в загадочной стране, все жители которой маленькие роботы, встретились 2 команды для игры в хоккей. У обеих команд есть свой персональный робот-тренер, который постоянно следит за игрой, и говорит всем игрокам, куда им необходимо ехать. Все бы ничего, но роботы-игроки понимают только такие простые действия, как идти, бить по шайбе, идти в заданную тренером точку.
Вам предстоит стать тренером для красной команды игроков. Против вас будет играть синяя команда, которая управляется алгоритмом, который уже успешно побеждает другие команды. На поле одновременно играют 2 команды. Команда состоит из 4 игроков: нападающего, 2х защитников и вратаря.
Ваша задача — написать алгоритм управления красными ботами. Для управления персонажами у вас будут 3 метода, которые описаны ниже. Также есть метод, получающий информацию обо всех игроках на поле и координаты шайбы.
Ограничения игры
Вратарь может только доезжать до середины поля от ворот. Защитники и нападающие могут кататься по всему полю, кроме зоны вратарей (красный полукруг около ворот).
Описание структуры приложения
Приложение представлено в виде клиента и сервера. Сервер будет запакован в jar файл, и запущен фоном. На сервере содержится вся основная логика движения персонажей и шайбы, хранение информации обо всех персонажах, шайбе, времени и счете.
Клиент при запуске приложения устанавливает соединение с сервером, и, с заданной периодичностью, получает данные с сервера. Также он отвечает за отрисовку всех персонажей, ворот и шайбы на хоккейном поле.
Весь программный код необходимо писать в классе Algoritm в папке algoritm в клиентском приложении (все изменения в других файлах учитываться не будут).
В этом классе присутствует следующие методы:
Также есть статическая переменная level, которая отвечает за уровень сложности алгоритма. Для участников олимпиады будут доступны следующие уровни:
Все методы, принимающие playerType работают только для игроков красной команды.
Переменная playerType представляет собой экземпляр класса PlayerType, и содержит
такие значения как вратарь, защитник1, защитник2, нападающий.
В классе Playground записаны константные значения игры (например середина поля, зона вратаря и т.д).
Метод getInfo() возвращает объект класса GameInfo.
Уточнения
Тоже взято из .pdf файла. Будет использоваться программный код только из класса Algoritm. Алгоритм каждого участника будет прогоняться против всех уровней сложности поочередно. По результатам прогона будут выставляться очки за результаты матча, а также будут начисляться баллы за реализованные возможности в алгоритме.
Штрафные очки будут начисляться за:
Изначально писали, что в финале будет “Промышленная разработка”. Я ожидал обычной работы с базой, разработки GUI. Приложение для учёта чего-либо, например. С горем пополам согласился на финал, ибо был не очень рад тому, что придётся делать. Однако 17 сентября приходит письмо с регламентом проведения финала, а там сообщается следующее: “Имеется компьютерная 2D-игра «Хоккей», в которой по некоторому алгоритму играют компьютерные боты. Необходимо на языке программирования Java реализовать алгоритм, по которому будут действовать персонажи участников“ (на сайте было написано, что задание может быть изменено). В моей голове сразу же вспомнился Russian AI Cup 2014 года. Я обрадовался и понял, что не зря согласился принять участие.
Первым же делом пошел в очередной раз читать статью победителя [3]. В целом я помнил, что там было, но далеко не все моменты были ясны. Дальше отправился на сайт конкурса [4] и прочитал правила. На этом остановился, ведь любая поправка в правилах может полностью изменить всю игру. Я не знал о том, сколько будет физики в их игре, не знал о том, как происходит удар и подбор шайбы и т.д. Игру могли очень сильно упростить, что даже углы не нужны будут. Поэтому я начал ждать…
Ждал и дождался! Днём 27 сентября приходит письмо о проведении вебинара! 28 сентября в 19:00. Это был идеальный день и время для меня. Однако… Однако за 4 часа до запланированного старта пришло еще одно письмо с переносом на 17:00! Письмо о переносе пришло за час до начала… Летел как мог и опоздал на минут 15 (не ожидал, что еще надо будет ставить Flash Player).
На вебинаре задавал вопросы и получил общую картину об игре. Данных было достаточно, даже чтобы написать свою и основательно подготовиться. Однако до последнего не было понятно, как происходит удар, некоторые моменты разработчики не стали раскрывать, а местами и сами еще не до конца решили.
Записав всё самое ценное, я пошел общаться со знакомыми активными участниками RAIC’a. Привет и спасибо m0rtido [5], DragoonXen [6], oreshn1k [7]. Обрисовав ситуацию, стало понятно, что надо хардкодить ифы и ни о каких симуляциях мира за такое время речи и не может идти. oreshn1k [7] поделилась бомбезной книгой “Programming Game AI by Example”, в четвертой главе которой рассказывалось о дизайне AI для футбола. Мне так сильно понравилось написанное в книге, что я решил расписать для себя всю стратегию, которую собирался написать на конкурсе, и совершенно забыл об ограничении на время. То, что я собирался писать, не подходило для этого конкурса…
Моя проделанная бесполезная подготовка доступна на quire [8] (аккуратно, там аж 168 задач. Местами с описанием). Бесполезная для данного конкурса, а в целом это отличная систематизация полученных знаний из книги. Там же я подумал над симуляцией шайбы, чтобы узнавать её месторасположение через некоторое время, над поиском подходящего угла для удара по воротам, логикой передачи шайбы между игроками и кучей всего интересного.
Выше я уже написал, что без понятия, как писать на ЯП Java, поэтому помимо стратегии я занялся изучением синтаксиса языка. В этом мне помог отличный сайт, которым я пользуюсь уже не первый раз — Learn X in Y minutes [9]. Зайдя в IntelliJ IDEA я понял, что писать на ней точно так же, как и на C#.
Вот с такой подготовкой я поехал в Москву.
Когда узнала о теме финала, первым делом решила повторить геому. А чтобы все это проходило ещё и весело, делала все это с помощью Processing [10]: смотрела примеры от разработчиков, связанные с движением, расчётом углов, скорости и ускорения, а потом практиковалась на своих небольших скетчах.
Время на то, чтобы освежить в памяти какие-то тонкости Джавы, я решила не тратить, потому что задача, как мне показалось, предполагала скорее навыки в написании стратегий и некотором знании математики. Поэтому я решила почитать статью победителя RAIC 2014 [3]. Статья была интересная, но не особо полезная конкретно для данного конкурса, потому что физика могла отличаться кардинальным образом, да и времени будет дано намного меньше.
Вебинар от разработчиков был интересным и полезным, дал общую картину игры. Но я, к сожалению, не смогла посмотреть его полностью, потому что трансляция велась с помощью Flash и мой ноут именно в этот момент решил поиграться с синим экраном смерти.
В итоге непосредственно перед финалом у меня не было никакой заранее проработанной стратегии: сложно было что-то планировать, когда не раскрыты детали физики игры. Были мысли о том, на что стоит обратить внимание в первую очередь, какие вспомогательные методы написать сразу, но не более того. Я решила, что главное перед финалом — это отдохнуть, выспаться и прийти туда с хорошим настроением.
[Готовился] Около 16-20 часов. Соответственно, рассматривал геометрию, с которой я, к сожалению, не сильно в ладах. Заранее подготавливал формулы и расчёты, тестировал всё. Оценил область, из которой можно забить в ворота по условиям, данным организаторами на вебинаре, затем написал эмулятор некоторых действий и получил то, как будет выглядеть область при прямой симуляции ударов с разных точек и оптимальной стратегии вратаря. В итоге не пригодилось ровным счётом почти ничего и пришлось писать костыли на костылях.
С распределением времени на конкурсах и олимпиадах у меня всегда были проблемы. Я наступил на грабли в третий раз. Еще после первого сказал, что никогда не допущу этого. Вновь засел над одной задачей, долго не переключался на другую.
Потратил уйму времени, всю первую часть конкурса до обеда, на реализацию всяких обёрток для игроков команд, классов состояний, сообщений между ними, внутренних ролей. В общем шёл по тем задачам, которые сформировал до конкурса напрочь забыв советы опытных участников о хардкоде ифами и вспомогательных методах. Просто писал совершенно не думая о времени.
Опомнился на обеде. Понимал, что половина конкурса прошла, а у меня работы на ещё часов 10 чтобы хоть что-то начало двигаться. Было принято решение оставить всё что есть и начать с самого начала. Это были увлекательные последние часы конкурса, когда я перестал грустить и хихикал с поведения своих ботов. Очень быстро начал переключаться с задачи на задачу. Не выходит там — перешел на другую, потом вернулся. Желание было только одно — забить хоть как-то, хоть что-то. Поэтому было напрочь забыто о чистоте кода и ООП, местами оставлены интересные комментарии.
Сначала я решила разобраться с тем, как вообще работают основные методы в игре: движение хоккеистов, захват шайбы, повороты и пасы. На это я потратила около часа. Также изучила предоставленные данные и методы, которые были у хоккеистов и шайбы. Затем я решила, что неплохо было бы научиться находить угол между двумя объектами (в частности, между хоккеистом и шайбой). С этим у меня возникли большие трудности: сначала я долго разбиралась с методом Math.atan2, а затем пыталась конвертировать полученные данные в систему углов разработчиков. Со всем этим я мучилась до обеда и была очень расстроена тем, что кучу времени потратила на одну небольшую задачу, хотя за это же время могла написать стратегию как минимум для первого уровня.
После обеда я решила более рационально распределять время. Быстренько дописала метод с определением угла, затем написала стратегию для первого уровня. Потом плавно перешла к стратегии для второго уровня, которую применила в итоге и для третьего. Собственно, этим и залипанием в то, как странно ведут себя мои хоккеисты, я занималась до окончания финала. Код получился ужасный, нечитабельный, с кучей if’ов и копипасты, но со своей задачей он более-менее справлялся: мои хоккеисты забивали шайбы.
За выданное время (7 часов, что безумно мало для такого конкурса), сделал простенький алгоритм, который смог стабильно выигрывать 1-2 уровни с разгромным счётом. А дальше, в зависимости от случайных событий с 3-им уровнем алгоритм выдавал счёт от 0-2 до 6-0. К сожалению, на четвёртый уровень посмотреть так и не удалось. При этом уверен, что за это время можно написать куда лучший вариант, но для этого надо понимать, как вообще какой-нибудь поворот-то работает, а тут организаторы водили плечами, мол, сами не понимаем, почему тут так.
Больше всего времени ушло на то, чтобы разобраться, как и что работает в проекте, особенно бесили не работающие .equals() и два поля .TypeOfPlayer и .PlayerType, возвращавшие абсолютно разные вещи. Ну и какие-то странные поведения игроков, которые организаторы толком не могли объяснить (а мы не знаем, почему ваш персонаж именно тут едет спиной вперёд при единственной данной команде, ну и уже упомянутые повороты :) ). Затем, в какой-то момент, выясняется, что в проекте есть константы для размеров разных игровых объектов и их позиции, что, казалось бы, должно было быть в справочном материале изначально, но нет, в итоге убил время на то, чтобы считать их вручную.
double res = 180 / Math.PI * Math.acos((pp.x - tp.x) / pp.dist(tp));
return (90 + (int) res) % 360;
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
Выставив значение 10, я получил очень частое обновление данных, раскомментировал участок кода, отвечающий за получение скорости, и всё заработало! Спустя минут 20 после этого краем уха услышал вопрос от участника к организаторам по поводу этого куска кода, а тот ему и объяснил, что это сделали специально для нас, чтобы легче было разрабатывать. В тот момент я улыбнулся, поняв, что не один я так поздно осознал это.
Но в таком случае не очень честно (Александр Полищук boba-alex [11]).
Ну, молодцы что использовали, раз в правилах не было запрета, а обфускатором решили не проходить, значит это было частью олимпиады (Максим Пьянков maxzxwd [12]).
Для сравнения, пример паса под прямым углом, у которого всё хорошо со скоростью и замедление есть.
Наверное, было бы сложно сравнивать близких по уровню участников, так как не было чётких назначений баллов за фичи, был просто список. Участники могли реализовывать разные фичи, но из все равно надо было как-то сравнивать (Роман).
В целом, если перестать относиться к финалу слишком серьезно, было весело, интересно и очень залипательно. Да, пришлось тратить время не на написание стратегии, а чтобы справиться с багами разработчиков. Но когда приспосабливаешься и начинаешь играть по их правилам, начинаешь даже получать некоторое удовольствие от процесса. Конечно, хотелось бы, чтобы в дальнейшем разработчики более ответственно отнеслись к данной задаче и довели дело до конца, не предоставляя участникам финала сырой и недоработанный материал.
Также стоит отметить, что победители данного финала — большие молодцы: в таких непростых и неожиданных условиях они смогли собраться, разобраться во всем и выдать качественное решение. Респект таким пацанам.
В первую очередь хотелось бы поблагодарить участников, которые помогли в написании статьи и любезно согласились ответить на наши вопросы. К сожалению, из-за смены направления, многий материал не приходился.
Спасибо Анне (odrus [1]), Льву (zadamantiy [2]), Александру (boba-alex [11]), Максиму (maxzxwd [12]), Ивану, Роману, Анне, Донату, Александру.
Также хотелось бы поблагодарить организаторов самого конкурса IT-Планета, организаторов финала по конкурсу “Программирование: Java” SimbirSoft, а в особенности разработчика Эдуарда, который присутствовал на финале и помогал участникам с проблемами билда, мог прояснить неочевидные моменты в логике игры.
Спасибки за то, что конкурс вообще не кикнули, как сделали с сишарпом (Александр).
Идея финала была хорошая, отборочные туры тоже (Иван).
Пока писали статью подъехали фоточки с конкурса и протоколы, а это значит, что теперь мы можем объявить свои места!
Больше всех кукарекал Илья — 28-32 место из 33
Анна — 16
Лев — 14
Спасибо, что дочитали аж до сюда!
Автор: Il`ya Semyonov
Источник [13]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/news/333865
Ссылки в тексте:
[1] odrus: https://habr.com/ru/users/odrus/
[2] zadamantiy: https://habr.com/ru/users/zadamantiy/
[3] статью победителя: https://habr.com/ru/post/241553/
[4] сайт конкурса: https://2014.russianaicup.ru/
[5] m0rtido: https://habr.com/ru/users/m0rtido/
[6] DragoonXen: https://habr.com/ru/users/dragoonxen/
[7] oreshn1k: https://habr.com/ru/users/oreshn1k/
[8] quire: https://quire.io/w/IT-Planet/
[9] Learn X in Y minutes: https://learnxinyminutes.com/docs/java/
[10] Processing: https://processing.org/
[11] boba-alex: https://habr.com/ru/users/boba-alex/
[12] maxzxwd: https://habr.com/ru/users/maxzxwd/
[13] Источник: https://habr.com/ru/post/472248/?utm_source=habrahabr&utm_medium=rss&utm_campaign=472248
Нажмите здесь для печати.