# How can you write unit tests for an opaque/nondeterministic algorithm like Monte Carlo tree search?

I've written an implementation of the UCT1 Monte Carlo Tree Search algorithm for selecting moves in a two-player game. In the future, I'd like to expand this implementation to use more advanced tree search techniques like RAVE to be able to search more efficiently. I'm trying to figure out how to write unit tests for this kind of highly complex "black box" code.

The basic idea of monte carlo search is to play thousands of random games and select promising search nodes based on previous game outcomes. The basic pseudocode for tree search (from "A Survey of Monte Carlo Tree Search Methods" by Browne et al.) would be:

``````function UCTSEARCH(s₀)
create root node v₀ with state s₀
while within computational budget do
v₁ ← TREEPOLICY(v₀)
∆ ← DEFAULTPOLICY(s(v₁))
BACKUP(v₁, ∆)
return 𝒂(BESTCHILD(v₀, 0))
``````

Using a Tree Policy to find a node in the tree which has not previously been explored, a Default Policy to score that node, e.g. by playing random games until termination, and a backpropagation step to apply reward values to parent nodes. Various algorithms exist to modify each of these steps, e.g. the selection function for RAVE (per wikipedia) maximizes

I'm finding it very difficult to write unit tests for code of this nature. From the perspective of a caller of this function, its behavior is opaque and non-deterministic, since it relies on random number generation. I also want to expand and modify the algorithm in the future, meaning all the implementation details are likely to change over time.

What strategy would you use to write unit tests for an algorithm like this?

• You may find some further tips in Unit testing for a scientific computing library. Commented Aug 1, 2022 at 20:04
• After rereading the question again, I removed my "duplicate close vote". The issue here is not just how to test non-deterministic code. It is moreover the combination of non-determinism and an algorithm which is too complex to be unit-tested efficiently as a whole. Commented Aug 2, 2022 at 8:27

it relies on random number generation

This is easy to solve - you ensure your code uses a pseudo-RNG for which you can precisely the seed the state. You now have deterministic behaviour.

(You should almost certainly be doing this anyway, or you are adding to the replication crisis)

• While making RNG state explicit is good (and a necessary precondition for advanced testing techniques), this isn't perfect in my experience. It tends to lead to a style of testing where you compare the output of the algorithm for exact equivalence with a golden master created from a previous execution. This is useful for finding unexpected regressions, but not useful for determining whether the output is correct. To make executions more robust, I recommend using splittable RNGs such as the Xoshiro family, so that changes to the RNG state can be scoped.
– amon
Commented Aug 1, 2022 at 20:34

This seems like a proper use case for Property Based Testing, a la Haskell's QuickCheck. In property based testing, you start by thinking of properties you expect your code to have. For instance, if you were testing a function to reverse the order of a list, you might brainstorm the following

1. The reverse of a list has the same length as the list.
2. The reverse of the reverse of the list is identical to the original list.
3. The reverse of a list has the same elements as the list.
4. etc.

You would then have test cases which generate random lists and check whether these properties hold, failing and printing the offending cases. If your function is nondeterministic you would also want to print out a seed on failure so that you can replicate these failures.

Note that so long as you state these properties in ways that depend only on the externally visible behavior of your code rather than its implementation details, you can treat your code as a black box. Similarly, careful choice of properties can ensure the tests are robust against improvements to the code.

The language you are implementing this in may or may not have a library like QuickCheck. If it does not, it is simple enough to rig one up. All you need is some code for randomly generating inputs to your method and a unit testing system. Robust property based testing libraries like QuickCheck will have some features that help to generate minimal counterexamples to properties, which can make it easier to understand what is failing and why. This comes down to having a notion of size of input (starting small and gradually generating larger inputs) and functionality to shrink a counterexample to try to find a smaller one.

• In this scenario, an example of a useful property would be “assuming a constant problem and RNG seed, increasing the evaluation budget always results in a solution that is at least as good”. That would be a “metamorphic” property describing a relationship between multiple algorithm executions.
– amon
Commented Aug 1, 2022 at 20:39
• @amon: not a bad idea. However, for a complex algo like MCS, increasing budget might not always lead to better solutions, only on average. Sometimes the behaviour of such algorithms can be pretty counter-intuitive (I have first-hand experience with this). Commented Aug 2, 2022 at 8:30
• This sounds nice in theory, but in reality, I think it is not easy to find robust properties for an algorithm like MCTS which are really significant (there should be at least a few properties which are really different for other two-player move generating algorithms). It is probably easy to find some meaningless properties to test, but those would probably apply to a lot other, simpler move-generators Commented Aug 2, 2022 at 9:27
• @amon: ... and the elephant in the room is: how do you evaluate the quality of a "solution" (=move) for a two player game like Chess or Go? Commented Aug 2, 2022 at 9:28
• @DocBrown Yes, for this property to work you'd need a node selection strategy that does not depend on the budget. For example, it doesn't work if budget is divided “⅓ on that subtree, ⅔ on that other subtree”. However, strategies of the kind “while I have budget: given my current knowledge, what node should I inspect next?” should work. Such greedy strategies are not theoretically optimal, but they're very good in practice. Evaluation of a solution is not a problem by design, since the algorithm already involves an evaluation policy. For testing the search, evaluation could be mocked away.
– amon
Commented Aug 2, 2022 at 10:09

How do you eat an elephant? One bite at a time.

What I am trying to say here is, for unit testing a complex algorithm like Monte Carlo Tree Search, it is probably best not to treat it in a black-box fashion as a single unit.

As you scetched in your question, this algorithm has some clearly separated parts. Each of its parts ("Treepolicy", "Defaultpolicy", "Backup", "Bestchild") has a clear input and output, hence it can (and probably should) be unit tested on its own (this works best when those parts are not implemented in a procedural fashion, but in a functional one). Note only one of those steps ("Defaultpolicy") has non-deterministic behaviour, which can be approached by replacing the non-deterministic pseudo-random generator by a deterministic one during tests.

Of course, once you finished your unit tests, you can also add integration tests afterwards to test the algorithm "as a whole". That can help you to verify the integrated units work together and produce some result of the desired form. However, since you wrote

I also want to expand and modify the algorithm in the future, meaning all the implementation details are likely to change over time.

an integration test against some expected output will only be of restricted value. Such tests can help you finding regressions when you are going to change things often in the algorithm which shall not change the results, but in this case, you are going to experiment with modifications of this algorithm where the results will be different and cannot easily predetermined. Hence, as long as you are experimenting with it, it will be probably more efficient to do the integration tests manually or "semi-automatic".

Instead, when you experimenting with different treepolicies, you want to be sure you don't change accidentally something in the other parts. This could happen, for example, when for implementing a different treepolicy you may have to change something in a common, underlying component (for example, the tree data structure). That's where unit test for the other components show their value.

Or, lets assume you have three Treepolicy1, Treepolicy2 and Treepolicy3 all "alive" in code in parallel, since you want to compare them. Here the chances are very high they share common parts you might want to refactor, for which unit tests are helpful. Moreover, those policies might be simple enough you can predetermine the output for a not overly complex input, which could make TDD feasible.