Функционирует при финансовой поддержке Федерального агентства по печати и массовым коммуникациям (Роспечать)

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

Пример стратегии DeepCube, ход 17 из 30

S. McAleer et al. / ArXiv, 2018

Новая система искусственного интеллекта 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 секунды.

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

Нашли опечатку? Выделите фрагмент и нажмите Ctrl+Enter.