Nested Depth Search

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.

Authors

• Junkang Li NukkAI, Paris, France Normandie Univ.; UNICAEN, ENSICAEN, CNRS, GREYC, 14 000 Caen, France
• Tristan Cazenave Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE, F-75016 Paris, France
• Swann Legras NukkAI, Paris, France
• Arthur Queffelec WorldWise, Paris, France
• Veronique Ventos NukkAI, Paris, France

Keywords

No keywords are indexed for this paper.