4

桥牌游戏使用 52 张不同的扑克牌,随机分配给四名玩家,每名玩家最终得到 13 张牌:所谓的“发牌”。大约 2^96 次过桥交易是可能的。在本文档中,生成随机交易的程序的要求如下所述:

  1. 该软件应该能够生成所有可能的过桥交易,因为手动交易也可以做到这一点。
  2. 软件应该以相同的概率生成每笔交易,不受板数、前手或任何其他情况的影响。
  3. 即使在会话中查看了所有其他交易之后,也应该无法预测交易。

该文档继续指出,伪随机生成器不能用于生成交易,因为看到伪随机序列的第一个元素将能够计算所使用的种子,从而使黑客能够预测接下来的交易。

此外,由于大多数伪随机生成器采用 32 位的种子,因此应该遵循这些生成器最多能够产生 2^32 个不同的桥接交易,而不是所需的 2^96 个,并且遵循所谓的生日悖论,在 2^32 笔交易的平方根之后,很可能会产生相同的交易。

描述桥接交易生成应用程序要求的文档的作者编写了一个程序,该程序在世界范围内用于生成随机交易,该程序使用人类在键盘上随机打字生成一个 96 位种子。十四年来,这种方法没有发现任何缺陷。

我想编写一个例程,无需使用人工输入来生成所需的种子。

进来了RNGCryptoServiceProvider。我使用下面的代码生成随机数,首先在 1 到 52 范围内,然后在 1 到 51 范围内,依此类推,直到剩下一张牌。

测试产生的交易我非常有信心这段代码能够以相同的概率产生能够产生的任何交易,并且任何一张牌最终与四名玩家之一的机会都等于 0.25。

但是由于我不知道 RNGCryptoServiceProvider 中使用的种子的强度,我想知道是否:

  1. 此代码将能够或可以适应产生 2^96 种不同的交易。
  2. 这段代码的下一笔交易是不可预测的。

编辑 这个问题中前面提到的获取随机数的方法是有缺陷的。这分散了主要问题的注意力,即这段代码是否能够产生 2^96 个不同的桥接交易。我用Stephen Taub 和 Shawn Farkas 在 MSDN 杂志上发表的随机数生成器替换了随机数生成器

用于生成范围为 1-52、1-51 等直到 1-2 的加密安全随机数的代码,取自本网站

     /// <summary>
/// Returns a random number within a specified range.
/// </summary>
/// <returns>
/// A 32-bit signed integer greater than or equal to <paramref name="minValue"/> and less than <paramref name="maxValue"/>; that is, the range of return values includes <paramref name="minValue"/> but not <paramref name="maxValue"/>. If <paramref name="minValue"/> equals <paramref name="maxValue"/>, <paramref name="minValue"/> is returned.
/// </returns>
/// <param name="minValue">The inclusive lower bound of the random number returned.</param>
/// <param name="maxValue">The exclusive upper bound of the random number returned. <paramref name="maxValue"/> must be greater than or equal to <paramref name="minValue"/>.</param>
/// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="minValue"/> is greater than <paramref name="maxValue"/>.</exception>
public override Int32 Next(Int32 minValue, Int32 maxValue)
{
    if (minValue > maxValue) throw new ArgumentOutOfRangeException("minValue");
    if (minValue == maxValue) return minValue;
    Int64 diff = maxValue - minValue;

    while (true)
    {
        //The cryptoProvider is of type RNGCryptoServiceProvider.
        cryptoProvider.GetBytes(uint32Buffer); //The uint32Buffer has a size of 4 bytes.
        UInt32 rand = BitConverter.ToUInt32(uint32Buffer, 0);

        Int64 max = (1 + (Int64)UInt32.MaxValue);
        Int64 remainder = max % diff;
        if (rand < max - remainder)
        {
            return (Int32)(minValue + (rand % diff));
        }
    }
}
4

1 回答 1

5

一旦你有一个“真正统一”的随机数生成器 (RNG),请执行以下操作:

  1. 使用基于外部源的种子初始化 RNG。这可能是键盘输入、程序启动时间或其他一些东西。根据我的研究,RNGCryptoServiceProvider 似乎已经完成了这部分工作。

  2. 最重要的是,每隔一段时间,从 RNG 中抽取一个数字。把数字扔掉吧,重要的是你已经“循环”了 RNG。如果需要,您可以使间隔随机化以增加不可预测性。更多的周期更好,所以我会选择一个尽可能低的最大间隔。

    • 随机间隔有两种选择,(a) 使用较弱的 RNG(他们确实使用),以及 (b) 忽略它。在老虎机中,用户的输入(按下“SPIN”)会导致实际的 RNG 抽奖。结合足够快的循环间隔,它被认为是不可预测的。

  3. (有些可选)不要连续画出所有数字。在绘制下一个数字(或一组数字)之前等待一段随机时间(允许 RNG 循环随机次数)。因为最初的绘制很可能是基于用户输入的,所以你应该能够一次绘制它们。不过也伤不起。

这是游戏(赌博)行业中使用的流程,其中不可预测的 RNG 受到严格监管(当然,也是必需的)。使用这种方法完成涉及 500 张牌(来自 100 个不同的牌组)的抽牌。请注意,使用的 RNG 通常采用 32 位种子,并且完全可以接受。

于 2014-09-06T00:37:50.557 回答