Randomized commercial poker game

Question

I need advice on solving an algorithmic problem (i.e. not programming as such). Following are my needs and how I tried to meet them. Any comments for improvement would be welcome.

Let me start by explaining my purpose first. I would like to play poker 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 create better randomized decks of cards than a typical program that calls random (). These should be quality production decks created from high quality random numbers. I heard that commercial-grade poker servers use 64-bit vectors for each card, thereby providing randomness to all the millions of poker games that are played every day.

I would like to keep everything I wrote simple. To achieve this goal, the program needs only one input . I decided that whenever a program starts, it records the current time and uses this as a starting point. I understand that this approach will not be feasible for the commercial environment, but so far it can delay several billion games, better than simple alternatives, I will be happy.

I started writing pseudo code to solve this problem, but ran into a thorny problem. This is clear to me, but it may not be for you, so please let me know.

The pseudoex 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 problem is with the last step. I can’t think of a way to correctly match each 64-bit value with the corresponding card, without worrying about the fact that the two numbers are the same (unlikely) or lose some randomness (probably).

My first idea was to break 0x0000000000000000 - 0xFFFFFFFFFFFFFFFF into four even sections (to represent the costumes). 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 problem?

- Edited -

Reading bytes from / dev / random will work efficiently. But it still leaves me with the loss of how to do the conversion? (assuming I read enough bytes for 52 cards).

My real desire is to take something simple and predictable, like system time, and turn it into a randomized deck of cards. Visiting random () with a system time is a BAD way to do this. Therefore, hashing time and hashing values ​​that come out of random ().

Hell, if I wanted to, I could have a byte hash from / dev / random, just for spikes and giggles. Hashing improves the randomness of things, doesn't it? Does this not mean that modern password administrators store passwords that have been hashed thousands of times?

- Change 2 -

So, I read your answers, and I'm confused by what many of you mean. I hinted at this in my first edit, but it really threw me into the loop. I just wanted to point this out and move on.

There are Rainbow tables that do funky math and smart magic, essentially serving as lookup tables for regular hashes that map to a specific password. As I understand it, longer, more strong passwords are unlikely to appear in these rainbow tables. But the fact is that despite the widespread use of many user passwords, hashed passwords remain secure after they are hashed thousands of times.

So, the case where many deterministic operations have increased the randomness of the original password (or, it seems ,?), I'm not saying that I'm right, I'm just saying that this is my feeling.

The second thing I want to point out is that I am doing it back.

I mean, you all suggest that I take a sorted, predictable, non-random deck of cards and use Shisher in Fisher-Yates. I'm sure Fisher-Yates is a great algorithm, but let's say you can't use it for any reason.

Could you take a random stream of bytes, say, in the region of 416 bytes (52 cards with 8 bytes per card), and BAM already gives an arbitrary deck of cards? The bytes were random, so it shouldn't be too hard to do this.

Most people will start with a deck of 52 cards (random or not) and swap them around a handful of times (by choosing a random index to exchange). If you can do this, you can take 52 random numbers, skip them once and create a randomized deck.

As simple as I can describe this, the Algorithm takes a stream of randomized bytes and looks at every 8-byte chunk. It displays each piece on a map.

Ex. 0x123 cards to Ace of Spades Ex. 0x456 Card King of Diamonds Ex. 0x789 cards for 3 clubs .... etc.

So far we have chosen a good model to display, this is great. No shuffling required. The program will be reduced to two steps.

Step 1: Get enough random bytes from a good source Step 2: Divide this stream of bytes into 52 pieces, one for each card in the deck Step 2a: Skip 52 pieces, converting them into card values ​​according to our card.

It makes sense?

Answer 1

You are breaking the problem badly. You need two components to solve your problem:

• Shuffling algorithm
• A reasonably high-quality random number generator to use the shuffle algorithm.

The first is easy, just use the Fisher-Yates shuffle algorithm.

For the second, if you want enough degrees of freedom to be able to generate every possible permutation (out of 52 possibilities!), Then you need at least 226 bits of entropy. Using the system clock will not give you more than 32 or 64 bits of entropy (in practice, much less, since most bits are predictable), regardless of how many redundant hashes you execute. Find an RNG that uses a 256-bit seed and runs it with 256 random bits (boot problem, but you can use / dev / random or an RNG hardware device for this).

Answer 2

You did not mention which OS you are in, but most modern OSs have pre-created sources of high-quality entropy. On Linux, these are /dev/random and /dev/urandom , from which you can read as many random bytes as you want.

Writing your own random number generator is very nontrivial if you want good randomness. Any homegrown decision is likely to be erroneous and could potentially be violated, and its results will be predicted.

Answer 3

You will never improve your randomness if you continue to use a pseudo-random generator, no matter how many deterministic manipulations you do to it. In fact, you are probably doing this much worse.

I would use a commercial random number generator. Most use hardware solutions, such as a Geiger counter. Some use existing user input as a source of entropy, such as background noise in a computer microphone or latency between keystrokes.

Edit:

You mentioned that you also want to know how to match this with the shuffling algorithm. This part is actually quite simple. One easy way to fisher-yates shuffle. Basically, all you need from your RNG is a random number evenly distributed between 0 and 51 inclusive. What you can do computationally with any RNG in mind and is usually built into a good library. See the “Potential Bias Sources” section of the Wikipedia article.

Answer 4

Great question!

I would categorically refuse to use the random function, which is built into any programming language. This generates pseudo-random numbers that are not cryptographically secure, and therefore a smart attacker could look at the sequence of numbers returned to the cards and reprogram the random number. From this, they could easily begin to predict cards that would come out of the deck. Some early poker sites, as I heard, had this vulnerability.

For your application, you will need cryptographically secure random numbers so that the adversary cannot predict the sequence of cards without breaking the cryptographically assumed safe. To do this, you can use a hardware random source or a cryptographically protected pseudo random number generator. Hardware random generators can be expensive, so cryptographically secure PRNGs can be a good option.

The good news is that it is very easy to get a cryptographically secure PRNG. If you take any secure block cipher (for example, AES or 3DES) and use a random key , start encrypting the numbers 0, 1, 2, ..., etc., Then the resulting sequence is cryptographically protected. That is, you can use /dev/random to get some random bytes to use as a key, and then get random numbers by encrypting the integers sequentially, using a strong cipher with this key. It's safe until you take it rude & radic; n numbers, where n is the size of the key space. For encryption such as AES-256, this value is 2 ¹²⁸ before you need to reset the random key. If you “only” want to play billions of games (2 ⁴⁰ ), this should be more than normal.

Hope this helps! And good luck with the project!

Answer 5

You should definitely read the answer to this question: Understanding "randomness"

Your approach of applying a series of arbitrary transformations to an existing pseudo-random number is unlikely to improve your results, but in fact, fewer random numbers will risk.

You can use random numbers obtained physically, rather than pseudo-random numbers: http://en.wikipedia.org/wiki/Hardware_random_number_generator

If you are definitely going to use pseudo-random numbers, then it is most likely best for you to plant your random device on your operating system, which is likely to include additional entropy from things like disk seek time as well as custom IO.

Answer 6

In terms of actually turning random numbers into cards (after you follow the advice of others when creating random numbers), you can match the lowest number with an ace of diamonds, the second smallest number up to 2 diamonds, etc.

Basically, you assume that the actual cards are in a natural order, and then sort random numbers and match with the deck.

Edit

Wikipedia appears to list this method as an alternative to the Fisher-Yates algorithm (which I had not heard of about -Thanks Dan Dyer!). One thing in the wikipedia article that I did not think about is that you need to be sure that you are not repeating random numbers if you use the algorithm used.

Answer 7

Reading bytes from / dev / random will work efficiently. But it still leaves me with the loss of how to do the conversion? (assuming I read enough bytes for 52 cards).

Converting what? Just grab a deck of cards and, using your cryptographically secure PRNG, shuffle it . This will produce every possible deck of cards with equal probability, and no one will be able to determine which cards follow next - which is the best you could do.

Just make sure the shuffling algorithm implements correctly :)

Answer 8

A finished, poker hand poker appraiser can be found here . All reviews are welcome at the email address found in it.