Шла десятая неделя после выхода нового рейда... Вот уже 9 раз ты со своей гильдией убивал нужного тебе босса, с которого падает эпический лук, но так ни разу и не видел его дропа. Зато другой статик, в котором нет хантов, дизает этот лук уже третий раз подряд. Но ты не расстраиваешься, ведь совсем недавно тебе повезло - со своего 198-го забега ты наконец выбил лошадь с барона. И вот, твой друг, который недавно решил попробовать поиграть, просит тебя  пропаравозить его разок в Стратхольм. Ок, погнали, за несколько минут ты проносишь знакомый до мелочей инст, убиваешь босса, друг получает ачивку, появляется окошкo лута, а в нём... лошадь. Ты видишь её второй раз. Из своих двухсот забегов. Твой друг, забирая коня, видит его впервые, как и самого барона. Знакомо? О китайском рандоме и его закономерностях порассуждаем на этот раз.


Dancing with swords, rivers of blood and games of probabilities

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




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

Допустим, мы убиваем мобов, с которых с шансом 1% падает эпический меч. Соответственно, когда мы убиваем первого моба, имеем шанс дропа 1 к 100. Но вот, мы убили уже 90 мобов, а меч всё не падает. Каков шанс, что он наконец выпадет с 91-го раза? Точно такой же, 1 к 100, и ничуть не выше. Объясняется это двольно просто. О том факте, что убито уже 90 мобов, знает сам игрок, который их отчаянно гриндит, но об этом ни капли не догадывается моб. Он не знает, что он уже 91-й.  Для каждого моба работает один и тот же алгоритм, который может выдать меч с шансом 1%. И этому алгоритму абсолютно пофиг, сколько мобов было убито ранее - один, сто, тысяча или ещё больше. Точно так же, монетке не важно, сколько раз её подбрасывали ранее - орёл или решка выпадут с одинаковым шансом в 50%.



Но не стоит считать, что количество попыток не приближает нас к желаемому. Довод о том, что со 100 попыток мы имеем больше шансов выбить наш эпический меч, чем с одной, не лишён логики и вполне справедлив. Вот только как быстро растут наши шансы? Понятно, что при однопроцентном дропе 100 попыток не гарантируют положительного результата, но и очевидно, что вероятность этого результата больше, чем с первого раза. Возникает вопрос: а насколько больше?

Рассмотрим пример, в котором дроп несколько выше - 10%, но это число я беру только для наглядности, на суть оно не влияет. Итак, мы в начале нашего пути. Когда мы убьём первого моба, с шансом 10% нам упадёт наш меч и с шансом 90% он не упадёт. Если результат положительный - мы прекращаем нашу кровавую резню, если отрицательный - с удовольствием продолжаем.



На втором мобе мы имеем всё те же шансы, но с поправкой на то, что мы лишь с вероятностью в 90% добрались до этой точки. Поэтому шанс выбить меч именно со второго моба равен 10% уже от этих 90%, а шанс пройти дальше по цепочке - 90% от этих же 90%. Это хорошо видно на рисунке. Если нас интересует, с какой вероятностью мы к этому моменту остановимся, то она равна сумме 10% после первого моба и 10% * 90% после второго моба, т.е. 0,1 + 0,9 * 0,1. Аналогично, для третьего моба шанс остановиться будет уже 0,1 + 0,9 * 0,1 + 0,9 * 0,9 * 0,1. И так далее.

Теперь то же самое, но в более общем виде. Пускай наш мега эпик падает с вероятностью p (в примере выше это 10%, т.е. p = 0,1). Вероятность отрицательного результата будет 1-p. Тогда, по аналогии с предыдущим примером, шанс выбить эпик именно со второго моба (т.е. при этом мы не выбьем его с первого) равен p * (1-p),  шанс не выбить ничего ни с первой ни со второй попытки будет (1-p)(1-p), а суммарный шанс получить желаемое с первой или второй попытки будет p + p * (1-p). И так далее, снова смотрим на картинку.



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



Вероятность выбить меч во время N-й попытки у нас получилась p * (1-p)^(N-1). А суммарная вероятность выбить его с этих N мобов равна



Чтобы понять, на кой хрен мы вывели эту формулу и что она нам даёт, нарисуем её график при p = 0,1 (т.е. при дропе 10%). С этого момента начинается интересное. Во-первых, хорошо видно, что зависимость не пропорциональная, т.е когда мы делаем, например, в 2 раза больше траев, шансы растут не вдвое, а медленнее. При 10%-ном дропе с 5 попыток мы имеем примерно 41% шанс на получение эпика, с 10 попыток  - примерно 65%.



Во-вторых, при большом числе попыток (в данном случае начиная с 35-40) для небольшого увеличения наших шансов нужно сделать уже намного больше траев, чем в самом начале. При дальнейшем увеличиении жопочасов вероятность асимптотически приближается к единице, т.е. к 100% при стремлении количества попыток в бесконечность. Логично, чёрт возьми :)

Возвращаясь к тому, с чего начинали, нарисуем график для 1%, т.е. для p = 0,01.



И тут мы видим, что всё намного печальнее, потому что даже на 100 попытках до 100% нам ещё очень далеко. Пусть задроты с удочками посмотрят на него и оценят свои шансы. Но что интересно, при 100 попытках имеем те же примерно 65%, что и с 10 попыток при 10%-ном дропе.

И ещё один момент, который надо прояснить, чтобы читатель не заглючил. Я говорил чуть выше, что не важно, убили мы 1 моба или 90, шансы будут одинаковыми. А судя по графикам, попытки кажутся неравноценными. Как так? Подвох в том, что когда мы уже убили 90 мобов и стоим перед 91-м, это свершившийся факт, это уже реализованный вариант, в котором нам не повезло. А вероятность свершившегося факта всегда 100%. Когда мы рисуем графики, мы стоим перед первым неубитым мобом и прикидываем, с каким шансом мы выбьем меч, если убьём N штук. Т.е. нам ещё может повезти на 1-м, 2-м, 10-м и так далее мобах. А когда мы уже убили сотню безрезультатно, мы снова стоим у начала графика, потому что факт уже свершился, и повезти где-то среди этой сотни нам уже не может. Пичаль, отсюда и разница.


You win or you wait

Теперь разберёмся с дропом в рейдах. В идеале, каждый эпик с каждого босса имеет фиксированный шанс дропа, независимо от того, кто пришёл этого боса убивать. Поэтому для всех рейдов эти шансы одинаковые, все находятся в равных условиях. Но на практике даже после 10 килов нужная вещь с хорошим шансом дропа может так и не упасть, а другой рейд уже не знает, куда им девать редкий предмет в таком количестве. Какого чёрта?



Начнём с того, что позовём Капитана Очевидность и поясним, как это всё работает. Например, в таблице лута у босса имеется 4 вещи: посох, щит, лук и шлем. Первые три падают с шансом 30%, а шлем редкий - всего 10%. Если падает всегда одна вещь, то в сумме обязательно должно быть 100%. Каждый раз, когда босс умирает, сервер генерирует случайное число. Для простоты объяснения будем считать, что оно в интервале от 1 до 100. Тогда, если число от 1 до 30 - падает посох, от 31 до 60 - падает щит, от 61 до 90 - падает лук, от 91 до 100 - шлем. Вроде бы, всё просто, прозрачно и честно.

Несправедливость возникает из-за того, что при малых размерах выборки, т.е. при небольшом количестве смертей босса, рандом не обязан выдавать запланированное распределение. Допустим, с босса падает 10 разных предметов, каждый с одинаковой вероятностью в 10%. Тогда для генерации лута достаточно использовать случайное целое число от 1 до 10, каждому такому числу будет соответствовать определённый предмет. Чтобы далеко не ходить, запустим тот самый рандом от Blizzard и посмотрим, что он нам даст:



Итак, мы убивали нашего "босса" раз в неделю в течение 10 недель. Вещи под номерами 1, 4, 5 и 6 не упали ни разу. В то же время, некоторые предметы упали дважды. Третий месяц не можете выбить нужный эпик? Он где-то среди этих 1, 4, 5, 6.

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

Чем больше количество смертей босса, тем более справедливым будет распределение. Для примера, сгенерируем 100 раз случайное число от 1 до 100. Я конечно не занимался таким извращением в игре, а сделал это в экселе, но суть не в том. Посмотрим на график.



Здесь уже видно, что такой ролл даёт более справедливые результаты, т.е. значения распределены более равномерно, а их среднее близко к 50. Убивая босса 100 раз, мы получили бы дроп каждой из падающих с него 10 вещей уже ближе к 10%, чем убив его 10 раз. Если мы сделаем это 1000 раз, то распределение будет ещё ближе к идеальному. Чтобы получить абсолютно точные 10%, нам нужно убивать босса бесконечно.

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

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


How to make it random

Все показанные примеры были привязаны к WoW. Но не сложно заметить, что тема, вообще говоря, более широкая, и всё то же самое вполне справедливо для других игр, да и не только для игр. При этом, мы всегда считали генератор случайных чисел идеальным, т.е. выдающим во время ролла абсолютно случайный результат. Так ли это на самом деле? И как вообще заставить машину взять число "с потолка"?



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

Первый способ кажется простым и естественным. Возьмём температуру процессора, количество занятых в данный момент мегабайт оперативки, миллисекунду времени смерти моба, фазу пятой луны Сатурна, всё это как-нибудь хитро перемножим и используем полученное число как случайное для генерации лута. В некоторых ситуациях такой подход годится, но не всегда. В чём проблема? В том, что когда результат непредсказуемый, он не обязательно случайный.

Чтобы это объяснить, я возьму всё тот же пример, когда с босса падают 10 вещей и у каждой должен быть 10%-ный дроп. Если мы используем непредсказуемые физические процессы, мы не сможем заранее узнать, упадёт нам с босса вещь под номером 3 или под номером 7, т.е. дроп непредсказуем. Но может получиться так, что даже при очень большой выборке, к примеру, семёрки выпадают чаще троек. И связано это будет с тем, что где-то в используемых нами процессах есть неслучайная составляющая, есть какая-то постоянная тенденция, которую мы не заметили и которую вообще очень сложно сразу заметить. В итоге, мы никогда не получим то распределение дропа, которое закладывали. Если делать всё как следует, такой метод генерации нам не подойдёт, но если мы бедные китайцы и хотим быстрее выпустить игру, то вполне сгодится, а на жалобы игроков в случае чего ответим, что это всё рандом, и мы тут не виноваты.



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

И ещё один подводный камень, на котором спотыкаются многие алгоритмы. Последовательности чисел не должны повторяться. Если у нас, например, есть тысяча случайных чисел от 1 до 10, где каждое число встречается примерно с равным шансом и разбросаны они все равномерно, то это не значит, что мы можем повторять эту же последовательность много раз. Для небольшой цепочки событий она сгодится, но когда миллионы игроков убьют сотни миллионов мобов, мы получим ситуации, когда всем прокнуло одновременно, черепаха стабильно вылавливается с каждой тысячи попыток и так далее. Понятно, что с таким рандомом играть станет не интересно.

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

Один из самых простых способов был придуман ещё в 1946 году и называется middle-square method. Человек один раз выбирает какое-нибудь шестизначное число (семя), закидывает его в алгоритм, а дальше на его основе генерируется сколько угодно случайных чисел.




Происходит это так:

- шестизначное число возводится в квадрат, получается 11-значное или 12-значное, в случае 11-значного к началу приписывается ноль
- из 12 знаков выбираются 6 посередине, а по 3 знака по краям отбрасываются нафиг
- полученное 6-значное число записывается как случайное, а потом юзается как семя для нового витка алгоритма

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



В современных научных исследованиях, естественно, применяются намного более мудрёные схемы, например алгоритм под названием Mersenne twister, который разработали в 1997 году няшные японские учёные. Он тоже не идеален, но последовательности начинают повторяться только через каждые 4,3 * 10^6000 чисел, а это намного больше количества атомов в видимой вселенной, поэтому... кхм, сойдёт. Но такие методы создают большую нагрузку на железо, так что скорее всего Blizzard юзает нечто попроще, хотя и поинтереснее описанного выше нубского варианта из 1946 года.

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


На этом, пожалуй, пришло время закончить. Надеюсь, не слишком загрузил математикой, схемами и графиками. Как говорила персонаж из одного аниме, 98% науки - скукотища. Но оставшиеся 2% иногда стоят того, чтобы разобраться в остальном. Мы никогда не сможем понять всё вокруг, но понимать хотя бы то, с чем постоянно  сталкиваешься - уже приятно. И чем больше мы узнаём о мире, тем он становится интереснее. Если я добавил к этому небольшой кусочек - уже отлично.


to be continued...