Fog Creek Software
Discussion Board




Card shuffling routine

Eric Sinks solitaire program got me thinking about how to write a card shuffling routine.  I'd like to see other peoples routines or algorithms on how you think it should be done and what provides the best randomness.

The routine below picks a random slot for each card and then swaps the cards.  It does this 100 times.

Please don't tell me to go look on google for routines etc.. I want to see your ideas for shuffling a deck of cards.  I remember in the early to mid 90's there was a company that would advertise that they would give you a job if you could write the most innovative card shuffling routine.

void Shuffle(void)
{
    Card Temp;
    int j;

    srand((unsigned) time(NULL));

    for (int k = 0; k < 100; k++)
    {
        for (int i = 0; i < 52; i++)
        {
            do {
                j = rand() % 52;
            } while (j == i);
            
            Temp = Cards[i];
            Cards[i] = Cards[j];
            Cards[j] = Temp;
        }
    }
}

Poker
Friday, August 20, 2004

Collection.shuffle(deckOfCards);

noname
Friday, August 20, 2004

Take a deck, pick a card at random move the picked card to the top of a second (initially empty) deck ... repeat until every card has been picked and moved.

http://www.pagat.com/misc/52pickup.html

Christopher Wells
Friday, August 20, 2004

assuming rand() is random, I think this accomplishes the arbitrary goal of each card having an equal opportunity to be in each position (assume a function swap, that works as expected)

void Shuffle(Card cards[])
{
  srand((unsigned) time(NULL));

  for (int i = 0; i < 51; i++) {
      int j = rand() % (52 - i);
      if ( i != j ) {
          swap(cards, i, j);
      }
  }
}

Lou Franco
Friday, August 20, 2004

Las Vegas has determined that after 7 shuffles by the dealer, the cards are sufficiently random that a normal person would never be able to see a pattern.

Why would you need an algorythm to randomize them 100 times? Your game is being played by people, not other computers. A one-pass randomization is plenty good enough.

old_timer
Friday, August 20, 2004

In fact, after a few thousand iterations, chaos theory would start to grab hold, and you'd start to see more patterns emerging ;-)

Edward
Friday, August 20, 2004

old_timer,

You can simply change the 100 to a 7 if that suits you.  I was simply giving an example.

Poker
Friday, August 20, 2004

Assign a random weight (value) to each card, then use any algorithm of your choice to sort the cards based on the weight of each card.

It's simple but effective.

redwagon
Friday, August 20, 2004

"Assign a random weight (value) to each card, then use any algorithm of your choice to sort the cards based on the weight of each card.

It's simple but effective."

This is what most online card houses do nowadays.

Captain McFly
Friday, August 20, 2004

Once, there was an online casino that offered texas holdem games. They thought they were being slick by posting the shuffle code for folks to see. What they did not realize was that there was a pretty hefty bug in their code, so that instead of 52! (about 8*10^67) possible shuffled decks of cards, they had about 5000. As a result, players could determine in 5 cards (or less) what the deck was (thus knowing the position of all 52 cards in that deck), and what they should bet.

If this is homework, the answers by the other posters above are good enough. If real money is involved, then you better do some digging for either a real (hardware) RNG or look up some decent RNGs like Yarrow.

http://www.developer.com/java/other/print.php/10936_616221

Peter
Friday, August 20, 2004

This thread is amazing. Everything written is basically wrong or badly misguided.

So here we go:

Time() isn’t a suitable seed for dealing a random deck of cards. Hint: How many possible configurations of a deck are there?

Most library implementations of rand() aren’t suitable for cards. They’re usually badly biased in some way, frequently the low order bits aren’t very random.

There is no reason to shuffle 100 times. This is like sorting a list 100 times.

The reason Vegas uses 7 shuffles is because the way cards are shuffled by humans; divided into 2 piles and then interleaved back together. There is no reason to shuffle a computer deck 7 times.

The solution: Pickup Knuth Vol 2. Use the Knuth shuffle or if you want to be a little more efficient an incremental Knuth shuffle. Use a real random number generator not a standard library routine.

Dutch Boyd
Friday, August 20, 2004

How about approximately simulating the riffle shuffle used by most people:

1. Split the deck by randomly selecting a split point from a smallish range whose bounds are equidistant from the middle.

2. Randomly pick a starting 'half'

3. From that half, pull a smallish random number of cards in order from next to the split point and place on stack

4. Do the same thing with the other half (i.e. smallish random number of cards), putting the cards pulled on top of the stack

5. Repeat from (3) until all cards are consumed.

6. Deal from top of stack.

Note that you probably need to do several shuffles before dealing--perhaps another smallish random number.

Ron Porter
Friday, August 20, 2004

Why even resort to random numbers? I'll show you a routine that still produces a random shuffle, and i did it myself, just now,as I'm writing this.
1. Take 1 card from the top,and put it at the bottom.
2. Using increasing amounts of cards, take N cards from the top and insert them N cards from the bottom.  Thus, at the midpoint, you'll be taking the bottom 26 cards, and insert them between cards 13 and 14 of the other 26.
2. Increase N until N = 52.
3. Repeat, using N-1 cards from the bottom, mod the number of cards, until you cycle around again.  Voila, deck shuffled, no random numbers.  Remember to "collect" the cards from the players in the order they're returned, so that you get a different shuffle every time.  Of course, if they draw the same cards, you get the same cards back out, but you can always repeat the algorithm a few times. (a random number of times perhaps?  Heck no!  use a GUID.)

devinmoore.com
Friday, August 20, 2004


Dutch Boyd -

You are right. Amazing thread.

The guy who said pick a card at random, put it in another deck, then another card at random, ...

His works. Just it isn't in place two decks are needed.

I'm going to tell Mitch and Murray downtown about you guys.

One on-line poker site does this:

High quality cryptographically secure random number generator.

Frequently re-seeded from physically random sources.

For each shuffle: Attach a 256 random bit vector to each card.

Sort the deck based on the 256-bit vector.

For less demanding -

Assume 52 cards.

for I = 0 to 50

  J <- Pick a random number between I and 51

  Swap item in position I with  item in position J

The quality of the shuffle depends on the quality of your random number generator.

The seven shuffle determination was made by the statistician Persi Diaconnis, not by Las Vegas.

I don't know about Vegas, but at California poker clubs, 90% of the dealers don't come close.

Some clubs are installing automatic shuffling machines.

One reason: They collect $3 a hand. Anything that speeds up play is desirable.

dot for this one
Friday, August 20, 2004

> The guy who said pick a card at random, put it in another deck, then another card at random, ... His works. Just it isn't in place two decks are needed.

Alternative is to move the picked card to the top of the first (only) deck ... and exclude the top (i.e. the already shuffled) portion of the deck when you pick the next card to be moved.

Christopher Wells
Friday, August 20, 2004

You're all wrong! Card shuffles are NOT random (e.g. because of card clumping and sticking, and uneven rifling between left and right hands), and there is a great deal of research into it (google on shuffle tracking). Blackjack card-counters who also shuffle-track have done a lot of study and shuffle simulation to help predict clumps of face-cards in multi-deck shoes, especially right after new decks are introduced when the cards do not end up shuffled fully.

It's not just random distribution!

Blackjack Bob
Friday, August 20, 2004

I was actually just researching this very topic for an Auction 45s game I am working on.

This is a good link about shuffling a list: http://okmij.org/ftp/Haskell/perfect-shuffle.txt

and I settled on using this algorithm for my own game:

;; list-remove : list number -> list
;; returns list l with element at idx i removed
;; example: (list-remove '(1 2 3) 1) -> (1 3)
(define (list-remove l i)
  (if (zero? i)
      (cdr l)
      (cons (car l) (list-remove (cdr l) (- i 1)))))

;; shuffle : list -> list
;; returns a randomly shuffled list
;; example (caar (shuffle (fresh-deck52))) -> c
;; example (caar (shuffle (fresh-deck52))) -> d
;; exmaple (cadar (shuffle (fresh-deck52))) -> 4
;; example (cadar (shuffle (fresh-deck52))) -> a
(define (shuffle l)
  (if (null? l)
      '()
      (let ((idx (random (length l))))
        (cons (list-ref l idx)
        (shuffle (list-remove l idx))))))

This will shuffle a 'deck' of 'cards' tht are stored in a scheme list like this:

((H A) ... (H 2) (D A) ... (D 2) (C A) ... (C 2) (S A) ... (S 2))

It works by starting with a list of size M and picking a random number from 1 to M, and moving the card at that index to a new list. It repeats the same routine for M-1, M-2 ... 1.

When it is doen the old list is empty and the new list contains a shuffled 'deck'.

Here is the original thread that I found to get me started: http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&c2coff=1&safe=off&threadm=ad5sfl%245av%241%40oravannahka.helsinki.fi&rnum=1&prev=/groups%3Fhl%3Den%26lr%3D%26ie%3DUTF-8%26c2coff%3D1%26safe%3Doff%26selm%3Dad5sfl%25245av%25241%2540oravannahka.helsinki.fi

And this is the post that gave me the algorithm I chose to use:
http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&c2coff=1&safe=off&selm=ad5sfl%245av%241%40oravannahka.helsinki.fi

30 Days
Friday, August 20, 2004

Oh you mentioned not to use google. Sorry I should proably read thing more thoroughly.

The actuall Idea was one I got from hearing about shuffling machines.

What they do is have a machine that can shoot a compressed stream of air through a port the width of a playing card. Fill the machine with a 52 card deck, and it moves the port to a random spot (1/52) and blows that card into a collector.

It then picks a new random spot (1/51) and repeats until there is only one card left.

So really I just used google to figure out how to acomplish this in Scheme, but the thread I stumbled across is a very interesting discussion on rngs and card shuffling.

Oh, and don't worry if you don't understand the Haskell in Oleg's post, I don't either :)

30 Days
Friday, August 20, 2004

30 days - that works well when lists are natural for the language.

When you work with arrays and want to sort in place, then the algorithm I outlined seems about as good as it gets.

dot for this one
Friday, August 20, 2004

My approach was always to use qsort() with a callback function based on a random number generator.  It's much simpler, even if not the most efficient algorithm.

(It's likely to degrade to O(n^2).)

Reply to "Card shuffling routine"
Friday, August 20, 2004

Ah yes, to sort in place is another beast entirely.

Your solution to assign each 'card' an additional random value and sort based on that value is very elegant.

However if you are using 256bits per value aren't you more than doubling the size of your card array (assuming your 'card' data structure is < 256bits in size)?

In which place carrying around an extra array of 52 'card' sized elements could possiby use less memory.

Of course if your card dat strucutre also contains say the image of the card, than I think 256bits is very cost effective.

And I bet using qsort is much faster than my version for multiple shuffles...

30 Days
Friday, August 20, 2004

http://www.daylight.com/meetings/emug98/Sayle/sample.c

I know the OP said to not provide links but this one explains it best.

The base idea is to have a deterministic algorithm which generates numbers between 1-52 sufficiently randomly but which does not generate the same number twice or miss any number.  The same logic is behind doing pixel fading of pictures.

Code Monkey
Friday, August 20, 2004

An interesting question in probability theory (group theory too, as we're dealing with permutations) is how manyconsecutive  independant uniformly-randomly-chosen two-card swaps are needed to bring the resulting distribution of pack orders sufficiently close to uniform amongst all possible orders?

Essentially how many cards do you need to swap randomly to get a 'fair' shuffle ?

If you're interested I can dig up some links.

Matt
Friday, August 20, 2004

30 days,

The algorithm with the 256 bits is used by an online poker site. They obviously need higly randomized shuffling.

The method which I showed for having one step for each card in the deck is in-place, and mathematically valid, assuming the "random number generator" is in fact random. It also does about the least work one can imagine for shuffling.

dot for this one
Saturday, August 21, 2004

Going right brained for a moment: what are we shuffling the deck for?

Althought there are 52! orderings of a standard deck, there aren't necessarily that many relevent orderings.

For example, in bridge, each of four players receives 13 cards, but the order those cards are received doesn't matter, so the total number of unique deals D = 52! / ( 13! ) ^4.

In Texas holdem, the order of the undealt cards, the order the players receive the cards, and the order of the flop don't matter.  So if you have N players, you are only dealing M=2N+5 cards anyway, and have D = 52! / [ (52-M!)  * 2^N * 6 ]  distinct deals to worry about.

Simply pick a number in the interval [0,D), translate to a deal, move on to the next.

Danil
Saturday, August 21, 2004

Just swap each card in the deck with a random card in the deck.


    For i = 0 To 51
        n = Int(Rnd * 51)
        temp = deck(i)
        deck(i) = deck(n)
        deck(n) = temp
    Next i

Bella
Saturday, August 21, 2004

... which is exactly the algorithm that the developer.com article linked above shows is wrong.

scruffie
Sunday, August 22, 2004

Very nice article !

Bella
Sunday, August 22, 2004

It's a fairly simple exercise to show that:

for (i = 0... N-1) {
  int n = rand(N-i);
  swap(deck[i], deck[n+i])
}

results in a random deck of cards, where random is defined as every possible arrangement of cards is equally likely after running the algorithm, ASSUMING rand(X) returns a uniform distribution from 0..X-1 independent of previous calls to rand.

I worked with the group that published the flaw in the poker web sites shuffling algorithm (it was entertaining seeing CNN in our small office).  Their critical flaw wasn't with their shuffling algorithm (don't remember if they had a good one or not, wasn't really relevant), their flaw was how they generated their random numbers.  They used the built in random number generator for their language, which they seeded off of their clock (to the millisecond).  Since the random number generator used  a 32 bit seed, there were only 4 billion possible hands that could be generated (they reseeded before each shuffle).

You could narrow this number down further by knowing the time on their system, which they so helpfully provided on one of their web pages.  Even assuming an error range of a couple seconds, this meant there were really only a few thousand possible starting seeds.  Running their shuffle algorithm, combined with the known rand algorithm, for each starting seed resulted in a few thousand candidate decks.  Then it was a just a simple matter of comparing each deck with the dealt cards that could be seen, and you could choose which deck was correct and therefore what cards will follow.



As a side note, bridge tournaments sometimes are played with "computer" hands, i.e. hands that were generated by a computer shuffling rather than people really shuffling.  There is a common perception among players that these "computer" hands aren't really random because distributions seem to be different than when  "really" shuffled.  One of the theories (besides the obvious one that it is just psychological), is that the human shuffled cards are rarely shuffled thouroughly and so are actually much less random than the "computer" hands.

madking
Monday, August 23, 2004

Contrary to popular belief, 7 riffle shuffles are not sufficient to randomize a deck of cards.  I've lost the links now, but there are poker articles that discuss this, and some theoretical papers that have been written on the subject.

Required
Tuesday, August 24, 2004

It seems to work

Tony
Friday, August 27, 2004

*  Recent Topics

*  Fog Creek Home