Разложите кубик Рубика, и вы создадите одну из 43 квинтиллионов возможных комбинаций из 54 разноцветных квадратных наклеек. Но эта часть - запутать его - проста. Решить его, как известно любому любителю, сложно.
Люди, конечно, способны решить ее, причем делают это поразительно быстро. Лучшие, например, чемпион 2019 года Филипп Вейер, решают ее менее чем за 7 секунд. А те, кто специализируется на том, чтобы вернуть перепутанный кубик к граням чистого красного, синего, зеленого, белого, желтого и оранжевого цветов, делают это примерно за 50 ходов.
В то время как люди решали эти головоломки десятилетиями, настал черед искусственного интеллекта: ИИ теперь может быстро вычислить очень эффективное решение кубика-шаблона. И в 60 процентах случаев этот ИИ вычислит решение, включающее наименьшее количество возможных ходов, которых обычно около 20 или около того. На самом деле, в мире кубика Рубика существует концепция, известная как алгоритм Бога, который был бы способом решения кубика, если бы всезнающее божество посмотрело на него и просто знало, как решить его за наименьшее количество возможных ходов. "Мы близки к алгоритму Бога", - говорит Пьер Бальди, профессор информатики из Калифорнийского университета в Ирвайне и старший автор нового исследования, описывающего бота для решения кубика Рубика, опубликованного в журнале Nature Machine Intelligence.
Прежде чем вы начнете представлять себе робота с механическими пальцами, манипулирующего кубиком и поднимающегося на пьедестал почета на соревнованиях по спидкубингу, подумайте о том, что это создание ИИ - всего лишь программное обеспечение. Он решает кубик виртуально. На самом деле, традиция использования игр в качестве задач для систем искусственного интеллекта насчитывает десятилетия, и они уже могут доминировать в таких состязаниях, как шахматы, го и многопользовательский техасский холдем-покер.
Когда речь идет о головоломке Эрно Рубика 1974 года, традиционные программы уже смогли найти решение для кубика, используя вычисления на основе правил, но новость здесь в том, что теперь это может сделать тип искусственного интеллекта, называемый глубоким обучением с подкреплением.
Поскольку кубик Рубика настолько сложен, нельзя ожидать, что система искусственного интеллекта разгадает его без обучения. А просто виртуально крутить и переворачивать его и пытаться решить его случайным образом тоже не получится. Вместо этого исследователи, стоящие за проектом, начали с маленьких шагов - с кубика, который очень близок к решению, и для его завершения нужно всего несколько движений. По словам Балди, в процессе обучения они продвигались по пути "скремблирования по возрастающей сложности".
"Это как ребенок", - говорит он. "Сначала мы даем ему легкие задачи, а затем постепенно усложняем их".
Так как же работает этот алгоритм - насколько он хорош для спидкубера? Версия алгоритма команды Балди доступна в Интернете, и вы можете попробовать ее здесь. Этой версии требуется всего около секунды, чтобы изучить кубик и выдать решение. Его решение будет значительно меньше, чем 50 ходов или около того, которые человек обычно использует для решения кубика на соревнованиях, но вероятность того, что решение будет идеально минимальным, меньше. Между тем, версия ИИ, о которой исследователи сообщают в своей статье, более мощная, но немного медленнее: она может выдать кратчайшее возможное решение в 60% случаев, но вычислительная задержка для этого составляет около 20 секунд, по словам Балди. Тем не менее, это намного, намного быстрее, чем человеку с кубиком в руках, чтобы найти решение, включающее минимальное количество ходов.
Для сравнения вспомните, что люди могут сделать это примерно за 6 секунд, но поскольку они работают в реальном мире, им приходится физически крутить и поворачивать его. Спидкуберы действительно могут решить кубик, используя меньше ходов, чем 50, но более быстрый по времени метод на самом деле для них не в том, чтобы сделать как можно меньше поворотов.
Кубик - элегантная головоломка, потому что, хотя существует квинтиллион различных способов испортить его и множество путей для его решения, есть только один пункт назначения: решенный кубик.
Инженеры-программисты используют игры в качестве основы для построения алгоритмов ИИ, но также следят за тем, как программное обеспечение, способное играть в игры, может быть применено в реальных ситуациях. В этом случае, по словам Балди, возможно применение в области робототехники. Например, он представляет себе робота, который убирает вашу кухню. Как и куб, кухня может быть захламлена, или загрязнена, по-разному, но есть только одно решенное состояние: чистое место для приготовления пищи, где все на своих местах. Алгоритмы, подобные решателю кубиков, могут быть применены к ситуациям, подобным этой. "Если робот будет перемещать предметы случайным образом - возьмет грязную посуду и будет беспорядочно перемещать ее по кухне - кухня никогда не станет чистой", - говорит он. "Вы [можете] увидеть сходство между некоторыми задачами роботов и тем, что мы сделали".