8

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

RAVE node selection

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?

2

3 Answers 3

6

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.

5
  • 4
    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
    Aug 1 at 20:39
  • 2
    @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).
    – Doc Brown
    Aug 2 at 8:30
  • 1
    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
    – Doc Brown
    Aug 2 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?
    – Doc Brown
    Aug 2 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
    Aug 2 at 10:09
5

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)

1
  • 3
    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
    Aug 1 at 20:34
4

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 (lets call them Treepolicy1, Treepolicy2 and Treepolicy3), you will often keep them all "alive" in code in parallel (and not like different versions of the same compontent in version control). That will result in stable unit tests for each of them. The steps are (hopefully) simple enough you can reuse some of the tests when extending from Treepolicy #1 to #2, and further. Moreover, the steps might be simple enough you can predetermine the output and write some tests before writing new code, which let you allow to do some TDD.

That way, your unit tests will help you to validate you don't break anything in the other steps whilst you are changing one of the steps. They will also help you to validate you don't break anything when you refactor Treepolicy1, Treepolicy2 and Treepolicy3 to use some common code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.