У обычного кубика Рубика по девять цветных плиток с каждой стороны. Алгоритм решения включает всего семь действий. Мировой рекорд по сборке кубика человеком двумя руками составляет 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).
Комментарии (43)
FForth
27.07.2019 17:05Интересно, а как задавалась начальное расположение конфигурации кубика?
(т.к. процесс перемешивания граней кубика следует физическим процессам)
P.S. Нельзя же, наверное, просто случайно сгенерировать цвета квадратиков кубика?AC130
27.07.2019 17:29Вроде можно из любой конфигурации перейти в любую другую. Т.е. можно сгенерировать случайно, но с учётом ограничений на угловые элементы, элементы на рёбрах и остальные элементы. К примеру, элементов на рёбрах ровно 12 видов (пар цветов), они размещены на рёбрах случайно и случайно повёрнуты, элементов каждого вида N-2, где N — длина ребра кубика.
Blaine_Mono
27.07.2019 20:53+1Можно сгенерировать полностью собранный кубик, а затем случайным образом его повертеть.
Oplkill
28.07.2019 09:20+5Потратив на это 2 месяца
Blaine_Mono
29.07.2019 03:14Я думаю что случайное вращение потребует куда меньше вычислительных мощностей.
Defersa
29.07.2019 12:30С чего это? Основная проблема — перемещение данных в массивах, алгоритм «чтокудаположить» — самая мелкая часть.
Zatamon
29.07.2019 06:22Для такого большого и четного размера я бы делал
1. Проверка валидности уголков
2. С ребрышками чуть сложнее, но можно для каждой орбиты ребрышек задать случайную подстановку и по ней расположить
3. На каждой орбите одностикерных элементов проверка правильного количества каждого из цветов
Для нечетного размера еще должны быть 2 проверки у центральных ребрышек: на четность подстановки (относительно угловых) и на четность ориентации
Arris
27.07.2019 20:00-4Интересно, а какова практическая польза алгоритма сборки кубика?
funca
27.07.2019 20:48+4Спросите у розы в саду, какая в ней практическая польза. Для программистов — как минимум тренировка.
Porohovnik
27.07.2019 23:05-9<зануда_on>
Из розы можно сварить отвар(возможно лечебный, я далёк от медицины поэтому не могу точно сказать за инфу по этому поводу в интернете)
Также можно сделать духи(пользы мало, но приятный аромат, что приносит удовольствие{но некоторым он может не понравиться, да и аллергия не исключена})
Просто роза тоже приносит удовольствие, но могут быть теже побочные условия как в случае с духами…
</зануда_on>
Grox
28.07.2019 02:06+6Решение задач может приносить удовольствие и поддерживать мозг в здравии. Это если очень коротко.
tandzan
28.07.2019 02:32-15Прям IT-шный онанизм какой-то.
androidovshchik
28.07.2019 09:41+4Слушайте, у каждого свои интересы, вам доставляет удовольствие неоправданное поругательство чужих занятий/хобби? Подумайте о себе в первую очередь
Gamliel_Fishkin
28.07.2019 03:13+5Кто-то много раз в день отжимается, или поднимает гантели или штангу, или делает что-то подобное; он тренирует свои мышцы. А кто-то занимается чем-то вроде описанного в статье; он тренирует свой мозг.
Arris
28.07.2019 14:17-2От розы в саду как раз есть практическая польза. Варенье, запах, лекарства.
Вопрос в другом: ок, алгоритм как тренировка. А в чем практическая польза выполнения задачи по решению кубика?sovaz1997
28.07.2019 18:23+1Подобные видео при случае могут набрать миллионы просмотров на YouTube. А если серьезно, то человеку это было интересно. Не надо везде искать практическую пользу. Какая практическая польза катания на аттракционах?
engine9
28.07.2019 18:18Человек просто поинтересовался практической целью. А вы повели себя несколько высокомерно. А хабрасообщество подкинуло минусцов. Ни за что!
Избегайте такого поведения, люди.Arris
30.07.2019 20:09Это было предсказуемо, на самом-то деле.
Коллективное бессознательное хабросообщества очень нервно реагирует на вопросы о практической пользе гиковских выдумок. Они самоценны и эта самоценность зачастую довлеет над здравым смыслом.
+ предрассудки. Те самые, которые перед рассудком.
P.S. как нахватать миллион минусов? Да очень просто: найти у этого коллективного бессознательного больную мозоль и на неё наступить. В силу некоторых особенностей окружающего мира таких больных мозолей много. И больные мозоли у разных людей пересекаются, образуя группы мозолей, а там и до супермозолей доходит.
P.P.S Это потянуло бы на юмористическую статью, но до первого апреля далеко, да и психологического образования мне не хватает.
DmitrySpb79
27.07.2019 21:55+34 месяца обсчитывать кубик рубика, невозможный в реальности. Завидую человеку, способному так заморочиться, я так не могу :)))
Внутренний голос подсказывает, что решай он на GPU, было бы разы быстрее, но может ошибаюсь.
TimsTims
28.07.2019 01:16Там он пишет, что часть мощностей упиралось в рендеринг (хотя зачем он здесь? можно же было просто логи писать, а потом по логам видео сделать). А рендеринг, я думаю, сделан как минимум с использованием GPU.
sovaz1997
28.07.2019 18:21Тоже думаю, найти правильную последовательность ходов, а потом в отдельной программе рендерить. Думаю, так намного быстрее будет (возможно, даже, не на 1 порядок). Все-таки, рендеринг такого числа полигонов может много съедать.
KvanTTT
29.07.2019 00:15Внутренний голос подсказывает, что решай он на GPU, было бы разы быстрее, но может ошибаюсь.
Если там много ветвлений, то польза от GPU сомнительно. А их там скорее всего много, на каждом ходу. И каждый следующий ход зависит от предыдущего, поэтому спекулятивное выполнение здесь вряд ли сработает.
tmnhy
27.07.2019 23:55+2Алгоритм решения включает всего семь действий.
Вот так, умудриться написать, обо всём и одновременно ни о чём. Что за действия, что за алгоритм.
Для CFOP возможных комбинаций по этапам — 41 (F2L) x 57 (OLL) x 21 (PLL), для каждого варианта каждого этапа — свой алгоритм.
Да, можно одним алгоритмом (той же лямбдой, для примера) собрать кубик, но это далеко не оптимально и совсем не быстро.
aleksandrzhmydyak
28.07.2019 10:10У меня вышло 65536?65536 (мне нравятся степени двойки)».
Поэтому он решил остановиться на кубике в четыре раза меньшего размера, то есть 32768?32768.
Только меня это смутило?
nidalee
28.07.2019 10:20Вас смутило «в четыре раза»? Это правильная формулировка. В два раза меньший кубик был бы уменьшен по одной стороне. В четыре раза — по двум (два раза в два раза).
Как альтернативный пример можно привести разрешения экрана FullHD и 4K.
MaximChistov
28.07.2019 11:00+3ну вообще-то в 8 раз)
nidalee
28.07.2019 11:12Ах да, то же 3D, там три стороны. Ну для сравнения 65536?65536 и 32768?32768 — в 4 :)
osmanpasha
28.07.2019 12:45+8Важен же не объем кубика, цветные клетки только на поверхности, а поверхность уменьшилась в 4 раза
aleksandrzhmydyak
28.07.2019 12:03+2Да согласен, для пользователя важен не объем а количество элементов, но мозг на слова «размер кубика» среагировал однозначно: a?, — а комментарий удалять нельзя.
barkalov
28.07.2019 10:20Тогда мы бы увидели эту статью сильно позже. Четыре месяца занимать компьютер и ждать — и так немало.
DmitrySpb79
28.07.2019 12:56+3> Четыре месяца занимать компьютер и ждать — и так немало.
Мне это напомнило старый анекдот про многозадачность Windows :)
Zatamon
29.07.2019 06:21+1А меня нет
Площадь поверхности — в 4 раза меньше, а, как, например, мой алгоритм сборки, так и объем памяти, необходимый для хранения, пропорционален именно площади поверхности
berez
28.07.2019 21:18Сам венгерский изобретатель Эрнё Рубик предложил несколько вариантов, а вообще ничто не мешает делать кубики произвольного размера.
Вообще-то сделать кубик произвольного размера мешает геометрия. Если сделать кубик больше, чем 5х5х5, то при повороте слоя на 45 градусов угловые кубики просто вывалятся.Zatamon
29.07.2019 06:17+1Не смешите мои тапочки. Физические выпускаются вплоть кажется до 17х17х17 (стоят порядка 50-60 тыр), а 6х6х6 у меня есть.
У оной проблемы как минимум 2 решения:1. Чуть изменяем пропорции малых квадратиков так, что крайние чуть больше 2. хитрые металлические штыри все подлдерживающие (как у кубика 2х2х4)
Zatamon
29.07.2019 06:25-1Статья производит впечатление абсолютной бессмысленности действий этого ютубе-блогера
Собрать компом кубик по чужому алгоритму — дело абсолютно бессмысленное и не требует высокой квалификации ни программиста ни математика.
Вот, если он запутыывание умное делал, тогда было бы лучше об этом написать
fdroid
Какой процессор использовался?
valera5505
8700k @ 5ghz