Skip to content
Naked Security Naked Security

Serious Security: How randomly (or not) can you shuffle cards?

What if you could guess the next card correctly twice as often as you should?

Cryptoguru Bruce Schneier (where crypto means cryptography, not the other thing!) just published an intriguing note on his blog entitled On the Randomness of Automatic Card Shufflers.

If you’ve ever been to a casino, at least one in Nevada, you’ll know that the blackjack tables don’t take chances with customers known in the trade as card counters.

That term is used to refer to players who have trained their memories to the point that they can keep close track of the cards played so far in a hand, which gives them a theoretical advantage over the house when predicting whether to stand or hit as play progresses.

Card counters can acquire an advantage even if all they do is keep track of the ratio of 10-cards (Ten, Jack, Queen and King) to non-10s left in the dealer’s shoe.

For example, if the dealer is sitting with an Ace, but an above-average number of 10-value cards have already been used up, then the dealer has a below-average chance of making a blackjack (21 points with two cards, i.e. Ace and one of 10-J-Q-K) and winning at once, and an above-average chance of going bust before reaching the stopping point of 17 and above.

If you can balance the probabilities in your head in real time, then you may be able modify your bets accordingly and come out ahead in the long run.

Don’t actually try this, at least in Nevada: the casino is likely to catch you out pretty quickly, because your pattern of play will diverge notably from the most informed winning choices available if you aren’t counting cards. You might not end up in court, but you will almost certainly get escorted off the premises, and never let back in again.

Levelling the odds

To reduce the counterbalance of probabilities that card counters enjoy (those who haven’t been caught yet, at least), the casinos typically:

  • Deal hands from a shoe loaded with six packs (decks) of 52 cards. This means that each hand dealt out skews the remaining distribution of cards less than if a single pack were used.
  • Shuffle the entire shoe of 312 cards (six packs) before every hand. To save time and to remove suspicion from the dealer, a pseudorandom electromechanical machine shuffles the cards right on the table, in front of all the players.

That immediately raises the question posed by Schneier: just how well-shuffled are the cards when they emerge from the machine?

Notably, with six new packs of cards, which arrive in a predictable order (e.g. Ace to King of Hearts, Ace to King of Clubs, King to Ace of Diamonds, King to Ace of Spades), how much partial ordering is left after the machine has done its work?

Could you “guess” the next card out of the shoe better than chance suggests?

A fully electronic randomiser is limited in its complexity mainly by the speed of the CPU that it uses, which is typically measured in hundreds of millions or billions of arithmetical operations a second.

But an electromechanical card shuffler literally has to move the cards around in real life.

There’s obviously a limit to how quickly it can perform pack splits, card swaps and interleaving operations before the speed of the mechanism starts to damage the cards, which means that there’s a limit to how much randomness (or, more precisely, pseudorandomness) the machine can introduce before it’s time to play the next hand.

Shuffle for too short a time, and the casino might actually make things easier for card counters, if there’s a known bias in the distribution of the cards right from the start.

Shuffle for too long, and play will be too slow, so that players will get bored and wander off, something that casinos desperately try to avoid.

Schneier’s blog posts links to a fascinating piece by the BBC that describes how a mathematician/magician called Persi Diaconis of Stanford University, together with Jason Fulman and Susan Holmes, conducted a formal investigation into this very issue earlier this century, in a paper entitled simply: ANALYSIS OF CASINO SHELF SHUFFLING MACHINES.

Levels of complexity

Clearly, there are some shuffling techniques that don’t mix the cards up much at all, such as simply cutting the pack into two parts and moving the bottom part to the top.

Other techniques result in (or feel as though they should result in) to better mixing, for example the riffle shuffle, where you split the pack roughly in half, hold one half in each hand, and “flip” the two halves together, interleaving them in a pseudorandom way that alternates between taking a few cards from one side, then a few cards from the other.

The idea is that if you riffle-shuffle the pack several times, you perform a pseudorandom sequence of cuts each time you divide the pack before each riffle, mixed together with a pseudorandomly variable sequence of pseudorandom interleaving operations involving an N-from-the-left-then-M-from-the-right process.

Intriguingly, however, when skilled human shufflers are involved, none of those assumptions of unpredictability are safe.

Dextrous magicians and crooked dealers (Diaconis himself is the former, but not the latter) can perform what are known as faro shuffles, or perfect shuffles, where they do both of the following things every time they riffle the pack:

  • Split the cards precisely in two, thus getting exactly 26 cards in each hand.
  • Interleave them perfectly, flipping down exactly one card at a time alternately from each hand, every single time.

Diaconis himself can do perfect shuffles (including the rare skill of doing so with just one hand to hold both halves of the pack!), and according to the BBC:

[He] likes to demonstrate the perfect shuffle by taking a new deck of cards and writing the word RANDOM in thick black marker on one side. As he performs his sleight of hand with the cards, the letters get mixed up, appearing now and then in ghostly form, like an imperfectly tuned image on an old TV set. Then, after he does the eighth and final shuffle, the word rematerialises on the side of the deck. The cards are in their exact original sequence, from the Ace of Spades to the Ace of Hearts.

Two types of perfection

In fact, there are two sorts of perfect shuffle, depending on which hand you start riffling from after cutting the cards into two 26-card piles.

You can interleave the cards so they end up in the sequence 1-27-2-28-3-29-…-25-51-26-52, if the first card you flip downwards comes from the hand in which you are holding he bottom half of the pack.

But if the first card you flip down is the bottom card of what was previously top half of the pack, you end up with 27-1-28-2-29-3-…-51-25-52-26, so the card just past halfway ends up on top afterwards.

The former type is called an out-shuffle, and reorders the pack every eight times you repeat it, as you can see here (the image has 52 lines of pixels, each line corresponding to the edge of one card with the word RANDOM written on it with a marker pen):

Every 8 out-shuffles, the original order of the lines in the image repeats.

The latter type is an in-shuffle, and this, amazingly, takes 52 re-shuffles before it repeats, though you can see clearly here that the pack never really shows any true randomness, and even passes through a perfect reversal half way through:

The in-shuffle repeats in a fascinating way every 52 times.

What did the mathematicians say?

So, back in 2013, when Diaconis el al. studied the shelf shuffler machine at the manufacturer's invitation, what did they find?

As the paper explains it, a shelf shuffler is an electromechanical attempt to devise an automated, randomised "multi-cut multi-riffle shuffle", ideally so that the cards only needs to be worked through once, to keep shuffling time short.

The cards in a shelf shuffler are rapidly "dealt out" pseudorandomly, one at a time, onto one of N metal shelves inside the device (whence the name), and each time a card is added to a shelf it's either slid in at the bottom, or dropped on the top of previous cards. (We assume that trying to poke the card in between two random cards already in the stack would be both slower and prone to damage the cards.)

After all cards have been assigned to a shelf, so that each shelf has about 1/Nth of the cards on it, the cards are reassembled into a single pile in a pseudorandom order.

Intuitively, given the pseudorandomness involved, you'd expect that additional re-shuffles would improve the overall randomness, up to a point…

…but in this case, where the machine had 10 shelves, the researchers were specifically asked, “Will one pass of the machine be sufficient to produce adequate randomness?”

Presumably, the company wanted to avoid running the machine through multiple cycles in order to keep the players happy and the game flowing well, and the engineers who had designed the device had not detected any obviously expoitable statistical anomalies during their own tests.

But the company wanted to make sure that it hadn’t passed its own tests simply because the tests suited the machine, which would give them a false sense of security.

Ultimately, the researchers found not only that the randomness was rather poor, but also that they were able to quantify exactly how poor it was, and thus to devise alternative tests that convincingly revealed the lack of randomness.

In particular, they showed that just one pass of the device left sufficiently many short sequences of cards in the shuffled output that they could reliably predict between 9 and 10 cards on average when a pack of 52 shuffled cards was dealt out afterwards.

As the researchers wrote:

[U]sing our theory, we were able to show that a knowledgeable player could guess about 9-and-a-half cards correctly in a single run through a 52-card deck. For a well-shuffled deck, the optimal strategy gets about 4-and-a-half cards correct. This data did convince the company. The theory also suggested a useful remedy.

[…]

The president of the company responded, “We are not pleased with your conclusions, but we believe them and that’s what we hired you for.” We suggested a simple alternative: use the machine twice. This results in a shuffle equivalent to a 200-shelf machine. Our mathematical analysis and further tests, not reported here, show that this is adequately random.

What to do?

This tale contains several “teachable moments”, and you’d be wise to learn from them, whether you’re programmer or product manager wrestling specifically with randomess yourself, or a SecOps/DevOps/IT/cybersecurity professional who’s involved in cybersecurity assurance in general:

  • Passing your own tests isn’t enough. Failing your own tests is definitely bad, but it’s easy to end up with tests that you expect your algorithm, product or service to pass, especially if your corrections or “bug fixes” are measured by whether they get you through the tests. Sometimes, you need a second opinion then comes from an objective, independent source. That independent overview could come from a crack team of mathematical statisticians from California, as here; from a external “red team” of penetration testers; or from an MDR (managed detection and reponse) crew who bring their own eyes and ears to your cybersecurity situation.
  • Listening to bad news is important. The president of the shuffling machine company in this case answered perfectly when he admitted that he was displeased at the result, but that he had paid to uncover the truth, not simply to hear what he hoped.
  • Cryptography in particular, and cybersecurity in general, is hard. Asking for help is not an admission of failure but a recognition of what it takes to succeed.
  • Randomness is too important to be left to chance. Measuring disorder isn’t easy (read the paper to understand why), but it can and should be done.

Short of time or expertise to take care of cybersecurity threat response? Worried that cybersecurity will end up distracting you from all the other things you need to do?

Learn more about Sophos Managed Detection and Response:
24/7 threat hunting, detection, and response  ▶


12 Comments

What to do?
Don’t bet in casinos – it seems to me that the owners are prepared to swing the odds in their favour in any way they can.

Reply

In this case, the casino’s best bet, so to speak, is to get the randomness right and the odds spot on…

As for banning card counting as a condition of entry, the casino might argue that is simply how the game is defined. Dealer has to hit to 16, must stick at 17 and up; players mustn’t use “a priori” knowledge from earlier cards in the hand to adjust their strategy.

Reply

Since casinos seem to know all the science and angles, as much as possible to date anyway, while enforcing the patrons use of as little knowledge as possible it’s a fools game to convince oneself ‘odds’ have anything to do with what $ you leave with… even with choreographed psych, alcohol and distraction left aside. The first look at a casino should tell a person they play to win, you… you’re just supposed to have a ‘good time’ while losing your $ with a smile of course should you chose to enter. Wonder what the average % of patrons who are having one of those rare just-can’t-lose nites is.

Reply

This article misses so many important points. Here are a few:

Card counting doesn’t require a trained mind, only a disciplined approach. Assigning each card one of three values, keeping a running count, converting to a true count, then adjusting your wager when the count is sufficiently positive. (Meaning there are more high cards than usual remaining, which means more blackjacks–which pay 3:2.)

You can beat card counters by running a 6:5 blackjack game. It increases the house edge so that even card-counting can’t overcome it.

The number of decks in the shoe is irrelevant. You adjust the running count into the true count by seeing how many decks remain to be dealt. This can be done with any number of decks.

Automatic shufflers don’t slow down the game; they speed it up. How? Because one set of cards is being shuffled while another is being used for play. Then, when that set is played out, it is switched with the cards in the shuffler. Thus, no time is lost to shuffling and the cards are shuffled so much during their time off the table that they are truly random. I’m not sure how this was missed.

Even with the information the article provides regarding card predicting, what would one do with the information? Remember, card-counting is not about knowing (or guessing) which cards will be dealt when. No one can do that. It’s about determining whether there are more blackjack-causing cards (10s and aces) than normal, sufficient to cause the counter to raise his bet accordingly. That’s it.

To be an effective card-counter–turning a slight house edge into a slight player’s edge–requires these things: perfect basic strategy, maintaining a running count, converting it to a true count, adjusting the wagers accordingly, and altering some basic strategy moves based on the true count.

Oh, and don’t get caught. Casinos do not like advantage players because they win. Card counting isn’t illegal and it isn’t cheating. But a casino has the right to refuse your play (or level-bet you, which is effectively the same thing) for any reason (or no reason at all.) And if they “trespass” you, you have to stay out of that casino for face charges. Not for cheating, but for trespass.

You’re welcome.

Reply

Seriously? You can’t imagine what you might do to boost your game if you could strongly predict the next card as well as adjusting your mental probabilities slightly after each card gets dealt?

Havide said that, this article is really about randomness and quality assurance rather than card counting, as you can see from the “What to do?” section at the end…

…I suspect you didn’t look at the paper itself that the article is about (where the randomness of the card shuffler is studied).

As for the cards being shuffled so much that they are “always random”, well, that’s the sort of assumption that would have got you in trouble if you were the company that made the machine in this case. They wanted the device to be fast enough that it only had to shuffle once, for all that you say speed doesn’t matter, yet be random enough, and their own tests suggested it was. But the right sort of tests shows it was not.

*That* is they key takeaway from the article: in coding and in cybersecurity, devising tests you can pass is easy. Devising tests that are worth passing can be hard.

Reply

If the house didn’t win most of the time, it wouldn’t exist.
The only way to win, is to play for fun.
Expect to lose any money you bet, and just have fun (with the free drinks)
Internet files are the same, but you gamble everything in your device and all it has access to.

Reply

The problem isn’t how easy/hard it is to randomly shuffle cards, but rather how easy it is to trick people into making a shuffle look real. With only a few hours of practice you can learn to thoroughly “shuffle” cards such that they’re in the exact same order they started, meaning you can pre-prep a deck. It’s also EXTREMELY easy to look at a card without people seeing, and then shuffle the deck such that it lands on top. I can’t stress enough how little skill is needed for that. Drawing from the bottom while making it look like you’re drawing from top is a bit harder, but also very doable for beginners so long as they can hold the deck in both hands while dealing. These are very easy learn. I went from zero to pretty good slight of in less than a week watching a few free youtube videos.

Reply

Of course, the ultimate goal here is kind of the inverse of that… how to avoid thinking you’re a good shuffler when in fact you aren’t mixing things up as well as you thought. And the even harder problem – how to make sure which camp you’re in.

(Knowing you’re shuffling non-randomly is easy in comparison, and if your goal is to restore the cards to the same order or not to disturb them to start with, measuring success is trivial in comparison!)

Reply

Rich makes some very good points above. I’m going to add info relevant to the shuffling challenge. I played on a card counting team in the late 1970’s and early 1980’s. The primary casino defenses against counters back then were casinos using multiple decks (lowering counter percentage win rate), reshuffling once about 60% of deck/shoe had been dealt and reshuffling when a new player makes a large bet (also cuts into the counter and counter team win rate) and watching for counting “tells” – obvious signs that a player was counting – and then barring counters from playing. Most of the physical surveillance happened at higher limit tables. Since then, casinos have devised more defenses. The simplest one is paying 6:5 (instead of 3:2) for blackjack which Rich points out is a game that card counters cannot beat. They also use technology (“eye in the sky” supplemented by software) to automatically calculate how closely a person is playing and betting to optimal play. Card counters though have also devised ways to combat casino countermeasures. The best card counting teams that play today use the exact kind of “clumping tracking” described by the imperfect shuffle article. I do not understand exactly how they use clumping to supplement card counting, just that they are able to do it and some have made considerable money ($1m+) doing it. I’m told that Edward Thorp (the “father” of card counting) has been involved with this with at least one or more counting/clumping teams. So this problem of the automated card shufflers NOT shuffling randomly has been known and successfully exploited for, at minimum, the last 10 years. A good analogy is when a known software vulnerability – known only by very, very few people – is actively exploited until it is patch. Final point: Using clumping tracking and modifying playing and betting strategy based on that plus card counting is MUCH more difficult than just regular card counting alone. My best guess is there are fewer than 5-10 teams actively using this strategy profitably.

Reply

As mentioned in the article, the paper cited (which you will see from the PDF dates to 2013) seems to have been written about an analysis done in the early 2000s (based on the dates of relevant media reports listed in the paper).

“Clumping” is a good shorthand term for “residual partial sequences”! The simplest form of prediction discussed in the paper was “guess one up” (e.g. 4H -> 5H) and if wrong switch to “one down”.

Reply

No you won’t end up in court because card counting is not illegal. Yes if they even think you are counting and they also think you are winning at an abnormal rate they will see you out and there is nothing you can do about it whether you were counting or not.

Reply

I think that’s pretty much what the article says… I chose to say “you might not end up in court” because my understanding is that if you are just counting and memorising the data you are legal but if you happen to use certain types of device to assist you (or if you return after you’re banned) you could call foul of the law. In simple words, “there’s counting you can do legally but won’t be allowed to by the casino, and there’s counting you can’t do legally and (obvs.) aren’t allowed to either”…

Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to get the latest updates in your inbox.
Which categories are you interested in?
You’re now subscribed!