扑克游戏的商业级随机化
我需要一些关于如何解决算法问题的建议（即本身不是编程）。以下是我的需求以及我如何努力满足这些需求。欢迎提出任何改进意见。
首先让我解释一下我的目标。我想玩大约十亿次扑克。也许我正在尝试创建下一个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 分成四个偶数部分（代表花色）。但不能保证每个部分都能找到十三张牌，这会很糟糕。
现在您知道我陷入困境了，您将如何克服这一挑战？
-- 已编辑 --
从 /dev/random 读取字节实际上效果很好。但这仍然让我不知道如何进行转换？ （假设我读取了 52 张卡的足够字节）。
我真正的愿望是采用一些简单且可预测的东西，例如系统时间，并将其转换为一副随机的纸牌。使用系统时间播种 random() 是一种糟糕的方法。因此，对时间进行哈希处理并对 random() 得出的值进行哈希处理。
天哪，如果我愿意的话，我可以对 /dev/random 中的字节进行哈希处理，只是为了发出嘶嘶声和咯咯笑声。散列提高了事物的随机性，不是吗？这难道不是现代密码管理器存储经过数千次哈希处理的密码的原因吗？
-- 编辑 2 --
因此，我已阅读了您的答案，但我发现自己对你们中许多人暗示的结论感到困惑。我在第一次编辑时就暗示过这一点，但这确实让我感到困惑。我只想指出这一点并继续前进。
彩虹表存在，它执行时髦的数学和巧妙的魔法，本质上充当映射到特定密码的常见哈希的查找表。据我了解，更长、更好的密码不太可能出现在这些彩虹表中。但事实仍然是，尽管有许多用户密码很常见，但经过哈希处理的密码在经过数千次哈希处理后仍然是安全的。
那么，在这种情况下，许多确定性操作增加了原始密码的随机性（或者似乎是这样？）我并不是说我是对的，我只是说这就是我的感觉。
我想指出的第二件事是我正在倒退。
我的意思是你们都建议我采取一套排序的、可预测的、非随机的牌并使用费舍尔-耶茨在上面拖着脚步。我确信 Fisher-Yates 是一个很好的算法，但假设您出于某种原因无法使用它。
您能否采用随机字节流，例如 416 字节附近（52 张卡，每张卡 8 字节），然后 BAM 生成一副已经随机的牌？字节是随机的，所以做到这一点应该不会太难。
大多数人会从一副 52 张牌（随机或非随机）开始，然后多次交换它们（通过选择随机索引进行交换）。如果你能做到这一点，那么你就可以随机抽取 52 个数字，运行一次，然后生成随机的牌组。
正如我所能描述的那样简单， 该算法接受随机字节流并查看每个 8 字节块。它将每个块映射到一张卡。
前任。 0x123 映射到黑桃 A 前任。 0x456 映射到钻石之王 前任。 0x789 映射到梅花 3 .... 等等。
只要我们选择一个好的映射模型就可以了。无需洗牌。该计划将减少为两个步骤。
第 1 步：从良好来源获取足够数量的随机字节 第 2 步：将此字节流拆分为 52 个块，每个块对应一副牌中的每张卡 步骤 2a：遍历 52 个块，根据我们的地图将它们转换为卡片值。
这有道理吗？
I need some advice on how to tackle an algorithmic problem (ie. not programming per se). What follows are my needs and how I tried to meet them. Any comments for improvement would be welcome.
Let me first start off by explaining my goal. I would like to play some poker about a billion times. Maybe I'm trying to create the next PokerStars.net, maybe I'm just crazy.
I would like to create a program that can produce better randomized decks of cards, than say the typical program calling random(). These need to be production quality decks created from high quality random numbers. I've heard that commercial-grade poker servers use 64-bit vectors for every card, thus ensuring randomness for all the millions of poker games played daily.
I'd like to keep whatever I write simple. To that end, the program should only need one input to achieve the stated goal. I have decided that whenever the program begins, it will record the current time and use that as the starting point. I realize that this approach would not be feasible for commercial environments, but as long as it can hold up for a few billion games, better than simpler alternatives, I'll be happy.
I began to write pseudo-code to solve this problem, but ran into a thorny issue. It's clear to me, but it might not be to you, so please let me know.
Psuedo-code below:
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.
My issue is with the last step. I cannot think of a way to properly map each 64-bit value to a corresponding card, without having to worry about two numbers being the same (unlikely) or losing any randomness (likely).
My first idea was to break 0x0000000000000000 - 0xFFFFFFFFFFFFFFFF into four even sections (to represent the suits). But there is no guarantee that we will find exactly thirteen cards per section, which would be bad.
Now that you know where I am stuck, how would you overcome this challenge?
-- Edited --
Reading bytes from /dev/random would work well actually. But that still leaves me lost on how to do the conversion? (assuming I read enough bytes for 52 cards).
My real desire is to take something simple and predictable, like the system time, and transform it into a randomized deck of cards. Seeding random() with the system time is a BAD way of going about doing this. Hence the hashing of the time and hashing the values that come out of random().
Hell, if I wanted to, I could hash the bytes from /dev/random, just for shizzles and giggles. Hashing improves the randomness of things, doesn't it? Isn't that why modern password managers store passwords that have been hashed thousands of times?
-- Edit 2 --
So I've read your answers and I find myself confused by the conclusion many of you are implying. I hinted at it in my first edit, but it's really throwing me for a loop. I'd just like to point it out and move on.
Rainbow tables exist which do funky math and clever magic to essentially act as a lookup table for common hashes that map to a particular password. It is my understanding that longer, better passwords are unlikely to show up in these rainbow tables. But the fact still stands that despite how common many user passwords are, the hashed passwords remain safe after being hashed thousands of times.
So is that a case where many deterministic operations have increased the randomness of the original password (or seems to?) I'm not saying I'm right, I'm just saying thats my feeling.
The second thing I want to point out is I'm doing this backwards.
What I mean is that you all are suggesting I take a sorted, predictable, non-random deck of cards and use the Fisher-Yates shuffle on it. I'm sure Fisher-Yates is a fine algorithm, but lets say you couldn't use it for whatever reason.
Could you take a random stream of bytes, say in the neighborhood of 416 bytes (52 cards with 8 bytes per card) and BAM produce an already random deck of cards? The bytes were random, so it shouldn't be too hard to do this.
Most people would start with a deck of 52 cards (random or not) and swap them around a bunch of times (by picking a random index to swap). If you can do that, then you can take 52 random numbers, run through them once, and produce the randomized deck.
As simply as I can describe it,
The algorithm to accepts a stream of randomized bytes and looks at each 8-byte chunk. It maps each chunk to a card.
Ex. 0x123 maps to the Ace of Spades
Ex. 0x456 maps to the King of Diamonds
Ex. 0x789 maps to the 3 of Clubs
.... and so on.
As long as we chose a good model for the mapping, this is fine. No shuffling required. The program will be reduced to two steps.
Step 1: Obtain a sufficient quantity of random bytes from a good source
Step 2: Split this stream of bytes into 52 chunks, one for each card in the deck
Step 2a: Run through the 52 chunks, converting them into card values according to our map.
Does that makes sense?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
你把问题过于复杂化了。您需要两个组件来解决您的问题：
第一个很简单，只需使用 Fisher-Yates shuffle 算法即可。
对于第二个，如果您想要 足够的自由度能够生成每种可能的排列（52！种可能性），那么你至少需要 226 位的熵。使用系统时钟不会给你超过 32 或 64 位的熵（实际上要少得多，因为大多数位都是可预测的），无论你执行多少个冗余哈希。找到一个使用 256 位种子的 RNG，并使用 256 个随机位对其进行种子（这是一个引导问题，但您可以使用 /dev/random 或硬件 RNG 设备来实现此目的）。
You are massively overcomplicating the problem. You need two components to solve your problem:
The first is easy, just use the Fisher-Yates shuffle algorithm.
For the second, if you want sufficient degrees of freedom to be able to generate every possible permutation (of the 52! possibilities) then you need at least 226 bits of entropy. Using the system clock won't give you more than 32 or 64 bits of entropy (in practice far fewer as most of the bits are predictable), regardless of how many redundant hashes you perform. Find an RNG that uses a 256-bit seed and seed it with 256 random bits (a bootstrapping problem, but you can use /dev/random or a hardware RNG device for this).
您没有提及您所在的操作系统，但大多数现代操作系统都有预制的高质量熵源。在 Linux 上，它是
/dev/random和/dev/urandom，您可以从中读取任意数量的随机字节。如果您想要良好的随机性，那么编写自己的随机数生成器非常重要。任何自制解决方案都可能存在缺陷，并且可能会被破坏并预测其输出。
You don't mention which OS you're on, but most modern OS's have pre-made sources of high quality entropy. On Linux, it's
/dev/randomand/dev/urandom, from which you can read as many random bytes as you want.Writing your own random number generator is highly non-trivial, if you want good randomness. Any homebrew solution is likely to be flawed and could potentially be broken and its outputs predicted.
如果您仍然使用伪随机生成器，无论您对其进行多少次确定性操作，您都永远不会提高随机性。事实上，你可能会让事情变得更糟。
我会使用商业随机数生成器。大多数使用硬件解决方案，例如盖革计数器。有些使用现有的用户输入作为熵源，例如计算机麦克风的背景噪音或键盘敲击之间的延迟。
编辑：
您提到您还想知道如何将其映射回洗牌算法。这部分实际上很简单。一种简单的方法是 Fisher-Yates shuffle。 基本上，您从 RNG 中需要的只是随机的数字均匀分布在 0 到 51 之间（含）。您可以在给定任何 RNG 的情况下进行计算，并且通常内置到一个好的库中。请参阅维基百科文章的“潜在偏见来源”部分。
You will never improve your randomness if you still use a pseudo-random generator, no matter how many deterministic manipulations you do to it. In fact, you are probably making it considerably worse.
I would use a commercial random number generator. Most use hardware solutions, like a Geiger counter. Some use existing user input as a source of entropy, such as background noise into the computer's microphone or latency between keyboard strokes.
Edit:
You mentioned that you also want to know how to map this back to a shuffle algorithm. That part is actually quite simple. One straightforward way is Fisher-Yates shuffle. Basically all you need from your RNG is a random number uniformly distributed between 0 and 51 inclusive. That you can do computationally given any RNG and is usually built into a good library. See the "Potential sources of bias" section of the Wikipedia article.
好问题！
我强烈建议您不要使用任何编程语言内置的
random函数。这会生成不加密安全的伪随机数，因此聪明的攻击者有可能查看以卡片形式返回的数字序列并对随机数种子进行逆向工程。由此，他们可以轻松地开始预测这副牌中会出现哪些牌。据我所知，一些早期的扑克网站存在此漏洞。对于您的应用程序，您将需要加密安全的随机数，以便对手无法在不破坏加密假定安全的情况下预测卡片的顺序。为此，您可以使用随机性硬件源或加密安全伪随机数生成器。硬件随机生成器可能很昂贵，因此加密安全的 PRNG 可能是一个不错的选择。
好消息是，获得加密安全的 PRNG 非常容易。如果您采用任何安全块密码（例如 AES 或 3DES）并使用随机密钥开始加密数字 0、1、2、...等，则生成的序列在加密上是安全的。也就是说，您可以使用 /dev/random 获取一些随机字节用作密钥，然后通过使用给定密钥的强密码按顺序加密整数来获取随机数。这是安全的，直到您交回大约 √n 个数字，其中 n 是密钥空间的大小。对于像 AES-256 这样的密码，在您需要重置随机密钥之前，这是 2128 个值。如果您“只想”玩数十亿场游戏 (240)，这应该就足够了。
希望这有帮助！祝项目顺利！
Great question!
I would strongly discourage you from using the
randomfunction that comes built-in with any programming language. This generates pseudorandom numbers that are not cryptographically secure, and so it would be possible for a clever attacker to look at the sequence of numbers coming back out as cards and to reverse-engineer the random number seed. From this, they could easily start predicting the cards that would come out of the deck. Some early poker sites, I've heard, had this vulnerability.For your application, you will need cryptographically secure random numbers so that an adversary could not predict the sequence of cards without breaking something cryptographically assumed to be secure. For this, you could either use a hardware source of randomness or a cryptographically secure pseudorandom number generator. Hardware random generators can be expensive, so a cryptographically secure PRNG may be a good option.
The good news is that it's very easy to get a cryptographically secure PRNG. If you take any secure block cipher (say, AES or 3DES) and using a random key start encrypting the numbers 0, 1, 2, ..., etc. then the resulting sequence is cryptographically secure. That is, you could use
/dev/randomto get some random bytes for use as a key, then get random numbers by encrypting the integers in sequence using a strong cipher with the given key. This is secure until you hand back roughly √n numbers, where n is the size of the key space. For a cipher like AES-256, this is 2128 values before you'd need to reset the random key. If you "only" want to play billions of games (240), this should be more than fine.Hope this helps! And best of luck with the project!
您绝对应该阅读这个问题的答案：理解“随机性”
现有的伪随机数不太可能改善您的结果，而且实际上存在渲染更少随机数的风险。
您可以考虑使用物理衍生的随机数而不是伪随机数：
http://en.wikipedia.org/wiki/Hardware_random_number_generator
如果您肯定要使用伪随机数，那么您可能最好使用操作系统的随机性设备进行播种，这可能包括来自磁盘寻道时间和用户 IO 等的额外熵。
You should definitely read the answer to this question: Understanding "randomness"
Your approach of applying a number of arbitrary transformations to an existing pseudorandom number is very unlikely to improve your results, and in fact risks rendering less random numbers.
You might consider using physically derived random numbers rather than pseudorandom numbers:
http://en.wikipedia.org/wiki/Hardware_random_number_generator
If you are definitely going to use pseudorandom numbers, then you are likely to be best off seeding with your operating system's randomness device, which is likely to include additional entropy from things like disk seek times as well as user IO.
转换什么？只需拿一副牌，然后使用加密安全的 PRNG，洗牌。这将以相同的概率产生每副可能的牌，任何人都无法确定接下来会出现什么牌 - 这是你能做的最好的事情。
只需确保正确实现洗牌算法 :)
Conversion of what? Just take a deck of cards and, using your cryptographically-secure PRNG, shuffle it. This will produce every possible deck of cards with equal probability, with no way for anyone to determine what cards are coming next - that's the best you could possibly do.
Just make sure you implement the shuffling algorithm correctly :)
就实际将随机数变成卡片而言（一旦您遵循其他人的建议生成随机数），您可以将最小的数字映射到钻石A，将第二小的数字映射到钻石2，等等。
基本上您假设实际的卡片具有自然顺序，然后对随机数字进行排序并映射到牌组。
编辑
显然维基百科将此方法列为Fisher-Yates 算法（我以前没有听说过 - 谢谢 Dan Dyer！）。维基百科文章中我没有想到的一件事是，如果您使用我描述的算法，则需要确保不会重复任何随机数。
In terms of actually turning the random numbers into cards(once you follow the advice of others in generating the random numbers), You can map the lowest number to the Ace of diamonds, the 2nd lowest number to the 2 of diamonds, etc.
Basically you assume the actual cards have a natural ordering and then you sort the random numbers and map to the deck.
Edit
Apparently wikipedia lists this method as an alternative to the Fisher-Yates algorithm(which I hadn't previously heard of -Thanks Dan Dyer!). One thing in the wikipedia article that I didn't think of is that you need to be sure that you don't repeat any random numbers if you're using the algorithm I described.
您可以在此处找到现成的现成扑克牌局评估器。欢迎通过其中的电子邮件地址提供所有反馈。
A ready-made, off the shelf poker hand evaluator can be found here. All feedback welcomed at the e-mail address found therein.