Нейросеть за два дня научилась искать кратчайшее решение кубика Рубика и пятнашек. Но иногда тратила на решение кубика в три раза больше времени, чем лучший в мире человек-спидкубер

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

Число стартовых состояний, которые может принимать «разобранный» кубик, составляет 4.3$\times$10¹⁹. В 2010 году группа математиков показала, что кубик любой конфигурации может быть решен не более чем за 20 ходов, а несколько лет назад группа Стивена Макалира создала алгоритм машинного обучения DeepCube, который за 44 часа научился решать кубик Рубика в среднем за 30 ходов.  Разработка алгоритмов для выполнения подобных задач может помочь разобраться с самыми разнообразными проблемами сортировки — например, в сворачивании молекул белка.

Искусственная нейронная сеть DeepCubeA, новая версия DeepCube от той же исследовательской группы, комбинирует технологии глубокого обучения с подкреплением и деревьев принятия решений. DeepCubeA может найти кратчайший алгоритм сборки кубика Рубика, при этом используя меньшую вычислительную мощность и занимая меньше памяти, чем традиционные алгоритмы. Он находит его, двигаясь в обратном направлении от цели. Иными словами, он «рассматривает» уже решенную головоломку и пытается «разобрать» ее до состояния, с которыми имеет дело, кратчайшим путем. Потратив два дня на обучение, DeepCubeA собрал все кубики Рубика на тестах, в 60,3% случаев избрав наикратчайшее решение. На сборку классического кубика Рубика в самой худшей ее попытке потребовалось 24 секунды. Это в несколько раз дольше, чем время, показанное в 2019 году чемпионом-человеком — тот собрал свой кубик за 6,78 секунды (а неофициальные результаты, показанные лучшими спидкуберами, составляют менее 4 секунд),— но в лучших своих попытках машина справлялась буквально за секунду.

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

Кроме этого, алгоритм научился решать и другие головоломки подобного типа: пятнашки на 15, 24, 35 и 48 костей (число возможных состояний, соответственно, 1$\times$10¹³, 7,7$\times$10²⁴, 1,8$\times$10⁴¹ и 3$\times$10⁶²), а также компьютерные Lights Out и Sokoban.

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

Текст подготовлен участницей мастерской научной журналистики летней школы «Летняя школа»

 Екатерина Заикина