CayleyPy: нейросеть обошла классический поиск в кубике Рубика

Проект CayleyPy, развиваемый на платформе Kaggle, посвящён поиску кратчайших путей в графах Кэли механических головоломок. Задача сборки кубика Рубика формализуется как поиск пути между состояниями-вершинами, а число ходов — как длина ребра. Для классического кубика 3×3×3 диаметр графа (число Бога) был установлен в 2010 году Томасом Рокицки и коллегами: 20 ходов в метрике HTM. Однако для кубов 4×4×4, 5×5×5, биг-кубов и мегаминкса точное значение диаметра до сих пор неизвестно.

Пространства состояний таких головоломок огромны: у куба 4×4×4 — около 7,4×10⁴⁵ состояний, у мегаминкса — примерно 1,01×10⁶⁸. Классические алгоритмы (IDA*, двунаправленный BFS) опираются на предвычисленные таблицы и симметрии, гарантируя оптимальность при наличии допустимой эвристики, но требуют больших ресурсов. CayleyPy предлагает заменить громоздкие таблицы обучаемой нейросетевой эвристикой: сеть оценивает удалённость состояния от собранного, а поиск ведётся методом лучевого поиска (Beam Search).

Обучение нейросети происходит на случайных блужданиях по графу: собираются пары «состояние — число ходов от старта», и модель учится предсказывать это число. На этапе решения из текущих позиций генерируются все возможные ходы, сеть оценивает новые состояния, и остаются несколько наиболее перспективных — например, пять при ширине луча 5. Процесс повторяется до нахождения собранного состояния или достижения лимита. Эксперименты показали, что увеличение ширины луча стабильно сокращает длину решения, тогда как бесконечный рост обучающей выборки быстро перестаёт улучшать эвристику.

На классическом кубике 3×3×3 подход CayleyPy дал 98,4% оптимальных решений, существенно превзойдя предыдущие ML-методы DeepCubeA (60,3%) и EfficientCube (69,6%). Это подтвердило конкурентоспособность нейросетевой эвристики в связке с лучевым поиском и открыло путь к тестированию на головоломках большего размера.

В конкурсе CayleyPy 444 Cube Solve Optimally команда CayleyPy заняла первое место, обойдя Томаса Рокицки. Средняя длина решения составила 46,51 хода при итоговом скоре 44 810. Для куба 4×4×4 точный диаметр неизвестен, но известны границы 32–53 в метрике BTM и гипотетическая оценка в 48 ходов, так что результаты нейросети оказались близки к математическому пределу.

На соревновании по мегаминксу CayleyPy также опередила Рокицки. Ключевым тестом стала конфигурация Superflip — симметричное состояние, считавшееся потенциально самой далёкой точкой от собранного мегаминкса. Классическое лучшее решение Superflip в метрике FTM составляло 55 ходов (Рокицки, май 2023), а нижняя граница диаметра в FTM была установлена Гербертом Коцембой в 2016 году на уровне 48 ходов.

Владислав Кузнецов с помощью CayleyPy нашёл решение Superflip длиной 47 ходов в метрике FTM (май 2026). Из неравенства 47<48 следует, что Superflip не является антиподом графа Кэли мегаминкса и не может достигать диаметра. На форуме SpeedSolving.com Томас Рокицки назвал это «первым крупным, значимым прорывом в применении искусственного интеллекта к теории механических головоломок». Сейчас идут конкурсы для куба 5×5×5 и биг-кубов 6×6×6 и 7×7×7.