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

Новая система искусственного интеллекта DeepCube самостоятельно за 44 часа научилась собирать кубик Рубика. Теперь программа решает головоломку не хуже систем, опирающихся на знания человека, сообщает Gizmodo.

Обновлено: в июле 2019 года статья опубликована в Nature.

Несмотря на то, что кубик Рубика был изобретен еще в 1974 году, головоломка до сих пор пользуется большой популярностью. Регулярно проводятся соревнования, в которых люди и роботы собирают кубик на скорость. Считается, что с этой задачей можно справиться не более чем за 20 ходов — это нижняя граница алгоритма Бога, который позволяет получить оптимальное решение головоломки, начиная с любой конфигурации (при поворотах на 180 градусов).

Программисты под руководством Стивена Макалира (Stephen McAleer) создали систему искусственного интеллекта, которая способна собрать кубик Рубика в среднем за 30 ходов. Примерно столько же движений используют люди, профессионально занимающиеся спидкубингом. В основе программы лежит глубокое обучение с подкреплением — его суть заключается в том, что управляемый алгоритмом агент находится в среде и, выполняя различные действия, может получать за них награду. Таким образом, методом проб и ошибок он учится выполнять последовательность действий, приводящую к наибольшей награде и тем самым постепенно приближается к нужному создателям результату.

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

В процессе обучения DeepCube за 44 часа решила около миллионов кубиков Рубика (включая повторы). Алгоритм использовал 32-ядерный сервер Intel Xeon E5-2620 с тремя видеокартами NVIDIA Titan XP. Система, как пишут авторы, получила достаточное количество знаний во время тренировки: например, она самостоятельно нашла стратегию, которую используют продвинутые спидкуберы — сопоставление сторон и углов головоломки перед тем, как их переместить в нужную позицию. «Наш алгоритм способен решить 100 кубиков со случайной конфигурацией, достигнув медианы в 30 шагов — это меньший или почти такой же результат, как у алгоритмов, использующих человеческие знания», — комментирует Макалир.

Некоторые конфигурации кубика Рубика вызвали трудности у алгоритма, поэтому в будущем разработчики надеются улучшить его работу. Кроме того, сейчас DeepCube использовался для того, чтобы решить головоломку 3×3×3, однако он может быть также обучен и для кубика 4×4×4.

Сегодняшний рекорд по скоростной сборке кубика Рубика принадлежит австралийцу Феликсу Земдегсу, который в мае 2018 года собрал головоломку за 4,22 секунды. Среди машин неофициальным чемпионом считается робот Бена Каца и Джареда Ди Карло, который способен собрать кубик Рубика за 0,38 секунды.

Кристина Уласович