Nested Depth Search

Abstract Nested Monte Carlo Search (NMCS) has numerous applications, ranging from chemical retrosynthesis to quantum circuit design. We propose a generalization of NMCS that we named Nested Depth Search (NDS), in which a fixed depth search is used during a higher-level playout to generate the states sent to lower-level exploration. We establish the runtime of NDS and provide algorithms to compute the exact probability distribution of sequences generated by NDS. Experiments with the Set Cover problem and the Multiple Sequence Alignment problem show that NDS outperforms NMCS with the same time budget.