Случайные блуждания и цепи Маркова в геймдизайне06.05.2022 13:16

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

Всем привет, меня зовут Лев, я геймдизайнер из Whalekit. И в этой статье мы разберем две математические концепции: цепи Маркова и случайные блуждания. Сразу замечу, что статья скорее «поп», чем «науч», поэтому часть доказательств выведенных формул будет опущена. После теории мы перейдем к реальным кейсам, где эти инструменты могут пригодиться, например:

Сколько сундуков откроет игрок, если из сундуков могут выпасть еще сундуки;
Сколько золота уйдет на прокачку меча, если меч может ломаться;
Какая вероятность победить в денежном поединке.

Задача про алхимика

Представим игру, в которой мы играем за алхимика. Наша задача — собрать ингредиенты для нового зелья:

Ингредиент	Локация, где искать
Траворосли	Шахматная поляна
Речные метеориты	Космическая река
Ыдогя	Уборная тролля

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

Обозначим дороги следующим образом: (локация А → локация Б: вероятность перехода из локации А в локацию Б):

Дом → Шахматная поляна: 0.8
Дом → Уборная тролля: 0.2
Шахматная поляна → Дом: 0.5
Шахматная поляна → Уборная тролля: 0.3
Шахматная поляна → Космическая река: 0.2
Уборная тролля → Дом: 0.5
Уборная тролля → Шахматная поляна: 0.2
Уборная тролля → Космическая река: 0.3
Космическая река → Шахматная поляна: 0.5
Космическая река → Космическая река: 0.5

Обратите внимание, что сумма всех вероятностей переходов из каждой локации равна 1. Если сумма вышла меньше 1, то считаем, что разность — это вероятность перехода из А в А. А если больше, определенно что-то пошло не так.

Алхимик отправляется за ингредиентами. Вопрос: какова вероятность, что спустя два перехода он окажется у Космической реки?

Есть два возможных пути до реки, состоящих из двух переходов:

Дом → Шахматная поляна → Космическая река: 0.8 ⋅ 0.2 = 0.16
Дом → Уборная тролля → Космическая река: 0.2 ⋅ 0.3 = 0.06

Получается, что с вероятностью 0.22 алхимик окажется у реки.

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

Цепи Маркова

Введем следующие обозначения:

S — конечное множество состояний. В нашем случае это множество локаций: {Дом, Шахматная поляна, Уборная тролля, Космическая река};
Xi— состояние, в котором мы находимся после i-ого перехода, Xi∈ S. Иными словами, это локация на момент i;
Переход — это смена состояния Xiна Xi+1 с заданной вероятностью;
Случайный процесс — набор состояний {X0, X1, X2, …, Xn−1, Xn}, например, {Дом, Шахматная поляна, Космическая река, …, Дом}.

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

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

Теперь представим ориентированный граф в виде таблицы:

*Xi / Xi+1*	Дом	Шахматная поляна	Уборная тролля	Космическая река
Дом		0.8	0.2
Шахматная поляна	0.5		0.3	0.2
Уборная тролля	0.5	0.2		0.3
Космическая река		0.5		0.5

Таблицу представим как матрицу:

$T = \begin{bmatrix} 0 & 0.8 & 0.2 & 0 \\ 0.5 & 0 & 0.3 & 0.2 \\ 0.5 & 0.2 & 0 & 0.3 \\ 0 & 0.5 & 0 & 0.5 \end{bmatrix}$

Строго говоря, мы получили матрицу переходов, где:

Строки — настоящее, то есть, состояние Xi;
Столбцы — будущее, то есть, состояние Xi+1;
Элемент (i, j) — вероятность перехода из состояния Xiв Xj.

Более того, сама матрица получилась квадратной и отражает все возможные переходы, поэтому сумма строк равна 1.

Небольшое напоминание:
1. aij— элемент матрицы, где i — номер строки, j — столбца;
2. Можно складывать матрицы только одного размера. При этом складываются элементы с одинаковым индексом;
3. Произведение матриц определено только в том случае, если число столбцов первой матрицы равно числу строк второй. При умножении i-ой строки матрицы A на j-ый столбец B получим cij, а в совокупности они образуют новую матрицу C.

$C = A \cdot B \\ c_{ij} = \sum_{l=1}^m a_{il} \cdot b_{lj}$

Любая случайная величина (например, Xi) обладает распределением. В нашем случае можно записать его как вектор-строку размерности N, где N — мощность множества S.

Если состояние переходит только само в себя, то оно называется поглощающим.

Подсказка:
Расчеты для этой части статьи можно найти в Google Sheets.

Странствия алхимика

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

Всего у нас четыре локации — следовательно, мощность S = 4. Алхимик начинает путешествие из дома. Отсюда получим распределение случайной величины X0 и обозначим его в виде вектора-строки X0′:

$X_0' = \begin{bmatrix} 1 & 0 & 0 & 0\end{bmatrix}$

При умножении X0′ на T получим X1′ — вектор-строку распределения X1:

$\begin{bmatrix} 1 & 0 & 0 & 0\end{bmatrix} \cdot \begin{bmatrix} 0 & 0.8 & 0.2 & 0 \\ 0.5 & 0 & 0.3 & 0.2 \\ 0.5 & 0.2 & 0 & 0.3 \\ 0 & 0.5 & 0 & 0.5 \end{bmatrix} = \begin{bmatrix} 0 & 0.8 & 0.2 & 0\end{bmatrix}$

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

Далее при при умножении X1′ на T получим X2′ — вектор-строку распределения X2:

$\begin{bmatrix} 0 & 0.8 & 0.2 & 0\end{bmatrix} \cdot \begin{bmatrix} 0 & 0.8 & 0.2 & 0 \\ 0.5 & 0 & 0.3 & 0.2 \\ 0.5 & 0.2 & 0 & 0.3 \\ 0 & 0.5 & 0 & 0.5 \end{bmatrix} = \begin{bmatrix} 0.5 & 0.04 & 0.24 & 0.22 \end{bmatrix}$

Обратим внимание:

$\begin{bmatrix} 0.5 & 0.04 & 0.24 & 0.22 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0\end{bmatrix} \cdot \begin{bmatrix} 0 & 0.8 & 0.2 & 0 \\ 0.5 & 0 & 0.3 & 0.2 \\ 0.5 & 0.2 & 0 & 0.3 \\ 0 & 0.5 & 0 & 0.5 \end{bmatrix} \cdot \begin{bmatrix} 0 & 0.8 & 0.2 & 0 \\ 0.5 & 0 & 0.3 & 0.2 \\ 0.5 & 0.2 & 0 & 0.3 \\ 0 & 0.5 & 0 & 0.5 \end{bmatrix} = \\ \begin{bmatrix} 1 & 0 & 0 & 0\end{bmatrix} \cdot \begin{bmatrix} 0 & 0.8 & 0.2 & 0 \\ 0.5 & 0 & 0.3 & 0.2 \\ 0.5 & 0.2 & 0 & 0.3 \\ 0 & 0.5 & 0 & 0.5 \end{bmatrix} ^ 2$

Подсказка:
Матрицы можно умножать в Google Sheets или Excel при помощи = МУМНОМ ().

Таким образом, получим, что распределение на шаг t — это произведение начального распределения и матрицы переходов в степени t:

$\boxed{X_t' = X_0' \cdot T^t}$

Здесь первый элемент получившейся вектор-строки — это вероятность оказаться дома спустя t переходов. Задача решена.

Интересный факт:
Предел Tnпри n → ∞ даст вероятность быть в состоянии j после бесконечного количества шагов, где j — это j-ый столбец. Это также называется эквилибриумом (steady state). Значение состояния может также трактоваться, как время, которое будет проведено в нем, причем вне зависимости от начального состояния. Время в данном случае измеряется в процентах.

$\lim_{n \rightarrow ∞} T^n \approx \begin{bmatrix} 0.25 & 0.35 & 0.16 & 0.24 \\ 0.25 & 0.35 & 0.16 & 0.24 \\ 0.25 & 0.35 & 0.16 & 0.24 \\ 0.25 & 0.35 & 0.16 & 0.24 \end{bmatrix}$

Река не отпускает

На практике нас чаще интересует вероятность наступления какого-то события, чем его распределение. А что касается процессов — то вероятность достижения (hitting probability). Например, вероятность достичь подмножество A множества S.

Для удобства обозначим локации через индексы:

Дом;
Шахматная поляна;
Уборная тролля;
Космическая река.

Предположим, что A = {4}, и начальное состояние i = 1, в таком случае вероятность достижения — это вероятность попасть когда-либо из Дома на Космическую реку.

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

Новая матрица переходов:

$T = \begin{bmatrix} 0 & 0.8 & 0.2 & 0 \\ 0.5 & 0 & 0.3 & 0.2 \\ 0.5 & 0.2 & 0 & 0.3 \\ 0 & 0 & 0 & \color{red}{1} \end{bmatrix}$

Допустим, если A — поглощающее состояние, то hi— вероятность поглощения.

Применим следующую формулу:

$h_{i} = \begin{cases} 1, i \in A \\ \sum_{j \in S} p_{ij}h_{j}, i \notin A \end{cases}$

Подсказка, как работать с этой формулой:
1. Пройдем по каждому состоянию i от первого до последнего, обозначив их как h c индексом состояния:
1.1 Если i в множестве A, приравняем hiк 1.»Перевернутая буква Э» обозначает принадлежность, а зачеркнутая — не принадлежность. Например, i = 1 — то есть, дом — не входит в A, потому что A = {4}.
1.2 Если i в нем нет, приравняем i к сумме вероятностей переходов i → j, умноженных на соответствующие hj, пока нам неизвестные.
2. Получим набор связанных h, то есть — систему линейных уравнений, где неизвестные переменные — hi. В некотором смысле это школьное x.

Найдем каждое hiс помощью метода подстановки или любого другого. В таблицах это делается с помощью более сложного метода.

Результат должен быть минимально возможным, но при этом каждое значение системы не меньше 0.

Проведем расчет для h14:

$h_{1} = \underbrace{p_{11}h_{1}}_0 + p_{12}h_{2} + p_{13}h_{3} + \underbrace{p_{14}h_{4}}_0 = 0.8 \cdot h_{2} + 0.2 \cdot h_{3}$

Проделав это для каждого состояния, получим:

$\begin{cases} h_{1} = 0.8 \cdot h_{2} + 0.2 \cdot h_{3} \\ h_{2} = 0.5 \cdot h_{1} + 0.3 \cdot h_{3} + 0.2 \cdot h_{4} \\ h_{3} = 0.5 \cdot h_{1} + 0.2 \cdot h_{2} + 0.3 \cdot h_{4} \\ h_{4} = 1 \end{cases} \Rightarrow \begin{cases} h_{1} = 1 \\ h_{2} = 1 \\ h_{3} = 1 \\ h_{4} = 1\end{cases}$ $h_A = \begin{bmatrix} 1 & 1 & 1 & 1\end{bmatrix}$

Таким образом, из какого бы состояния алхимик ни начал, он обязательно попадет на реку. Вполне ожидаемо!

Шаги до неизбежности

Также часто может интересовать не столько вероятность наступления события, сколько его математическое ожидание (expected value). Когда речь заходит о случайных процессах, это время перехода из начального состояния в заданное (expected hitting time). Время — абстракция, которая может быть шагом, действием, чем захотим. Время попадания также часто называют временем достижения. Если A — поглощающее состояние, время также называют временем поглощения.

Применим следующую формулу:

$m_{i} = \begin{cases} 0, i \in A \\ 1 + \sum_{j \notin A} p_{ij}m_{j}, i \notin A \end{cases}$

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

Вопрос: через сколько ходов алхимик застрянет на реке?

Проведем расчет для m1:

$m_{1} = 1 + \underbrace{p_{11}m_{1}}_0 + p_{12}m_{2} + p_{13}m_{3} + \underbrace{p_{14}m_{4}}_0 = 1 + 0.8 \cdot m_{2} + 0.2 \cdot m_{3}$

Проделав это для каждого состояния, получим:

$\begin{cases} m_{1} = 1 + 0.8 \cdot m_{2} + 0.2 \cdot m_{3} \\ m_{2} = 1 + 0.5 \cdot m_{1} + 0.3 \cdot m_{3} \\ m_{3} = 1 + 0.5 \cdot m_{1} + 0.2 \cdot m_{2} \\ m_{4} = 0 \end{cases} \Rightarrow \begin{cases} m_{1} = \frac{37}{5} \approx 8 \\ m_{2} = \frac{13}{2} \approx 7 \\ m_{3} = 6 \\ m_{4} = 0\end{cases}$

Вот и получается, что алхимик примерно через 8 шагов будет заточен у реки (37/5 ближе к 7, но будем оптимистами — да и, как показывает практика, лучше округлять в большую сторону).

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

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

Алхимик варит зелья

Представим, что теперь алхимик делает магические зелья:

Начальное здоровье: 1, максимальное: 5;
Делаем зелье регенерации, которое восстанавливает +1 здоровье;
Иногда получаем плохое зелье, и оно отнимает 1 здоровье;
Вероятности сделать хорошее и плохое зелье равны;
При здоровье, равном 0, алхимик погибает, а при 5 — заканчивает эксперимент.

Вопрос: как скоро игра закончится — то есть, алхимик погибнет или полностью восстановит здоровье?

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

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

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

Рассмотрим случай полного восстановления здоровья.

Для того, чтобы попытаться найти закономерность, начнем с простых случаев. Самый банальный — мы выпили 4 правильно сваренных зелья подряд, и отсюда получим вероятность:

$\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{16}$

А если одно зелье отняло здоровье?

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

$\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} \cdot \frac{\color{green}1}{\color{green}2}\cdot \frac{\color{red}1}{\color{red}2}\cdot \frac{1}{2} = \frac{1}{64}$

Плохое зелье должно быть компенсировано хорошим, чтобы восполнить здоровье до максимума. Таких вариантов всего три — в зависимости от того, когда выпьем испорченное зелье:

С ростом числа плохих зелий растет и количество возможных вариантов. Один из вариантов их подсчета — представить все в виде графа.

Для 8 зелий (2 из которых — плохие) получаем 8 возможных путей:

Возникает два вопроса:

Сколько зелий можно брать? 5? 12?
Можно ли посчитать это аналитически, а не с помощью графа?

Мы понимаем, что надо восполнить 4 здоровья (если начинаем с 1 и максимально — 5), выпив n-ное количество зелий. В таком случае получаем:

m = 4 — здоровье, которое надо восстановить;
p — количество хороших зелий;
(n — p) — количество плохих зелий.

$p - (n - p) = m \\ p = \frac{m + n}{2}$

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

$8 - \frac{8 + 4}{2} = 2$

Любая попытка восстановить себе здоровье — это набор зелий, например {хорошее, плохое, хорошее, …, плохое}. В нашем случае такой набор состоит из 8 зелий, 2 из которых — плохие. Значит, достаточно рассчитать количество сочетаний без повторений.

Напомню формулу:

$\boxed{C^k_n=\frac{n!}{k!(n-k)!}}$

Получим:

$C^2_8=\frac{8!}{2!(8-2)!} = 28$

Но 28 намного больше 8! Мы что-то не учли на графе?

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

Ранние смерти:

Игрок изначально выпил плохое зелье;
Игрок выпил хорошее, а потом два плохих зелья.

Раннее оздоровление:

Игрок выпил 4 хороших зелья подряд;
Игрок выпил хорошее, потом одно плохое и 4 хороших.

Если посчитаем все такие комбинации, получим как раз 20 лишних кейсов. И по итогу 8 возможных.

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

$\frac{1}{16} + \frac{3}{64} + \frac{8}{256} + ...$

Легко заметить, что это почти обычная бесконечно убывающая прогрессия, сумму которой можем найти:

$\frac{\frac{1}{16}}{1 - \frac{17}{24}} = \frac{3}{14}$

Примем за веру, что мы не можем потеряться где-то в пространстве и постоянно пить то хорошее, то не очень зелье, то есть вероятность потерять алхимика:

$1 - \frac{3}{14} = \frac{11}{14}$

За кадром осталось:
1. Знаменатели дробей — вероятность (½)n, где n — количество зелий всего.
2. Применение формулы БГП к почти БГП не совсем верно, ведь отношение двух соседних дробей получается различным, что противоречит сути БГП. Однако можем посчитать среднее и получить результат в 17/24.
3. Для получения вероятности гибели алхимика можем проделать точно такую же операцию, как и для вероятности полного восстановления, что даст нам результат в 11/14.

Общий случай

Пусть начальное здоровье нашего алхимика — current (c), а максимальное — max (m). В таком случае, если c — ноль, то вероятность восстановить здоровье — 0, а если m, то 1. Если же c лежит где-то между, вероятность будет суммой слева или справа:

$P_c = \frac{1}{2} P_{c-1} + \frac{1}{2} P_{c+1} = \frac{P_{c-1}+P_{c+1}}{2}$

Отсюда можем получить систему линейных уравнений, где неизвестные — вероятность восстановить себе здоровье, если ты начинаешь с определенной позиции. Для удобства обозначим на числовой оси и отметим известные нам вероятности (концы). Получаем:

$\begin{cases} c = \frac{b+d}{2} \\ a = \frac{0+b}{2} \\ ... \\ g = \frac{f+1}{2} \end{cases}$

Решив эту систему уравнений, получим:

$\boxed{P_c = \frac{c}{m}}$

Если вернемся к нашему случаю, где c = 1, а m = 5, то получим 1, что почти совпадает с 13/14 (разница в 0.014).

Проделав такую же операцию, но поменяв края, получим вероятность в ⅘ — значит, у алхимика нет шансов быть в суперпозиции между смертью и жизнью. Более того, если мы считаем, что после достижения какого-то максимума здоровье продолжает восстанавливаться, получим:

$\boxed{\lim_{m \rightarrow ∞} \frac{m - c}{c} = 1}$

Сколько бы зелий алхимик ни выпил, рано или поздно он погибнет.

Сколько зелий придется выпить?

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

Логично, что крайние значения — нулевые, а n-ное — сумма соседних и ещё одно зелье в силу линейности величины:

$E_0 = 0 \\ E_m = 0 \\ E_n = 1 + E_{n-1} + E_{n+1}$

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

$\boxed{E_n = n(m-n)}$

Интересные факты:
1. Вероятности восстановиться полностью, находясь изначально с n, образуют арифметическую прогрессию;
2. Набор времени перехода — строка из треугольника Паскаля с номером m, но с нулями на краях.

Если вернуться к тому, что возможен оверхил, получим:

$\lim_{m \rightarrow ∞} 1 (m-1) = ∞$

Подсказка, откуда здесь берется бесконечность:
Опустим строгое определение предела. Пусть m — бесконечность. Бесконечность — это что-то очень огромное: мы можем из нее вычитать, прибавлять, умножать — и все равно получим бесконечность. Хотя иногда бывают исключения!

Можно выпить бесконечное количество зелий, но погибнуть в любом случае.

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

$\boxed{E_n = \frac{n}{1-2p}}$

За кадром осталось:
1. Решение рекурсивных выражений;
2. Вывод формулы для несимметричных блужданий.

Реальные Кейсы

Пришло время приступить к небольшой практике. Когда все это вообще может пригодиться?

Сундуки из сундука из сундука…

Предположим, что в игре есть следующая механика сундуков:

У игрока изначально есть 1 сундук;
С вероятностью 0.4 из него выпадут 2 таких же;
С вероятностью 0.6 не выпадет ничего.

Вопрос: сколько в среднем сундуков откроет один игрок?

Можем считать, что n — текущее количество сундуков, которое изначально равно 1, а каждое действиелибо увеличивает n на 1, либо уменьшает на 1. Увеличение на 1 обусловлено тем, что игрок как бы потерял 1 сундук, но получил 2 новых. Условия очень хорошо ложатся на концепцию блужданий. Следовательно, просто применяем формулу:

$\frac{n}{1-2p} =\frac{1}{1-2 \cdot 0.4} = 5$

Заточка меча

Предположим, что в игре есть следующая механика улучшения меча:

У игрока изначально меч 1 уровня, currentLevel = 1;
Максимальный уровень — 4;
Игрок может попытаться поднять уровень меча с помощью прокачки. Однако в процессе меч может сломаться и понизить свой уровень;
- Цена прокачки зависит от текущего уровня: 10 ∗ currentLevel;
- Вероятность улучшения: 1 − currentLevel/10;
- Если меч сломался при попытке улучшения с 1 уровня до 2, он остается 1 уровня.

Вопрос: сколько в среднем игрок потратит монет, чтобы улучшить меч до максимального уровня?

Представим механику в виде графа, вершины которого — уровни, а ребра — вероятность улучшения:

Это обычная цепь Маркова, и надо просто найти m1 с A = {4}, то есть — среднее количество шагов от 1 до 4 уровня. Воспользуемся формулой:

$m_{i} = \begin{cases} 0, i \in A \\ 1 + \sum_{j \notin A} p_{ij}m_{j}, i \notin A \end{cases}$

Получим: m1 ≈ 4.72, средняя цена улучшения = 20, и их осталось перемножить. Таким образом, в среднем игрок потратит около 94 монет, чтобы улучшить меч с 1 уровня до 4.

Вопрос на засыпку:, а справедливо ли вот так просто брать среднюю цену улучшения?

Денежный поединок (Gambler«s Ruin)

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

Есть два игрока, у которых n и m монеток;
Игроки последовательно подбрасывают монетку:
- Если выпала решка, первый игрок забирает у второго одну монетку;
- Если орел, то второй — у первого;
Игроки могут играть, пока у обоих строго больше 0 монеток.

Вопрос: с какой вероятностью проиграет первый игрок?

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

Переходы имеют вероятность 0.5, ведь мы просто подбрасываем монетку, кроме крайних — у них 1. Если проиграл или выиграл, то это окончательно.

Граф блужданий легко перенести в матрицу переходов:

$T = \begin{bmatrix} 1 & 0 & 0 & 0 & \dots & 0 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & \dots & 0 \\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & \dots & 0 \\ \dots & \dots & \dots & \dots & \ddots & \dots \\ 0 & 0 & 0 & 0 & \dots & 1 \\ \end{bmatrix}$

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

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

$\frac{m}{n+m}$

Соответственно, это и есть вероятность проигрыша первого.

Дополнительно можем посчитать количество бросков:

n(m + n - n) = nm

Если считать, что второй игрок — казино с бесконечным запасом денег, то первый рано или поздно проиграет, хотя перед этим сделает бесконечное количество бросков.

Заключение

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

Ах, да, все это можно было посчитать с помощью метода Монте-Карло — но, во-первых, это скучно, а во-вторых, полезно знать, что стоит за результатами, а не принимать их на веру. И еще надо уметь писать простые скрипты! Не бойтесь математики, развивайтесь и делайте хорошие игры!

Литература

Matthew Aldridge. MATH2750 Introduction to Markov Processes. University of Leeds, 2020–2021.
Eric Lehman, Tom Leighton, and Albert Meyer. 6.042J Mathematics for Computer Science. MIT, 2010.
Rachel Fewster. STATS325 Stochastic Processes. University of Auckland, 2014.
Ian Schreiber, Brenda Romero. Game Balance. 2022.

Иллюстрации by shabbyrtist