ИИ учится собирать кубик Рубика — быстро!

Да, это еще одна новость о том, что ИИ осваивает игру или головоломку, но она удивительна. Научившись решать логические задачи, ИИ превращается в производительность, которая, как правило, не только превосходит человека, но и не уступает ручным методам.

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

Последняя нейронная сеть, которая впечатлила, — DeepCubeA от Фореста Агостинелли, Стивена МакАлира, Александра Шмакова и Пьера Бальди из Калифорнийского университета в Ирвине. Это глубокая нейронная сеть, которая изучает ряд комбинаторных головоломок — головоломки с скользящими блоками 15, 24, 35, 48, Lights Out, Sokoban и, конечно же, кубик Рубика. Сеть изучает функцию ценности подкрепления, но делает это «в обратном направлении». То есть он начинается с решения и случайным образом удаляется от цели. По мере удаления от цели его ходы и конфигурации становятся все менее ценными, то есть они удаляются от цели. Это дает вам функцию значения для каждой конфигурации, которая затем используется в поиске A * в качестве эвристики для реальных головоломок. Это просто, прямо и в то же время умно. DeepCubeA был разработан на основе более ранней попытки, которая смоделировала себя на основе DeepMind Alpha Go. Разница, по-видимому, в том, что управляемый алгоритм A * стремится найти кратчайшее решение.
«DeepCubeA находит кратчайший путь к цели для головоломок, для которых кратчайший путь можно проверить с помощью вычислений: 60,3% времени для кубика Рубика и более 90% времени для головоломки 15, головоломки 24 и Lights Out».
Так насколько хорошо это работает?
Первое, что нужно сказать, это то, что DeepCubeA не гарантирует нахождение оптимального решения, и есть алгоритм — PDB. В тестах с этим алгоритмом DeepCubeA удалось получить 60% оптимальных решений, но 97% находятся в пределах 2 операций от оптимального. Если найти хорошие решения, то он делает это быстро — PDB потребовалось почти 4 часа, а DeepCubeA — 18 секунд.
Аналогичная хорошая производительность была получена и по другим задачам, но именно кубик Рубика, вероятно, поразит воображение. Чемпионы кубика Рубика собирают куб примерно за 50 ходов, ИИ нужно всего 20 ходов. ИИ работает быстро, но людям требуется в лучшем случае всего 5-6 секунд, включая перемещение физического куба.
Вы можете попробовать программу и посмотреть, что вы думаете о ее решении — она быстрая и может работать на скромном оборудовании. Совершенно очевидно, что здесь не используется ни один из «человеческих» алгоритмов, но это впечатляет и, кажется, может быть обобщено на целый ряд задач планирования:
«Общность основного алгоритма предполагает, что у него могут быть приложения, выходящие за рамки комбинаторных головоломок, поскольку проблемы с большими пространствами состояний и несколькими целевыми состояниями не редкость в планировании, робототехнике и естественных науках».
Одна интересная мысль — DeepCubeA узнал ценность хода, работая в обратном направлении. Он также узнал ценность движений, близких к цели, прежде чем распространять свои знания на более удаленные состояния. Могут ли люди научиться чему-то таким же образом?