# Towards Tackling MaxSAT by Combining Nested Monte Carlo with Local Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 26 Feb 2023.

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

- [Generalized Nested Rollout Policy Adaptation](https://mlsanity.com/paper/2003.10024/) (2020)
- [Tackling Morpion Solitaire with AlphaZero-likeRanked Reward Reinforcement Learning](https://mlsanity.com/paper/2006.07970/) (2020)
- [Adaptive Warm-Start MCTS in AlphaZero-like Deep Reinforcement Learning](https://mlsanity.com/paper/2105.06136/) (2021)
- [Assessing the Potential of Classical Q-learning in General Game Playing](https://mlsanity.com/paper/1810.06078/) (2018)
- [Warm-Start AlphaZero Self-Play Search Enhancements](https://mlsanity.com/paper/2004.12357/) (2020)
- [Analysis of Hyper-Parameters for Small Games: Iterations or Epochs in Self-Play?](https://mlsanity.com/paper/2003.05988/) (2020)
- [Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search](https://mlsanity.com/paper/2005.11335/) (2020)

## Abstract (arXiv)

Recent work proposed the UCTMAXSAT algorithm to address Maximum Satisfiability Problems (MaxSAT) and shown improved performance over pure Stochastic Local Search algorithms (SLS). UCTMAXSAT is based on Monte Carlo Tree Search but it uses SLS instead of purely random playouts. In this work, we introduce two algorithmic variations over UCTMAXSAT. We carry an empirical analysis on MaxSAT benchmarks from recent competitions and establish that both ideas lead to performance improvements. First, a nesting of the tree search inspired by the Nested Monte Carlo Search algorithm is effective on most instance types in the benchmark. Second, we observe that using a static flip limit in SLS, the ideal budget depends heavily on the instance size and we propose to set it dynamically. We show that it is a robust way to achieve comparable performance on a variety of instances without requiring additional tuning.