## Introduction

For the most part, I don't play a lot of table games, and I *don't play party games*. But occasionally, I'll sit down with my family and play a board game or card game. When we play a card game though, I get teased by how I shuffle the deck of cards.

I know that to maximize entropy in the deck, it should be riffle shuffled at least 7 times, but a better security margin would be around 10 shuffles, and after 12, I'm just wasting my time. But I don't always riffle shuffle. I'll also do various deterministic shuffles as well, such as the pile shuffle to separate cards from each other.

I'm familiar with a number of deterministic card shuffles, which I didn't even know had names:

**Pile shuffle**- Separate the cards into piles, one at a time, until exhausted, then collect the piles. I usually just do 4 or 5 piles, and pick up in order.**Mongean shuffle**- Move the cards from one had to the other, strictly alternating placing each discard on top then beneath the previously discarded cards.**Mexican spiral shuffle**- Discard the top card on the table, and the second card to the bottom of the deck in your hard. Continue discarding all odd cards to the table, all even cards beneath the deck in hand until exhausted. I never do this shuffle, because it takes too long to execute.

In practice, when I'm playing a card game with my family, I'll do something like 3 riffle shuffles, a pile shuffle, 3 more riffle shuffles, a Mongean shuffle, 3 more riffle shuffles, another pile shuffle, then one last riffle shuffle. I'll get teased about it, of course: "Dad, I'm sure the cards are shuffled just fine. Can we just play now?", but when we play the game, I'll never hear complaints about how poorly the deck was shuffled.

This got me thinking though- there aren't that many simple deterministic blind card shuffles (I say "blind", because any of the playing card ciphers would work, but that requires seeing the cards, which is generally frowned upon when playing competitive card games). I wonder what else is out there. Well, doing some web searches didn't turn out much. In fact, all I could find were variations of the above shuffles, such as random pile discarding and pickup, but nothing new.

So the question then turned into- could I create my own simple deterministic card shuffle? It didn't take me long before I came up with what I call the "Ouroboros shuffle".

## The Ouroboros Shuffle

Before going any further, let me state that I *very much doubt* I'm the first to come up with this idea, but I have searched and couldn't find where anyone else had documented it. If it does in fact exist, let me know, and I'll gladly give credit where credit is due. Until then, however, I'll stick with calling it the "Ouroboros Shuffle", named after the serpent or dragon eating its own tail.

The shuffle is simple:

- Holding the deck in your hard, discard the first card from the bottom of the deck to the table.
- Discard the top card of the deck to the discard pile on the table.
- Repeat steps 1 and 2, strictly alternating bottom and top cards until the deck is exhausted.

If the playing cards are plastic-based, like those from Kem or Copag, then you could "pinch" the top and bottom cards simultaneously, and pull them out of the deck in your hand to the tale. If you do this perfectly, you will pinch 2 cards only 26 times. If they're paper-based though, this may or may not work as efficiently due to cards having a tendency to stick together after heavy use.

If the deck was unshuffled as "1, 2, 3, ..., 50, 51, 52", then the first shuffle would look like this:

Step: 0 Unshuffled: 1, 2, 3, ..., 50, 51, 52 Shuffled: <none> Step: 1 Unshuffled: 1, 2, 3, ..., 49, 50, 51 Shuffled: 52 Step: 2 Unshuffled: 2, 3, 4, ..., 49, 50, 51 Shuffled: 1, 52 Step: 3 Unshuffled: 2, 3, 4, ..., 48, 49, 50 Shuffled: 51, 1, 52 Step: 4 Unshuffled: 3, 4, 5, ..., 48, 49, 50 Shuffled: 2, 51, 1, 52 Step: 5 Unshuffled: 3, 4, 5, ..., 47, 48, 49 Shuffled: 50, 2, 51, 1, 52 Step: 6 Unshuffled: 4, 5, 6, ..., 47, 48, 49 Shuffled: 3, 50, 2, 51, 1, 52 .... Step 50: Unshuffled: 26, 27 Shuffled: 25, 28, 24, ..., 51, 1, 52 Step 51: Unshuffled: 26 Shuffled: 27, 25, 28, ..., 51, 1, 52 Step 52: Unshuffled: <none> Shuffled: 26, 27, 25, ..., 51, 1, 52

As you can see, the top and bottom cards are always paired together in the unshuffled deck, and discarded as a pair to the shuffled deck. The top and bottom cards could also be thought of as the head and tail of a list, and thus why I called it the Ouroboros shuffle.

If you execute this algorithm perfectly from an unshuffled deck, it will take 51 rounds to before restoring the deck to its unshuffled state.

## Observations

Almost immediately, I noticed a bias. It doesn't matter how many times I execute this algorithm, the bottom card will always remain on the bottom. In the above example, the King of Spades (if assigned the value of "52") will stay at the bottom of the deck, due to the nature of the shuffle of discarding the bottom card first. So I recognized that I would need to cut at least 1 card from the top of the deck to the bottom of the deck before the next round of the shuffle, to ensure the bottom card gets mixed in with the rest of the deck.

Other questions started popping up, specifically:

- How many perfect shuffles will it take to restore the deck to an unshuffled state now?
- Is there a different bias hidden after cutting the top card to the bottom?
- What if I cut 2 cards? 3 cards? 51 cards?

Whelp, time to code up some Python, and see what pops out. What I'm looking for is what the state of the deck looks like after each round. In other words, I want to know which card occupies which positions in the deck. For example, does the Seven of Clubs see all possible 52 positions in the deck? Without the cut, we know that's not possible, because the bottom card stubbornly stays in the bottom position.

Typing up a quick script and graphing with Gnuplot gave me the following images. The first image on the left is the Ouroboros shuffle with no cuts, where the right image is the Ouroboros shuffle followed by cutting the top card to the bottom of the deck as the end of the round. Click to enlarge.

What you're looking at is the card position in the deck along the X-axis and the card value along the Y-axis. In the left image, where the Ouroboros shuffle is executed without any following cuts, the 52nd card in the deck is always the face value of 52. But in the right image, where the Ouroboros shuffle is followed by cutting one card from the top of the unshuffled deck to the bottom, every card position sees every face value.

So what would happen if instead of cutting 1 card off the top to the bottom at the end of each round, I cut 2 cards, and cards, etc. all the way to cutting 51 cards off the top to the bottom? Well, more Python scripting, and I generated a total of 52 images showing every possible position a card occupies in the deck until the deck returns to its unshuffled state.

Interestingly enough, executing the Ouroboros shuffle followed by cutting 19 cards, leads to a cycle length of 6,090 perfect shuffles before restoring the deck back to its unshuffled state. Awesome! Except, as you can see in the Imgur post above, it's extremely biased.

Every shuffle-and-cut is listed here with its cycle length:

Cut: 0, iter: 51 Cut: 1, iter: 52 Cut: 2, iter: 51 Cut: 3, iter: 272 Cut: 4, iter: 168 Cut: 5, iter: 210 Cut: 6, iter: 217 Cut: 7, iter: 52 Cut: 8, iter: 418 Cut: 9, iter: 52 Cut: 10, iter: 24 Cut: 11, iter: 350 Cut: 12, iter: 387 Cut: 13, iter: 252 Cut: 14, iter: 1020 Cut: 15, iter: 144 Cut: 16, iter: 1972 Cut: 17, iter: 34 Cut: 18, iter: 651 Cut: 19, iter: 6090 Cut: 20, iter: 175 Cut: 21, iter: 90 Cut: 22, iter: 235 Cut: 23, iter: 60 Cut: 24, iter: 2002 Cut: 25, iter: 144 Cut: 26, iter: 12 Cut: 27, iter: 50 Cut: 28, iter: 24 Cut: 29, iter: 10 Cut: 30, iter: 44 Cut: 31, iter: 72 Cut: 32, iter: 297 Cut: 33, iter: 90 Cut: 34, iter: 45 Cut: 35, iter: 132 Cut: 36, iter: 12 Cut: 37, iter: 210 Cut: 38, iter: 207 Cut: 39, iter: 104 Cut: 40, iter: 420 Cut: 41, iter: 348 Cut: 42, iter: 30 Cut: 43, iter: 198 Cut: 44, iter: 35 Cut: 45, iter: 140 Cut: 46, iter: 390 Cut: 47, iter: 246 Cut: 48, iter: 28 Cut: 49, iter: 12 Cut: 50, iter: 36 Cut: 51, iter: 30

The only "shuffle then cut" rounds that are uniform appear to be cutting 1 card, 7 cards, and 9 cards. The other 49 shuffles are biased in one way or another, even if each of them have different cycle lengths.

Here's the Python code I used to create the shuffled lists, each into their own comma-separated file:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | #!/usr/bin/python def step_1(deck): tmp = [] for card in range(26): tmp.insert(0, deck[-1]) deck.pop(-1) tmp.insert(0, deck[0]) deck.pop(0) return tmp def step_2(deck, cut): return deck[cut:] + deck[:cut] orig = [_ for _ in range(1, 53)] deck = [_ for _ in range(1, 53)] for i in range(52): with open("cut_{}.csv".format(i), "w") as f: f.write(",".join(map(str, deck)) + "\n") deck = step_1(deck) deck = step_2(deck, i) n = 1 while deck != orig: with open("cut_{}.csv".format(i), "a") as f: f.write(",".join(map(str, deck)) + "\n") deck = step_1(deck) deck = step_2(deck, i) n += 1 print "Cut: {}, iter: {}".format(i, n) |

## Conclusion

This was a fun shuffle to play with and one that I'll incorporate into my card playing with my family. Now I could do something like: 3 riffle shuffles, Ouroboros shuffle with 1 card cut, 3 riffle shuffles, Mongean shuffle, 3 riffle shuffles, pile shuffle, 1 riffle shuffle, and I will be happy.

## Post a Comment