# Combining Simulated Annealing and Monte Carlo Tree Search for Expression Simplification

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2013.

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

- [LLM-First Search: Self-Guided Exploration of the Solution Space](https://mlsanity.com/paper/2506.05213/) (2025)
- [Geometry-Aware MCTS for Extremal Problems in Combinatorial Geometry](https://mlsanity.com/paper/2606.26399/) (2026)
- [Learning to Play: Reinforcement Learning and Games](https://mlsanity.com/paper/2610.17391/) (2026)

## Abstract (arXiv)

In many applications of computer algebra large expressions must be simplified to make repeated numerical evaluations tractable. Previous works presented heuristically guided improvements, e.g., for Horner schemes. The remaining expression is then further reduced by common subexpression elimination. A recent approach successfully applied a relatively new algorithm, Monte Carlo Tree Search (MCTS) with UCT as the selection criterion, to find better variable orderings. Yet, this approach is fit for further improvements since it is sensitive to the so-called exploration-exploitation constant Cp and the number of tree updates N. In this paper we propose a new selection criterion called Simulated Annealing UCT (SA-UCT) that has a dynamic exploration-exploitation parameter, which decreases with the iteration number i and thus reduces the importance of exploration over time. First, we provide an intuitive explanation in terms of the exploration-exploitation behavior of the algorithm. Then, we test our algorithm on three large expressions of different origins. We observe that SA-UCT widens the interval of good initial values Cp where best results are achieved. The improvement is large (more than a tenfold) and facilitates the selection of an appropriate Cp.