The Javascript Shuffle

Photo by Jack Hamilton on Unsplash

I was always fascinated by card games, especially those that involved skill over luck. I’ve passed this love of card games onto my children and have taught them many of the popular standards, including an altered version of Gin Rummy (that involves a Joker) and BlackJack. We played War, Go Fish, Crazy 8’s, and Hearts, but Poker is my go-to game, specifically No Limit Texas Hold ’Em. I’ve attended many Poker tournaments and played till the wee hours at many casino tables and home games.

What do those games have in common? Before dealing out the cards, they should be shuffled. When my career started decades ago, one of the first simulated card games that I developed was BlackJack. It was written in BASIC, and I’ve probably rewritten it a dozen times now in multiple languages: Java, C#, C, Assembler, PHP, Perl, Python, Shell scripting, even in FileMaker. The most challenging version was on a scientific HP calculator.

My favorite programming language now is Javascript, using server-side Node.js and client-side Vue.js. Implementing a tech stack like VENoM removes the context switching inherent in other stacks; reducing the language fragmentation by leveraging the entire Javascript ecosystem.

With Javascript, there are numerous ways to simulate a deck of shuffled cards. So let’s get down to the code.

The Deck

First, we will need a deck. The most simplified version of a deck is just a plain array of numbers from 0 to 51 to represent the 52 cards in a standard set of playing cards. For this, we need one line of code:

let deck = Array.from(new Array(52), (x, i) => i);

A real-world schema for a deck structure would include the actual suits (Club, Diamond, Heart, Spade) and the ranks (2, 3, 4, 5, 6, 7, 8, 9, T, J. Q, K, A), but for now, we will keep it simple.

No Shuffle

The most minimal use of shuffling the deck is to have no shuffle. What do you mean no shuffle? Isn’t shuffling the gist of this article? It depends on how your program will use this deck. If you are dealing out hands, maybe a shuffle is not needed. It’s a computer simulation. You can randomly pull cards out of the ordered deck and deal them in that fashion. In real life, if you were pulling cards from the middle of the deck, you’d at least solicit funny looks from other players, and at worse, probably receive a good beating. Here is an example of how you would deal from an unshuffled deck:

hand.push(deck.splice(Math.floor(Math.random() * deck.length), 1)[0]);

Using Array.splice() serves a dual purpose: 1) directly affecting the array by removing the element, 2) returning that element to the caller. This line would be included in a loop that would iterate through the players and deal out N-number of cards per player, dictated by the rules of the game. That same code could also be used on a shuffled deck. An example deal function would look like this:

function deal(deck, players, numCards) {
  players.forEach(player => {
    while(player.hand.length !== numCards) {
      player.hand.push(deck.splice(Math.floor(Math.random() * deck.length), 1)[0]);
    }
  });
}

For simplicity and brevity, the deal function does not contain error-handling code. It does not ensure if enough cards are remaining to fulfill the complete distribution to the players. Since this is dealing cards from an unshuffled deck, it doesn’t matter if the order of the deal ignores the typical round-robin pattern. The loop will deal out the correct number of cards at once to each player.

Now on to the shuffling.

Naive Shuffle

Let’s start with what I would coin the “naive” shuffle. The code below would represent an initial first version of a shuffle algorithm that a majority of programmers would discover. This mechanism would switch the values of two random cards:

function naiveShuffle(deck) {
  let randomCardA;
  let randomCardB;
  let tempX;
  for (let index = 0; index < deck.length; index += 1) {
    randomCardA = Math.floor(Math.random() * deck.length);
    randomCardB = Math.floor(Math.random() * deck.length);
    tempX = deck[randomCardA];
    deck[randomCardA] = deck[randomCardB];
    deck[randomCardB] = tempX;
  }
}

This code has a significant flaw. Can you spot it? Since there is no guarantee that the two random numbers will be different, it’s possible that a card switches with itself and some cards will never be switched. Let’s improve this code by forcing the swap on each card in the deck and eliminating the need to generate two random numbers:

function altNaiveShuffle(deck) {
  let randomCard;
  let tempX;
  for (let index = deck.length - 1; index > -1 ; index -= 1) {
    randomCard = Math.floor(Math.random() * deck.length);
    tempX = deck[index];
    deck[index] = deck[randomCard];
    deck[randomCard] = tempX;
  }
}

This alternative is better, with less code, but does not guarantee that the position of randomCard will not equal the index. We can make a small alteration which will match an algorithm that fixes this problem.

Fisher-Yates Shuffle

A single line change in the function above will morph it into implementing the Fisher-Yates algorithm. This change will randomly choose cards that have not been iterated through, avoiding the possibility that a card switches with itself.

randomCard = Math.floor(Math.random() * index);

The random pool of cards to choose from will be one less than the current index due to the mechanism of Math.floor. In other words, it’s targeting the set of remaining cards that are eligible for a swap.

Value vs. Position

The code above works great. It’s performant and optimal. But there is one aspect that bothers me. Instead of moving the position of each card, it’s swapping the values. In a real-world recreation, it would be equivalent to this:

1. Remember the value of the card in position A
2. Draw over the card in position A with a value from position B
3. Draw over the card in position B with the remembered value
4. Repeat this process for the duration of the shuffle

It seems a bit dirty to me. Shuffling by changing the face value of a card is like moving the labels of a Rubik’s Cube to solve it. Let’s use a bit of code from an earlier section to shuffle the cards by position instead of value, using Array.splice() but adhering to the Fisher-Yates algorithm:

function spliceShuffle(deck) {
  let count = deck.length;
  let tempX;
  while(count) {
    tempX = deck.splice(Math.floor(Math.random() * count), 1);
    deck.splice(count, 0, tempX[0]);
    count -= 1;
  }
}

This solution feels cleaner. But wait, now there are two splice operations. Could this be improved? Yes, let’s try a different mechanism.

Stack Shuffle

I’m always looking to improve my coding, including refactoring, to reduce the size or optimize performance. The shuffle function can be reduced further, by using native prototypical functions built into the Array model, like Array.push() and a little experimentation:

function stackShuffle(deck) {
  let count = deck.length;
  while(count) {
    deck.push(deck.splice(Math.floor(Math.random() * count), 1)[0]);
    count -= 1;
  }
}

The stack push moves the card to the bottom of the array (by order) which walls it from the random selection, keeping it in line with the Fisher-Yates algorithm.

Riffle Shuffle

The stack shuffle represents one of the most optimal implementations (in code-size) of the Fisher-Yates algorithm, but it does not follow how shuffling is done in the real world. It is a simulation where the result presents itself as a shuffled deck of cards. It does not mimic the mechanics of a riffle shuffle, the most widely used technique for shuffling a deck of cards. Here is how a riffle shuffle works in the physical world:

1. Split the deck approximately in half
2. One half in the left hand, the other half in the right hand
3. Riffle the edges of both sets so they intermingle
4. Push the cards together
5. Repeat the process for 6 more times

How can we alter the stackShuffle function to represent a physical riffle shuffle? Assuming that a cut deck will not always be exactly 26 cards, we will introduce a random variant of -4 to +4 on one half. When the cards are riffled, they will not intermesh exactly one card apart; therefore, another variant of 1–3 cards should be introduced. Then both sides are meshed back together from the bottom up. There is also a 50 percent chance that the left side will start before the right side. In reality, I assume the dealer’s dominant hand would lead. Let’s codify all of those variants into the shuffle function:

function riffleShuffle(deck) {
  const cutDeckVariant = deck.length / 2 + Math.floor(Math.random() * 9) - 4;
  const leftHalf = deck.splice(0, cutDeckVariant);
  let leftCount = leftHalf.length;
  let rightCount = deck.length - Math.floor(Math.random() * 4);
  while(leftCount > 0) {
    const takeAmount = Math.floor(Math.random() * 4);
    deck.splice(rightCount, 0, ...leftHalf.splice(leftCount, takeAmount));
    leftCount -= takeAmount;
    rightCount = rightCount - Math.floor(Math.random() * 4) + takeAmount;
  }
  deck.splice(rightCount, 0, ...leftHalf);
}

As shown, the riffleShuffle function is relatively complicated compared with the stackShuffle. It requires multiple shuffles due to the possibility that the first or last card on either side of the deck would remain the same, depending on how the deck is cut and which side starts the riffle. Shuffling seven times is the suggested number of shuffles to produce a substantially randomized deck when using the riffle technique.

Sometimes experimenting with alternate solutions will amplify a previous one and promote that as the clear winner.

For any of my future card-related projects, I would stick with the stackShuffle as it is the most compact version. Less code equates to lower defect counts.

Iterate and Improve

There are probably numerous ways to code a shuffle function. As long as it fits your needs and creates the effect of a shuffled set of items, then continue to use it. But challenge yourself to think of alternative strategies and methods to improve your coding skills and reduce lines of code while optimizing for performance. Revisiting past projects may be helpful to start with an existing code-base. Refactor code by iterating through small changes and leveraging the full capabilities of a programming language. A continuous approach to improve your code by iterating small changes will eventually yield an optimal solution.