Рубик и Марков

Rubik and Markov

Здесь мы получаем вероятность оптимального решения кубика Рубика

Кубик Рубика является прототипом задачи планирования с огромным пространством состояний и только одним решением. Это и есть настоящий поиск иголки в стоге сена. Без какого-либо руководства (даже если вы можете поворачивать грани 100 раз в секунду), вы можете потратить всю эру Вселенной, но так и не достичь успеха. Все, что связано с ним, кажется включающим в себя огромные числа.

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

Если решенный кубик подвергается N случайным поворотам, то какова вероятность p(d|N), что оптимальному решителю потребуется именно d ходов, чтобы его решить обратно?

В обычной ситуации, если кто-то попросит вас решить кубик, вы получите только перемешанный куб без каких-либо ориентиров или меток. Здесь у нас есть одна информация о перемешанном состоянии: оно было получено после N случайных ходов из решенного состояния. Эта информация полезна!

• Могут ли языковые модели создавать свои собственные инструменты?
• Понимание Обучения с учителем Теория и Обзор
• Эта научная статья вводит агентов открытый Python-фреймворк для автономных языковых агентов

Почему нас интересует p(d|N)?

Вы можете попытаться декодировать кубик вычислительно разными способами. Амбиции проекта по Рубиковому кубику могут варьироваться от решения любых или некоторых состояний неоптимально до оптимального решения каждого возможного состояния (например, это займет известные 35 ЦПУ-лет). Решатель кубика обычно включает две вещи: алгоритм поиска и эвристическую функцию. Выбирая эти два компонента, мы параметризуем, насколько сложным, эффективным или требовательным к вычислениям будет наш подход.

В области эвристической функции, то есть поискового направления, всегда есть место для новых идей. Исторически эвристика кубика была комбинацией оценок расстояний, подобных Манхэттенским, для положения перемешанной грани кубика относительно их решенных позиций. Только недавно нейронная сеть была использована в качестве эвристики.

Нейронная сеть = новая эвристика кубика Рубика

Работа нейронной сети проста (классификатор): вы передаете состояние кубика x, и предсказывается глубина d этого состояния. Глубина d состояния определяется как минимальное количество ходов, необходимых для оптимального решения кубика из этого состояния. Обратите внимание на следующее. Если у нас есть устройство, которое знает глубину любого состояния, то у нас фактически есть оптимальный решитель, потому что каждый раз мы можем выбирать ход, который дает нам состояние с меньшей глубиной, пока не достигнем глубины = 0 (решенное состояние).

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

training_data = (x , d).

Как мы уже сказали, точность d трудно получить, но с некоторыми конкретными перемешанными состояниями можно легко связать число N: те, которые получены путем действия на решенное состояние N случайных ходов. Тогда

p(d|N) оценивает d при заданном N.

p(d|N) будет использована для повышения точности этих обучающих данных. Авторы вышеупомянутой статьи (или статей) создали первую нейронную сеть для классификации глубины кубика Рубика. Их обучающие данные имели следующий формат:

training_data = (x , N).

Они взяли d как N. Этот выбор был компенсирован динамическим улучшением точности меток с использованием цикла, подобного циклу Беллмана, во время обучения. Вероятность p(d|N), вычисленная здесь, предлагает лучшую отправную точку для точности этого обучающего набора данных (изобильно полученного простым случайным перемешиванием решенного состояния N раз).

Случайное блуждание

Вычисление p(d|N) эквивалентно вопросу, насколько далеко d окажется случайный блуждатель после N шагов. Вместо блуждания по квадратной решетке он будет блуждать по графу Рубика с 10 в степени 19 узлами (состояния куба) и примерно таким же количеством связей (допустимых ходов). Если мы выберем такой макет, где узлы организованы по глубине: с решенным состоянием в центре и состояния глубины d расположены на радиусе d от центра, граф будет выглядеть очень симметричным. Радиальное (глубина) направление предлагает очень простую перспективу.

Конвенция

Здесь мы используем так называемую метрику четверти поворота для куба 3x3x3, где ход включает поворот грани на 90 градусов, либо по часовой стрелке, либо против часовой стрелки. В этой метрике возможны двенадцать возможных ходов. Если бы мы выбрали другую метрику, например, метрику полуповорота (которая также включает повороты граней на 180 градусов как один ход), выражение для p(d|N) отличалось бы.

Данные

Чтобы получить p(d|N), нам понадобится использовать некоторые знания в области, но мы не хотим иметь дело с графами, базами данных шаблонов или теорией групп. Мы будем использовать что-то более “первичное”:

Список, содержащий популяцию состояний кубов на глубине d.

Список (предоставленный авторами статьи “Число Бога” 2012 года) не указывает, какие состояния находятся на определенной глубине, только общее их количество, и нет ссылки на какое-либо N.

# Список популяции глубины# количество состояний кубов на глубине d в метрике четверти поворота      D_d={# глубина  количество состояний  0:     1,  1:     12,  2:     114,  3:     1068,  4:     10011,  5:     93840,  6:     878880,  7:     8221632,  8:     76843595,  9:     717789576,  10:    6701836858,  11:    62549615248,  12:    583570100997,  13:    5442351625028,  14:    50729620202582,  15:    472495678811004,  16:    4393570406220123,  17:    40648181519827392,  18:    368071526203620348,  19:    3000000000000000000,  # приблизительно  20:    14000000000000000000, # приблизительно  21:    19000000000000000000, # приблизительно  22:    7000000000000000000,  # приблизительно  23:    24000000000000000,    # приблизительно  24:    150000,               # приблизительно  25:    36,  26:    3,  27:    0}

Некоторые наблюдения по этому списку:

Во-первых, нет состояний на глубине большей, чем 26 (число Бога равно 26 в метрике четверти поворота). Во-вторых, список указывает приблизительное количество состояний для d от 19 до 24. Нам нужно будет быть внимательными с этим позже. В-третьих, если мы построим график с логарифмической шкалой, мы увидим линейный рост для большинства глубин (кроме тех, что близки к концу). Это означает, что популяция D(d) состояний растет экспоненциально. Подгоняя линейную часть логарифмического графика прямой линией, мы узнаем, что между d = 3 и d = 18 популяция состояний растет как

На глубинах 3 < d < 18 в среднем 9.34 из 12 ходов будут отводить вас от решенного состояния, а 2.66 будут приближать вас к нему.

Марковский процесс на классах глубины

Чтобы найти p(d|N), мы представляем классы глубины как узлы марковского процесса. Позвольте мне объяснить:

Класс глубины d – это набор всех состояний куба на глубине d (минимальное количество ходов до решенного состояния). Если мы случайным образом выбираем состояние в классе глубины d и поворачиваем случайную грань случайным ходом, то это даст нам либо состояние в классе d + 1 с вероятностью p_d, либо состояние в классе d – 1 с вероятностью q_d. В метрике четвертого поворота нет ходов внутри класса.

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

Мы предполагаем равномерное распределение вероятностей для выбора случайных ходов на каждом временном шаге. Это вызывает некоторые вероятности перехода p_d, q_d (вычисляются) между классами глубины. Количество случайных ходов N является дискретным временем марковского процесса. Это также одномерный случайный блуждающий: на каждом узле (номер класса глубины d), вероятность движения вперед равна p_d, а вероятность движения назад равна q_d. Эта одномерная цепь, грубо говоря, представляет “радиальное” направление в графе Рубика (организованном в радиальном макете глубины).

Матрица переходов

Любой марковский процесс закодирован в матрице переходов M. Вход (i,j) матрицы M представляет собой вероятность перехода с узла i на узел j. В нашем случае только следующие входы отличаются от нуля:

Здесь p_0 = 1: из класса глубины 0 (содержащего только решенное состояние) мы можем перейти только в класс глубины 1 (нет класса -1). Также q_26 = 1: из класса глубины 26 мы можем перейти только в класс глубины 25 (нет класса 27). По той же причине, нет p_26 или q_0.

Стационарное распределение

Мы сопоставили действие случайного перемещения куба с одномерным случайным блужданием в глубину, перепрыгивающим вперед и назад с вероятностями q_d и p_d. Что происходит после долгой прогулки? Или сколько раз посетитель посещает определенное место после долгой прогулки? В реальной жизни: как часто посещается глубинный класс, когда куб подвергается случайным поворотам?

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

нормализованный список глубинной популяции D(d) следует интерпретировать как вектор, представляющий стационарное распределение нашего марковского процесса глубинного класса.

Математически D(d) является левым собственным вектором M

Это матричное уравнение даст нам 26 линейных уравнений, из которых мы получим p_i’ и q_i.

Учитывая, что p_0 = q_26 = 1, мы можем переписать их как

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

и p_i получается с использованием p_i + q_i = 1.

Некоторые условия для популяции глубинного класса

Есть нечто интересное в этих решениях. Поскольку q_i – это вероятность, мы должны иметь, что

и это приводит к следующему условию для распределения D_k:

Это столбец неравенств, которому должно удовлетворять глубинное распределение D_k. Явно, они могут быть организованы так:

В частности, последние два неравенства:

Из-за того, что D_27 = 0, мы получаем, что нижняя и верхняя границы равны:

Или:

Сумма популяции четных мест должна быть равна сумме популяции нечетных мест!

Мы можем рассматривать это как детальное равновесие между четными и нечетными сайтами: каждый ход всегда осуществляется на другой и смежный класс глубины. Любой переход будет приводить вас из нечетного класса глубины (класс всех нечетных классов глубины) в четный класс глубины (класс всех четных классов глубины). Таким образом, переход из нечетного в четный класс происходит с вероятностью 1 (и наоборот). Будучи вероятностями одинаковыми в обоих направлениях, их популяция должна быть равной по детальному балансу.

По той же причине процесс Маркова достигнет периода-два “стационарного распределения”, которое переключается между четными и нечетными сайтами после каждого хода (дискретное время N).

Проблема с данными

Количество глубины D_d, указанное в источнике данных, которые мы планируем использовать, приближено для d = 19,20,21,22,23,24. Поэтому нет гарантии, что оно будет удовлетворять всем этим условиям (неравенствам). Не удивляйтесь, если мы получим некоторые вероятности q_i вне диапазона [0,1] (как в данном случае!). В частности, если мы попытаемся проверить последнее условие (равенство четно-нечетной популяции), оно будет сильно отличаться от истинного значения! (обновление: см. примечание в конце)

Выход

Кажется, что нечетный класс недостаточно населен (это является следствием приближения, выбранного авторами для отчета данных). Чтобы все работало (получить вероятности в диапазоне [0,1]), мы решаем добавить предыдущее большое число к популяции класса глубины 21 (нечетный класс с наибольшей популяцией или тот, который меньше всего заметит это добавление). С этой коррекцией все полученные вероятности, кажется, правильные (что означает, что неравенства также удовлетворены).

Вероятности перехода:

p_i = {1., 0.916667, 0.903509, 0.903558, 0.903606, 0.903602, 0.90352, 0.903415, 0.903342, 0.903292, 0.903254, 0.903221, 0.903189, 0.903153, 0.903108, 0.903038, 0.902885, 0.902409, 0.900342, 0.889537, 0.818371, 0.367158, 0.00342857, 6.24863*1e-12, 0.00022, 0.0833333}# i от 0 до 25q_i = {0.0833333, 0.0964912, 0.0964419, 0.096394, 0.0963981, 0.0964796, 0.096585, 0.096658, 0.0967081, 0.0967456, 0.0967786, 0.0968113, 0.0968467, 0.0968917, 0.0969625, 0.0971149, 0.0975908, 0.0996581, 0.110463, 0.181629, 0.632842, 0.996571, 1., 0.99978, 0.916667, 1.}# i от 1 до 26

Обратите внимание, что практически все первые p_i (до i = 21) близки к 1. Это вероятности ухода от решенного состояния. Вероятности приближения к решенному состоянию (q_i) почти равны 1 для i больше 21. Это ставит в перспективу сложность решения куба: случайный шагающий (или случайный перемещатель куба) будет “навсегда заперт” в окрестности класса глубины 21.

p(d|N)

Подставляя числовые значения ​​p_i, q_i в матрицу перехода M, процесс Маркова полностью описывается. В частности, если мы начинаем с сайта 0 с вероятностью единица, после N шагов случайный шагающий будет находиться на сайте d с вероятностью:

Вот вероятность, которую мы искали:

Численно мы узнали, что p(d|N) отлично от нуля только в случае, если N и d имеют одну и ту же четность (что хорошо известно некоторым ученым-кубистам Рубика). Ниже мы строим некоторые p(d|N) для разных N:

Мы замечаем, что после N = 31 или 32, p(d|N) довольно близко к стационарному распределению D(d) (за исключением того, что оно переключается между четными и нечетными позициями). Это еще один ответ на вопрос, сколько ходов достаточно, чтобы сказать, что мы действительно перемешали кубик.

Заметим, что мы решили обратную задачу. Мы получили переходные вероятности из стационарного распределения. Это невозможно для общего марковского процесса. В частности, невозможно найти p(d|N) с помощью описанного здесь метода для метрики полухода. Метрика полухода отличается тем, что мы можем оставаться в той же глубинной классификации после хода (согласно их определению ходов). Эти переходы в одинаковую глубину вводят дополнительные вероятности r_i на диагонали матрицы переходов, и у нас будет больше переменных, чем уравнений.

Заключительные комментарии

Несмотря на то, что кубик Рубика является проблемой, требующей 35 лет ЦПУ с вычислительной точки зрения, существует множество его аспектов, которые можно описать аналитически или с помощью скромных численных усилий. Рассчитанная нами вероятность является примером такого подхода. Все, что мы сказали, может быть легко обобщено на более сложные варианты кубика Рубика. Интересным обобщением является переход к большему числу измерений: S = 4D, 5D, 6D, … мерный кубик Рубика. Пространство состояний в этих случаях экспоненциально растет с увеличением S. Таким образом, существуют кубики, для которых цепь Маркова может быть сколь угодно длинной. Другими словами, у нас есть аналогичные головоломки, для которых число Бога может быть настолько большим, насколько мы хотим (грубо говоря, число Бога – это логарифм числа состояний, а число состояний увеличивается с размерностью S). В таких случаях мы можем рассмотреть определенные предельные значения, которые объясняют некоторые аспекты нашего трехмерного случая, например:

В пределе большого числа Бога G вероятность p(d|N) должна приближаться к биномиальному распределению

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

для k, отличного от 0 и G. Как мы уже сказали, в случае S = 3D b = 9.34. Для более высоких значений S b должно увеличиваться (при увеличении числа граней увеличивается ветвящийся коэффициент b). Это приводит к следующим значениям вероятностей:

q_i приближается к постоянному значению 1/(b+1), когда i находится вдали от начала (i>>1) и числа Бога (i<<G). p_i также будет постоянным в этом диапазоне. Вы можете видеть, что значения p_i и q_i, рассчитанные здесь для случая 3D, почти постоянны для i=3, …, 15, и что q_i приблизительно равно 1/(b+1) с b = 9.34. Для 0 << i << G у нас будет одномерный случай случайного блуждания с постоянными вероятностями возврата (q) и движения вперед (p). В этом случае положение блуждающего будет описываться биномиальным подобным распределением.

Вероятность того, что случайный шагун пройдет k шагов вправо (с вероятностью успеха p) и N-k шагов влево (с вероятностью успеха q) после N попыток составляет Биномиальный(k,N,p). Расстояние, пройденное после N шагов, будет равно

d = k – (N – k),

откуда мы получаем

Из этого мы можем получить аналитические оценки для наиболее вероятного d

Это интересно: с увеличением размерности S куба, коэффициент разветвления b растет, и наиболее вероятная глубина d фактически приближается к N.

Примечание об обновлении. После публикации этой истории я связался с Томасом Рокицки и Морли Дэвидсоном (двумя из авторов доказательства 2012 года, что число Бога в полу-оборотной метрике равно 20) относительно их отчета D(d) и отрицательных вероятностей, полученных мною с его использованием. Они поделились со мной более точными данными, с нижними и верхними границами для популяции глубин d = 19, …, 24 . Их данные полностью совместимы с здесь полученными неравенствами, и с тем, что популяция четных классов глубины должна быть равна популяции нечетных классов глубины (в четверть-оборотной метрике). Вероятности, вычисленные здесь, имеют незначительную поправку при использовании этих новых данных.