Нейросеть собирает кубик Рубика 4×4×4 и 5×5×5 короче 1000+ командКак это работает

Ролик: та же история за 12 минут

Статья идёт по сюжету ролика, сцена за сценой, и подробнее его. Под схемами — ссылка на этот момент видео.

Статья: A Machine Learning Approach That Beats Large Rubik's Cubes, arXiv 2502.13266, 18 февраля 2025. Лабиринт, компас, фронт и отряд — образы для объяснения; в статье это граф Кэли, нейросеть, лучевой поиск и ансамбль.

Вопрос: собрать кубик легко, собрать за минимум ходов — трудно

Кубик Рубика собирают за вечер по инструкции. Инструкция даёт длинную сборку, обычно 50–100 ходов и больше. Самая короткая сборка — отдельная задача, и для больших кубиков её до сих пор никто не умеет находить.

Два слова понадобятся дальше. Ход — поворот одной грани на четверть оборота. Позиция — то, как сейчас раскрашены грани. Поворот грани переводит кубик из одной позиции в другую. Вопрос статьи: как из данной позиции дойти до собранной за наименьшее число ходов.

Слева собранный кубик, в центре — после одного хода, справа — после 20 случайных ходов. ▶ 0:12

Почему не собрать по инструкции и не сократить лишнее? Инструкция собирает кубик слоями: сначала один слой, потом второй, потом третий, и каждый шаг временно портит и чинит уже собранное. Ходов получается в несколько раз больше минимума. Чтобы найти минимум, нужно сравнить все возможные пути, а их слишком много.

Сколько комбинаций у кубика Рубика

У обычного кубика Рубика 3×3×3 — 43 252 003 274 489 856 000 комбинаций, около 43 миллиардов миллиардов: перебрать их подряд нельзя. Поэтому собрать кубик за самое маленькое число ходов трудно.

Число складывается из деталей. У кубика 8 уголков (у каждого 3 цвета) и 12 рёбер (у каждого 2 цвета); центры граней не двигаются. Уголки можно расставить по местам 8! способами и повернуть 3⁷ способами — последний уголок поворачивается сам, когда повёрнуты остальные. Рёбра расставляются 12! способами и переворачиваются 2¹¹ способами. Половина сочетаний на настоящем кубике недостижима (без разборки нельзя поменять местами ровно две детали), поэтому произведение делится пополам.

Слева яркие только уголки, справа только рёбра. ▶ 0:34

Если проверять миллиард позиций в секунду, полный перебор обычного кубика займёт около 1370 лет: начав в 2025 году, закончим в 3395-м.

Перебор со скоростью миллиард позиций в секунду. ▶ 0:41

У больших кубиков деталей больше, и число растёт ещё быстрее. У кубика 5×5×5 позиций больше, чем атомов на Земле.

Длина полосы — число цифр в количестве позиций. ▶ 0:51

Для обычного кубика минимум всё-таки известен. Число Бога — наибольшее число ходов, которое может понадобиться самой короткой сборке. Его нашли перебором на мощных компьютерах с сокращениями за счёт симметрий: 20 ходов, если поворот на пол-оборота считать одним ходом (2010), и 26 ходов, если считать только четверти оборота (2014). Для 4×4×4 и 5×5×5 такого ответа нет.

Статья, авторы и соревнование

В 2023 году более тысячи команд программистов соревновались на Kaggle в конкурсе Santa 2023: кто соберёт головоломки, включая большие кубики, за меньшее суммарное число ходов.

Kaggle — площадка, где компании и исследователи выкладывают задачи, а команды со всего мира соревнуются в решениях. В Santa 2023 счёт был простой: сумма ходов по всем задачам, чем меньше — тем выше место. Лучшие ответы конкурса стали планкой для больших кубиков.

18 февраля 2025 года двенадцать авторов проекта CayleyPy выложили статью «A Machine Learning Approach That Beats Large Rubik's Cubes». Их программа обошла лучшие ответы соревнования на кубиках 4×4×4 и 5×5×5 и стала первой нейросетью, которая собирает кубики больше обычного.

Авторы в порядке статьи. Автор этого блога — один из соавторов.

Конкурс и результат: средняя длина решения, ходов. ▶ 1:17

Кубик как лабиринт позиций

Главный образ: каждая позиция — комната, каждый ход — дверь в соседнюю комнату, собранный кубик — выход.

Комната — это одна раскраска кубика. Повернули грань — перешли в соседнюю комнату. Комната соседняя, потому что раскраска отличается одним поворотом.

Справа та же раскраска, только правая грань повернулась. ▶ 1:35

Из любой комнаты обычного кубика ведут 12 дверей: у кубика 6 граней, каждую можно повернуть по часовой стрелке или против.

Все 12 соседних комнат: за каждой дверью своя раскраска. ▶ 1:45

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

Ниже — игрушечный лабиринт на 40 комнат. В настоящем 4,3·10¹⁹ комнат, у каждой 12 дверей, поэтому нарисовать его нельзя; на маленьком видно, как работает каждая часть программы.

Выход слева, старт справа, толстые линии — стены. ▶ 2:12

Поставим каждую комнату на высоту, равную числу ходов до выхода. Получится рельеф: выход в самой низкой точке, а кратчайший путь из любой комнаты — спуск по ступеням, где каждая следующая на одну ниже. Если бы высота каждой комнаты была известна, собрать кубик было бы просто: всегда шагать вниз. Высоту никто не знает — её и будет угадывать нейросеть.

Рельеф того же лабиринта. ▶ 1:59

Прогулка от выхода

Карты лабиринта ни у кого нет: комнат слишком много. Поэтому авторы идут от обратного.

Встают у выхода и делают случайные ходы — это прогулка, то есть перемешивание собранного кубика. После каждого хода записывают раскраску и сколько ходов уже сделано. Такие пары «позиция → число ходов» компьютер делает миллиардами прямо во время обучения: прогулка стоит почти ничего, и карта лабиринта для неё не нужна.

Слева прогулка по лабиринту, справа — записи, на которых учится нейросеть. ▶ 2:44

Компас: нейросеть, которая угадывает расстояние до выхода

Из прогулок учится компас: он смотрит на раскраску и угадывает, сколько ходов до выхода, то есть высоту комнаты на рельефе.

Компас — обычная нейросеть: раскраска на входе, число на выходе.

Компас ошибается, причём в большую сторону: прогулка петляет, и ходов в ней больше, чем на кратчайшем пути. На схеме прогулка дошла до комнаты за 8 ходов, а настоящий путь до неё — 2. Но чем дальше ушла прогулка, тем в среднем дальше комната от выхода, поэтому компас верно показывает направление: где число меньше, там ближе к выходу. Среднее число ходов прогулки до позиции авторы называют диффузионным расстоянием.

Почему компас завышает. ▶ 3:06

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

Фронт: почему одного пути мало

Если идти одним путём туда, куда показывает компас, одна ошибка компаса заводит в тупик.

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

Одиночный путь по компасу. ▶ 3:37

Поэтому сборщик идёт фронтом — в статье это лучевой поиск. Фронт — несколько комнат сразу. На каждом шаге сборщик открывает все двери из всех комнат фронта, компас оценивает новых соседей, и на следующий шаг остаются только самые многообещающие. Сколько комнат держать, задаёт ширина фронта; у авторов она доходит до 2²⁴ ≈ 16 млн. Если компас ошибся в одной комнате, рядом во фронте есть другие, и путь не обрывается.

Тот же компас, фронт шириной 3. ▶ 4:09

Отряд: несколько компасов и самый короткий ответ

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

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

Три компаса с разными ошибками на одном лабиринте. ▶ 4:36

Результаты

Три кубика — три истории.

Обычный кубик 3×3×3. Сборщик находит самый короткий из возможных путей в 98 случаях из 100. Прошлые лучшие нейросети — DeepCubeA (2019) и EfficientCube (2023) — в 60 и 70.

98 из 100 задач — кратчайший путь (точнее, 98,4 % на 1000 позиций из работы DeepCubeA). ▶ 4:43

Кубик 4×4×4. Путь сборщика в среднем на 7 ходов короче, чем у лучших команд соревнования: 46,5 против 53,5. Это меньше гипотетического предела в 48 ходов.

Кубик 5×5×5. Сборщик короче лучших команд в каждой из 19 задач соревнования: 92,2 хода против 96,6 в среднем.

19 из 19. ▶ 5:02

Таблица I статьи.

Почему: ширина фронта

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

На схеме один и тот же компас при ширине 1 заходит в тупик, при ширине 2 находит путь в 11 ходов, при ширине 3 — кратчайший, в 9. Пути посчитаны настоящим лучевым поиском. Цена ширины — время: чем шире фронт, тем больше комнат он осматривает.

Тот же компас, разная ширина фронта. ▶ 5:31

У авторов на кубике 4×4×4 фронт шире в 256 раз укоротил путь с 60 ходов до 50, и каждое удвоение ширины срезало примерно одинаковое число ходов.

Ширина фронта и средний путь на кубике 4×4×4, ходов. Таблица III статьи.

Почему: отряд

Для кубика 5×5×5 авторы обучили 69 компасов. На каждой задаче побеждает тот, чей путь короче, и в итоговые ответы вошли пути 10 из них.

Даже слабые компасы оказались нужны: каждый выиграл одну-две трудные задачи. Вместе отряд находит путь до 8 ходов короче, чем лучший из компасов в одиночку. А самый первый компас для кубика 4×4×4 один обогнал все лучшие ответы соревнования — и всё равно не вошёл в итог: другие вместе оказались короче.

69 компасов для 5×5×5, подсвечены 10, чьи пути вошли в ответ. Какие именно — схема, в статье это рисунок 3. ▶ 6:02

Неожиданное

Три наблюдения, которые авторы называют неожиданными.

Данные, размер сети, время. ▶ 6:37

1. 1
   Данных больше — не лучше

   Больше 8 млрд позиций компас почти не улучшают: 4, 8 и 16 млрд дают средний путь 55,4, 55,1 и 55,8 хода на кубике 4×4×4
2. 2
   Маленький компас точнее

   4 млн настроек против 14,7 млн у прошлых сетей — почти вчетверо меньше и всё равно точнее; даже однослойная сеть даёт 90,4 % кратчайших путей
3. 3
   Быстрее

   Обучение — 4 ч 40 мин вместо 86 ч 25 мин; сборка кубика на том же компьютере и с той же шириной фронта — 10,9 с против 287,8 с, примерно в 26 раз быстрее

Главное

Вопрос был: можно ли найти короткую сборку огромного кубика, если все позиции не перебрать? Можно.

Для этого хватает трёх частей: компас учится на случайных прогулках от выхода, широкий фронт прощает ему ошибки, а отряд из разных компасов выбирает самый короткий путь. Про сам кубик сборщик ничего не знает — только комнаты и двери, поэтому годится и для других лабиринтов.

Формально: тот же путь языком статьи

Вторая часть ролика: те же шаги формулами.

Позиция — перестановка: как тасовка колоды, карты те же, порядок другой. Показаны 9 наклеек из 54. ▶ 8:15

Один шаг лучевого поиска: как отбор в турнире, дальше проходят лучшие. ▶ 9:39

Схема лучевого поиска в несколько строк; полный код на PyTorch авторы выложили вместе со статьёй.

def beam_search(start, model, W, steps=200):
    front = [start]
    for _ in range(steps):
        nbrs = unique(move(v) for v in front for move in MOVES)
        if SOLVED in nbrs: return True
        front = sorted(nbrs, key=model)[:W]   # W лучших по компасу
    return False

Где это пригодится

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

Кто и когда, что доказано

1. 1
   1974

   Эрнё Рубик придумал кубик
2. 2
   2010

   Доказано: любую позицию 3×3×3 можно собрать за 20 ходов, если поворот на пол-оборота считать одним ходом
3. 3
   2014

   Доказано: за 26 ходов, если считать только четверти оборота
4. 4
   2019

   Нейросеть DeepCubeA из Калифорнийского университета в Ирвайне впервые собрала обычный кубик без подсказок человека
5. 5
   2023

   Соревнование Kaggle Santa: 1000+ команд собирают большие кубики
6. 6
   2025

   Статья CayleyPy: первая нейросеть, которая обходит всех на 4×4×4 и 5×5×5

Это эксперимент, а не доказательство: числа измерены на наборах задач из прошлых работ и из соревнования, а кратчайшие пути для больших кубиков неизвестны. Средний путь 46,5 хода на кубике 4×4×4 ниже гипотетического предела в 48 ходов, но сама гипотеза не доказана. В тексте статьи несколько чисел расходятся: доля кратчайших путей на обычном кубике названа то 98,4 %, то 97,6 %, а число нейросетей в отряде для 4×4×4 ниже 48 ходов — то 29, то 6.

Частые вопросы