wheel-of-fortune-spin-id-number_b8e1102d6248f63b

Вероятностный баланс: тюним святой рандом

  • Facebook
  • Twitter
  • VKontakte
  • LinkedIn
  • Email
  • RSS

Балансируя игровые механики, гейм дизайнер свято верит в то, что и математика не подведет, и программист напишет код так, чтобы 2 было равно 2, и не иначе. Истина, как обычно бывает, где-то рядом. Рандом, то вовсе и не такой уж то рандом! О том, как улучшить вероятностный баланс читайте в этой заметке.

Вначале немного истории…

Поднимите руки те, кто четко прописали вероятность какого-то события, а потом в аналитике, на большой выборке, наблюдал, что, по факту, это событие было чаще/реже заложенной вероятности?

Например, в колесе фортуны я ставил вероятность Джекпота — 1%, спустя 6 месяцев увидел, что Джекпот выпадет значительно чаще, и это создает дыру в балансе. Как из 1% получилось 1,8%?

Чтобы ответить на этот вопрос надо капнуть глубже. Начнем с теории.

Что такое вероятностный баланс

gty-wheel-of-fortune-ll-130425-wmain-jpg_120026

Вероятностным балансом, мы называем баланс, в котором исход определяется вероятностями. Для примера возьмем все тоже «колесо фортуны». У колеса есть, например 10 секторов, и подразумевается, что вероятности выпадения каждого сектора равны между собой. Это был бы честный рандом, если бы он был в жизни.

Пример живой реализации вы можете посмотреть в гугле написав запрос «колесо фортуны» или пройдя по этой ссылке.

Конфиг такого колеса (на 5 значений) выглядит так:

Сектор ID Значение Вероятность
1 1 20%
2 2 20%
3 3 20%
4 4 20%
5 5 20%

Это честное колесо, вероятность выпадения каждого сектора равны между собой — это 20%. По крайней мере так думает балансировщик.

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

Пример конфига колеса с вероятностям балансом

Сектор ID Значение Вероятность
1 1.000.000 1%
2 100 15%
3 200 10%
4 2.000 5%
5 350 10%
6 100 15%
7 5.000 5%
8 200 14%
9 300 10%
10 100 15%

Тут каждый третий сектор — дорогой, он окружен более дешевыми выигрышами, один из которых — Джекпот. Вероятности распределены таким образом, чтобы минимальное значение выпадало максимально часто (45% от всех исходов), эти сектора находятся рядом с Джекпотом (#2,10), и у игрока будет все время ощущение «почти» — т.е. чуток не докрутил, или чуток перекрутил.

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

Как работает рандом

И так, Гейм-Диз написал таблицу вероятностей, и, скорее всего даже экспортнул ее в конфвиг. Вжух-вжух — оно работает. Давайте разбираемся как.

На сервере/клиенте выстраивается ряд всех исходов, а затем по принципу как у «random.org» выбирается случайно число от 1 до 100. Получив нужный исход, колесо останавливается в нужном секторе.

Вот примеры рядов для конфигов выше (для наглядности, я их чуток почикал):

1й — честный (с равно распределенными вероятностями):

1.1.1.1.1.1.1.1.1.1.2.2.2.2.2.2.2.2.2.2.3.3.3.3.3.3.3.3.3.3.4.4.4.4.4.4.4.4.4.5.5.5.5.5.5.5.5.5.5.

2й — реальный (где балансер подтасовал исходы):

1.2.2.2.2.2.3.3.3.4.4.5.5.5.6.6.6.6.6.7.7.8.8.8.8.8.9.9.9.10.10.10.10.10.

Далее функция генерит число номера в ряде, забирает значение сектора в таблице, и — профит. Баланс готов, в теории всё хорошо — каждое число (от 1 до 100) на большой выборке (на 100 млн.) должно выпадать одинаковое количество раз. Но на практике дела обстоят намного иначе.

Проблема святого рандома

На каждой отдельной машине (процессоре), на которой генерится рандомное число одной из функций рандома, например mt_rand, есть погрешность. И в диапазоне от 1 до 100 есть участок, в котором числа выпадают реже, чем должны, а есть участок, где чаще, чем должны. Это зависит исключительно от процессора, на котором выполняется операция рандомизации. Один и тот же проц, для одной функции будет иметь всегда одну и ту же погрешность.

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

do

Вот представьте, что на «70» — у вас стоит исход «Джекпот». В итоге на святом рандоме у вас Джекпоту стоит меньшая вероятность, а он выпадает чаще, чем другие исходы — и это чуток ломает баланс. Ну если не ломает, то как минимум, портит статистику, и вообще ведет себя не так, как ожидает разработчик.

Решение: Делаем рандом более рандомным

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

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

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

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

Способ 1: Шаффл ряда значений

1.2.3.4.5.5.4.3.2.1.1.2.3.4.5.5.4.3.2.1.1.2.3.4.5.5.4.3.2.1.1.2.3.4.5.5.4.3.2.1.1.2.3.4.5.5.4.3.2.1

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

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

Способ 2: Шаффл на лету

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

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


Стоит ли заморачиваться по этому поводу?

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

  • Vitaliy Balanyuk

    Приставка mt в названии функции намекает на Mersenne Twister. Возможно, в реализации в php допустили ошибку

    На моих тестах с фартовым сидом погрешность более оптимистичная
    https://i.gyazo.com/8af4a0a28568a4ba4ac454ce03b55c2b.png

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

  • Maxim Tkach

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

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

    https://gist.github.com/gollariel/5be805e7cee44198ee5591480d9d68aa

    На 1 млрд итераций результаты приблизительно следующие:
    $indexes = [1 => 1, 2=>29, 3=>70];

    3 — 700026813 (70.0026813%)
    2 — 289975378 (28.9975378%)
    1 — 9997810 (0.999781%)

    Как по мне достаточно точные результаты