Домашний ПК с 32 ГБ RAM за четыре месяца решил кубик Рубика 32768×32768×32768
У обычного кубика Рубика по девять цветных плиток с каждой стороны. Алгоритм решения включает всего семь действий. Мировой рекорд по сборке кубика человеком двумя руками составляет 3,47 секунды, среднее по пяти попыткам — 5,69 с, а робот делает это за 0,38 секунды (если кубик не разлетается на составные части, что частенько случалось из-за скорости).
Но у кубика не обязательно должны быть такие пропорции. Сам венгерский изобретатель Эрнё Рубик предложил несколько вариантов, а вообще ничто не мешает делать кубики произвольного размера. Такие головоломки гораздо сложнее решить, чем классическую.
Пользователь YouTube под ником ShellPuppy написал компьютерную программу, которая имитирует решение массивных кубиков Рубика. Самый большой кубик, который программе удалось «собрать», состоит из 32 768 плиток в высоту, ширину и глубину. Это в общей сложности 6.442.450.944 цветных квадратов. Если сделать такой кубик в реальности со стандартными размерами плиток, то он почти сравняется с дубайским небоскрёбом Бурдж-Халифа высотой 828 метров. Согласно описанию на YouTube, компьютеру понадобилось примерно 2700 часов для решения головоломки. На видео этот процесс показан в ускоренной съёмке.
ShellPuppy — американский инженер и разработчика программного обеспечения. Он говорит, что начал работу над проектом, когда посмотрел на YouTube видео с компьютером, который собирает кубик Рубика 55×55. Тогда он подумал, что он может попробовать что-то ещё более сложное. Кубик 55×55 он называет «крошечным»: «У компьютеров гораздо больше памяти и вычислительной мощности, — сказал ShellPuppy. — Поэтому я сел, быстро прикинул математику и посчитал, что можно сделать на 32 гигабайтах оперативной памяти. У меня вышло 65536×65536 (мне нравятся степени двойки)».
Разработчик начал тестировать программу, но быстро понял, что куб такого размера компьютер будет вычислять как минимум несколько лет. Причина в том числе в не очень эффективном алгоритме. Автор самокритично назвал его «абсурдно неэффективным алгоритма сортировки». Поэтому он решил остановиться на кубике в четыре раза меньшего размера, то есть 32768×32768. По его расчётам получалось, такой кубик программа должна собрать в восемь раз быстрее. ShellPuppy за выходные написал код для компьютерной симуляции кубика.
Но оставалась проблема: разработчик ничего не знал об алгоритме сборки этой симуляции: «Честно скажу, я понятия не имел, как решить кубик Рубика», — сказал он. — До сих пор я никогда не брал и не собирал настоящий кубик».
Ему пришлось делать то, что и каждый новичок, то есть смотреть учебники на YouTube и читать статьи о решении кубиков. Только его интересовали кубики необычного размера: «Мне пришлось отказаться от первых нескольких попыток, так как они не всегда приводили к удачной сборке или были слишком медленными», — сказал он. Написание кода для этой программы оказалось уже сложнее, заняв несколько вечеров и уикендов.
На видео показаны несколько первых неудачных подходов, от которых пришлось отказаться.
Очевидно, что решение виртуального кубика Рубика размером с массивный небоскрёб представляет некоторые уникальные проблемы. Согласно ShellPuppy, решение углов ничем не отличались от классического кубика 3×3×3, и поэтому их было легко решить с учётом центров. Самым сложным стало решение граней, то есть краёв массивного куба: «Решение граней было не так элегантно, — сказал автор. — Я написал алгоритм, который «работал», но уверен, что он далеко не самый эффективный. Однако эффективность не имела значения для краёв, так как их размер незначителен по сравнению с центрами».
Хотя алгоритм не самый элегантный, но программа делает свою работу и в конце концов всё-таки решает кубик. ShellPuppy говорит, что она даже масштабируема, то есть при увеличении числа компьютеров можно распаралеллить вычисления. Но вот с решением кубиков большего размера уже возникнут проблемы, потому что одновременно с вычислениями усложняется и рендеринг: «Вы словно упираетесь в стену с точки зрения сложности. Даже если у вас компьютер в 10 или 100 раз быстрее, вы просто переместите эту стену немного дальше», — сказал он.
Можно добавить, что в последнее время исследователи начали подключать к решению кубика Рубика глубокое обучение и нейросети. Недавно в научном журнале Nature публиковалось описание системы DeepCubeA, которая по некоторым параметрам оказалась эффективнее, чем традиционные методы машинного обучения для сборки кубика Рубика, основанные на базах с паттернами (pattern databases, PDB).
