Learning a Prior for Monte Carlo Search by Replaying Solutions to Combinatorial Problems
This provides a general method for improving search efficiency in combinatorial optimization, though it is incremental as it builds on existing prior-based approaches.
The authors tackled the problem of automatically generating priors for Monte Carlo Search in combinatorial problems, achieving large performance gains without computational cost at playout time.
Monte Carlo Search gives excellent results in multiple difficult combinatorial problems. Using a prior to perform non uniform playouts during the search improves a lot the results compared to uniform playouts. Handmade heuristics tailored to the combinatorial problem are often used as priors. We propose a method to automatically compute a prior. It uses statistics on solved problems. It is a simple and general method that incurs no computational cost at playout time and that brings large performance gains. The method is applied to three difficult combinatorial problems: Latin Square Completion, Kakuro, and Inverse RNA Folding.