4

我需要一些关于如何解决算法问题的建议（即本身不是编程）。以下是我的需求以及我如何努力满足它们。欢迎任何改进意见。

让我首先解释我的目标。我想玩一些扑克大约十亿次。也许我正在尝试创建下一个 PokerStars.net，也许我只是疯了。

我想创建一个程序，它可以生成更好的随机牌组，而不是调用 random() 的典型程序。这些需要是由高质量随机数创建的生产质量套牌。我听说商业级扑克服务器对每张牌使用 64 位向量，从而确保每天玩的所有数百万扑克游戏的随机性。

我想保持我写的简单。为此，该程序应该只需要一个输入来实现既定目标。我已经决定，每当程序开始时，它都会记录当前时间并将其用作起点。我意识到这种方法在商业环境中是不可行的，但只要它能够支持数十亿游戏，比更简单的替代方案更好，我会很高兴。

我开始编写伪代码来解决这个问题，但遇到了一个棘手的问题。这对我来说很清楚，但对你来说可能不是，所以请告诉我。

伪代码如下：

    Start by noting the system time.
    Hash the current time (with MD5) around ten times (I chose the ten arbitrarily).
    Take the resulting hash, and use it as the seed to the language-dependent random() function.
    Call random() 52 times and store the results.
    Take the values produced by random() and hash them.
    Any hash function that produces at least 64-bits of output will do for this.
    Truncate (if the hash is too big) so the hashes will fit inside a 64-bit double.
    Find a way to map the 52 doubles (which should be random now, according to my calculations) into 52 different cards, so we can play some poker.

我的问题是最后一步。我想不出一种将每个 64 位值正确映射到相应卡的方法，而不必担心两个数字相同（不太可能）或丢失任何随机性（可能）。

我的第一个想法是将 0x0000000000000000 - 0xFFFFFFFFFFFFFFFF 分成四个偶数部分（代表花色）。但是不能保证我们会在每个部分找到正好 13 张卡片，这会很糟糕。

既然您知道我被困在哪里，您将如何克服这一挑战？

-- 已编辑 --

从 /dev/random 读取字节实际上会很好。但这仍然让我迷失了如何进行转换？（假设我为 52 张卡读取了足够的字节）。

我真正的愿望是采用简单且可预测的东西，例如系统时间，并将其转换为随机的一副牌。使用系统时间播种 random() 是一种不好的方法。因此，时间的散列和随机（）出来的值的散列。

见鬼，如果我愿意，我可以散列来自 /dev/random 的字节，只是为了发出嘘声和咯咯笑声。散列提高了事物的随机性，不是吗？这不是现代密码管理器存储经过数千次哈希处理的密码的原因吗？

-- 编辑 2 --

所以我已经阅读了你们的答案，我发现自己对你们中许多人暗示的结论感到困惑。我在第一次编辑中暗示了它，但它真的让我陷入了循环。我只想指出并继续前进。

彩虹表的存在可以进行时髦的数学运算和巧妙的魔法，本质上充当映射到特定密码的常见哈希的查找表。据我了解，更长、更好的密码不太可能出现在这些彩虹表中。但事实仍然是，尽管有多少用户密码很常见，但经过哈希处理的密码经过数千次哈希处理后仍然安全。

那么，在这种情况下，许多确定性操作增加了原始密码的随机性（或似乎？）我不是说我是对的，我只是说这就是我的感觉。

我想指出的第二件事是我正在倒退。

我的意思是，你们都在建议我使用一副有序的、可预测的、非随机的纸牌，并在上面使用 Fisher-Yates 洗牌。我确信 Fisher-Yates 是一个很好的算法，但可以说你不能出于任何原因使用它。

您能否获取一个随机的字节流，例如大约 416 个字节（52 张卡片，每张卡片 8 个字节），然后 BAM 会生成一个已经随机的卡片组？字节是随机的，所以这样做应该不会太难。

大多数人会从一副 52 张牌（随机或非随机）开始，然后将它们交换很多次（通过选择一个随机索引进行交换）。如果你能做到这一点，那么你可以取 52 个随机数，遍历它们一次，然后生成随机牌组。

正如我所描述的那样， 该算法接受随机字节流并查看每个 8 字节块。它将每个块映射到一张卡片。

前任。0x123 映射到黑桃 A。0x456 映射到钻石之王 Ex。0x789 映射到 Clubs 的 3 .... 等等。

只要我们为映射选择了一个好的模型，就可以了。无需改组。该程序将减少到两个步骤。

第 1 步：从一个好的源中获取足够数量的随机字节 第 2 步：将此字节流拆分为 52 个块，每张卡片一个块 第 2a 步：遍历这 52 个块，根据我们的方法将它们转换为卡片值地图。

这有意义吗？

4

8 回答 8

15

您将问题严重过度复杂化。您需要两个组件来解决您的问题：

  1. 洗牌算法
  2. 一个足够高质量的随机数生成器供混洗算法使用。

第一个很简单，只需使用Fisher-Yates shuffle算法。

其次，如果您想要足够的自由度来生成每个可能的排列（在 52 种可能性中），那么您至少需要 226 位熵。无论您执行多少冗余哈希，使用系统时钟不会给您超过 32 或 64 位的熵（实际上要少得多，因为大多数位是可预测的）。找到一个使用 256 位种子的 RNG，并使用 256 个随机位对其进行种子处理（这是一个引导问题，但您可以为此使用 /dev/random 或硬件 RNG 设备）。

于 2011-03-17T21:05:48.833 回答
6

您没有提及您使用的是哪个操作系统，但大多数现代操作系统都有预制的高质量熵源。在 Linux 上，它是/dev/randomand /dev/urandom，您可以从中读取任意数量的随机字节。

如果您想要良好的随机性，编写自己的随机数生成器非常重要。任何自制解决方案都可能存在缺陷，并且可能会被破坏，并且可以预测其输出。

于 2011-03-17T21:00:00.120 回答
5

如果您仍然使用伪随机生成器，无论您对其进行多少确定性操作，您将永远不会提高随机性。事实上，你可能会让情况变得更糟。

我会使用商业随机数生成器。大多数使用硬件解决方案，例如盖革计数器。有些使用现有的用户输入作为熵的来源，例如计算机麦克风的背景噪音或键盘敲击之间的延迟。

编辑：

您提到您还想知道如何将其映射回 shuffle 算法。那部分其实很简单。一种直接的方法是Fisher-Yates 洗牌。 基本上，您从 RNG 中需要的只是一个均匀分布在 0 到 51 之间的随机数。您可以在给定任何 RNG 的情况下进行计算，并且通常内置在一个好的库中。请参阅维基百科文章的“潜在偏见来源”部分。

于 2011-03-17T20:59:16.357 回答
2

好问题！

我强烈建议您不要使用random任何编程语言内置的函数。这会生成在密码学上不安全的伪随机数，因此聪明的攻击者可能会查看以卡片形式返回的数字序列并对随机数种子进行逆向工程。由此，他们可以很容易地开始预测会从牌堆中出来的牌。我听说一些早期的扑克网站有这个漏洞。

对于您的应用程序，您将需要加密安全的随机数，以便对手无法在不破坏加密假设安全的情况下预测卡片序列。为此，您可以使用硬件随机源或加密安全的伪随机数生成器。硬件随机生成器可能很昂贵，因此加密安全的 PRNG 可能是一个不错的选择。

好消息是很容易获得加密安全的 PRNG。如果您采用任何安全分组密码（例如 AES 或 3DES）并使用随机密钥开始加密数字 0、1、2、...等，则生成的序列在密码学上是安全的。也就是说，您可以使用/dev/random获取一些随机字节以用作密钥，然后通过使用具有给定密钥的强密码按顺序加密整数来获取随机数。这是安全的，直到您交回大约 √n 个数字，其中 n 是密钥空间的大小。对于像 AES-256 这样的密码，在您需要重置随机密钥之前，这是 2 128个值。如果您“只”想玩数十亿个游戏（2 40），这应该很好。

希望这可以帮助！祝你项目好运！

于 2011-03-17T21:04:15.260 回答
1

你绝对应该阅读这个问题的答案：理解“随机性”

您对现有伪随机数应用大量任意转换的方法不太可能改善您的结果，实际上可能会导致随机数减少。

您可以考虑使用物理派生的随机数而不是伪随机数： http ://en.wikipedia.org/wiki/Hardware_random_number_generator

如果您肯定要使用伪随机数，那么您可能最好使用操作系统的随机设备进行播种，这可能包括磁盘寻道时间和用户 IO 等额外的熵。

于 2011-03-17T21:03:30.373 回答
0

就实际将随机数变成卡片而言（一旦您按照其他人的建议生成随机数），您可以将最小的数字映射到方块的 A，将第二小的数字映射到方块的 2，等等。

基本上，您假设实际卡片具有自然顺序，然后您对随机数进行排序并映射到牌组。

编辑

显然，维基百科将此方法列为Fisher-Yates 算法的替代方法（我以前没有听说过 - 谢谢 Dan Dyer！）。维基百科文章中我没有想到的一件事是，如果您使用我描述的算法，您需要确保不会重复任何随机数。

于 2011-03-17T21:10:07.560 回答
0

从 /dev/random 读取字节实际上会很好。但这仍然让我迷失了如何进行转换？（假设我为 52 张卡读取了足够的字节）。

转换什么？只需拿一副纸牌，然后使用您的加密安全 PRNG，将其洗牌。这将以相同的概率产生所有可能的牌组，任何人都无法确定接下来会出现什么牌 - 这是你能做的最好的事情。

只要确保你正确实施洗牌算法:)

于 2011-03-17T21:16:57.257 回答
0

可以在此处找到现成的现成扑克手评估器。欢迎在其中找到的电子邮件地址提供所有反馈。

于 2011-06-02T00:03:14.183 回答