  We consider the automatic online synthesis of black-box test cases from
functional requirements specified as automata for reactive implementations. The
goal of the tester is to reach some given state, so as to satisfy a coverage
criterion, while monitoring the violation of the requirements. We develop an
approach based on Monte Carlo Tree Search, which is a classical technique in
reinforcement learning for efficiently selecting promising inputs. Seeing the
automata requirements as a game between the implementation and the tester, we
develop a heuristic by biasing the search towards inputs that are promising in
this game. We experimentally show that our heuristic accelerates the
convergence of the Monte Carlo Tree Search algorithm, thus improving the
performance of testing.
