On the Randomness of Automatic Card Shufflers

Many years ago, Matt Blaze and I talked about getting our hands on a casino-grade automatic shuffler and looking for vulnerabilities. We never did it—I remember that we didn’t even try very hard—but this article shows that we probably would have found non-random properties:

…the executives had recently discovered that one of their machines had been hacked by a gang of hustlers. The gang used a hidden video camera to record the workings of the card shuffler through a glass window. The images, transmitted to an accomplice outside in the casino parking lot, were played back in slow motion to figure out the sequence of cards in the deck, which was then communicated back to the gamblers inside. The casino lost millions of dollars before the gang were finally caught.

Stanford mathematician Persi Diaconis found other flaws:

With his collaborator Susan Holmes, a statistician at Stanford, Diaconis travelled to the company’s Las Vegas showroom to examine a prototype of their new machine. The pair soon discovered a flaw. Although the mechanical shuffling action appeared random, the mathematicians noticed that the resulting deck still had rising and falling sequences, which meant that they could make predictions about the card order.

New Scientist article behind a paywall. Slashdot thread.

Tags: , ,

Posted on October 24, 2022 at 6:37 AM • 17 Comments

Comments

William Entriken • October 24, 2022 10:00 AM

For people seriously studying this topic, I have also worked on studying manual shuffling. I worked with dealers to watch exactly what they are doing and how those rules could be used to predict the next card to be dealt. With an emphasis on blackjack.

Here is a visualization https://github.com/fulldecent/blackjack-simulator/blob/master/Unshuffle/Unshuffle%20visualization.pdf

Internally, calling this project Hit on 18. Since it can come up with uncommon recommendations.

SpaceLifeForm • October 24, 2022 2:23 PM

@ sofa

From-the-Department-of-Redundancy-Department:

You are hired!

You did not check what Bruce posted.

Read.

SpaceLifeForm • October 24, 2022 3:45 PM

re: seven shuffles

Find it on the slashdot thread, and see what I wrote yesterday. I have described seven shuffles here previously.

Note that an AC troll popped up quickly, and see the responses.

The slashdot trolls always attack users with lower id numbers. Always.

Jeff • October 24, 2022 5:30 PM

@Ted: Perfect shuffles are not rare or very hard. There’s an entire literature in magic about what’s known as the “Faro Shuffle” (referring to the game, not the ruler). Some practitioners have the ability to make a Faro shuffle look like a normal riffle shuffle. It really doesn’t have much use for gamblers, though.

David Leppik • October 24, 2022 5:30 PM

Shuffling a deck of cards is anything but random. In fact, a perfect shuffle—which magicians learn—causes the deck to be back to the beginning after 8 shuffles. Even a novice can make sure the top and bottom cards stay in place with only a little practice.

What’s more interesting to me is how card games have been designed to minimize the effects of the non-randomness. I’m not talking professional casinos, I’m thinking of how poker has been played by amateurs for over a century. The middle of the deck is the most random, so another player cuts the deck to put the middle on top. Cards are dealt round-robin, so an off-by-one error causes a crooked dealer to give a different player their desired hand. Relatively few cards are dealt per round, and a different player deals every round, so a single crooked shuffle has limited effect.

Here’s a visualization of a perfect shuffle I did with CSS animations (and a little JavaScript) a while ago.

lurker • October 24, 2022 7:00 PM

@David Leppik

The article seems to say that although the deck returns to zero state after the 8th shuffle, it has a special feature that after the 7th “perfect” shuffle, even though deterministic, it is sufficiently mixed for many practical purposes. Using a “riffle” shuffle it’s no longer deterministic.

Clive Robinson • October 25, 2022 12:05 AM

@ Bruce,

As I’ve mentioned in the past I have an interest in “Card Shuffling Algorithms”(CSA) for security applications including as “entropy spreaders” on “True Random Number Generators”(TRNGs).

The problem is that all machine based CSA’s are bound and thus without an actual TRNG input are by definition not just determanistic but predictably so. Worse due to just how small the mechanical bounds are they are generally not that hard to reverse the sequences.

For those with a little more than curiosity consider the machines as being in several parts

1, Feed input / store.
2, Mix range store.
3, Mix function.
4, True Random input.

For reliability the “mix function” has to be mechanically simple, and is in effect at best can be compared to a simple “cellular automata” / “state machine”. Whilst the output can appear complex it’s not at all random and in the case of mechanics fully reversable.

But whilst these card shufflers can appear to have a very large state array due to the input store, in practice it’s not. At best it’s a simple “block swap” at worst just a linear feed hopper.

Thus the question of how big the state array is? Often it’s tiny and just spans a few cards due to the mechanical limits of the mixer and it is very linear in it’s operation. Thus the actual mixing even with a true random generator input is very limited in it’s range. But even if it were not limited by mechanical limits, it would be limited by the gaming commissions, because they would expect the statistics to fall into those you would get from a single pack –or five– of cards.

As for using a True Random Input, I would expect it to do in reality no more than a very limited swap process at the input or output of the mix function.

As we know due to certain “statistical” requirments it is very rare for the random generator in gambling devices to be actually “truely random” or even “nonlinear”.

So these mechanical card shufflers have the seeds of their own downfall more or less built in by design.

SpaceLifeForm • October 25, 2022 2:43 AM

@ Ted

re: Can you do a perfect shuffle?

Paper or Plastic?

Years ago, I probably could with a plastic deck. But, dexterity is not what it used to be.

@ Jeff

re: It really doesn’t have much use for gamblers, though.

But it can for the House or two co-conspirators in a home poker game that are sitting next to each other and know how to stack the deck and do not do cuts.

@ David Leppik. lurker

It is seven. Not eight.

Read what I posted on slashdot.

Do not repeat misinformation from the two articles. Seven shuffles is not sufficiently random at all. Eight shuffles is like doing one shuffle if you never cut the deck.

Just to verify, I just opened up a never used deck of cards. Quite old in fact. There was a plastic wrapper around the deck, which was brittle. Old. Root66 is the name on the cards. Out of the box, stripping off the brittle plastic, and after removing the Jokers on each side, the order was Spades Ace to King, Diamonds King to Ace, Clubs Ace to King, and Hearts King to Ace.

I then went thru the perfect shuffle procedure as I wrote up on slashdot.

As I said, seven perfect shuffles. Returns it to the exact starting order.

It is not Eight. Please do not repeat misinformation.

JonKnowsNothing • October 25, 2022 10:44 AM

@All

One experiment you can try, without even a perfect shuffle.

  • 1 pack of cards (new old doesn’t matter, poker deck or other)
  • 1 different back-colored card from another deck (the toss away card is a good choice)
  • Insert the different card anywhere you want in the deck. The back-color should be easy to spot it’s position.
  • Shuffle and note the position of the card as it travels through the deck.

For card games that run in sequences, like solitaire, spite and malice or games with “tricks” that capture same suit cards even with multiple decks being shuffled together, if you examine the results of shuffles, you will find “runs” in sequences.

Depending on circumstances, the game and the players, it’s not necessarily bad to have runs.

lurker • October 26, 2022 9:32 PM

@SLF
@Rachel Tobac did some people a good turn by revealing the nature of the beast:
“… where you need to scroll all the way down, potentially close a “log in” dialogue box, to reveal the “remove result” icon …”

Phillip • October 27, 2022 2:17 AM

I never really worked much at improving any shuffling. Though I sometimes figured perfection was interleaving these one-by-one. Then, is that right? The whole flair thing…

I am one to admit to sometimes being overly suspicious. Well, maybe it is just a game, though I never wasted much thought with putting money on a table, like, this way. Thus, it is imperative for me to explain how I manage my money well. Never mind this aspect of the comment.

James Bond is so debonaire, that any of us have to go to prove we are not worthy in a hole casino.

Next, a credit card is priceless.

Clive Robinson • October 27, 2022 9:32 AM

@ ResearcherZero, ALL,

This link,

https://research.checkpoint.com/2022/attacking-very-weak-rc4-like-ciphers-the-hard-way/

Is a useful read for those wondering about the mathmatics of certain types of “Card Shuffling Algorithms”(CSAs) used in crypto like Stream Cipher “Key Generators” of which the most well known generally is the “Alleged RC4” of Ron Riviset (the R of RSA algorithm fame). Oh and readers of certain books our own host @Bruce’s stream cipher actually based on using a pack of cards,

https://www.schneier.com/academic/solitaire/

Nearly all CSA’s have issues for various reasons and the link describes in part why.

But if you want to independently think about the issue before reading the link… Consider that the generator has a “State Arrary”(Sary) that is updated by what is usually a very simple algorithm not much different to a cellular automata that simply selects two cards and swaps them. One big problem is when the cards to be swapped is just one card so Sary does not get shuffled, which means information can leak, as well as putting bias in the output statistics and most importantly thesedays the side chanbels to do with time and power…

All these card shuffling machines are at best very very poor very limited subsets of such crypto systems, so reading the link will in part make it easier to assess the design of them and just how badly they actually fail.

The link was originally posted by @ResearcherZero over on another page, and I suggested a couple of days ago they also post it here due to it’s relevance. But…

wumpus • October 30, 2022 12:36 PM

And now for something completely different…

While I haven’t played bridge for ages, my understanding is that normal play tends to gather “good hands” and shuffling (twice?) makes things a bit more fair but “overshuffling” (i.e. more perfect shuffling) leaves the point distribution so low as to lead to many hands without a single bid.

Of course in bridge, tournament play is almost exclusively going to be duplicate bridge, a style that eliminates chance from the game. No idea if any casinos have high stakes “contract bridge” and how they would shuffle the cards. I’d expect casinos would want “more exciting” hands rather than many “no bid” hands, but then again I can’t see casinos wanting bridge (a game I tend to associate with grandparents in the 1970s).

SpaceLifeForm • October 31, 2022 2:38 AM

@ wumpus

Faux Noise missed their calling.

If they covered Bridge 24×7, they would have viewers and ad revenue.

You can imagine the commentary and play-by-play.

That was a lousy opening bid! Should have bid one diamond!

No, it was good that it was 1 no trump.

Time for a commercial break.

Many commercials later: OK, we have the dummy now here in the booth. Thanks for joining us. What did you think about the bidding process?

Dummy: I had to pass. The restrooms are not that close by.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.