Determining how well a deck is shuffled

Question

I am doing a small poker program and I want to determine how well a deck is shuffled. I have a List with 52 cards then I run my shuffling algorithm and I want to be able to determine how well the deck is shuffled on some scale. Does someone have an idea how to do this? Thanks

EDIT: Wow. A lot of responses. All good but not exactly what I was looking for. That is my fault for not specifying my question further. But I think Saran is closest to what I actually want. Let me specify.

I do NOT want a "perfect" shuffle straight away. I already read up on that and I implemented Fisher-Yates. That one is pretty good at giving "perfect" shuffle. What I AM trying to do is to simulate a real world situation where friends are playing texas hold-em and the dealer takes the deck and shuffles it using riffle shuffle mixed with other shuffles. In the end, what I want is a way to measure the difference between real world shuffles.

An example. Assume the deck is always fresh (ace to king suited, then next suit ace to king for all four suits). Joe takes the deck and does 2 riffle shuffles with one cut in between. Peter does 5 stripping shuffles. I want to find a way to see which one shuffles the deck "better".

The more I think about it the more I think it is very very veeery hard to determine.

Thanks again.

EDIT 23.10.2013

Here is the method I came up with, combining Sarans idea with mine:

 public int checkShuffle(List<Card> cardDeckToCheck,int[] previousOrder)
    {
        // Higher is worse? Sure.
        int score = 0;

        for (int i = 0; i < cardDeckToCheck.Count; i++)
        {
            Card cardToCheck = cardDeckToCheck[i];
            Card cardToLeft = null;
            Card cardToRight = null;

            // Should cost more since the card has not moved at all.
            // For this I need an array that shows me the arangement of the deck before shuffling.
            if(cardToCheck.index == previousOrder[i])
            {
                score += 3;
            }

            if (i == 0)
            {
                Console.WriteLine("i == 1");
                cardToRight = cardDeckToCheck[i+1];
                // if the card we are checking is one lower or one higher than the card to the right
                if(Math.Abs(cardToCheck.index - cardToRight.index) == 1)
                {
                    score++;
                }
                continue;
            }

            else if (i == cardDeckToCheck.Count-1)
            {
                Console.WriteLine("i == carddecktocheck.count-1");
                cardToLeft = cardDeckToCheck[i - 1];
                // if the card we are checking is one lower or one higher than 
                if (Math.Abs(cardToCheck.index - cardToLeft.index) == 1)
                {
                    score++;
                }
                continue;
            }

            else
            {
                cardToLeft = cardDeckToCheck[i - 1];
                cardToRight = cardDeckToCheck[i + 1];
                // if the card we are checking is one lower or one higher than 
                if (Math.Abs(cardToCheck.index - cardToLeft.index) == 1)
                {
                    score++;
                }
                if (Math.Abs(cardToCheck.index - cardToRight.index) == 1)
                {
                    score++;
                }
                continue;
            }

        }
        return score;
    }

I first record how the deck looks like into an int array then I shuffle the deck and then I run this method with the shuffled deck and the previous order of the deck. Like so:

int[] previousOrder = getCurrentOrder(deck.getDeck());
deck.setDeck(riffleShuffle2(3));
textBoxShuffleness.Text = "" + checkShuffle(deck.getDeck(), previousOrder);
displayDeck(deck);

When I start with an unshuffled deck and run the riffle shuffle method 5 times I get 70,33,28,5,10. When I start with an unshuffled deck and run the Durstenfeld shuffle method 5 times I get 5,0,7,11,7.

Those results are very much what I would expect.

If someone can find something wrong with this method then I would appreciate if you would comment :) Thanks

Answer 1

To have any hope, you would need to run your shuffling program over and over, always starting with the same initial deck, and compare the results.

If it is completely fair, you expect that any given card has a 1-in-52 chance of ending up in any spot after shuffling.

If there is bias, you'd see that it ends up in some spots more frequently than others.

Of course, some variation from the ideal 1-in-52 is expected.
The amount of variation that is acceptable is predictable by stats and various confidence intervals. (95%? 97%?)

And even if you got a perfect distribution, that doesn't mean your shuffling is random.
(Imagine a shuffle-algorithm that simply rotates the deck by one card on each successive shuffle.... it would have perfect 1-in-52 results, but wouldn't be at all random)

Another aspect to look for is correlation between cards.
For example, the final location of the Ace-of-Spades and the King-of-Spades should be completely uncorrelated.
A bad shuffling algorithm could move those two cards around together, resulting in high correlation. Checking for the correlation of every card against every other card is computationally expensive, but should be a simple algorithm.

I think the end result is that you cannot prove your algorithm is a fair/good shuffle. You can only set up various tests to look for "bad" shuffles (non-uniform distribution, or high correlations of card positions). If you pass all the tests for bad-shuffles, it doesn't mean your algorithm is not flawed in some other way that the tests didn't cover.
But it does give you increasing confidence.

There may be an even better way to test for randomness, but it is computationally impossible.

As the Coding Horror Blog entry points out, a far better way may be to run your algorithm against very small decks of cards (the article uses a 3-card deck), and carefully evaluate those results. With only 3 cards it should be much easier to trace all paths, and see if all outcomes are equally likely.