Doing The Card City Shuffle

How humans approximate a random deck versus a computer approximation and how it affects the game

This may seem like a non-question as most human shuffles of cards are trying to randomize the placement of cards in a deck. So, if we are making a computer representation of a deck of cards and we want to “shuffle” them, we usually just have the computer place them at random in the deck. Done, no more thought on that one. Well, I wanted to explore this a little. Is a human shuffled deck truly random? Does the human shuffled deck give a different playing experience to the computer shuffled deck?

Let’s break this down in what a human may do while “randomizing” a deck of cards. Most people would employ what is called a Riffle shuffle where you split the deck in two, then interleave the cards in each pile. It turns out that I’m not the first person to think about this problem (shocking, I know). Most notably a mathematician/statistician/magician named Persi Diaconis and mathematician David Bayer made a groundbreaking discovery that in 7 imperfect riffle shuffles a deck can be considered randomized (although, they revisited it and for games where suits don’t matter 4 shuffles are enough). What is meant be an imperfect shuffle is that it does not interleave each card of the pile with the next. Just try riffle shuffling a deck only once and then looking at the distribution of the cards (I recommend a canonically ordered deck, so by number in suit). You’ll see that you have pockets of cards that have interleaved in the same order they started in along with small pockets of perfect shuffling. I know what you’re thinking, wouldn’t a perfect shuffle be better? The answer is no actually, it turns out that perfect shuffling will return the deck to its original state in 2n shuffles (where the size of the full deck is 2n) and in n shuffles the order will be reversed. It’s really interesting stuff, I’ll list some articles at the bottom of the post.

I feel it’s important to note that the 7 imperfect shuffles is the number needed to randomize a standard deck of 52 playing cards. Bang! has 80 playing cards so in order to achieve an actual random on this deck we’d need to shuffle 9 times at least since two decks take this many shuffles for the same randomization as one deck shuffled 7 times. I’m guessing that 8 would likely be enough since 80 is half way between 52 and 104 but since it doesn’t seem like this scales perfectly and extra shuffles do not hurt the randomization it’s better to ensure we’ve achieved randomness.

Does this means when playing a game of Bang! we should shuffle the deck 9 times? Now, this is what I was first thinking about when I started addressing this problem. In a real game of Bang! (or any card game) it is highly unlikely that anyone is going to shuffle this many times unless they make a point of it. This is the problem I see in simulating a real game involving cards, as the real player experience is not with a truly randomized deck. So, should we make our shuffling imperfect as to give players what they are used to when they play or should we optimize it so they get the experience of a truly randomized deck. Most players don’t think about this until they get “déjà vu” while drawing cards in that it seems like cards that were played in a recent game are occurring in a similar order (commonly this happens in my games when we need to reshuffle the discard pile for more cards to draw). Nothing annoys players more than this, they feel like it somehow has cheapened the game so of course, I feel that we should idealize the game even though it will likely result in games being different from what the player is used to. Another good reason for doing so is that a good player can start to infer what cards should be next because the shuffling is creating less than random decks. They can even start to do this without realizing they’re doing something much akin to counting cards! Therefore, if we actually create a random deck we are accomplishing what everyone shuffling cards is attempting and will avoid the pitfalls of pseudo-randomness.

I was thinking for kicks I’d try to implement an imperfect riffle shuffle on my virtual deck of cards. Although 8 of these may not be the “best” algorithm for a virtual shuffle, I thought it would be interesting. Then, I’ll work on the true algorithms to create truly random virtual card decks. According to the almighty wiki, a Fisher-Yates shuffle when properly implemented should give a truly random deck of cards (even though this algorithm can be used on things more than cards). Now that the problem has been researched and thought over, lets get coding!

PS. Here are some articles if you feel like reading more on this

SIAM News on how Diaconis showed how some new shelf shuffling machines in Vegas were giving players a 1 in 20 chance of guess the next card: http://www.siam.org/pdf/news/295.pdf

Paper on the perfect shuffle by Diaconis, Persi; Graham, R. L.; Kantor, William M: http://www-stat.stanford.edu/~cgates/PERSI/papers/83_05_shuffles.pdf

A news article on Diaconis’ work with imperfect shuffles: http://www.dartmouth.edu/~chance/course/topics/winning_number.html

Starting out again

Hi, my name is Alex, I'm a 24 year old software developer living in Vancouver. I created this blog because I wanted to start developing something I'm interested in and thought it would be good to chronicle my progresses. To be honest, I'm writing mostly for myself and will be surprised if anyone actually starts reading this regularly. If that become you, then thanks and let me know!

I've been out of university for about 2 years now, still feels like it hasn't been nearly that long. Out of university after a little traveling I got offered a nice position at a large company with a generous salary except that it was in QA Development. This means I develop testing automation software but also have to test manually when. Basically I end up splitting my time between the two and it has had it's challenges and can be interesting but doesn't really leave me feeling fulfilled as a developer.

After working there for a while, I found myself putting aside my personal development projects. I'd still keep up with technology and sometimes read up on the interesting things I encountered at work but this isn't even. I've given my head a shake and now it's time to do something I want to do. The plan here is to pick a project, think of where I want to take it then dice it into pieces and work on it.
Since I like to work on things that I personally would find useful or fun I decided that I will create a software representation of the card game Bang! as it seems like a good thing to get those programming muscles working the way I want them to again. You can see more info about it here and as the wiki article states, it's an interesting application of game theory.

So, I hope you'll look forward to growing with me as I take on this new challenge. I'm going to start on the first and smallest problem in my next post: The card shuffle - To approximate true random or to approximate human random.