Сможет ли ИИ собрать кубик Рубика быстрее человека? —

Что такое cube tastic

Перед нами игрушка, которая представляет собой классический кубик Рубика 3 на 3. Стороны различаются по цветам, однако это сделано не за счет наклеек, а за счет пластмассовых вставок.

Вторая часть игры — это мобильное приложение. Кубик умеет синхронизироваться со смартфоном. Разумеется, никаких Bluetooth/Wi-fi тут нет: все происходит за счет технологий дополненной реальности.

Что вы как итог получаете?

Вы получаете классический кубик Рубика 3 на 3 с чуть доработанным дизайном боковых поверхностей. Он отлично упакован, выглядит и тянет на достойный сувенир и ребенку, и взрослому, и уж тем более в коллекцию к тем, кто кубики такие собирает.

Продукт локализован, в комплекте даже есть русская инструкция.

Кубиков-головоломок, безусловно, немало: есть и одноцветные, с разной величиной квадратов, есть и с увеличенной площадью, и многие другие варианты, вплоть до куда более агрессивных экспериментов с формой. Так что классический кубик с «изюминкой» в виде гарантированной сборки — логично занимает свою нишу.

Стоимость его 990 рублей. Тут можно много спорить, насколько это дорого / дешево. Наверняка вы сейчас же отправитесь на китайские сайты, чтобы сказать, что там кубики стоят по пять копеек, однако наш маркет ценами не вот прям радует. В рознице, в том же Ашане позавчера я видел кубик за 490 рублей.

990 рублей за дизайнерскую игрушку с дополненой реальностью — звучит неплохо.

Введение

В статье рассматривается «Y-метод» сборки кубика Рубика — его легко понять и запомнить. Он основан всего на одной последовательности, которая называется «Y-движение». Поняв этот алгоритм, вы навряд ли забудете как собрать кубик самостоятельно.

Если попытаться нагуглить инструкцию по сборке кубика Рубика, то найдётся много вариантов с описанием «простой сборки», в том числе на википедии. Которые, в целом, действительно достаточно простые к пониманию, но обладают существенным недостатком.

Для того, чтобы собрать кубик, нужно знать порядка пяти или более нетривиальных последовательностей (алгоритмов) для перестановки отдельных кубиков, для сборки кубика Рубика по слоям. В связи с чем запомнить и воспроизвести самостоятельно эти инструкции затруднительно.

Недавно я случайно наткнулся на упоминание алгоритма «The Ultimate Solution to Rubik’s Cube», о котором утверждалось, что его легко запомнить и понять, и в нём используются всего две последовательности. А когда стал выяснять подробнее, то нашёл также и другой алгоритм — «Y-метод», тоже простой и использующий всего одну последовательность.

К сожалению, описания данного алгоритма на русском я не нашёл, поэтому я решил восполнить этот пробел. Также мне кажется, что главное в этом методе ­— понимание того как он работает. Поэтому тут я не предлагаю готовых наборов движений для конкретных ситуаций, а вместо этого я постарался подробнее описать что происходит.

Mindcub3r по-русски — делаем робота, который может собрать кубик рубика (статья обновлена)

Y-движение

Основу данного алгоритма составляет Y-движение. И довольно важная составляющая алгоритма — это разобраться в механике этого движения.

Данная последовательность поворотов так называется из-за того, что кубики, которые она затрагивает, выглядят как буква «Y», составленная тремя рёбрами, выходящими из одного угла кубика.

Y-движение довольно простое и состоит из четырёх поворотов двух смежных граней, например правой и передней. В распространённой нотаци поворотов для кубика Рубика это выглядит так: R’ F R F’. Что можно описать следующим образом:

1. правая грань против часовой стрелки на четверть оборота
2. передняя грань по часовой стрелке на четверть оборота
3. правая грань по часовой стрелке на четверть оборота
4. передняя грань против часовой стрелки на четверть оборота

То есть грани сначала по очереди поворачиваются «на себя», а потом в обратном порядке «от себя».

Назовём этот вариант «правым Y-движением» (т.к. поворачивается сначала грань справа). В этом случае меняется положение кубиков на ребре, общем у данных граней и на верхних рёбрах. Если начинать повороты с передней грани, то будут затронуты те же самые кубики, такой вариант мы будем называть «левым Y-движением» (т.к. поворачивается сначала грань слева).

Также можно начинать с поворотов «от себя» — это будет то же самое, если бы мы перевернули кубик и начинали с поворотов «на себя», поэтому назовём такие варианты «правым и левым перевёрнутым Y-движением». При перевёрнутых Y-движениях будет также затронуто смежное ребро, а также уже не верхние, а нижние рёбра, соседние с ним.

Принципиальной разницы во всех этих движениях, конечно же, нет. Такое разнообразие нужно исключительно для удобства.

Перечислим некоторые свойства Y-движений:

• Правое и левое Y-движения обратны друг другу, т.е. последовательность правого и левого или левого и правого движений не изменят состояния кубика.
• Одно Y-движение приводит к тому, что меняются местами в паре два угловых кубика на смежной грани и два других угловых кубика. А три кубика находящиеся посередине рёбер (рёберные) перемещаются по кругу.
• Как можно догадаться, после двух движений угловые кубики возвращаются на свои места. Но при этом они оказываются повёрнутыми.
  
• И если выполнить три раза по два движения, то кубики повернутся три раза и в результате вернутся в исходное состояние.
• Рёберные кубики возвращаются в исходное состояние после цикла из трёх движений.
  
• Таким образом, если выполнить Y-движение шесть раз подряд, то состояние кубика вернётся в изначальное.
• После одного Y-движения рёберные кубики перемещаются в направлении первого поворота, при этом два кубика как бы поворачиваются вдоль соответствующих граней (вокруг их оси), а третий также поворачивается, но при этом переворачивается. Переворачивается тот кубик, который перемещается между верхними рёбрами, в случае обычного (не перевёрнутого) Y-движения. При работе с рёберными кубиками Y-движение вдоль одних и тех же рёбер можно производить повернув кубик в разных направлениях, тем самым добиваясь переворота нужного нам кубика.

Зачем это нужно?

На самом деле, если вы заглянете в статистику поисковых запросов, то запросы из серии, как собрать кубик Рубика или «схемы кубика», то или удивитесь, или возмутитесь, сколько человек не хочет, де-скать, думать и ищет простой хак. Такой простой хак нашелся в виде Cube-Tastic: вы можете последовательно собирать кубик согласно подсказкам.

Как работает ии для решения головоломки

Новый искусственный интеллект получил название DeepCubeA и он разработан учеными из Калифорнийского университета. Создатели алгоритма отмечают, что его работа принципиально отличается от всего того, что было создано ранее.

«Мы посчитали, что способ мышления ИИ должен полностью отличаться от человеческого», — сказал профессор Пьер Балди из Калифорнийского университета. «DeepCubeA комбинирует технологии глубокого машинного обучения с «архивом известных решений». То есть он может найти наиболее эффективный алгоритм сборки кубика Рубика, при этом используя меньшую вычислительную мощность.»

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

Как это работает?

Кубик вы «сканируете» с помощью камеры смартфона в определенной последовательности. Последовательность эта указана цветом точки: каким цветом она горит, на такой кружок и надо наводить.

Наводить следует на центральные кружки, что понятно по сетке, а, чтобы уж наверняка не ошибиться, то каждый сканируемый элемент кубика помечен дополнительным символом.

После того, как вы отсканировали все части, приложение подскажет, как расположить кубик и начнет давать подсказки.

В зависимости от того, как тщательно вы перемешали грани, алгоритм рассчитает количество шагов. Их может быть и 9-10 и 20-30 и т. д. 

По бокам экрана расположены стрелочки, а там, где количество шагов «1/30», — кнопка Play. Это означает, что предусмотрено два режима сборки: ручной и автоматический на время. Также сверху в правом углу можно вызвать специальное меню, где все шаги сборки расположены по порядку.

В результате: 

Кому это нужно?

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

Кто быстрее всех собирает кубик рубика?

Несмотря на то, что DeepCubeA собрал кубик Рубика всего за 1 секунду, основной рекорд принадлежит другому ИИ. В 2022 году инженеры Массачусетского Технологического Института разработали min2phase, который на решение задачи тратит всего 0,38 секунды. Но благодаря традиционному подходу найти применение min2phase так и не удалось. DeepCubeA в этом плане куда перспективнее

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

А вы умеете собирать кубик Рубика? Какой у вас рекорд? Поделитесь результатами в комментариях и в нашем официальном чате в Телеграм.

По личным впечатлениям

Полный восторг. И сама идея, и процесс сборки «для ленивых», и реализация приложения, — то есть вот прям понравился. Теперь кручу в руках вместо спиннера. 

Последовательность сборки кубика

Сначала собираются два нижних слоя кубика за исключением одного вертикального ребра, проходящего через эти слои. Это место мы оставляем себе как пространство для манёвра. Нижний крест и нижние угловые кубики собираются довольно просто, но если есть затруднения, то не так сложно приспособить Y-движение для этого или посмотреть одну из инструкций для простой послойной сборки кубика.

Далее нужно собрать средние кубики на вертикальных рёбрах (рёберные). Для этого нужно повернуть верхнюю грань с нужным кубиком, чтобы он оказался на одной из соседних с целевым ребром граней. А также временно (не забываем потом вернуть на место) повернуть нижнюю грань, чтобы на месте целевого ребра оказался кубик, который мы специально оставили несобранным. Теперь можно воспользоваться Y-движением, чтобы переместить кубик с верхней грани на нужное нам место. Y-движение нужно делать такое, чтобы этот рёберный кубик повернулся в нужном направлении в сторону ребра и если нужно, то перевернулся.

Если нужный кубик не находится на верхней грани, то нужно его предварительно, также Y-движением, «освободить» оттуда, не забывая опять же подставить несобранный угол на нижней грани.

Пока что мы собрали два нижних слоя без одного ребра. Далее нам нужно будет собрать два рёберных кубика на верхних рёбрах, которые не граничат с тем, что мы специально не собираем. После этого из рёберных кубиков останется только три несобранных, на рёбрах, которые формируют букву «Y»: вертикальное, которое мы не собирали, и два верхних ребра, соседних с ним.

И, конечно же, мы собираем их с помощью одного или нескольких Y-движений, переворачивая и ставя на нужные места. Тут только нужно учесть один момент с количеством перестановок, который описан чуть ниже.
При сборке последних пяти рёберных кубиков нам может понадобиться развернуть эту букву «Y», чтобы сделать Y-движение в другом направлении (поворачивая другие грани вдоль этих рёбер), таким образом добиваясь перемещения нужных нам кубиков на другие места с переворотом или без него.

К этому моменту у нас будет почти собранный кубик, в котором не собраны только угловые кубики на верхней грани и на вертикальном ребре, которое мы не собирали. Описанными ниже методами сначала переставляем углы друг с другом, чтобы они оказались на своих местах, возможно неправильно ориентированные. А потом разворачиваем их.

Ура, наш кубик собран!

Работа с угловыми кубиками

На последнем этапе сборки нам нужно переставлять угловые кубики местами и поворачивать их. Для этого воспользуемся перечисленными ранее свойствами Y-движения в отношении угловых кубиков. Т.к. удобнее работать с угловыми кубиками, расположенными на верхней грани, то для этого нам больше подойдёт перевёрнутое Y-движение (начинается с поворота «от себя»).

Для перестановки угловых кубиков заметим, что одиночное Y-движение (как левое, так и правое) меняет местами пару угловых кубиков на «смежном ребре», а также что последовательное применение левого и правого Y-движения (или правого и левого) возвращает весь кубик в исходное состояние. Давайте подумаем, что произойдёт, если между этими движениями мы повернём верхнюю грань. Как мы уже обратили внимание, на верхней грани меняется только один угловой кубик, который переставляется с парным кубиком на ребре. В таком случае у нас произойдёт два обмена угловыми кубиками на ребре, но каждый раз сверху будет подставлен разный угол, а все остальные кубики останутся как были (конечно, нужно ещё не забыть повернуть верхнюю грань в исходное состояние). Таким образом, мы осуществили обмен местами трёх угловых кубиков — одного с нижней грани и двух с верхней.
Теперь разберёмся с поворотом кубиков. Для этого воспользуемся похожим трюком. Будем делать два последовательных Y-движения в одном направлении. В результате этого угловые кубики остаются на месте, но меняют свою ориентацию. Тут нас интересуют два варианта комбинации движений: три двойных движения в одном направлении (левые или правые) или двойное движение в одном направлении и двойное движение в обратном направлении. В каждом из этих вариантов весь кубик возвращается в исходное состояние. И мы опять будем между двойными движениями подставлять очередной нужный нам угол на место верхнего угла «смежного ребра». Таким образом мы можем повернуть либо три угловых кубика на одной грани в одном направлении, либо два угловых кубика на одной грани в разных направлениях, не меняя состояния остальных кубиков. Обратим внимание, что после двойного движения верхний кубик смежного ребра поворачивается в том же направлении, в котором осуществляется первое Y-движение.

Считаем перестановки

На что же нужно обратить внимание когда мы собираем пять последних рёберных кубиков. Когда их останется только три, то чтобы у всё получилось с перестановкой их в пределах буквы «Y», нужно чтобы либо они все находились на своих местах (возможно перевёрнутые) или же все были не на своих местах.

Это связано с тем, что Y-движение переставляет три рёберных кубика одновременно. Если рассмотреть это с точки зрения попарных обменов кубиков местами на соседних рёбрах, то происходит два обмена (перестановки). Теперь должно быть понятно почему в случае, когда у нас ровно два кубика не на своих местах, то мы не сможем их собрать. Т.к. нам нужно совершить одну перестановку, а с помощью Y-движений мы можем сделать только чётное число перестановок.

Что же делать в таком случае? Обратим внимание, что если повернуть грань кубика, то мы поменяем местами одновременно четыре рёберных кубика, что будет эквивалентно трём перестановкам, т.е. нечётному числу, что нам и нужно. Из этого следует, что верхняя грань должна быть правильно ориентирована для того, чтобы мы могли собрать последние три рёберных кубика.

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

Заключение

Не знаю как будет в вашем случае, но для меня плюс данного алгоритма не только в том, что его легко запомнить и не нужно зубрить инструкцию по сборке. Но также и в том, что теперь, собирая кубик, я собираю его сам, понимая что происходит, вместо почти механического следования инструкции, а это намного приятнее. Чего и вам желаю!