用window.crypto.getRandomValues在JavaScript中洗牌

浏览 63关注 0回答 3得票数 19
原文

一副扑克牌有52张牌,因此52!或大体上是2^226可能的排列。

现在我想完美地洗一副这样的牌,具有真正随机的结果和均匀的分布,这样你就可以达到这些可能的排列中的每一个,并且每个排列都有可能出现。

为什么这实际上是必要的?

也许,对于游戏来说,你并不真的需要完美的随机性,除非有钱可以赢。除此之外,人类可能甚至不会察觉到随机性中的“差异”。

但是如果我没有记错的话,如果您使用混洗函数和通常内置于流行编程语言中的RNG组件,您通常会得到不超过32位的熵和2^32状态。因此,在洗牌时,你永远不能到达所有可能的52!排列,而只能...

0.000000000000000000000000000000000000000000000000000000005324900157 %

..。可能的排列。这意味着在理论上可以玩或模拟的所有可能的游戏实际上永远看不到。

顺便说一句,如果你不是每次在洗牌前都重置为默认顺序,而是从最后一次洗牌的顺序开始,或者在玩完游戏后保持“混乱”,那么你可以进一步改善结果。

要求:

因此,据我所知,为了完成上面描述的工作,需要以下三个组件:

一种良好的混洗算法,可确保至少226位内部状态的统一distribution.

  • A正确的
  1. 。由于我们是在确定性机器上,PRNG将是我们将得到的全部,也许这应该是CSPRNG。
  2. 至少具有226位熵的随机种子。

解决方案:

现在这是可以实现的吗?我们有什么?

  1. Fisher-Yates shuffle将会很好,据我所知,
  2. xorshift7 RNG的内部状态超过了所需的226位,并且如果
  3. 我们可以生成所需的226位的熵来用作我们的种子。如果这还不够,我们可以添加更多的熵from other sources.

问题:

上面提到的解决方案(以及需求)是否正确?那么,在实践中,如何在JavaScript中使用这些解决方案实现混洗呢?如何将这三个组件组合成一个有效的解决方案?

我想我必须用一个对xorshift7的调用来替换Fisher-Yates shuffle示例中Math.random的用法。但是该RNG输出一个[0, 1)浮点数范围内的值,而我需要[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,我也不知道如何修改它来接受这一点。

原文
msanford修改于2017-11-14 05:18

3 个回答

caw
回答于2017-11-13 04:38
得票数 1

将这里的this answeranother questionthis answer结合起来,似乎可以成为一个更通用、更模块化(尽管不太优化)的版本:

// Fisher-Yates
function shuffle(array) {
    var i, j;

    for (i = array.length - 1; i > 0; i--) {
        j = randomInt(0, i + 1);
        swap(array, i, j);
    }
}

// replacement for:
//     Math.floor(Math.random() * (max - min)) + min
function randomInt(min, max) {
    var range = max - min;
    var bytesNeeded = Math.ceil(Math.log2(range) / 8);
    var randomBytes = new Uint8Array(bytesNeeded);
    var maximumRange = Math.pow(Math.pow(2, 8), bytesNeeded);
    var extendedRange = Math.floor(maximumRange / range) * range;
    var i, randomInteger;

    while (true) {
        window.crypto.getRandomValues(randomBytes);
        randomInteger = 0;

        for (i = 0; i < bytesNeeded; i++) {
            randomInteger <<= 8;
            randomInteger += randomBytes[i];
        }

        if (randomInteger < extendedRange) {
            randomInteger %= range;

            return min + randomInteger;
        }
    }
}

function swap(array, first, second) {
    var temp;

    temp = array[first];
    array[first] = array[second];
    array[second] = temp;
}
页面原文内容由caw、msanford、r3mainer、Community、dandavis、Dylan Brams提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:https://stackoverflow.com/questions/47194034复制

扫码关注腾讯云开发者

领取腾讯云代金券