Моделирование игр с помощью цепей Маркова

Моделирование игр с использованием цепей Маркова

Исследование вероятностного моделирования с использованием игры “Закрыть коробку”

Введение

От игры в карты с друзьями до выигрыша денег за рулеточным столом, радость от отличной игры неотразима для большинства. Но несмотря на то, насколько весело, после нескольких поражений даже самые оптимистичные игроки не могут не задаться вопросом: “Игра подстроена под определенный исход?” Для тех из нас, кто обладает некоторыми знаниями в области вероятности, оставить этот вопрос без ответа может быть неприятным. В этой статье мы рассмотрим тип вероятностной модели для ответа на подобные вопросы. В частности, я покажу, как Марковские цепи могут быть применены к игре “Закрыть коробку”, в надежде вдохновить вас использовать вероятность для ответа на свои собственные вопросы, связанные с играми.

Что такое Марковская цепь и как она связана с играми?

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

Предположим, вы собираетесь играть в азартную игру с последовательностью честных подбрасываний монетки. В начале игры у вас есть 5 долларов, и перед каждым подбрасыванием монетки вы предсказываете результат (орел или решка). За каждое правильное предсказание вы получаете доллар, а за неправильное предсказание теряете доллар. Игра завершается, когда вы достигаете 0 или 10 долларов.

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

• Ваш собственный персональный ЛаМа
• Обновление визуализации данных овладение временной ресемплированием в Pandas
• Понимание минимальных остовных деревьев важное понятие в теории графов

На диаграмме выше оранжевые кружки представляют состояния игры, а стрелки представляют вероятность перехода между состояниями. Обратите внимание, что все вероятности перехода равны 0,5, так как изменение состояний требует правильного предсказания результата честного подбрасывания монетки. Кроме того, состояния 0 и 10 имеют стрелку, указывающую на себя, помеченную вероятностью 1, так как это конечные состояния игры.

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

1. Какова ожидаемая вероятность выигрыша/проигрыша?
2. Сколько шагов (подбрасываний монетки) в среднем потребуется для победы/проигрыша в игре?
3. После t шагов (подбрасываний монетки) каково распределение вероятностей по состояниям игры?

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

Объяснение игры “Закрыть коробку”

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

Shut the Box – это многопользовательская игра, которая играется на доске (показано выше) и состоит из девяти плиток (помеченных от 1 до 9) и двух шестигранных кубиков. На каждом ходу каждой игрока все плитки находятся в вертикальном положении. Затем бросаются два кубика, и игроку разрешается опустить плитки, сумма которых равна объединенной значению двух кубиков. Затем игрок повторяет этот процесс бросания кубиков и опускания плиток, пока существует подмножество вертикальных плиток, сумма которых равна объединенному значению двух кубиков. В этот момент ход игрока заканчивается, и его счет равен сумме плиток, которые все еще находятся в вертикальном положении на доске. В этой версии игры после того, как все игроки закончили свои ходы, победителем считается игрок с наименьшим счетом. Однако, если ход игрока заканчивается потому, что он смог опустить все плитки (т.е. “захлопнуть коробку”), он автоматически выигрывает игру. Именно это правило привлекло мое внимание, и поэтому будет основой этого исследования. Конкретно, я хотел ответить на вопрос: насколько сложно “захлопнуть коробку”?

Моделирование игры “Захлопни коробку” с использованием цепей Маркова

Из предыдущих разделов может быть ясно, что теперь мы должны моделировать игру “Захлопни коробку” как цепь Маркова. Хотя это может показаться интуитивным следующим шагом, давайте убедимся, что это возможно, проверив, сохраняется ли свойство Маркова. Для этого мы определим уникальные состояния этой игры как все подмножества множества {1, 2, 3, 4, 5, 6, 7, 8, 9}. Это связано с тем, что в любой момент во время хода игрока его можно однозначно определить по тому, какие плитки подняты и опущены. Численно мы можем рассматривать эти состояния как 9-разрядные двоичные числа (поднятая плитка – это 1), их всего 2⁹, что дает 512 уникальных состояний. При таком определении состояний свойство Маркова сохраняется, так как только вероятностные характеристики кубиков, текущее состояние и правила игры определяют вероятность перехода между состояниями. Самое главное, зная текущее состояние, предыдущие состояния, достигнутые во время хода игрока, не влияют на вероятность достижения других состояний в будущем.

Теперь, когда состояния хорошо определены, и мы убедились, что “Захлопни коробку” действительно можно моделировать как цепь Маркова, осталось определить только матрицу переходов T. Конкретно, Tᵢₖ (элемент в i-й строке и k-м столбце) представляет собой вероятность перехода из состояния i в состояние k. При определении этих вероятностей возникают интересные сложности моделирования этой игры.

Чтобы вычислить вероятность перехода из одного состояния в другое, нам нужно ответить на вопрос: “какие действия должны произойти в игре, чтобы состояние изменилось?” Для нашей игры “Захлопни коробку” существуют два вероятностных действия, которые происходят для определения следующего состояния: бросок кубика и выбор плиток для опускания. Давайте начнем с рассмотрения роли кубика в переходе между двумя состояниями i и k. Пусть Sᵢ и Sₖ будут множествами, содержащими поднятые номера в состояниях i и k соответственно. Чтобы вероятность перехода от состояния i к состоянию k была ненулевой, ясно, что Sₖ должно быть подмножеством Sᵢ. Это связано с тем, что количество поднятых плиток должно уменьшаться при переходе между состояниями, и плитки не могут быть подняты после опускания. При таком представлении состояния и предположении Sₖ ⊂ Sᵢ, плитки, опущенные в процессе перехода между состояниями i и k, образуют множество D = Sᵢ – Sₖ (элементы в Sᵢ, которых нет в Sₖ).

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

где X₁ и X₂ – дискретные случайные переменные, представляющие значения двух кубиков. Если мы позволим z быть суммой элементов в D, то вероятность того, что указанное уравнение выполняется при броске двух шестигранных кубиков, может быть вычислена следующим образом:

С помощью вышеприведенных результатов для точных вероятностей переходов мы теперь можем использовать некоторые из великолепных свойств цепей Маркова, чтобы ответить на вопрос: насколько сложно “заблокировать ящик”? В частности, мы можем ответить на вопрос: какова вероятность того, что игрок “закроет ящик” с использованием полностью случайной стратегии?

Вычисление вероятности выигрыша в “Закрывание ящика” с использованием Python

Для вычисления вероятности “выигрыша/проигрыша” в этой игре важно понимание полезности матрицы переходов. Для цепи Маркова матрица переходов позволяет нам изучать, как разпределение вероятностей по состояниям меняется после одного перехода, используя только умножение матрицы на вектор. Математически это можно записать так:

где T – матрица переходов, а πₜ – вектор-строка, представляющий распределение вероятностей по всем состояниям после t переходов. Таким образом, имея информацию о текущей вероятности нахождения в любом состоянии, мы можем ответить на вопрос: “какова вероятность нахождения в любом состоянии после одного броска кубика при условии, что мы выбираем плитки для переворачивания случайным образом?” Более того, с нашим знанием о детерминированном начальном состоянии игры (все плитки перевернуты вверх) мы легко можем определить π₀ и рекурсивно умножить его на Т, чтобы определить распределение по состояниям после произвольного числа переходов (бросок кубика + переворот плиток). Эта рекурсия может быть записана как следующее замкнутое выражение для πₜ:

Цепь Маркова, моделирующая “Закрывание ящика”, имеет два конечных состояния: выигрыш и проигрыш, которые однажды достигнуты, не могут быть покинуты (иначе говоря, абсорбирующие состояния). Таким образом, мы можем быть уверены, что распределение по всем состояниям будет сходиться к распределению по этим двум состояниям после некоторого конечного числа переходов. Интуитивно это утверждение подчеркивает тот факт, что ход игрока должен закончиться либо “закрытием ящика”, либо неудачей в этом, и поэтому существует конечный лимит на количество ходов, которое игрок может сделать за один ход.

Чтобы найти этот верхний предел, отметим, что самый длинный ход происходит, когда игрок переворачивает одну плитку после каждого броска кубика, пока плитка с меткой “1” не останется вверху, и, следовательно, в следующем броске кубика игрок не сможет “закрыть ящик”. Эта последовательность действий составляет в общей сложности 9 ходов, так как всего 9 плиток. Таким образом, решение вероятности выигрыша/проигрыша сводится к простому условию t ≥ 9 и вычислению πₜ. После вычисления πₜ вероятность того, что игрок “закроет ящик” с помощью случайной стратегии, является первым элементом в πₜ, так как это соответствует состоянию, при котором все плитки перевернуты вниз (S₀). Кроме того, рекурсивный процесс развития состояния распределения может быть повторен, начиная с 0, пока распределение не сойдется. Кроме того, существуют более быстрые методы для вычисления πₜ в этом случае, которые я не рассмотрю в этой статье. Они используют наличие абсорбирующих состояний и специальное определение матрицы переходов. Узнайте больше здесь: https://en.wikipedia.org/wiki/Absorbing_Markov_chain

Для вычисление вероятности выигрыша/проигрыша в Python мы полностью полагаемся на библиотеку для научных вычислений Numpy. Сначала мы определяем количество плиток, количество кубиков и количество состояний в игре, соответственно 9, 2 и 513.

num_tiles = 9num_dice = 2num_states = (2**num_tiles)+1 # +1 для состояния "игра окончена/проигрыш"

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

# Генерация представления всех возможных состоянийtile_nums = [i for i in range(1, num_tiles+1)]states = []for i in range(0, 2**num_tiles):  binary_rep = np.binary_repr(int(i), width=num_tiles)  states.append([tile_nums[idx] for idx, a in enumerate(binary_rep) if a == '1'])

Здесь функция binary_repr из библиотеки Numpy очень полезна, поскольку она генерирует двоичное представление состояния с использованием целого числа i. Таким образом, найдя позиции единиц в этой строке, мы можем определить, какие плитки находятся в вертикальном положении в состоянии i.

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

# Генерируем матрицу переходовtransition_matrix = np.zeros((num_states, num_states))for i in range(num_states):  for j in range(num_states):    transition_matrix[i][j] = compute_transition_probability(i, j)  transition_matrix[i][num_states-1] = 1 - transition_matrix[i][:num_states-1].sum()  assert np.allclose(transition_matrix[i].sum(), 1), "Матрица переходов не является стохастической"

Наконец, с использованием матрицы переходов мы отвечаем на основной вопрос этого исследования: какова вероятность того, что игрок “закроет коробку” при полностью случайной стратегии? Для этого мы должны определить начальное распределение, π₀, для всех состояний следующим образом:

# Определение начального распределения состоянийinit_state_dist = np.zeros((1, num_states))init_state_dist[:, num_states-2] = 1

Поскольку игра всегда начинается с вертикального положения всех плиток, распределение состояний представляет собой строковый вектор длиной 513 со значениями ноль для всех элементов, кроме элемента 511 (индексация с нуля), где ставится единица. Это связано с тем, что двоичное представление числа 511 – это строка “111111111”, которая соответствует состоянию с вертикальным положением всех плиток.

Определив начальное распределение, мы можем получить вероятность “закрытия коробки” с помощью формулы πₜ = π₀Tᵗ, где t = 9 для получения сходящегося распределения состояний. Еще раз, мы можем установить t = 9, потому что π₉T = π₉, и, следовательно, использование значения большего, чем девять для t, приводит к ненужным вычислениям. Код, решающий эту задачу, выглядит следующим образом:

# Вычисление и печать вероятностей выигрыша и проигрышаt = 9multiple_transition_matrix = np.linalg.matrix_power(transition_matrix, t)final_dist = np.matmul(init_state_dist, multiple_transition_matrix)win_prob = final_dist[0, 0]lose_prob = final_dist[0, num_states-1]# Печать результатов с точностью до 4 десятичных знаковprint("Вероятность выигрыша: {:.4f}".format(win_prob))print("Вероятность проигрыша: {:.4f}".format(lose_prob))

В этом фрагменте кода мы используем функции matrix_power и matmul из библиотеки Numpy для вычисления матрицы T₉ и вектора π₉ соответственно. Используя эти результаты, вероятность “закрытия коробки” просто хранится как первый элемент вектора π₉, который соответствует состоянию без вертикальных плиток (“000000000” в двоичной системе). С учетом этого, мы окончательно узнаем, что с использованием полностью случайной стратегии очень сложно “закрыть коробку” (шанс около 2%)! (точные значения вероятностей указаны ниже).

Вышеприведенный код и модельная формула с некоторыми модификациями могут быть расширены для поддержки вариантов игры “Shut the Box” с любым количеством плиток и любым количеством игральных костей. Следовательно, я визуализировал график вероятности выигрыша при изменении количества игральных костей и количества плиток:

Заключение

В этой статье мы исследовали цепи Маркова и их конкретное применение для ответов на вопросы об игре “Shut the Box”. Тем не менее, техники, на которые я обратил внимание, с некоторыми критическими мыслями и изменениями, могут быть использованы для моделирования множества игр. Таким образом, хотя ваши шансы “закрыть коробку” составляют 2 из 100, я уверен, что вы сможете добиться большего успеха, используя вероятностное моделирование для ответов на свои любимые игровые вопросы.

За исключением случаев, указанных иначе, все изображения принадлежат автору