tvin 26 окт 2020 в 13:17

Баланс «камень — ножницы — бумага». Математический подход к решению задачи

4 мин

6.3K

Разработка игр*Дизайн игр*Игры и игровые консоли

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

Статья состоит из 3 частей:

Постановка задачи
Формализация (переход к постановке на математическом языке)
Решение

Постановка задачи

Пусть есть три класса кораблей – линкоры, крейсера и эсминцы. У каждого из них есть очки жизней, урон, наносимый противнику при попадании и меткость. Необходимо настроить эти параметры таким образом, чтобы в 60% случаев каждый тип побеждал своего антагониста:

Линкоры побеждают крейсера
Крейсера побеждают эсминцы
Эсминцы побеждают линкоры

Формализация

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

В нашей задаче взаимодействие игроков происходит по следующей схеме:

Игрок 1 делает выстрел. Вероятность попадания – p1
В случае попадания урон dam= dam1, где dam1 – величина урона, который наносит первый игрок при попадании. В случае промаха dam= 0. Количество здоровья игрока 2 уменьшается на величину dam
Если количество единиц здоровья игрока 2 меньше либо равно 0 (hp2 <= 0), то взаимодействие оканчивается победой игрока 1, в противном случае ход переходит к игроку 2
Игрок 2 делает выстрел. Вероятность попадания – p2
В случае попадания урон dam= dam2, где dam2 – величина урона, который наносит второй игрок при попадании. В случае промаха dam= 0. Количество здоровья игрока 1 уменьшается на величину dam
Если количество единиц здоровья игрока 1 меньше либо равно 0 (hp1 <= 0), то взаимодействие оканчивается победой игрока 2, в противном случае ход переходит к игроку 1 и процесс начинается заново с пункта 1

Решение

Решение состоит из 3 этапов

Определить вероятность победы игрока 1 за k выстрелов
Определить вероятность победы игрока 1 за произвольное количество выстрелов
Произвести балансировку юнитов в соответствии с условием задачи

Этап 1

Пусть параметры игроков даны и равны (hp1, dam1, p1), (hp2, dam2, p2). Для того, чтобы упростить дальнейшие вычисления понизим количество переменных заменив hp и dam на их отношение k=hp/dam. Таким образом, вместо 6 переменных будем работать с 4, а именно (k1, p1), (k2, p2).

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

Итак, вероятность того, что игрок 1 сделав k выстрелов попадет ровно k2 раз равна

$C_{k-1}^{k_2-1}p_1^{k_2}(1-p_1)^{k-k_2}$

(т.е. среди первых k-1 выстрелов будет ровно k2-1 попадание, и k-ый выстрел будет попаданием). Одновременно с этим игрок 2, сделав k-1 выстрел должен попасть менее k1 раз. Вероятность этого события равна

$\sum_{i=0}^{min(k_1-1, k-1)}C_{k-1}^{i}p_2^i(1-p_2)^{k-1-i}$

(т.е. игрок 2 попадаем не более чем min(k1-1, k-1) раз). С учетом выше сказанного получаем, что вероятность для игрока 1 победить, сделав ровно k выстрелов равна

$\begin{cases} p(1wins|k)=[C_{k-1}^{k_2-1}p_1^{k_2}(1-p_1)^{k-k_2}]\sum_{i=0}^{min(k_1-1, k-1)}C_{k-1}^{i}p_2^i(1-p_2)^{k-1-i}, \: if \: k\geq k_2 \\ p(1wins|k)=0, \: if\: k<k_2\end{cases}$

Этап 2

Используя формулу полной вероятности приходим с учетом последней формулы к тому, что вероятность игрока 1 победить за произвольное количество выстрелов равна

$p(1wins)=\sum_{i=0}^{\infty}p(1wins|i)$

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

Этап 3

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

Решение можно искать по следующему алгоритму

Понятно, что искомые переменные (hp, dam, p) не могут принимать произвольных значений, а находятся в рамках некоторых интервалов. Зададим эти интервалы:
1. Для вероятностей победы классов над антагонистами
  1. 0.595 <= p(линкор, крейсер) <= 0.605
  2. 0.595 <= p(крейсер, эсминец) <= 0.605
  3. 0.595 <= p(эсминец, линкор) <= 0.605
2. Для здоровья: нижняя граница 60, верхняя – 200 (здесь беру общие границы для всех классов, но можно было задать для каждого отдельно, на подход к решению это никак не повлияет)
3. Для урона: нижняя граница 8, верхняя – 15
4. Вероятности будем искать с шагом 0.01, здоровье – с шагом 10, а урон – с шагом 1.
Находим все (k1, p1), (k2, p2) такие, что 0.595 <= p(x, y) <= 0.605 (p(x, y) – вероятность победы игрока x над игроком y см. этап 2)
Находим все (k1, k2, k3, k4, k5, k6, p1, p2, p3) так, чтобы удовлетворять удовлетворить ограничениям из пункта 1.1 данного алгоритма
Для того, чтобы перейти от найденных вспомогательных переменных к исходным, необходимо решить систему уравнений.

$\begin{cases} {hp_1\over{dam_2}}=k_1, {hp_2\over{dam_1}}=k_2 \\ {hp_2\over{dam_3}}=k_3, {hp_3\over{dam_2}}=k_4 \\ {hp_3\over{dam_1}}=k_5, {hp_1\over{s \: dam_3}}=k_6 \end{cases}$

Здесь s – десятичное число от 0 до 1, смысл которого объясняется ниже

Найденные наборы (hp1, dam1, p1), (hp2, dam2, p2), (hp3, dam3, p3) – искомое решение задачи баланса.

Важное замечание по пункту 4 алгоритма. Решения задачи в изначальной постановке не существует т.к. в рамках принятых ограничений один из классов (линкоры) обязательно будет доминировать. Для того чтобы это исправить его антагонисту (эсминцам) необходимо дать бонус к атаке. Параметр s отвечает за коррекцию, на пример, s= 1.3 – означает 30% бонус.

Итоги

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

Успехов в балансе

Камень, ножницы, бумага. Цу, е, фа ;)

Теги:

Хабы:

Баланс «камень — ножницы — бумага». Математический подход к решению задачи

Постановка задачи

Формализация

Решение

Итоги

Публикации

Истории

Работа

Ближайшие события