21. Псевдослучайные числа

В этой главе

• Аналоговая случайность.

• Псевдослучайность.

Аналоговая случайность

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

Первый закон ненадежности Джилба

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

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

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

Сходные проблемы возникают и при использовании других разновидностей кубиков. Если вам приходилось играть в настольные ролевые игры, то вы, возможно, сталкивались с ситуацией, когда кубик d20 оказывался «счастливым» для кого-то из игроков (может быть, для вас лично), чаще обычного выдавая в качестве результата число 20. Надо сказать, что такое поведение кубика может объясняться вполне естественными причинами. В силу применяемой технологии производства большинство кубиков d20 имеют не идеально круглую, а слегка вытянутую форму. Из-за этого числа, расположенные на более округлых частях кубика, выпадают реже, а расположенные на приплюснутых его частях — чаще. Кроме того, не следует исключать и вероятности того, что игрок будет умышленно применять кубик со смещенным центром тяжести, натренируется выбрасывать нужное ему число или воспользуется иной разновидностью нечестной игры.

Ничуть не лучше в этом плане ведут себя и монеты. Хотя принято думать, что при бросании монеты могут с равной вероятностью выпасть и орел, и решка, на самом деле вероятность выпадения той стороны монеты, которая до броска была обращена вверх, обычно чуть выше. (Вращение монеты еще больше осложняет ситуацию, поскольку у большинства из них одна сторона чуть тяжелее другой, что существенно повышает вероятность выпадения более легкой стороны.) Не обеспечивает случайного распределения и тасование колоды карт. Например, такой распространенный способ тасования, как рифленая тасовка, вряд ли можно назвать хорошим способом рандомизации. При этом колода сначала разделяется на две равные части, которые затем с перемешиванием соединяются. При этом верхняя и нижняя карты исходной колоды становятся верхней и нижней картами отдельных половин колоды. После их соединения верхняя карта одной половины оказывается в самом верху или рядом с верхом итоговой колоды, а нижняя карта другой половины — в самом низу итоговой колоды или рядом с ним. Таким образом, чтобы как следует перемешать карты, их приходится тасовать довольно долго. А некоторые способы тасования спустя некоторое количество повторений могут вернуть колоду в исходное состояние. Эта уловка часто используется при демонстрации карточных фокусов: делая вид, что тасует колоду, фокусник просто несколько раз перекладывает одни и те же ее части. Однако даже при «честном» тасовании без многократного перекладывания одних и тех ее же частей колоды возможные результаты процесса не будут равновероятными, а некоторые виды результатов просто физически невозможно получить после однократного тасования. Например, в силу особенностей рифленой тасовки относительное положение каждой карты в двух промежуточных колодах остается неизменным, и вы не можете обратить порядок карт в колоде, однократно перетасовав ее.

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

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

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

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

Псевдослучайность

Компьютеры работают абсолютно детерминированным образом. Если вы посмотрите, что находится внутри системного блока, то не увидите там ни шестигранных кубиков, ни карт, ни каких-либо иных случайных элементов. Если вы не готовы задействовать специальное оборудование для измерения степени проявленности хаотических физических явлений (например, скорости частиц при радиоактивном распаде), что выходит далеко за рамки обычного использования компьютера, то вам неминуемо придется столкнуться с проблемой применения детерминированной машины для игры в недетерминированные азартные игры, основанные на случайности. До сих пор генерируемые компьютером числа мы называли случайными, но правильнее называть их псевдослучайными, поскольку они не являются действительно случайными. Для предоставления псевдослучайных чисел по запросу компьютер использует генератор псевдослучайных чисел (который, однако, сокращенно обозначается RNG (random number generator — «генератор случайных чисел»), а не PNG (pseudorandom number generator — «генератор псевдослучайных чисел»), потому что тот, кто придумывал это сокращение, не слишком хорошо разбирался в технических тонкостях).

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

Каким же образом при этом выбирается начальное значение? Конечно, было бы лучше определять его случайным образом, но, как вы понимаете, это невозможно. Получив это так называемое зерно псевдослучайной последовательности (или просто зерно), компьютер начинает последовательно генерировать все остальные псевдослучайные числа. В силу этого генератор псевдослучайных чисел снабжается зерном только один раз — обычно при первом запуске игры. Однако важно понимать, что если в качестве зерна всегда будет использоваться одно и то же число, то вы постоянно будете получать одинаковые результаты. Помните о том, что это детерминированный механизм! Хотя эта особенность может оказаться полезной на этапе тестирования (поскольку вы сможете в точности воспроизводить результаты теста), такое поведение вряд ли окажется уместным в окончательной версии игры.

Хотя теме выбора подходящего зерна псевдослучайной последовательности можно посвятить отдельную книгу, обычно в качестве него выбирается значение, которое плохо поддается умышленному воспроизведению, например количество времени в миллисекундах, прошедшее с полуночи. Здесь, однако, следует проявлять осторожность: если, например, в качестве зерна псевдослучайной последовательности будет выбрано значение системных часов, содержащее лишь дробную часть в миллисекундах (с диапазоном от 0 до 999), то ваша игра фактически будет иметь лишь 1000 вариантов перетасовки. Этого достаточно, чтобы игровой процесс казался случайным стороннему наблюдателю, но слишком мало для того, чтобы игрок не сталкивался с одинаковыми вариантами развития событий в ходе продолжительной игры. В случае PvP-игры не исключена вероятность того, что кто-то из игроков настолько хорошо изучит ее, что сможет по первым нескольким псевдослучайным результатам определять, какое из 1000 зерен было использовано, затем на основе этой информации точно предсказывать все последующие результаты с целью получения несправедливого преимущества. Когда речь идет об игре, в которую ежедневно играют миллионы людей, даже время в миллисекундах, прошедшее с полуночи, может обеспечивать недостаточное количество вариантов. В целом это дает 86,4 млн вариантов зерна, и если игрок будет каждый день начинать играть примерно в одно и то же время, он вполне может дважды столкнуться с одним и тем же зерном. Крайне внимательно следует подходить и к использованию псевдослучайных чисел в онлайн-играх, особенно если они генерируются не на сервере, а на машинах игроков. Допустим, либо один из двух игроков, либо сервер генерирует начальное зерно, которое затем применяется обоими игроками. После этого всякий раз, когда кому-то из них требуется псевдослучайное число, оно должно генерироваться на машинах обоих игроков, чтобы оба генератора псевдослучайных чисел продолжали работать синхронно. Если из-за программной ошибки одна из двух машин сгенерирует псевдослучайное число, не сообщив об этом машине другого игрока, это приведет к рассогласованию генераторов псевдослучайных чисел игроков. После этого игра может продолжаться еще в течение нескольких ходов, пока один из игроков не решит выполнить действие, требующее виртуального бросания кубика. При этом на одной из двух машин будет получен успешный результат броска, а на другой — неудачный, поскольку там генератор выдаст другое псевдослучайное число. В определенный момент два клиента игры сравнят свои игровые состояния и обнаружат, что они различаются, и каждый из игроков подумает, что другая машина играет нечестно (упс!). В таком случае зачастую сложно определить источник проблемы, потому что она может проявиться лишь спустя несколько ходов после того, как некоторое псевдослучайное событие происходит для каждого игрока по-разному.

Сохранение и загрузка

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

Вот несколько распространенных методов реализации сохранения и загрузки.

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

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

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

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

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

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

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

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

Защищенное сохранение. Вы также можете использовать систему сохранения, в которой игроку можно сохраняться в любой момент и в любом месте, но файл сохранения удаляется после перезагрузки (что не позволяет многократно загружаться из одного и того же файла сохранения). Нечто подобное реализовано в игре The Nightmare of Druaga: если она замечает, что игрок производит сброс, с тем чтобы не потерять прогресс, на экран выводится длинная скучная лекция о недопустимости нечестной игры (в дополнение к наказанию в виде гибели персонажа). Конечно, если вам отключат электричество во время игры, вы потеряете прогресс, даже если будете играть честно, — вот вам и продвинутый метод!

Ограниченное количество сохранений. Вы можете позволить игрокам сохраняться в любом месте, ограничив при этом общее количество файлов сохранения (как, например, было сделано в первой версии игры Tomb Raider).

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

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

Вы не можете победить. Поиск идеальной системы сохранения относится к числу еще не решенных задач в игровом дизайне. Даже в полностью детерминированной игре выбрать метод сохранения и загрузки, который был бы удобным и приятным для игроков и в то же время исключал возможность нечестной игры, — весьма непростая задача. Добавление в игру псевдослучайных чисел еще больше усугубляет проблему. У игрока появляется возможность управлять прошлым (путем «перемотки» в нужных местах с помощью механизма сохранения и загрузки) или будущим (посредством проверки различных вариантов и повторного прохождения игры из точки сохранения уже с точным предвидением того, как будут развиваться события).

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

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

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

Псевдослучайные алгоритмы тасования

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

В качестве примера посмотрим, как обычно реализуется простое действие — тасование колоды карт. Многие начинающие программисты задействуют следу­ющий простейший алгоритм: начав с неперетасованной колоды, вы генерируете два псевдослучайных числа для выбора в колоде двух карт (если в ней 52 карты, нужно сгенерировать два числа в диапазоне от 1 до 52 или от 0 до 51 в зависимости от используемого языка программирования). Эти две карты меняются местами. Затем операция случайного обмена повторяется несколько тысяч раз.

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

Более удачный алгоритм тасования выглядит следующим образом: начав с неперетасованной колоды, вы случайным образом выбираете в ней одну карту и меняете ее местами с картой, расположенной в первой (или последней) позиции. Затем случайным образом выбираете одну из оставшихся карт (то есть любую, кроме той, которая была выбрана в первый раз) и меняете ее местами с картой, расположенной во второй (или предпоследней) позиции. После этого продолжаете выбирать одну из еще не выбранных карт и размещать ее в следующей по счету позиции. На языке C++ этот код может выглядеть так, как показано далее (версии на других языках будут иметь небольшие отличия):

for (int i=DECK_SIZE-1; i>0; i--)

{

    int r = rand() %(i+1);

    tmp = Deck[i];

    Deck[i] = Deck[r];

    Deck[r] = tmp;

}

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

Однако в силу технических ограничений даже этот алгоритм неидеален.

На момент написания этой книги большинство используемых компьютеров — 64-разрядные. Это означает, что длина отдельной инструкции процессора составляет 64 бита, равно как и длина самого большого целого числа, то есть у нас может быть 264, или чуть больше чем 18 квинтильонов, или 1,8 × 1019, различных целых чисел, а значит, столько же различных зерен псевдослучайной последовательности. На первый взгляд, это чрезвычайно много. Но сколько может быть различных вариантов перетасовки колоды из 52 карт? Первая карта может занять одну из 52 возможных позиций, следующая карта — одну из 51 позиции, следующая — одну из 50 позиций и так далее до последней карты, которая может занять только одну позицию, оставшуюся свободной после того, как будут заняты все остальные.

Определить общий размер пространства возможностей можно, перемножив эти числа друг на друга: 52 × 51 × 50 … 3 × 2 × 1. В математике результат умножения целого числа на все другие целые числа, которые меньше него, называется факториалом (обозначается с помощью восклицательного знака). Таким образом, общее количество вариантов перетасовки стандартной колоды составляет 52!, что в результате дает около 8 × 1067. Это намного больше, чем размер пространства возможностей, доступного нам при выборе зерна случайной последовательности. То есть даже самые современные компьютеры не позволяют получить подавляющее большинство теоретически возможных вариантов перетасовки колоды из 52 карт. Чтобы получить все возможные варианты ее перетасовки, нужно использовать 256-разрядный компьютер, и даже этого будет не вполне достаточно для колоды из 60 карт, как показывает сетевая реализация игры Magic: the Gathering.

Кроме того, даже в доступном пространстве возможностей предполагается идеальная ситуация с равной вероятностью выбора каждого из 264 зерен псевдослучайной последовательности. Если бы зерно выбиралось путем определения количества миллисекунд, прошедших с полуночи, размер пространства возможностей сократился бы до количества миллисекунд, содержащихся в одних сутках, что составляет около 86 млн. Это чрезвычайно малое количество возможностей, если мы примем во внимание реальное пространство возможностей колоды из 52 карт или вычислительные возможности современных компьютеров. Используемый вами компьютер, вероятно, сможет выполнять поиск уникальной последовательности, соответствующей одному из 86 млн возможных вариантов, в режиме реального времени и всего за несколько секунд. Если игроку удастся установить, каким образом выбираются зерна и какой именно алгоритм задействуется для генерации псевдослучайных чисел (например, он может установить, что применяется функция rand() из стандартной библиотеки C++), то ему потребуется не так уж много псевдо­случайных результатов для того, чтобы точно определить, в каком месте последовательности он находится. Это позволит ему точно предсказывать последующие результаты и использовать это для нечестной игры.

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

Вопросы для обсуждения

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

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

3. Хотя на первый взгляд кажется, что барабаны слот-машины вращаются случайным образом и останавливаются на совершенно случайно выбранном символе, на самом деле они специально программируются таким образом, чтобы «почти выигрышные» комбинации (например, с отклонением одного из трех одинаковых символов лишь на одну позицию) выпадали чаще, чем это возможно при случайном выборе, потому что такие результаты вызывают у игрока радостное возбуждение и практически всегда убеждают его сделать еще несколько попыток, поскольку, как ему кажется, он был очень близок к успеху. Если бы вам поручили разработку ИИ для слот-машины, какие еще элементы вы добавили бы в программный код, чтобы игрок как можно дольше не терял интереса и не прекращал игру?

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

5. Какие виды видеоигр требуют повышенной осторожности при использовании псевдослучайных чисел?

6. Какие преимущества и недостатки несет задействование в игре случайных чисел, генерируемых на основе действительно случайного физического явления (вместо псевдослучайных чисел, генерируемых компьютером)?

7. Рассмотрите физическую настольную игру, в которой используются какие-либо случайные элементы, например кубики или карты (если у вас нет физического экземпляра этой игры, найдите в Интернете фотографии применяемых в ней компонентов). Каких видов отклонений от абсолютно случайного поведения можно ожидать от этих «случайных» компонентов игры?

8. Если в игре из предыдущего вопроса «случайные» компоненты действительно будут вести себя не совсем случайным образом, как этим сможет воспользоваться игрок для получения преимущества над противниками?

9. Некоторые игры, например Slay the Spire и Minecraft, предоставляют игроку информацию об используемом зерне псевдослучайной последовательности и позволяют ввести в качестве него собственное значение. Чем такая функцио­нальность может быть полезна для игроков?

10. Чем описанная в предыдущем вопросе функциональность может быть полезна для разработчиков игры, особенно на этапе контроля качества?

Побочные квесты

Различие между случайным и псевдослучайным имеет далекоидущие последствия для разработчиков видеоигр (и даже для разработчиков настольных игр, поскольку у многих популярных настольных и карточных игр со временем появляется компьютерная версия, кроме того, разработчики настольных игр могут использовать компьютерные симуляции в качестве вспомогательного средства при настройке игрового баланса). Хотя псевдослучайные числа могут быть прекрасным инструментом и при разработке видеоигр, как правило, оказываются единственным доступным вариантом, у них есть естественные ограничения в отношении обеспечиваемой степени случайности… И это еще не считая того, что вы можете реализовать их с ошибками или сделать это не совсем удачно, в результате чего тасование карт или бросание кубиков будет выполняться с еще меньшей степенью случайности. Мы должны смириться с тем, что в сфере разработки игр совершенно случайное число представляет собой недостижимый в реальности идеальный случай. В реальности мы должны удовлетвориться довольно высокой степенью случайности, которая может варьироваться в зависимости от того, идет ли речь об обычной игре в неформальной обстановке, киберспортивном турнире с высокими ставками или строго регулируемой индустрии азартных игр.

Побочный квест 21.1. Проверка генератора случайных чисел

В своем редакторе электронных таблиц выполните следующую быструю проверку: введите формулу =СЛЧИС() (=RAND()) в ячейке A1 и продублируйте ее вниз 1000 раз с помощью функции автозаполнения. Не снимая выделения с этой 1000 ячеек, продублируйте их вправо, получив таким образом два столбца по 1000 независимых псевдослучайных чисел.

Теперь представьте эти данные графически в виде точечной диаграммы рассеяния, как если бы они представляли собой 1000 пар координат (x, y).

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

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

Побочный квест 21.2. Еще один алгоритм тасования карт

Вот как может выглядеть слегка модифицированная версия рассмотренного в этой главе алгоритма тасования. Как и раньше, вы начинаете с неперетасованной колоды. Затем случайным образом выбираете одну карту и меняете ее местами с первой или последней картой в колоде. Затем случайным образом выбираете еще одну карту (из всех карт, включая ту, которая была только что выбрана) и меняете ее местами со второй или предпоследней картой в колоде. Так продолжаете до тех пор, пока не поменяете на случайно выбранную карту все остальные карты колоды. Соответствующий код на C++ может выглядеть следующим образом:

for (int i=DECK_SIZE-1; i>0; i--)

{

    int r = rand() %DECK_SIZE;

    tmp = Deck[i];

    Deck[i] = Deck[r];

    Deck[r] = tmp;

}

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

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

Побочный квест 21.3. Тасование большой колоды

В этой главе мы выяснили: чтобы как следует перетасовать колоду из 52 карт, потребуется компьютер, имеющий как минимум 256 разрядов (строго говоря, хватило бы и компьютера, имеющего 226 разрядов, но, как мы знаем, у любого компьютера количество разрядов должно быть равным степени числа 2). Компьютер с каким количеством разрядов потребуется для тасования колоды из 60 карт, используемой в игре Magic: the Gathering? А для тасования колоды из 100 карт?

Побочный квест 21.4. Взлом своего собственного генератора случайных чисел

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

Сначала напишите программу, которая будет подбрасывать монету 200 раз. (Для этого нужно выбрать подходящее зерно псевдослучайной последовательности, сгенерировать псевдослучайное число в диапазоне от 0 до 1 с помощью такой функции, как rand(), и округлить результат до ближайшего целого числа так, чтобы все, что меньше 0,5, стало равным 0, а все, что больше или равно 0,5, стало равным 1. При получении 0 можно считать, что выпал орел, а при получении 1 — что выпала решка.) Также можно в редакторе электронных таблиц записать в ячейке формулу =ЕСЛИ(СЛЧИС()<0,5; "Орел"; "Решка") и продублировать ее в 200 строках с помощью функции автозаполнения.

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

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

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

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

Побочный квест 21.5. Использование уязвимостей системы сохранения

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

Сначала опишите, как она функционирует.

• При каких условиях игрок может сохранить игру (или при каких условиях не может)?

• Сохраняется ли зерно псевдослучайной последовательности, судя по внешним признакам? (То есть если после перезагрузки игры выполнять несколько действий, связанных с генерированием псевдослучайных чисел, будет ли при этом всегда происходить одно и то же?)

• Легко ли продублировать файл сохранения, чтобы снова загрузиться в той же позиции, если первая попытка продвижения вперед с этого места окажется неудачной?

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

---