ИИ впервые без участия человека научился собирать кубик Рубика

Специалисты Калифорнийского университета представили алгоритм DeepCube, который умеет определять оптимальный способ решения головоломки. Они разработали новый метод машинного обучения — метод автодидактических итераций (autodidactic iteration, ADI). В этом случае алгоритм сам выстраивает для себя систему вознаграждений.

DeepCube собирает кубик Рубика в 100 % случаев из произвольной позиции примерно за 30 шагов. Примерно такой же уровень показывают модели, натренированные человеком.

В чём была проблема?

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

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

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

Ученые работают над применением метода к другим сложным комбинаторным задачам, например, к предсказанию третичной структуры белка.

Предыдущий барьер — игру в Го — технологии машинного обучения в лице алгоритма AlphaGo преодолели в 2016 году. В апреле 2018 года этот успех повторил китайский ИИ Golaxy.