Число Бога — как думает компьютер

43 252 003 274 489 856 000

Столько положений у кубика Рубика — сорок три квинтиллиона. Собери каждое на отдельном кубике обычного размера, 5,7 сантиметра, — и этими кубиками можно выложить всю поверхность Земли примерно в 275 слоёв. А если перебирать по одному положению в секунду, работы хватит почти на сто возрастов Вселенной.

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

Число Бога

Представь всеведущее существо: глядя на любой кубик, оно сразу видит самое короткое решение. Сколько ходов ему понадобится в самом трудном случае? Это число в шутку назвали числом Бога.

Ответ — 20. Поворот на 180° здесь считается одним ходом. Если считать его за два, выйдет 26 — это доказали позже, в 2014 году.

На кубике — одно из самых трудных положений, суперфлип. Все углы и все рёбра стоят на своих местах, но каждое ребро перевёрнуто. Кажется, до сборки рукой подать, а быстрее чем за 20 ходов его не собрать: это доказал Майкл Рид ещё в 1995 году. Вот эти двадцать ходов: U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2. Нажми и заметь: один и тот же алгоритм и запутывает, и распутывает. Суперфлип сам себе обратный.

Лестница Тислтуэйта

Перебрать всё в лоб не выйдет даже у компьютера: проверяя миллиард положений в секунду, он возился бы почти 1400 лет. Нужна хитрость.

В 1981 году математик Морвен Тислтуэйт придумал спускаться к решению по ступеням. На каждой ступени кубик заводят в «мир», где часть поворотов уже не нужна. Сначала верх и низ разрешено крутить только на 180°. Потом так же перед и зад. Потом вообще все грани — только на 180°. Каждый следующий мир в тысячи, а то и в миллионы раз меньше предыдущего, и искать в нём легче. Четыре ступени — и любой кубик собран не больше чем за 52 хода.

На кубике — последняя ступень. Грани крутят только на 180°, и на каждой видно лишь два цвета: свой и противоположный.

Попробуй сам: шахматка

Загляни в мир последней ступени изнутри. Собери «шахматку» — узор, где на каждой грани клетки чередуются, как на доске. Рецепт простой: поверни каждую грань один раз на 180°, причём противоположные — друг за другом: правую и левую, верх и низ, перед и зад. Пары можно брать в любом порядке.

Коциемба: две ступени вместо четырёх

В 1992 году Герберт Коциемба сократил лестницу до двух ступеней.

Фаза 1 — навести порядок. Нужно, чтобы все детали были правильно повёрнуты, а четыре ребра среднего пояса стояли в нём же, пусть и не на своих местах. Со стороны это видно так: верх и низ состоят только из жёлтых и белых наклеек. И ещё одна примета, потоньше: у рёбер среднего пояса зелёная или синяя наклейка смотрит вперёд или назад.

На кубике сейчас цветные только жёлтые и белые наклейки, и они разбросаны по всем граням. Нажми B' L U' R F' — всего пять ходов, и жёлтые с белыми соберутся сверху и снизу. Вперемешку, но только на этих двух гранях.

Зачем это? Из такого положения кубик можно собрать, не выходя из «мира», где верх и низ крутят как угодно, а остальные грани — только на 180°. Положений в этом мире около 19,5 миллиарда. Много, но рядом с сорока тремя квинтиллионами — горстка.

Фаза 2 и таблицы-подсказки

Фаза 2 — расставить по местам. Дальше в ходу только разрешённые повороты, поэтому порядок из первой фазы уже не разрушится. Осталось переставить детали: U2 F2 D2 R2 U L2 B2 D R2 F2 U'. Посмотри: ни одного поворота боковой грани на 90°.

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

Первое найденное решение бывает длинноватым. Но программа на нём не останавливается: пробует фазу 1 чуть длиннее, чтобы фаза 2 стала короче, и за секунду-другую спускается к решениям около 20 ходов. Самое короткое находится не всегда, но близкое к нему — почти всегда.

Как доказали двадцать

Число Бога искали тридцать лет. В 1981 году знали, что хватит 52 ходов, к 2008-му — 22. Снизу границу подпирал простой подсчёт: различных цепочек длиной до 17 ходов — если выбросить заведомо лишние вроде R R' — меньше, чем положений кубика. Значит, некоторым положениям нужно хотя бы 18. Суперфлип поднял эту планку до 20. Оставалось сомкнуть верхнюю и нижнюю границы.

В июле 2010 года это сделали Томас Рокицки, Герберт Коциемба — тот самый, — Морли Дэвидсон и Джон Детридж. Они разбили все положения на 2,2 миллиарда частей по 19,5 миллиарда положений — каждая часть устроена как мир второй фазы. Симметрии кубика и ещё пара хитростей сократили работу до 56 миллионов частей, и каждую программа проходила примерно за 20 секунд. Всего ушло около 35 лет процессорного времени — его пожертвовала Google. Вывод: ни одному положению не нужно больше 20 ходов.

Сколько раз повторить

Кубик — ещё и учебник теории групп. Любой алгоритм, если повторять его снова и снова, рано или поздно вернёт кубик в исходное положение. Положений конечное число, так что когда-нибудь кубик попадёт туда, где уже был. А раз каждый ход можно отменить, первым повторится именно начало. Число повторов до возвращения называют порядком алгоритма. Пиф-паф, как ты помнишь, возвращает кубик за шесть повторов.

А у простенького R U порядок — 105. Почему так много? Семь рёбер ходят по одному кругу, и им нужно 7 повторов. Пять углов тоже ходят по кругу, но возвращаются повёрнутыми — им нужно 15. А ещё один угол просто крутится на месте, ему хватает 3. Всё сойдётся, когда число повторов будет делиться и на 7, и на 15, и на 3. Впервые это случается на 105-м.

По дороге бывают чудеса. На кубике — R U, повторённый 35 раз: все рёбра дома, а шесть углов стоят на своих местах, но повёрнуты. После 15 повторов — наоборот: углы дома, а семь рёбер переставлены. Самый большой порядок, какой вообще бывает на кубике, — 1260: есть цепочка всего из пяти ходов, которую нужно повторить 1260 раз, чтобы вернуться.

Попробуй сам: думай с конца

Этот кубик запутали всего тремя ходами. Попробуй собрать его тоже за три. Подсказка: думай, как компьютер, с конца. Какой слой повернули последним? Его и раскрути первым.

Четыре решения одного кубика

На странице «Собрать мой кубик» можно ввести свой кубик и увидеть рядом четыре решения. Для новичка — послойное, 120–180 ходов, и каждый шаг тебе знаком по этому учебнику. Переходное — интуитивный F2L, около 75 ходов: пары, как в трёх главах про F2L, и последний слой в четыре взгляда — 2-look OLL и PLL из главы про CFOP. Как у спидкуберов — CFOP, около 55 ходов. И компьютерное — по Коциембе, около двадцати.

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