扑克游戏的商业级随机化

Question

我需要一些关于如何解决算法问题的建议(即不是编程本身).以下是我的需求以及我如何尝试满足它们.任何改进意见都会受到欢迎.

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

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

我想保留我写的简单的东西.为此,该计划只需要一个输入来实现既定目标.我已经决定,无论何时程序开始,它都会记录当前时间并将其作为起点.我意识到这种方法对于商业环境来说是不可行的,但只要能够支持几十亿游戏,比简单的替代方案更好,我会很高兴.

我开始编写伪代码来解决这个问题,但遇到了一个棘手的问题.这对我来说很清楚,但它可能不适合你,所以请让我知道.

Psuedo代码如下:

    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分成四个偶数部分(代表套装).但是我们无法保证每个部分会找到十三张卡片,这样会很糟糕.

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

- 编辑 -

从/ dev/random读取字节实际上很有效.但这仍然让我失去了如何进行转换？(假设我为52张卡读取了足够的字节数).

我真正的愿望是采取简单和可预测的东西,比如系统时间,并将其转换为随机的卡片组.用系统时间播种random()是一种很好的方法.因此散列时间并散列随机()的值.

地狱,如果我想,我可以从/ dev/random哈希字节,只是为了shizzles和咯咯笑.哈希提高了事物的随机性,不是吗？这不是为什么现代密码管理器存储已被数千次扫描的密码？

- 编辑2 -

所以我已经阅读了你的答案,我发现自己被许多人暗示的结论搞糊涂了.我在第一次编辑中暗示了这一点,但这真的让我陷入了困境.我只想指出并继续前进.

存在彩虹表,其中有时髦的数学和聪明的魔法,基本上充当映射到特定密码的常见哈希的查找表.我的理解是,更长,更好的密码不太可能出现在这些彩虹表中.但事实仍然表明,尽管许多用户密码有多么常见,但是经过数千次哈希后,哈希密码仍然是安全的.

因此,许多确定性操作增加了原始密码的随机性(或似乎？),我不是说我是对的,我只是说这是我的感觉.

我要指出的第二件事是我正在倒退.

我的意思是你们都建议我采用一个有序的,可预测的,非随意的牌组,并使用Fisher-Yates shuffle.我确信Fisher-Yates是一个很好的算法,但是假设你无论出于什么原因都不能使用它.

你可以采用一个随机的字节流,比如在416字节附近(52张卡,每张卡8个字节),BAM产生一张已经随机的卡片组吗？字节是随机的,所以这不应该太难.

大多数人会从一副52张牌(随机或非随机)开始,并将它们交换多次(通过选择随机索引进行交换).如果你能做到这一点,那么你可以随机抽取52个随机数,然后生成随机数.

正如我可以描述的那样, 该算法接受随机字节流并查看每个8字节的块.它将每个块映射到卡.

防爆.0x123映射到黑桃王牌Ex.0x456映射到钻石之王Ex.0x789映射到3个俱乐部....依此类推.

只要我们为映射选择了一个好的模型,这很好.不需要洗牌.该计划将减少到两个步骤.

步骤1:从良好的源获取足够数量的随机字节步骤2:将此字节流拆分为52个块,一个用于卡中的每个卡步骤2a:运行52个块,根据我们的转换为卡值地图.

这有道理吗？

Answer 1

你是在大量过度复杂的问题.您需要两个组件来解决您的问题:

1. 一种改组算法
2. 用于混洗算法的足够高质量的随机数发生器.

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

对于第二种情况,如果你想要足够的自由度来产生每种可能的排列(52种可能性),那么你需要至少226位的熵.无论您执行多少冗余哈希,使用系统时钟都不会为您提供超过32或64位的熵(实际上,大多数位是可预测的更少).找到一个使用256位种子并使用256个随机位播种的RNG(引导问题,但您可以使用/ dev/random或硬件RNG设备).

Answer 2

你没有提到你所使用的操作系统,但大多数现代操作系统都有预先制作的高质量熵源.在Linux上,这是/dev/random和/dev/urandom,从中你想要的,你可以读出许多随机字节.

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

Answer 3

如果你仍然使用伪随机生成器,无论你做了多少次确定性操作,你都永远不会提高你的随机性.事实上,你可能会让它变得更糟.

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

编辑:

你提到过你也想知道如何将它映射回一个随机算法.那部分实际上非常简单.一个直截了当的方式是Fisher-Yates洗牌. 基本上,您需要从RNG获得的是一个均匀分布在0到51之间的随机数.你可以在给定任何RNG的情况下进行计算,并且通常构建在一个好的库中.请参阅维基百科文章的"潜在偏见来源"部分.