Математика игры 2048

в 7:10, , рубрики: 2048, комбинаторика, марковский процесс принятия решений, математика, разработка игр, цепи маркова

Часть 1. Расчёт минимального количества ходов для победы с помощью цепей Маркова

Screenshot of 2048

После недавнего обновления экран «You win!» игры 2048 начал показывать количество ходов, потребовавшихся для победы, и я задался вопросом: сколько же нужно ходов, чтобы выиграть?

В первой части статьи мы ответим на этот вопрос, смоделировав игру 2048 в виде цепи Маркова и проанализировав её, чтобы показать, что вне зависимости от мастерства игрока для победы в среднем нужно не менее 938,8 ходов. Это даёт нам неплохое мерило отсчёта — если вы можете выигрывать примерно за такое количество ходов, то неплохо играете.

Количество ходов, необходимых для победы, зависит от случайности, потому что игра добавляет тайлы 2 и 4 случайным образом. Анализ также покажет, что распределение минимального количества ходов до победы имеет стандартное отклонение в 8,3 хода, и что его общая форма хорошо аппроксимируется смесью биномиальных распределений.

Чтобы получить эти результаты, мы воспользуемся упрощённой версией 2048: вместо размещения тайлов на поле, мы… будем бросать их в мешок. То есть мы проигнорируем геометрические ограничения, вводимые формой поля, на которой могут объединяться тайлы. Такое упрощение сильно облегчит нашу работу, потому что игроку больше не придётся принимать никаких решений 1, и потому что нам не нужно будет отслеживать положение тайлов на поле.

Ценой избавления от этих геометрических ограничений будет то, что мы сможем вычислить только нижнюю границу ожидаемых ходов до победы; может случиться так, что геометрические ограничения не позволят достичь этой границы. Однако, сыграв множество партий в 2048 (ради науки!), я также покажу вам, что на практике мы часто можем приблизиться к этой границе.

Если вы незнакомы с 2048 или с цепями Маркова, то не волнуйтесь — я буду объяснять необходимые понятия по ходу статьи. Код (исследовательского качества), на основе которого написана статья, имеет открытые исходники, на случай, если вы захотите изучить код для генерирования цепи и графиков.

2048 как цепь Маркова

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

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

The initial state for the Markov chain

Подготовка поля

Montage of a sample of eight setup states.

Пример дюжины полей для новой игры.

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

К счастью, мы можем посмотреть на исходный код игры, чтобы понять, как игра это делает. Когда игра размещает на поле случайный тайл, она всегда следует такому сценарию: выбирает случайным образом клетку, затем добавляет новый тайл, либо со значением 2 (с вероятностью 0,9), либо со значением 4 (с вероятностью 0,1).

В случае «2048 в мешке» нас не волнует поиск свободной клетки, потому что мы не ставили никаких ограничений на ёмкость мешка. Нас интересует только добавление тайла 2 или 4 с заданной вероятностью. Это приводит к трём вероятным последующим состояниям из начального состояния:

  • $left { 2,2 right }$, когда оба новых тайла имеют значение 2. Это происходит с вероятностью $0,9 times 0,9=0,81$.
  • $left { 4,4 right }$, когда оба новых тайла имеют значение 4. Это происходит с вероятностью $0,1 times 0,1=0,01$, то есть вам довольно сильно повезло, если вы начинаете игру с двумя четвёрками.
  • $left { 2,4 right }$, когда новые тайлы имеют значение 2, а потом 4, что происходит с вероятностью $0,9 times 0,1=0,09$, или сначала 4, а потом 2, что происходит с вероятностью $0,1 times 0,9=0,09$. Нас не волнует порядок, поэтому оба случая приводят к одному состоянию с общей вероятностью $0,09 + 0,09=0,18$.

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

Directed graph showing the initial state and its immediate successors: {2, 2}, {2, 4}, {4, 4}

Играем в игру

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

Правило объединения тайлов в игре с мешком будет следующим: находим в мешке все пары тайлов, имеющие одинаковое значение, и удаляем их; затем заменяем каждую пару тайлов одним тайлом с удвоенным значением 2.

После объединения пар одинаковых тайлов для перехода к последующему состоянию игра случайным образом добавляет один новый тайл, воспользовавшись уже описанным выше процессом, то есть тайл 2 с вероятностью 0,9 или тайл 4 с вероятностью 0,1.

Например, чтобы найти возможные последующие состояния состояния $left { 2,2 right }$, мы сначала объединяем два тайла 2 в один тайл 4, а затем игра добавляет или тайл 2, или тайл 4. Таким образом, возможными последующими состояниями будут $left { 2,4 right }$ и $left { 4,4 right }$, которые, так уж получилось, мы встречали ранее. Тогда схема, содержащая эти два перехода от $left { 2,2 right }$, которые имеют вероятность 0,9 и 0,1, соответственно, будет иметь вид:

Directed graph showing the additional transitions from the {2, 2} state

Если мы продолжим выполнять этот процесс для последующих состояний состояния $left { 2,4 right }$, то увидим, что пока объединение невозможно, потому что нет пар одинаковых тайлов, и последующее состояние будет или $left { 2,2,4 right }$ или $left { 2,4,4 right }$, в зависимости от того, будет ли новый тайл иметь значение 2 или 4. Тогда обновлённая схема будет такой:

Directed graph showing the additional transitions from the {2, 4} state

Слои и «пропуски»

Мы можем продолжить добавлять переходы таким образом. Однако при добавлении новых состояний и переходов схемы могут становиться всё более сложными 3. Мы можем немного упорядочить схемы, воспользовавшись следующим наблюдением: сумма тайлов в мешке увеличивается с каждым переходом или на 2, или на 4. Так получается потому, что объединение пар одинаковых тайлов не меняет сумму значений тайлов в мешке (или на поле — это свойство применимо и к реальной игре), а значит, игра добавляет тайл 2 или тайл 4.

Если мы сгруппируем состояния по их сумме в «слои», то первые несколько слоёв будут выглядеть примерно так:

Directed graph showing states up to sum 12

Чтобы снизить зашумлённость схем, для более поздних слоёв я также не указываю пометки для переходов с вероятностью 0,9 (сплошные линии, если они никак не помечены) и 0,1 (пунктирные линии).

При группировке состояний в слои по суммам становится очевидной ещё одна закономерность: каждый переход (кроме перехода из начального состояния) совершается или в следующий слой с вероятностью 0,9, или в слой после него с вероятностью 0,1. (Это особенно очевидно, если посмотреть на слои с суммами 8, 10 и 12 со схемы выше.) То есть чаще всего игра даёт нам 2, и мы переходим на следующий слой, но иногда нам везёт, и игра даёт нам 4, и это означает, что мы можем пропустить слой, что немного приближает нас к цели — достижению тайла 2048.

Конец игры

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

В этом случае все поглощающие состояния являются «состояниями победы» — мы получили тайл 2048, а значит, выиграли игру. В «игре с мешком» нет возможности «проиграть», потому что в отличие от реальной игры, мы не можем попасть в ситуацию, когда поле (или мешок) заполнится.

Первое состояние, содержащее тайл 2048 находится в слое с суммой 2066. Примечательно, что невозможно получить на поле единственный тайл 2048 — для объединения тайлов 1024, тайлов 512, и так далее, требуется несколько ходов, за которые накапливается больше тайлов 2 и 4. Поэтому сумма тайлов для первого состояния с тайлом 2048 выше, чем 2048.

Вот как выглядит граф возле этого первого выигрышного состояния (посмотреть подробнее). Поглощающие состояния выделены красным:

Screenshot of the end of the Markov chain

Если мы продолжим добавлять переходы до тех пор, пока не останется непоглощающих состояний, то в результате получим 3487 состояний, 26 из которых являются поглощающими; на этом завершится определение цепи Маркова. Схема полной цепи довольно велика, но если ваш компьютер способен справиться с 5-мегабайтным файлом SVG, то вот схема полной цепи (возможно, придётся немного прокрутить экран вниз, чтобы увидеть начало). Если уменьшить масштаб, то она будет выглядеть так:

Zoomed out view of the whole chain

Выборки из цепи

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

Distribution of the number of moves to win, with the mean of 938.8 highlighted

Среднее, помеченное вертикальной синей линией, оказывается равным 938,8 ходам, исключая первый переход из начального состояния, со стандартным отклонением в 8,3 ходов. Итак, вот наш ответ на вопрос о минимальном ожидаемом количестве ходов до победы в игре!

Теория цепей Маркова также позволяет нам вычислить некоторые из этих свойств напрямую, с помощью хитрой математики. В Приложении А я покажу, как вычислить среднее число и стандартное отклонение для количества ходов, не используя симуляцию. Затем в Приложении Б я воспользуюсь некоторыми из свойств цепи, чтобы предложить хотя бы частичное объяснение формы кривой распределения.

Проверяем теорию практикой

Наконец, чтобы проверить эти результаты в реальной жизни, я много раз сыграл в 2048 (ради науки!) и в 28 выигранных играх я записал количество ходов, а также сумму тайлов на поле, когда я достиг тайла 2048 4:

Montage of 28 winning games of 2048

Выписав эти числа в электронную таблицу и построив по ним график, я получил следующую диаграмму разброса:

Moves to Win and Tiles on Board for the 28 games I won

Я пометил синим минимальное ожидаемое количество ходов, плюс-минус одно стандартное отклонение, и красным сумму тайлов 2066, которая, как мы выяснили, является минимальной суммой тайлов, возможной при наличии тайла 2048.

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

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

Этот график также подчёркивает тот факт, что наш анализ даёт нам только минимальное ожидаемое количество ходов. Было несколько игр, в которых мне везло и я выигрывал менее чем за 938,8 ходов, в том числе была победа с 927 ходами и суммой тайлов 2076. (Это второй слева результат в нижнем ряду подборки.) Так получилось потому, что в той игре мне случайно выпадало много тайлов 4, а ещё потому, что я не совершал серьёзных ошибок, требовавших лишних ходов.

В принципе, есть ненулевая вероятность того, что мы можем выиграть игру всего за 519 ходов. Мы можем определить это, пройдя по цепи, всегда выбирая переход в сторону 4 и считая количество переходов, необходимых для достижения тайла 2048. Однако вероятность такого исхода равна $0,1^{521}$, или $10^{-521}$. В наблюдаемой нами Вселенной всего примерно $10^{80}$ атомов, так что не стоит, затаив дыхание, ждать, что такая игра выпадет именно вам. Также, если нам очень не повезёт и мы всегда будем получать тайлы 2, мы всё равно сможем выиграть всего за 1032 ходов. Такая игра гораздо более вероятна, её вероятность равна $0,9^{1034}$, что равно примерно равно $10^{-48}$, так что, скорее всего, и такой игры не стоит ждать, затаив дыхание. Среднее в 938,8 ходов гораздо ближе к 1032, чем 519, потому что вероятность появления тайлов 2 гораздо выше, чем у тайлов 4.

Заключение

В этой части мы рассмотрели способ создания цепи Маркова, моделирующей эволюцию игры 2048 в случае, когда всегда возможно объединение одинаковых тайлов. Благодаря этому мы смогли применить техники теории поглощающих цепей Маркова для вычисления интересных свойств игры, и, в частности, выяснили, что в среднем для победы требуется не менее 938,8 ходов.

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

Приложение А: анализ цепи Маркова

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

Чтобы относиться к поглощающим цепям, цепь Маркова должна соответствовать следующим критериям:

  1. В ней должно быть хотя бы одно поглощающее состояние. Как мы видели выше, в нашей цепи существует 26 поглощающих состояний, по одному на каждое выигрышное состояние с тайлом 2048.
  2. Любое состояние может достичь поглощающего состояния за конечное число переходов. Один из способов определить это — убедиться, что в цепи нет других циклов, кроме чем для поглощающих состояний: за исключением поглощающих состояний цепь является направленным ациклическим графом.

Переходная матрица

Теперь, когда мы определили, что имеем поглощающую цепь Маркова, следующим шагом будет написание её переходной матрицы в каноническом виде. Переходная матрица — это матрица, упорядочивающая переходные вероятности, которые для нашей цепи мы определили выше, такая, что элемент $(i, j)$ является вероятностью перехода из состояния $i$ в состояние $j$.

Чтобы переходная матрица $mathbf{P}$ поглощающей цепи с $r$ поглощающих состояний и $t$ невозвратных (то есть непоглощающих) состояний могла быть в каноническом виде, должна иметься возможность разбить её на четыре меньших матрицы $mathbf{Q}$, $mathbf{R}$, $mathbf{0}$ и $mathbf{I}$, таких, что:

$mathbf{P}=left( begin{array}{cc} mathbf{Q} & mathbf{R} \ mathbf{0} & mathbf{I}_r end{array} right)$

где $mathbf{Q}$ — это матрица $t times t$, описывающая вероятность перехода из одного невозвратного состояния в другое невозвратное состояние, $mathbf{R}$ — это матрица $t times r$, описывающая вероятность перехода из невозвратного состояния в поглощающее состояние, $mathbf{0}$ обозначает матрицу $r times t$ нулей, а $mathbf{I}_r$ — это переходная матрица для поглощающих состояний, являющаяся единичной матрицей $r times r$.

Чтобы преобразовать переходную матрицу нашей цепи в канонический вид, нам нужно определиться с порядком состояний. Достаточно будет упорядочить состояния (1) по тому, являются ли они поглощающими (поглощающие состояния идут последними), затем (2) по сумме их тайлов (по возрастанию) и, наконец, (3) в лексическом порядке, чтобы избавиться от зависимостей. Если мы сделаем это, то получим следующую матрицу:

The full transition matrix for the absorbing Markov chain

Она довольно большая, а именно, размером $3487 times 3487$, поэтому при уменьшении масштаба выглядит почти диагональной, но если мы приблизим правый нижний угол, то увидим, что у неё есть структура, и, в частности, есть канонический вид, к которому мы стремимся:

The lower right hand corner of the transition matrix for the absorbing Markov chain, which shows more structure

Фундаментальная матрица

Получив канонический вид переходной матрицы, дальше мы используем её для нахождения того, что называется фундаментальной матрицей цепи. Она позволить нам вычислить ожидаемое количество переходов до поглощения, то есть мы (наконец-то!) найдём ответ на наш исходный вопрос.

Фундаментальная матрица $mathbf{N}$ задаётся относительно $mathbf{Q}$ тождественным равенством

$mathbf{N}=sum_{k=0}^{infty} mathbf{Q}^kmathbf{N}=sum_{k=0}^{infty} mathbf{Q}^k$

где $mathbf{Q}^k$ обозначает $k$-тую степень матрицы $mathbf{Q}$.

Элемент $(i, j)$ $mathbf{N}$ имеет определённую интерпретацию: это ожидаемое число раз, которое мы войдём в состояние $j$, если будем следовать по цепи, начиная с состояния $i$. Чтобы увидеть это, мы можем заметить, что как элемент $(i, j)$ матрицы $mathbf{Q}$ является вероятностью перехода из состояния $i$ в состояние $j$ за один переход, так и элемент $(i, j)$ матрицы $mathbf{Q}^k$ является вероятностью входа в состояние $j$ ровно за $k$ переходов после входа в состояние $i$. Если для заданной пары состояний $i$ и $j$ мы суммируем упомянутые вероятности для всех $k geq 0$, то сумма будет включать в себя каждый раз, когда мы имеет возможность войти в состояние $j$ после состояния $i$, взвешенный по соответствующей вероятности, что и даёт нам нужное ожидание.

К счастью, фундаментальную матрицу можно вычислить напрямую, без неприятного бесконечного суммирования, как обратную матрицу $mathbf{I}_t - mathbf{Q}$, где $mathbf{I}_t$ — это единичная матрица $t times t$. То есть, $mathbf{N}=(mathbf{I}_t - mathbf{Q})^{-1}$. (Доказательство этого будет домашним заданием для читателя!)

Ожидаемое число ходов до победы

Получив фундаментальную матрицу, мы можем найти ожидаемое число переходов из любого состояния $i$ к поглощающему состоянию с помощью суммирования всех элементов в ряду $i$ — иными словами, количество переходов до попадания в поглощающее состояние равно общему числу переходов, которое нам пришлось совершить во всех невозвратных состояниях по пути.

Мы можем получить эти суммы рядов сразу для всех состояний, вычислив произведение матрицы на вектор $mathbf{N} mathbf{1}$, где $mathbf{1}$ обозначает вектор-столбец $t$. Поскольку $mathbf{N}=(mathbf{I}_t - mathbf{Q})^{-1}$, мы можем сделать это, решив линейную систему уравнений

$(mathbf{I}_t - mathbf{Q})mathbf{t}=mathbf{1}$

для $mathbf{t}$. Элемент в $mathbf{t}$, соответствующий начальному состоянию (пустому множеству $left { right }$), является числом переходов. В этом случае, получаемое число равно 939,8. Для завершения нам нужно только вычесть $1$, потому что переход из начального состояния не считается ходом. Это даёт нам конечный ответ — 938,8 ходов.

Также мы можем получить дисперсию для минимального числа ходов как

$2(mathbf{N} - mathbf{I}_t) mathbf{t} - mathbf{t} circ mathbf{t}$

где $circ$ обозначает (покомпонентное) произведение Адамара. Для начального состояния получаем дисперсию 69,5, что даёт нам стандартное отклонение в 8,3 шагов.

Приложение Б: форма кривой распределения

Примечательно, что нам удалось вычислить и среднее, и дисперсию распределения ходов до победы из цепи Маркова с помощью фундаментальной матрицы. Однако неплохо было бы узнать, почему распределение получилось такой формы. Предлагаемый здесь мной подход является только приблизительным. но он достаточно близко соответствует эмпирическим результатам из симуляции и даёт нам кое-какую полезную информацию.

Мы начнём с возврата к сделанному ранее наблюдению: сумма тайлов на поле увеличивается с каждым переходом на 2 или на 4 (кроме первого перехода из начального состояния). Как мы увидим ниже, если мы были бы заинтересованы в получении конкретной суммы на поле, а не получении тайла 2048, то было бы довольно просто вычислить нужное количество переходов с помощью биномиального распределения.

Итак, следующий вопрос будет заключаться в том, какую сумму мы хотим получить. Из приведённого выше анализа цепи Маркова мы определили, что существует 26 поглощающих (выигрышных) состояний. Мы также увидели, что они находятся на разных «слоях сумм», то есть нет одной суммы, к которой мы стремимся, их несколько. Нам нужно знать, какова вероятность для каждого состояния стать поглощённым. Она называется вероятностью поглощения. Затем мы можем суммировать вероятности поглощения для каждого из поглощающих состояний в отдельном слое сумм, чтобы найти вероятность выигрыша с конкретной получившейся суммой.

Вероятности поглощения

К счастью, вероятности поглощения тоже можно найти из фундаментальной матрицы. В частности, мы можем получить их, решив линейные уравнения

$(mathbf{I}_t - mathbf{Q}) mathbf{B}=mathbf{R}$

для матрицы $mathbf{B}$ размером $t times r$, чей элемент $(i, j)$ — это вероятность поглощения в состоянии $j$, начиная со состояния $i$. Как и раньше, нас интересуют вероятности поглощения, при начале из начального состояния. Построив график вероятности поглощения, мы увидим, что существует 15 поглощающих состояний, вероятности которых достаточно велики для отображения на графике (не менее $10^{-3}$):

Absorbing probabilities for the Markov chain

В частности, большинство игр завершается или состоянием $left { 2,2,8,8,2048 right }$, сумма которого равна 2068, или состоянием $left {2,4,16,2048right }$, сумма которого 2070. Суммируя все поглощающие состояния по сумме слоёв, мы получаем полные вероятности суммы слоя:

Total absorbing probabilities by sum of tiles

Биномиальные вероятности

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

В этом случае под «попыткой» мы будем подразумевать ход, а под «успехом» — ход, в котором игра даёт нам тайл 4; как показано выше, это происходит с вероятностью 0,1. «Неудачей» здесь является ход, в котором игра даёт нам тайл 2, что происходит с вероятностью 0,9.

С учётом такой интерпретации успехов, для того, чтобы получить заданную сумму $S$ за $M$ ходов, нам потребуется $frac{S}{2} - M$ успехов из $M$ ходов. Так получается, потому что каждый ход прибавляет к сумме как минимум $2$, что в целом даёт $2M$, а каждый успех добавляет к сумме дополнительные $2$, внося в общем $2 left(frac{S}{2} - Mright)=S - 2M$. Складывая эти значения, мы получим нужную сумму $S$.

Тогда совместная вероятность получения суммы $S$ за количество ходов $M$ является биномиальной, и в частности

$mathrm{Pr}(M=m, S=s)=Bleft(frac{s}{2} - m; m, 0.1right)$

где $B(k; n, p)$ — это функция распределения масс для биномиального распределения, которая даёт нам вероятность получения ровно $k$ успехов за $n$ попыток, где вероятность успеха равна $p$, т.е.

$B(k; n, p)={nchoose k}p^k(1-p)^{n-k}$

где $n choose k$ обозначает биномиальный коэффициент.

Теперь, когда мы знаем целевую сумму $S$, к которой стремимся, мы можем вычислить условное распределение ходов с учётом того, что сумма, которая нас интересует — из совместного распределения. То есть мы можем найти $mathrm{Pr}(M | S)$ как

$mathrm{Pr}(M | S)=frac{mathrm{Pr}(M, S)}{mathrm{Pr}(S)}$

где $mathrm{Pr}(S)$ получается из совместного распределения суммированием $M$ для каждой возможной суммы $S$. Стоит заметить, что $mathrm{P}(S)$ меньше единицы для каждой возможной суммы, потому что всегда существует вероятность того, что игра «перескочит» сумму, выдав нам тайл 4.

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

Simulated and binomial mixture model distributions for minimum moves to win

Здесь симулированное распределение показано серыми столбцами, а цветными областями показаны каждое из условных распределений. Каждое условное распределение отмасштабировано согласно общей вероятности поглощения для его суммы, а также смещено на несколько ходов, потому что бо́льшие суммы в среднем требуют больше ходов.

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

Благодарю Хоуп Томас и Нейта Стемена за правку черновиков этой статьи.

Примечания

  1. Если мы позволим игроку принимать решения, то нужно использовать марковский процесс принятия решений, а не цепь Маркова. Это будет темой следующей части.
  2. Такое объединение пар одинаковых тайлов ухватывает важный нюанс логики объединения в реальной игре: например, если у вас есть четыре тайла 2 в ряд, и вы сдвинете их, чтобы объединить, в результате получится два тайла 4, а не один тайл 8. То есть нельзя объединять только что объединённые тайлы одним смещением
  3. Эти схемы получены с помощью отличного инструмента dot из graphviz. Если вы не подскажете dot группировать состояния в слои по сумме, то создание полного графа займёт довольно большое время.
  4. Внешний вид экрана «You win!» за месяцы сбора этих данных менялся несколько раз. Для протокола: все эти месяцы я не только играл в 2048.

Часть 2. Подсчёт состояний с помощью комбинаторики

Screenshot of 2048 with an infeasible board configuration

В предыдущей части я выяснил, что для победы в игре 2048 в среднем потребуется не менее 938,8 ходов. Основным упрощением, позволившим выполнить эти вычисления, было то, что мы игнорировали структуру поля — в сущности, мы бросали тайлы в мешок, а не размещали их на поле. Благодаря этому «мешочному» упрощению мы смогли смоделировать игру в виде цепи Маркова со всего лишь 3486 состояниями.

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

Для этого мы воспользуемся (простыми) техниками из перечислительной комбинаторики, чтобы исключить некоторые состояния, которые можно записать, но которые не могут возникнуть в игре, например, как приведённое выше. Результаты также будут применимы к всем играм, похожим на 2048, даже к играемым на других полях (а не только 4x4) и до других тайлов (не только до 2048). Мы увидим, что такие игры на меньших полях и/или до тайлов меньшего значения имеют гораздо меньше состояний, чем полная игра 4x4 в 2048, и что использованные здесь техники относительно гораздо более эффективны в снижении ожидаемого количества состоянии при маленьком размере поля. В качестве бонуса мы также увидим, что поле 4x4 является наименьшим квадратным полем, на котором возможно достичь тайла 2048.

Код (исследовательского качества), на котором основана эта часть, имеет открытые исходники, на случай, если вы захотите оценить реализацию или код для графиков.

Базовая линия

Наиболее очевидный способ оценки количества состояний игры 2048 заключается в следующем наблюдении: существует 16 клеток, каждая клетка может быть пустой или содержать тайл, значение которого является одной из 11 степеней двойки, от 2 до 2048. Это даёт нам 12 возможных значений для каждой из 16 клеток, то есть всего $12^{16}$, или 184 квадриллионов (примерно $10^{17}$) возможных значений, которые можно записать таким образом. Для сравнения: по некоторым оценкам, количество возможных конфигураций положений на шахматной доске примерно равно $10^{45}$, а по последним оценкам, в игре го примерно $10^{170}$ состояний, поэтому хоть $10^{17}$ — это много, но это не рекорд для игр.

В более общем виде подобные 2048 игры можно представить так: пусть $B$ — размер поля, а $K$ — степень выигрышного тайла со значением $2^K$. Для удобства пусть $C$ обозначает количество клеток на поле, то есть $C=B^2$. Для обычной игры 2048 с полем 4x4: $B=4$, $C=16$, и $K=11$, потому что $2^{11}=2048$, а возможное количество состояний равно

$(K + 1)^C$

Теперь давайте посмотрим, как мы можем уточнить возможное значение.

Во-первых, поскольку игра завершается, когда мы получаем тайл $2^K$, то нас не волнует, где находится этот тайл и что на поле есть кроме него. Поэтому мы можем объединить все состояния с тайлом $2^K$ в одном специальное состояние «победы». В остальных состояниях каждая клетка может быть или пустой, или содержать один из тайлов $K - 1$. Это уменьшает количество состояний, которые нас интересуют, до

$K^C + 1$

где $1$ — это состояние «победы».

Во-вторых, мы можем заметить, что некоторые из этих состояний $K^C$ никогда не могут возникнуть в игре. В частности, правила игры подразумевают два полезных свойства:

Свойство 1: на поле всегда есть как минимум два тайла.

Свойство 2: на поле всегда есть как минимум один тайл 2 или тайл 4.

Первое свойство соблюдается, потому что даже если вы начнёте игру с двумя тайлами и объедините их, то всё равно останется один, после чего игра добавит один случайный тайл и их станет два. Второе свойство соблюдается, потому что игра всегда добавляет тайл 2 или тайл 4 после каждого хода.

Таким образом, мы знаем, что в любом верном состоянии на поле должно быть как минимум два тайла, и один из них должен быть тайлом 2 или тайлом 4. Чтобы учесть это, мы можем вычесть все состояния без тайла 2 или без тайла 4, которых $(K-2)^C$, а также состояния только с одним тайлом 2 и остальными пустыми клетками, которых $C$, а также состояния с только одним тайлом 4 и остальными пустыми клетками, которых тоже $C$. Это даёт нам возможное значение

$K^C - (K-2)^C - 2C + 1$

состояний. Разумеется, когда $K$ или $C$ велико, это выглядит почти как $K^C$, то есть основной член, но для малых значений эта корректировка более значима.

Давайте используем эту формулу для сведения возможного количества состояний для различного полей размера и максимальных тайлов:

Максимальный тайл Размер поля
2x2 3x3 4x4
8 73 19 665 43 046,689
16 233 261 615 4 294 901 729
32 537 1 933 425 152 544 843 873
64 1 033 9 815 535 2 816 814 940 129
128 1 769 38 400 465 33 080 342 678 945
256 2 793 124 140 015 278 653 866 803 169
512 4 153 347 066 865 1 819 787 258 282 209
1024 5 897 865 782 255 9 718 525 023 289 313
2048 8 073 1 970 527 185 44 096 709 674 720 289

Сразу можно увидеть, что в играх с полями 2x2 и 3x3 на много порядков меньше состояний, чем в игре 4x4. Кроме того, нам удалось ограничить возможное количество тайлов в игре 4x4 до 2048 «всего лишь» 44 квадриллионами, или ~$10^{16}$.

Подсчёт в слоях

Чтобы немного больше разобраться с этими количествами состояний, мы можем воспользоваться ещё одним важным свойством, которое пригодилось и в предыдущей части:

Свойство 3: сумма тайлов на поле увеличивается с каждым ходом на 2 или на 4.

Это правило соблюдается, потому что объединение двух тайлов не изменяет сумму тайлов на поле, и после него игра добавляет 2 или 4.

Свойство 3 подразумевает, что состояния в течение игры никогда не повторяются. Это значит, что мы можем упорядочить состояния в слои по сумме их тайлов. Если игра находится в состоянии в слое с суммой 10, мы знаем, что следующее состояние будет в слое с суммой или 12, или 14. Получается, что мы также можем посчитать количество состояний в каждом слое.

Пусть $S$ обозначает сумму тайлов на поле. Мы хотим посчитать количество способов, которыми $C$ чисел, каждое из которых является степенью двойки от 2 до $2^{K-1}$, можно сложить, чтобы получить $S$.

К счастью, это оказывается разновидностью хорошо изученной задачи комбинаторики: подсчёта композиций целого числа. В общем случае композиция целого числа $S$ — это упорядоченная совокупность целых чисел, которые в сумме дают $S$; каждое целое число в совокупности называется частью. Например, у целого числа $3$ существует четыре композиции, а именно $1 + 1 + 1$, $1 + 2$, $2 + 1$ и $3$. Когда для частей существуют ограничения, например, быть степенью двойки и наличие определённого количества частей, то такая композиция называется ограниченной.

Ещё более удачно то, что Чинн и Нидерхаузен (2004 год) 1 уже изучили именно такой тип ограниченной композиции и вывели рекурсию, которая позволит нам посчитать количество композиций, в которых есть определённое количество частей, при этом каждая часть будет являться степенью двойки. Пусть $N(s, c)$ обозначает количество композиций (положительного) целого $s$ ровно в $c$ частях, причём каждая часть является степенью двойки. Тогда

$N(s, c)=begin{cases} sum_{i=0}^{lfloor log_2 s rfloor} N(s - 2^i, c - 1), & 2 le c le s \ 1, & c=1 textrm{, а } s textrm{ - степень 2} \ 0, & textrm{в противном случае} end{cases}$

потому что для каждой композиции числа $s - 2^i$ в $c - 1$ частях мы можем получить композицию $s$ из $c$ частей, прибавив одну часть со значением $2^i$.

Теперь нам нужно внести небольшие изменения в границы суммирования: надо использовать степени двойки, начиная с 2 и до $2^{K-1}$, потому что если у нас есть тайл $2^K$, то игра выиграна. Для этого пусть $N_m(s, c)$ обозначает количество композиций числа $s$ ровно в $c$ частях, при этом каждая часть является степенью двойки от $2^m$ до $2^{K-1}$. По представленной выше логике это можно задать уравнением

$N_m(s, c)=begin{cases} sum_{i=m}^{K - 1} N(s - 2^i, c - 1), & 2 le c le s \ 1, & c=1 textrm{, а } s=2^i textrm{ для } i in { m, ldots, K-1 } \ 0, & textrm{в противном случае} end{cases}$

Теперь у нас есть формула ровно для $c$ частей, но нам нужна формула, чтобы частей было до $c$. Можно воспользоваться теми же рассуждениями, что и в предыдущем разделе: вычесть состояния без тайлов 2 или 4, которых есть $N_3(s, c)$. Согласно свойству 1, нам нужно не менее двух частей, поэтому мы начинаем суммировать с $c=2$. Это даёт нам в качестве возможного значения для количества состояний с суммой $s$

$sum_{c=2}^{C} {C choose c} left( N_1(s, c) - N_3(s, c) right)$

Здесь $C choose c$ — это биномиальный коэффициент, дающий нам количество способов выбора $c$ из возможных $C$ клеток, в которых размещаются тайлы. Давайте отметим их на графике.

Number of states by sum of tiles (with K=11)

В отношении порядка мы можем заметить, что игра 2x2 никогда не имеет более 60 состояний на слой, в игре 3x3 максимум примерно 3 миллиона состояний на слой, а в игре 4x4 максимум примерно 32 триллиона ($10^{13}$) состояний на слой. Количество состояний быстро растёт на ранних этапах игры, но потом замедляется и постепенно снижается при заполнении поля. На снижающейся части кривой мы видим разрывы, особенно для больших сумм. Такое может происходить, когда нет тайлов, которые подходят к полю и суммируются с этим значением.

Верхний предел на горизонтальной оси возникает потому, что у нас может быть $C$ значений, каждое из которых до $2^{K-1}$, то есть максимально достижимая сумма равна $C 2^{K-1}$, или 16 384 для игры 4x4 до 2048.

Наконец, стоит заметить, что если мы суммируем число состояний в каждом слое по всем возможным суммам слоёв от 4 до $C 2^{K-1}$ и добавим единицу для особого состояния выигрыша, то мы получим то же количество состояний, которое ожидалось в предыдущем разделе. Это полезная проверка на правильность наших рассуждений.

Достижимость слоёв

Ещё одно полезное следствие из свойства 3 заключается в том, что если два последовательных слоя не имеют состояний, то более поздних слоёв достичь невозможно. Так получается потому, что сумма может за ход увеличиваться максимум на 4; если есть два соседних слоя без состояний, то сумма должна увеличиться на 6 за один ход, чтобы «перепрыгнуть» к последующему слою, что невозможно. Таким образом, нахождение сумм слоёв, которые не содержат состояний, с помощью представленных выше вычислений позволяет нам сузить возможное значение, исключив состояния в недостижимых слоях после последнего достижимого слоя. Наибольшие достижимые суммы слоёв (без недостижимого тайла 2048):

Размер поля Максимально достижимая сумма слоя
2x2 60
3x3 2 044
4x4 9 212

Эта таблица также показывает нам, что максимальный тайл, которого мы можем достичь на поле 2x2 — это тайл 32, потому что тайл 64 не может появиться в слое с суммой 60 или меньше. Аналогично, максимально достижимый тайл на поле 3x3 — это тайл 1024. Это значит, что поле 4x4 является минимальным квадратным полем, на котором можно достичь тайла 2048 2. В случае поля 4x4 максимальной суммой слоя, которую можно достичь, не доходя до тайла 2048 (то есть без победы) является 9 212, но если разрешить тайл 2048, то можно достичь и бо́льших сумм.

С учётом достижимости слоёв, новыми возможными значениями для количества состояний будут:

Максимальный тайл Способ Размер поля
2x2 3x3 4x4
8 Базовая линия 73 19 665 43 046 689
Достижимость слоёв 73 19 665 43 046 689
16 Базовая линия 233 261 615 4 294 901 729
Достижимость слоёв 233 261 615 4 294 901 729
32 Базовая линия 537 1 933 425 152 544 843 873
Достижимость слоёв 529 1 933 407 152 544 843 841
64 Базовая линия 1 033 9 815 535 2 816 814 940 129
Достижимость слоёв 905 9 814 437 2 816 814 934 817
128 Базовая линия 1 769 38 400 465 33 080 342 678 945
Достижимость слоёв 905 38 369 571 33 080 342 314 753
256 Базовая линия 2 793 124 140 015 278 653 866 803 169
Достижимость слоёв 905 123 560 373 278 653 849 430 401
512 Базовая линия 4 153 347 066 865 1 819 787 258 282 209
Достижимость слоёв 905 339 166 485 1 819 786 604 950 209
1024 Базовая линия 5 897 865 782 255 9 718 525 023 289 313
Достижимость слоёв 905 786 513 819 9 718 504 608 259 073
2048 Базовая линия 8 073 1 970 527 185 44 096 709 674 720 289
Достижимость слоёв 905 1 400 665 575 44 096 167 159 459 777

Это сильно влияет на поле 2x2, снижая количество состояний с 8 073 до 905 для игры до 2048, и примечательно, что значения для числа достижимых состояний не увеличиваются с 905 для максимальных тайлов после 32, потому что на поле 2x2 невозможно достичь тайлов, больше чем 32. Также это немного влияет на поле 3x3, но на 4x4 это оказывает относительно малое влияние — мы избавляемся «всего» от примерно 500 миллиардов состояний от общего количества в случае игры до 2048.

В графической форме эти данные выглядят так:

Estimated number of states each for board size and maximum tile

Заключение

Мы получили приблизительные оценки количества состояний в игре 2048 и в похожих играх на досках меньшего размера и меньшими максимальными тайлами. Пока наша наилучшая оценка количества состояний в игре 4x4 до 2048 приблизительно равна 44 квадриллионам (~$10^{16}$).

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

An infeasible board position with three 2 tiles in the middle with empty cells around

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

В следующем посте мы увидим, что количество действительно достижимых состояний намного ниже, на самом деле перечислив их. Их всё равно будет много для полей 3x3 и 4x4, поэтому нам потребуются знания теории обработки информации, а также математики.

Если вы дочитали до этого места, возможно, стоит подписаться на меня в Twitter, или даже прислать просьбу о найме в Overleaf.

Примечания

  1. Chinn, P. and Niederhausen, H., 2004. Compositions into powers of 2. Congressus Numerantium, 168, p.215. (препринт)
  2. Мы могли показать это и с помощью анализа цепей Маркова из первой части, убрав все состояния с более чем девятью тайлами, и проверив, возможно ли всё ещё достичь тайла 2048. Если мы сделаем это, то выясним, что это невозможно. Интересно, что если мы позволим цепи Маркова продолжить увеличивать максимальные значения тайла, то тот же анализ покажет, что на поле 4x4 можно достичь тайла 131072 (то есть $2^{17}$), если при этом игнорировать структуру поля. Будет ли это справедливо для случая со структурными ограничениями — не знаю, но подозреваю, что нет. Однако, как показано этим ИИ-ботом, возможно играть как минимум до тайла 8192, и существует видео «доказательства концепции» для тайла 131072

Автор: PatientZero

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js