Домашний ПК с 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).
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 44

      0
      Какой процессор использовался?
      0
      Интересно, а как задавалась начальное расположение конфигурации кубика?
      (т.к. процесс перемешивания граней кубика следует физическим процессам)

      P.S. Нельзя же, наверное, просто случайно сгенерировать цвета квадратиков кубика?
        +1
        конечно. если случайно, легко можно получить невозможный кубик
          0

          Вроде можно из любой конфигурации перейти в любую другую. Т.е. можно сгенерировать случайно, но с учётом ограничений на угловые элементы, элементы на рёбрах и остальные элементы. К примеру, элементов на рёбрах ровно 12 видов (пар цветов), они размещены на рёбрах случайно и случайно повёрнуты, элементов каждого вида N-2, где N — длина ребра кубика.

            +1
            Можно сгенерировать полностью собранный кубик, а затем случайным образом его повертеть.
              +5

              Потратив на это 2 месяца

                0
                Я думаю что случайное вращение потребует куда меньше вычислительных мощностей.
                  0
                  С чего это? Основная проблема — перемещение данных в массивах, алгоритм «чтокудаположить» — самая мелкая часть.
                    0

                    Я думаю, что это был сарказм :)

                0
                Для такого большого и четного размера я бы делал
                1. Проверка валидности уголков
                2. С ребрышками чуть сложнее, но можно для каждой орбиты ребрышек задать случайную подстановку и по ней расположить
                3. На каждой орбите одностикерных элементов проверка правильного количества каждого из цветов
                Для нечетного размера еще должны быть 2 проверки у центральных ребрышек: на четность подстановки (относительно угловых) и на четность ориентации
                –4
                Интересно, а какова практическая польза алгоритма сборки кубика?
                  +4

                  Спросите у розы в саду, какая в ней практическая польза. Для программистов — как минимум тренировка.

                    –9

                    <зануда_on>
                    Из розы можно сварить отвар(возможно лечебный, я далёк от медицины поэтому не могу точно сказать за инфу по этому поводу в интернете)
                    Также можно сделать духи(пользы мало, но приятный аромат, что приносит удовольствие{но некоторым он может не понравиться, да и аллергия не исключена})
                    Просто роза тоже приносит удовольствие, но могут быть теже побочные условия как в случае с духами…
                    </зануда_on>

                      +6
                      Решение задач может приносить удовольствие и поддерживать мозг в здравии. Это если очень коротко.
                        –15
                        Прям IT-шный онанизм какой-то.
                          +4
                          Слушайте, у каждого свои интересы, вам доставляет удовольствие неоправданное поругательство чужих занятий/хобби? Подумайте о себе в первую очередь
                            –5
                            Ау, але? Человек публично самоудовлетворятся вприсядку. Делает он, а стыдно мне. За 4 месяца можно было научиться писать многопоточные приложения.
                              +2
                              Так не заходите сюда. Стыдно ему))
                        +5
                        Кто-то много раз в день отжимается, или поднимает гантели или штангу, или делает что-то подобное; он тренирует свои мышцы. А кто-то занимается чем-то вроде описанного в статье; он тренирует свой мозг.
                        –1
                        От розы в саду как раз есть практическая польза. Варенье, запах, лекарства.

                        Вопрос в другом: ок, алгоритм как тренировка. А в чем практическая польза выполнения задачи по решению кубика?
                          +1
                          Подобные видео при случае могут набрать миллионы просмотров на YouTube. А если серьезно, то человеку это было интересно. Не надо везде искать практическую пользу. Какая практическая польза катания на аттракционах?
                          –1
                          Человек просто поинтересовался практической целью. А вы повели себя несколько высокомерно. А хабрасообщество подкинуло минусцов. Ни за что!

                          Избегайте такого поведения, люди.
                            +1
                            Это было предсказуемо, на самом-то деле.

                            Коллективное бессознательное хабросообщества очень нервно реагирует на вопросы о практической пользе гиковских выдумок. Они самоценны и эта самоценность зачастую довлеет над здравым смыслом.

                            + предрассудки. Те самые, которые перед рассудком.

                            P.S. как нахватать миллион минусов? Да очень просто: найти у этого коллективного бессознательного больную мозоль и на неё наступить. В силу некоторых особенностей окружающего мира таких больных мозолей много. И больные мозоли у разных людей пересекаются, образуя группы мозолей, а там и до супермозолей доходит.

                            P.P.S Это потянуло бы на юмористическую статью, но до первого апреля далеко, да и психологического образования мне не хватает.
                              0
                              Хорошо сказано, согласен.
                        +3
                        4 месяца обсчитывать кубик рубика, невозможный в реальности. Завидую человеку, способному так заморочиться, я так не могу :)))

                        Внутренний голос подсказывает, что решай он на GPU, было бы разы быстрее, но может ошибаюсь.
                          0
                          Там он пишет, что часть мощностей упиралось в рендеринг (хотя зачем он здесь? можно же было просто логи писать, а потом по логам видео сделать). А рендеринг, я думаю, сделан как минимум с использованием GPU.
                            0
                            Тоже думаю, найти правильную последовательность ходов, а потом в отдельной программе рендерить. Думаю, так намного быстрее будет (возможно, даже, не на 1 порядок). Все-таки, рендеринг такого числа полигонов может много съедать.
                            0
                            Внутренний голос подсказывает, что решай он на GPU, было бы разы быстрее, но может ошибаюсь.

                            Если там много ветвлений, то польза от GPU сомнительно. А их там скорее всего много, на каждом ходу. И каждый следующий ход зависит от предыдущего, поэтому спекулятивное выполнение здесь вряд ли сработает.

                            +2
                            Алгоритм решения включает всего семь действий.

                            Вот так, умудриться написать, обо всём и одновременно ни о чём. Что за действия, что за алгоритм.
                            Для CFOP возможных комбинаций по этапам — 41 (F2L) x 57 (OLL) x 21 (PLL), для каждого варианта каждого этапа — свой алгоритм.

                            Да, можно одним алгоритмом (той же лямбдой, для примера) собрать кубик, но это далеко не оптимально и совсем не быстро.
                              0
                              У меня вышло 65536×65536 (мне нравятся степени двойки)».
                              Поэтому он решил остановиться на кубике в четыре раза меньшего размера, то есть 32768×32768.
                              Только меня это смутило?
                                0
                                Вас смутило «в четыре раза»? Это правильная формулировка. В два раза меньший кубик был бы уменьшен по одной стороне. В четыре раза — по двум (два раза в два раза).
                                Как альтернативный пример можно привести разрешения экрана FullHD и 4K.
                                  +3
                                  ну вообще-то в 8 раз)
                                    0
                                    Ах да, то же 3D, там три стороны. Ну для сравнения 65536×65536 и 32768×32768 — в 4 :)
                                      +8

                                      Важен же не объем кубика, цветные клетки только на поверхности, а поверхность уменьшилась в 4 раза

                                      +2
                                      Да согласен, для пользователя важен не объем а количество элементов, но мозг на слова «размер кубика» среагировал однозначно: a³, — а комментарий удалять нельзя.
                                      0
                                      Тогда мы бы увидели эту статью сильно позже. Четыре месяца занимать компьютер и ждать — и так немало.
                                        +3
                                        > Четыре месяца занимать компьютер и ждать — и так немало.

                                        Мне это напомнило старый анекдот про многозадачность Windows :)
                                          0
                                          Занимать 1 ядро компьютера*
                                          +1
                                          А меня нет
                                          Площадь поверхности — в 4 раза меньше, а, как, например, мой алгоритм сборки, так и объем памяти, необходимый для хранения, пропорционален именно площади поверхности
                                          0
                                          Сам венгерский изобретатель Эрнё Рубик предложил несколько вариантов, а вообще ничто не мешает делать кубики произвольного размера.

                                          Вообще-то сделать кубик произвольного размера мешает геометрия. Если сделать кубик больше, чем 5х5х5, то при повороте слоя на 45 градусов угловые кубики просто вывалятся.
                                            +1
                                            Не смешите мои тапочки. Физические выпускаются вплоть кажется до 17х17х17 (стоят порядка 50-60 тыр), а 6х6х6 у меня есть.
                                            У оной проблемы как минимум 2 решения:1. Чуть изменяем пропорции малых квадратиков так, что крайние чуть больше 2. хитрые металлические штыри все подлдерживающие (как у кубика 2х2х4)
                                              0
                                              А, да, еще и 3е решение есть: Делать кубы выпуклыми
                                              –1
                                              Статья производит впечатление абсолютной бессмысленности действий этого ютубе-блогера
                                              Собрать компом кубик по чужому алгоритму — дело абсолютно бессмысленное и не требует высокой квалификации ни программиста ни математика.
                                              Вот, если он запутыывание умное делал, тогда было бы лучше об этом написать

                                              Only users with full accounts can post comments. Log in, please.