Нейросеть CayleyPy победила классический алгоритм: как ИИ решает задачу кубика 4x4 и мегаминкса

# Нейросеть CayleyPy победила классический алгоритм: как ИИ решает задачу кубика 4x4 и мегаминкса

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

Проблема неизвестного диаметра графа

Для классического кубика Рубика 3×3×3 точное решение было найдено в 2010 году Томасом Рокицки и его коллегами. В метрике Half-Turn Metric (HTM, полуобороты) оказалось, что в худшем случае достаточно 20 ходов для сборки любого положения. Это число получило название «число Бога». Однако, как только мы переходим к кубикам большего размера, картина меняется.

Для кубиков 4×4×4, 5×5×5 и более сложных форм, таких как мегаминкс, точное значение диаметра графа Кэли (максимальное расстояние от собранных состояний до любых других) остается неизвестным. Пространство состояний здесь астрономически велико. Например, у кубика 4×4×4 оно составляет около 7,4×10⁴⁵ конфигураций. У мегаминкса цифра достигает порядка 10⁶⁸. Перебрать их методом «грубой силы» или даже классическим поиском с симметричной редукцией в обозримом будущем невозможно.

Архитектура CayleyPy: от случайного блуждания к провидению

Проект CayleyPy, развивающий серию соревнований на платформе Kaggle, предлагает иной подход. Вместо создания гигантских предвычисленных таблиц (Pattern Databases), которые занимают терабайты памяти, команда использует обучаемую нейросетевую эвристику. Процесс обучения проходит в три этапа:

1. Случайные блуждания и генерация датасета. Исходный собранный кубик подвергается тысячам случайных перемешиваний. Для каждого достигнутого состояния фиксируется не только его вид, но и количество шагов, совершенных от целевой точки. Фактически создается карта графа, где узлы — состояния, а вес ребер — количество ходов. 2. Обучение нейросети. На полученных данных обучается модель (в проекте используется архитектура ResMLP). Сеть принимает на вход текущее состояние головоломки и предсказывает, насколько оно далеко от собранного состояния. Важно отметить: нейросеть не запоминает последовательности ходов, она учится оценивать «дальность» любого момента. 3. Поиск пути методом лучевого поиска (Beam Search). Поскольку нейросети могут ошибаться, слепо доверять им нельзя. В решении используется алгоритм Beam Search. Он рассматривает не один лучший вариант на каждом шаге, а узкий конус вероятных вариантов (например, топ-5). Нейросеть оценивает каждый из них, и процесс фильтрует варианты, оставляя наиболее перспективные направления до тех пор, пока цель не будет достигнута.

Эксперименты показали, что бесконечное увеличение обучающей выборки после определенного момента перестает давать прирост качества. Однако расширение ширины луча поиска напрямую и стабильно сокращает длину решения.

Победа над традиционным поиском: результаты на кубиках 4x4 и мегаминксе

Первым крупным тестом стала задача решения кубика 4×4×4. В финальном зачете команды CayleyPy возглавили лидерборд, обойдя Томаса Рокицки. Средняя длина найденных решений составила 46,51 хода, а итоговый скор — 44 810. Это подтвердило, что метод сочетания нейросетевой оценки и лучевого поиска способен находить пути, математически близкие к теоретическому пределу, превосходя классические алгоритмы IDA* и BFS.

Более впечатляющим стало событие в конкурсе по мегаминксу. Здесь классическое лучшее решение знаменитой конфигурации «Superflip» (симметричное состояние, где все ребра перевернуты) составляло 55 ходов. Новая модель CayleyPy нашла путь длиной всего 47 ходов.

Этот результат имеет глубокое теоретическое значение. Известная нижняя граница диаметра графа мегаминкса равна 48 ходам. Найдя решение за 47 ходов, команда автоматически доказала, что конфигурация Superflip не является самой далекой точкой на карте состояний мегаминкса. Как отметил Томас Рокицки, это первый крупный и значимый прорыв в применении ИИ к теории механических головоломок.

Биг-кубы и будущее комбинаторики

На данный момент серия соревнований продолжается для кубиков 5×5×5, 6×6×6 и 7×7×7. Пространство состояний последних уже перевычисляет 10¹¹⁶. Здесь традиционные методы поиска практически бессильны.

Однако в обучении с подкреплением (Reinforcement Learning) для таких задач существует проблема «разреженного сигнала»: агент не получает обратной связи, пока не соберет куб полностью, а путь к цели может быть сотен шагов. CayleyPy решает эту проблему, предоставляя непрерывный сигнал: нейросеть на каждом шаге говорит, приближается ли текущее состояние к цели или удаляется от нее. Это позволяет градиентному поиску двигаться не вслепую, а по «наклонной плоскости» к решению.

На текущий момент в рамках проекта нет крупных денежных призов, кроме символических наград за рекорды (например, 10 000 рублей за решение 5×5×5 короче 90 ходов). Главный приз — строчка в истории алгоритмов и доступ к задачам, которые не были решены за последние сорок лет.

*«Мы не заменяем математику, мы предоставляем инструмент, который позволяет ей оперировать в пространствах, где человеческий разум и классический алгоритм бессильны»* — так можно охарактеризовать суть подхода CayleyPy.

Соревнования доступны на платформе Kaggle. Участники получают доступ к мощным аппаратным ускорителям GPU и открытому коду проекта. Это уникальная возможность проверить свои идеи на задачах, которые десятилетия назад считались непреодолимым барьером для компьютерной науки.