15 июля в Долгопрудном может войти в историю спидкубинга. Команда лаборатории интеллектуальных технологий робототехники МФТИ выведет на официальную попытку робота, который, по предварительным данным, способен собрать мегаминкс примерно втрое быстрее действующего мирового рекорда среди людей - и в 68 раз быстрее предыдущего достижения роботов.
Что за головоломка и почему это сложно
Мегаминкс - это додекаэдральный родственник кубика Рубика, только на порядки злее. Пространство состояний этой головоломки оценивается примерно в 10 в степени 68 - для сравнения, у классического кубика это «всего» около 4,3 × 10 в степени 19. Перебрать варианты вслепую не выйдет ни у человека, ни у машины. Нужны алгоритмы.
Действующий рекорд среди роботов принадлежит устройству Megaminxer британского инженера Дэвида Гилдея - 8 минут 4 секунды, установленные около 15 лет назад. Лучший человеческий результат у китайского спидкубера Ziyu Wu - 21,04 секунды. Физтех метит разом перепрыгнуть обе отметки.
Не только быстрые руки - алгоритмы решают
Скорость системы достигается на двух уровнях. Первый - механика: манипулятор вращает независимые грани параллельно, без микропауз между ходами. Компьютерное зрение распознаёт начальное состояние головоломки автоматически, без ручного ввода.
Второй уровень - математика. Вокруг проекта сложилось open-source сообщество, которое через соревновательную платформу работает над сокращением длины решений в графах Кэли. Участники применяют Pattern Databases, алгоритм Корфа и Beam Search. За последние недели среднюю длину маршрута удалось срезать на 15-20% - до примерно 90 ходов. Потенциальный предел, по оценкам разработчиков, около 81-85 ходов.
- Прежний рекорд роботов: 8 минут 4 секунды (Megaminxer, ~15 лет назад)
- Рекорд человека: 21,04 секунды (Ziyu Wu, Китай)
- Пространство состояний мегаминкса: ~10⁶⁸
- Текущая средняя длина решения: ~90 ходов, цель - 81-85
Куда прийти и как следить
Официальная попытка пройдёт 15 июля с 17:30 до 21:30 в Физтех.Клубе МФТИ. Мест немного - вход по предварительной регистрации. Для тех, кто не успеет попасть вживую, организована онлайн-трансляция на YouTube.
Кроме самой попытки разработчики планируют открытое выступление: расскажут про кинематику манипулятора, систему захвата и алгоритмическую часть - как именно графовые методы превращают хаотичную головоломку в управляемую последовательность движений. Следить за проектом можно в Telegram-группе команды.