# Learning a Prior for Monte Carlo Search by Replaying Solutions to Combinatorial Problems

arXiv: https://arxiv.org/abs/2401.10431 · HTML: https://mlsanity.com/paper/2401.10431/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 34 references that are in the map.
- First posted on arXiv 19 Jan 2024.

## Builds on (most cited first, 5 of 5)

- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Designing RNA Secondary Structures is Hard](https://mlsanity.com/paper/1710.11513/) (2017)
- [Generalized Nested Rollout Policy Adaptation](https://mlsanity.com/paper/2003.10024/) (2020)
- [Monte Carlo Inverse Folding](https://mlsanity.com/paper/2005.09961/) (2020)
- [Monkey Business: Reinforcement learning meets neighborhood search for Virtual Network Embedding](https://mlsanity.com/paper/2202.13706/) (2022)

## Built on by (most cited first, 4 of 4)

- [The Montparnasse Algorithm for RNA Design](https://mlsanity.com/paper/2606.07562/) (2026)
- [Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problems](https://mlsanity.com/paper/2609.00859/) (2026)
- [Eterna is Solved](https://mlsanity.com/paper/2505.02110/) (2025)
- [Adaptive Bias Generalized Rollout Policy Adaptation on the Flexible Job-Shop Scheduling Problem](https://mlsanity.com/paper/2505.08451/) (2025)

## Abstract (arXiv)

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.