Математика 2048 года: минимум ходов для победы с цепями Маркова

08.09.2021

2017-09-25На Hacker News прошла оживленная дискуссия об этой серии.

В рамках недавнего обновления «Вы выигрываете!» 2048 года. screen начал отображать количество ходов, необходимых для победы, что заставило меня задуматься: сколько ходов нужно сделать, чтобы выиграть?

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

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

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

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

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

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

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

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

Настройка Совета



Образец десятка новых игровых досок.

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

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

Для 2048 в сумке мы не заботимся о поиске доступной ячейки, потому что мы не наложили никаких ограничений емкости на сумку; мы просто заботимся о добавлении плитки 2 или 4 с заданными вероятностями. Это приводит к трем возможным состояниям-преемникам для начального состояния:

  • \ (\ \), когда обе новые плитки равны 2 с. Это происходит с вероятностью \ (0,9 \ умножить на 0,9 = 0,81 \).
  • \ (\ \), когда обе новые плитки равны 4 с. Это происходит с вероятностью \ (0,1 \ умножить на 0,1 = 0,01 \), то есть вам очень повезет, если вы начнете с двух 4 с.
  • \ (\ \), когда новые плитки равны 2, а затем 4, что происходит с вероятностью \ (0,9 \ умножить на 0,1 = 0,09 \), или 4, а затем 2, что происходит с вероятностью \ (0,1 \ раз 0,9 = 0,09 \). Нас не заботит порядок, поэтому оба случая приводят к одному и тому же состоянию с полной вероятностью \ (0,09 + 0,09 = 0,18 \).

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

Игра в игру

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

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

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

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

Если мы проследим тот же процесс для преемников \ (\ \), мы увидим, что слияние еще невозможно, потому что нет пары одинаковых плиток, и состояние преемника будет либо \ (\ \) или \ (\ \), в зависимости от того, является ли новый тайл 2 или 4. Обновленная диаграмма выглядит так:

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

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

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

Для более поздних слоев я также опустил метки для переходов с вероятностью 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.

Вот как выглядит график вокруг этого первого выигрышного состояния (см. Больше), когда поглощающие состояния окрашены в красный цвет:

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

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

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

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

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

Проверка теории

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

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

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

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

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

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

В принципе, вероятность того, что мы выиграем всего за 519 ходов, ненулевая. Мы можем найти это, пройдя по цепочке, всегда выбирая переход за 4 и подсчитывая количество переходов, необходимых для достижения плитки 2048. Однако вероятность этого равна \ (0.1 ^ \) или \ (10 ​​^ \); в наблюдаемой Вселенной всего около \ (10 ​​^ \) атомов, поэтому не стоит задерживать дыхание в ожидании такой игры. Точно так же, если нам очень не везет и мы всегда получаем 2 плитки, мы все равно сможем выиграть всего за 1032 хода. Такая игра гораздо более вероятна, с вероятностью \ (0.9 ^ \), что примерно \ (10 ​​^ \), но вам, вероятно, не стоит задерживать дыхание в ожидании этой игры. . Среднее значение 938,8 хода намного ближе к 1032, чем к 519,потому что 2 плитки гораздо более вероятны, чем 4 плитки.

Вывод

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

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

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

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

Критерии того, чтобы быть поглощающей цепью Маркова, заключаются в следующем:

Должно быть хотя бы одно поглощающее состояние. Как мы видели выше, существует 26 поглощающих состояний, по одному для каждого выигрышного состояния с плиткой 2048.

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

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

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

Для матрицы перехода \ (\ mathbf

\) поглощающей цепи с \ (r \) поглощающими состояниями и \ (t \) переходными (что означает непоглощающие) состояниями, чтобы иметь каноническую форму, необходимо иметь возможность разбить ее на четыре меньшие матрицы, \ (\ mathbf \), \ (\ mathbf \), \ (\ mathbf \) и \ (\ mathbf _r \), такие, что: \ [\ mathbf

= \ left (\ begin \ mathbf & \ mathbf \\\

\ mathbf & \ mathbf _r \ конец \ right) \] где \ (\ mathbf \) - матрица \ (t \ times t \), которая описывает вероятность перехода из одного переходного состояния в другое переходное состояние, \ (\ mathbf \) представляет собой матрицу \ (t \ times r \), которая описывает вероятность перехода из переходного состояния в поглощающее состояние, \ (\ mathbf \) обозначает матрицу нулей \ (r \ times t \) , а \ (\ mathbf _r \) - матрица перехода для поглощающих состояний, которая представляет собой единичную матрицу \ (r \ times r \).

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

Он довольно большой, а именно \ (3487 \ times 3487 \), поэтому при уменьшении он выглядит довольно диагональным, но если мы увеличим масштаб в правом нижнем углу, мы увидим, что у него есть некоторая структура, и в частности он имеет каноническую форму, которую мы ищем:

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

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

Фундаментальная матрица \ (\ mathbf \), определяется в терминах \ (\ mathbf \) тождеством \ [\ mathbf = \ сумма_ ^ \ mathbf ^ k \], где \ (\ mathbf ^ k \) обозначает \ (k \) -ю матричную степень \ (\ mathbf \).

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

К счастью, фундаментальную матрицу также можно вычислить напрямую, без громоздкого бесконечного суммирования, как обратную матрицу \ (\ mathbf _t - \ mathbf \), где \ (\ mathbf _t \) - это \ (t \ times t \) единичная матрица; то есть \ (\ mathbf = (\ mathbf _t - \ mathbf ) ^ \). (Доказательство этого тождества оставляем читателю в качестве упражнения!)

Ожидаемые ходы к победе

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

Мы можем получить эти строчные суммы для всех состояний сразу, вычислив произведение матрица-вектор \ (\ mathbf \ mathbf \), где \ (\ mathbf \) обозначает вектор-столбец из \ (t \) единиц. Поскольку \ (\ mathbf = (\ mathbf _t - \ mathbf ) ^ \), мы можем сделать это эффективно, решив линейную систему уравнений \ [(\ mathbf _t - \ mathbf ) \ mathbf = \ mathbf \] для \ (\ mathbf \). Запись в \ (\ mathbf \), соответствующее начальному состоянию (пустое множество, \ (\ \)) - количество переходов. В этом случае получается цифра 939,8. Чтобы закончить, нам просто нужно вычесть \ (1 \), потому что переход из начального состояния не считается ходом. Это дает наш окончательный ответ - 938,8 хода.

Мы также можем получить дисперсию минимального числа ходов как \ (2 (\ mathbf - \ mathbf _t) \ mathbf - \ mathbf \ circ \ mathbf \), где \ (\ circ \) обозначает (поэлементное) произведение Адамара. Для начального состояния дисперсия составляет 69,5, что дает стандартное отклонение в 8,3 хода.

Приложение B: Форма распределения

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

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

Итак, следующий вопрос: на какую сумму мы должны стремиться? Из анализа цепи Маркова, приведенного выше, мы определили, что существует 26 поглощающих (выигрышных) состояний, и мы также увидели, что они находятся в разных `` слоях сумм '', поэтому нет единой целевой суммы - есть несколько целевых сумм. . Что нам нужно знать, так это вероятность быть поглощенным в каждом состоянии, которая называется вероятностью поглощения . Затем мы можем сложить вероятности поглощения для каждого из поглощающих состояний в конкретном слое суммы, чтобы найти вероятность выигрыша с заданной целевой суммой.

Поглощающие вероятности

К счастью, вероятности поглощения также можно найти из фундаментальной матрицы. В частности, мы можем получить их, решив линейные уравнения \ [(\ mathbf _t - \ mathbf ) \ mathbf = \ mathbf \] для матрицы \ (t \ times r \) \ (\ mathbf \), чья запись \ ((i, j) \) представляет собой вероятность быть поглощенным в состоянии \ (j \) при запуске из состояния \ ( я\). Как и раньше, нас интересуют вероятности поглощения при старте из начального состояния. На графике вероятностей поглощения есть 15 состояний поглощения, для которых вероятности достаточно велики, чтобы построить график (по крайней мере, \ (10 ​​^ \)):

В частности, большинство игр заканчиваются либо в состоянии \ (\ \) с суммой 2068, либо в состоянии \ (\ \) состояние, которое имеет сумму 2070. Суммирование всех поглощающих состояний по сумме слоев дает полные вероятности суммы слоев:

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

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

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

При такой интерпретации успехов, чтобы набрать заданную сумму \ (S \) за \ (M \) ходов, нам нужно \ (\ frac - M \) успехов из \ (M \) ходов. Это связано с тем, что каждый ход учитывает как минимум \ (2 \) к сумме, что дает общий вклад в \ (2M \), и каждый успех учитывает дополнительное \ (2 \) к сумме, что дает общий вклад \ ( 2 \ left (\ frac - M \ right) = S - 2M \); сложение этих вкладов дает желаемую сумму \ (S \).

Совместная вероятность получения суммы \ (S \) за несколько ходов \ (M \) тогда биномиальна, и, в частности, \ [\ mathrm (M = m, S = s) = B \ left (\ frac - m; m, 0,1 \ right) \], где \ (B (k; n, p) \) - функция массы вероятности для биномиальное распределение, которое дает вероятность точно \ (k \) успехов в \ (n \) испытаниях, где вероятность успеха равна \ (p \), а именно \ [B (k; n, p) = р ^ к (1-р) ^ \] где \ (n \ choose k \) обозначает биномиальный коэффициент.

Теперь, если мы знаем целевую сумму \ (S \), к которой мы стремимся, мы можем вычислить условное распределение количества ходов с учетом этой суммы, которая нас интересует, из совместного распределения. То есть мы можем найти \ (\ mathrm (M | S) \) как \ [\ mathrm (M | S) = \ гидроразрыва (M, S)> (S)>. \] где \ (\ mathrm (S) \) получается из совместного распределения суммированием \ (M \) для каждой возможной суммы \ (S \). Стоит отметить, что \ (\ mathrm

(S) \) меньше единицы для каждой возможной суммы, потому что всегда есть шанс, что игра «пропустит» сумму, поместив плитку 4.

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

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

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

Спасибо Хоуп Томас и Нейту Стемену за рецензирование черновиков этой статьи.

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

Сноски

Если мы позволим игроку принимать решения, у нас будет Марковский процесс принятия решений, а не цепь Маркова. Это будет предметом более позднего сообщения в блоге. ↩

Такое слияние пар одинаковых плиток позволяет уловить важный нюанс логики объединения в реальной игре: если у вас есть, например, четыре плитки по 2 в ряд, и вы проводите пальцем, чтобы объединить их, результатом будет две плитки по 4, а не одна плитка 8. То есть вы не можете объединить недавно объединенные плитки одним движением. ↩

Диаграммы здесь взяты из превосходного точечного инструмента в graphviz. Если мы не дадим точку, сгруппировав состояния вместе в слои по сумме, создание полного графика может занять довольно много времени. ↩

Появление в игре «Ты выиграл!» экран менялся несколько раз за те месяцы, когда я собирал эти данные. Кстати, игра в 2048 - не единственное, чем я занимался за эти месяцы. ↩

Еще новости