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

Решаем геймдизайнерские задачки при помощи высшей математики.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Получим:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. У игрока изначально меч 1 уровня, currentLevel = 1;

2. Максимальный уровень — 4;

3. Игрок может попытаться поднять уровень меча с помощью прокачки. Однако в процессе меч может сломаться и понизить свой уровень;

3.1. Цена прокачки зависит от текущего уровня: 10 ∗ currentLevel;

3.2. Вероятность улучшения: 1 − currentLevel/10;

3.3. Если меч сломался при попытке улучшения с 1 уровня до 2, он остается 1 уровня.

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

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

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

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

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

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

1. Есть два игрока, у которых n и m монеток;

2. Игроки последовательно подбрасывают монетку:

2.1. Если выпала решка, первый игрок забирает у второго одну монетку;

2.2. Если орел, то второй — у первого;

3. Игроки могут играть, пока у обоих строго больше 0 монеток.

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

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

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

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

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

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

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

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

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

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

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

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