C# Code Snippet Review

stitchs_login · 2015-01-14T22:27:59

Hi community, Working my way through a book, I've come to that classic "Create a deck of cards and Shuffle method" question. I research shuffling techniques online as I wanted to implement this on my own. I decided to use the 'Overhand Shuffle' technique (details found: http://en.wikipedia.org/wiki/Shuffling#Overhand_shuffle). The basic premise is that you cut the deck and at 2 points and move this middle section to the top, or bottom, of said deck, repeating until sufficiently shuffled. I have created a method that implements the same behavior: public void ShuffleDeck(Random pRng) { int deckCutPoint = 0; List<Card> firstCutDeck = new List<Card>(); List<Card> secondCutDeck = new List<Card>(); for (int i = 0; i < MAX_SHUFFLE; i++) { // RNG a point at which to cut the deck. deckCutPoint = pRng.Next(DECK_LIMIT); for (int j = 0; j <= deckCutPoint; j++) { firstCutDeck.Add(DrawCard()); } // RNG a point at which to cut the deck, based on the new deck count. deckCutPoint = pRng.Next(lDeck.Count); for (int k = 0; k < deckCutPoint; k++) { secondCutDeck.Add(DrawCard()); } lDeck = lDeck.Concat(secondCutDeck).Concat(firstCutDeck).ToList(); // Clear the cut decks so that they can be reloaded on the next shuffle. firstCutDeck.Clear(); secondCutDeck.Clear(); } } I have a list of Cards in my DeckOfCards class. This is the main deck. I create 2 more decks in my method, that I use to draw cards out of the deck, adding each card to the back of the list. I randomly cut into my deck the first time by using its size to generate the index position. I do the same for the second cut, using the updated size. To achieve the actual shuffle, I Concat the secondCut to the original deck, and then Concat the first cut to the back of the now modified main Deck. My question/desire for feedback is how efficient is this? I understand that each time I draw my original list is getting smaller, and new memory has to be allocated for the new temporary lists. FYI; MAX_SHUFFLE is set to 25, meaning it repeats this process 25 times. My thanks in advance, Stitchs.

For Beginners

Started by stitchs_login January 12, 2015 05:50 PM

13 comments, last by frob 9 years, 3 months ago

Bacterius

13,181

January 13, 2015 05:35 PM

I've always preferred a fairly simple and straightforward method of shuffling of deck.

For each location in the deck, randomly select another location in the deck and swap the two cards.

Exactly 52 iterations, exactly 52 swaps.

This is actually a very poor way to do it, as the distribution of decks shuffled by this method is quite biased (under the metric of "each possible shuffled deck should be produced with equal probability, or at least computationally indistinguishably so" but almost certainly also under the metric of "how a human would shuffle"). It's a very common mistake, the right algorithm restricts the selection of the other location at each iteration to ensure correctness and isn't actually any slower, see the Fisher-Yates pseudocode. Your algorithm looks correct (I mean, what could possibly go wrong) but it actually isn't...

EDIT: ninja'd by Frob while I was typing this!

“If I understand the standard right it is legal and safe to do this but the resulting value could be anything.”

stitchs_login

1,361

Author

January 13, 2015 10:12 PM

Wow. Thanks for all the response guys. You've given me a lot to think about.

I'm actually eager to finish this chapters exercises just so I can go back to the Deck example and implement these new ideas.

When I first saw the problem, one method I kept coming up with was swapping cards, but ignoring ALL cards previously swapped. Not just the card put into the visited portion. What is the 'bias' being quoted? Is this more to do with the computation of the randomness, or the same as the randomness created during a 'human' shuffle?

My thanks,

Stitchs.

frob

46,221

January 14, 2015 12:01 AM

What is the 'bias' being quoted? Is this more to do with the computation of the randomness, or the same as the randomness created during a 'human' shuffle?

It is statistical bias.

In a perfectly random shuffle of the cards, each card has a 1/n chance of being in any particular spot after a shuffle.

The Wikipedia article on card shuffling algorithms has this fun little image for the "permute with all" algorithm that was described earlier:

If there were no bias, shuffling seven cards should have a 1/7 chance (~14.3%) of being in any particular spot. In that image every slot would have the same uniform peach color. You could make a guessing game "Which slot is it in?" and no matter what slot you picked you would have the same odds of being right, and every different choice would tend toward 14.3% correct if you played that guessing game enough times.

But there is some bias in that routine, you are slightly more likely to have the one that started in slot 1 end up in slot 0 (17.9% chance according to the chart).

So if I were playing the same "guess which slot it is in" game, I would always guess that slot zero now contains what was in slot one, or that slot five now contains what was in slot six. This would be slightly more likely than the other options. It has a very slight bias.

Shuffling algorithms are very heavily studied thanks to real-money gambling. Players want to ensure that the game is fair... but if it is not fair, they want to ensure they have the advantage. Depending on their location on the globe, some regulated real-money gambling sites will post the exact algorithms they use and the sources of their random numbers. RNG's range from values generated from hashes of segments of images of multiple lava lamps, to radioactive isotope detectors, to radio receivers tuned to static.

jHaskell

1,856

January 14, 2015 08:56 PM

Let's keep in mind that your average 32 bit, or even 64 bit, PRNG algorithm is capable of producing less than a fraction of a percent of all the possible permutations of a 52 card deck.

Great discussion on biased vs unbiased shuffles, for sure, but let's keep in mind you've already thrown out over 99.99% of the possible permutations. If you're concerned about a biased algorithm, you better be a thousand times more concerned about using an adequate RNG.

frob

46,221

January 14, 2015 10:27 PM

Let's keep in mind that your average 32 bit, or even 64 bit, PRNG algorithm is capable of producing less than a fraction of a percent of all the possible permutations of a 52 card deck.

Great discussion on biased vs unbiased shuffles, for sure, but let's keep in mind you've already thrown out over 99.99% of the possible permutations. If you're concerned about a biased algorithm, you better be a thousand times more concerned about using an adequate RNG.

For card shuffling? No, not really.

Sure you eliminate a lot of possibilities if you use a number generator algorithm, but that's a different problem altogether. Just because you don't use all the possible values from a given seed does not mean to ignore bias.

Yes, if you know the number generator and you know the algorithm you can "predict" what the next version is going to be by doing it yourself, repeating the result. And yes, there are only a limited number of starting conditions for the number generator. Of course a 64-bit number space is very tiny compared to the 52! (factorial) number of permutations.

But that does not mean that you need to use a biased algorithm. The limited number of options can still generate an unbiased pseudorandom ordering of cards.

As a terrible example, many solitare games allow you to specify a seed for shuffling. That is not bias, it is the ability to repeat caused by pseudorandom number generation. If a third of the four billion possible shuffles ended up with the ace of spades as the last card, that IS bias, and it should be avoided.

C# Code Snippet Review

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

C# Code Snippet Review

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines