Exploring the Unknown: Testing Functions with a Random Factor

In software development, testing should be an integral part of the process because it guarantees that the code is working as expected and will continue to do so after being subjected to changes.

Testing is especially important when trying to solve complex problems, because we may come up with different algorithms to solve the same issue. Exact algorithms are easy to test because, for a given input, we always get the same output. The problem comes when testing algorithms that add randomness, which is often the case in metaheuristic algorithms. This article will tackle Unit Testing for functions that have a random factor.

Do you need to test thoroughly?

When testing a piece of code with a random factor, programmers need to understand the context in which randomness is used. For example, if you are generating a random ID for a user, check if the ID is generated (not null) and if the ID format is the intended one, but the actual value is not as important.

Ranges are a good example of this. For instance, when rolling a six-sided die, we know the result should be between 1 and 6. If we get a value of 7 or -5, something needs to be fixed. The following TypeScript code showcases how to test this behavior, adding iterations to guarantee that the result is within the range after multiple executions, using the Jest framework.

it("rolls a 6 sided die multiple times", () => {
  const ITERATIONS = 100;
  const sixSidedDie = new Die(6);
  for (let index = 0; index < ITERATIONS; index++) {
    const rollResult = sixSidedDie.roll();
    expect(rollResult).toBeGreaterThan(0);
    expect(rollResult).toBeLessThanOrEqual(6);
  }
});

At last, there are instances where the obtained value is important, such as the aforementioned metaheuristic algorithms. I have faced the importance of testing in this circumstance because I developed several algorithms that have to take a random element from a list.

The objective of this project was to provide good quality solutions to the Cross-Docking Assignment Problem (CDAP) in a reasonable computing time, and the random factor was present in the algorithms that generate initial solutions (ConstructiveMaxCapacityRandom and ConstructiveMinCapacityRandom).

Testing randomness: determinism

The first approach to test algorithms that work with randomness is to use a deterministic approach. This means that it returns the same output in every execution. Sometimes, randomness is used to select between n elements from a list, so defining n = 1 should always return the same value. For example, in the aforementioned Cross-Docking Assignment Problem project, an algorithm had to select a random door among a set of n with maximum capacity per iteration (where n is the parameter door_list_number). The tests I developed for checking the correctness of the algorithm set the value of the variable door_list_number as one so it always gets the highest capacity door and generates a predictable output.

One way to force deterministic behavior is to mock the result of the specific function that returns the random value. This allows the programmer to test multiple paths and to see how the algorithm acts with different values. Mocking is preferable to establishing a seed for the random number generator because it allows the programmer to be more specific.

For instance, when developing a poker game, we could establish a rule where the user doubles his or her points after getting two straight flushes in a row. In this example, instead of generating a random hand for the player, we would mock the hand and force it to be a straight flush, and the test will check if the points are doubled. For example, if we design a Poker class that uses a CardDealer, we could implement the following test:

it("doubles the points when getting two straight flushes in a row", () => {
  const DIAMOND_STRAIGHT_FLUSH: Card[] = [
    { suit: Suit.DIAMONDS, rank: Rank.SEVEN },
    { suit: Suit.DIAMONDS, rank: Rank.EIGHT },
    { suit: Suit.DIAMONDS, rank: Rank.NINE },
    { suit: Suit.DIAMONDS, rank: Rank.TEN },
    { suit: Suit.DIAMONDS, rank: Rank.JACK },
  ];
  // ...
  const player1Name = "Player1";
  const player2Name = "Player2";
  const cardsAmount = 5;
  const poker = Poker.create([player1Name, player2Name], cardsAmount);
  jest
    .spyOn(CardDealer, "deal")
    .mockReturnValueOnce(KINGS_PAIR)
    .mockReturnValueOnce(DIAMOND_STRAIGHT_FLUSH)
    .mockReturnValueOnce(FIVE_PAIR)
    .mockReturnValueOnce(CLUBS_STRAIGHT_FLUSH);
  const firstMatch = poker.play();
  const secondMatch = poker.play();
  expect(secondMatch.winner.getName()).toEqual(player2Name);
  expect(secondMatch.winner.getScore()).toEqual(4);
}

True randomness

At last, there are a few instances where a deterministic approach is insufficient. For example, a roulette game should be completely random and not leave room for determinism because some players could take advantage. When developing tests in this scenario, the main approach is to run the program multiple times and check that it follows a reasonable distribution.

Checking the distribution of the numbers does not guarantee randomness, which is why we should also check for patterns. For example, if we detect a pattern after multiple executions of the same function, the output is not random. This can be achieved by performing visual or statistical tests, where visual tests consist of generating a large bitmap image based on the numbers received and checking for repetitions, and statistical tests apply statistics to help find repeating patterns in a sequence of numbers (frequency tests, discrete Fourier transform, aperiodic tests, linear complexity tests, etc.).

Another use case for randomness in testing is to check how resilient to unexpected failures a system is (chaos engineering). A good example is Chaos Monkey, developed by Netflix. It is used for randomly terminating instances in production, which forces the developers to design a system that can withstand such conditions. For example, if a server failure severely impacts the application's performance, that could indicate that the system should be less dependent on a single server. Ideally, when terminating random instances, we expect performance degradation to some extent, but the application should still be running and performing automatic processes for diagnosing and fixing the problem.

Conclusion

It isn't easy to work with randomness, especially when doing automatic tests where we want consistent results. In this article, we have seen some ways to deal with this test. The first step is to analyze the behavior we expect and design the tests accordingly. We should find deterministic approaches unless we want to test true randomness in cases such as checking that we get true random outputs or chaos engineering.

Repository: http://github.com/VirenAcidTango/testing-with-randomness