Как нейросети обходят классический поиск при сборке кубика Рубика с помощью CayleyPy

Поиск кратчайших траекторий для сборки механических головоломок сводится к классической задаче нахождения кратчайшего пути в графе Кэли. В такой структуре узлы символизируют допустимые конфигурации пазла, а ребра — разрешенные движения, трансформирующие одно положение в другое. Для стандартного кубика Рубика 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). Таким образом модель учится ранжировать различные позиции, определяя, какая из них находится ближе к финалу. Обучение производится заранее, задолго до старта этапа непосредственного поиска решений, превращая сеть в надежного штурмана по лабиринтам графа.

Этап 3. Алгоритм поиска маршрута

Любая нейросеть способна ошибаться. Если слепо опираться исключительно на наилучший прогноз и совершать единичные шаги, погрешность модели может завести алгоритм в тупик. Именно поэтому на стадии вывода задействуется лучевой поиск (Beam Search).

Задается фиксированная ширина луча, например, параметр 5. Из текущих позиций генерируются все возможные последующие ходы. Нейросеть выставляет оценки получившимся состояниям, после чего отбираются 5 наиболее перспективных кандидатов с наименьшими метриками удаленности. Процедура повторяется итеративно: из выбранной пятерки порождаются новые соседи, отсеиваются дубликаты, происходит повторная оценка и отбор топ-5.

Цикл продолжается вплоть до обнаружения целевого собранного состояния либо до исчерпания заданных лимитов поиска.

Любопытно, что в ходе экспериментов выяснился интересный факт: бесконечное наращивание объема обучающей выборки довольно быстро перестает приносить дивиденды в точности эвристики. Зато расширение ширины луча во время поисковой фазы стабильно и эффективно уменьшает итоговую длину решений.

Сравнение подхода CayleyPy с методами Рокицки

Изначально команда протестировала свою концепцию на классическом кубике 3×3×3, задействовав общепризнанный корпус данных DeepCubeA. Показатель в 98,4% оптимальных исходов существенно превзошел результаты прежних лидеров среди машинного обучения — DeepCubeA и EfficientCube, удерживавших планку на уровне 60,3% и 69,6% соответственно. Эксперимент подтвердил, что комбинация нейросетевой эвристики и лучевого поиска способна на равных конкурировать с детерминированными алгоритмами, открывая дорогу к испытаниям на кубах размерности 4×4×4 и выше.

Соревнование CayleyPy 444 Cube Solve Optimally стало пилотным масштабным испытанием для архитектуры на головоломке, точный диаметр графа Кэли которой все еще не установлен. Пространство состояний четверки превосходит кубик Рубика на 26 порядков, составляя примерно 7,4×10⁴⁵ вариантов. Точное число Бога для куба 4×4×4 до сих пор не вычислено аналитически, известны лишь границы: от 32 до 53 в метрике BTM (Block-Turn Metric), при этом эксперты склоняются к гипотетическому значению в 48 ходов.

По итогам финальной таблице лидеров команда CayleyPy заняла первую строчку, опередив признанного эксперта по алгоритмическому поиску Томаса Рокицки. Итоговый балл коллектива составил 44 810 при средней длине найденных путей в 46,51 хода. Иными словами, нейросеть продемонстрировала способность находить траектории, экстремально близкие к абсолютным математическим пределам головоломки.

Недавний контест CayleyPy Megaminx Solve Optimally наглядно продемонстрировал превосходство нейросетевых эвристик над классическими алгоритмами, где команда также закрепилась на вершине лидерборда, обогнав Рокицки.

Пространство состояний мегаминкса (правильного додекаэдра) оценивается в астрономические ≈1.01×10⁶⁸ вариаций. Серьезнейшим испытанием в рамках состязания выступала конфигурация Superflip — симметричное состояние, при котором все ребра перевернуты относительно своей ориентации, а угловые элементы и центры находятся на базовых местах. Поскольку эта позиция инвертивна (обратна сама себе), долгое время она считалась главным кандидатом на звание наиболее удаленной от сборки точки.

Лучший традиционный результат для Superflip в метрике FTM (Face-Turn Metric) равнялся 55 ходам (достижение Т. Рокицки от мая 2023 года, добытое посредством симметрической редукции и эвристического поиска). При этом точный нижний предел графового диаметра мегаминкса в FTM был зафиксирован Гербертом Коцембой еще в 2016 году на отметке в 48 ходов.

В мае 2026 года Владислав Кузнецов, задействовав инструментарий CayleyPy, обнаружил для Superflip решение длиной всего 47 ходов в метрике FTM. Из строгого неравенства 47<48 прямо следует, что конфигурация 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.

Пространство состояний для пятерки достигает 2,83×10⁷⁴, для шестерки — 1,57 × 10¹¹⁶, а для семерки впечатляет воображение цифрой в 1,95 × 10¹⁶⁰. Точные значения чисел Бога для этих объектов неизвестны: для 5×5×5 существуют лишь теоретические предположения без строгих доказательств.

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

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

***

Серия турниров CayleyPy на Kaggle продолжается и открыта для новых участников. В распоряжении энтузиастов предоставлены облачные GPU, открытый исходный код (заслуживший более 480 звезд на GitHub) и задачи, над которыми мировое сообщество бьется уже четыре десятка лет. Помимо строчки в зале славы и признания коллег, участников ждут символические награды: например, за куб 5×5×5 объявлен специальный приз в 10 000 рублей за нахождение траекторий короче 90 ходов.

Если вы хотите присоединиться к развитию экосистемы CayleyPy или обсудить детали алгоритмов, свяжитесь с Александром Червовым в Telegram.

 

Источник