Привет, Хабр! Это Михаил Елизаров, разработчик трека «Программирование роботов» на True Tech Champ. Сегодня я расскажу, как наша команда придумала челлендж для любителей кода и сложных задач.
Для чемпионата нам нужно было сделать наглядные и интересные состязания по программированию и придумать необычный формат. Мы вдохновлялись соревнованиями роботов в лабиринте, но упростили его. Теперь в нем могут принять участие все, кому интересно решать подобные задачи.
Итак, под катом будет механика лабиринта, обзор заданий и требуемых для них навыков.
Что нужно будет делать в лабиринте
Нашей команде поступила задача придумать крутое состязание. В прошлом году за True Tech Champ наблюдало восемь тысяч человек, а в этом нужно было сделать его еще интереснее и дать участникам и зрителям возможность сразу видеть результат своей работы. Challenge accepted!
За основу мы взяли соревнования по поиску выхода из лабиринтов. Например, Micromouse, где используется полигон 16 х 16 клеток. Обычно участники сами конструируют и программируют роботов, но мы решили сделать уже готовую мышь, чтобы с ней мог поработать кто угодно.
При выполнении заданий участники в режиме реального времени смогут видеть свои ошибки и отлаживать алгоритмы. И по итогам получить баллы.
Первый этап пройдет в онлайне. Нужно будет решить простые задачи в виртуальном лабиринте: сканировать поле и собирать данные, находить выход из тупика, проезжать от старта до финиша на скорость.
Следующий этап — полуфинал. Участники объединятся в команды от 2 до 4 человек и получат доступ к управлению «живой» робомышью.
До 36 лучших команд попадут в финал, где полигон будет еще сложнее. Девять лучших отправятся в суперфинал, который пройдет в офлайне 8 ноября. На нем стены будут двигаться, а геройская робомышь должна будет прорываться сквозь вспышки света, дым и огонь.
Пока я пишу этот текст, у меня вовсю печатается лабиринт для финалистов.
Как устроен полигон
В онлайне это будет классический лабиринт, который заново генерируется при каждой новой попытке выполнить задание. Участники после регистрации скачивают его и с помощью API отправляют организаторам алгоритм прохождения. Мы смотрим, насколько эффективно все сделано, и присуждаем баллы.
Чтобы участники видели результаты своей работы, мы добавили возможность посмотреть на мышь от третьего лица, как в классических играх:
Самой сложной задачей оказалось сделать симулятор на Unreal Engine, максимально приближенный к реальному роботу, и обеспечить его правильное управление по API. С платформой мы угадали, так как в Unreal Engine уже есть функция работы через веб — мы допилили модуль, который позволяет управлять роботом по REST API.
Какие будут задания
Всего в лабиринте предстоит выполнить три усложняющиеся задачи.
Изучение лабиринта
Сначала нужно построить карту: просканировать стены и отправить организаторам двумерный массив. Этот алгоритм поможет выполнить второе и третье задание.
Прохождение на скорость
Нужно будет написать алгоритм, который поможет робомыши как можно быстрее добраться до конечной точки.
Выход из тупика
И снова речь о скорости, но на этот раз управление усложнится. Участники смогут не только поворачивать направо или налево, но и включать сильнее или слабее каждый из моторов.
В помощь участникам — датчики, которыми оборудован робот. Это и лазерные дальномеры, и гироскоп. В суперфинале мы будем стараться максимально помешать их работе с помощью вспышек, огня и дыма, а также движущихся консолей, усложняющих лабиринт.
Что нужно от участников
Для управления робомышью нужно:
Понимать базовые концепции программирования: переменные, циклы, условные операторы, функции, массивы и структуры данных.
Знать алгоритмы:
Жадный алгоритм (Greedy Algorithm): для быстрого поиска решения.
Алгоритм поиска в глубину (Depth-First Search, DFS): используется для прохождения всех возможных путей.
Алгоритм поиска в ширину (Breadth-First Search, BFS): для поиска кратчайшего пути.
Алгоритм A*: для эффективного поиска оптимального пути с использованием эвристик.
Алгоритм волновой трассировки (Lee Algorithm): полезен для поиска кратчайшего пути в сетке.
Знать основы математики и логики: в процессе выполнения заданий нужно будет решать логические задачи и анализировать поведение робомыши в лабиринте.
Уметь работать с координатами и ориентацией в пространстве: управлять положением робота, ориентировать на поворот и движение вперед.
Уметь отлаживать и тестировать код: искать и исправлять ошибки, анализировать поведение робота в симуляции.
Понимать работу с сенсорами: использовать данные с них для принятия решений.
Участники получают доступ к платформе, через которую они смогут следить за роботом и отправлять ему команды. Здесь нужно уметь работать с REST API, а также знать один из языков программирования:
C++,
Python,
Java,
Go,
Links,
C#,
JavaScript.
Сложность увеличивается с каждым заданием, но можно переиспользовать код и наработки из предыдущих. Изначально участники создают MVP — то есть просто знакомятся с полем и управлением. Затем процессы усложняются вплоть до суперфинала, где лабиринт и робот становятся физическими, а на пути аппарата начинают появляться новые препятствия, мешающие прохождению.
Прокачивать нужно будет не только хард-, но и софт-скиллы. Участники собираются в команды от двух до четырех человек, им нужно договориться, распределить роли и так далее.
Что будет в финале
Заявки на участие в чемпионате принимаются до 15 октября. На программировании роботов призы будут у команд, занявших первые три места:
4 млн рублей за первое место;
2,5 млн рублей — за второе;
1 млн рублей — за третье.
Кроме программирования роботов, будет еще и алгоритмический трек, где нужно решать разные задачки. Финал состоится 8 ноября в МТС Live Холл. На площадке будет целая серия «айтивностей»: мастер-класс по пайке плат, сборка креативных роботов, сбор серверов и поиск отмычек от замков на скорость, веб-серфинг, шахматные партии против ИИ, экстремальный кодинг, скалодром с генерацией маршрутов, гадание по строчкам кода. Также все гости смогут попробовать пройти робомышью лабиринт и почувствовать себя финалистом чемпионата.
На этом у меня все, если возникли вопросы — задавайте в комментариях. Ну а ниже я собрал основные вопросы, которые возникают у наших участников. Ждем ваших заявок!
FAQ
Специально для тех, кому интересно соревнование, я собрал небольшой FAQ:
Где я могу посмотреть еще про соревнование и задачи?
У нас прошло два вебинара, доступ к ним всегда есть на платформе в разделе «Обучение»:
Будет ли учитываться время выполнения задач при отборе в полуфинал?
В зачет идут результаты по всем трем задачам: для первой — баллы до 256, для второй и третьей — скорость прохождения лабиринта.
Где найти документацию на API?
Вместе с приложением открывается консоль. В ней есть нужная ссылка: http://127.0.0.1:8801/api/v1/docs (Swagger) и адрес, куда отправлять запросы: http://127.0.0.1:8801/api/v1.
Какое время дается на прохождение одного задания?
15 минут.
Как работает несколько попыток во втором и третьем заданиях?
Один и тот же лабиринт можно пройти до трех раз, затем он генерируется заново. Чтобы начать новое прохождение, нужно доехать до центра и переместить мышь на старт с помощью специального API-метода:
POST: http://127.0.0.1:8801/api/v1/maze/restart
Как должен выглядеть массив для решения первого задания?
Пример:
[
[8, 10, 7, 8, 10, 2, 11, 8, 10, 2, 10, 11, 8, 10, 2, 7],
[1, 7, 9, 5, 7, 5, 10, 6, 12, 5, 10, 10, 6, 12, 9, 9],
[9, 9, 9, 12, 9, 8, 10, 2, 0, 10, 10, 10, 7, 9, 9, 9],
[9, 9, 9, 9, 9, 5, 11, 9, 9, 8, 10, 7, 9, 9, 9, 9],
[9, 9, 5, 3, 5, 10, 10, 3, 14, 9, 8, 6, 5, 6, 9, 9],
[9, 5, 7, 14, 8, 10, 10, 6, 8, 6, 5, 10, 10, 10, 6, 9],
[9, 12, 5, 10, 6, 12, 8, 10, 6, 8, 2, 11, 8, 10, 10, 6],
[9, 1, 10, 10, 10, 6, 9, 2, 7, 9, 9, 8, 6, 8, 10, 7],
[9, 9, 8, 7, 8, 10, 6, 5, 6, 9, 5, 6, 12, 9, 12, 9],
[9, 5, 6, 9, 9, 13, 7, 8, 7, 5, 10, 7, 9, 1, 6, 9],
[5, 2, 10, 6, 5, 7, 9, 9, 1, 11, 8, 6, 1, 6, 8, 3],
[8, 6, 8, 7, 8, 6, 1, 6, 5, 7, 9, 8, 6, 12, 9, 14],
[9, 8, 6, 5, 6, 8, 6, 13, 7, 5, 6, 5, 10, 6, 5, 7],
[9, 5, 7, 8, 7, 5, 7, 8, 4, 10, 10, 10, 7, 8, 10, 6],
[5, 11, 9, 9, 1, 11, 9, 5, 7, 8, 10, 7, 9, 5, 10, 7],
[13, 10, 6, 14, 5, 10, 4, 10, 6, 5, 11, 5, 4, 10, 10, 6]
]Куда писать код и на каком языке?
На странице задания на платформе выберите один из поддерживаемых языков программирования — появится шаблон с кодом. Его надо стереть и вставить свой код. После чего нужно отправить его на проверку.
Какие библиотеки на языке go можно применить для управления роботом?
Можно использовать любые библиотеки, но мы вводим ограничения на 100 Мб для контейнера, так как многие пытаются использовать тяжелые библиотеки. Так мы никогда не сможем проверить все отправленные исходники.
Надо, чтобы робот посетил все клетки?
Не обязательно. Важен именно ответ. Мы не следим за тем, где был робот.
Гарантируется ли, что финиш (красная коробка) имеет ровно один вход?
Да, гарантируется.
