Придуманный в 1974 году кубик Рубика — одна из самых популярных головоломок. Люди собирают ее с закрытыми глазами, за несколько секунд на скорость, или даже жонглируя тремя кубами сразу. Компьютерные алгоритмы-мастера в собирании кубика Рубика тоже есть, но все они создавались людьми. Сам изобретатель головоломки Эрне Рубик представил первый «автоматический решатель» через месяц после дебюта игрушки.

В Университете Калифорнии пошли другим путем: команда во главе со Стивеном Макалером помогла ИИ-алгоритму самостоятельно научиться собирать головоломку. Препринт работы опубликован на сайте Arxiv.

Как указывает MIT Technology Review, на деле задача вышла сложнее, чем это может показаться со стороны.

Создателям алгоритма DeepCube потребовалось изобрести новую методику обучения.

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

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

Макалер и коллеги предложили другой метод обучения, который он называет «автодидактической итерацией». Он помогает оценить выгоду каждого поворота куба с помощью «обратного инжиниринга». Машина оценивает, сколько поворотов нужно, чтобы из собранного Кубика Рубика получить нынешний вариант. И если движений стало меньше, значит, алгоритм продвинулся в решении головоломки. Это позволяет ИИ самому выявлять паттерны, которые таят в себе выгоду. В программах, которые обучены людьми, эти промежуточные стадии задавали их создатели.

Теоретически минимальное число поворотов, чтобы собрать кубик Рубика из любого начального положения, — 26.

«Алгоритм смог собрать 100% случайным образом развернутых кубиков, затратив на это в среднем по 30 движений — это меньше либо наравне с достижениями других алгоритмов, которые натренировали люди», — указывает Макалер.

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

На прошлой неделе стартап Google DeepMind научил нейросеть еще одной сверхсложной задаче — реконструировать трехмерные пространства и объекты по рисункам, фотографиям или даже наброскам. Можно сказать, что у ИИ появилось воображение.