JUnit Test method with randomized nature

Question

I'm working on a small project for myself at the moment and I'm using it as an opportunity to get acquainted with unit testing and maintaining proper documentation.

I have a Deck class with represents a deck of cards (it's very simple and, to be honest, I can be sure that it works without a unit test, but like I said I'm getting used to using unit tests) and it has a shuffle() method which changes the order of the cards in the deck.

The implementation is very simple and will certainly work:

public void shuffle()
{
    Collections.shuffle(this.cards);
}

But, how could I implement a unit test for this method. My first thought was to check if the top card of the deck was different after calling shuffle() but there is of course the possibility that it would be the same. My second thought was to check if the entire order of cards has changed, but again they could possibly be in the same order. So, how could I write a test that ensures this method works in all cases? And, in general, how can you unit test methods for which the outcome depends on some randomness?

Cheers,

Pete

Answer 1

You could shuffle repeatedly, keeping track of how many times the Ace of spades (or some other card, or all other cards) ends up as the first card in the deck. Theoretically the card should end up on top about 1 out of 52 shuffles. After all the data has been gathered, compare the actual frequency to the number 1/52 and check if the difference (absolute value) is lower than some chosen epsilon value. The more you shuffle, the smaller your epsilon value can be. If your shuffle() method puts the card on the top within your epsilon threshold, you can be sure it is randomizing the cards as you would like.

And you don't have to stop just at the top card. You can test if each location in the deck gives the same results. Do it with one card, do it will all cards, it probably doesn't matter. It might be overkill, but it would guarantee your shuffle() is working correctly.

Answer 2

Firstly, let's think about the probabilities involved:

1. You can't guarantee that the shuffle won't place the cards in exact order. However, the probability of doing this with a 52-card deck is 1 / 52! (i.e. it's minimal and probably not worth worrying about.)

2. You definitely will need to check the whole deck, though because the probability of the top card being the same as it was before the shuffle is 1 / 52.

For the general case, and assuming you're using the java.util.Random number generator, just initialise it with the same seed. Then the output for a pre-determined input should then be repeatable.

However, specifically for this case, assuming you haven't implemented your own List I don't really see the point in testing Collections.shuffle(List<?> list) or Collections.shuffle(List<?> list, Random rnd) (API link) as these are just part of the Java API.

Answer 3

I've worked on random numbers in a modeling and simulations framework and stood before a similar problem: How can I actually unit-test our PRNG implementations. In the end I actually didn't do it. What I did instead was to perform a few sanity checks. For example, our PRNGs all advertise how many bits they generate, so I checked whether those bits actually did change (with 10k iterations or so) and all other bits were 0. I checked for proper behavior concerning seeds (initializing the PRNG with the same seed must produce the same sequence of numbers), etc. I then decided to put the actual randomness tests into an interactive UI so they can be tested whenever desired but for unit tests a non-deterministic outcome isn't that nice, I thought.

Answer 4

You're actually delegating away all the hard work to the java.util.Collections class. This is a central class in Java's collection API and you should just assume that it works like you probably do with the java.lang.String class.

I would rather recommend to code against interfaces and mock/stub away your implementation class with the shuffle() method. Then you can just assert that your calls on the shuffle() method are actually called from your test instead of testing exactly the same as the Sun/Oracle guys have tested thorough before.

This enables you to focus more on testing your own code where 99.9% of all the bugs probably are located. And if you for example replace java.util.Collections.shuffle() method with one from another framework or your own implementation, your integration test will still work!

I understand that you're doing this because you want to learn and I believe the knowledge about stubbing/mocking away logic from other frameworks are very useful as part of your testing knowledge.

Answer 5

Most people seem to be of the opinion that you should test what you're testing. By that I mean what you're building (or integrating, when you're making sure a third-party library actually does what it says it does).

But you should not test the Java language itself.

There should be some testing principle like "Don't Test PlusEquals".

Answer 6

Asserting whether your shuffle method actually shuffles the cards is very hard if not impossible. Default random number generators are only random to a certain degree. It's impossible to test whether you're satisfied with this degree of randomness because it would take too much time. What you're actually testing is the random number generator itself which doesn't make much sense.

What you can test however, are the invariants of this method.

• If you exit the method, there should be the exact same number of cards in the deck as when you entered it.
• The shuffle method should not introduce duplicates.

You can of course create a test that checks that in a sequence of n shuffles there are no duplicate decks returned. But once in a while this test may fail (however unlikely, as already stated in other answers).

Something else to take into account is the random number generator itself. If this is just a toy project, java.util.Random is sufficient. If you intend to create some online card game, consider using java.security.SecureRandom.

Answer 7

Another approach would be to use the shuffle(List<?> list, Random random) method and to inject a Random instance seeded with a constant.

That way your JUnit test can run a series of calls and check the output to be the expected output.

The normal implementation of your class would create a Random instance which is unseeded.

Answer 8

Interesting question. In my opinion the best way would be to store each "shuffle" in a collection, then compare after each shuffle if your deck matches any of the previous "decks" in the collection.

Depending on the ammount of "Randomness" you require you will increase the ammount of shuffled decks you store in that unit test i.e. after 50 shuffles you would have a collection of 50 "decks"

Answer 9

I suppose you have 52 cards in your deck. The possibility of getting the same order in two subsequent calls is extremely low, so I wouldn't bother about it too much. But, if you do start getting similar decks multiple times, I think it's safe to say you have some problems with your random number generator.

So, the answer: check that the order is different for the whole deck.

Also, I think that you can safely make it a requirement for your shuffle() method not to return the cards in the same order twice in a row. And if you want to absolutely make sure to follow that requirement, you can check for similarity in the method implementation.