Математическая сенсация: как ИИ опроверг гипотезу о мегаминксе
Долгое время считалось, что классические алгоритмы дискретной оптимизации вроде IDA* с предвычисленными базами паттернов (PDB) — непревзойденный стандарт для сборки механических головоломок. Однако открытый проект CayleyPy доказал обратное: нейросетевая модель смогла превзойти рекорд признанного эксперта комбинаторного поиска Томаса Рокицки и попутно совершить теоретическое открытие.
В головоломке «Мегаминкс» (додекаэдр с пространством состояний около 1,01×10⁶⁸) ключевым испытанием считалась симметричная конфигурация Superflip. Долгое время предполагалось, что она максимально удалена от собранного состояния. Прежний рекорд ее сборки составлял 55 ходов при теоретической нижней границе диаметра графа в 48 ходов. Участник команды CayleyPy Владислав Кузнецов с помощью машинного обучения нашел путь всего за 47 ходов в метрике FTM. Поскольку 47 меньше 48, это строго доказало: Superflip не является антиподом графа Кэли для мегаминкса. Рокицки назвал данный результат первым крупным прорывом в применении ИИ к теории перестановочных головоломок.
В чем суть метода CayleyPy
В огромных пространствах состояний (для кубика 4×4×4 это 7,4×10⁴⁵ комбинаций) классические таблицы PDB требуют колоссальной памяти, а алгоритмы обучения с подкреплением страдают от разреженного сигнала подкрепления. Разработчики CayleyPy предложили изящную трехступенчатую альтернативу:
- Генерация данных случайными блужданиями: от собранного состояния запускаются случайные ходы, а модель фиксирует пары «состояние — число шагов от финиша».
- Обучение эвристики: нейросеть обучается оценивать дистанцию произвольной расстановки до собранного вида, создавая непрерывный градиент вместо бинарного «собрано/не собрано».
- Поиск по лучу (Beam Search): при поиске решения алгоритм генерирует соседние узлы, оценивает их с помощью нейросети и оставляет только фиксированное число лучших кандидатов, методично углубляясь до победной комбинации.
Практика показала, что увеличение объема выборки дает ограниченный эффект, тогда как простое расширение ширины луча в Beam Search стабильно сокращает итоговую траекторию.
Триумф на больших кубах
Эффективность подхода подтвердилась серией тестов:
- На классическом кубике 3×3×3 пайплайн показал 98,4% оптимальных сборок, оставив позади модели DeepCubeA (60,3%) и EfficientCube (69,6%).
- В соревновании по кубику 4×4×4 на платформе Kaggle команда заняла верхнюю строчку, опередив Рокицки со средней длиной решения 46,51 хода (при гипотетическом «числе Бога» около 48).
В настоящее время авторы CayleyPy тестируют алгоритм на гигантских кубах 5×5×5, 6×6×6 и 7×7×7, где пространство состояний доходит до 1,95×10¹⁶⁰. Все наработки проекта выложены в открытый доступ, а в открытых контестах на Kaggle может принять участие любой энтузиаст машинного обучения.