Статьи

Метод Монте-Карло

Один мой друг боялся летать на самолетах.

Как-то раз он спросил меня: «Какова вероятность того, что на самолете будет бомба?» Я ответил, что не могу сказать точно, но примерно один шанс на миллион.

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

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

Теория вероятностей — штука чрезвычайно интересная и местами очень полезная.

Илья достаточно критично написал о реальной необходимости использования теории вероятностей в гейм-дизайне. Спорить я с ним сейчас не буду (да и не уверен, что вообще хочу). Вместо этого поговорим об отличиях теории и практики вероятностей.

Старые солдаты гейм-дизайнерского фронта не знают слов любви, но зато им известно, что на самом деле есть две вероятности любого события.

Теоретическая и практическая вероятности

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

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

Теоретическая вероятность получить на орехи равна 1/6 или 16,67%.
Практическую вероятность вы узнаете, когда аристократ бросит кубик, скажем, 100 раз. (Я упоминал о его хорошем настроении? Я солгал.)

Например, аристократ из 100 попыток выбросил шестёрку 22 раза.
Помимо того, что вам точно влетит, это значит, что практическая вероятность выпадения шестёрки равна 22%.

Не так уж и далеко от теоретической вероятности, но разницу вы чувствуете, не правда ли? Разумеется, чем большее количество попыток сделает аристократ, тем больше практическая вероятность приблизится к теоретической. Этот подход к вычислению вероятности события и называется «серией научных бросков кубика», также он известен как…

Метод Монте-Карло. Джеймс Бонд здесь просто для красоты.

Метод Монте-Карло

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

Если вы хотя бы немного знаете программирование — cмоделируете миллионы попыток за несколько минут. Если нет, то вам поможет наш любимый Excel / Google Spreadsheets.

Представим себе игру, в которой несколько игроков должны создавать предметы по случайно выдаваемым рецептам.
В начале игры каждый игрок получает по 3 рецепта. Каждый рецепт требует разного количества ресурсов и приносит разное количество победных очков.

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

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

Давайте попробуем смоделировать наш пример с помощью Google Spreadsheets.

Настройка математической модели

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

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

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

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

Теперь нам нужно смоделировать случайную раздачу рецептов между игроками.

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

В столбце B мы расположили названия (id) всех рецептов, а в столбце А мы генерируем случайные числа с помощью функции Rand().

Почему я использую Rand(), а не Randbetween(1,20)? Можно использовать и Randbetween(), но необходимо помнить, что результаты функции всегда случайны. В этом случае я могу получить одинаковые значения. А это вызовет проблемы с сортировкой. Rand() же дает 15 знаков после запятой, что сводит шанс точного повторения практически на нет.

Приступим к сортировке. Просто так отсортировать наш список не получится, потому что порядок будет меняться при каждом “перемешивании” рецептов. Воспользуемся комбинацией функций Vlookup() и Small().

Мы помним, что Small() возвращает n-нное наименьшее значение в списке. Поэтому для начала в столбце D сделаем список от 1 до 20, который будет олицетворять собой порядок рецептов в начальной раздаче.

Затем в Е2 мы используем Small(), чтобы вернуть наименьшее случайное значение из столбца А: =Small(A:A,D2).

Следующий шаг — вернуть id нашего рецепта из столбца B с помощью Vlookup(): =Vlookup(Small(A:A,D2)),A:B,2,0).

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

Теперь нам осталось только распределить рецепты между игроками. Создадим ещё одну небольшую табличку в этой же вкладке. У нас четыре игрока, и каждому из них мы хотим раздать по три рецепта. Первый игрок получит 1, 5 и 9 рецепт по счету, и т.д. Не забываем вбивать значения рецептов ссылками (=E2, =E3, и т.д.).

Ниже подсчитаем количество необходимых ресурсов и очков для каждого игрока. Для этого используем кучу Vlookup() со ссылками на нашу вторую вкладку Sheet2, где хранится информация о параметрах рецептов. Не забывайте менять в формуле номер столбца для каждого ресурса (Сталь — 3, Мифрил — 4, Пыль — 5, Очки — 2).

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

Автоматизация тестов.

…или можно сделать это стильно!

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

Этот ряд я назвал “Ключ”, потому что это отправная точка нашей симуляции. Отталкиваясь от него мы будем создавать нашу тысячу моделей. И есть три пути…

Путь Экселя
Проще всего сделать это в Excel.

Выбирайте всю вашу ключевую строку, включая ячейку со словом “Ключ”, и тяните рамку вниз до самого конца. В итоге у вас будет выбрано 1000 строк и несколько столбцов. Теперь кликайте Data -> What-If Analysis -> Data Table. В появившемся окне оставляйте Row input cell пустым, а для Column input cell выберите любую пустую ячейку, не входящую в нужную нам область.

Жмите ОК, откидывайтесь на спинку кресла и позвольте Экселю сотворить всю магию за вас. Он прогонит нашу модель тысячу раз и запишет всё в табличку.

Путь Гуглодоков
Brace yourselves. Тут все будет немного сложнее.

  1. Берем формулу из столбца D и заменяем C2 на ключ (F17:F1016).

2. Так как у нас нет 21 рецепта, нам нужно итеративно прогонять всё по 20, поэтому превращаем любое число в его порядок при 20 рецептах:

(KEY - 20 * (ROUNDDOWN(KEY/20)))+1

Например, при ключе = 62:

(62 - 20 * (ROUNDDOWN(62/20)))+1 = 3

3. Вставляем эту формулу вместо (F17:F1016) и получаем:

Vlookup(Small($A:$A,(($F17:$F1016)-20*(ROUNDDOWN($F17:$F1016/20)))+1),$A:$B,2,0)

4. Берем формулу поиска из G8 и вместо поискового значения вставляем результат из 3 пункта.

5. Важно прописать над столбцами цифры поиска в таблице (3,4,5,2).

После этого вставляем ссылку на эту цифру вместо 3,4,5,2 в нашей формуле. Получаем:

Vlookup(Vlookup(Small($A:$A,(($F17:$F1016)-20*(ROUNDDOWN($F17:$F1016/20)))+1),$A:$B,2,0),Sheet2!$A$3:$E$22,G$14,0)

6. Складываем ресурсы 3 рецептов по нашей формуле:

Vlookup(Vlookup(Small($A:$A,(($F17:$F1016)-20*(ROUNDDOWN($F17:$F1016/20)))+1),$A:$B,2,0),Sheet2!$A$3:$E$22,G$14,0)+Vlookup(Vlookup(Small($A:$A,(($F17:$F1016)-20*(ROUNDDOWN($F17:$F1016/20)))+1),$A:$B,2,0),Sheet2!$A$3:$E$22,G$14,0)+Vlookup(Vlookup(Small($A:$A,(($F17:$F1016)-20*(ROUNDDOWN($F17:$F1016/20)))+1),$A:$B,2,0),Sheet2!$A$3:$E$22,G$14,0)

7. Обёртываем это в ARRAYFORMULA, которая прочитает $F17:$F1016 и посчитает значения для всех ключей и автоматом вставит во все поля.

8. Копируем всё по горизонтали, не забывая проставить $ там где надо, чтобы ничего не сдвигалось.

9. Выдыхаем и благодарим Ларетиана, что всё закончилось.

Путь скрипта
Достаточно простой способ для тех, кто не боится набить (скопипастить) десяток строк в редакторе скриптов гуглодоков.

  1. Создаем вкладку History в нашем документе и копируем туда наши две строчки:

2. Открываем Script Editor и пишем туда такой вот простенький скрипт:

function recordHistory() {
     var activeSS = SpreadsheetApp.getActiveSpreadsheet();
     var sheet = activeSS.getSheetByName("History");
     var source = sheet.getRange("$A$2:$W$2");
     var values = source.getValues();
     var i = 0;
while (i<1000) {
i++;
values[0][0] = i;
sheet.appendRow(values[0]);
values = source.getValues();
}
};


P.S. Я не то чтобы труъ-мастер скриптов, этот просто работает. Если у кого-то появятся замечания и комментарии по его улучшению — велкам.

3. Запускаем его и наслаждаемся массивом данных:

Обработка результатов

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

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

Если у вас есть цель, представление о балансе, видение — тогда вы сможете сравнить полученные с помощью Монте-Карло показатели со своими ожиданиями. А затем поправить баланс в нужную сторону.

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

Мифрил и Чародейная Пыль более-менее сбалансированы относительно друг друга, тогда как Сталь — ресурс гораздо более востребованный. Это не страшно, если вы так и задумывали. Главное не забудьте убедиться, что в вашей игре достаточно способов получить Сталь.

Среднее количество Очков на игрока ~18 за одну партию, при этом минимум Очков — 9, а максимум — 27. Среднее общее количество Очков у всех игроков — 72. Среднее максимальное количество Очков у одного игрока — 22 за партию. При этом разница между максимальным и минимальным количество Очков — 8.

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

Разумеется, этот метод не способен в полной мере заменить плей-тесты. Увы, математика не способна однозначно рассказать вам, насколько весело играть в вашу игру. Также метод Монте-Карло не очень хорошо дает понять о разнообразных применимых в игре стратегиях и тактиках. Монте-Карло не может принимать сложных решений или ударять вам в спину в неожиданный момент. В отличие от ваших друзей / плей-тестеров 🙂

Но все же это очень удобный инструмент для определения слабых мест в вашем балансе и их исправления.

Гуглодок со всеми вычислениями и формулами лежит здесь.

Надеюсь, этот материал был вам полезен! Увидимся в следующих постах!

Спасибо Ilya Ostashko за неоценимую помощь в написании поста.

4 комментария

Добавить комментарий для Sinichkin Отменить ответ