Задача сборки механических головоломок за минимальное количество ходов формализуется как поиск кратчайшего пути в графе Кэли. Вершинами такого графа являются допустимые состояния головоломки, а ребрами – допустимые ходы, переводящие одно состояние в другое. Для классического кубика Рубика 3×3×3 диаметр графа был определен в 2010 году Томасом Рокицки с коллегами – число Бога составило 20 ходов в метрике HTM (Half-Turn Metric). Однако для головоломок больших размеров – кубиков 4×4×4, 5×5×5, биг-кубов, мегаминкса – точное значение диаметра графа Кэли остается неизвестным.
Проект CayleyPy развивает серию соревнований на платформе Kaggle, посвященных поиску оптимальных и субоптимальных путей в графах Кэли с огромным числом состояний. В этой статье я разберу архитектуру нейросетевого пайплайна CayleyPy, проанализирую результаты завершившихся конкурсов и расскажу о текущих контестах для больших кубов, где участвую как член команды.
***
Инфраструктура Kaggle для комбинаторного поиска
Для задач, где пространство состояний исчисляется величинами порядка 10⁴⁵ и более, локальных вычислительных ресурсов недостаточно. Платформа Kaggle предоставляет доступ к аппаратным ускорителям (GPU NVIDIA Tesla T4/P100 и TPU v3-8/v5e-8), необходимым для обучения моделей и запуска широкого поиска по лучу (Beam Search).
Соревнования CayleyPy формулируются как задачи регрессии и поиска. Состояния головоломки описываются перестановками. Участнику предоставляется тестовый набор – порядка тысячи случайно сгенерированных начальных состояний. Цель – для каждого состояния из набора найти последовательность ходов, которая вернет головоломку в собранное состояние, минимизировав при этом общее количество ходов во всех найденных решениях.
Как работает CayleyPy
Классические алгоритмы (IDA*, двунаправленный поиск в ширину BFS), применяемые для алгоритмического поиска, опираются на предвычисленные таблицы (Pattern Databases, PDB) и редукцию пространства за счет симметрий. При наличии допустимой эвристики они гарантируют нахождение оптимального пути.
Подход CayleyPy позволяет заменить большие таблицы обучаемой нейросетевой эвристикой. Нейросеть по состоянию головоломки оценивает его удаленность от целевого состояния. Весь процесс состоит из трех шагов:
Шаг 1. Случайные блуждания и генерация датасета для обучения
Берем собранный кубик и начинаем его перемешивать случайным образом, то есть совершать случайное блуждание по графу состояний. Для всех состояний (узлов) в процессе блуждания мы сохраняем пару: текущее состояние кубика (v) и число случайных ходов, сделанных от старта (собранного состояния) до этого узла (k).
Шаг 2. Обучение нейросети
Полученные пары (v, k) используются для обучения нейросети. Для каждой пары (v, k) сетка берет на вход (v) и должна предсказать (к). Подобным образом она учится оценивать разные состояния и давать оценку, какое из них, вероятно, ближе к решению. После обучения нейросеть становится своего рода проводником по графу кубика. Важно понимать, что нейросеть не учит конкретные последовательности ходов. Обучение происходит заранее, до начала процесса решения головоломки.
Шаг 3. Поиск пути
Проводник может ошибаться. Если слепо доверять только одной лучшей оценке и каждый раз выбирать один ход, ошибка нейросети может увести поиск в неудачном направлении. Поэтому на этапе решения используется Beam Search.
Задаем ширину луча, например 5. Из текущих позиций луча генерируем все возможные следующие ходы. Нейросеть оценивает полученные состояния. Из них оставляем 5 наиболее перспективных – то есть имеющих наименьшие оценки. Затем из этих пяти снова генерируем соседние состояния, удаляем дубликаты, оцениваем новые позиции и снова оставляем топ-5.
Процесс повторяется до тех пор, пока не будет найдено собранное состояние или не будет достигнут установленный лимит поиска.
При этом в ходе экспериментов выяснилось, что бесконечное увеличение объема обучающей выборки довольно быстро перестает влиять на качество эвристики. Зато увеличение ширины луча непосредственно при поиске пути стабильно и надежно сокращает длину решения.
CayleyPy vs Рокицки
Сначала команда CayleyPy проверила свой подход на классическом кубике Рубика 3×3×3, используя стандартный датасет DeepCubeA. Результат 98,4% оптимальных решений оказался существенно лучше, чем у предыдущих лидеров среди ML-подходов – DeepCubeA и EfficientCube, которые показывали 60,3% и 69,6% соответственно. Эксперимент показал, что нейросетевая эвристика в связке с лучевым поиском способна конкурировать с классическими алгоритмами. Можно было переходить к тестированию подхода на кубах с размерностями 4×4×4 и выше.
CayleyPy 444 Cube Solve Optimally стало первым крупным соревнованием, где подход CayleyPy проверили на головоломке, для которой еще не определен диаметр графа Кэли (максимальное количество ходов, необходимых для сборки любого состояния). Пространство состояний куба 4×4×4 на 26 порядков больше, чем у классического кубика Рубика, и составляет около 7,4×10⁴⁵ состояний. Точное число Бога (диаметр графа Кэли) для кубика 4×4×4 до сих пор не вычислено, известны только его нижняя и верхняя границы: 32–53 в метрике BTM (Block-Turn Metric). Есть гипотетические оценки в 48 ходов. Но вопрос пока остается открытым.
В финальном лидерборде конкурса по кубику 4×4×4 команда CayleyPy возглавила лидерборд, обойдя гуру алгоритмического поиска Томаса Рокицки. Итоговый скор команды составил 44 810, а средняя длина решения – 46,51 хода. То есть нейросеть находила пути, которые математически близки к абсолютному пределу для этой головоломки.
Недавно завершившийся конкурс CayleyPy Megaminx Solve Optimally хорошо показал разницу между классическим поиском и нейросетевыми эвристиками. Здесь команда CayleyPy также опередила Томаса Рокицки в лидерборде.
Пространство состояний мегаминкса (додекаэдра) составляет ≈1.01×10⁶⁸. Одним из главных тестов соревнований была конфигурация Superflip – симметричное состояние, в котором все ребра перевернуты, а углы и центры находятся на своих местах. Это состояние мегаминкса является обратным самому себе (инволюцией). Поэтому Superflip считался потенциально самой далекой точкой от собранного мегаминкса.
Классическое лучшее решение Superflip в метрике FTM (Face-Turn Metric) составляло 55 ходов (результат Т. Рокицки, май 2023 г., полученный с использованием симметричной редукции и эвристического поиска). При этом точная нижняя граница диаметра графа мегаминкса в FTM была установлена Гербертом Коцембой в 2016 году и равняется 48 ходам.
Владислав Кузнецов, используя подход CayleyPy, нашел решение Superflip длиной 47 ходов в метрике FTM (май 2026 г.). Из неравенства 47<48 непосредственно следует, что конфигурация Superflip не является антиподом графа Кэли мегаминкса. Следовательно, Superflip не может быть конфигурацией, достигающей диаметра. Оценивая этот результат на форуме SpeedSolving.com, Томас охарактеризовал его как «the first major, significant breakthrough in the application of AI to twisty puzzle theory» (первый крупный, значимый прорыв в применении искусственного интеллекта к теории механических головоломок).
CayleyPy и биг-кубы
В настоящий момент идут конкурсы по решению кубика 5×5×5 CayleyPy 555 Cube Solve Optimally и биг-кубов 6×6×6 и 7×7×7. Я участвую в этих соревнованиях в команде CayleyPy.
Пространство состояний куба 5×5×5 достигает 2,83×10⁷⁴, для 6×6×6 – 1,57 × 10¹¹⁶, для 7×7×7 – 1,95 × 10¹⁶⁰. Число Бога не известно ни для одного из этих кубов. Для 5×5×5 есть только гипотезы, но строгого доказательства нет.
С точки зрения обучения с подкреплением здесь возникает знакомая проблема разреженного сигнала, когда полезная информация появляется только в целевом состоянии. До этого момента, на протяжении сотен шагов, у агента нет никакой информации о том, приближается он к цели или отдаляется от нее.
Подход CayleyPy решает эту проблему. Вместо бинарного сигнала «собрал / не собрал» используется непрерывный сигнал. Нейросеть оценивает каждое промежуточное состояние числом – например: «это состояние ближе к цели, а соседнее – значительно дальше». Алгоритм поиска использует эти оценки как градиент, двигаясь в сторону уменьшения значения, вместо того чтобы блуждать по графу вслепую.
***
Соревнования серии CayleyPy на Kaggle открыты. В распоряжении участников доступ к GPU, открытый код (480 звезд на GitHub) и задачи, которые пока никто не решил за сорок лет. А еще строчка в лидерборде и признание сообщества. Призовых денег там нет… или почти нет: для кубика 5×5×5 объявлен приз 10000 рублей тому, кто получит решения короче 90 ходов.
Если интересно поучаствовать в развитии проекта CayleyPy или узнать подробности, напишите в телеграм Александру Червову.
Автор: academicmaslow
