Даже когда вы тщательно выбираете инициирующее зерно для псевдослучайной последовательности, даже если вы закрываете глаза на баги и эксплойты игрока, всё равно случайность может пойти насмарку из-за плохо подобранных алгоритмов. Допустим, у вас есть колода карт и вам надо их перетасовать. Вот наивный алгоритм, который приходил в голову большинству начинающих программистов:
- Начать с нетасованной колоды.
- Сгенерировать псевдослучайное число, которое соответствует какой-либо карте в колоде (то есть, если колода из 52, нужно сгенерировать число от 1 до 52… или от 0 до 51, в зависимости от языка, который вы используете). Назовём это число А.
- Сгенерируйте второе псевдослучайное число, таким же образом. Назовём его числом Б.
- Поменяйте карты под номерами А и Б местами.
- Повторяйте шаги 2-4 много-много раз.
Проблема тут в том, что, во-первых, чтобы получить нечто, похожее на случайный порядок, у вас уйдёт неприлично много времени. Во-вторых, из-за того, что стартовые позиции карт фиксированы, и вы просто меняете местами случайные пары по одной за раз, неважно сколько раз вы это повторите – шанс получить тот же порядок, что и при старте, всегда будет выше. Представьте это так: если карта меняет своё место, она занимает случайную позицию, так что все позиции одинаково вероятны для каждой карты, если её вообще перемещали. Многократная перемена мест не меняет сути дела: карта перемещается с одного случайного места в другое, так что в конце концов, любая позиция карты равновероятна. То есть, каждая перемещённая карта с равной вероятностью может оказаться где угодно, с равной базовой частотой (и это хорошо). Однако есть некоторый ненулевой шанс, что карта не будет перемещена, и в этом случае она останется на своём изначальном месте, таким образом суммарный шанс того, что она останется там, где была, гораздо выше. Чем больше раз вы произвели замены, тем ниже шанс, что карта останется на своём месте, но сколько бы вы ни меняли карты местами, вы никогда не снизите эту вероятность до 0. Как это ни странно, но это значит, что самый вероятный расклад в этом алгоритме – это увидеть все карты на тех же местах, с которых они начинали!
Таким образом вы видите, что даже если псевдослучайные числа, сгенерированные для этого расклада совершенно случайные (или близки к этому), сам расклад всё равно не случаен.
Достаточно ли псевдослучайны ваши псевдослучайные числа?
Кроме того, существует вопрос, действительно ли сама функция вашего генератора псевдослучайных чисел производит достаточно случайные числа, или на самом деле есть числа, которые менее вероятны, чем другие, либо из-за погрешности в округлении, либо из-за плохого алгоритма. Проверить это можно самым простым способом: заставить ваш генератор произвести несколько тысяч пар случайных координат для двумерного графика и построить этот график, чтобы увидеть, не принимает ли он какой-либо заметной формы (вроде ячеистой структуры или с видимыми скоплениями результатов и пустым пространством между ними). Конечно, вероятно, что вы увидите некоторые скопления, потому что, как мы выяснили, это характерно для случайных чисел. Но если вы повторяете эксперимент несколько раз, эти скопления должны появляться в разных местах. Это один из способов использования симуляции Монте-Карло, чтобы быстро и наглядно проверить, действительно ли случайны ваши псевдослучайные числа. Существуют и более математические способы вычислить действительный уровень случайности вашего генератора, но тут требуется основательное знание математики. Этот же способ проще – дёшево и сердито, как раз годится для целей гейм-дизайна.
Как правило, вам всё это даже не потребуется. Большинство языков программирования и игровых библиотек имеют свои, встроенные функции генерации псевдослучайных чисел, дающие достаточно случайные числа, при этом они используют устоявшиеся, испытанные алгоритмы – именно такими, как правило, пользуется большинство программистов. Но если ваш программист по какой-то причине решил, что необходимо внедрение своей собственной функции для генерации случайных цифр, её вам следует протестировать очень внимательно!
Домашняя работа
На прошлых неделях я давал вам материал, который вы могли сразу же использовать для улучшения баланса своей игры, а также задание для дальнейшей практики. В этот раз я сделаю всё в обратном порядке. Давайте сперва попрактикуемся, а уже потом приложим изученное к вашему проекту, когда вы освоитесь с идеей.
Для «домашнего задания» этой недели я собираюсь рассмотреть два алгоритма тасования карт. Я видел оба алгоритма в некоторых вариациях в составе рабочих кодов изданных игр (не скажу каких, дабы защитить невиновных). В обоих случаях мы сталкивались с нескончаемым потоком жалоб от игроков, что механизм тасования неисправен, что есть некие «горячие точки» — места в колоде, куда можно поместить карту с наибольшей вероятностью, что она окажется наверху колоды и будет сдана вам на первом круге. Я хочу, чтобы вы пустили в ход своё логическое мышление, подумали над обоими алгоритмами и выяснили, эффективны ли они в действительности. Дам вам подсказку: один эффективен, другой нет. Собственно, я дам вам их исходный код, но и объясню их работу тем из вас, кто не умеет программировать. Обратите внимание: всё может выглядеть так, как будто это ошибка программирования, но на самом деле ошибка здесь в расчёте вероятностей: сколькими способами можно посчитать различные варианты тасования и как они распределяются по возможным положениям карт в колоде.
Алгоритм №1
Первый алгоритм выглядит следующим образом:
- Начните с нетасованной колоды.
- Выберите случайную карту из тех, что у вас есть (если колода из 60 карт, выберите псевдослучайное число от 1 до 60). Возьмите карту под этим номером и поменяйте местами с картой № 60. По сути, это значит взять любую карту из колоды и положить её на дно «тасуемой» колоды, закрепив там.
- Теперь возьмет случайную карту из оставшихся (от 1 до 59), и поменяйте местами с картой №59, положив поверх предыдущей.
- Затем возьмите ещё одну случайную карту из оставшихся (от 1 до 58), поменяйте её местами с картой №58, и так далее.
- Продолжайте, пока не дойдёте до карты №1, которая меняется местами сама с собой (то есть не делает ничего), и всё готово.
Этот способ очевидно отличается от всех нормальных способов, которыми люди тасуют карты, но помните, цель – не эмулировать тасование живым человеком, а получить случайный расклад, то есть, случайный порядок карт.
Алгоритм №2
Второй алгоритм похож на первый, но есть два небольших изменения.
- Начните с нетасованной колоды.
- Выберите случайную карту из тех, что у вас есть (если колода из 60 карт, выберите псевдослучайное число от 1 до 60). Возьмите карту под этим номером и поменяйте местами с картой №60, положив её на дно колоды.
- Выберите случайную карту из всех карт, включая те, что уже были выбраны (то есть, выберите ещё одну случайную карту от 1 до 60). Поменяйте местами с картой №59.
- Выберите ещё одну случайную карту от 1 до 60 и поменяйте местами с картой №58.
- Продолжайте повторять, пока в конце концов не выберете случайную карту от 1 до 60 для обмена с картой №1. Готово.
- Ах да, и вот ещё что. Повторите весь процесс (шаги 2-5) пятьдесят раз. Так мы сделаем расклад ещё случайнее.
Подсказки
Как взяться за это, когда в колоде из 60 карт так много различных раскладов, что и не пересчитаешь? Ответ в том, что можно сделать гораздо проще. Представьте колоду всего из трёх карт (все три карты разные, назовите их А, Б, В, если хотите).
Во-первых, вычислите сколькими способами можно расположить колоду из 3 карт. Для этого есть математические хитрости, о которых мы ещё не говорили, но вы должны дойти до этого методом проб и ошибок.
Далее, взгляните на оба алгоритма и вычислите, сколькими способами каждый из алгоритмов может сформировать расклад. То есть, в первом случае выбираете из трёх карт, потому из двух, потом из одной. Во втором случае выбираете из трёх, потом из трёх, потом снова из трёх. Сравните список всех действительно возможных вариантов расклада колоды, то есть уникальных способов расположения карт… и список всех способов, какими можно перетасовать колоду при помощи этих алгоритмов. Вы обнаружите, что один из них даёт случайный порядок (по крайней мере настолько, насколько вообще может быть случайным генератор псевдослучайных чисел), а другой «предпочитает» одни расклады другим. И если это работает для колоды из 3 карт, предположите, что такими же случайными (или неслучайными) будут и бо́льшие колоды. Если хотите проверить математикой большие колоды – на здоровье, но вам не обязательно этого делать.
Если вы сейчас работаете над игрой…
Видеоигры
Когда вы закончите разбираться с приведёнными выше алгоритмами, если вы работаете над игрой, связанной с компьютерами, взгляните на её псевдослучайные числа и на то, как программа их использует. В частности, если вы используете последовательности псевдослучайных чисел для того, чтобы изобразить нечто похожее на тасование колоды, проверьте действительно ли случайным получается результат; если вы используете нестандартный способ генерации псевдослучайных чисел, проверьте его построением графика из множества сгенерированных пар координат на наличие нежелательных закономерностей. И наконец, посмотрите, как инициирующее зерно хранится в состоянии игры; если это многопользовательская игра, хранится ли оно в различных клиентах или на единственном сервере? Если игра однопользовательская, работает ли ваша система сохранения так, что игрок может сохраниться, попытать счастья в ситуации с высоким риском, и продолжить свои попытки с сохранённого места до тех пор, пока ему не повезёт?
Все игры, цифровые и нецифровые
Ещё одна вещь, которую необходимо сделать независимо от того, настольную игру вы разрабатываете или видеоигру – это рассмотреть случайные механики в вашей игре (если есть такие) и задать себе некоторые вопросы:
— Доминирует в игре мастерство или удача? или они смешаны в равных пропорциях?
— Соответствует ли сочетание мастерства и удачи целевой аудитории игры, или игре стоит склониться немного в одну или в другую сторону?
— Какие погрешности восприятия вероятностей могут обнаружиться у ваших игроков в ходе игры? Можете ли вы устроить свою игру иначе, чтобы изменить мнение ваших игроков о том, насколько справедлива игра? Стоит ли это делать?