Testing a card deck shuffler

Question

I have a class PlayingCard which represents a particular playing card. I have another class, Deck, which contains a list of PlayingCard objects. Deck has a shuffle() method that randomizes the card order.

I would like to write some unit tests for the shuffle() method, but I'm at a bit of a loss. I'd prefer the test to not care about the internals of just how the shuffle is done, but I want them to be good tests.

How do I best unit test when randomness is involved?

Answer 1

1. Create a list.
2. Create a deep copy of that list.
3. Shuffle the first list.
4. Assert list1 != list2

Add more descriptive tests as you require. Quality of the shuffle, randomness, etc...

As Alex Martelli pointed out, you can perform a statistical analysis of the sorting to confirm it is sorted to the degree you expect.

The best outcome is that every card position has changed. Meaning, every one of the 52 cards is now in a new position. You could take my above approach, record the number of elements that are different and set a threshold for the test.

Expect at least 20 cards to be in new positions. Create the list, copy it, sort it and then compare it. If the result is less than 20, fail, otherwise pass.

Answer 2

One approach is to make statistical tests; after each shuffle check for correctness (the set of cards must not have been changed, only the order), and collect statistics about some random variables ("position of the 7 of diamonds", "is the 5 of clubs before or after the 8 of hearts", and the like) to be tested after a suitable number of shuffles by Student's t-test and other statistical hypothesis-testing approaches.

Answer 3

A good question. First, an absolute pass/fail test: after shuffling, the multiset (e.g. compare after sorting) must be unchanged.

To test the randomness, you'll need to do sufficient shuffles that the probability of a false "not sufficiently random" failure is vanishingly small. For instance:

There is a .0000001% chance that in 10000 shuffles, that a particular card is in one of the given 52 slots less than (1-e)/52 or greater than (1+e)/52. (for some small e, I don't know offhand how to compute it).

A correct program may "fail" such a test, but shouldn't fail very often.

With respect to shuffling; one common failure is to do this:

for i from 1..52: choose a random j from 1..52 and swap card i with card j (wrong)

That doesn't give you any permutation with equal probability; this, however, does:

for i from 1..52: choose a random j from i..52 and swap card i with card j (right)

Answer 4

Since I haven't tried this I can't say immediately how practical it is, but it should be possible to make unit tests with small decks and a special deterministic random-number-generator, run exhaustively such that the shuffler should produce each possible permutation once.

Answer 5

There was the subject of an exhaustive (or exhausting) thread on the Yahoo Groups TDD list a few years ago. Ron Jeffries has some useful insights but but it is best to start at the top.

Answer 6

Your goal is to test shuffle(). Since you know how you constructed shuffle(), it would be a deterministic unit test of your initial deck vs. the shuffled deck if you were able to know the series of numbers generated.

This is a case where injecting a method into your Deck() class during testing can make your shuffle function deterministic.

Build your class to use the random() function by default but to use a predetermined, number generating function when injected. For example, in Python you can do:

class Deck():
   def __init__(self, rand_func = random.random):
      self._rand = rand_func
   def rand(self):
      return self._rand()

When simply using Deck with no arguments, you get the random number expected. But if you craft your own random number function, you can generate your predetermined sequence of numbers.

With this construction you can now build an initial deck (whatever size you want) and a list of random numbers (again, whatever size you need) and you will know what to expect as output. Because shuffle() doesn't change between the injected version and the truly random version you can unit test shuffle() deterministically and yet have random behavior at runtime. You can even generate multiple different number sequences if there are corner cases you want to test.

With respect to the other's answers involving statistical modeling: I think those are acceptance level tests to prove the correctness of the "shuffle" algorithm, but it doesn't deterministically unit test the function shuffle()'s implementation.