[aj_reading]

Hi,

I'm planning on building a card game but i wanted to make sure i could make a shuffle thats as random as possible. So i made a little application to deal 52 cards and pick the first one, counting how many times that card is picked.

If i set it to shuffle 1,000,000 times, each card seems to get delt between 17,000 and 20,000 times.

My question is, how many times would you guys say i would need to shuffle to get a fair result and how much of a deviation would be considered "not random enough"

Heres an example of 1,000,000 shuffles

0,20006
1,17605
2,19737
3,19499
4,19731
5,18753
6,20898
7,20063
8,18848
9,18548
10,18929
11,19945
12,18146
13,19590
14,19013
15,19289
16,19968
17,17792
18,19136
19,18314
20,18597
21,20356
22,19965
23,19139
24,18521
25,19625
26,17916
27,19458
28,18224
29,18570
30,20225
31,19745
32,19947
33,18728
34,18496
35,18344
36,18244
37,18615
38,19687
39,19404
40,21702
41,19509
42,19756
43,19906
44,19852
45,18575
46,18486
47,19315
48,19353
49,19889
50,19217
51,18825

[aj_reading]

Just to clarify, i basically would like to know if my shuffling function is producing random enough results...

Thanks for your time guys

[AstroTux]

Hi,

Search the forums on PRNGs - Pseudo Random Number Generators. There are some good examples explaining how to check their normal distributions to prove they are indeed random (or as close as you can get in software, anyway).

Best regards,
AstroTux.

[Rockoon]

You will not see much of a problem with .NET's random number generator using a test like this because it is designed to do particularly well in this sort of test.

The weekness of "good" psuedo random number generators is not evident when looking at its individual outputs in isolation, but instead when considering multiple consecutive outputs.

A "good" generator has these properties:

card #1 is selected 1 out of 52 times
card #2 is selected 1 out of 52 times
.
.
card #52 is selected 1 out of 52 times

That is 52 properties, and are the ones you are essentialy testing.

..but a "good" random number generator also has these properties:

card #1 is selected immediately after card #2 1 out of 2652 times
card #1 is selected immediately after czrd #3 1 out of 2652 times
.
.
card #52 is selected immediatly after card #51 1 out of 2652 times

There are 2652 properties (52 * 51) in that group

The next group has 132600 (52 * 51 * 50) properties, and follows the form:

card (A) is selected immediately after the card pair (B) (C)

and the one after that has 6497400 (52 * 51 * 50 * 49) properties...

card (A) is selected immediately after the card tripplet (B) (C) (D)


No psuedo random number generator is ideal, and doing a "perfect" test on them is usualy far outside the scope of time constraints (you wont live long enough)

I recommend implimenting the Mersenne Twister algorithm

http://www.google.com/search?hl=en&s...er&btnG=Search

[AtmaWeapon]

You might want to look at this article for some pitfalls.

Also, before you can select the "best" algorithm, can you define what "more random" means? Ponder that one for a while. Anything that delivers the cards in a non-predictable fashion should be good, but keep in mind that the way the computer shuffles cards is not how physical cards are shuffled.

[Targe]

What's wrong with the basic random function for each card?

[AtmaWeapon]

Targe, did you read the article at all? There's plenty wrong with it. Treating card-shuffling as trivial can have severe economic consequences.

First, a deck has 52 cards. The most basic "shuffle" algorithm would simply select a card at random each time. The trouble is, this means in theory, "4H, 4H, 4H, 4H" (four of hearts 4 times in a row) is a valid draw. If you are playing a game that requires an infinite number of decks of cards, this is acceptable. However, most people like to play an n-deck game, and this is unacceptable for that type of game.

The easiest shuffling algorithm has a bias; the article proves this with a nice graph and a 3 card deck. With the most basic random shuffle algorithm there are 3 out of 9 scenarios that are favored significantly more than the others. Oops.

The Knuth-Fisher-Yates shuffle featured in the article and the Mersenne Twister mentioned by Rockoon are two "good" algorithms. The problem is computer scientists want the "most random" shuffle, and such a concept is ridiculous. What's the metric for randomness? How do you define if a deck is "random"? Doesn't saying, "This deck meets this pattern." imply that the deck's pattern is predictable and thus non-random?

Furthermore, dedicated card players don't like either algorithm. There are several methods for shuffling a deck of cards; the "ripple" shuffle and successive cuts are two. Neither of these is modeled by the algorithms above. A ripple shuffle involves dividing the deck into two approximately equal decks, then successively inserting semi-random numbers of cards into a new deck to form the shuffled deck. Successive cuts involve dividing the deck into several small decks then placing the decks in order to create the shuffled deck. Very talented card players can make certain assumptions about the state of a deck when it is shuffled via these methods, and I read comments associated with that article (and other similar ones) from people who have written card game software, and they claim they got complaints from consumers until their shuffle algorithms matched the "real" shuffling more closely.

So, unless the target is dedicated players, I'd suggest the implementation of Knuth-Fisher-Yates or the Mersenne twister; supposedly running them twice makes them "more random" if you believe in such a thing. It might be worth wrapping the System.Security.Cryptography.RNGCryptoServiceProvider class with an adapter that suits your needs, as the same people who laugh at "more random shuffles" seem to think that in this case "more random" is sane. I don't pretend to understand but many people I respect suggest this.

Anyway, if your customers are poker whizzes, you might want to toss out the generally accepted shuffles and simulate more real shuffles.

[Targe]

I thought it went without saying that you'd need to check if the card was already used or not.

My blackjack program uses 1-6 decks and has a boolean array which randomizes a card using the computer clock and if the card has been used it selects again (more to it, but that's the basics). I found it to work perfectly for my uses, and I don't see any problems with it.

If you think it's so predictable to get the system clock's randomize, just randomize X times with it. A seed value is more predictable in my opinion since it will output the same results every game.

[Rockoon]

Originally Posted by Targe

If you think it's so predictable to get the system clock's randomize, just randomize X times with it.

Why not just randomize with the last seed?

Overwritting the seed X times doesnt improve anything.

No offense, but I am guessing that you really arent well versed in the algorithms and techniques used in PNRG's.

While you may not have noticed any issues with your methodology, it isnt fit for public consumption. It would be a complete disaster for an online real money poker server (as some sites have had the misfortune of finding out)


Additionally, this isnt about things being 'predictable.' This is about the output of the card generator being as close as possible, statistically, to what you would expect if the source was truely random.

What should be expected from a truely random shuffle is well defined, and while that ideal can never be reached it is certainly worthwhile to come arbitrarily close to that ideal.

[aj_reading]

Thanks for the replies.

The game is going to be texas hold'em but its not aimed at the really big poker players, nor will much real money be exchanged so im thinking that the Knuth-Fisher-Yates shuffle will be sufficient.

[AtmaWeapon]

Originally Posted by Targe

I thought it went without saying that you'd need to check if the card was already used or not.

My blackjack program uses 1-6 decks and has a boolean array which randomizes a card using the computer clock and if the card has been used it selects again (more to it, but that's the basics). I found it to work perfectly for my uses, and I don't see any problems with it.

If you think it's so predictable to get the system clock's randomize, just randomize X times with it. A seed value is more predictable in my opinion since it will output the same results every game.

Targe, I linked to an article where someone documented and demonstrated how they were able to make an application that accurately chose the time-seed value that an online casino used to shuffle its cards. This application was able to display the entire deck accurately, with no inside knowledge.

For your purposes, it's probably not a big deal, but my issue is not that I think it's predictable when you use the system clock as a seed value, it's that I posted an article that showed an application that does it. It is much better, from a security standpoint, to use an unpredictable seed, or at least one that requires active cracking on the part of the attacker.

I really don't understand why you think the system clock tick value is unpredictable. The clock has a resolution of 10ms if I recall; that means for any given second there are only 100 possibilities for the random seed. Given the first few outputs of the RNG, it's trivial to write an application that can figure out the correct seed, then predict the remaining random values. Even if I'm not really sure when you seed the clock, if I know you do it at application startup there's maybe a 10 second window in which I have to fish; 1,000 possibilities is still trivial to analyze.

Part of the reason I'm so ill about it is I've linked to articles twice with lots of information, only to have your next response make some comment that is completely wrong in the face of the linked article. Read, man. Read.

[Targe]

I read it. I understood it. You're not understanding me.

Here's my problem. You can seed the value of the card and you can randomize that seed with another seed billions of times if you want to, but every time you run the game, the same cards will come into play. How is that random? That's my problem with all of this. If you want random each game, the only way is going to be with the system clock, otherwise you're going to see the same stuff. Yes, I know the system clock has flaws and can be predictable when set to the same ms, but that's why you random the random a random number of times.

You could argue any random function is going to be predictable based on what you're saying, but to see new cards each time the game starts up, you can't use a seed. For online poker places, the game only has to start once and stay on, so they can get away with it, but not a .NET application unless you're saving the last randomed values for the next use or something.

[Rockoon]

Originally Posted by Targe

If you want random each game, the only way is going to be with the system clock, otherwise you're going to see the same stuff.

Is that the only way?

No, no it isnt. Infact, you gave another way right at the end of your post.

Originally Posted by Targe

Yes, I know the system clock has flaws and can be predictable when set to the same ms, but that's why you random the random a random number of times.

If the first time it was predictable, why isnt the second? Where is your source of all this randomness?

"random the random a random number of times"

Ok so you start with what you admit is a flawed method, you use the timer as a seed. You then use the predictable random that comes out of it to repeatedly reseed the generator with a predictable value a predictable number of times. Think about it.

Originally Posted by Targe

For online poker places, the game only has to start once and stay on, so they can get away with it, but not a .NET application unless you're saving the last randomed values for the next use or something.

Online poker sites reboot often as the server is upgraded. I know from personal experience that this happens several times a month on every site that I have dealt with.

VB98's random number generator gives you the next in a sequence of 2^24 values, and .NET's random number generator gives you the next in a sequence of 2^32 values. The seed only defines where in the sequence you start.

It doesnt take many observations to figure out where in the sequence you are at, given that there are only 2^24 and 2^32 respective locations within the sequence where you can be, and this is further reduced if you use an even lower resolution source such as the systems tick count for your seed.

These arent big numbers in the game of PNRG's. The sequence length of the Mersenne Twister's has a length is 2^19937. For all intents and purposes, you can decide to never repeat any part of that sequence, ever. The problem still exists of seeding it correctly, but this is alleviated by the fact that you only need to do it once.

Seeding a PNRG is the most important thing you will ever do with it.

[AtmaWeapon]

Rockoon is quite a bit more educated in this field than I, but I do want to address an issue because it gave me an idea for a fun demo app tonight.

You mention that advocating against the use of the system time is futile, since having a different seed value is crucial to having different numbers every time. Half of that statement is correct: if you use the same seed you will get the same sequence. For the other half, you have to take your blinders off and think outside the normal realm. The system clock is a predictable number, but you can add an element of unpredictability to it, or you can use a truly random source of data.

What if we take the system time value and add some secret, variable value to it? Suddenly, the time-guess attack doesn't hold up as well. Some people like to use a bit of mouse movement or random keypresses to salt the system time value. I was going to recommend this approach, but in the face of Rockoon's post about the sequence of the numbers, this is just as vulnerable to a sequence-guessing attack as using the system time alone would be. Still, it solves the time-based attack.

There exists expensive equipment that derives random numbers from the decay of radioactive elements. As far as I know, this is considered a true random number generator, as there's no repeatability to it at all. I've heard rumors but never seen evidence that lava lamps can be used to derive random numbers; I don't think it's too ridiculous in principle but I've never seen it in action.

Rockoon, what's the story with RNGCryptoServiceProvider? Is it vulnerable to the sequence-guessing attack? It seems like it has to be a PRNG, but could it be that its sequence is in a range that discourages a sequence-based attack?

[Rockoon]

Originally Posted by AtmaWeapon

Rockoon, what's the story with RNGCryptoServiceProvider? Is it vulnerable to the sequence-guessing attack? It seems like it has to be a PRNG, but could it be that its sequence is in a range that discourages a sequence-based attack?

Well lets go over the main weakness of all encryption algorithms.

The more certain an attacker is about parts of the unencrypted messages, the easier it is for him to reverse the process given encrypted messages, thereby exposing the original key. Lets call this Observation Quality.

Attackers are usualy dealing with a logarithmic rate of progress. Reducing the search space in half takes N observations, but reducing it in half again only takes an additional N/2 observations, and so on. Cryptography works when N is large relative to the number of messages being sent with a given key.

You can keep N large by minimizing the Observation Quality and can foil the attacker by changing keys well before he can get enough observations (Observation Quantity).

In the various cryptographic contests, the Quantity is infact precisely 1, reducing the problem to basically brute force unless a fundamental weakness in the algorithm can be found.

Various wireless encryption strategies such as WEP are hopelessly flawed because there is always predictable information in wireless packets and the encryption algorithm itself doesnt do anything special to minimize its value (stream ciphering instead of block ciphering.) Observation Quality is high, making N very small relative to the number of observations an attacker can make. Last I heard, a person with a laptop sitting in a car outside your home can crack your wireless WEP encryption wide open in only a few minutes if your connection is active.


Moving on to the suggested use of PNRG's here, that of selecting things at random and presenting them to the user.

The original alphabet is known in advance.. its a deck of 52 cards. You also cannot hide the randomized message because you must by definition present at least some of the selected cards to the user.

LCG's such as VB98's have this nasty habit of literally exposing part of its state every single time you observe it, even when the observations are reduced to a single bit, such as Int(RND * 2). This bit is infact the most significant bit of its internal state.

In the case of VB98's generator, it only takes 24 (or maybe 25?) such single-bit observations before we can determine its state completely with 100% certainty. In practice it would take many more observations because you may not know the order with which symbols were selected, the default ordering of the alphabet, or how many pulls were made that you didnt observe. The fact that we can enumerate through all of VB98's LCG states in well under a second means that we can rapidly eliminate the full set of possibilities that do not jive with observation. Remember that this all happens in logarithmic time.

[Rockoon]

For the record, here is VB98's RND()

Seed = (Seed * 1140671485 + 12820163) Mod 16777216
RND = Seed / 16777216

It requires having overflow checking disabled, or using words larger than 32-bit, and it can be significantly optimized to use And instead of Mod.

Also found this page

[aj_reading]

Well the thread has moved off topic from my original post, yet it still made some interesting reading for me (even if some of it is a bit over my head).

I had a look around for a Knuth function in VB to shuffle an array but didnt manage to find one so i gave it a go myself. However ive proberbly got it wrong. How does this look?

    Private Sub ShuffleArray(ByVal strItems() As String)
        Dim intUbound As Integer = strItems.Length - 1
        Dim Rnd As New Random
        For i As Integer = 0 To intUbound - 1
            Dim j As Integer = Rnd.Next(i, intUbound + 1)
            Dim strTemp As String = strItems(i)
            strItems(i) = strItems(j)
            strItems(j) = strTemp
        Next i
    End Sub

[AtmaWeapon]

Completely incorrect, and more like the naive algorithm that is wrong.

The key to Knuth-Fisher-Yates seems to be that it works by placing a card in a position, then never fooling with that card again. It works "backwards" from the end of the array to the front, never reshuffling a card in a position that has been visited. Because of this, its possible results map one-to-one with the permutations of the values it is shuffling.

The incorrect algorithm can shuffle the same card several times, because even though you are iterating up the array, you choose from the entire array on each iteration. This means that it has more possible permutations than the permutations of the value it is shuffling, which means that some permutations will happen more than once.

Jeff Atwood posted a C-like pseudocode implementation of Knuth-Fisher-Yates:

for (int i = cards.Length - 1; i > 0; i--)
{
    int n = rand.Next(i + 1);
    Swap(ref cards[i], ref cards[n]);
}

When translating this into VB, keep 2 key points in mind:[list][*]The loop starts at the last element and moves to the first.[*]The random number will never be greater than the loop variable.[/code]This leads to a VB implementation like so:

For i As Integer = array.Length - 1 To 1
    Dim n as Integer = Random.Next(0, i + 1)
    Swap(array[i], array[n])
End For

I might be wrong about the To 1 part; I can't remember if the VB for loop iterates for the To value or if it stops when the counter reaches that value.

[Rockoon]

Atmas should be:

For i As Integer = array.Length - 1 To 0

..and you really dont want to be creating a new instance of Random every time this function is called.. I dont know the specific of its implimentation but if each instance has its own seed than this is a definate no-no. In a fully OOP methodology there should be a shuffler class with an instance that persists for the life of your program (perhaps, dare a say, a singleton), and has its own instance of Random.

[AtmaWeapon]

Thanks for the correction, I was too lazy to check. I kind of implied the Random issue in the algorithm but didn't make it clear. The documentation even explicitly states it but who reads it:

However, because the clock has finite resolution, creating different Random objects in close succession creates random number generators that produce identical sequences of random numbers. This problem can be avoided by creating a single Random object rather than multiple ones.

To improve performance, create one Random to generate many random numbers over time, instead of repeatedly creating a new Random to generate one random number.