CayleyPy обыграла классические алгоритмы в решении больших кубиков Рубика

Проект CayleyPy развивает серию соревнований на платформе Kaggle, посвященных поиску оптимальных решений для механических головоломок с неизвестным числом Бога. Вместо классических алгоритмов вроде IDA* и двунаправленного BFS, которые полагаются на предвычисленные таблицы (Pattern Databases), CayleyPy применяет обучаемую нейросетевую эвристику. На классическом кубике Рубика 3×3×3 с диаметром графа в 20 ходов (метрика HTM, Томас Рокицки 2010) система достигла 98,4% оптимальных решений — это превосходит DeepCubeA (60,3%) и EfficientCube (69,6%).

Архитектура: три шага от случайных блужданий к поиску

Метод состоит из трех этапов. Первый — генерация выборки: берут собранный кубик, перемешивают случайно, сохраняя для каждого состояния пару «конфигурация–расстояние до старта». Второй — обучение: нейросеть учится предсказывать расстояние по состоянию, становясь эвристикой для поиска. Третий — Beam Search: алгоритм держит W наиболее перспективных позиций (обычно W=5 или W=40), оценивает их соседей, отбирает топ-W. Процесс повторяется до сборки или лимита поиска.

Важный вывод из экспериментов: увеличение обучающей выборки быстро перестает улучшать качество эвристики, зато расширение ширины луча стабильно сокращает длину решения.

От кубика 4×4 к мегаминксу: прорывы на неизвестных диаметрах

На кубике 4×4×4 пространство содержит 7,4×10⁴⁵ состояний (в 26 порядков больше, чем 3×3). Число Бога неизвестно; известны границы: 32–53 ходов в метрике BTM с гипотезой 48 ходов. CayleyPy достигла среднего 46,51 хода на финальном лидерборде, обойдя Томаса Рокицки.

На мегаминксе (додекаэдре) пространство состояний ≈1,01×10⁶⁸. Конфигурация Superflip (все ребра перевернуты, углы и центры на местах) рассматривалась как потенциально самая далекая от собранного состояния. Томас Рокицки в мае 2023 года решил Superflip за 55 ходов в метрике FTM. Герберт Коцемба в 2016 году установил нижнюю границу диаметра мегаминкса: 48 ходов в FTM.

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

Текущие конкурсы: масштабы задач и доступные ресурсы

На Kaggle проходят соревнования по трем кубам с неизвестным числом Бога:

• Кубик 5×5×5 (2,83×10⁷⁴ состояний) с призом 10000 рублей за решения короче 90 ходов; • Кубик 6×6×6 (1,57×10¹¹⁶ состояний); • Кубик 7×7×7 (1,95×10¹⁶⁰ состояний).

Основная проблема классического обучения с подкреплением здесь — разреженный сигнал: агент получает полезную информацию только при достижении целевого состояния, сотни промежуточных шагов остаются без обратной связи. CayleyPy решает это непрерывным сигналом: нейросеть оценивает каждое промежуточное состояние числом, позволяя алгоритму двигаться по градиенту вместо слепого блуждания.

Участникам доступны GPU NVIDIA Tesla T4/P100 и TPU v3-8/v5e-8 на платформе Kaggle, открытый исходный код проекта (480 звезд на GitHub) и задачи, не решенные четыре десятилетия. Присоединиться можно через Александра Червова в Telegram.