CayleyPy применяет нейросети к кубикам Рубика, где число Бога неизвестно

Кубик Рубика 3×3×3 имеет около 4,3×10^19 допустимых состояний, и с 2010 года известно, что любое из них собирается не более чем за 20 ходов в метрике HTM. Этот результат Томас Рокицки с коллегами получил полным разбором пространства состояний. Для кубиков 4×4×4 и 5×5×5, биг-кубов и мегаминкса точный диаметр графа Кэли до сих пор неизвестен. Проект CayleyPy пробует подойти к этим головоломкам с другой стороны: нейросетевым поиском, а не исчерпывающим перебором. Разбор пайплайна и результатов соревнований опубликовал на Habr один из участников команды.

Головоломка как граф

Формализация простая. Вершины графа Кэли — допустимые состояния головоломки, рёбра — допустимые ходы. Сборка за минимальное число ходов превращается в задачу кратчайшего пути от текущей вершины до собранного состояния. Диаметр графа, то есть максимум кратчайших расстояний по всем парам вершин, и есть «число Бога».

Для 3×3×3 такой расчёт был возможен, хотя и потребовал серьёзных вычислительных ресурсов и симметрий для сокращения пространства. С ростом размера головоломки картина меняется. У 4×4×4 порядка 7,4×10^45 состояний, у 5×5×5 около 2,8×10^74. Полный обход графа здесь невозможен. Остаются эвристики, оценки сверху и снизу и поиск субоптимальных решений, которые постепенно сокращают разрыв с неизвестным оптимумом.

Что делает CayleyPy

CayleyPy — открытая библиотека, вокруг которой выстроена серия соревнований на Kaggle. Задача в них — находить оптимальные и субоптимальные пути в графах Кэли с огромным числом вершин. Участники отправляют решения, платформа проверяет их и ранжирует по длине найденных путей. Для исследователей это бесплатная проверка идей на общем бенчмарке, для организаторов — способ собрать много разных подходов к одной математической задаче.

По анонсу, в статье автор разбирает три вещи:

• архитектуру нейросетевого пайплайна CayleyPy;
• результаты уже завершившихся конкурсов;
• условия текущих контестов для больших кубов, в которых он участвует как член команды.

Цифр по длинам найденных путей и местам команд в доступном фрагменте нет, поэтому оценивать, насколько нейросетевой подход обходит классический поиск, придётся по полному тексту. Заголовок оригинала утверждает именно это: нейросеть превосходит классические методы. Какие метрики и какие базовые алгоритмы взяты для сравнения, из анонса не следует.

Почему подход важен за пределами кубиков

Общая схема здесь хорошо известна: нейросеть учится оценивать расстояние до цели, а алгоритм поиска использует эту оценку, чтобы не раскрывать лишние ветки. Так устроены и более ранние работы по решению кубика Рубика обучением с подкреплением. Ценность в том, что граф Кэли — чистая математическая лаборатория. У неё есть точные ответы для малых случаев, масштабируемая сложность и однозначная метрика качества. Если метод работает на 3×3×3, его можно проверять на 4×4×4 и дальше, наблюдая, где он ломается.

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

Что с этим делать практикующему инженеру

Если вы работаете с поиском и эвристиками, открытый репозиторий CayleyPy на GitHub и контесты на Kaggle — готовая площадка для проверки собственных идей на задаче, где ответ можно измерить числом ходов. Начать разумно с малых головоломок, где диаметр известен, и сверять нейросетевую оценку расстояния с точным значением. Затем переходить к большим кубам, где соревнуются уже длины найденных решений.

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