Fisher–Yates shuffle: how random numbers become a fair deck of cards

A dice roll needs one random number, but a hand of cards or a Mines grid needs a whole order in which nothing repeats. The Fisher–Yates shuffle, first published for pencil and paper in 1938, makes every order equally likely. Below are the method, a Mines layout checked by hand, and the shortcuts that break it, including a 1999 poker shuffle that let researchers see every card.

Why a deck needs a shuffle

Once the ace of spades is dealt, the next card has to come from the 51 left, so the randomness must choose a whole order, or for a partial draw a set:

The deck figure is 52 factorial (52 × 51 × … × 1), between 2²²⁵ and 2²²⁶. A fair shuffle makes every result equally likely.

On cs2.casino, Video Poker uses a full 52-card shuffle for every hand, Mines fixes its 1 to 24 mines on the 5×5 grid when the bet is placed, and Keno draws 10 of 40 numbers. Blackjack uses an infinite deck instead, drawing each card on its own, so cards can repeat.

Strike out and pick again

Ronald Fisher and Frank Yates described the method in 1938 in their book Statistical Tables for Biological, Agricultural and Medical Research, using a table of random numbers. Write down 1 to N, pick a random k from 1 to however many are left, strike out the k-th number still standing and copy it to a new list, and repeat.

Richard Durstenfeld's 1964 computer version in Communications of the ACM swaps the chosen item with the last unchosen one instead, so the list never needs recounting. Donald Knuth popularised it in The Art of Computer Programming as Algorithm P.

It is fair as long as each pick is: the first card is one of 52, the next one of 51 and so on, so every order has the same chance, 1/52 × 1/51 × … × 1/1, or 1 in 52 factorial. With floats, random numbers from 0 up to 1, a pick from m items left is floor(float × m): the float times m, rounded down. A partial draw stops early: 3 mines are the first 3 picks from 25 tiles, a Keno draw the first 10 from 40.

Checking a Mines layout by hand

Here is a 3-mine layout from made-up seeds, so you can reproduce every number:

• Server seed: 754637dc56ac86a1182d8e122654b55f9e234b6404eec323dbff12562c33e75d, 32 random bytes as 64 hex characters
• Its SHA-256 hash, shown before betting: 5e5bca3ef6e095867a47cca5a5d449d94d4571aeb5bc865dfb5da47ba4a86c55
• Client seed inferno_banana, nonce 4 (the bet counter)

Block 0 is the keyed hash HMAC-SHA256 of inferno_banana:4:0 with the server seed as key, which gives 533d03206e6ca9a1911d33921ba40628e449ac03e14f4abec1fe0876aa5c8ef0. Every four bytes make a float, b0/256 + b1/256² + b2/256³ + b3/256⁴, and the step-by-step verification guide has commands for both steps. Number the tiles 0 to 24, row by row from the top left (floats rounded to six places):

The index is floor(float × tiles left), counted among tiles still in play. With tile 8 gone, index 10 is tile 11, and with 8 and 11 gone, index 13 is tile 15.

For a real bet, rotate your seed pair to reveal its server seed and apply that game's rule from the provably fair page. The check covers the whole deck or grid, not just what you saw.

Three ways to get a shuffle wrong

Swapping with any card

A common mistake is to swap each position with one chosen from the whole deck, not just from the cards not yet placed. That makes nⁿ equally likely swap sequences for n factorial orders, and with more than two cards the first is never a multiple of the second, so some orders come up more often. Three cards give 27 sequences for 6 orders:

A fair shuffle gives each 1 in 6 (16.7%). A full deck can't split evenly either, since 52⁵² = 2¹⁰⁴ × 13⁵² has no factor of 3 and 52 factorial does. Worked out exactly for this article, the card that starts second ends on top 2.60% of the time and the last card 1.43%, against 1.92% (1 in 52) in a fair shuffle.

Never leaving a card in place

Picking the swap position strictly below the current one, rather than up to and including it, gives Sattolo's algorithm, published by Sandra Sattolo in 1986. It only makes orders that form one loop through the whole deck, so no card stays put and 51 of every 52 possible decks never appear.

Sorting at random

Another shortcut sorts with a comparison that answers at random. The result depends on the sort algorithm and is usually far from even, as Mike Bostock's 2012 visualisations show.

How even floor(float × n) is

A float built from 4 bytes has 2³² = 4,294,967,296 possible values, which 52 doesn't divide, so in a pick from 52 cards, 48 cards own 82,595,525 values each and 4 own 82,595,524, a gap of about 1 in 82.6 million. Across a whole deck, every order stays within 0.00002% of 1 in 52 factorial.

Modulo bias, the classic form of the problem, shows what a small random source does: turning numbers 00 to 99 into 0 to 15 by the remainder after dividing by 16 makes 0 to 3 about 17% more likely, because 16 doesn't divide 100. Discarding 96 to 99 and drawing again fixes it.

The 1999 poker shuffle

In September 1999, researchers at Reliable Software Technologies showed what a weak shuffle costs. ASF Software's Texas Hold'em software ran real-money games, and its shuffle code had been posted on a poker room's site to show the game was fair. Its flaws included:

1. An off-by-one error: the swap position came from random(51)+1, 1 to 51, so the 52nd card could never end in 52nd place.
2. The swap-with-any-card method above.
3. A 32-bit generator re-seeded for every shuffle, allowing at most about 4.3 billion decks. The seed was the milliseconds since midnight, cutting that to 86,400,000.

Syncing with the server's clock narrowed it to about 200,000 decks, few enough to search on a PC in real time. From the player's own two cards and the first three shared cards, the researchers' program found the whole deck, and with it every opponent's hand and every card to come. ASF changed its shuffle after being told. The researchers' advice was not to hide the code but to pair a sound shuffle with a 64-bit generator seeded from a hardware random source.

What a committed seed changes

A provably fair deck also follows entirely from its seeds, but size and timing differ. A seed of 32 random bytes, like the example's, has 2²⁵⁶ possible values, about 1.4 billion per order of a deck; at a trillion guesses a second, trying them all would take around 3.7 × 10⁵⁷ years. And the server seed is committed by its SHA-256 hash before you bet, while your client seed can change afterwards, so the house can't pick a server seed to suit a client seed it hasn't seen. The provably fair explainer covers why that order matters.

A fair shuffle only makes every order equally likely; it doesn't change what a game pays. Every game on cs2.casino shows its house edge and bet limits, and over time the house wins. Video poker odds shows what 9/6 Jacks or Better returns from a perfectly shuffled deck, and Mines game odds shows how the Mines multipliers follow from mines drawn this way.

Sources

• Fisher–Yates shuffle — Wikipedia
• Fisher-Yates shuffle — NIST Dictionary of Algorithms and Data Structures
• Statistical tables for biological, agricultural and medical research (1938) — Wellcome Collection
• Fisher–Yates Shuffle (2012) — Mike Bostock
• Will It Shuffle? (2012) — Mike Bostock
• How to Cheat at Online Poker: A Study in Software Security (1999) — Datamation
• Internet Gambling Exploit (3 September 1999) — Bugtraq via SecLists.org
• Cheating in casinos — Wikipedia