Покерная колода имеет 52 карты и, следовательно, 52! или примерно 2^226 возможные перестановки.
Теперь я хочу перетасовать такую колоду карт отлично, с действительно случайными результатами и равномерным распределением, чтобы вы могли достичь каждой из этих возможных перестановок, и каждая из них будет в равной степени появляться.
Почему это действительно необходимо?
Для игр, возможно, вам не нужна идеальная случайность, если нет денег, которые нужно выиграть. Кроме того, люди, вероятно, даже не будут воспринимать "различия" в случайности.
Но если я не ошибаюсь, если вы используете функции перетасовки и компоненты RNG, обычно встроенные в популярные языки программирования, вы часто получаете не более 32 бит состояний энтропии и 2^32. Таким образом, вы никогда не сможете достичь всех 52! возможных перестановок колоды при перетасовке, но только о...
0.0000000000000000000000000000000000000000000000000000000000005324900157%
... возможных подстановок. Это означает, что многие из возможных игр, которые могут быть воспроизведены или смоделированы в теории, на практике никогда не будут на практике.
Кстати, вы можете еще больше улучшить результаты, если вы не reset в порядке по умолчанию каждый раз перед перетасовкой, а вместо этого начинаете с порядка с последнего перетасовки или сохраняете "беспорядок" после того, как игра была играл и перетасовывал оттуда.
Требования:
Итак, чтобы сделать то, что описано выше, нужно, насколько я понял, все три следующих компонента:
- Хороший алгоритм перетасовки, обеспечивающий равномерное распределение.
- Собственный RNG с не менее чем 226 битами внутреннего состояния. Поскольку мы находимся на детерминированных машинах, PRNG будет всем, что мы получим, и, возможно, это должно быть CSPRNG.
- Случайное семя с не менее чем 226 бит энтропии.
Решения:
Теперь это достижимо? Что у нас есть?
- Перетасовка Fisher-Yates будет, насколько я понимаю, прекрасной.
- xorshift7 RNG имеет более чем 226 бит внутреннего состояния и должен быть достаточным.
- Используя
window.crypto.getRandomValues, мы можем генерировать требуемые 226 бит энтропии, которые будут использоваться в качестве нашего семени. Если этого еще недостаточно, мы можем добавить еще несколько энтропий из других источников.
Вопрос:
Правильны ли упомянутые выше решения (а также требования)? Как вы можете реализовать перетасовку с использованием этих решений в JavaScript на практике? Как объединить три компонента с рабочим решением?
Я думаю, мне нужно заменить использование Math.random в примере Shuffle Fisher-Yates вызовом xorshift7. Но этот RNG выводит значение в диапазоне [0, 1) float, и вместо этого мне нужен целочисленный диапазон [1, n]. При масштабировании этого диапазона я не хочу потерять равномерное распределение. Более того, я хотел около 226 бит случайности. Если мой RNG выводит только один Number, разве эта случайность не уменьшается до 2 ^ 53 (или 2 ^ 64) битов, потому что больше нет возможностей для вывода?
Чтобы генерировать семя для RNG, я хотел сделать что-то вроде этого:
var randomBytes = generateRandomBytes(226);
function generateRandomBytes(n) {
var data = new Uint8Array(
Math.ceil(n / 8)
);
window.crypto.getRandomValues(data);
return data;
}
Это правильно? Я не вижу, как я мог бы передать randomBytes в RNG как семя в любом случае, и я не знаю, как я мог бы изменить его, чтобы это сделать.
