  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.
