Ставим мировой рекорд на Физтехе

Расскажем подробнее о проекте-победителе конкурса «Обратная перспектива», получившем поддержку в 3,68 млн руб. из ежегодного дохода целевого капитала № 1.

Мегаминкс

Мегаминкс — это перестановочный пазл, похожий на кубик Рубика, но имеющий гораздо больше состояний. У него не 6, а 12 граней (это правильный додекаэдр), и у каждой грани не 4 стороны, а 5. Для обычного кубика Рубика в 2010 году было показано, что диаметр графа состояний (самый длинный кратчайший путь между состояниями) составляет 20. Для мегаминкса есть оценка снизу в 48 и сверху в 116, но точное значение человечеству пока не известно.

Мировой рекорд по сборке кубика Рубика 3x3 человеком составляет 2,76 секунды, а роботом — 103 миллисекунды. Это вполне объяснимо, поскольку робот может и крутить, и считать существенно быстрее. Однако для мегаминкса человеческий рекорд составляет 21,99 секунды, а рекордное время сборки роботом около 8 минут. Роботы могут быть и быстрее, и сильнее людей в отдельных задачах, но в универсальности пока отстают.

Мировой рекорд

На соревнованиях команда проекта попытается поставить мировой рекорд в сборке мегаминкса роботом, который был разработан в лаборатории интеллектуальных технологий робототехники МФТИ. Это первый в мире робот, в котором обеспечивается независимое вращение всех граней. Остальные переворачивают головоломку и крутят только одну грань, что увеличивает время сборки.

Для сборки мегаминкса роботом нужно две вещи: робот и алгоритм. Робот был изготовлен сотрудниками лаборатории, и на нем можно будет протестировать свои алгоритмы.

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

Мини-курс

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

Спикеры: Андроник Арутюнов, профессор ВШМ МФТИ, и Игорь Шиманогов.

• В первой части курса Андроник Арутюнов расскажет про группы, графы и действия. Будут изучены ключевые аспекты того, как группы действуют на множествах — в частности, на графах — и как это связано с головоломками и прикладными задачами.
• В начале будет определено действие группы на множестве и сразу применено к классической задаче: сколькими способами можно раскрасить куб в заданное количество цветов. По ходу дела будут рассмотрены группы диэдра и вопрос о симметрии снежинок.
• Далее будет рассмотрено геометрическое представление групп — графы Кэли, их свойства (в первую очередь вершинную транзитивность) и то, как это даёт наглядную геометрическую интерпретацию образующих и соотношений группы.
• Одной из ключевых тем станет доказательство теоремы Сабидусси и ряда связанных с ней результатов. Всё это позволит сформировать строгое теоретико-групповое представление об устройстве головоломок типа «Кубика Рубика».
• Также будут обсуждены алгоритмы их решения, скорость работы и так называемое «число Бога». В завершение увидим, как эта теория связана с такими прикладными задачами, как сортировка массива, и другими проблемами из теории алгоритмов.
• В рамках второй части курса Игорь Шиманогов расскажет про классический результат вычислительной теории групп: алгоритм Шрайера-Симса. Этот алгоритм представляет интерес как один из основных способов решения произвольных перестановочных головоломок. В лекциях будет рассказана вся необходимая теория для доказательства корректности данного алгоритма. При наличии времени и желания у слушателей возможно как рассмотрение модификаций алгоритма, так и его применение к другим вопросам теории групп.

Соревнование

Мини-курс будет идти с 27 февраля. Для тестирования алгоритмов будет выложен в свободный доступ симулятор мегаминкса, с которым можно будет работать на Python.

В конце апреля или начале мая будет проведено оффлайн-соревнование, на котором будет определен победитель. Скорее всего, робот с этим алгоритмом будет самым быстрым в мире на тот момент.

Записывайтесь на курс, если:

• нравятся кубики Рубика
• нравится теория групп и графы
• хочется вписать свое имя в историю странной нишевой области

Участвовать могут как студенты МФТИ, так и все остальные желающие. Для участия обязательно зарегистироваться в форме! Внешним гостям необходимо оформить временные пропуска для очного посещения лекций.

Ссылки и контакты

Форма для регистрации: https://forms.gle/PfmT1nnjpmakYYAb6
Руководитель проекта: Илья Осокин tg @elijahmipt
Чат соревнования в тг: @starkitmega

«Обратная перспектива» — открытый конкурс Фонда целевого капитала, созданный для финансирования проектов, реализуемых студентами, сотрудниками и выпускниками МФТИ.